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

Broadcast fault tolerant routing algorithms in hypercube networks

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

The broadcast fault tolerant routing algorithms in hypercube networks with a large number of faulty nodes were investigated. Suppose Hn is a locally 3 subcube connected n 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 Hn 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 only n +1 when the node faulty probability is uniform and independent, which strongly supports the theoretical results.