一種多約束最優路徑寬度優先松弛算法
2007-01-01 00:00:00錢進陳立家賀貴明
計算機應用研究 2007年1期
摘要：在分析單播QoS路由問題的基礎上，提出了寬度優先松弛算法BFRA，其核心思想是基于改進的寬度優先搜索策略，采用特殊的松弛算法分別前向（從源節點）和后向（從目標節點）搜索網絡拓撲。前向搜索預先計算路徑的綜合度量、約束等參數，收集路徑信息;后向搜索則采用Costmeasurement策略對路徑進行選擇和篩選，不斷搜索到新的可行路徑，并選取最優路徑。討論了在路徑振蕩時BFRA選取次優路徑，為其他QoS流的接入預留了資源。理論分析表明BFRA保存的狀態信息較少，時間復雜度為線性，仿真結果表明，BFRA發現最優路徑的成功率較高。
關鍵詞：多約束； 花費； 前向搜索； 后向搜索； 松弛； 路徑振蕩
中圖法分類號：TP301．6文獻標識碼：A
文章編號：1001－3695(2007)01－0090-04
當前的研究主要集中在搜索出滿足多個約束的單播QoS路徑上。QoS路由算法主要有最短最寬路徑算法[1]、包探測法[2]、擴展距離向量算法[3，4]、圖論刪減算法[5]、尋找優化函數的離散點方法[6]等。對于用戶來說，不僅要求路徑能滿足度量參數，還希望路徑的代價最小，即向ISP支付的費用最小，一些文獻對此進行了研究，但僅僅研究了延遲和代價兩個約束的情況，即研究的是RSP算法。Raz和Shavitt提出了一種算法，通過沿路徑分配延遲，使得路徑的代價最小，但在這里他們認
為代價是延遲的函數；Lorenz等人研究了花費函數為連續凸函數時的分割方式[7]；Turgay Korkmaz和Marwan Krunz在文獻[8]中提出了多約束優化路徑（MCOP）選擇算法H_MCOP， H_MCOP是通過一個花費函數合成多度量，然后在最短路徑算法的松弛過程中選擇代價最小的路徑。目前H_MCOP算法是在MCOP研究中被公認為性能比較好的算法。
本文研究在多加性度量參數條件下，搜索出代價最小的路徑，在這里代價也可以是其他加性度量參數。當前網絡應用的QoS請求的內容已經不僅僅是延遲和帶寬，還包括延遲抖動、丟包率等，所以QoS路由應該針對多約束的QoS請求。對于任何一個用戶或ISP來說，得到一條滿足QoS請求的QoS路徑能適應其應用的需求，如果找到的路徑不僅適應應用的需求，而且付出的代價最小，則能達到業務順利進行、費用最小的兩個目的，這對用戶和ISP都極具意義。
定理1同時滿足兩個以上加性參數的QoS路由問題屬于NP完全問題[9]。
1問題提出和網絡模型
1．1問題提出
計算機技術和網絡技術不斷發展，網絡的應用得到普及，使得網絡規模更大，網絡更加復雜，同時用戶的需求越來越高，各種新的應用，如多媒體等相繼出現。Internet已逐步由單一的數據傳輸網向多媒體綜合傳輸網演進，但是目前Internet中的傳輸模式“盡力而為”（BestEfford）服務，無法滿足多媒體應用和用戶對網絡傳輸質量的種種要求。因此以保障用戶應用請求服務質量為目標的QoS成為當前研究的熱點，提供給用戶需求服務保證，尋求最小代價——多約束最小代價問題成為ISP關注的焦點。
定義1多約束優化路徑（MultiConstrained Optimal Path，MCOP）。在網絡中G=（V，E），每條鏈路（i， j)∈E關聯m個加性權重wi(i， j)≥0（i=1，…，m）和一個花費參數c(i， j)。假設有m個約束Li（i=1，…，m），多約束優化路徑就是要在源節點s和目的節點d之間找到路徑P，P要滿足多約束且花費最小。
其數學表達式為
1．2網絡模型
為了研究問題的方便，往往將網絡中的交換機、路由器、集線器等網絡設備抽象為節點，它們之間的鏈路抽象為邊，鏈路上的帶寬、延遲、隊列長度等參數抽象為邊上的權重，而用戶或供應商所關心的費用抽象為花費函數。
2寬度優先搜索算法
2．1前向搜索與后向搜索
許多算法，如H_MCOP，MMPR采用雙向搜索的方法，雙向搜索方案的優點是可以減少某些情況下算法的復雜程度。有些問題單向需要復雜的算法，而采用雙向的方法可以簡單地解決。
前向搜索的目的是預先進行信息搜集，通過一定的搜索算法，將每個節點的狀態信息收集并緩存；后向搜索則依據預先得到的節點狀態信息進行啟發式路由選擇。
BFS中每個節點入隊一次，呈層次式搜索；改進的BFS算法則在此基礎上加入了松弛算法，并且每個節點刷新所有的相鄰節點信息。
定理3在BFT中，從源節點s到任一節點v的路徑p，其權重大于等于最短路徑p′的權重，即w(p)≥w(p′)。
證明：因為在BFT中，從源節點s到任一節點v的路徑p不能保證是最短路徑，所以其權值小于最短路徑p′。
從源節點s開始，采用Dijkstra算法對網絡進行搜索所生成的最短路徑樹為圖1(b)。對比最短路徑樹，在BFT中從s到某些節點的路徑并不是最短路徑。
從s到t的路徑，實際上其最短路徑的權值是14，這表明了前向搜索的不精確性。
以t為根生成后向搜索BFT，將BFTs與BFTt疊加，從s到t的路徑p的權值為14，即p=p′。后向搜索成功地找出了從s到t的最短路徑。
由于鏈路的有向性，前向搜索考慮出度的邊，而后向搜索考慮入度的邊。實際的鏈路是雙向的、權值相異的，這里為了說明前向和后向搜索，認為其權值是相同的。
2．2綜合度量函數
綜合度量函數確定多個約束轉換為單一約束的方法，綜合度量函數定義的好壞，直接關系到算法的成功率。
在H_MCOP算法中提到，gλ(p)=(w1(p)c1)λ+(w2(p)c2)λ+…+(wK(p)cK)λ，并證明在λ從1趨近于正無窮的過程中，H_MCOP算法的成功率逐漸上升，當λ=+∞時，算法有最好的性能。
2．3松弛函數
松弛函數定義了在節點搜索過程中，刷新節點綜合度量及花費的方法。
Costmeasurement策略探索當前節點通過與之相連的節點是否滿足路徑約束，如果滿足，則刷新那些還沒有找到可行路徑的節點和雖然已經找到了可行路徑，但路徑的花費比當前路徑花費大的節點；如果不滿足，則刷新那些沒有找到可行路徑，并且綜合度量比當前路徑綜合度量大的那些路徑。
路由中環路的形成有多種原因，如路由信息陳舊、算法缺陷等。BFRA從算法角度消除了路由環路的形成。
定理4在BFRA中，松弛算法消除了路由環。
證明：用反證法。假定路由中存在環路p，則u∈p，e(v)=min[e(u)] ，v∈p。由松弛算法，用花費小的路徑信息刷新花費大的或者用綜合度量小的路徑信息刷新綜合度量大的節點，v不可能再次被刷新，因此不存在環路，與p矛盾。故命題得證。
2．4寬度優先松弛算法（BFRA）
寬度優先松弛算法的主要思想是首先前向搜索，采用FORWARD_BFS_RELAX（u，v）松弛算法，各節點獲得e(v)，w(v)，cost(v)等內容并保存下來，以確保為后向搜索提供必要的信息；然后后向搜索，采用BACKWARD_BFS_RELAX（u，v）松弛算法，確定得到滿足約束的各條路徑，并且獲得花費最小的路徑。
BFRA算法的偽代碼如下：
定理5在BFRA算法中，如果前向搜索發現一條路徑p，滿足wk(p) 證明：如果前向搜索發現一條路徑p，那么p必然通過一個與目標節點t相鄰的節點v。后向搜索算法首先搜索與t相鄰的節點，則必然可以發現從t到v是一條可行路徑。后向搜索算法刷新每個節點u的信息集合S時，都要判定是否有滿足約束的路徑存在和滿足約束的路徑是否有最小的cost。這樣前向搜索算法可能遺漏的路徑，就能夠被后向搜索算法所發現，最終找到cost最小的可行路徑p′。 定理5保證后向搜索至少能發現比前向搜索更優的路徑。 2．5特殊情況分析 對于特殊情形，該算法找到次優路徑，這樣給其他流的接入預留了空間。圖3（a）表示一種網絡拓撲，其中，源節點s到節點t的每條鏈路上的數字表示這條鏈路的度量，節點邊上的字母表示節點號，1< 2．6性能分析和復雜度分析 該算法時間復雜度為線性，優于H_MCOP算法的時間復雜度。時間復雜度分析如下： 初始化隊列、綜合度量等需要O(V)時間，修改的BFS算法增加了松弛函數，但是沒有增加時間復雜度，標準的BFS的時間復雜度為O(V+E)，所以修改的BFS算法的時間復雜度仍然是O(V+E)。BFRA算法包括前向搜索和后向搜索，其時間復雜度為O(V)+2O(V+E)=O(V+E)。 可以看出，該算法的時間復雜度為線性，比當前路由算法時間復雜度要低。 3仿真試驗 仿真實驗使用NS2中的GTITM生成基于Waxman模式的100個節點的拓撲圖和Transitstub模式200個節點的拓撲圖。wi(u，v)，i=1，2，…，K，均勻分布在[0，10]之間，鏈路花費函數cost均勻分布在[1，10]之間。橫軸表示滿足約束條件的平均路徑數，即拓撲中存在滿足約束的路徑平均個數，縱軸表示發現最優路徑的成功率。 仿真實驗從平均路徑為1~1.5條開始，逐漸放大路徑約束各個分量，放大增量為0.01，放大次數為1 000次。每次循環執行100次BFRA算法，計算平均路徑，發現路徑成功率和最優路徑成功率。 (1)不同拓撲規模相同約束下成功率的比較（圖4） 相同約束下，從圖4中可以看出，60節點和100節點的拓撲發現最優路徑的成功率很高，而200節點拓撲的成功率相對較低。這是因為60節點和100節點拓撲的類型是Waxman，其節點的平均度數比較大，網絡直徑較小；而200節點的拓撲類型是Transitstub，節點度數很小，網絡直徑較大。 (2)相同拓撲不同約束數目的比較 BFRA算法采用綜合度量的方式，將多約束化為一個度量，因此，在相同拓撲下，不同約束數目的成功率差異不是很大，如圖5所示。從試驗中可以看出，BFRA算法對約束的數目并不敏感。 拓撲的類型和節點的度數是影響BFRA算法的主要因素，而約束的數目和拓撲的規模對BFRA算法的影響很小，因此BFRA算法具有很好的可擴展性。 (3)與H_MCOP算法的比較 Turgay Korkmaz 和Marwan Krunz提出的H_MCOP是當前比較好的多約束最小代價算法，算法時間復雜度為O(V logV+E)，而搜索到最優路徑的成功率比較高。為提高H_MCOP算法搜索優化路徑的成功率，選取λ＝10。圖6是在Transitstub模式200個節點的拓撲下兩種算法成功率的比較。 BFRA相比較H_MCOP的平均成功率有很大的優勢。表1比較了兩者的最高、最低和平均成功率。其中，B代表了BFRA算法，H代表H_MCOP算法。 表1BFRA與H_MCOP性能比較 圖7是在Waxman模式100個節點的拓撲下兩種算法成功率的比較。 圖7表明，在Waxman模式下，BFRA算法的成功率遠遠高于H_MCOP算法的成功率。 (4)與有限路徑啟發式算法的比較（圖8） 有限路徑啟發式算法是由Yuan等人提出的一種基于EBFA的算法，它在每個中間節點保存一個路徑緩沖區，記錄通過該節點的路徑。該算法是一種多約束QoS路由算法，它發現路徑的成功率受到節點保存路徑數目的影響。如果節點保存的路徑數目越多，發現可行路徑的可能性就越大，但是同時算法復雜度呈指數增加。筆者使用該算法與本文提出的BFRA算法進行比較，選取節點保存的路徑數目為八條。 試驗結果表明，當可行路徑數目較小時，BFRA搜索優化路徑的成功率較EBFA有明顯優勢。 4結論 在解決QoS問題的算法中，H_MCOP是目前較好的一種，然而它也存在著一些問題，本文提出的BFRA算法，解決了這些問題，從而提升了算法的性能。相對于H_MCOP算法而言，BFRA算法在時間復雜度和最優路徑成功率上有著更好的表現。同時與EBFA算法進行比較，可行路徑數目較少時，BFRA算法的性能明顯高于EBFA算法。然而，BFRA算法在分布式路由計算中還有待于進一步研究。 參考文獻： ［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. 作者簡介： 錢進(1974)，男，湖北荊門人，博士，主要研究方向為網絡管理；陳立家(1979)，男，河南開封人，博士，主要研究方向為高速信息網絡;賀貴明(1962)，男，教授，博導，主要研究方向為計算機網絡。 注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
