超立方体多处理机系统中基于扩展安全向量的容错路由

针对超立方体结构的多处理机系统中存在链路故障的情况，修改了吴杰提出的安全向量的概念，提出了扩展安全向量的概念，并给出了一个基于扩展安全向量的容错路由算法，与基于安全向量的路由算法相比，基于扩展安全向量的路由算法搜索最优通路的能力有了非常大的提高，即使故障数较多时，它仍能保证把绝大多数源、目的节点间有最优通路和消息沿最优通路传递。超立方体结构中各节点扩展安全向量的赋值可以通过ｎ－１轮邻接点的信息交换

A Fault-Tolerant Routing Strategy Based on Extended Safety Vectors in Hypercube Multicomputers

This paper modifies the definition of safety vectors (SVs) 8] , which is proposed for hypercube multicomputers, and proposes a new concept extended safety vectors (ESVs). The values of extended safety vectors of nodes in a hypercube system can be determined in n-1 rounds information exchange between neighbors. Optimal unicasting between two nodes is guaranteed if the k th bit of extended safety vector of the source node is 1, where the k is equal to the Hamming distance between the two nodes. A fault tolerant routing algorithm is then proposed to make use of the information recorded in extended safety vectors. It can easily determine whether a path of length no greater than the Hamming distance between the source and destination plus 2 can be established. The simulation results show that it is much more powerful than those based on safety vectors in dealing with link faults.