点对点并行路由算法及容错性概率分析

用概率性分析方法,研究了在结点错误概率性分布的情形下,超立方体网络的点对点并行路由算法,并对算法的容错性概率、路径长度、算法复杂性进行了严格的推导。提出的算法是基于任意给定两个正确结点可以找出n条不相交的路径。分析了算法保证一条或多条路径同时联通的概率达到99.99%时结点的错误概率上界,同时考虑了两点间的海明距离变化,得出了较好的理论结论与计算结果。方法为研究超立方体网络容错性与并行路由算法提供了一种新的途径与新的考虑角度,具有更一般与更接近实际的意义。

Fault Tolerance and Probability Study on Hypercube Node-to-Node Parallel Routing Algorithm

The paper mainl y studies node-to-node parallel routing algorithms of hypercube networks and strictly analyses the connected routing probability and fault tolerance of hyper cube networks in terms of node failure probability.It also analyses the length of path and the bound of algorithms' running time.The algorithm considers how to find n disjoint paths and studies the probability that any of them keeps con nected.The result shows that the n-hypercube network can tolerate faulty nod es and keep any given two nodes finding one or many no fault routing paths with probability99.99%along with the change of the two given nodes' Hamming d istance.Theoretical conclusion and computational result are given in the paper .The approach proposes a new way and a new point of view to study the hypercub e fault tolerance.