通信论文超立方体网络的不相交路径通信策略

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

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

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

　　0引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　[4]GAOFeng，LIZC，MINYH，etal.Afault-tolerantroutingstrategybasedonextendedsafetyvectorsinhypercubemulti-computers[J].ChineseJournalofComputers，2000，23（3）：248-254.

　　[5]DASGUPTAM.CHOUDHURYS.CHAKIN.AsecurehypercubebasedteammulticastroutingProtocos（S-HTMRP）[C]//AdvanceComputingConference，2009：1265–1269.

　　[6]LIUYingying，LIUHongmei，ZHANGYanjuan.Theconnectivityofedge-fault-tolerantenhancedhypercube，electricinformationandcontrolengineering（ICEICE）[C]//2011InternationalConference，2011：805-807，doi：10.1109/ICEICE.2011.5777262.