覆蓋網(wǎng)絡(luò)中一種具有全局優(yōu)化的路由策略

耿慶民，鄭明春

覆蓋網(wǎng)絡(luò)中一種具有全局優(yōu)化的路由策略

耿慶民，鄭明春

互聯(lián)網(wǎng)中流量分布不均引起網(wǎng)絡(luò)資源得不到有效利用、網(wǎng)絡(luò)擁塞。采用Wardrop均衡作為理論基礎(chǔ)，結(jié)合多下一跳路由機(jī)制，給出了一種基于系統(tǒng)最優(yōu)的負(fù)載均衡路由算法。仿真實(shí)驗(yàn)結(jié)果表明，該算法能夠滿足關(guān)鍵路徑流長度和網(wǎng)絡(luò)最大帶寬利用率等方面的要求。

服務(wù)覆蓋網(wǎng)絡(luò)（SON）；Wardrop均衡；負(fù)載均衡；路由算法

1 引言

目前，互聯(lián)網(wǎng)已經(jīng)成為一個(gè)由大量網(wǎng)絡(luò)自治域連接起來的、異構(gòu)巨型復(fù)雜網(wǎng)絡(luò)，隨著高速網(wǎng)絡(luò)與通信技術(shù)和流媒體技術(shù)的發(fā)展，Internet QoS服務(wù)支持獲得越來越多的需求。然而，由于歷史的原因，今天的Internet更多的是基于“盡力而為”的服務(wù)。為了增強(qiáng)當(dāng)前QoS服務(wù)模型，IETF開發(fā)了一系列提高Internet服務(wù)質(zhì)量的RFC標(biāo)準(zhǔn)，比如IntServ、DiffServ，但是迄今為止，這些成果都沒有大規(guī)模地應(yīng)用于互聯(lián)網(wǎng)。作為AS的經(jīng)營者，ISPs只能在在自己管轄的域中提供域間QoS，而對于域外的用戶，ISPs并不關(guān)心。在過去的幾年中，Overlay作為一種實(shí)現(xiàn)增值服務(wù)的網(wǎng)絡(luò)而受到人們廣泛關(guān)注，比如其優(yōu)秀的差錯(cuò)容忍、多播實(shí)現(xiàn)和安全性。但是絕大多數(shù)的Overlay是端用戶系統(tǒng)的，沒有中間用戶的支持。于是一種新型的模型應(yīng)運(yùn)而生——服務(wù)覆蓋網(wǎng)絡(luò)（Service Overlay Network，SON）。向ISP購買具有一定帶寬保證的鏈路構(gòu)成跨區(qū)域的虛擬覆蓋網(wǎng)，然后向用戶提供端到端QoS保證的增值服務(wù)而獲得效益，依據(jù)服務(wù)等級(jí)合同SLA（Service Level Agreement），SON經(jīng)營商與ISP、其他SON經(jīng)營者和其服務(wù)的用戶之間建立經(jīng)濟(jì)關(guān)系，通過在Overlay網(wǎng)絡(luò)節(jié)點(diǎn)上部署有效的管理設(shè)施，實(shí)現(xiàn)端到端QoS[1]。由于實(shí)現(xiàn)了網(wǎng)絡(luò)服務(wù)與底層設(shè)施的分離，因此SON的建立使跨區(qū)域的端到端的QoS體系的部署成為可能。

圖1 服務(wù)覆蓋網(wǎng)絡(luò)體系結(jié)構(gòu)

2 SON及Wardrop均衡

Duan Zhenhai等[1]提出了服務(wù)疊加網(wǎng)絡(luò)SON的概念，它是在現(xiàn)有IP基礎(chǔ)網(wǎng)絡(luò)之上建立的虛擬網(wǎng)絡(luò)。SON經(jīng)營者

文獻(xiàn)[2]提出了Wardrop均衡的概念，假設(shè)每個(gè)節(jié)點(diǎn)都是自私的，如果沒有一個(gè)節(jié)點(diǎn)能通過改變自己的路徑而降低自己的阻抗（時(shí)延、鏈路利用率等），那么就說系統(tǒng)是Wardrop均衡的。

定義1如果對于網(wǎng)絡(luò)中的每一個(gè)OD對i∈[k]，以及路徑 p∈Pi(fp＞0)，有Φp(f)≤Φp′(f)(p′∈Pi)，則流向量f達(dá)到WE均衡。

提出的算法的理論背景見文獻(xiàn)[3-8]。其中，F(xiàn)ederico Larroca的CNLS問題給出了基于最小時(shí)延的無參負(fù)載均衡函數(shù)，并證明了其結(jié)果的收斂性[3]。文獻(xiàn)[4]，證明了路由博弈CG問題等同于Wardrop均衡，且給出了系統(tǒng)最優(yōu)解。Vivek Raghunathan等分析了STARA路由算法[5]在移動(dòng)網(wǎng)絡(luò)中的性能，并提出了基于Wardrop均衡的系統(tǒng)模型：P-STARA和M-STARA[9-11]。Simon Fischer等提出了自適應(yīng)采樣TE模型，并證明該模型能快速收斂到Wardrop均衡[12]。文獻(xiàn)[13-14]則針對覆蓋組播網(wǎng)絡(luò)的路由研究，提出了均衡度分配（Balanced Degree Allocation，BDA）的路由方案，能夠有效均衡網(wǎng)絡(luò)負(fù)載并減小端到端時(shí)延。

本文在以上研究基礎(chǔ)上，提出一種基于Wardrop均衡的多路徑負(fù)載自適應(yīng)路由算法，具體見第3章。

3 基于Wardrop均衡的負(fù)載均衡路由算法（WELB）

3.1 模型描述

根據(jù)Wardrop均衡（WE）原理，網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都是“自私的”，它們中的每一個(gè)都想通過網(wǎng)絡(luò)G=(V，E)（V是所有網(wǎng)絡(luò)節(jié)點(diǎn)的集合，E是有向鏈路的集合）發(fā)送無限的流量以滿足自己的需求。設(shè)在網(wǎng)絡(luò)中存在k個(gè)源-目的對（OD對）{si，ti}，記所有OD對的集合為[k]={1，2，…，k}。在每一OD對之間存在一條或多條路徑，連接此OD對的源端和目的端，記連接OD對{si，ti}的源端和目的端的所有路徑集合為 Pi，網(wǎng)絡(luò)中所有路徑的集合為 P=Ui∈[k]Pi。記(fp)p∈P為OD對k在路徑p上分配的流量的大小，其中p∈Pk。

擁塞博弈（Congestion Game，CG）下潛在函數(shù)Ψ() d=為鏈路e上所有OD對流量的總和。每條鏈路都伴隨著一個(gè)基于流量的阻抗函數(shù)因此沿著路徑p傳輸一單位流量所導(dǎo)致的阻抗費(fèi)用為，并已證明CG滿足WE。這說明Φe(fe)為鏈路阻抗時(shí)，根據(jù)定義1 CG WE均衡達(dá)到最優(yōu)解。經(jīng)計(jì)算鏈路阻抗

選取一條路徑 p∈Pk，節(jié)點(diǎn)趨向于路徑阻抗φ最小化。按照博弈論的觀點(diǎn)，直到?jīng)]有一個(gè)節(jié)點(diǎn)可以通過轉(zhuǎn)換路徑獲得更好的阻抗（即節(jié)點(diǎn)所選的必為最短路中的一條，其他選擇的路徑一定比所選路徑差），即系統(tǒng)達(dá)到Wardrop均衡。

接下來動(dòng)態(tài)地理解下面的WE均衡。節(jié)點(diǎn)每隔T1s被激活一次，同時(shí)允許轉(zhuǎn)換路徑。為了避免碰撞，節(jié)點(diǎn)考慮的最佳策略是讓它被激活的時(shí)候轉(zhuǎn)移到阻抗最低的路徑，然而這將導(dǎo)致最優(yōu)路徑上的堵塞加劇并引起碰撞。文獻(xiàn)[15]采用了分區(qū)間采樣的策略。

在每一輪，每一個(gè)節(jié)點(diǎn)以概率λ被激活。每個(gè)被激活的節(jié)點(diǎn)執(zhí)行以下兩步：

（1）采樣。以概率ε執(zhí)行步驟①，以概率1-ε執(zhí)行步驟②：

3.2 WE網(wǎng)絡(luò)路由模型及其在SON網(wǎng)絡(luò)中的應(yīng)用

假設(shè)1在已知拓?fù)涞腟ON網(wǎng)絡(luò)中，若 S(p)≤S(Q) （S(p)指路徑P的長度），則有ΓS(p)≤ΓS(Q)。

基于此假設(shè)，本文的基本思想是所選路徑盡量保證跳數(shù)最少（允許一定的冗余，比如不超過最小跳數(shù)2跳），這樣既能充分保證所選路徑的阻抗較小，也能消除回路。

設(shè)S(r，t)為r～t的最短路徑（跳數(shù)）的長度，N(r，t)為OD對r～t路由器r的下一跳的集合。為r設(shè)置了兩種狀態(tài)：奇（1）和偶（0），用來標(biāo)記數(shù)據(jù)包逐跳的轉(zhuǎn)發(fā)收斂集合。當(dāng)狀態(tài)為奇（1）時(shí)，路由器下一跳僅僅從跳數(shù)嚴(yán)格減少的集合N1( ) r，t中選擇；當(dāng)狀態(tài)為偶（0）時(shí)，路由器下一跳所選路徑并不嚴(yán)格減少從集合N0(r，t)選取下一條。如下所示：

顯而易見，在這種方式下每經(jīng)過2跳路由到目的節(jié)點(diǎn)的路徑長度便減小1，同時(shí)消除了所有的回路，且所選路徑的長度不超過最短路徑長度的2倍。此處省略證明，細(xì)節(jié)見文獻(xiàn)[3]。

在真實(shí)IP網(wǎng)絡(luò)環(huán)境中，節(jié)點(diǎn)最主要的問題是不能控制流經(jīng)它的包。通常，網(wǎng)絡(luò)流的最終節(jié)點(diǎn)往往處于網(wǎng)絡(luò)邊緣，最典型的情況就是僅僅有一條鏈路與路由器相連。在路由選擇過程中，僅僅取決于目的端而忽略源端的其他屬性。

假設(shè)有一個(gè)存在于路徑s→r～t上的路由r，r為s的下一跳。r～t之間存在多條路徑。對于WE重路由策略而言，路由r能正確的在r～t選擇路由。然而，路由器r并不能知道所有的路徑，它僅僅知道r的下一跳的一個(gè)集合N(r，t)。其中，n為T時(shí)間間隔后的更新次數(shù)，ξ為轉(zhuǎn)移率，為鏈路r～t上的平均阻抗估計(jì)值，為r～t經(jīng)過下一跳vi的阻抗值。

為了達(dá)到負(fù)載均衡，每一個(gè)路由器將持有一個(gè)關(guān)于目的節(jié)點(diǎn)t動(dòng)態(tài)變化的權(quán)值π(r，t，vi)(vi∈N(r，t))，并且可表示為路徑s→r～t的流量具體分配方案。

具體實(shí)施過程中，采用vi～t上的期望阻抗?fàn)顟B(tài)即為1狀態(tài)，e狀態(tài)即為0狀態(tài)。為鏈路s→vi上的實(shí)時(shí)阻抗；為路徑的估計(jì)阻抗，等于上的實(shí)時(shí)阻抗與vi～t上估計(jì)阻抗的加權(quán)值；為s～t上的阻抗，由鏈路加權(quán)所得。

隨著負(fù)載的分配權(quán)值需要自適應(yīng)變化，以滿足負(fù)載均衡的需要。權(quán)值變化公式：

3.3 算法流程

算法流程如下：

（1）在每一個(gè)數(shù)據(jù)包中添加一個(gè)字段F，初始化可隨機(jī)設(shè)置。F每經(jīng)過一跳減少1(F=F-1)，在網(wǎng)絡(luò)中可以用IPV4 TTL值作為L。

（2）初始化一個(gè)空信息M；在每一個(gè)節(jié)點(diǎn)上測得n對觀測值(f1，Q1)，(f2，Q2)，…，(fn，Qn)，也稱為訓(xùn)練集合。訓(xùn)練函數(shù)為：

每隔T s通過訓(xùn)練函數(shù)及其(fn，Qn)測量數(shù)據(jù)計(jì)算一次αi與βi，然后測得鏈路即時(shí)阻抗：

（3）計(jì)算節(jié)點(diǎn)狀態(tài)X(F)=(1+F)mod 2，如果X(F)=0，則下一跳在N0( ) r，t中選擇?；蛘?X(F)=1，下一跳在N1( ) r，t中選擇。

（4）找到下一跳路由器集合Ni(r ，t)，i∈(0,1)后，通過以下方式選擇下一跳：

（5）權(quán)值以及轉(zhuǎn)移率決定路由：

根據(jù)以上流程，路由算法實(shí)施過程中需要實(shí)現(xiàn)幾個(gè)任務(wù)：首先，需要計(jì)算αi與 βi用于計(jì)算當(dāng)前鏈路的阻抗Γ*，為了達(dá)到這個(gè)目的就需要保存訓(xùn)練集合(fn，Qn)；然后需要?jiǎng)澐窒乱惶酚杉螻i( ) r，t，在此過程中需要保存字段F；接下來計(jì)算不需要節(jié)點(diǎn)額外信息。為了實(shí)現(xiàn)以上幾個(gè)任務(wù)，每一個(gè)路由器需要保存幾個(gè)值：L，路徑長度；下一跳集鏈路阻抗；路徑阻抗；路徑權(quán)值；轉(zhuǎn)移率。

4 仿真實(shí)驗(yàn)及算法性能分析

本文仿真使用文獻(xiàn)[16]中的網(wǎng)絡(luò)拓?fù)洌ㄈ鐖D2所示），圖中共有15個(gè)節(jié)點(diǎn)，每條鏈路都是雙向鏈路。本文假定拓?fù)渲兴墟溌返乳L，每條鏈路長度為1。

圖2 實(shí)驗(yàn)仿真拓?fù)鋱D

采取下面的策略驗(yàn)證算法的可靠性：從節(jié)點(diǎn)0到節(jié)點(diǎn)3中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為發(fā)送源點(diǎn)，從節(jié)點(diǎn)11到節(jié)點(diǎn)14中隨機(jī)選擇一個(gè)作為接收點(diǎn)，采用文獻(xiàn)[17]（奧克蘭大學(xué)實(shí)驗(yàn)室提供）中截取的網(wǎng)絡(luò)真實(shí)流量作為發(fā)送流，從5 s時(shí)刻開始不斷向網(wǎng)絡(luò)中加入靜態(tài)數(shù)據(jù)流（所謂靜態(tài)，這里指的是一旦加入就不再離開并持續(xù)到實(shí)驗(yàn)結(jié)束）直到網(wǎng)絡(luò)徹底擁塞（崩潰）。一旦網(wǎng)絡(luò)中某處鏈路負(fù)載達(dá)到飽和（這里認(rèn)為在真實(shí)網(wǎng)絡(luò)中鏈路利用率在40%以上即為網(wǎng)絡(luò)崩潰，所以選擇鏈路利用率40%作為臨界點(diǎn)），實(shí)驗(yàn)便宣告結(jié)束。算法在每條新流到達(dá)接收點(diǎn)時(shí)執(zhí)行，并且選取網(wǎng)絡(luò)中所有帶寬利用率最高的鏈路上流量最大的流作為關(guān)鍵流。本文模擬仿真在UBUNTU9.10下，采用NS2 2.34完成，所有實(shí)驗(yàn)編碼均采用C++及腳本Gawk實(shí)現(xiàn)。

實(shí)驗(yàn)選取SP算法、OSPF算法、P-START算法作為對比對象。SP即最短路徑優(yōu)先，采用迪克斯屈拉算法，是一種基礎(chǔ)路由算法。最短路徑優(yōu)先算法（OSPF）是一種典型的鏈路狀態(tài)（Link-State）的路由協(xié)議，一般用于同一個(gè)路由域內(nèi)。P-START算法是文獻(xiàn)[10]中提出的，具有較好的分散效果。對每種算法均作20次實(shí)驗(yàn)，進(jìn)行比較。

圖3和圖4分別是流個(gè)數(shù)和平均加權(quán)流長曲線。由圖可知，SP可承載流個(gè)數(shù)最少，且只考慮路徑長度，因此其平均加權(quán)流長最小。WELB算法可以加入流個(gè)數(shù)最多，并且其路徑長度較小，流量均衡，反應(yīng)其用戶體驗(yàn)較好。OSPF算法和P-START算法所承載流個(gè)數(shù)相當(dāng)，比SP算法有較大的改善，但是其路徑長度波動(dòng)性很大，證明其用戶體驗(yàn)相對WELB算法差。

圖3 流個(gè)數(shù)曲線圖

圖4 加權(quán)平均流長曲線圖

圖5是minLp曲線。由圖可知SP與OSPF無明顯收斂特征，P-START經(jīng)過長時(shí)間波動(dòng)之后逐漸收斂，但是效果并不理想。WELB算法波動(dòng)時(shí)間短，收斂明顯，說明對于網(wǎng)絡(luò)流量的均衡起到了良好的效果。

圖5 MinLp曲線圖

5 總結(jié)與展望

由于當(dāng)前互聯(lián)網(wǎng)資源管理依靠不斷擴(kuò)容，而得到基本服務(wù)的階段已經(jīng)過去，高品質(zhì)的應(yīng)用和有限的資源之間的矛盾會(huì)越來越突出，由第三方提供高質(zhì)量的區(qū)分應(yīng)用的服務(wù)是必然趨勢，QSON必將成為研究的熱點(diǎn)問題。本文首先分析了服務(wù)覆蓋網(wǎng)絡(luò)SON面臨的主要問題，然后提出了一種基于Wardrop均衡的負(fù)載均衡路由算法（WELB）。

通過模擬實(shí)驗(yàn)分析，說明本文算法性能有較大提高。但是由于算法本身對參數(shù)設(shè)置極為敏感，這成為實(shí)際應(yīng)用中最大的瓶頸，接下來要做的就是減小算法的參數(shù)敏感度，并在區(qū)分服務(wù)方面進(jìn)行更為細(xì)致的優(yōu)化。

近年來，Wardrop均衡理論在交通網(wǎng)絡(luò)中的應(yīng)用已經(jīng)逐漸成熟，但是在計(jì)算機(jī)網(wǎng)絡(luò)，特別是覆蓋網(wǎng)絡(luò)中的研究還待進(jìn)一步發(fā)展。

[1]DuanZhenhai，Zhang Zhili，HouYiwei.Serviceoverlay networks：SLA，QoS，and bandwidth provi-sioning[J].IEEE/ ACM Transactions on Networking，2003，11（6）：870-883.

[2]Wardrop J G.Some theoretical aspects of road traffic research[J]. Proceeding of the Institution of Civil Engineers，1952（1）：352-362.

[3]Larroca F，Rougier J L.Minimum-delay load-balancing through non-parametric regression[C]//Proceedings of the 8th InternationalIFIP-TC6 Networking Conference，Germany，May 11-15，2009，5550：782-794.

[4]Larroca F，Rougier J L.Routing games for traffic engineering[C]// Proceedings of the IEEE International Conference on Communication，2009：1-6.

[5]Gupta P，Kumar P R.A system traffic dependent adaptive routing algorithm for Ad hoc networks[C]//Proceedings of the IEEE Conference on Decision and Control（CDC），1997，3：2375-2380.

[6]Borkar V S，Kumar P R.Dynamic Cesaro-Wardrop equilibration in networks[J].IEEE Transactions on Automatic Control，2003，48：382-396.

[7]洪永發(fā)，徐娟.一般網(wǎng)絡(luò)中彈性效用價(jià)格競爭博弈的寡占均衡[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009（4）：550-554.

[8]王旸旸，畢軍，吳建平.互聯(lián)網(wǎng)覆蓋路由技術(shù)研究[J].軟件學(xué)報(bào)，2009（11）：2988-3000.

[9]Raghunathan V，Kumar P R.Issues in Wardrop routing in wireless networks[C]//Proceedings of the 1st International Conference on Wireless Internet，2005：34-41.

[10]Raghunathan V，Kumar P R.On delay adaptive routing in wireless networks[C]//Proceedings of the IEEE Conference on Decision and Control（CDC），2004，5：4661-4666.

[11]Raghunathan V，Kumar P R.Wardrop routing in wirless networks[J].IEEE Transactions on Mobile Computing，2004，8 （5）：636-652.

[12]FischerS，KammenhuberN，Charny A.REPLEX-dynamic traffic engineering based on Wardrop routing policies[C]// Proceedings of the International Conference on Emerging Networking Experiments And Technologies，2006.

[13]Lao L，Gokhale S S，Cui J.Distributed QoS routing for backbone overlay networks[C]//Proceedings of the 5th International IFIP-TC6NetworkingConference（NETWORKING2006），Coimbra，Portugal，May 15-19，2006：1014-1025.

[14]王超，卜佑軍，張興明，等.多下一跳路由機(jī)制下負(fù)載均衡算法研究[J].計(jì)算機(jī)應(yīng)用研究，2009，26（4）：1476-1479.

[15]Fischer S，Rache H，Vocking B.Fast convergence to Wardrop Equilibria by adaptive sampling methods[C]//Proceedings of the ACM Symposium on Theory of Computing（STOC），2006，5：653-662.

[16]Kar K，Kodialam M，Akshman T V.Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications[J].IEEE Journalon Selected Areas in Communication，2000，18（12）：2566-2579.

[17]WAND Network Research Group.Waikato Internet traffic storage[DB/OL].[2011-05-16].http：//www.wand.net.nz/wits/auck/ 9/20080328-160000-0.php.

GENG Qingmin,ZHENG Mingchun

山東師范大學(xué) 管理與經(jīng)濟(jì)學(xué)院，濟(jì)南 250014

School of Management and Economics,Shandong Normal University,Jinan 250014,China

The uneven distribution of the Internet traffic may lead to network congestion and underutilization of network resources. Concerning both the Wardrop Equilibrium（WE）and the next hop routing mechanism,an algorithm based on the system optimization is proposed.The effectiveness of the proposed algorithm in satisfying the demand of the length of key flow's path and the maximal bandwidth utilization rate is verified with simulation experiments.

Service Overlay Networks（SON）;Wardrop Equilibrium（WE）;load balancing;routing algorithm

A

TP301.6

10.3778/j.issn.1002-8331.1109-0107

GENG Qingmin,ZHENG Mingchun.Routing strategy offering global optimization in SON.Computer Engineering and Applications,2013,49（7）：102-105.

國家自然科學(xué)基金（No.60873058）；山東省自然科學(xué)基金（No.Y2008G16）。

耿慶民（1987—），男，碩士研究生，主要研究方向?yàn)镺verlay網(wǎng)絡(luò)，網(wǎng)絡(luò)流量預(yù)測；鄭明春（1963—），女，博士生，教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)協(xié)議，Overlay網(wǎng)絡(luò)。E-mail：gengqingmin@gmail.com

2011-09-13

2011-11-21

1002-8331（2013）07-0102-04

CNKI出版日期：2012-01-16 http://www.cnki.net/kcms/detail/11.2127.TP.20120116.0928.057.html