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

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

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

中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)志碼:A

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

0引言

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

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

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

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

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

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

2MWA_MCP

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

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

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

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

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

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

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

3仿真

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

仿真是在兩種拓?fù)湎逻M(jìn)行的。第一種拓?fù)涫菆D3的8×8 torus結(jié)構(gòu)。在該規(guī)則網(wǎng)絡(luò)結(jié)構(gòu)中，任何節(jié)點(diǎn)都與四個(gè)其他節(jié)點(diǎn)連接。第二種拓?fù)涫菆D1的11節(jié)點(diǎn)結(jié)構(gòu)。

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

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

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

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn):

[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]余健，陳琳，楊志云，等.一個(gè)有效的延遲費(fèi)用受限的多路徑算法[J].計(jì)算機(jī)應(yīng)用研究，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)容請(qǐng)以PDF格式閱讀原文”