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

（1. 北京交通大學 計算機與信息技術學院，北京 100044；2. 清華大學 電子工程系，北京 100084；3. 北京交通大學 電子信息工程學院，北京 100044）

1 引言

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

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

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

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

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

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

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

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

非線性長度是歸一化的長度。當l( P)＞1.0時，路徑P至少有一維權重超出了約束C。

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

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

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

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

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

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

DIMCRA[10,11]算法由單約束的鏈路分離路徑算法LBA[10,11]演化而來，對RF算法有一定的改進。給定G( V, E)和約束C，其步驟如下。第 1步：執(zhí)行SAMCRA，尋找1條最短路徑1P；第2步：將1P的所有鏈路反向并置其權重為 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)絡的連通性。因此DIMCRA同樣不能保證對任意結構的網(wǎng)絡都可求得可行解和最優(yōu)解，如本文第5節(jié)的算例3和算例5。

3 MCLPRA

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

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

3.1 MCLPRA的求解步驟

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

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

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

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

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

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

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

第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é)點的2條鏈路分離路徑Pa, Pb所構成的鏈路集合中，找到滿足約束C且長度和最小的2條鏈路分離路徑。

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

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

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

3.2 MCLPRA的求解過程

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

圖1 等效變換

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

圖2 MCLPRA算例1

算例2 如圖3(a)所示網(wǎng)絡，C=(10,10)。MCLPRA第1步是在圖3(a)上運行SAMCRA得到最短路徑1P為sabct。第2步如圖3(b)所示，將sabct上的鏈路反向，重置鏈路權重為0。第3步在圖3(b)上運行SAMCRA，求得滿足2C約束的路徑集合S，求解結果只有一條路徑sbt滿足要求。第4步對S進行分類，sbt屬于Sβ，Sα為空。第5步搜索Sβ，調用Search_in_Linkjoint( )的過程，因為sbt與1P無共用鏈路，所以調用Search_in_nodeshared( )。在由1P和sbt鏈路構成的并集中，除了{sabct, sbt}這組鏈路分離的路徑，還有一組為{sabt, sbct}。由于路徑sbt的權向量為(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設計的科學性，從MCLPP解的構成形式入手證明MCLPRA求解結果與網(wǎng)絡結構無關，在此基礎上給出MCLPRA求得可行解和最優(yōu)解的控制參數(shù)T的取值。

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

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

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

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

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

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

圖4 P1與P2路徑的4種關系

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

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

③ 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é)點，也有共用鏈路，但所有共用節(jié)點都和共用鏈路關聯(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é)點也有共用鏈路，但并非所有共用節(jié)點都與共用鏈路關聯(lián)；

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

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

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

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

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

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

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

5 MCLPRA與DIMCRA的性能比較

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

5.1 算例比較

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

圖5 DIMCRA算例3

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

圖6 DIMCRA算例4

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

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

圖7 DIMCRA算例5

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

5.2 仿真比較

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

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

圖8 算法求解成功率比較

由圖8可以看出：① MCLPRA的可行解求解概率都高于相同情況下的 DIMCRA。2個算法的求解成功率都隨著網(wǎng)絡節(jié)點數(shù)的增加而提高，這是因為ρ一定的情況下，N越大網(wǎng)絡連接密度越高，網(wǎng)絡可行路徑數(shù)量也在增長，客觀存在可行解的概率就越大。②另外，仿真結果顯示MCLPRA的可行解求解率并不總是 100%。這是因為：MCLPRA基于SAMCRA，MCLPRA對任意拓撲均可保證求得可行解的前提條件是在第3步運行SAMCRA時求得并存儲所有滿足約束的可行解，因為計算機的實際存儲能力有限，仿真實驗中只選取所有滿足2C路徑中前20條最短路徑進行存儲和搜索，因而會有解的損失，要提高求解成功率，可以適當增加T的值；隨機生成的RGU很可能客觀上并不存在可行解，因而也就難以求解，這也是網(wǎng)絡節(jié)點數(shù)較少時，2種算法求解成功率都偏低的原因之一，即便如此，仿真結果仍表明即使在限制了搜索范圍的情況下，MCLPRA的可行解求解平均概率仍要高于DIMCRA。③在2約束條件下，MCLPRA和DIMCRA的平均求解概率都高于3約束的條件，這是因為約束個數(shù)越少網(wǎng)絡的可行路徑數(shù)目越多。

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

圖9 算法所求解的平均長度比較

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

圖10 算法所求解的平均長度比較

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

6 結束語

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

[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].鐵道學報, 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] 張品, 張堅武, 李樂民等. QoS約束下的鏈路分離問題的研究[J].通信學報, 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.