耿慶民，鄭明春

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

耿慶民，鄭明春

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

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

1 引言

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

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

2 SON及Wardrop均衡

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

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

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

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

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

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

3.1 模型描述

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

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

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

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

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

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

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

假設(shè)1在已知拓撲的SON網(wǎng)絡中，若 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），用來標記數(shù)據(jù)包逐跳的轉(zhuǎn)發(fā)收斂集合。當狀態(tài)為奇（1）時，路由器下一跳僅僅從跳數(shù)嚴格減少的集合N1( ) r，t中選擇；當狀態(tài)為偶（0）時，路由器下一跳所選路徑并不嚴格減少從集合N0(r，t)選取下一條。如下所示：

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

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

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

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

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

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

3.3 算法流程

算法流程如下：

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

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

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

（3）計算節(jié)點狀態(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ù)以上流程，路由算法實施過程中需要實現(xiàn)幾個任務：首先，需要計算αi與 βi用于計算當前鏈路的阻抗Γ*，為了達到這個目的就需要保存訓練集合(fn，Qn)；然后需要劃分下一跳路由集合Ni( ) r，t，在此過程中需要保存字段F；接下來計算不需要節(jié)點額外信息。為了實現(xiàn)以上幾個任務，每一個路由器需要保存幾個值：L，路徑長度；下一跳集鏈路阻抗；路徑阻抗；路徑權(quán)值；轉(zhuǎn)移率。

4 仿真實驗及算法性能分析

本文仿真使用文獻[16]中的網(wǎng)絡拓撲（如圖2所示），圖中共有15個節(jié)點，每條鏈路都是雙向鏈路。本文假定拓撲中所有鏈路等長，每條鏈路長度為1。

圖2 實驗仿真拓撲圖

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

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

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

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

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

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

圖5 MinLp曲線圖

5 總結(jié)與展望

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

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

近年來，Wardrop均衡理論在交通網(wǎng)絡中的應用已經(jīng)逐漸成熟，但是在計算機網(wǎng)絡，特別是覆蓋網(wǎng)絡中的研究還待進一步發(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)絡中彈性效用價格競爭博弈的寡占均衡[J].同濟大學學報：自然科學版，2009（4）：550-554.

[8]王旸旸，畢軍，吳建平.互聯(lián)網(wǎng)覆蓋路由技術(shù)研究[J].軟件學報，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].計算機應用研究，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

山東師范大學 管理與經(jīng)濟學院，濟南 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.

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

耿慶民（1987—），男，碩士研究生，主要研究方向為Overlay網(wǎng)絡，網(wǎng)絡流量預測；鄭明春（1963—），女，博士生，教授，研究方向為計算機網(wǎng)絡協(xié)議，Overlay網(wǎng)絡。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