超立方体网络的不相交路径通信策略研究综述

王洪伟等

摘要：超立方体是一类具有良好的拓扑性质的互连网络模型。不相交路径的实现是超立方体网络中容错通信的有效保证。介绍了超立方体网络的不相交路径路由策略中的主要研究内容和研究现状，对近年来该方面取得的研究成果进行分析和总结，并指出了其中存在的问题和该策略研究的方向。

关键词：互连网络； 超立方体； 不相交路径； 容错路由

中图分类号：TP393 文献标识码：A文章编号：2095-2163（2014）01-0017-04

0引言

超立方体网络是多处理机系统中广受关注的一种互连网络。该拓扑结构具有结构简单和规则、直径小、且路由简单有效等特点，因而已然成为了最具影响力的网络模型之一[1-3]，并在实际并行计算机中得到了广泛应用。2012年TOP500排行榜位列第二的K computer超级计算机[1]中，富士通公司为其设计了专用网络拓扑结构tofu，其基本结构为6维花环。从理论上讲，该结构属于广义超立方体拓扑。

超立方体网络规模的扩大导致了链路和节点不可避免地出现故障[4]， 研究网络的容错通信就变得极为重要[5，6]。节点不相交多路径策略是针对相应存在一定数量故障节点的超立方体中，可以实现可靠和高效通信的一种重要方式。该策略还具备着有效的避免拥塞，加大传输带宽，并提供冗余备用传输路径的优点[7，8]。不相交路径路由策略是增大节点间网络带宽并提高容错能力的综合解决方案，并且为网络及系统可靠性也提供了更高层次的保障。

本文从大规模并行计算机应用的角度，由不相交路径路由的概念分类出发，综合探讨了超立方体网络中一对一不相交路径路由、一对多不相交路径路由的各种算法思想及存在的问题，最后指出需要深入研究的方向。

1不相交路径路由策略性质及其分类

通过对网络可靠性传输方法的研究分析发现，仅依靠传统路由重新建立机制来提高传输可靠性有着较大弊端。因为这类被动的解决方案将会耗费大量的时间开销和网络资源，并且未必一定能取得预期的效果。由于超立方体网络节点和节点间通信路径的冗余性以及节点具有的路由功能，在数据源节点与目标节点之间存在多条路径，若能利用节点间的多条路径进行信息传输，则可取得通信性能上的显著改进。不相交多路径的路由协议虽然比单路径的路由协议更加复杂，但其优势却也是相当明显的。具体分析如下。

第一，提高网络路由的可靠行和容错性。由于超立方体网络中节点失效现象导致的网络拓扑结构发生变化，此时若能为每个信源和信宿节点对都建立两条或两条以上通信路径，网络整体的路由可靠性和容错性必会得到提高。

第二，改进通信性能，满足一定的QoS需求。如果在信源和信宿之间能够同时使用多条互相独立的路径，而两者之间的可用带宽就等于各条路径的带宽和。这能够充分利用网络资源，改进通讯性能，从而满足各类应用对于通信质量的需求。

第三，平衡网络负载。单路径的路由协议多会将数据分组的转发工作全部集中在路径的部分节点上，由此则可能导致这些节点产生过载。在多路径的路由协议中，数据分组可以平均分配到多条路径当中，从而使网络中的节点负载趋于平衡。

目前，有关超立方体网络上的不相交路径路由方法已经产生了大量研究成果，根据路径上节点或链路的相交或不相交性，可将其分为三类[9]：

（1）节点不相交（Node Disjoint）多路径路由。这是全局意义的不相交多路径，也称为完全不相交多路径，其含义就是各条路径中除源节点和目标节点之外没有其他任何共用节点。节点不相交多路径路由容错能力强、数据传输的可靠性高、带宽大且载荷平衡能力出众，但相比其它类型的多路径协议，路由算法复杂，路径之间的独立性最高，负载均衡率高，且占用的网络资源也较其它算法更多。

（2）链路不相交 （Link-Disjoint）多路径路由。这是局部意义的不相交多路径，也可称为缠绕多路径 （Braided Multipath），各条路径中没有任何共用的链路，但却可能含有共用的节点。相比节点不相交多路径协议，路由算法简单一些，路径之间的独立性稍差，负载均衡率高，同时占用的网络资源也较少。

（3）相交多路径路由。路径上既可能有共用的链路、也可能有共用节点的多路径路由即称作相交多路径。相比前两种不相交多路径协议，路由算法更简单，但路径之间的独立性最差，负载均衡率最低，占用的网络资源不高。链路不相交（Link Disjoint）多路径路由也可视为一种特殊的相交多路径路由。

超立方体拓扑中，在单源节点情形下，根据目标节点数量的不同，节点不相交路径一般分为两种[9]：node to node节点不相交路径路由算法和node to set节点不相交路径路由算法。其中，node to node节点不相交路径算法是指目标节点只有一个，算法结果是要获得尽可能多的节点不相交路径。node to set节点不相交路径算法是指拥有多个目标节点，算法结果是要获取源节点到达每个目标节点的一条路径，且各条路径不具有公共节点。其目的旨在增加网络聚合通信的可靠性，单一路径失效不会影响源节点和其他节点的实时通信。

为了减少传输延迟和总体通信开销，节点不相交多路径总是期望具有较小的平均长度和较小的最大长度上界，其中的长度即为路径的中转节点数量。路径长度是衡量不相交多路径算法优劣的重要指标。然而，在不相交路径研究方面，多数研究成果却仅只集中于路径的数量，和最长路径上界等指标的优化。

在无故障节点和存在部分节点故障的超立方体网络中，如何在多项式时间内找到多条不相交路径，并且使获取的路径长度最短或较短，则是优化该策略的研究关键所在。

2不相交路径路由策略主要研究成果与存在的问题

大规模并行计算应用对于数据传输的网络负载均衡和容错性能提出了较高的要求。不相交多路径传输机制是从传输角度来提高可靠性和容错性的方法。与重传机制不同的是，多路径机制是一种空间复用技术，即在同一时间的不同路径传输数据分组；而重传机制却是一种时间复用技术，在传输遇到阻塞后重新建立路由路径传输相同的数据。显然多路径机制侧重路由的选择，重传机制则侧重数据的重路由。不相交多路径路由机制在多个方面具有突出优点，因此不相交多路径路由策略的优化就成为当前大规模并行计算网络可靠传输研究的重要课题之一。

2.1node to node不相交多路径

现给出超立方体网络的node to node节点不相交多路径问题的一般形式化定义如下：

定义1 在n维超立方体Hn中，给定故障节点集合F，满足|F|

针对超立方体网络及类似网络的node to node节点不相交多路径构造策略，学者们从各自角度给出了很多不同的方法。

Michael在文献[10]中开创性地提出了信息分派算法（IDA），其方法主要是关注如何将长度为L的信息分割为n个长度为L/m的分组，n≥m，满足m个分组即可还原原文件。Michael在文献中讨论了该信息分派算法在超立方体网络中信息并行传输的应用，当node to node多路径同时存在大于等于n条路径时，如果n-m条路径发生故障，则信息依然可以完整地送达信宿节点。该文献为超立方体node to node不相交多路径的应用指明了一种重要的应用模式。通过对不相交多路径的应用，IDA算法保证了网络信息传输的容错性和信息存储的安全性，IDA算法已经获得了许多具体应用。文献给出了具体应用的一些实例。

QP等人在文献[11]中提出了研究了n维超立方体Hn在集群容错模型基础上的节点到节点容错路由问题。文中给出了定义，对于图G，故障集群是一个连通子图G，所有节点均出现故障。文献研究了保证容错路由是存在的条件下，集群的大小和总数的容忍上限。同时，也证明了对于节点到节点的路由，Hn可以容忍直径至多为1的n-1个故障簇，并且最多2n-3个故障节点总数。文献中还给出了一个算法，在直径最多1以及最多n-1个故障集群，并且不超过2n-3故障节点的情况下，可以找到容错路由路径的长度至多为n-2，算法时间复杂度为O（n）。其中提出的算法虽然将容忍的故障节点数量提高到了2n-3，但却限制了故障节点簇直径，这就对现实网络提出了过于苛刻的要求，该算法的这一局限性即限制了对其的大范围应用。

文献[12]提出了在层次超立方体中的节点不相交算法。该算法局限于层次超立方体结构，同时也使得算法移植到其它类似网络则较为困难。

文献[13]提出了采用超立方体网络自身特性的一种路由算法，该算法使用一个简洁的演算公式根据当前节点地址和目标节点地址，求得路径中下一个节点的地址，其公式设计的巧妙性和合理性保证了算法得到的路径输出均不相交，而且其时间复杂度是O（n）。文中证明了该多路径算法在网络信息传输发生错误的情况下，消息分组在经过多轮转发之后，将自动退出传输，而不会造成无限循环过程，算法输出路径长度上界仅为n+1等多个有用的性质。但是该算法假设在无故障节点的超立方体网络中通信，并未考虑故障节点对该节点不相交路径路由算法的影响，也由于此路径计算公式采用的参数少而导致每次取得的多路径是同一个，因而缺少了路径变换的灵活性。

2.2node to set不相交多路径

针对超立方体网络及类似网络的node to set节点不相交多路径路由，学者们开展了大量的研究工作，最近几年的研究热点均集中于存在部分节点或链接故障情形下的不相交路径构造策略和无故障情形下的最短不相交路径策略。为此，本文仅讨论近年来的最新研究成果。

Bassard在文献[14]中研究了存在故障节点的超立方体的node to set问题，提出了基于单个节点到达相邻子立方体的最长路径为2的定理，并且给出了node to set节点不相交路径的求解策略，得到的路径长度上限为n+k+4，其中，k为故障节点数量。该策略仅仅限制了最长路径长度的极限，每条路径的建立是通过穿越不同的子立方体而得到的，这就决定了其建立的路径平均长度没有包含在算法的优化范围内。

Xiang等人在文献[15]中证明了k-ary n-cube网络中，最多存在2n-2条故障链路的情况下，在每对节点之间存在min{degH（u） ， degH（v）}（degH为节点可用邻居数量的函数）条节点不相交路径。也即证明了该网络中链路故障数小于等于2n-2时，网络路由是可靠的。该文献没有论述其在超立方体网络情形下的解决方案。

文献[16]提出了在无故障节点的超立方体中node to set节点不相交最短多路径算法，算法的时间复杂度为O（mn），其中m为目标节点数量。在该算法基础上，文献同时也给出了多路径总长度最小化的算法，其总的算法复杂度为O（m2n2.5+mn3）。虽然相对于类似算法，该算法取得了在node to set节点不相交的最短路径，并具有较低的时间复杂度，但是算法本身是建立在无故障节点的超立方体情形下，即使存在少量，在极端情况下甚至一个故障节点，就将导致算法的输出结果的可用价值大幅减小。

3不相交路径策略研究的发展方向

作为超立方体网络负载的均衡性和通信的可靠性的重要保证，不相交路径路由策略具有广泛的应用背景和重要的理论研究价值。尤其是如何在保证存在部分节点故障前提下实现不相交路径路由，同时还要具有较高的效率，是当前研究的热点。然而，超立方体网络中路径的大量冗余和节点或连接故障出现的不可预测性等特性使不相交路径路由机制设计面临巨大而严峻的挑战。近年来，相关研究从不同角度讨论了不相交路径路由机制，但由本文的分析可看出，该领域的研究仅处于初步探讨的阶段，尚未建立成熟的理论体系和实践标准。另外，还需重点考察超立方体网络中故障节点数量对不相交路径存在性，路径的存在数量上的影响，设计支持节点故障动态出现的多路径路由协议，对现有协议进行必要的修改，并且进一步完善路由算法设计。

参考文献：

[1]http：//www.top500.org/

[2]LU Song， YANG XiaoDong. A multicast path algorithm on hypercube Interconnection Networks[C]//Proceedings of IEEE International conference on High Performance Computing and Communications， Dalian， China， 2008：641-646.

[3]DUOTO J， YALAMANCHILI S， NI L. Interconnection networks： an engineering approach. Morgan Kaufmann Publishers， 2002： 149-160.

[4]GAO Feng， LI ZC， MIN YH， et al. A fault-tolerant routing strategy based on extended safety vectors in hypercube multi-computers[J]. Chinese Journal of Computers， 2000，23（3）：248-254.

[5]DASGUPTA M. CHOUDHURY S. CHAKI N. A secure hypercube based team multicast routing Protocos （S-HTMRP） [C]//Advance Computing Conference， 2009：1265 – 1269.

[6]LIU Yingying， LIU Hongmei， ZHANG Yanjuan. The connectivity of edge-fault-tolerant enhanced hypercube， electric information and control engineering （ICEICE） [C]//2011 International Conference， 2011：805-807， doi： 10.1109/ICEICE.2011.5777262.

[7]LU S， FAN B H， DOU Y. Clustering multicast on hypercube network[C]//Proceedings of IEEE International conference on High Performance Computing and Communications， Munich， Germany， 2006：61-70.

[8]QIU Ke. An efficient disjoint shortest paths routing algorithm for the Hypercube[C]//Parallel and Distributed Systems， 2008. ICPADS '08. 14th IEEE International Conference on， 2008：43-47.

[9]DIETZFELBINGER M， MADHAVAPEDDY S， SUDBOROUGH I H. Three disjoint path paradigms in star networks[C]//Proc. IEEE Third Symp. Parallel and Distributed Processing， 1991：400-406.

[10]RABIN M. Efficient dispersal of information for security， load balancing， and fault tolerance[J]. Journal of the Association for computing machinery ，1989，36（2）：335-348.

[11]GU Q， PENG S. An efficient algorithm for node-to-node routing in Hypercubes with faulty clusters[J].The Computer Journal，1996， 39（1）： 14–19 .

[12]WU Ruei-Yu， et.al. Node-disjoint paths in hierarchical hypercube networks. Information Sciences， 2007，177：4200–4207.

[13]SINANOGLU O， KARAATA M H， ALBDAIWI B. An inherently stabilizing algorithm for node-to-node routing over all shortest