一種多約束最優(yōu)路徑寬度優(yōu)先松弛算法

摘要：在分析單播QoS路由問題的基礎(chǔ)上，提出了寬度優(yōu)先松弛算法BFRA，其核心思想是基于改進(jìn)的寬度優(yōu)先搜索策略，采用特殊的松弛算法分別前向（從源節(jié)點）和后向（從目標(biāo)節(jié)點）搜索網(wǎng)絡(luò)拓?fù)?。前向搜索預(yù)先計算路徑的綜合度量、約束等參數(shù)，收集路徑信息;后向搜索則采用Costmeasurement策略對路徑進(jìn)行選擇和篩選，不斷搜索到新的可行路徑，并選取最優(yōu)路徑。討論了在路徑振蕩時BFRA選取次優(yōu)路徑，為其他QoS流的接入預(yù)留了資源。理論分析表明BFRA保存的狀態(tài)信息較少，時間復(fù)雜度為線性，仿真結(jié)果表明，BFRA發(fā)現(xiàn)最優(yōu)路徑的成功率較高。

關(guān)鍵詞：多約束； 花費； 前向搜索； 后向搜索； 松弛； 路徑振蕩

中圖法分類號：TP301．6文獻(xiàn)標(biāo)識碼：A

文章編號：1001－3695(2007)01－0090-04

當(dāng)前的研究主要集中在搜索出滿足多個約束的單播QoS路徑上。QoS路由算法主要有最短最寬路徑算法[1]、包探測法[2]、擴(kuò)展距離向量算法[3，4]、圖論刪減算法[5]、尋找優(yōu)化函數(shù)的離散點方法[6]等。對于用戶來說，不僅要求路徑能滿足度量參數(shù)，還希望路徑的代價最小，即向ISP支付的費用最小，一些文獻(xiàn)對此進(jìn)行了研究，但僅僅研究了延遲和代價兩個約束的情況，即研究的是RSP算法。Raz和Shavitt提出了一種算法，通過沿路徑分配延遲，使得路徑的代價最小，但在這里他們認(rèn)

為代價是延遲的函數(shù)；Lorenz等人研究了花費函數(shù)為連續(xù)凸函數(shù)時的分割方式[7]；Turgay Korkmaz和Marwan Krunz在文獻(xiàn)[8]中提出了多約束優(yōu)化路徑（MCOP）選擇算法H_MCOP， H_MCOP是通過一個花費函數(shù)合成多度量，然后在最短路徑算法的松弛過程中選擇代價最小的路徑。目前H_MCOP算法是在MCOP研究中被公認(rèn)為性能比較好的算法。

本文研究在多加性度量參數(shù)條件下，搜索出代價最小的路徑，在這里代價也可以是其他加性度量參數(shù)。當(dāng)前網(wǎng)絡(luò)應(yīng)用的QoS請求的內(nèi)容已經(jīng)不僅僅是延遲和帶寬，還包括延遲抖動、丟包率等，所以QoS路由應(yīng)該針對多約束的QoS請求。對于任何一個用戶或ISP來說，得到一條滿足QoS請求的QoS路徑能適應(yīng)其應(yīng)用的需求，如果找到的路徑不僅適應(yīng)應(yīng)用的需求，而且付出的代價最小，則能達(dá)到業(yè)務(wù)順利進(jìn)行、費用最小的兩個目的，這對用戶和ISP都極具意義。

定理1同時滿足兩個以上加性參數(shù)的QoS路由問題屬于NP完全問題[9]。

1問題提出和網(wǎng)絡(luò)模型

1．1問題提出

計算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)不斷發(fā)展，網(wǎng)絡(luò)的應(yīng)用得到普及，使得網(wǎng)絡(luò)規(guī)模更大，網(wǎng)絡(luò)更加復(fù)雜，同時用戶的需求越來越高，各種新的應(yīng)用，如多媒體等相繼出現(xiàn)。Internet已逐步由單一的數(shù)據(jù)傳輸網(wǎng)向多媒體綜合傳輸網(wǎng)演進(jìn)，但是目前Internet中的傳輸模式“盡力而為”（BestEfford）服務(wù)，無法滿足多媒體應(yīng)用和用戶對網(wǎng)絡(luò)傳輸質(zhì)量的種種要求。因此以保障用戶應(yīng)用請求服務(wù)質(zhì)量為目標(biāo)的QoS成為當(dāng)前研究的熱點，提供給用戶需求服務(wù)保證，尋求最小代價——多約束最小代價問題成為ISP關(guān)注的焦點。

定義1多約束優(yōu)化路徑（MultiConstrained Optimal Path，MCOP）。在網(wǎng)絡(luò)中G=（V，E），每條鏈路（i， j)∈E關(guān)聯(lián)m個加性權(quán)重wi(i， j)≥0（i=1，…，m）和一個花費參數(shù)c(i， j)。假設(shè)有m個約束Li（i=1，…，m），多約束優(yōu)化路徑就是要在源節(jié)點s和目的節(jié)點d之間找到路徑P，P要滿足多約束且花費最小。

其數(shù)學(xué)表達(dá)式為

1．2網(wǎng)絡(luò)模型

為了研究問題的方便，往往將網(wǎng)絡(luò)中的交換機(jī)、路由器、集線器等網(wǎng)絡(luò)設(shè)備抽象為節(jié)點，它們之間的鏈路抽象為邊，鏈路上的帶寬、延遲、隊列長度等參數(shù)抽象為邊上的權(quán)重，而用戶或供應(yīng)商所關(guān)心的費用抽象為花費函數(shù)。

2寬度優(yōu)先搜索算法

2．1前向搜索與后向搜索

許多算法，如H_MCOP，MMPR采用雙向搜索的方法，雙向搜索方案的優(yōu)點是可以減少某些情況下算法的復(fù)雜程度。有些問題單向需要復(fù)雜的算法，而采用雙向的方法可以簡單地解決。

前向搜索的目的是預(yù)先進(jìn)行信息搜集，通過一定的搜索算法，將每個節(jié)點的狀態(tài)信息收集并緩存；后向搜索則依據(jù)預(yù)先得到的節(jié)點狀態(tài)信息進(jìn)行啟發(fā)式路由選擇。

BFS中每個節(jié)點入隊一次，呈層次式搜索；改進(jìn)的BFS算法則在此基礎(chǔ)上加入了松弛算法，并且每個節(jié)點刷新所有的相鄰節(jié)點信息。

定理3在BFT中，從源節(jié)點s到任一節(jié)點v的路徑p，其權(quán)重大于等于最短路徑p′的權(quán)重，即w(p)≥w(p′)。

證明：因為在BFT中，從源節(jié)點s到任一節(jié)點v的路徑p不能保證是最短路徑，所以其權(quán)值小于最短路徑p′。

從源節(jié)點s開始，采用Dijkstra算法對網(wǎng)絡(luò)進(jìn)行搜索所生成的最短路徑樹為圖1(b)。對比最短路徑樹，在BFT中從s到某些節(jié)點的路徑并不是最短路徑。

從s到t的路徑，實際上其最短路徑的權(quán)值是14，這表明了前向搜索的不精確性。

以t為根生成后向搜索BFT，將BFTs與BFTt疊加，從s到t的路徑p的權(quán)值為14，即p=p′。后向搜索成功地找出了從s到t的最短路徑。

由于鏈路的有向性，前向搜索考慮出度的邊，而后向搜索考慮入度的邊。實際的鏈路是雙向的、權(quán)值相異的，這里為了說明前向和后向搜索，認(rèn)為其權(quán)值是相同的。

2．2綜合度量函數(shù)

綜合度量函數(shù)確定多個約束轉(zhuǎn)換為單一約束的方法，綜合度量函數(shù)定義的好壞，直接關(guān)系到算法的成功率。

在H_MCOP算法中提到，gλ(p)=(w1(p)c1)λ+(w2(p)c2)λ+…+(wK(p)cK)λ，并證明在λ從1趨近于正無窮的過程中，H_MCOP算法的成功率逐漸上升，當(dāng)λ=+∞時，算法有最好的性能。 

2．3松弛函數(shù)

松弛函數(shù)定義了在節(jié)點搜索過程中，刷新節(jié)點綜合度量及花費的方法。

Costmeasurement策略探索當(dāng)前節(jié)點通過與之相連的節(jié)點是否滿足路徑約束，如果滿足，則刷新那些還沒有找到可行路徑的節(jié)點和雖然已經(jīng)找到了可行路徑，但路徑的花費比當(dāng)前路徑花費大的節(jié)點；如果不滿足，則刷新那些沒有找到可行路徑，并且綜合度量比當(dāng)前路徑綜合度量大的那些路徑。

路由中環(huán)路的形成有多種原因，如路由信息陳舊、算法缺陷等。BFRA從算法角度消除了路由環(huán)路的形成。

定理4在BFRA中，松弛算法消除了路由環(huán)。

證明：用反證法。假定路由中存在環(huán)路p，則u∈p，e(v)=min[e(u)] ，v∈p。由松弛算法，用花費小的路徑信息刷新花費大的或者用綜合度量小的路徑信息刷新綜合度量大的節(jié)點，v不可能再次被刷新，因此不存在環(huán)路，與p矛盾。故命題得證。

2．4寬度優(yōu)先松弛算法（BFRA）

寬度優(yōu)先松弛算法的主要思想是首先前向搜索，采用FORWARD_BFS_RELAX（u，v）松弛算法，各節(jié)點獲得e(v)，w(v)，cost(v)等內(nèi)容并保存下來，以確保為后向搜索提供必要的信息；然后后向搜索，采用BACKWARD_BFS_RELAX（u，v）松弛算法，確定得到滿足約束的各條路徑，并且獲得花費最小的路徑。

BFRA算法的偽代碼如下：

定理5在BFRA算法中，如果前向搜索發(fā)現(xiàn)一條路徑p，滿足wk(p)

證明：如果前向搜索發(fā)現(xiàn)一條路徑p，那么p必然通過一個與目標(biāo)節(jié)點t相鄰的節(jié)點v。后向搜索算法首先搜索與t相鄰的節(jié)點，則必然可以發(fā)現(xiàn)從t到v是一條可行路徑。后向搜索算法刷新每個節(jié)點u的信息集合S時，都要判定是否有滿足約束的路徑存在和滿足約束的路徑是否有最小的cost。這樣前向搜索算法可能遺漏的路徑，就能夠被后向搜索算法所發(fā)現(xiàn)，最終找到cost最小的可行路徑p′。

定理5保證后向搜索至少能發(fā)現(xiàn)比前向搜索更優(yōu)的路徑。

2．5特殊情況分析

對于特殊情形，該算法找到次優(yōu)路徑，這樣給其他流的接入預(yù)留了空間。圖3（a）表示一種網(wǎng)絡(luò)拓?fù)?，其中，源?jié)點s到節(jié)點t的每條鏈路上的數(shù)字表示這條鏈路的度量，節(jié)點邊上的字母表示節(jié)點號，1<

2．6性能分析和復(fù)雜度分析

該算法時間復(fù)雜度為線性，優(yōu)于H_MCOP算法的時間復(fù)雜度。時間復(fù)雜度分析如下：

初始化隊列、綜合度量等需要O(V)時間，修改的BFS算法增加了松弛函數(shù)，但是沒有增加時間復(fù)雜度，標(biāo)準(zhǔn)的BFS的時間復(fù)雜度為O(V+E)，所以修改的BFS算法的時間復(fù)雜度仍然是O(V+E)。BFRA算法包括前向搜索和后向搜索，其時間復(fù)雜度為O(V)+2O(V+E)=O(V+E)。

可以看出，該算法的時間復(fù)雜度為線性，比當(dāng)前路由算法時間復(fù)雜度要低。

3仿真試驗

仿真實驗使用NS2中的GTITM生成基于Waxman模式的100個節(jié)點的拓?fù)鋱D和Transitstub模式200個節(jié)點的拓?fù)鋱D。wi(u，v)，i=1，2，…，K，均勻分布在[0，10]之間，鏈路花費函數(shù)cost均勻分布在[1，10]之間。橫軸表示滿足約束條件的平均路徑數(shù)，即拓?fù)渲写嬖跐M足約束的路徑平均個數(shù)，縱軸表示發(fā)現(xiàn)最優(yōu)路徑的成功率。

仿真實驗從平均路徑為1~1.5條開始，逐漸放大路徑約束各個分量，放大增量為0.01，放大次數(shù)為1 000次。每次循環(huán)執(zhí)行100次BFRA算法，計算平均路徑，發(fā)現(xiàn)路徑成功率和最優(yōu)路徑成功率。 

(1)不同拓?fù)湟?guī)模相同約束下成功率的比較（圖4）

相同約束下，從圖4中可以看出，60節(jié)點和100節(jié)點的拓?fù)浒l(fā)現(xiàn)最優(yōu)路徑的成功率很高，而200節(jié)點拓?fù)涞某晒β氏鄬^低。這是因為60節(jié)點和100節(jié)點拓?fù)涞念愋褪荳axman，其節(jié)點的平均度數(shù)比較大，網(wǎng)絡(luò)直徑較??；而200節(jié)點的拓?fù)漕愋褪荰ransitstub，節(jié)點度數(shù)很小，網(wǎng)絡(luò)直徑較大。

(2)相同拓?fù)洳煌s束數(shù)目的比較

BFRA算法采用綜合度量的方式，將多約束化為一個度量，因此，在相同拓?fù)湎?，不同約束數(shù)目的成功率差異不是很大，如圖5所示。從試驗中可以看出，BFRA算法對約束的數(shù)目并不敏感。

拓?fù)涞念愋秃凸?jié)點的度數(shù)是影響B(tài)FRA算法的主要因素，而約束的數(shù)目和拓?fù)涞囊?guī)模對BFRA算法的影響很小，因此BFRA算法具有很好的可擴(kuò)展性。

(3)與H_MCOP算法的比較

Turgay Korkmaz 和Marwan Krunz提出的H_MCOP是當(dāng)前比較好的多約束最小代價算法，算法時間復(fù)雜度為O(V logV+E)，而搜索到最優(yōu)路徑的成功率比較高。為提高H_MCOP算法搜索優(yōu)化路徑的成功率，選取λ＝10。圖6是在Transitstub模式200個節(jié)點的拓?fù)湎聝煞N算法成功率的比較。

BFRA相比較H_MCOP的平均成功率有很大的優(yōu)勢。表1比較了兩者的最高、最低和平均成功率。其中，B代表了BFRA算法，H代表H_MCOP算法。

表1BFRA與H_MCOP性能比較

圖7是在Waxman模式100個節(jié)點的拓?fù)湎聝煞N算法成功率的比較。

圖7表明，在Waxman模式下，BFRA算法的成功率遠(yuǎn)遠(yuǎn)高于H_MCOP算法的成功率。

(4)與有限路徑啟發(fā)式算法的比較（圖8）

有限路徑啟發(fā)式算法是由Yuan等人提出的一種基于EBFA的算法，它在每個中間節(jié)點保存一個路徑緩沖區(qū)，記錄通過該節(jié)點的路徑。該算法是一種多約束QoS路由算法，它發(fā)現(xiàn)路徑的成功率受到節(jié)點保存路徑數(shù)目的影響。如果節(jié)點保存的路徑數(shù)目越多，發(fā)現(xiàn)可行路徑的可能性就越大，但是同時算法復(fù)雜度呈指數(shù)增加。筆者使用該算法與本文提出的BFRA算法進(jìn)行比較，選取節(jié)點保存的路徑數(shù)目為八條。

試驗結(jié)果表明，當(dāng)可行路徑數(shù)目較小時，BFRA搜索優(yōu)化路徑的成功率較EBFA有明顯優(yōu)勢。

4結(jié)論

在解決QoS問題的算法中，H_MCOP是目前較好的一種，然而它也存在著一些問題，本文提出的BFRA算法，解決了這些問題，從而提升了算法的性能。相對于H_MCOP算法而言，BFRA算法在時間復(fù)雜度和最優(yōu)路徑成功率上有著更好的表現(xiàn)。同時與EBFA算法進(jìn)行比較，可行路徑數(shù)目較少時，BFRA算法的性能明顯高于EBFA算法。然而，BFRA算法在分布式路由計算中還有待于進(jìn)一步研究。

參考文獻(xiàn)：

［1］R Guerin， A Orda. Networks with Advance Reservations： The Routing Perspective[C]. Israel： INFOCOM， 2000. 118127.

［2］Cidon R Rom， Y Shavitt. MultiPath Routing Combined with Resource Reservation[C]. Kobe， Japan： INFOCOM， 1997.92100.

［3］X Yuan. On the Extended BellmanFord Algorithm to Solve TwoConstrained Quality of Service Routing Problems[C]. Boston， Massachusetts： Proceedings of the 8th International Conference on Computer Communications and Networks，1999.304310.

［4］X Yuan， X Liu. Heuristic Algorithms for MultiConstrained Quality of Service Routing[C]. Anchorage， Alaska： INFOCOM， 1997.844853.

［5］Claudio Casetti， Renato Lo Cigno. A New Class of QoS Routing Strate￣gies Based on Network Graph Reduction[J]. Computer Networks，2003，41(4):475487.

［6］S Siachalou， L Georgiadis. Efficient QoS Routing[C]. San Francisco， MA： INFOCOM， 2003. 938947.

［7］H Lorenz， Ariel Orda. Optimal Partition of QoS Requirements on Unicast Paths and Multicast Trees[C]. New York， NY， USA： INFOCOM， 1999.246253.

［8］T Korkmaz， M Krunz. MultiConstrained Optimal Path Selection[C]. Anchorage， Alaska， USA： INFOCOM， 2001. 834843.

［9］M S Garey， D S Johnson. Computers and Intractability： A Guide to the Theory of NPCompleteness[M]. New York： W.H. Freeman Co.， 1979.1738.

作者簡介：

錢進(jìn)(1974)，男，湖北荊門人，博士，主要研究方向為網(wǎng)絡(luò)管理；陳立家(1979)，男，河南開封人，博士，主要研究方向為高速信息網(wǎng)絡(luò);賀貴明(1962)，男，教授，博導(dǎo)，主要研究方向為計算機(jī)網(wǎng)絡(luò)。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文