超立方体网络广播容错路由算法

来源期刊：中南大学学报(自然科学版)2002年第3期

论文作者：王国军 陈建二 陈松乔

文章页码：305 - 308

关键词：互联网络;超立方体网络;广播容错路由算法;局部连通性

Key words：interconnection network; hypercube; broadcast fault tolerant routing algorithm; local-connectivity

摘    要：研究了具有大量错误结点的超立方体网络中的广播容错路由算法.假定H_n是一个局部3维子立方体连通的n维超立方体网络,并且每一个基本的3维子立方体中分别最多有1个和2个错误结点,从理论上证明了在最坏情况下基于shouting广播通信模式的广播容错路由算法分别经过最多1.5(n-1)和2(n-1)时间步,就可以将源结点的信息广播到H_n中的所有正确结点中;通过实验验证了在均匀和独立的错误结点分布情况下广播时间步的上界实际上只有n+1,支持了理论分析结果.

Abstract: The broadcast fault tolerant routing algorithms in hypercube networks with a large number of faulty nodes were investigated. Suppose H_n is a locally 3-subcube-connectedn-dimensional hypercube network, in which every basic 3-subcube has at most one and two faulty nodes, respectively. The authors theoretically prove that, in the worst case the broadcast fault tolerant routing algorithms with the shouting communication mode can propagate a message from a source node to all the non-faulty nodes within H_n in 1.5(n-1) and 2(n-1) time steps respectively, and also perform experiments to verify that the upper bound of the time step is onlyn+1 when the node faulty probability is uniform and independent, which strongly supports the theoretical results.