一種多協(xié)議標簽交換流量工程的k條最短路徑的動態(tài)路由算法

一種多協(xié)議標簽交換流量工程的k條最短路徑的動態(tài)路由算法

1動態(tài)路由優(yōu)化算法多協(xié)議身份驗證（pms）是下一代網(wǎng)絡(luò)技術(shù)的先進技術(shù)之一?；趍pl的商業(yè)設(shè)計主要基于mpl的面向連接和顯式路徑的特點，將網(wǎng)絡(luò)流量基于適當?shù)牧６确植嫉较鄳?yīng)的標記交換路徑（lps）。根據(jù)資源優(yōu)化原則，維護所有l(wèi)ps物理路徑，能夠很好地控制網(wǎng)絡(luò)中的流量分布，顯著提高網(wǎng)絡(luò)交換速度，減少網(wǎng)絡(luò)復(fù)雜性，并提供有效的qos（quiu出口商）的保證。約束路由技術(shù)是流量工程的核心技術(shù),研究者提出了許多動態(tài)路由算法,包括最短路徑算法(CSPF)和最小干擾路由算法(MIRA)等,但都不能有效的解決鏈路使用不均衡問題.因此,本文提出了一種新的K路徑標號算法(KPathLabelAlgorithm,簡稱KPLA).該算法首先利用擴展標號算法計算出K條最短路徑,進一步考慮鏈路關(guān)鍵度和鏈路最大剩余帶寬的影響,并結(jié)合預(yù)計算和在線計算減少計算復(fù)雜度.模擬結(jié)果表明,算法的性能與CSPF和MIRA等相比有較大提高.2最小干擾路由算法目前MPLS-TE的實現(xiàn)多使用最短路徑算法(CSPF)選擇路徑.其核心思想是通過選擇源到目的的最短路徑,達到節(jié)省網(wǎng)絡(luò)資源的目的.CSPF計算復(fù)雜度低,容易實現(xiàn)和部署,同時也是很多啟發(fā)式路由算法的基礎(chǔ).但是CSPF未從全網(wǎng)的范圍內(nèi)考慮網(wǎng)絡(luò)流量分配和性能優(yōu)化,容易導(dǎo)致部分鏈路被過度使用而引起網(wǎng)絡(luò)擁塞.Kodialam等首次利用了MPLS網(wǎng)絡(luò)入出口節(jié)點對已知的性質(zhì),指出在這些入出口對之間存在著互相競爭使用網(wǎng)絡(luò)鏈路的關(guān)系,并把這種現(xiàn)象命名為干擾現(xiàn)象.他們首次提出了最小干擾路由算法(MIRA),試圖在尋路時使得各個入出口對之間的干擾最小,從而實現(xiàn)網(wǎng)絡(luò)資源的優(yōu)化利用.MIRA的關(guān)鍵思想是:在為當前請求選擇LSP時,考慮將來可能存在的請求對鏈路的需求,該請求的LSP必須盡可能地避免干擾其他SD節(jié)點對滿足將來需求的路由的建立.MIRA在性能上取得了顯著的提高,是本領(lǐng)域中比較著名的研究工作.但是MIRA也存在一些缺點:一是某些被MIRA認為是非關(guān)鍵的鏈路有些情況下是非常重要的;二是MIRA有可能選擇過長的路徑,不利于節(jié)省網(wǎng)絡(luò)資源;三是計算復(fù)雜度較高.因此,本文在MIRA基礎(chǔ)上提出一種新的啟發(fā)式算法KPLA,并針對MIRA的以上缺點進行了較完備的改進.3鏈路算法的高效快絡(luò)本文提出K路徑標號算法.算法首先基于擴展標號算法來計算K條最短路徑集合,避免忽視掉重要的非關(guān)鍵鏈路,而同時將最大流計算映射為最短路徑權(quán)值的計算降低了計算復(fù)雜度,然后綜合考慮鏈路關(guān)鍵度和鏈路最大剩余帶寬的影響,結(jié)合K值賦予不同的鏈路權(quán)值,避免選擇過長的路徑,并進一步結(jié)合預(yù)計算和在線計算減少計算復(fù)雜度,使得算法高效快捷.我們首先定義網(wǎng)絡(luò)模型和介紹相關(guān)概念.3.1網(wǎng)絡(luò)模型的建立我們使用圖論工具來描述網(wǎng)絡(luò)圖拓撲模型.采用一個n個點m條邊的無向加權(quán)連通圖G(V,E,C)為網(wǎng)絡(luò)的模型,其中,n表示節(jié)點個數(shù),m表示鏈路數(shù),V代表網(wǎng)絡(luò)中路由器的集合,E為鏈路集合,C為鏈路帶寬集.V中的子集(s,d)作為產(chǎn)生LSP請求的入口出口節(jié)點對集合,其中,s為入口節(jié)點,d為出口節(jié)點,(i,j)∈(s,d).R(l)表示任意時刻鏈路l的剩余帶寬.3.2擴展標記算法由于傳統(tǒng)的K-最短路徑算法如二分掃除法等求出的K-最短路徑無法保證是簡單路徑,可能存在回路,因此本文提出擴展標號算法以求出K條最短路徑長度,算法對節(jié)點進行標號,消除了路徑存在回路的可能性,確保求出無回路的K條最短路徑.我們用鏈表LIST記錄節(jié)點,對于V中的每一個頂點j,賦予兩個標號:距離標號uj,記錄從起點到該頂點的最短路徑長度的上界;前趨標號predj,記錄當起點s到該頂點j的一條路長取到該上界uj時,該條路中頂點j前面的那個直接前趨節(jié)點,wij為權(quán)值.具體步驟如下:1.設(shè)h1j1j,h2j2j,…,hkijjkijj分別為入口s到任意節(jié)點j的最短路徑長度,次最短路徑長度,…,次k短路徑長度,距離標號u1j1j,u2j,…,ukj分別記錄入口s到任意節(jié)點j的最短路徑長度上界,次最短路徑長度上界,…,次k短路徑長度上界.前趨標號pred1j,pred2j,…,predkj分別記錄當起點s到該頂點j的一條路長取到該上界uj時,該條路中頂點j前面的那個直接前趨節(jié)點,其中(j∈V).初始化所有hxj,令2.計算最短路徑長度h1j,方法如下:(1)令鏈表LIST(1)記錄已經(jīng)求得最短權(quán)值距離的節(jié)點,LIST(1)={s},u1s=0,前趨標號pred1s=0,對所有其它節(jié)點j令u1j為無窮大.(2)如果LIST(1)=?,則結(jié)束,u1j就是從起點s到節(jié)點j的最短路長,最短路通過前趨標號回溯獲得,否則,進行下一步.(3)從LIST中刪去一個節(jié)點i,對從i出發(fā)的每條弧(i,j)判斷是否滿足u1j>u1i+wij.如果是,則令u1j=u1j+wij,并令LIST(1)=LIST(1)∪{j}.當從i出發(fā)的所有弧都檢查完以后,轉(zhuǎn)步(2).3.利用已有的h1j計算次最短路徑長度h2j,方法如下:(1)令鏈表LIST(2)記錄已經(jīng)求得次最短權(quán)值距離的節(jié)點,LIST(2)={s},u2s=0,前趨標號pred2s=0,對所有其它節(jié)點j令u2j為無窮大.(2)如果LIST(2)=?,則結(jié)束,u2j就是從起點s到節(jié)點j的次最短路長,次最短路通過前趨標號回溯獲得,否則,進行下一步.(3)從LIST(2)中刪去一個節(jié)點i,對從i出發(fā)的每條弧(i,j)判斷是否滿足u2j>min{[u2j,u1i+wij,u2i+wij]/[u1j]},運算A/B表示集合A去掉集合B后形成的集合.如是,則令u2j=min{[u2j,u1i+wij,u2i+wij]/[u1j]},并令LIST(2)=LIST(2)∪{j}.當從i出發(fā)的所有弧都檢查完以后,轉(zhuǎn)步(2).4.利用已有的h1j,h2j,…h(huán)n-1j計算次n短路徑長度hnj,方法如下:(1)令鏈表LIST(n)記錄已經(jīng)求得次n短權(quán)值距離的節(jié)點,LIST(n)={s},uns=0,前趨標號predns=0,對所有其它節(jié)點j令unj為無窮大.(2)如果LIST(n)=?,則結(jié)束,unj就是從起點s到節(jié)點j的次n短路長,次n短路通過前趨標號回溯獲得,否則,進行下一步.(3)從LIST(n)中刪去一個節(jié)點i,對從i出發(fā)的每條弧(i,j)判斷是否滿足unj>min{[unj,u1i+wij,u2i+wij,…uni+wij]/[u1j,u2j,…,un-1j]}如果是,則令unj=min{[unj,u1i+wij,u2i+wij,…,uni+wij]/[u1j,u2j,…,un-1j]},并令LIST(n)=LIST(n)∪{j}.當從i出發(fā)的所有弧都檢查完以后,轉(zhuǎn)步(2).5.按照上述方法,直至n=k,即可計算次k最短路徑長度hkj.分析以上算法我們可以得出結(jié)論:擴展標號算法對任何節(jié)點最多進行K次重新標號,重復(fù)執(zhí)行擴展標號算法必定能夠得出K條最短路徑,且其復(fù)雜度為O(kmn).運用擴展標號算法來計算K條最短路徑集合,能夠避免忽視掉重要的非關(guān)鍵鏈路,而同時將最大流計算映射為最短路徑權(quán)值的計算降低了計算復(fù)雜度.3.3鏈路關(guān)鍵度估計算本算法分為預(yù)計算和在線計算兩個階段.預(yù)計算階段算法首先使用擴展標號算法來計算K條最短路徑集合,然后刪除網(wǎng)絡(luò)中鏈路剩余帶寬R(l)小于C的瓶頸鏈路,得到殘留網(wǎng)G′,殘留網(wǎng)中鏈路的權(quán)重不會改變.由于網(wǎng)絡(luò)拓撲和鏈路結(jié)構(gòu)較少發(fā)生改變,我們將定位關(guān)鍵鏈路部分放在預(yù)計算階段進行.本文定義鏈路關(guān)鍵度的概念,它反映了任意鏈路在靜態(tài)拓撲信息網(wǎng)絡(luò)中鏈路可能的負載.鏈路關(guān)鍵度的引入有助于減少那些容易發(fā)生擁塞的路徑的負載,其函數(shù)值如公式(1):式中α(l)表示鏈路l的鏈路的關(guān)鍵度,Fl(s,d)表示入/出節(jié)點對(s,d)之間的最大流中通過鏈路l的流量,m(x)表示所有節(jié)點對中通過鏈路l的最大流數(shù)量.α(l)即為鏈路l所占所有入/出節(jié)點對的網(wǎng)絡(luò)最大流流量的平均值.3.4鏈路權(quán)重函數(shù)的合成在線計算階段我們進一步設(shè)置鏈路權(quán)重以求出最短路徑.該階段網(wǎng)絡(luò)提供的動態(tài)信息是最大剩余帶寬R(l),R(l)代表了該路徑上可用最大帶寬,給我們提供了每個入/出節(jié)點對之間的不同路徑的帶寬利用情況,在本算法中剩余帶寬越少的路徑,被選擇路由的可能性越小.我們針對不同K值的大小,將鏈路關(guān)鍵度和最大剩余帶寬兩個信息量合成鏈路權(quán)重函數(shù)β(l),公式如下:式中α(l)表示鏈路l的鏈路關(guān)鍵度,R(l)表示鏈路l的剩余帶寬,β(l)即為路徑l上的每一條鏈路的α(l)/R(l)比值和再加上K倍的權(quán)值系數(shù)λ.通過式(2)得出每條鏈路的成本后,選擇β值最小的可行路徑為最短路徑路由帶寬需求為c的當前LSP請求r(s,d,c),最后更新網(wǎng)絡(luò)中鏈路的剩余帶寬R(l).3.5殘留網(wǎng)gKPLA算法的步驟如下:輸入:G(V,E,C),LSP請求r(s,d,c).輸出:在s和d之間有c單位帶寬容量的一條路由.Step1.應(yīng)用擴展標號算法求出K條最短路徑Step2.刪除網(wǎng)絡(luò)中鏈路剩余帶寬R(l)小于C的瓶頸鏈路,得到殘留網(wǎng)G′;Step3.根據(jù)公式(1)計算鏈路關(guān)鍵度α.Step4.根據(jù)公式(2),計算出k條最短路徑相應(yīng)的鏈路權(quán)值β.Step5.選出β值最小的路徑,如果該路徑的每一條鏈路的剩余帶寬都高于請求帶寬,則該路徑即為最短路徑.Step6.否則選出β值次小的路徑,如果該路徑的每一條鏈路的剩余帶寬都高于請求帶寬,則該路徑即為最短路徑,否則進一步選出β值稍大的路徑,直至β值最大的路徑.Step7.如果每一條備選路徑都沒有選上,則拒絕該請求,返回到Step1,輸入下一個請求.Step8.從s到d沿著最短路徑路由帶寬需求為c單位的LSP,更新鏈路剩余容量;Step9.返回到Step4,為下一個LSP請求做好準備.3.6算法復(fù)雜度的估計我們根據(jù)算法步驟來分析復(fù)雜度.Step1遍歷一遍網(wǎng)絡(luò)中所有鏈路,執(zhí)行k次擴展標號算法,復(fù)雜度為O(kmn),Step2、Step3需O(m),Step4～9最多需O(kn2).因此,算法總的復(fù)雜度為O(kmn+kn2),實踐中k通常取較小的常數(shù),比MIRA的復(fù)雜度Ο((p-1)n2√m)要低.同時,由于實際網(wǎng)絡(luò)中網(wǎng)絡(luò)拓撲結(jié)構(gòu)很少改變,Step1～3在預(yù)計算階段進行,只有當網(wǎng)絡(luò)拓撲結(jié)構(gòu)改變時才重新計算,所以KPLA復(fù)雜度實際為在線階段的復(fù)雜度O(kn2).因此我們可以得出:KPLA求出的LSP路徑能夠有效的進行LSP路由,并且算法高效快捷.4業(yè)務(wù)請求中三種算法間的比較本節(jié)我們通過模擬仿真實驗來評價KPLA算法的性能表現(xiàn).NS2是一種面向?qū)ο蟮?、離散事件驅(qū)動的網(wǎng)絡(luò)環(huán)境模擬器,能夠支持眾多的協(xié)議,提供了豐富的測試腳本,是目前網(wǎng)絡(luò)分析、研究和教學(xué)的首選工具.本文在linux平臺下,運行NS2的ns-allinone-2.26版本,進一步使用mns_v2.0擴展包向NS2添加MPLS流量工程模塊,并修改文件夾/ns-allinone-2.26/ns-2.26/tcl/mns_v2.0中的ns-mpls-cr.tcl文件以及部分底層C++源代碼文件以實現(xiàn)路由算法,最后采用數(shù)據(jù)分析工具awk分析運行產(chǎn)生的.tr文件分析結(jié)果.本實驗選擇較為流行的CSPF、MIRA與KPLA算法在拒絕率、時延、吞吐量以及路由計算時間等性能指標上進行比較分析.實驗中,我們設(shè)置K=3,權(quán)值系數(shù)λ=0.1.網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖1所示,由學(xué)術(shù)界普遍認同的MIRA算法拓撲結(jié)構(gòu)改進,能夠較好的模擬實際中的網(wǎng)絡(luò)拓撲結(jié)構(gòu),并便于同其他算法進行比較.其中節(jié)點0、1、2、13、14、15是傳統(tǒng)路由器,節(jié)點3、4、5、6、7、8、9、10、11、12是支持MPLS的標記交換路由器LSR(LabelSwitchingRouter),用正方形表示,鏈路帶寬如圖1所示.在本實驗中我們建立三種業(yè)務(wù)請求:(1)節(jié)點0發(fā)送數(shù)據(jù)流到節(jié)點13;(2)節(jié)點1發(fā)送數(shù)據(jù)流到節(jié)點14;(3)節(jié)點2發(fā)送數(shù)據(jù)流到節(jié)點15;在這三對入/出節(jié)點對之間分別建立5、10、15、20、25、30、35、40、45、50個LSP請求,請求頻率為每隔0.1秒同時建立一個請求,請求帶寬為200kb/s.三種算法在不同LSP請求數(shù)量下被拒絕的請求數(shù)如圖2所示.從圖2中可以看出,在30個請求之后CSPF首先出現(xiàn)了拒絕請求的行為,且拒絕數(shù)始終最大,這是由于其采用直接搶占機制,導(dǎo)致部分鏈路被過度使用而引起網(wǎng)絡(luò)擁塞;35個請求以后MIRA和KPLA都出現(xiàn)了拒絕請求的行為,但KPLA的請求拒絕曲線始終處于最低端.這表明KPLA從全網(wǎng)的范圍內(nèi)考慮網(wǎng)絡(luò)流量分配和性能優(yōu)化,采用的K條最短路徑集合能夠有效地避免忽視掉重要的非關(guān)鍵鏈路,同時利用鏈路權(quán)值均衡了負載分布,有效地減少了網(wǎng)絡(luò)擁塞.圖3是三種算法在進行業(yè)務(wù)請求(1)時端到端平均時延的比較.CSPF從10個請求以后上升較快,這是因為CSPF算法在帶寬滿足的情況下只選擇最短的路徑,沒有考慮后續(xù)請求的到達.KPLA在前10個請求時,延遲比CSPF和MIRA稍大,這是由于KPLA須離線計算,導(dǎo)致初始延遲較大;10個請求以后,KPLA延遲明顯降低,表明KPLA綜合考慮了進出口節(jié)點對、鏈路關(guān)鍵度和最大剩余帶寬的影響,能夠更好地均衡網(wǎng)絡(luò)負載,進一步結(jié)合K值賦予不同的鏈路權(quán)值,避免了選擇過長的路徑,減小了請求運行時間和擁塞等待時間.圖4是分別運行三種算法時終端鏈路node11→node13的吞吐量的比較.如圖所示KPLA的吞吐量從1.5秒開始在三種算法中一直是最大的,這說明KPLA算法計算最短路徑和最大流時,綜合考慮了進出節(jié)點對、鏈路關(guān)鍵度及最大剩余帶寬的影響,產(chǎn)生的路徑對未來LSP請求的干擾最小,并從全局范圍內(nèi)進行流量分配,使得更多的LSP請求均衡地通過網(wǎng)絡(luò),擴大了鏈路的吞吐