Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (29): 99-101.DOI: 10.3778/j.issn.1002-8331.2009.29.029

• 网络、通信、安全 • Previous Articles     Next Articles

Research on fault-tolerant routing algorithm in Torus using extended safety levels

LIANG Jia-rong1,XU Shuang1,WU Hua-jian2   

  1. 1.School of Computer and Electrical Information,Guangxi University,Nanning 530004,China
    2.Department of Mathematics and Computer Science,Yulin Normal University,Yulin,Guangxi 537000,China
  • Received:2008-06-03 Revised:2008-08-25 Online:2009-10-11 Published:2009-10-11
  • Contact: LIANG Jia-rong


梁家荣1,徐 霜1,伍华健2   

  1. 1.广西大学 计算机与电子信息学院,南宁530004
    2.玉林师范学院 数计系,广西 玉林 537000
  • 通讯作者: 梁家荣

Abstract: How to design fault-tolerant routing in multiprocessors with fault nodes is an issue of fault-tolerant research.Two-dimensional tori with faulty blocks is studied.A sufficient and necessary condition for minimal routing is proposed.This approach is based on the concept of extended safety level,which is a special form of limited fault information.Based on extended safety le-
vel,an approach which is used to establish RMP(Region of Minimal Path) is presented.The research can provide theoretical basis for finding shortest fault-tolerant routing path in Torus.

Key words: fault-tolerant routing, fault block model, extended safety level

摘要: 在存在故障结点的网络中如何设计最小容错路由是网络容错研究中的一个热点问题。以存在矩形故障块的二维Torus网络为例,将扩展安全级运用到Torus中,对于网络中任意一对结点,给出存在最小路径的充要条件;并且结合扩展安全级的概念,给出建立最小通路区的方法,并用实验验证了方法的可行性。研究为存在故障结点的Torus网络寻找最小容错路径提供了理论依据。

关键词: 容错路由, 矩形故障块, 扩展安全级

CLC Number: