基于TeXCP的多路徑流量工程協議

,,

(解放軍理工大學 指揮信息系統學院 網絡工程教研中心,南京 210007)

0 概述

流量工程是當前因特網服務提供商提升網絡性能的重要方法,學術界和工業界對該研究領域進行了大量的探索。流量工程問題可以形式化為網絡鏈路最大鏈路率的最小化問題,這允許因特網服務提供商實現流量均衡、避免節點過熱和單點故障的優化目的。流量工程方法通過觀測網絡流量的變化規律來優化路由配置,達到通過在相同網絡流量需求下保持較低的網絡利用率的目的。

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

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

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

1 網絡模型

(1)

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

ft≥0,?t∈T

(2)

表示的多面體記為Γ。

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

2 具有穩定性的多路徑路由協議

2.1 MTE的流程

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

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

(3)

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

(4)

(5)

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

(6)

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

(7)

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

2.2 網絡的動態方程

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

(8)

隧道t對應的發送概率pt同該條隧道上的流ft成正比,如果定時器的間隔Isra足夠小,則式(8)的左邊變為隧道對應的發送概率的微分,因此可以導出下面的公式:

(9)

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

(10)

在流網絡模型假設下,文獻[5]和文獻[1]的流量穩定流程能夠轉換為一組微分方程。

2.3 MTE的穩定性分析

(11)

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

(12)

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

(13)

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

(14)

式(14)可以重新寫成:

(15)

定義ξ如下:

ξ=max{ξt},t∈T

(16)

則對于任意t∈T,有:

(17)

因此可以得到:

3 性能評估

3.1 仿真場景設置

為了驗證本文提出的MTE機制,在NS2中實現了MTE協議,并在Abilene網絡中評估了MTE的性能,其中Abilene網絡的拓撲如圖1所示。

圖1 典型Abilene網絡的拓撲結構

網絡中鏈路的帶寬為25 Mb/s,數據包的平均長度為1 000 Byte,而鏈路上的隊列長度為50個數據包。表1所示為MTE協議中的參數值設定。

表1 MTE協議的仿真參數

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

表2 Abilene網絡路徑的不同鏈路傳播時延

本文只關注MTE算法的穩定性,在實驗仿真中以數據包為單位進行調度。隨機選擇兩通信節點,并且記錄流量在其各條隧道上的變化情況。具體來說,評估算法的度量包括隧道對應的發送比例的變化情況及各條隧道的平均代價。

3.2 仿真結果

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

圖2 從亞特蘭大到堪薩斯的3條隧道上發送比例動態變化情況

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

為了從性能上對MTE和TeXCP進行比較,在Abilene網絡中分別實現了MTE和TeXCP,并對堪薩斯到亞特蘭大所有隧道上的隧道代價進行了統計,如圖3所示。

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

在圖3中,縱軸表示的是最小鏈路代價,曲線分別代表TeXCP和MTE各自進行的5次實驗結果。根據本文提出將非可加和的鏈路最大利用率作為路徑代價,縱軸表示的實驗結果則是網絡鏈路最大鏈路利用率達到的最小值。從圖3可以看出,在網絡穩定性上,MTE和TeXCP協議中網絡達到穩定狀態需要大約10 s,隧道代價均保持非常穩定的狀態。從達到穩定性狀態所需要的時間來比較,MTE和TeXCP具有基本相當的性能;從網絡穩定性狀態上來看,MTE協議所得到的數據曲線擬合度更高,TeXCP的數據曲線存在較大的波動,MTE的網絡穩定性更好;從圖中可以比較得到,TeXCP計算得到的隧道代價稍高于MTE。

4 結束語

本文在TeXCP的基礎上提出并驗證了MTE協議,證明了使用非可加和的最大鏈路利用率作為鏈路代價的可行性,并將網絡中運行機制抽象為一組微分方程。仿真結果表明,MTE協議具有較好的穩定性,與TeXCP相比,計算代價更低。

[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流量工程的路徑最優排序算法[J].計算機工程,2009,35(18):45-47.

[4] 鄧吉生,王海兵,張根度,等.基于MPLS的流量工程——分布實時網絡承載能力估計與分配模型[J].電子學報,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.