基于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.