覆蓋網絡中一種具有全局優化的路由策略

耿慶民，鄭明春

覆蓋網絡中一種具有全局優化的路由策略

耿慶民，鄭明春

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

服務覆蓋網絡（SON）；Wardrop均衡；負載均衡；路由算法

1 引言

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

圖1 服務覆蓋網絡體系結構

2 SON及Wardrop均衡

Duan Zhenhai等[1]提出了服務疊加網絡SON的概念，它是在現有IP基礎網絡之上建立的虛擬網絡。SON經營者

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

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

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

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

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

3.1 模型描述

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

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

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

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

在每一輪，每一個節點以概率λ被激活。每個被激活的節點執行以下兩步：

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

3.2 WE網絡路由模型及其在SON網絡中的應用

假設1在已知拓撲的SON網絡中，若 S(p)≤S(Q) （S(p)指路徑P的長度），則有ΓS(p)≤ΓS(Q)。

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

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

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

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

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

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

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

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

3.3 算法流程

算法流程如下：

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

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

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

（3）計算節點狀態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）權值以及轉移率決定路由：

根據以上流程，路由算法實施過程中需要實現幾個任務：首先，需要計算αi與 βi用于計算當前鏈路的阻抗Γ*，為了達到這個目的就需要保存訓練集合(fn，Qn)；然后需要劃分下一跳路由集合Ni( ) r，t，在此過程中需要保存字段F；接下來計算不需要節點額外信息。為了實現以上幾個任務，每一個路由器需要保存幾個值：L，路徑長度；下一跳集鏈路阻抗；路徑阻抗；路徑權值；轉移率。

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

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

圖2 實驗仿真拓撲圖

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

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

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

圖3 流個數曲線圖

圖4 加權平均流長曲線圖

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

圖5 MinLp曲線圖

5 總結與展望

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

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

近年來，Wardrop均衡理論在交通網絡中的應用已經逐漸成熟，但是在計算機網絡，特別是覆蓋網絡中的研究還待進一步發展。

[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]洪永發，徐娟.一般網絡中彈性效用價格競爭博弈的寡占均衡[J].同濟大學學報：自然科學版，2009（4）：550-554.

[8]王旸旸，畢軍，吳建平.互聯網覆蓋路由技術研究[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

山東師范大學 管理與經濟學院，濟南 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網絡，網絡流量預測；鄭明春（1963—），女，博士生，教授，研究方向為計算機網絡協議，Overlay網絡。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