%0 Journal Article
%T Probabilistic Analysis of Fault Tolerant Broadcast Routing Algorithms on Mesh Networks<br>Mesh网络容错广播路由算法的概率分析
%A WANG Gao-Cai CHEN Jian-Er WANG Guo-Jun CHEN Song-Qiao
%A <br>王高才
%A 陈建二
%A 王国军
%A 陈松乔
%J 计算机科学
%D 2003
%I 
%X 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.
%K Mesh networks
%K k-submesh-connectivity
%K Fault tolerance
%K Broadcast routing algorithm
%K Probabilistic analysis<br>计算机网络
%K Mesh算法
%K 网络容错广播路由算法
%K 概率分析
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=59445119640F9099&yid=D43C4A19B2EE3C0A&vid=340AC2BF8E7AB4FD&iid=F3090AE9B60B7ED1&sid=A63576421B012172&eid=8477411EEDB08A86&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=14