超立方體網絡是一種新型互聯網絡，由于其特性使得其在計算機技術中得以廣泛應用，本文主要探討了超立方體網絡近些年的發展成果與現狀，研究了超立方體網絡的類型與工作原理。

　　《數字通信世界》是由工業和信息化部主管，電子工業出版社主辦的通信類綜合月刊，發行范圍覆蓋了IT、通信、廣電及其它專網系統，其發行網已延伸至國內外企業、研究機構和院校等。

　　超立方體網絡是多處理機系統中廣受關注的一種互連網絡。該拓撲結構具有結構簡單和規則、直徑小、且路由簡單有效等特點，因而已然成為了最具影響力的網絡模型之一[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.