基于TeXCP的多路徑流量工程協(xié)議

,,

(解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院 網(wǎng)絡(luò)工程教研中心,南京 210007)

0 概述

流量工程是當(dāng)前因特網(wǎng)服務(wù)提供商提升網(wǎng)絡(luò)性能的重要方法,學(xué)術(shù)界和工業(yè)界對該研究領(lǐng)域進(jìn)行了大量的探索。流量工程問題可以形式化為網(wǎng)絡(luò)鏈路最大鏈路率的最小化問題,這允許因特網(wǎng)服務(wù)提供商實(shí)現(xiàn)流量均衡、避免節(jié)點(diǎn)過熱和單點(diǎn)故障的優(yōu)化目的。流量工程方法通過觀測網(wǎng)絡(luò)流量的變化規(guī)律來優(yōu)化路由配置,達(dá)到通過在相同網(wǎng)絡(luò)流量需求下保持較低的網(wǎng)絡(luò)利用率的目的。

近年來流量工程方法上的研究取得了突出進(jìn)展[1-4],其中離線方法中以最短路徑權(quán)重優(yōu)化(OSPF-TE)[5]和MPLS多商品流優(yōu)化[6]為代表,使用純Dijstra方法達(dá)到了顯著降低網(wǎng)絡(luò)最大利用率的效果。但是,離線的流量工程算法提前計(jì)算路由的方式不能很好地適應(yīng)實(shí)時的網(wǎng)絡(luò)流量需求,而且對網(wǎng)絡(luò)故障的發(fā)現(xiàn)和處理不能達(dá)到最優(yōu)化的效果。

目前網(wǎng)絡(luò)技術(shù)的飛速發(fā)展以及流量實(shí)時動態(tài)的發(fā)展需求使得實(shí)時的流量工程方法受到了越來越多的研究人員的關(guān)注,其中在線分布式的流量工程協(xié)議TeXCP[7]就是該領(lǐng)域的重要方法。TeXCP協(xié)議采用了多路徑標(biāo)記交換的機(jī)制,在網(wǎng)絡(luò)中構(gòu)造通信節(jié)點(diǎn)的路徑,并將流量在多條路徑上進(jìn)行分配[8]。TeXCP的流量均衡模塊根據(jù)最小化網(wǎng)絡(luò)最大利用率的目標(biāo)將流量負(fù)載在所有路徑上進(jìn)行分配,并且采用了閉環(huán)的反饋控制器用于保證鏈路利用率的穩(wěn)定性。流量工程問題從理論上可以抽象為多商品流(Multi Commodity Flow,MCF)問題,TeXCP并不能保證能夠收斂到MCF問題的最優(yōu)解,但TeXCP優(yōu)化網(wǎng)絡(luò)路由的性能非常出色。TeXCP協(xié)議中的流量均衡流程,即對路徑對應(yīng)的發(fā)送概率的更新同文獻(xiàn)[7]中的一致,該更新流程被證明能夠收斂到Wardrop均衡[8-9]。TeXCP與文獻(xiàn)[10]的重要差別主要有以下2點(diǎn):1)TeXCP采用基于路徑的發(fā)送方式,不同于文獻(xiàn)[10]中跳到跳的發(fā)送方式;2)在流量均衡的方式上,TeXCP采用了非可加和的路徑最大鏈路利用率作為路徑的代價,而文獻(xiàn)[11]采用可加和的鏈路時延作為路徑的代價。REPLEX[12]同樣是一個基于跳到跳傳輸?shù)牧髁烤鈪f(xié)議,并且采用非可加和的最大鏈路利用率作為路徑的代價,但該協(xié)議的支撐理論實(shí)際上采用了可加和的鏈路代價[13]。

綜上可知,同現(xiàn)有的研究相比,TeXCP確保網(wǎng)絡(luò)鏈路利用率的穩(wěn)定性機(jī)制較為復(fù)雜。此外,TeXCP在流量均衡機(jī)制上缺少完善的理論上的支撐。因此,本文提出并評估基于TeXCP的具有穩(wěn)定性特征的多路徑路由流量工程協(xié)議(Multi-path Traffic Engineering,MTE)。MTE和TeXCP最大的不同在于,MTE修改了TeXCP的流量穩(wěn)定流程,證明了將非可加和的最大鏈路利用率作為路徑代價的可行性,并且具有更為簡單的鏈路穩(wěn)定性機(jī)制。本文采用利亞普諾夫直接法[14]證明MTE能夠收斂到穩(wěn)定狀態(tài),通過仿真驗(yàn)證其穩(wěn)定性。

1 網(wǎng)絡(luò)模型

(1)

當(dāng)流量向量(ft),t∈T滿足如下條件時,則稱其為可行的:

ft≥0,?t∈T

(2)

表示的多面體記為Γ。

因特網(wǎng)提供商的自治網(wǎng)絡(luò)同樣可以用G=(V,E)表示,其中,V表示路由器而E表示路由器之間的有向鏈路集合。源路由器能夠通過一定的機(jī)制,比如MPLS,構(gòu)建到發(fā)送端的隧道,并將數(shù)據(jù)通過隧道發(fā)送到接收端。

2 具有穩(wěn)定性的多路徑路由協(xié)議

2.1 MTE的流程

MTE中包含2個具體的操作模塊:鏈路代價收集(CIG),鏈路發(fā)送概率調(diào)整(SRA),分別對應(yīng)于TeXCP中的路徑探測和負(fù)載均衡模塊。本節(jié)主要關(guān)注MTE同TeXCP兩者對應(yīng)的模塊之間的不同之處,其中最主要的不同在于MTE避免了TeXCP中復(fù)雜的鏈路穩(wěn)定性機(jī)制。

MTE中的隧道代價收集模塊包含2個流程。每個路由器維護(hù)一個鏈路利用率更新定時器,其超時間隔為Icig。當(dāng)定時器超時后,路由器計(jì)算鏈路e對應(yīng)的第k次鏈路利用率ue,k。因而鏈路的利用率ue可以通過如下公式計(jì)算:

(3)

其中,0<λ<1。每個發(fā)送端路由器同時維護(hù)一個反饋定時器,其超時間隔同樣為Icig。當(dāng)定時器超時后,發(fā)送端路由器向隧道t上發(fā)送數(shù)據(jù)包收集隧道對應(yīng)的最大鏈路利用率ut。

(4)

(5)

其中,0<ξ≤1是一個隨機(jī)變量,該變量能夠保證發(fā)送端探索路徑。Δpt的計(jì)算公式如下:

(6)

其中,δ>0是收斂速率。最后,發(fā)送端通過下面的公式更新隧道t對應(yīng)的發(fā)送概率:

(7)

路由器中沒有針對反饋數(shù)據(jù)包作特殊的優(yōu)化,因而反饋數(shù)據(jù)包在網(wǎng)絡(luò)中同樣有可能由于鏈路擁塞而導(dǎo)致丟包。當(dāng)隧道概率更新定時器超時后,發(fā)送端沒能在上一個Isra間隔中收到反饋數(shù)據(jù)包,則將該隧道t的最大鏈路利用率ut簡單地置為1,表示該隧道中的某條鏈路可能正在經(jīng)歷嚴(yán)重的擁塞。

2.2 網(wǎng)絡(luò)的動態(tài)方程

如果忽略式(5)中的邊界條件,則式(5)可以轉(zhuǎn)換為如下的公式:

(8)

隧道t對應(yīng)的發(fā)送概率pt同該條隧道上的流ft成正比,如果定時器的間隔Isra足夠小,則式(8)的左邊變?yōu)樗淼缹?yīng)的發(fā)送概率的微分,因此可以導(dǎo)出下面的公式:

(9)

其中,pt(0)=pt,0表示隧道t,t∈Ti,i∈I對應(yīng)的初始發(fā)送概率。式(9)是一個微分方程集合,表示了整個網(wǎng)絡(luò)中各條隧道上流的動態(tài)變化過程。式(9)能夠改寫為如下的公式:

(10)

在流網(wǎng)絡(luò)模型假設(shè)下,文獻(xiàn)[5]和文獻(xiàn)[1]的流量穩(wěn)定流程能夠轉(zhuǎn)換為一組微分方程。

2.3 MTE的穩(wěn)定性分析

(11)

對式(10)進(jìn)行微分可得:

(12)

將式(10)帶入式(12)中可得:

(13)

對任意t∈T,定義ξt如下:

(14)

式(14)可以重新寫成:

(15)

定義ξ如下:

ξ=max{ξt},t∈T

(16)

則對于任意t∈T,有:

(17)

因此可以得到:

3 性能評估

3.1 仿真場景設(shè)置

為了驗(yàn)證本文提出的MTE機(jī)制,在NS2中實(shí)現(xiàn)了MTE協(xié)議,并在Abilene網(wǎng)絡(luò)中評估了MTE的性能,其中Abilene網(wǎng)絡(luò)的拓?fù)淙鐖D1所示。

圖1 典型Abilene網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

網(wǎng)絡(luò)中鏈路的帶寬為25 Mb/s,數(shù)據(jù)包的平均長度為1 000 Byte,而鏈路上的隊(duì)列長度為50個數(shù)據(jù)包。表1所示為MTE協(xié)議中的參數(shù)值設(shè)定。

表1 MTE協(xié)議的仿真參數(shù)

路由器之間的傳播時延同2個路由器之間的距離成正比,具體的值如表2所示。對于網(wǎng)絡(luò)中任意2個路由器,在2個方向同時存在負(fù)載為1 Mb/s的泊松流。在網(wǎng)絡(luò)開始的時候,通過最短路徑算法計(jì)算任意通信節(jié)點(diǎn)對之間的隧道。

表2 Abilene網(wǎng)絡(luò)路徑的不同鏈路傳播時延

本文只關(guān)注MTE算法的穩(wěn)定性,在實(shí)驗(yàn)仿真中以數(shù)據(jù)包為單位進(jìn)行調(diào)度。隨機(jī)選擇兩通信節(jié)點(diǎn),并且記錄流量在其各條隧道上的變化情況。具體來說,評估算法的度量包括隧道對應(yīng)的發(fā)送比例的變化情況及各條隧道的平均代價。

3.2 仿真結(jié)果

圖2所示為從亞特蘭大到堪薩斯的隧道上發(fā)送比例的變化情況。2個城市之間有3條隧道:亞特蘭大->休斯頓->堪薩斯、亞特蘭大->印第安納波利斯->堪薩斯和亞特蘭大->休斯頓->洛杉磯->森尼維爾->丹佛->堪薩斯分別對應(yīng)于圖2中的x軸、y軸和z軸。圖2中任意一條曲線表示一次實(shí)驗(yàn)。

圖2 從亞特蘭大到堪薩斯的3條隧道上發(fā)送比例動態(tài)變化情況

從仿真實(shí)驗(yàn)的結(jié)果不難看出,所有的曲線都會收斂到一個固定的點(diǎn)(0.44,0.42,0.26),并最終在這個固定的點(diǎn)附近抖動。因此,MTE能夠收斂到某個固定的值。

為了從性能上對MTE和TeXCP進(jìn)行比較,在Abilene網(wǎng)絡(luò)中分別實(shí)現(xiàn)了MTE和TeXCP,并對堪薩斯到亞特蘭大所有隧道上的隧道代價進(jìn)行了統(tǒng)計(jì),如圖3所示。

圖3 亞特蘭大到堪薩斯的所有隧道上平均隧道代價

在圖3中,縱軸表示的是最小鏈路代價,曲線分別代表TeXCP和MTE各自進(jìn)行的5次實(shí)驗(yàn)結(jié)果。根據(jù)本文提出將非可加和的鏈路最大利用率作為路徑代價,縱軸表示的實(shí)驗(yàn)結(jié)果則是網(wǎng)絡(luò)鏈路最大鏈路利用率達(dá)到的最小值。從圖3可以看出,在網(wǎng)絡(luò)穩(wěn)定性上,MTE和TeXCP協(xié)議中網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)需要大約10 s,隧道代價均保持非常穩(wěn)定的狀態(tài)。從達(dá)到穩(wěn)定性狀態(tài)所需要的時間來比較,MTE和TeXCP具有基本相當(dāng)?shù)男阅?從網(wǎng)絡(luò)穩(wěn)定性狀態(tài)上來看,MTE協(xié)議所得到的數(shù)據(jù)曲線擬合度更高,TeXCP的數(shù)據(jù)曲線存在較大的波動,MTE的網(wǎng)絡(luò)穩(wěn)定性更好;從圖中可以比較得到,TeXCP計(jì)算得到的隧道代價稍高于MTE。

4 結(jié)束語

本文在TeXCP的基礎(chǔ)上提出并驗(yàn)證了MTE協(xié)議,證明了使用非可加和的最大鏈路利用率作為鏈路代價的可行性,并將網(wǎng)絡(luò)中運(yùn)行機(jī)制抽象為一組微分方程。仿真結(jié)果表明,MTE協(xié)議具有較好的穩(wěn)定性,與TeXCP相比,計(jì)算代價更低。

[1] WARDROP J G.Some theoretical aspects of road traffic research[J].Ice Proceedings Engineering Divisions,1900,1(3):325-362.

[2] FORTZ B,THORUP M.Optimizing OSPF/IS-IS weights in a changing world[J].IEEE Journal on Selected Areas in Communications,2002,20(4):756-767.

[3] 林 娜,呂萬方.基于MPLS流量工程的路徑最優(yōu)排序算法[J].計(jì)算機(jī)工程,2009,35(18):45-47.

[4] 鄧吉生,王海兵,張根度,等.基于MPLS的流量工程——分布實(shí)時網(wǎng)絡(luò)承載能力估計(jì)與分配模型[J].電子學(xué)報,2000,28(S1):127-130.

[5] ELWALID A,JIN C,LOW S,et al.MATE:MPLS adaptive traffic engineering[C]//Proceedings of the 20th Joint Conference of the IEEE Computer and Com-munications Societies.Washington D.C.,USA:IEEE Press,2001:1300-1309.

[6] FORTZ B,THORUP M.Robust optimization of OSPF/IS-IS weights[C]//Proceedings of International Network Optimization Conference.Berlin,Germany:Springer,2003:225-230.

[7] KANDULA S,KATABI D,DAVIE B,et al.Walking the tightrope:responsive yet stable traffic engineering[J].ACM SIGCOMM Computer Communication Review,2005,35(4):253-264.

[8] FISCHER S,KAMMENHUBER N,FELDMANN A.REPLEX:dynamic traffic engineering based on wardrop routing policies[C]//Proceedings of ACM Conference on Emerging Network Experiment and Technology.New York,USA:ACM Press,2006:6-17.

[9] MICHAEL N,TANG Ao,XU Dahai.Optimal link-state hop-by-hop routing[C]//Proceedings of IEEE Inter-national Conference on Network Protocols.Washington D.C.,USA:IEEE Press,2013:1-10.

[10] WANG Meng,TAN C W,XU Weiyu,et al.Cost of not splitting in routing:characterization and estimation[J].IEEE/ACM Transactions on Networking,2011,19(6):1849-1859.

[11] BORKAR V S,KUMAR P R.Dynamic cesaro-wardrop equilibration in networks[J].IEEE Transactions on Automatic Control,2003,48(3):382-396.

[12] WARDROP J G.Some theoretical aspects of road traffic research[J].ICE Proceedings Engineering Divisions,1900,1(3):325-362.

[13] MERTIKOPOULOS P,MOUSTAKAS A L.Selfish routing revisited:degeneracy,evolution and stochastic fluctuations[C]//Proceedings of International Conference on Performance Evaluation Methodologies and Tools.New York,USA:ACM Press,2011:217-226.

[14] WOLF A,SWIFT J B,SWINNEY H L,et al.Determining lyapunov exponents from a time series[J].Physica D Nonlinear Phenomena,1985,16(3):285-317.

[15] COLE R,DODIS Y,ROUGHGARDEN T.Bottleneck links,variable demand,and the tragedy of the com-mons[J].Networks,2012,60(3):194-203.

[16] APPLEGATE D,COHEN E.Making intra-domain routing robust to changing and uncertain traffic demands:understanding fundamental tradeoffs[J].Sigcomm,2003,33(4):313-324.