一個效率可觀的啟發(fā)式多約束ＱｏＳ路由算法

摘要:提出的MWA_MCP(maximal weight amputation for multi－constrained problem)算法，充分利用了BFS(bread first search)算法計算復雜度簡單的特點，使用BFS搜索QoS路徑。MWA_MCP在搜索過程中有選擇地去掉QoS性能差的邊，即權(quán)重較大的邊將在搜索中有策略地被去掉。與仿真的幾個算法相比，MWA_MCP體現(xiàn)了較高的路由性能。

關(guān)鍵詞:服務質(zhì)量; 服務質(zhì)量路由; 多約束服務質(zhì)量路由

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001－3695(2008)02－0345－03

0引言

對于多約束QoS路由問題，只要找到一條路徑滿足各QoS約束條件，即路由成功。當加性約束或者乘性約束多于一個時，多約束QoS路由問題是NPC(NP complete)的[1]。NPC問題的解決，只有將解域中所有可能值都窮舉了之后才能得出答案。但是這樣窮舉之后，算法的復雜程度是指數(shù)關(guān)系。因此計算的時間隨問題的復雜程度呈指數(shù)增長，很快就變得不可計算了。

在已有文獻中提出的多約束QoS算法，大多使用了Dijkstra或Bellman－Ford算法，它們的計算復雜度都是不小于O(n2)的。文獻[2，3]提出的SMM－LS(single mixed metric based on link－states)算法，用一個單一混合參數(shù)來綜合表示各參數(shù)并求解，其計算復雜程度為O(n2)。其中n為圖中的節(jié)點數(shù)。文獻[4]提出的CP－H/RDS(constraint path heuristic/routing decision system)由兩個步驟組成:第一步先由CP－H[4]算法提供k×l條路徑(其中:k為加性參數(shù)的個數(shù);l為一用戶定義數(shù))，該步驟的計算復雜度為O(k×l×n2);第二步由RDS[5]從以上各路徑中選擇一條路徑。文獻[6]給出的擴展DFS(extended depth first search)方法，其復雜程度為O(r2×mn+n2)。其中:m為邊數(shù);r為從源點到終點可能的路徑數(shù)。可以看出，QoS問題的求解還是非常復雜的。

在已有的多約束QoS路由的啟發(fā)式算法中，也有用到BFS的。不過，它們大多將BFS當做一個輔助步驟。文獻[7]提出了BFS_MCP(BFS for multi－constrained paths)算法。它將BFS應用于Dijkstra算法進行深度為H的調(diào)整，即對深度為H的子節(jié)點進行處理。H值根據(jù)CPU負荷量可進行調(diào)整。BFS_MCP的計算復雜程度為O(km(2m/n)H+kn log n)。其中:k是約束數(shù);m為邊數(shù); H為一個可調(diào)的正整數(shù)。鑒于隨著H的增大，計算時間會增加，建議H取0~2的一個數(shù)。文獻[8]提出了隨機化算法，該算法包括初始化和隨機化搜索兩個階段。在第二階段，采用隨機化的BFS算法。該BFS過程選擇可能到達目的節(jié)點的下一跳進行搜索。該算法的計算復雜程度為O(n3)。

純粹的BFS算法不能解決多約束QoS問題。因為BFS在搜索時只能考慮單個指標，在多約束的QoS問題面前，單獨的BFS算法就捉襟見肘了。已有的算法大多將BFS與其他算法進行了結(jié)合，比如文獻[9]提出的K_DCP算法解決的是延遲受限#65380;成本最小的問題。該算法用Dijkstra計算所有節(jié)點到目的節(jié)點的最短路徑延遲和最小路徑費用;用改進的BFS在已得到的多個節(jié)點中，選擇當前節(jié)點到目的節(jié)點費用最小的下一個節(jié)點進行搜索。該算法的復雜度為O(n log n+m+r(n+m))。其中:r代表找到的滿足條件的路徑數(shù)目。

QoS各項指標是隨機的，保證了一個指標最優(yōu)，別的指標就不能保證最優(yōu)。在負載高時，非最短路由將比最短路由表現(xiàn)出較劣的性能[10]。很明顯，非最短路由將占用額外的資源，該額外的占用將對路由的性能產(chǎn)生影響。

1問題及相關(guān)知識

2MWA_MCP

多約束QoS路由就是要找到一條從源點到終點滿足各QoS約束的路徑。只要算法找到一條從源點到終點滿足各約束條件的路徑，則算法即尋路成功。在解決MCP時，本文將有策略地去掉鏈路QoS狀態(tài)較高的邊，該算法即MWA_MCP。它有前向搜索和后向搜索兩個步驟。MWA_MCP先進行前向BFS搜索，即從源點到終點的forward BFS(FBFS);如果該搜索失敗，則進行與FBFS類似的后向BFS，即從終點到源點的backward BFS(BBFS)。

由于BFS的簡單性，可以多次進行BFS。為了下輪搜索時盡量不重復上輪的搜索，避免重復上輪失敗的路徑，在每次搜索時將會保存一些QoS狀態(tài)較差的鏈路相關(guān)的權(quán)值。當搜索失敗，將去掉失敗路徑上的這些特殊邊。這樣，下輪搜索就將會得到不同的路徑。

參考用的鏈路狀態(tài)值可以為任意影響路由及網(wǎng)絡性能的參數(shù)值。除了延遲#65380;傳輸成功率#65380;連通度外，還可以為代表鏈路擁擠情況的帶寬#65380;其他任意的網(wǎng)絡狀態(tài)參數(shù)。

行1~29為FBFS的偽代碼。行1控制BFS次數(shù)，加性參數(shù)和乘性參數(shù)(已轉(zhuǎn)換成加性參數(shù))個數(shù)為k，times為自定義變量;行2~4對原圖進行備份;行5去掉不滿足帶寬約束的邊;行6和7進行初始化，源點用ss表示，終點用dd表示，S1為已處理的節(jié)點集合，S2是需要處理的節(jié)點集合，S3是未處理的節(jié)點集合，route[ss]表示節(jié)點ss的上一節(jié)點，maxvalue儲存的是最大的權(quán)重值，maxedge儲存相應的邊;行8~27對各當前節(jié)點進行處理;行10~26是對當前節(jié)點的子節(jié)點進行處理(當前節(jié)點用u表示;其子節(jié)點用v表示;wj(u)表示在路徑上第j個約束從ss到當前節(jié)點的和，wj(u，v)則表示邊(u，v)上第j個約束的值，1≤j≤k);行17~19更新從ss到v的路徑上各約束的最大值;行20~22更新從源點ss到節(jié)點v的路徑上出度最大的節(jié)點值;行23~25進行截邊處理。當1≤i≤k×times時，去掉的邊為該路徑上第[i/times]個約束值最大的邊;當k×times+1≤i≤(k+1)×times時，去掉的是該路徑上出度最大的節(jié)點所在的邊。[i/times]代表大于i/times的最小整數(shù)。行23給出的截邊條件是尋路到終點但路徑不滿足QoS約束。如果該路徑搜索到半路終止，即u的所有子節(jié)點都不滿足行11的條件，也進行去邊處理。

在獲得maxedgej時(即行17~22)，如果maxedgej為空，則還應增加條件do(u)>1;如果子節(jié)點v為終點dd，還應增加條件di(dd)>1。比如在圖1中，如果源點是節(jié)點0，終點是節(jié)點11，則邊(0，2)不會去掉，因為do(0)為1;并且邊(6，11)也不會被去掉，因為di(6)為1。

BBFS與FBFS的不同之處在于其搜索的方向是從終點到源點。在BBFS中，行6初始化的是dd。由于本文考慮的是有向圖，則FBFS中的權(quán)值wj(u，v)在BBFS中應該是wj(v，u)。行20的比較值在算法BBFS中應該是v的入度，即di(v)。相應地，在23行應該是ss。

下面以一個例子來說明。假設進行帶寬截取后得到圖2所示的9節(jié)點結(jié)構(gòu)，并且源點是0，終點是3，則最多再進行兩次搜索，將搜遍源點到終點的所有可能路徑?？紤]算法進行FBFS的第一次搜索。第一步，從源點0出發(fā)，有兩條路(0，1)，(0，8)。第二步，假設路徑(0，1，3)上的延遲不滿足QoS，即w1(3)=w1(1)+w1(1，3)大于QoS延遲約束，則節(jié)點1會考慮節(jié)點2。所以第二步得到的三條路徑搜索的結(jié)果為(0，1，2)#65380;(0，8，6)和(0，8，7)。第三步，假設路徑(0，1，2，3)不滿足QoS約束，則該條路搜索停止。其余兩條路徑搜索時，由于都到節(jié)點5，只會有一條路徑。該步搜索的結(jié)果得到的路徑可能為(0，8，6，5)。第四步，假設搜索停止，即第二條路徑在節(jié)點5處搜索不到滿足QoS約束的下跳節(jié)點，算法將轉(zhuǎn)入第二次搜索。在下輪搜索前，會進行截邊處理。假設截取的兩條邊是(1，2)和(8，6)，則下輪搜索時，將搜索上輪沒有搜索到的路徑(0，8，7，5，4，3)。

3仿真

為了體現(xiàn)代表性，本文仿真選擇了三個參數(shù)，分別是瓶頸參數(shù)類的帶寬#65380;加性參數(shù)類的傳輸延遲#65380;乘性參數(shù)類的傳輸成功率。對于傳輸成功率的處理辦法，本文參考第1章討論的辦法進行處理。帶寬約束在[0，1]均勻分布，傳輸成功率約束在[0.2，0.8]服從均勻分布，延遲約束服從均值為250的指數(shù)分布。鏈路的最大帶寬是1，即滿負荷下的帶寬值為1;鏈路某個時刻的使用帶寬即為一定時間內(nèi)該鏈路實際通過的信息包數(shù)與滿負荷時能通過的信息包數(shù)的比值。各鏈路的傳輸成功率服從[0，0.18]的均勻分布;鏈路上的延遲服從均值為20的指數(shù)分布。仿真時間是15 min。在仿真時間內(nèi)，當一個信息包從源點全部到達終點后，該信息包所占用路徑上的鏈路資源又可分配給其他信息包了。

仿真是在兩種拓撲下進行的。第一種拓撲是圖3的8×8 torus結(jié)構(gòu)。在該規(guī)則網(wǎng)絡結(jié)構(gòu)中，任何節(jié)點都與四個其他節(jié)點連接。第二種拓撲是圖1的11節(jié)點結(jié)構(gòu)。

本文對五種算法進行了仿真:MWA_MCP(MWA)#65380;SMM－LS[2](SMM)#65380;CP－H/RDS[4](CPR)#65380;BFS_MCP[7]#65380;MIN HOP[8]。在仿真時，CPR在CP－H步驟時搜索的路徑數(shù)是六條;BFS_MCP中的H值取為1;MWA_MCP的循環(huán)次數(shù)times取值為2。圖4是在11節(jié)點結(jié)構(gòu)內(nèi)的仿真結(jié)果;圖5是在8×8 torus結(jié)構(gòu)內(nèi)的仿真結(jié)果。為了方便性能比較，在網(wǎng)絡中每個節(jié)點所發(fā)的包皆為QoS包。這樣，當運行不同算法時，網(wǎng)絡中的流量就能體現(xiàn)各算法的性能。

從圖4可以看出，五種算法中，MWA_MCP性能最好，接下來依次是CPR#65380;SMM－LS#65380;MIN HOP和BFS_MCP。CPR表現(xiàn)突出，是因為它使用Dijkstra找到六條最優(yōu)路徑，然后從中選擇。由于CPR是使用RDSS[5]選擇一個路徑，在仿真時增加了驗證步驟，以保證選擇的路徑滿足QoS各約束。

從圖5可以看出，在仿真所在的環(huán)境下，明顯地，MWA_MCP性能最好，其次是CPR和SMM－LS，最后分別是MIN HOP和BFS_MCP。

在本文的仿真環(huán)境下由仿真結(jié)果可以看出，MWA_MCP性能明顯比另外兩個使用BFS算法的性能高。

4結(jié)束語

本文提出的MWA_MCP算法具有簡單#65380;易擴展的特點。在本文程序偽代碼中，給出的去邊條件是各QoS約束的最大值和連通度的最大值。實際情況中，不同的截邊條件可以獲得不同的性能。截邊條件除了筆者用到的各約束的最大值和連通度，還可以為最窄帶寬#65380;最大花費等;并且，根據(jù)實際情況(如網(wǎng)絡復雜程度)，改變times以增加或減小BFS搜索次數(shù)，也可能對算法性能產(chǎn)生影響。從本文的仿真結(jié)果還可以看出，在解決多約束QoS問題時，MWA_MCP比其他四種算法性能都好。

參考文獻:

[1]WANG Zheng， CROWCROFT J. Quality－of－service routing for supporting multimedia applications[J]. IEEE Journal on Selected Areas in Communications， 1996，14(7):1228－1234.

[2]COSTA L， FDIDA S， DUARTE O. Developing scalable protocols for three－metric QoS routing[J]. Computer Networks， 2002，39(6):713－727.

[3]COSTA L， FDIDA S， DUARTE O. A scalable algorithm for link－state QoS－based routing with three metrics[C]//Proc of IEEE ICC. 2001:2603－2607.

[4]GOODRIDGE W， ROBERTSON W， PHILLIPS W J， et al. Heuristic constraint－path routing decision system[C]//Proc of the 3rd Annual Communication Networks and Services Research Conference(CNSR’05). 2005.

[5]GOODRIDGE W， ROBERTSON W， PHILLIPS W J， et al. Traffic driven multiple constraint optimization for QoS routing[J].Internatio－nal Journal of Internet Protocol Technology， 2005，1(1):19－29.

[6]LI Zhen－jiang， GARCIA－LUNA－ACEVES J J. Solving the multi－constrained path selection problem by using depth first search[C]//Proc of the 2nd Int’l Conf on Quality of Service in Heterogeneous Wired/Wireless Networks(QShine’05). 2005.

[7]CUI Yong， XU Ke， WU Jian－ping. Adjustable multi－constrained routing with a novel evaluation method[C]//Proc of IPCCC’03.Phoenix:[s.n.]， 2003:141－148.

[8]KORKMAZ T，KRUNZ M.A randomized algorithmfor finding a path subject to multiple QoS requirements[J]. Compu－ter Networks， 2001，36(2/3):251－268.

[9]余健，陳琳，楊志云，等.一個有效的延遲費用受限的多路徑算法[J].計算機應用研究，2004，21(7):222－224.

[10]CASETTI C， CIGNO R L， MELLIA M， et al. A new class of QoS routing strategies based on network graph reduction[J]. Computer Networks， 2003，41(4):475－487.

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