基于极大安全通路向量的超立方体容错路由

A fault-tolerant routing strategy based on maximum safety-path vectors for hypercube multi-computers

针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全通路向量的概念,给出了一个建立MSPV及其容错路由算法。证明了MSPV通过n-1轮邻节点之间的信息交换,能以向量的形式记录最多的最优通路;与基于安全向量及扩展安全向量的容错路由算法相比,MSPV是SV以及ESV的最大扩展,解决了如何用向量的形式来记录最多最优通路的问题.

In order to deal with the increasing fault possibility of computers and their links in hypercube multi-computers system, a novel fault-tolerant routing algorithm for hypercube multi-computers system is proposed, in which each node uses a maximum safety path vectors (MSPV) to record the optimal paths to the other nodes. It proves that MSPV can record the most of optimal paths by n-1 rounds of information exchanges between neighboring nodes. Furthermore, it proves MSPV is the final extension of safety vectors (SV) and extended safety vectors (ESV), which also use the vectors to record the optimal paths in hypercube multi-computers system.