摘要
该文基于k Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法 ,并对其容错性进行概率分析 ;在每个结点具有独立的出错概率的假设条件下 ,推导出路由算法成功返回由正确结点组成的路径的概率 .该文运用严格的数学推理 ,证明了Mesh网络结点出错概率只要控制在 1 .87%以内 ,则对于多达几十万个结点的Mesh网络 ,提出的路由算法具有 99%的概率确保找到正确结点组成的路径 .路由算法的时间复杂性是线性的 .模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度 .
Mesh networks are very important network topologies in massively multiprocessor parallel systems. With the continuous increasing in network size, routing algorithm in large size networks with faults has become unavoidable. This paper mainly focuses on fault-tolerant routing algorithm on mesh networks. Based on the concept of k-submesh, this paper proposes two simple routing algorithms for mesh networks. The algorithms are distributed and local information based. Authors apply probabilistic analysis on the fault tolerance of above routing algorithms. Supposing each node has an independent failure probability, it is able to derive the probability that the routing algorithms successfully return a fault-free routing path. For example, authors formally prove that as long as the node failure probability is bounded by 1.87%, the routing algorithms succeed in finding a fault-free routing path with probability at least 99%. The routing algorithms run in linear time. Simulation results show that the length of the routing paths constructed by the algorithms is very close to the optimal length.
出处
《计算机学报》
EI
CSCD
北大核心
2004年第3期319-327,共9页
Chinese Journal of Computers
基金
国家自然科学基金 ( 6 0 3 73 0 83
90 10 40 2 8)
长江学者奖励计划资助
