基于NPV广义超立方体最佳容错路由算法

在网络可靠性研究中,设计较好的容错路由策略、尽可能多地记录系统中最优通路信息,一直是一项重要的研究工作.超立方体系统的容错路由算法分为可回溯算法和无回溯算法.一般说来,可回溯算法的优点是容错能力强:只要消息的源节点和目的节点有通路,该算法就能够找到把消息传递到目的地的路径;其缺点是在很多情况下传递路径不能按实际存在的最短路径传递.其代表是深度优先搜索(DFS)算法.无回溯算法是近几年人们比较关注的算法.该算法通过记录各邻接节点的故障信息,给路由算法以启发信息,使消息尽可能按实际存在的最短路径传递.这些算法的共同缺点是只能计算出Hamming距离不超过n的路由.在n维超立方体系统连通图中,如果系统存在大量的故障,不少节点对之间的最短路径大于n,因此,这些算法的容错能力差.提出了一个实例说明采用上述算法将遗失60%的路由信息.另外,由于超立方体的结构严格,实际中的真正超立方体系统不多.事实上,不少的网络系统可转换为具有大量错误节点和错误边的超立方体系统.因此,研究能适应具有大量错误节点和错误边的超立方体系统的容错路由算法是一个很有实际价值的工作.研究探讨了:(1) 定义广义超立方体系统;(2) 在超立方体系统中提出了节点通路向量(NPV)概念及其计算规则;(3) 提出了中转点技术,使得求NPV的计算复杂度降低到O(n);(4) 提出了基于NPV的广义超立方体系统最佳容错路由算法(OFTRS),该算法是一种分布式的和基于相邻节点信息的算法.由于NPV记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.

An NPV-Based Optimal Fault-Tolerant Routing Algorithm for Generalized Hypercube

Optimal fault-tolerant routing is imperative for large hypercube systems in the existence of large number of faulty links or nodes. This paper first defines hypercube network with a large number of faulty nodes and/or links to be generalized hypercube and illustrates that many non-hypercube systems can be transformed to Generalized Hypercube systems. It then proposes node path vector (NPV) to capture the complete optimal and sub-optimal routing information for a generalized hypercube system. To reduce the computation iterations in solving NPV, it also introduces the concept of relay node technique. Based on NPV and relay node technique, this paper further proposes optimal fault-tolerant routing scheme (OFTRS) to derive shortest path for any communication pair in a generalized hypercube system. With an example of large number of faulty nodes or faulty links, it is illustrated that the previous algorithm could omit up to 60% routing paths, while this approach achieves all optimal and sub-optimal routing paths. Compared to previous work, OFTRS has a significant improvement in obtaining routing information for optimal and sub-optimal, i.e. no matter how many faulty nodes or links exist, it is guaranteed to route through the optimal or sub-optimal path as long as a path between the source-destination pair exists. In addition, the proposed scheme is distributed and relying only on non-faulty neighboring nodes since it only requires the information of non-faulty neighbor nodes in computing NPV, thus it has high applicability, especially when some non-hypercube systems can be transformed into Generalized Hypercube systems.