超立方體網(wǎng)絡(luò)是一種新型互聯(lián)網(wǎng)絡(luò)，由于其特性使得其在計算機技術(shù)中得以廣泛應(yīng)用，本文主要探討了超立方體網(wǎng)絡(luò)近些年的發(fā)展成果與現(xiàn)狀，研究了超立方體網(wǎng)絡(luò)的類型與工作原理。

　　《數(shù)字通信世界》是由工業(yè)和信息化部主管，電子工業(yè)出版社主辦的通信類綜合月刊，發(fā)行范圍覆蓋了IT、通信、廣電及其它專網(wǎng)系統(tǒng)，其發(fā)行網(wǎng)已延伸至國內(nèi)外企業(yè)、研究機構(gòu)和院校等。

　　超立方體網(wǎng)絡(luò)是多處理機系統(tǒng)中廣受關(guān)注的一種互連網(wǎng)絡(luò)。該拓撲結(jié)構(gòu)具有結(jié)構(gòu)簡單和規(guī)則、直徑小、且路由簡單有效等特點，因而已然成為了最具影響力的網(wǎng)絡(luò)模型之一[1-3]，并在實際并行計算機中得到了廣泛應(yīng)用。2012年TOP500排行榜位列第二的Kcomputer超級計算機[1]中，富士通公司為其設(shè)計了專用網(wǎng)絡(luò)拓撲結(jié)構(gòu)tofu，其基本結(jié)構(gòu)為6維花環(huán)。從理論上講，該結(jié)構(gòu)屬于廣義超立方體拓撲。

　　超立方體是一類具有良好的拓撲性質(zhì)的互連網(wǎng)絡(luò)模型。不相交路徑的實現(xiàn)是超立方體網(wǎng)絡(luò)中容錯通信的有效保證。介紹了超立方體網(wǎng)絡(luò)的不相交路徑路由策略中的主要研究內(nèi)容和研究現(xiàn)狀，對近年來該方面取得的研究成果進行分析和總結(jié)，并指出了其中存在的問題和該策略研究的方向。

　　0引言

　　超立方體網(wǎng)絡(luò)規(guī)模的擴大導(dǎo)致了鏈路和節(jié)點不可避免地出現(xiàn)故障[4]，研究網(wǎng)絡(luò)的容錯通信就變得極為重要[5，6]。節(jié)點不相交多路徑策略是針對相應(yīng)存在一定數(shù)量故障節(jié)點的超立方體中，可以實現(xiàn)可靠和高效通信的一種重要方式。該策略還具備著有效的避免擁塞，加大傳輸帶寬，并提供冗余備用傳輸路徑的優(yōu)點[7，8]。不相交路徑路由策略是增大節(jié)點間網(wǎng)絡(luò)帶寬并提高容錯能力的綜合解決方案，并且為網(wǎng)絡(luò)及系統(tǒng)可靠性也提供了更高層次的保障。

　　本文從大規(guī)模并行計算機應(yīng)用的角度，由不相交路徑路由的概念分類出發(fā)，綜合探討了超立方體網(wǎng)絡(luò)中一對一不相交路徑路由、一對多不相交路徑路由的各種算法思想及存在的問題，最后指出需要深入研究的方向。

　　1不相交路徑路由策略性質(zhì)及其分類

　　通過對網(wǎng)絡(luò)可靠性傳輸方法的研究分析發(fā)現(xiàn)，僅依靠傳統(tǒng)路由重新建立機制來提高傳輸可靠性有著較大弊端。因為這類被動的解決方案將會耗費大量的時間開銷和網(wǎng)絡(luò)資源，并且未必一定能取得預(yù)期的效果。由于超立方體網(wǎng)絡(luò)節(jié)點和節(jié)點間通信路徑的冗余性以及節(jié)點具有的路由功能，在數(shù)據(jù)源節(jié)點與目標節(jié)點之間存在多條路徑，若能利用節(jié)點間的多條路徑進行信息傳輸，則可取得通信性能上的顯著改進。不相交多路徑的路由協(xié)議雖然比單路徑的路由協(xié)議更加復(fù)雜，但其優(yōu)勢卻也是相當(dāng)明顯的。具體分析如下。

　　第一，提高網(wǎng)絡(luò)路由的可靠行和容錯性。由于超立方體網(wǎng)絡(luò)中節(jié)點失效現(xiàn)象導(dǎo)致的網(wǎng)絡(luò)拓撲結(jié)構(gòu)發(fā)生變化，此時若能為每個信源和信宿節(jié)點對都建立兩條或兩條以上通信路徑，網(wǎng)絡(luò)整體的路由可靠性和容錯性必會得到提高。

　　第二，改進通信性能，滿足一定的QoS需求。如果在信源和信宿之間能夠同時使用多條互相獨立的路徑，而兩者之間的可用帶寬就等于各條路徑的帶寬和。這能夠充分利用網(wǎng)絡(luò)資源，改進通訊性能，從而滿足各類應(yīng)用對于通信質(zhì)量的需求。

　　第三，平衡網(wǎng)絡(luò)負載。單路徑的路由協(xié)議多會將數(shù)據(jù)分組的轉(zhuǎn)發(fā)工作全部集中在路徑的部分節(jié)點上，由此則可能導(dǎo)致這些節(jié)點產(chǎn)生過載。在多路徑的路由協(xié)議中，數(shù)據(jù)分組可以平均分配到多條路徑當(dāng)中，從而使網(wǎng)絡(luò)中的節(jié)點負載趨于平衡。

　　目前，有關(guān)超立方體網(wǎng)絡(luò)上的不相交路徑路由方法已經(jīng)產(chǎn)生了大量研究成果，根據(jù)路徑上節(jié)點或鏈路的相交或不相交性，可將其分為三類[9]：

　　(1)節(jié)點不相交(NodeDisjoint)多路徑路由。這是全局意義的不相交多路徑，也稱為完全不相交多路徑，其含義就是各條路徑中除源節(jié)點和目標節(jié)點之外沒有其他任何共用節(jié)點。節(jié)點不相交多路徑路由容錯能力強、數(shù)據(jù)傳輸?shù)目煽啃愿摺�帶寬大且載荷平衡能力出眾，但相比其它類型的多路徑協(xié)議，路由算法復(fù)雜，路徑之間的獨立性最高，負載均衡率高，且占用的網(wǎng)絡(luò)資源也較其它算法更多。

　　(2)鏈路不相交(Link-Disjoint)多路徑路由。這是局部意義的不相交多路徑，也可稱為纏繞多路徑(BraidedMultipath)，各條路徑中沒有任何共用的鏈路，但卻可能含有共用的節(jié)點。相比節(jié)點不相交多路徑協(xié)議，路由算法簡單一些，路徑之間的獨立性稍差，負載均衡率高，同時占用的網(wǎng)絡(luò)資源也較少。

　　(3)相交多路徑路由。路徑上既可能有共用的鏈路、也可能有共用節(jié)點的多路徑路由即稱作相交多路徑。相比前兩種不相交多路徑協(xié)議，路由算法更簡單，但路徑之間的獨立性最差，負載均衡率最低，占用的網(wǎng)絡(luò)資源不高。鏈路不相交(LinkDisjoint)多路徑路由也可視為一種特殊的相交多路徑路由。

　　超立方體拓撲中，在單源節(jié)點情形下，根據(jù)目標節(jié)點數(shù)量的不同，節(jié)點不相交路徑一般分為兩種[9]：nodetonode節(jié)點不相交路徑路由算法和nodetoset節(jié)點不相交路徑路由算法。其中，nodetonode節(jié)點不相交路徑算法是指目標節(jié)點只有一個，算法結(jié)果是要獲得盡可能多的節(jié)點不相交路徑。nodetoset節(jié)點不相交路徑算法是指擁有多個目標節(jié)點，算法結(jié)果是要獲取源節(jié)點到達每個目標節(jié)點的一條路徑，且各條路徑不具有公共節(jié)點。其目的旨在增加網(wǎng)絡(luò)聚合通信的可靠性，單一路徑失效不會影響源節(jié)點和其他節(jié)點的實時通信。

　　為了減少傳輸延遲和總體通信開銷，節(jié)點不相交多路徑總是期望具有較小的平均長度和較小的最大長度上界，其中的長度即為路徑的中轉(zhuǎn)節(jié)點數(shù)量。路徑長度是衡量不相交多路徑算法優(yōu)劣的重要指標。然而，在不相交路徑研究方面，多數(shù)研究成果卻僅只集中于路徑的數(shù)量，和最長路徑上界等指標的優(yōu)化。

　　在無故障節(jié)點和存在部分節(jié)點故障的超立方體網(wǎng)絡(luò)中，如何在多項式時間內(nèi)找到多條不相交路徑，并且使獲取的路徑長度最短或較短，則是優(yōu)化該策略的研究關(guān)鍵所在。

　　2不相交路徑路由策略主要研究成果與存在的問題

　　大規(guī)模并行計算應(yīng)用對于數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)負載均衡和容錯性能提出了較高的要求。不相交多路徑傳輸機制是從傳輸角度來提高可靠性和容錯性的方法。與重傳機制不同的是，多路徑機制是一種空間復(fù)用技術(shù)，即在同一時間的不同路徑傳輸數(shù)據(jù)分組;而重傳機制卻是一種時間復(fù)用技術(shù)，在傳輸遇到阻塞后重新建立路由路徑傳輸相同的數(shù)據(jù)。顯然多路徑機制側(cè)重路由的選擇，重傳機制則側(cè)重數(shù)據(jù)的重路由。不相交多路徑路由機制在多個方面具有突出優(yōu)點，因此不相交多路徑路由策略的優(yōu)化就成為當(dāng)前大規(guī)模并行計算網(wǎng)絡(luò)可靠傳輸研究的重要課題之一。[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.