多加性QoS約束下的鏈路分離路由算法

熊軻，裘正定，張煜，張宏科

（1. 北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044；2. 清華大學(xué) 電子工程系，北京 100084；3. 北京交通大學(xué) 電子信息工程學(xué)院，北京 100044）

1 引言

網(wǎng)絡(luò)多媒體業(yè)務(wù)和實(shí)時(shí)性業(yè)務(wù)的飛速增漲，迫切要求網(wǎng)絡(luò)為其提供相應(yīng)的QoS保障。與此同時(shí)，光交換技術(shù)和傳輸技術(shù)的發(fā)展使得網(wǎng)絡(luò)的傳輸速率成倍增長(zhǎng)，在高速網(wǎng)絡(luò)中即使很短暫的鏈路失效，也會(huì)造成數(shù)據(jù)包的大量丟失和網(wǎng)絡(luò)QoS的急劇下降。如何提高網(wǎng)絡(luò)可靠性和QoS恢復(fù)能力已成為網(wǎng)絡(luò)研究的重要課題[1～3]。

在通信的源和目的節(jié)點(diǎn)間尋找滿足QoS約束的2條分離路徑，一條作為主用，另一條作為備用。在主用路徑失效時(shí)，將業(yè)務(wù)流迅速切換至備用路徑傳輸，被認(rèn)為是可同時(shí)提高網(wǎng)絡(luò)可靠性和QoS保障的重要方法[1,2,4～8]。多約束分離路徑亦十分有利于網(wǎng)絡(luò)流量工程、負(fù)載均衡和擁塞避免的實(shí)施。

通常QoS約束可分為鏈路約束和路徑約束2類。鏈路約束是對(duì)單條鏈路的約束，如帶寬約束，屬于凹性約束；路徑約束則指對(duì)傳輸路徑上所有鏈路QoS參數(shù)端到端總和的約束，如花費(fèi)(cost)、延時(shí)(delay)等約束，屬于加性約束。鏈路約束處理起來相對(duì)簡(jiǎn)單，只需在路徑計(jì)算前將不滿足約束條件的鏈路刪去即可[8]。路徑約束則需要將路徑上端到端的參數(shù)疊加起來考慮，因此要復(fù)雜的多。當(dāng)路徑約束個(gè)數(shù)大于2時(shí)，路由問題就變NP問題[9]。分離路徑包括鏈路分離和節(jié)點(diǎn)分離2類。前者要求路徑間無共用鏈路，后者要求路徑間無共用節(jié)點(diǎn)。節(jié)點(diǎn)分離一定為鏈路分離，反之則不成立。因此討論鏈路分離路徑是研究分離路徑問題的基礎(chǔ)。

本文主要研究多個(gè)加性QoS約束下的鏈路分離路徑算法，旨在在一對(duì)通信的源和目的節(jié)點(diǎn)間尋找2條鏈路分離且滿足多個(gè)加性QoS約束的路徑，并提出了與網(wǎng)絡(luò)結(jié)構(gòu)無關(guān)的多約束鏈路分離路徑路由算法(MCLPRA, multiple constrained link- disjoint path routing algorithm)，該算法基于多約束下的最短路徑精確算法(SAMCRA)[9,10]，在解的搜索過程中，首先對(duì)解空間按照解的不同構(gòu)成形式進(jìn)行分類，然后按類進(jìn)行搜索處理；引入了控制搜索精度和深度的控制參數(shù)，能夠保證對(duì)任意結(jié)構(gòu)網(wǎng)絡(luò)求得可行解。

2 問題描述及研究現(xiàn)狀

將網(wǎng)絡(luò)抽象為加權(quán)有向圖，記為G( V, E)。網(wǎng)絡(luò)中的路由設(shè)備和通信鏈路分別用圖中的節(jié)點(diǎn)和有向邊表示。V代表G中節(jié)點(diǎn)的集合，E代表G中有向邊的集合，(u, v)表示從節(jié)點(diǎn)u到節(jié)點(diǎn)v的一條有向邊。G中每條邊都帶有m維的加性權(quán)重向量W( u, v)=[w1( u, v), w2( u, v),…,wm(u, v)]。用s和t分別代表通信的源和目的節(jié)點(diǎn)，P為從s到t的一條路徑，wi( P)表示P的第i維權(quán)重，路徑P的權(quán)向量W( P)=[w1( P), w2( P),…,wm(P)]，其中

用E( P)={(u, v)|(u, v)∈P}代表路徑P上的邊的集合，用V( P)代表路徑P上的節(jié)點(diǎn)集合，V( P)={u|＜u, v＞∈P或＜v, u＞∈P}。

定義1 非線性長(zhǎng)度。給定帶m維權(quán)重的加權(quán)有向圖G(V, E)和m維約束向量C，C=[c1, c2,…,cm]，G中路徑P的非線性長(zhǎng)度定義為[9,10]

非線性長(zhǎng)度是歸一化的長(zhǎng)度。當(dāng)l( P)＞1.0時(shí)，路徑P至少有一維權(quán)重超出了約束C。

定義2 鏈路分離路徑(link-disjoint path)假設(shè)P1和P2為G( V, E)中的2條路徑，若E( P1)∩E( P2)=?，則P1與P2為鏈路分離路徑。

定義3 多約束鏈路分離路徑對(duì)(MCLPP, multiple constrained link-disjoint path pair)問題。給定一個(gè)加權(quán)有向圖G( V, E)和一個(gè)m維的約束向量C=[c1, c2,…,cm]，m≥2。MCLPP問題的目的是在源s和目的t節(jié)點(diǎn)之間找到2條路徑P1與P2，要求E( P1)∩E( P2)=?，且P1與P2均滿足約束C，即wi( P1)≤ci, wi( P2)≤ci，1≤i≤m。

實(shí)際上，在s和t間可能同時(shí)存在多條滿足約束C的鏈路分離路徑對(duì)，往往希望找到路徑總長(zhǎng)最小的一對(duì)。當(dāng)l( P1)+l( P2)為最小時(shí)，定義{P1, P2}為MCLPP的最優(yōu)解。

近年來，多QoS約束鏈路分離路由問題受到了研究者的廣泛關(guān)注，然而新的研究基本都是針對(duì)delay單個(gè)約束的，旨在找出一對(duì)鏈路分離路徑，在滿足delay約束的前提下達(dá)到2條路徑總的cost最小。當(dāng)給定的delay約束針對(duì)的是路徑對(duì)中的每條路徑的延時(shí)時(shí)，問題被稱為DCLDOP-I，當(dāng)delay約束針對(duì)的是路徑對(duì)中2條路徑延時(shí)的總和時(shí)，問題被稱為DCLDOP-II。文獻(xiàn)[13]對(duì)DCLDOP-I和DCLDOP-II問題進(jìn)行了建模，證明了這2種問題都屬于NP完全問題。文獻(xiàn)[14]提出了針對(duì)這2種問題的近似求解算法。文獻(xiàn)[15]對(duì)DCLDOP-II問題進(jìn)行了研究，提出了單條鏈路失效下的路徑恢復(fù)算法。文獻(xiàn)[16]研究了Min-Min問題，旨在求解2條滿足QoS約束的分離路徑，且實(shí)現(xiàn)較短的路徑cost最小。文獻(xiàn)[17]采用了將 2個(gè)加性權(quán)值進(jìn)行線性組合的方法來求解滿足QoS約束的分離路徑，并給出了求解算法，所提算法雖然簡(jiǎn)單，卻不能保證一定能求得可行解。

MCLPP問題由文獻(xiàn)[11,12]提出并證明了MCLPP為NP完全問題，分析了多約束鏈路分離路徑問題與單約束鏈路分離路徑問題的不同，且給出了啟發(fā)式求解算法 DIMCRA。本文在文獻(xiàn)[11,12]的基礎(chǔ)上，對(duì)MCLPP進(jìn)行了進(jìn)一步的研究，旨在通信的源和目的節(jié)點(diǎn)間找到一對(duì)鏈路分離路徑，且每條路徑都滿足2個(gè)或2個(gè)以上的QoS約束。

目前求解 MCLPP問題的最直觀的算法為 RF算法。其原理是：先計(jì)算一條滿足QoS約束的最短路徑，然后刪去該路徑上的所有鏈路的修正圖，再在修正圖中解得另一條最短路徑。RF算法能保證所求得的2條路徑為鏈路分離路徑，但由于在求解過程中刪去了第一條路徑上的鏈路，破壞了原網(wǎng)絡(luò)的連通性，導(dǎo)致很多情況下得不到最優(yōu)解，甚至連可行解也得不到。

DIMCRA[10,11]算法由單約束的鏈路分離路徑算法LBA[10,11]演化而來，對(duì)RF算法有一定的改進(jìn)。給定G( V, E)和約束C，其步驟如下。第 1步：執(zhí)行SAMCRA，尋找1條最短路徑1P；第2步：將1P的所有鏈路反向并置其權(quán)重為 0，得修正圖G′( V, E )；第3步：在 G ′( V, E )中執(zhí)行SAMCRA，尋找1條滿足約束2C的最短路徑 P2，若 P2不存在，算法停止；第4步：取 P1和 P2的并集，刪去反向鏈路出現(xiàn)在 P1上的 P2的鏈路和反向鏈路出現(xiàn)在 P2上的 P1的鏈路，將余下的鏈路組成2條路徑 { P1′, P2′} ；第 5步：檢查集合 { P1′, P2′}中的每條路徑，若路徑Pi′(i=1,2)不滿足約束，則從修正圖 G ′( V, E )中刪去 Pi′與 P1未發(fā)生交疊的鏈路集合，得到更新的修正圖 G ′′( V, E )，返回第3步；否則，算法停止。

與RF一樣，DIMCRA也能保證所求解一定滿足鏈路分離，但由于在解搜索過程中采用了刪除不滿足約束條件的路徑上的部分或全部鏈路的方法，見算法第 5步，亦破壞了網(wǎng)絡(luò)的連通性。因此DIMCRA同樣不能保證對(duì)任意結(jié)構(gòu)的網(wǎng)絡(luò)都可求得可行解和最優(yōu)解，如本文第5節(jié)的算例3和算例5。

3 MCLPRA

針對(duì)上述問題，本文提出了 MCLPRA。與DIMCRA算法相似，MCLPRA也以SAMCRA為基礎(chǔ)，充分利用了SAMCRA的幾個(gè)特點(diǎn)：①基于非線性長(zhǎng)度；②k-shortest path特性，即在求解最短路徑的搜索過程中，不僅可以得到最短路徑，也可以得到第2短路徑，……，第k短路徑；③多約束路由最短路徑的無環(huán)路精確算法。

MCLPRA采用先將解空間分類，然后按類進(jìn)行搜索處理的方法。在算法處理過程中，保持了原網(wǎng)絡(luò)的結(jié)構(gòu)和連通性，確保了解空間的完整性，引入了搜索深度控制參數(shù)，能夠保障對(duì)任意網(wǎng)絡(luò)求得可行解。需要補(bǔ)充說明的是，DIMCRA的第3步僅求得了最短的一條2P，而MCLPRA利用了SAMCRA的k-shortest path特性，對(duì)SAMCRA進(jìn)行了修改，使其在一次運(yùn)行過程中可將滿足約束的所有2P路徑記錄下來，然后將這些路徑按類處理，進(jìn)行解的搜索。

3.1 MCLPRA的求解步驟

下面給出 MCLPRA的求解步驟，給定加權(quán)有向圖G( V, E)和約束向量C。

第1步：執(zhí)行SAMCRA，求1條最短路徑1P；

第2步：將1P的所有鏈路反向并置其權(quán)重為0，得修正圖 G ′( V, E )；

第3步：在修正圖 G ′( V, E )中運(yùn)行SAMCRA，計(jì)算出從s到t的滿足約束向量2C的k條最短路徑集合 S = { P1′ , … ,Pk′}，如果S為空，算法停止；

第4步：將S按如下規(guī)則分成2個(gè)子集：

下面給出Search_Sβ(P1, Sβ,T)的處理過程，其中T為搜索深度控制參數(shù)。

接下來介紹Search_in_Linkjoint(Pa, Pb)的步驟。功能是從有共用鏈路的2條路徑Pa, Pb的鏈路所構(gòu)成的集合中搜索滿足約束的可行解。

第1步：取Pa和Pb的并集，從中刪去反向鏈路出現(xiàn)在Pa上的Pb鏈路和反向鏈路出現(xiàn)在Pb上的Pa上的鏈路，將余下的鏈路組成2條路徑{Px, Pw};

第2步：

if V( Px)∩{V( Pw)-s-t}=V( E( Px)∩E( Pw))≠?

最后介紹Search_in_nodeshared(Pa, Pb)的步驟。功能是從有共用節(jié)點(diǎn)的2條鏈路分離路徑Pa, Pb所構(gòu)成的鏈路集合中，找到滿足約束C且長(zhǎng)度和最小的2條鏈路分離路徑。

第1步：取Pa和Pb的并集，由Pa和Pb的鏈路構(gòu)成一個(gè)G( V, E)的子圖Gsub；

第2步：對(duì)Gsub做如圖1所示的等效變換，在等效圖中找到由Gsub鏈路構(gòu)成的2條滿足約束的鏈路分離路徑{,}，且l()+l()為最小。

對(duì)圖1(a)的結(jié)構(gòu)，通過合并出度與入度都為1的節(jié)點(diǎn)相連接的鏈路，可得到等效圖1(b)，在圖1(b)的結(jié)構(gòu)中易找到s和t之間的非線性長(zhǎng)度和最小的鏈路分離路徑對(duì)，圖1(b)中為{sabt, sbcdt}。

3.2 MCLPRA的求解過程

下面通過算例說明MCLPRA的求解過程。

圖1 等效變換

算例1 如圖2(a)所示網(wǎng)絡(luò)，C=(10,10)。目的是在源節(jié)點(diǎn)s和目的節(jié)點(diǎn)t間尋找一對(duì)滿足C約束條件的鏈路分離路徑。第1步在圖2(a)上運(yùn)行SAMCRA得到最短路徑P1為sabt。第2步如圖2(b)所示，將sabt上的鏈路反向，并且重置鏈路權(quán)重為0。第3步在圖2(b)上運(yùn)行SAMCRA，求得滿足2C約束的路徑集合S={sdt, sbat}。第4步對(duì)S進(jìn)行分類，sbat∈Sβ，sdt∈Sα。第5步先查找Sα中的最短路徑，Sα中只有一條路徑sdt，故Pα=sdt。然后調(diào)用Search_Sβ()搜索Sβ構(gòu)成的可行解中的最優(yōu)解。取Sβ中的最短路徑sbat，由于sbat與1P有共用鏈路，所以調(diào)用Search_in_Linkjoint()處理，從sabt和sbat鏈路構(gòu)成的并集中去掉共用鏈路ab，剩余鏈路構(gòu)成2條鏈路分離路徑{sat, sbt}，經(jīng)判斷sat與sbt均滿足約束C，故{sat, sbt}為Sβ與1P構(gòu)成的最優(yōu)解。因?yàn)镻1和sdt均滿足約束C且l( sat)+l( sbt)＜l( sabt)+l( sdt)，故{sat, sbt}為最終解。顯然，該解為圖2(a)上的最優(yōu)解。

圖2 MCLPRA算例1

算例2 如圖3(a)所示網(wǎng)絡(luò)，C=(10,10)。MCLPRA第1步是在圖3(a)上運(yùn)行SAMCRA得到最短路徑1P為sabct。第2步如圖3(b)所示，將sabct上的鏈路反向，重置鏈路權(quán)重為0。第3步在圖3(b)上運(yùn)行SAMCRA，求得滿足2C約束的路徑集合S，求解結(jié)果只有一條路徑sbt滿足要求。第4步對(duì)S進(jìn)行分類，sbt屬于Sβ，Sα為空。第5步搜索Sβ，調(diào)用Search_in_Linkjoint( )的過程，因?yàn)閟bt與1P無共用鏈路，所以調(diào)用Search_in_nodeshared( )。在由1P和sbt鏈路構(gòu)成的并集中，除了{(lán)sabct, sbt}這組鏈路分離的路徑，還有一組為{sabt, sbct}。由于路徑sbt的權(quán)向量為(11,2)，不滿足約束條件(10,10)，故{sabct, sbt}不能作為MCLPRA的解。經(jīng)判斷，sabt和sbct均滿足約束條件，故在算例2中，MCLPRA的解為{sabt, sbct}，該解也是圖3(a)上的最優(yōu)解。

圖3 MCLPRA算例2

4 MCLPRA特性分析

本節(jié)將從理論上分析MCLPRA設(shè)計(jì)的科學(xué)性，從MCLPP解的構(gòu)成形式入手證明MCLPRA求解結(jié)果與網(wǎng)絡(luò)結(jié)構(gòu)無關(guān)，在此基礎(chǔ)上給出MCLPRA求得可行解和最優(yōu)解的控制參數(shù)T的取值。

定理1 給定加權(quán)有向圖G( V, E)，1P為節(jié)點(diǎn)s和t間非線性長(zhǎng)度最短路徑，若s和t間滿足約束向量C(dim(C)≥2)的MCLPP問題的最優(yōu)解{P1*,P2*}存在，則{E( P1*)∪E( P2*)}∩E( P1)≠?成立。

證明 假設(shè){E( P1*)∪E( P2*)}∩E( P1)=?，則有E( P1*)∩E( P1)=?且E( P2*)∩E( P1)=?。因?yàn)镻1*和P2*鏈路分離，故E( P1*)∪E( P2*)=?。因此，P1*、P2*和P1為鏈路彼此分離的3條路徑。又因?yàn)镻1為s和t間的最短路徑，可得

這與定理1題設(shè){P1*,P2*}為最優(yōu)解矛盾，故假設(shè)不成立。定理1得證。

推論1 給定加權(quán)有向圖G( V, E)，P1為節(jié)點(diǎn)s和t間非線性長(zhǎng)度最短路徑，若s和t間滿足約束向量C(dim(C)≥2)的MCLPP問題的最優(yōu)解{P1*,P2*}存在，當(dāng)且僅當(dāng)E( P1*)∩E( P1)=?時(shí)，P1=P2*(P1*和P2*互換推論1仍然成立)。

證明 由定理1{E( P1*)∪E( P2*)}∩E( P1)≠?，所以有E( P1*)∩E( P1)≠?或E( P2*)∩E( P1)≠?。假設(shè)E( P1*)∩E( P1)=?，若P2*≠P1，最優(yōu)鏈路分離路徑對(duì)則為{P1, P1*}，這與推論1題設(shè)矛盾，假設(shè)不成立，必要性得證。若P2*=P1，因和P2*為鏈路P1*分離路徑對(duì)，E( P1*)∩E( P1)=?，充分性得證。故推論1成立。

定理1和推論1說明了對(duì)于任意結(jié)構(gòu)的網(wǎng)絡(luò)，如果MCLPP的最優(yōu)鏈路分離路徑對(duì){P1*,P2*}存在，最短路徑要么與P1*和P2*都相交，要么和其中的一條重合。故給定加權(quán)有向圖G( V, E)，P1為從源、目的間的最短路徑。S={P1′,…,Pk′}為MCLPRA第3步求得結(jié)果。?P2∈{P1′,…,Pk′}，P1與P2的結(jié)構(gòu)關(guān)系只能為下列4種情況之一。

圖4 P1與P2路徑的4種關(guān)系

① E( P1)∩E( P2)=? 且V( P1)∩{V( P2)-s-t}=?，如圖4(a)所示，P1與P2既無共用節(jié)點(diǎn)，也無共用鏈路；

② E( P1)∩E( P2)=?,V( P1)∩{V( P2)-s-t}≠?，如圖4(b)所示，P1與P2有共用節(jié)點(diǎn)，但無共用鏈路；

③ E( P1)∩E( P2)≠?, V( P1)∩{V( P2)-s-t}≠?且V( P1)∩{V( P2)-s-t}=V( E( P1)∩E( P2))，如圖4(c)所示，P1與P2既有共用節(jié)點(diǎn)，也有共用鏈路，但所有共用節(jié)點(diǎn)都和共用鏈路關(guān)聯(lián)；

④ E( P1)∩E( P2)≠? ，V( P1)∩{V( P2)-s-t}≠?且V( P1)∩{V( P2)-s-t}≠V( E( P1)∩E( P2))，如圖4(d)所示，P1與P2既有共用節(jié)點(diǎn)也有共用鏈路，但并非所有共用節(jié)點(diǎn)都與共用鏈路關(guān)聯(lián)；

在上述表達(dá)式中，E( P1)∩E( P2)表示P1與P2共用的鏈路的集合，V( E( P1)∩E( P2))表示P1與P2所有共用鏈路上的節(jié)點(diǎn)的集合；

?P2∈{P1′,…,Pk′}，若P1和P2屬于第①種關(guān)系，則{P1′,…,Pk′}中的最短路徑min{P1′,…,Pk′}和P1構(gòu)成的鏈路分離路徑對(duì)即為總長(zhǎng)最短的鏈路分離的路徑對(duì)，如果P1和min{P1′,…,Pk′ }均滿足約束，則{P1,min{P1′,…,Pk′ }}為最優(yōu)解；若P1和P2屬于第②種關(guān)系，P1和P2可構(gòu)成多組鏈路分離路徑對(duì)（如圖4(b)的結(jié)構(gòu)中存在2組鏈路分離路徑對(duì)），處理方法是從滿足約束的路徑對(duì)中選取總長(zhǎng)度最小的一組作為最優(yōu)解，具體過程見Search_in_nodeshared()的處理過程；若P1和P2屬于第③種關(guān)系，可先將P1和P2共用的鏈路去除，將其轉(zhuǎn)換成情況①進(jìn)行處理；若P1和P2屬于第④種關(guān)系，可先將P1和P2共用的鏈路刪除，將其轉(zhuǎn)換成情況②進(jìn)行處理；對(duì)情況③和④的詳細(xì)處理過程見第2節(jié)的Search_in_ Linkjoint( )。

在給定的任意網(wǎng)絡(luò)中，由MCLPRA第3步求得的集合S={P1′,…,Pk′}上的路徑P2與P1的關(guān)系必然屬于上述4種關(guān)系中的一種。MCLPRA第4步先對(duì)S上的路徑按照與P1的結(jié)構(gòu)關(guān)系進(jìn)行分類，再針對(duì)不同情況分別進(jìn)行處理，最后比較選取各種情況下的最優(yōu)解作為最終求解結(jié)果，以此來保證尋求所得可行解中的最優(yōu)解。定理1、推論1以及MCLPP解構(gòu)成的4種可能情況表明了本文所提算法MCLPRA采用先計(jì)算最短路徑P1，再求{P1′,…,Pk′}，然后按類處理求解過程的科學(xué)性。MCLPRA在求解過程中未對(duì)原網(wǎng)絡(luò)拓?fù)溥M(jìn)行改變，保持了網(wǎng)絡(luò)的連通性和解空間的完整性，故求解結(jié)果與網(wǎng)絡(luò)的結(jié)構(gòu)無關(guān)。

由MCLPRA求解步驟可以看出，在Search_Sβ()操作中引入了參數(shù)T來控制搜索的精度和深度，本文將T設(shè)置為減計(jì)數(shù)器來控制搜索循環(huán)的次數(shù)。

證明 MCLPRA第3步采用SAMCRA計(jì)算出圖中所有滿足2C約束的路徑集合S={P1′,…,Pk′}。根據(jù)定理1、推論1和對(duì)解構(gòu)成的4種情況的分析，MCLPP的最優(yōu)解一定由P2與P1構(gòu)成，P2∈S。根據(jù)MCLPRA，Sα∪Sβ=S ， Sα為滿足情況①的P2的集合，Sβ為情況②、③和④的集合，MCLPRA分別求得Sα上的最優(yōu)解和Sβ上的最優(yōu)解，選擇其中最優(yōu)的一組為最終解。對(duì)于Sα，Sα中最短的路徑Pα與P1組成的分離路徑對(duì)即為Sα上的最優(yōu)解。對(duì)于Sβ，在Search_Sβ()中參數(shù)T可控制搜索Sβ的深度。根據(jù)算法過程，在搜索的每一次循環(huán)中，Sβ的當(dāng)前最短路徑在處理完后被刪除，而T的值也被減1，當(dāng)Sβ中的路徑全被處理完畢時(shí)，即可搜索到Sβ上的最優(yōu)解，當(dāng)可以保證Sβ上的路徑被全部處理，因而時(shí)可確保MCLPRA所得最優(yōu)解不丟失。

推論2 當(dāng)T取判決條件——在Sβ中搜索到與1P構(gòu)成滿足約束條件的鏈路分離路徑的一組可行解就退出搜索循環(huán)時(shí)，MCLPRA能夠保障對(duì)任意結(jié)構(gòu)的網(wǎng)絡(luò)求得可行解，并且該可行解為當(dāng)前搜索深度下的可行解中的最優(yōu)解。

證明 根據(jù)前文所述，MCLPRA的可行解落在Sα和Sβ與最短路徑1P構(gòu)成的路徑對(duì)上。Sα中最短的路徑Pα與1P組成的分離路徑對(duì)即為Sα上的最優(yōu)解。對(duì)于Sβ，如果在Sβ中搜索到與1P構(gòu)成滿足約束條件的鏈路分離路徑的一組可行解就退出搜索。根據(jù)算法過程，MCLPRA的最終解為該組可行解與Sα上可行解中最優(yōu)的一組。推論2得證。

5 MCLPRA與DIMCRA的性能比較

DIMCRA是目前求解 MCLPP問題最有效算法，故對(duì)MCLPRA和DIMCRA進(jìn)行對(duì)比分析。

5.1 算例比較

算例3 仍取算例1中的網(wǎng)絡(luò)和相同的約束，如圖5(a)所示。若運(yùn)行DIMCRA，第1、2步的運(yùn)行過程和結(jié)果與MCLPRA的第1、2步一樣（見圖5(a)和圖5(b)），所得最短路徑1P為sabt。第 3步，在圖 5(b)上運(yùn)行SAMCRA，解得最短的路徑2P為sdt。第4步，因?yàn)?P和2P已經(jīng)是鏈路分離路徑，轉(zhuǎn)至第5步。經(jīng)判斷，1P和2P均滿足約束C，算法結(jié)束。所以DIMCRA在圖5(a)的網(wǎng)絡(luò)上的求解結(jié)果為{s abt, s dt}。顯然{s abt, s d t}僅為圖5(a)上的一個(gè)可行解，并非最優(yōu)解，而MCLPRA可以求得最優(yōu)解(見算例1)。

圖5 DIMCRA算例3

算例 4 仍采用圖 5(a)的拓?fù)?，將約束向量修改為 C = ( 7,7)。運(yùn)行 MCLPRA，求解過程與結(jié)果仍與算例1相同。若運(yùn)行DIMCRA，前4步過程和圖 5(a)、圖 5(b)和圖 5(c)相同，可求得1P=sabt，2P=sdt。在第5步中，因?yàn)?P的權(quán)向量為(7,8)，不滿足C的約束，故2P上與1P不相交鏈路被刪除，結(jié)果得到圖6(a)所示的修正圖，并返回第3步，在圖6(a)上重新運(yùn)行SAMCRA求得新的最短路徑sbat。第4步將sbat與1P的鏈路并集中共用鏈路ab刪除，將剩余鏈路組成2條新的鏈路分離路徑{sat, sbt}。第5步判斷{sat, sbt}滿足約束為DIMCRA的最終解。

圖6 DIMCRA算例4

在算例4中，雖然DIMCRA得到了與MCLPRA相同的解，但運(yùn)行了3次SAMCRA，而MCLPRA僅運(yùn)行了2次SAMCRA。

算例5 采用圖3(a)所示的拓?fù)浜拖嗤募s束。若運(yùn)行DIMCRA，前3步與MCLPRA相同，如圖3(a)、圖 3(b)和圖 3(c)所示，可得到1P=sabct，2P=sbt。第4步，因?yàn)?P與2P無共用鏈路，轉(zhuǎn)而執(zhí)行第5步。由于2P的權(quán)向量為(11,2)，不滿足C的約束，故2P與1P不相交的鏈路被刪除，結(jié)果得圖7所示修正圖，然后返回第3步。顯然，在圖7的結(jié)構(gòu)上，已不存在從s到t的路徑，算法終止，故此算例中 DIMCRA返回為無解。而算例 2已表明MCLPRA可以在圖3(a)的網(wǎng)絡(luò)上得到最優(yōu)解。

圖7 DIMCRA算例5

綜上所述，MCLPRA的求解能力要高于DIMCRA。原因在于：① DIMCRA對(duì)2P采用了計(jì)算出一條就處理一條的方法，一旦滿足約束條件就終止算法。這樣的過程實(shí)際上求得的只是算法最先搜索到的可行解，并未進(jìn)行最優(yōu)解的搜索處理，因而DIMCRA不能保證對(duì)任意網(wǎng)絡(luò)求得最優(yōu)解；② DIMCRA的第5步，對(duì)不能和1P構(gòu)造滿足約束條件的分離路徑對(duì)的2P，采用刪鏈路的處理，破壞了網(wǎng)絡(luò)的原本結(jié)構(gòu)和連通性，導(dǎo)致了可行解和最優(yōu)解的丟失，因而也不能保證對(duì)任意網(wǎng)絡(luò)求得可行解；③MCLPRA避免了DIMCRA上述幾個(gè)問題，是一種與網(wǎng)絡(luò)結(jié)構(gòu)無關(guān)的MCLPP求解算法，這一點(diǎn)第4節(jié)已論證。

5.2 仿真比較

本小節(jié)通過仿真實(shí)驗(yàn)對(duì)這2個(gè)算法進(jìn)行比較，仿真采用隨機(jī)拓?fù)鋱D(RGU)[18]，RGU圖的節(jié)點(diǎn)數(shù)為N，鏈路密度ρ取值為0.2。每條鏈路都帶有m維的加性權(quán)重, 每維權(quán)重均服從[0,1]上的均勻分布。仿真所用計(jì)算機(jī)CPU主頻為1.9GHz，內(nèi)存為1G。RGU圖的節(jié)點(diǎn)數(shù)取為 100、150、200、250、300、350、400、450和500，每個(gè)N上生成1 000個(gè)RGU。取 ci=1(1 ≤ i ≤ m )，在m=2和m=3的條件下分別進(jìn)行實(shí)驗(yàn)。每個(gè)RGU上運(yùn)行MCLPRA和DIMCRA各1次。

圖8給出了MCLPRA和DIMCRA分別在2約束和3約束下每個(gè)N上的1 000個(gè)RGU上成功求解的比率。

圖8 算法求解成功率比較

由圖8可以看出：① MCLPRA的可行解求解概率都高于相同情況下的 DIMCRA。2個(gè)算法的求解成功率都隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加而提高，這是因?yàn)棣岩欢ǖ那闆r下，N越大網(wǎng)絡(luò)連接密度越高，網(wǎng)絡(luò)可行路徑數(shù)量也在增長(zhǎng)，客觀存在可行解的概率就越大。②另外，仿真結(jié)果顯示MCLPRA的可行解求解率并不總是 100%。這是因?yàn)椋篗CLPRA基于SAMCRA，MCLPRA對(duì)任意拓?fù)渚杀ＷC求得可行解的前提條件是在第3步運(yùn)行SAMCRA時(shí)求得并存儲(chǔ)所有滿足約束的可行解，因?yàn)橛?jì)算機(jī)的實(shí)際存儲(chǔ)能力有限，仿真實(shí)驗(yàn)中只選取所有滿足2C路徑中前20條最短路徑進(jìn)行存儲(chǔ)和搜索，因而會(huì)有解的損失，要提高求解成功率，可以適當(dāng)增加T的值；隨機(jī)生成的RGU很可能客觀上并不存在可行解，因而也就難以求解，這也是網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較少時(shí)，2種算法求解成功率都偏低的原因之一，即便如此，仿真結(jié)果仍表明即使在限制了搜索范圍的情況下，MCLPRA的可行解求解平均概率仍要高于DIMCRA。③在2約束條件下，MCLPRA和DIMCRA的平均求解概率都高于3約束的條件，這是因?yàn)榧s束個(gè)數(shù)越少網(wǎng)絡(luò)的可行路徑數(shù)目越多。

圖9給出了MCLPRA和DIMCRA分別在2約束和3約束下在每個(gè)N上的1 000個(gè)RGU上所求分離路徑對(duì)的平均非線性長(zhǎng)度和情況。結(jié)果表明，MCLPRA所求解的平均總長(zhǎng)度明顯小于 DIMCRA所求解的平均總長(zhǎng)度，即MCLPRA所求解優(yōu)于DIMCRA。

圖9 算法所求解的平均長(zhǎng)度比較

圖10給出了MCLPRA和DIMCRA分別在2約束和3約束下在每個(gè)N上的1 000個(gè)RGU平均執(zhí)行時(shí)間開銷對(duì)比結(jié)果。結(jié)果顯示，MCLPRA的時(shí)間開銷略高于DIMCRA，這是因?yàn)橐獙?shí)現(xiàn)算法更高的求解率和更優(yōu)的求解結(jié)果, 往往需要以增加一定的復(fù)雜性為代價(jià)。從圖中可以看出，節(jié)點(diǎn)數(shù)在500，平均連接度達(dá)200的情況下(即高密度連接的復(fù)雜網(wǎng)絡(luò))，算法的執(zhí)行時(shí)間開銷仍在數(shù)百毫秒，這對(duì)網(wǎng)絡(luò)的路由計(jì)算仍處于可行的范圍之內(nèi)。

圖10 算法所求解的平均長(zhǎng)度比較

上述實(shí)驗(yàn)說明MCLPRA在可行的執(zhí)行開銷內(nèi)，求解成功率和所求解都明顯優(yōu)于現(xiàn)有算法。

6 結(jié)束語

本文針對(duì)多個(gè)加性 QoS約束下的鏈路分離算法進(jìn)行了研究，提出了基于解空間分類搜索的算法MCLPRA，給出了MCLPRA的求解過程。從理論上分析了 MCLPP問題解的構(gòu)成形式，證明了MCLPRA對(duì)任意結(jié)構(gòu)的網(wǎng)絡(luò)均可求得最優(yōu)解，并給出了 MCLPRA求得最優(yōu)解的控制參數(shù)取值條件。通過理論分析和仿真比較，MCLPRA均可獲得比DIMCRA更優(yōu)的求解性能。筆者下一步工作將對(duì)MCLPRA進(jìn)行優(yōu)化和改進(jìn)，并進(jìn)一步降低其算法復(fù)雜性。

[1] DAS A, MARTEL C, MUKHERJEE B, et al. A better approach to reliable multi-path provisioning[A]. IEEE Global Communications Conferences (GLOBECOM)[C]. 2007. 2724-2728.

[2] SAWADA N, KANEKO K. Pairwise disjoint paths in pancake graphs[A]. Eighth International Conference on Parallel and Distributed Computing, Applications and Technologies, DPCAT ’07[C]. 2007.376-382.

[3] CHEN S, NAHRSTEDT K. On finding multi-constrained paths[A].IEEE International Conference on Communications ICC’98[C]. 1998.874-879.

[4] TAFT-PLOTKIN N, BELLUR B, OGIER R. Quality-of-service routing using maximally disjoint paths[A]. The 7th International Workshop on Quality-of-Service[C]. 1999. 119-128.

[5] GUO L, LI L M, CAO J, et al. On finding feasible solutions with shared backup resources for surviving double-link failures in path-protected WDM mesh networks[J]. Journal of Lightwave Technology, 2007, 25(1): 287-296.

[6] XIONG K, QIU Z D, ZHANG H K, Towards link-disjoint paths under multiple additive QoS constraints[A]. The 2nd IET International Conference on Wireless Mobile and Multimedia Networks (ICWMMN)[C].2008. 119-127.

[7] XU D H, QUAO C M, XIONG Y Z. Ultrafast potential-backup-cost(PBC)-based shared path protection schemes[J]. Journal of Lightwave Technology, 2007, 25(8): 2251-2259.

[8] VAN MIEGHEM P, DE NEVE H, KUIPERS F. Hop-by-hop quality of service routing[J]. Computer Networks, 2001, 37(3/4): 407-423.

[9] XUE G L, SEN A, ZHANG W Y, et al. Finding a path subject to many additive QoS constraints [J]. IEEE/ACM Transactions on Networking,2007, 15(1): 201-211.

[10] VAN MIEGHEM P, KUIPERS F. Concepts of exact QoS routing algorithms[J]. IEEE/ACM Transactions on Networking, 2004, 12(5):851-864.

[11] GUO Y C, KUIPERS F, VAN MIEGHEM P. Link disjoint paths algorithm for reliable QoS routing[J]. International Journal of Communication Systems, 2003, 16(9): 779-798.

[12] 郭宇春, KUIPERS F, MIEGHEM P V等. 多約束分離路徑算法[J].鐵道學(xué)報(bào), 2005, 27(2): 49-57.GUO Y C, KUIPERS F, VAN MIEGHEM P, et al. Disjoint multiple-constrained paths algorithms[J]. Journal of the China Railway Society, 2005, 27(2): 49-57.

[13] 張品, 張堅(jiān)武, 李樂民等. QoS約束下的鏈路分離問題的研究[J].通信學(xué)報(bào), 2006, 27(6): 37-42.ZHANG P, ZHANG J W, LI L M, et al. Researches on the problem of link disjoint paths with QoS constraints[J]. Journal on Communications, 2006, 27(6): 37-42.

[14] CHAO P, HONG S. An improved approximation algorithm for computing disjoint QoS paths[A]. IEEE ICN/ICONS/MCL[C]. 2006.

[15] NASER H, GONG M. Link-disjoint shortest-delay path-pair computation algorithms for shared mesh restoration networks[A]. IEEE Symposium on Computers and Communications[C]. 2007. 269-274

[16] XU D H, CHEN Y, XIONG Y Z, QIAO C M, et al. On the complexity of and algorithms for finding the shortest path with a disjoint counterpart[J]. IEEE/ACM Transctions on Networking, 2006,14(1): 147-158.

[17] XIAO Y, THULASIRAMAN K, XUE G L. Constrained shortest link-disjoint paths selection: a network programming based approach[J]. IEEE Transactions on Circuits and Systems-I: Regular Papers, 2006, 53(5): 1174-1187.

[18] BOLLOBáS B. Random Graphs[M]. MA: Cambridge Univ, Press,2001.