组合星图中一对一容错路由算法  

A algorithm of node-to-node fault tolerant routing in the(n,k)-star

作　　者：李静力[1] 向永红[2] 吕雅丽[1] 周永恒[1] 

机构地区：[1]云南大学信息学院,云南昆明650091 [2]云南大学软件学院,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2006年第S1期170-176,共7页Journal of Yunnan University(Natural Sciences Edition)

基　　金：云南省教育厅基金资助项目(03Y153D);云南大学校级科研资助项目(2003Q022A)

摘　　要：解决了组合星图的一对一容错路由问题.给出了故障节点不超过n-2时,无故障节点s到t的路由算法,证明了算法可以在O(n)内找到一条长度不超过D(Sn,k)+4的路P:s t,其中,D(Sn,k)是Sn,k的直径.运用列举法,推导出组合星图Sn,k中任意点p到固定点Ik的距离公式;并从图论的观点,推导出Sn,k任意2个子图之间的星边数目为(n-2)!/(n-k)!.It is important for an interconnection network to route data among nodes despite faulty nodes in the network.Alternative paths in case of nodes failure can not only avoid communication bottlenecks,but increase the efficiency of message transmission.In this paper,we present a angorithm to find a faultless path st of length at most D(S_(n,k))+4 in O(n) time,given at most n-2 faulty nodes,also two distinct faultless nodes s and t in the (n,k)-star graph,where D(S_(n,k)) is the diameter of S_(n,k).

关 键 词：组合星图 距离 容错 路 路由 

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