| Mesh网络容错广播路由算法的概率分析 |
| |
| 引用本文： | 王高才,陈建二,王国军,陈松乔.Mesh网络容错广播路由算法的概率分析[J].计算机科学,2003,30(10):113-116. |
| |
| 作者姓名： | 王高才 陈建二 王国军 陈松乔 |
| |
| 作者单位： | 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金(90104028)，长江学者奖励计划资助项目 |
| |
| 摘 要： | One-to-all or broadcast communication is one of the most important communication patterns and occurs in many important applications in parallel computing. This paper proposes a fault tolerant, local-irdormation-based, and distributed broadcast routing algorithm based on the concept of k-submesh-cormectivity in all-port mesh networks.The paper analyzes the fault tolerance of the algorithm in terms of node failure probability. Suppose that every nodehas independent failure probability, and deduce the success probability of the broadcast routing, which successfully routes a message from a source node to all non-faulty nodes in the networks. The paper strictly proves that the broadcast routing algorithm with the success probability of 99％ to route among all non-faulty nodes on mesh networks with forty thousand nodes, in case that the node failure probability is controlled within 0.12％ Simulation results show that the algorithm is practically efficient and effective, and the time steps of the algorithm are very closeto the optimum.
|
| 关 键 词： | 计算机网络 Mesh算法 网络容错广播路由算法 概率分析 |
Probabilistic Analysis of Fault Tolerant Broadcast Routing Algorithms on Mesh Networks |
| |
| WANG Gao-Cai CHEN Jian-Er WANG Guo-Jun CHEN Song-Qiao.Probabilistic Analysis of Fault Tolerant Broadcast Routing Algorithms on Mesh Networks[J].Computer Science,2003,30(10):113-116. |
| |
| Authors: | WANG Gao-Cai CHEN Jian-Er WANG Guo-Jun CHEN Song-Qiao |
| |
| Abstract: | One-to-all or broadcast communication is one of the most important communication patterns and occurs in many important applications in parallel computing. This paper proposes a fault tolerant, local-information-based, and distributed broadcast routing algorithm based on the concept of k-submesh-connectivity in all-port mesh networks. The paper analyzes the fault tolerance of the algorithm in terms of node failure probability. Suppose that every node has independent failure probability, and deduce the success probability of the broadcast routing, which successfully routes a message from a source node to all non-faulty nodes in the networks. The paper strictly proves that the broadcast routing algorithm with the success probability of 99% to route among all non-faulty nodes on mesh networks with forty thousand nodes, in case that the node failure probability is controlled within 0. 12%. Simulation results show that the algorithm is practically efficient and effective, and the time steps of the algorithm are very close to the optimum. |
| |
| Keywords: | Mesh networks k-submesh-connectivity Fault tolerance Broadcast routing algorithm Probabilistic analysis |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
