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

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

作　　者：张祖平[1] 郑瑾[1] 陈建二[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机工程与应用》2003年第33期19-21,共3页Computer Engineering and Applications

基　　金：国家海外杰出青年自然科学基金(69928201);长江学者奖励计划;教育部高等学校骨干教师资助计划

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

关 键 词：互联网络 超立方体网络 容错性 路由算法 概率分析 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]