超立方体网络下的自适应容错路由研究  

Research of adaptive fault tolerant routing algorithm in hypercube networks

作　　者：翁毅[1] 梁家荣[1] 花仁杰[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机应用研究》2010年第3期1151-1153,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(60564001);国家教育部新世纪优秀人才支持计划资助项目(NCET-06-0756)

摘　　要：针对超立方体结构的多处理机系统出现故障的问题,对容错超立方体网络的局部连通性进行了研究。根据局部连通性的特点定义了相邻节点集合类的概念,提出并证明了求解两类相邻节点集合的公式。给出了满足任意子连通性条件的超立方体网络的自适应容错路由算法。该算法是分布式和基于局部信息的,可以预防死锁。仿真实验的结果表明算法是高效的,且构建的路径长度接近于最优路径长度。In order to deal with the fault possibility of computers and links in hypercube multi-computer system, this paper studied local connectivity of fault tolerant hypercube networks. The concept of the neighbor sets of present node had been defined in accordance with the characteristics of local connectivity. The formula which could solve two kinds of sets of neighbor nodes was proposed and proved. This paper developed an adaptive fault tolerant routing algorithm for arbitrary subcube-connetted hypereube networks. This algorithm was distributed and based on local information, and it could prevent deadlock. Simulation results show that this algorithm is efficient and the length of the routing path constructed by this algorithm is close to the optimal length.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]