基于扩展安全级的Torus网络容错路由算法研究

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

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

How to design fault-tolerant routing in multiprocessors with fauh 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 level,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.