超立方體網(wǎng)絡(luò)的不相交路徑通信策略研究綜述

王洪偉等

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

關(guān)鍵詞：互連網(wǎng)絡(luò)； 超立方體； 不相交路徑； 容錯(cuò)路由

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2014）01-0017-04

0引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1node to node不相交多路徑

現(xiàn)給出超立方體網(wǎng)絡(luò)的node to node節(jié)點(diǎn)不相交多路徑問(wèn)題的一般形式化定義如下：

定義1 在n維超立方體Hn中，給定故障節(jié)點(diǎn)集合F，滿(mǎn)足|F|

針對(duì)超立方體網(wǎng)絡(luò)及類(lèi)似網(wǎng)絡(luò)的node to node節(jié)點(diǎn)不相交多路徑構(gòu)造策略，學(xué)者們從各自角度給出了很多不同的方法。

Michael在文獻(xiàn)[10]中開(kāi)創(chuàng)性地提出了信息分派算法（IDA），其方法主要是關(guān)注如何將長(zhǎng)度為L(zhǎng)的信息分割為n個(gè)長(zhǎng)度為L(zhǎng)/m的分組，n≥m，滿(mǎn)足m個(gè)分組即可還原原文件。Michael在文獻(xiàn)中討論了該信息分派算法在超立方體網(wǎng)絡(luò)中信息并行傳輸?shù)膽?yīng)用，當(dāng)node to node多路徑同時(shí)存在大于等于n條路徑時(shí)，如果n-m條路徑發(fā)生故障，則信息依然可以完整地送達(dá)信宿節(jié)點(diǎn)。該文獻(xiàn)為超立方體node to node不相交多路徑的應(yīng)用指明了一種重要的應(yīng)用模式。通過(guò)對(duì)不相交多路徑的應(yīng)用，IDA算法保證了網(wǎng)絡(luò)信息傳輸?shù)娜蒎e(cuò)性和信息存儲(chǔ)的安全性，IDA算法已經(jīng)獲得了許多具體應(yīng)用。文獻(xiàn)給出了具體應(yīng)用的一些實(shí)例。

QP等人在文獻(xiàn)[11]中提出了研究了n維超立方體Hn在集群容錯(cuò)模型基礎(chǔ)上的節(jié)點(diǎn)到節(jié)點(diǎn)容錯(cuò)路由問(wèn)題。文中給出了定義，對(duì)于圖G，故障集群是一個(gè)連通子圖G，所有節(jié)點(diǎn)均出現(xiàn)故障。文獻(xiàn)研究了保證容錯(cuò)路由是存在的條件下，集群的大小和總數(shù)的容忍上限。同時(shí)，也證明了對(duì)于節(jié)點(diǎn)到節(jié)點(diǎn)的路由，Hn可以容忍直徑至多為1的n-1個(gè)故障簇，并且最多2n-3個(gè)故障節(jié)點(diǎn)總數(shù)。文獻(xiàn)中還給出了一個(gè)算法，在直徑最多1以及最多n-1個(gè)故障集群，并且不超過(guò)2n-3故障節(jié)點(diǎn)的情況下，可以找到容錯(cuò)路由路徑的長(zhǎng)度至多為n-2，算法時(shí)間復(fù)雜度為O（n）。其中提出的算法雖然將容忍的故障節(jié)點(diǎn)數(shù)量提高到了2n-3，但卻限制了故障節(jié)點(diǎn)簇直徑，這就對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)提出了過(guò)于苛刻的要求，該算法的這一局限性即限制了對(duì)其的大范圍應(yīng)用。

文獻(xiàn)[12]提出了在層次超立方體中的節(jié)點(diǎn)不相交算法。該算法局限于層次超立方體結(jié)構(gòu)，同時(shí)也使得算法移植到其它類(lèi)似網(wǎng)絡(luò)則較為困難。

文獻(xiàn)[13]提出了采用超立方體網(wǎng)絡(luò)自身特性的一種路由算法，該算法使用一個(gè)簡(jiǎn)潔的演算公式根據(jù)當(dāng)前節(jié)點(diǎn)地址和目標(biāo)節(jié)點(diǎn)地址，求得路徑中下一個(gè)節(jié)點(diǎn)的地址，其公式設(shè)計(jì)的巧妙性和合理性保證了算法得到的路徑輸出均不相交，而且其時(shí)間復(fù)雜度是O（n）。文中證明了該多路徑算法在網(wǎng)絡(luò)信息傳輸發(fā)生錯(cuò)誤的情況下，消息分組在經(jīng)過(guò)多輪轉(zhuǎn)發(fā)之后，將自動(dòng)退出傳輸，而不會(huì)造成無(wú)限循環(huán)過(guò)程，算法輸出路徑長(zhǎng)度上界僅為n+1等多個(gè)有用的性質(zhì)。但是該算法假設(shè)在無(wú)故障節(jié)點(diǎn)的超立方體網(wǎng)絡(luò)中通信，并未考慮故障節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)不相交路徑路由算法的影響，也由于此路徑計(jì)算公式采用的參數(shù)少而導(dǎo)致每次取得的多路徑是同一個(gè)，因而缺少了路徑變換的靈活性。

2.2node to set不相交多路徑

針對(duì)超立方體網(wǎng)絡(luò)及類(lèi)似網(wǎng)絡(luò)的node to set節(jié)點(diǎn)不相交多路徑路由，學(xué)者們開(kāi)展了大量的研究工作，最近幾年的研究熱點(diǎn)均集中于存在部分節(jié)點(diǎn)或鏈接故障情形下的不相交路徑構(gòu)造策略和無(wú)故障情形下的最短不相交路徑策略。為此，本文僅討論近年來(lái)的最新研究成果。

Bassard在文獻(xiàn)[14]中研究了存在故障節(jié)點(diǎn)的超立方體的node to set問(wèn)題，提出了基于單個(gè)節(jié)點(diǎn)到達(dá)相鄰子立方體的最長(zhǎng)路徑為2的定理，并且給出了node to set節(jié)點(diǎn)不相交路徑的求解策略，得到的路徑長(zhǎng)度上限為n+k+4，其中，k為故障節(jié)點(diǎn)數(shù)量。該策略?xún)H僅限制了最長(zhǎng)路徑長(zhǎng)度的極限，每條路徑的建立是通過(guò)穿越不同的子立方體而得到的，這就決定了其建立的路徑平均長(zhǎng)度沒(méi)有包含在算法的優(yōu)化范圍內(nèi)。

Xiang等人在文獻(xiàn)[15]中證明了k-ary n-cube網(wǎng)絡(luò)中，最多存在2n-2條故障鏈路的情況下，在每對(duì)節(jié)點(diǎn)之間存在min{degH（u） ， degH（v）}（degH為節(jié)點(diǎn)可用鄰居數(shù)量的函數(shù)）條節(jié)點(diǎn)不相交路徑。也即證明了該網(wǎng)絡(luò)中鏈路故障數(shù)小于等于2n-2時(shí)，網(wǎng)絡(luò)路由是可靠的。該文獻(xiàn)沒(méi)有論述其在超立方體網(wǎng)絡(luò)情形下的解決方案。

文獻(xiàn)[16]提出了在無(wú)故障節(jié)點(diǎn)的超立方體中node to set節(jié)點(diǎn)不相交最短多路徑算法，算法的時(shí)間復(fù)雜度為O（mn），其中m為目標(biāo)節(jié)點(diǎn)數(shù)量。在該算法基礎(chǔ)上，文獻(xiàn)同時(shí)也給出了多路徑總長(zhǎng)度最小化的算法，其總的算法復(fù)雜度為O（m2n2.5+mn3）。雖然相對(duì)于類(lèi)似算法，該算法取得了在node to set節(jié)點(diǎn)不相交的最短路徑，并具有較低的時(shí)間復(fù)雜度，但是算法本身是建立在無(wú)故障節(jié)點(diǎn)的超立方體情形下，即使存在少量，在極端情況下甚至一個(gè)故障節(jié)點(diǎn)，就將導(dǎo)致算法的輸出結(jié)果的可用價(jià)值大幅減小。

3不相交路徑策略研究的發(fā)展方向

作為超立方體網(wǎng)絡(luò)負(fù)載的均衡性和通信的可靠性的重要保證，不相交路徑路由策略具有廣泛的應(yīng)用背景和重要的理論研究?jī)r(jià)值。尤其是如何在保證存在部分節(jié)點(diǎn)故障前提下實(shí)現(xiàn)不相交路徑路由，同時(shí)還要具有較高的效率，是當(dāng)前研究的熱點(diǎn)。然而，超立方體網(wǎng)絡(luò)中路徑的大量冗余和節(jié)點(diǎn)或連接故障出現(xiàn)的不可預(yù)測(cè)性等特性使不相交路徑路由機(jī)制設(shè)計(jì)面臨巨大而嚴(yán)峻的挑戰(zhàn)。近年來(lái)，相關(guān)研究從不同角度討論了不相交路徑路由機(jī)制，但由本文的分析可看出，該領(lǐng)域的研究?jī)H處于初步探討的階段，尚未建立成熟的理論體系和實(shí)踐標(biāo)準(zhǔn)。另外，還需重點(diǎn)考察超立方體網(wǎng)絡(luò)中故障節(jié)點(diǎn)數(shù)量對(duì)不相交路徑存在性，路徑的存在數(shù)量上的影響，設(shè)計(jì)支持節(jié)點(diǎn)故障動(dòng)態(tài)出現(xiàn)的多路徑路由協(xié)議，對(duì)現(xiàn)有協(xié)議進(jìn)行必要的修改，并且進(jìn)一步完善路由算法設(shè)計(jì)。

參考文獻(xiàn)：

[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