摘 要： MATE算法通过检测多条路径的状态并计算其成本实现多条等价路径上的自适应流量调整，从而实现流量均衡，能有效地解决交换式网络中多TRUNK路径间的流量均衡。

　　关键词： 交换式网络; TRUNK; MATE; 流量均衡

　　互联网服务提供商正面临着设计网络为客户提供快速、可靠和区分服务的挑战。在计算网络成本的模式下，互联网流量工程成为实现这个目标的一种关键技术[1]。根据IETF，互联网流量工程被定义为:在运行的IP网络上进行性能评估和性能优化的网络工程[2]。更精确地讲，流量工程经常有效地将流量需求映射到网络拓扑，并自动调节这种映射关系以适应网络状态的变化。值得一提的是，流量工程是通过满足一些限定条件来实现整个运行网络的最高效率，而QoS路由的主要目标是满足某些给定的源-目的数据流的QoS限制，从这个角度讲，流量工程的意义更为广泛。

　　交换式网络的发展，尤其是交换式以太网技术的发展(如千兆以太网标准[3]的提出)满足了高速网络的多种关键需求，以太网技术的应用范围已经由局域网(LAN)扩展到城域网(WAN)。以太网是采用基于生成树的路由算法，网络结构都简化为简单的树形结构。虚拟局域网(VLAN)[4]及多生成树协议(MSTP)[5]的提出为以太网流量均衡的实现提供了条件。基于VLAN和MSTP的以太网流量均衡选路算法[6]通过控制VLAN与生成树拓扑的映射关系来实现业务流的选路，从而达到流量均衡的目的。但这种算法只是提高了有效链路的利用率及整个网络树形路径上的流量均衡，并没有解决网络中两个节点(尤其是汇聚节点)之间多条TRUNK链路的流量均衡。目前市场上的交换式网络设备都是采用静态配置的方法在多条TRUNK链路上进行流量分配，一旦某条TRUNK路径产生流量拥塞，网络就不能在多条TRUNK上进行流量自适应调整，必须由人工修改配置，这大大增加了网络维护的难度和网络拥塞发生的概率。交换式网络中多TRUNK路径的MATE流量均衡旨在解决这个问题，实现多TRUNK之间的自适应动态流量均衡。

　　1 问题场景描述

　　交换式网络中多TRUNK路径一般出现在网络的汇接层面，如互联网服务供应商局端设备汇接了多台接入设备，或汇接设备与核心设备之间的路由等。这里的TRUNK路径指两个节点间用于传输其他节点数据的链路，多TRUNK路径指两个节点间的多条等价链路。在交换式以太网中，如802.1Q封装的就是VLAN TRUNK。下文描述两个以太网接入过程中的多TRUNK路径的场景。

　　1.1 二层交换网络中的多TRUNK

　　二层交换网络中的TRUNK环境如图1所示。在小区、商务中心等驻地宽带网建设过程中，一般采用以太网交换机组成的二层交换网络，每幢楼根据用户接入需求设置楼层接入交换机，多台楼层交换机串连方式互联，最终接到小区的汇接交换机，交换机上采用VLAN技术进行安全隔离。在图1所示的小区网络中，共有五幢小区居民楼，其中‘2’号和‘4’号楼因用户数较多串连了三台楼层交换机，各采用了两条到汇接交换机的TRUNK链路，其他三幢楼都是两台楼层交换机和一条TRUNK链路。小区汇接交换机接入网络提供商的局端交换机时，考虑峰值流量和线路备份，也采用了两条TRUNK链路。

　　

 

　　在汇接交换机到局端交换机之间的两条TRUNK链路上配置了不同的VLAN用于输送不同楼的流量，TRUNK1上配置了VLAN 20～23，TRUNK2配置了VLAN 24～26。因‘1’号楼具有特殊的通信重要性，其VLAN 20同时配置在两条TRUNK上，以保证一条线路故障时能自动切换到另一条线路。根据以太网的工作原理，正常情况下，VLAN20只会选择其中的一条链路，不会均分到两条链路上，更不会根据两条TRUNK链路的流量状况自动调节其流量负载以达到最佳性能，一旦该TRUNK链路上其他VLAN的流量增大产生拥塞，VLAN20用户的访问质量就会明显下降，但目前情况下是没有办法解决的。

　　1.2 三层交换到路由之间的多TRUNK

　　三层交换到路由之间的多TRUNK环境如图2所示。在网络服务商提供的局端汇接交换机(三层交换机)与核心路由器之间有两条TRUNK链路，TRUNK1上的VLAN 30～35和TRUNK2上的VLAN 36～39用于将一些专线用户直接二层透传到核心路由器，其三层路由在核心路由器上实现;TRUNK1上的VLAN 10和TRUNK2上的VLAN 11用于转发汇接交换机到核心路由器之间的其他流量，汇接交换机上这两个VLAN下直接配置IP地址和相关的默认路由。假设这两条路径是等价的，根据PER-DESTINATION或PER-PACKET的三层转发原则，其他流量会均分到TRUNK1的VLAN 10和TRUNK2的 VLAN 11两个虚口上。当某条TRUNK链路上的透传VLAN流量增大造成拥塞时，该链路上的转发流量是无法根据当前链路状况自动调整到另一条空闲链路上实现动态流量均衡的。

　　

 

　　2 MATE算法

　　MATE(Multipath Adaptive Traffic Engineering)算法[1]是一个基于状态的流量工程机制，称为。它的特点有：

　　(1) 分布式自适应负载均衡算法;

　　(2) 入节点和出节点之间的端到端控制;

　　(3) 不需要在中间节点引入新的硬件或协议;

　　(4) 不需要知道流量需求;

　　(5) 对节点上的调度或缓冲管理机制不做假定;

　　(6) 基于路径拥塞测量的优化决定;

　　(7) 最少的分组重排序;

　　(8) 在两个节点之间没有时钟同步。

　　假设在链路l∈L上的流量为所有经过l的TRUNK上的源速率的总和：

　　

 

　　与每个链路l相关联的成本函数是Cl(xl)，作为链路流量xl的函数。假设对于所有的链路l，Cl(·)为凸函数，是连续的。算法的主要思想是：

　　(1)算法的目标是通过在TRUNKs上最优化流量路由，使总成本：C(x)=

为最小。

 

　　(2)将链路L的成本函数的一次导数看作链路的一次导数长度。

　　(3) 最优速率是在最优情况下，链路L的成本函数的一次导数长度最小。

　　成本函数的选择决定了在执行MATE中要测量和均衡的参数。链路成本的一个自然选择是时延。图3描述了流量均衡的基本模型。

　　

 

　　测量和分析模块主要用于发送探测包，获取TRUNK路径时延，并测量各VLAN和TRUNK上的流量，分析计算可以负荷调整的流量。流量工程模块决定在多TRUNK路径间转移流量的时间和方式，用于实现流量均衡，是算法实现的核心。它基于使用探测包分组测量获得的TRUNK路径统计信息完成。流量工程有两个阶段：监视阶段和负载均衡阶段。在监视阶段，如果探测到网络状态是可估计和持久变化的，就转移到负载均衡阶段。在负载均衡阶段，算法试图使多TRUNK路径之间的拥塞测量结果相等。一旦测量结果相等，算法就转移到监视阶段，重复以上过程。

　　3 多TRUNK路径的MATE流量均衡

　　在多TRUNK路径的MATE流量均衡中，将TRUNK上的流量划分为：(1)需要负荷分担的VLAN流量(如场景一中的VLAN20，场景二中的VLAN10和VLAN11)，称为保障流量;(2)不需要负荷分担的VLAN流量，称为汇聚流量。选取TRUNK时延为成本函数，最优速率的情况是TRUNK时延对流量的一次偏导数的绝对值最小。将导数绝对值最大的TRUNK的保障VLAN流量转移fl/N至绝对值最小的TRUNK的保障VLAN，直到所有TRUNK的导数绝对值近似相等。

　　流量负荷分担的过程分为四个阶段，如图4所示。

　　

 

　　3.1 初始化

　　这一阶段主要完成交换式网络环境的初始化，包括汇聚VLAN流量初始化、保障VLAN流量初始化和TRUNK流量初始化，并获取初始化时延，用Init()实现。

　　#define RAND_MAX 01010000 //设置随机函数最大值为80%*L(链路带宽)，以便为各VLAN FE链路产生链路利用率80%以下的正常流量。

　　//初始化

　　Init()

　　{

　　// 汇聚VLAN流量初始化

　　for(int i=0;i++;i　　　　　{fvlan3i=rand();} //初始化汇聚VLAN流量

　　//保障VLAN流量初始化

　　//假设有L条TRUNK,分为两种情况:

　　//第一种，初始情况下，保障VLAN仅有一个，流量全部由Trunk0承载

　　//第二种，初始情况下，有L个保障VLAN，流量平均分担在L条Trunk上,α为汇聚流量与保障流量的带宽倍率。

　　//第一种情况 保障VLAN初始化

　　fu=rand()/α;

　　fvlan10=fu ;

　　for(int i=0;i++;i　　　{fvlan1i=0;};

　　//第二种情况 保障VLAN初始化：假设有L条TRUNK，也就有L个保障VLAN需要在L条TRUNK上负荷分担流量

　　fu=rand( )/α;

　　for(int i=0;i++;i　　　　　{fvlan1i=fu/L;}

　　//Trunk流量初始化

　　for(int j=0; j++;j　　{Ftrj(old)=fvlan1j;

　　Qj=Q(Trunkj); //为Trunkj上的汇聚VLAN数量赋值

　　for(int i=0;i++;i　　　　{Ftrj(old)= Ftrj(old)+ fvlan3i ;}

　　Dtrj(old)=ICMP1;} //发送ICMP探测包、获取各TRUNK的时延

　　}

　　}

　　上面算法中，通过随机函数rand()为每个VLAN生成链路利用率80%以下的正常流量，根据VLAN的区分生成汇聚VLAN流量，然后根据通常情况下TRUNK流量分担的情况，累加相关VLAN流量，得到各TRUNK的流量，最后通过发送ICMP包，获取各TRUNK的初始化时延。

　　3.2 产生突发流量

　　这个阶段通过产生突发流量来仿真网络上流量发生变化的情况，从而使某TRUNK路径上的流量过大产生拥塞问题，导致网络质量下降，用burst()函数实现。

　　//产生流量变化

　　Burst()

　　{

　　//为汇聚VLAN产生随机流量增量

　　for(j=0;j++;j　　{Δf=rand()/β; //产生一个流量增量，

　　β为流量增量因子

　　fvlan3j=fvlan3j + Δf;}

　　//为保障VLAN产生随机流量增量，同时计算保障VLAN

　　总流量增量fl

　　fl=0;

　　for(int i=0;i++;i　　{cout << ' fvlan1i != 0' << endl;

　　//如果是上面第一种情况，则只增加VLAN10的流量，跳出循环

　　Δfl=rand()/αβ;

　　fvlan1i=fvlan1i +Δfl;

　　fl=fl+Δfl;}

　　//更新所有Trunk流量

　　for(int j=0;j++;i　　{ Ftrj(new)=fvlan1j;

　　Qj=Q(Trunkj);

　　for(int i=0; i++; i　　　　{Ftrj(new)= Ftrj(new)+ fvlan3i ;}

　　Dtrj(new)=ICMP1;} //发送ICMP探测包、获取各TRUNK的时延

　　}

　　上面算法中，通过随机函数为每个VLAN产生一个合适的突发流量，然后根据通常情况下TRUNK流量分担的情况，累加相关VLAN流量，得到各TRUNK的流量。由于负荷调整的VLAN仅为保障VLAN,因此还需要计算这部分增加的流量，用于下一步流量负荷调整。另外还需要获取流量变化后各TRUNK的时延。

　　3.3 平衡流量

　　这个阶段实现突发流量的平衡，将某个TRUNK路径上产生的过大突发流量均衡到其他TRUNK路径上，从而实现多TRUNK路径之间的自适应流量调整，用balance()函数实现。

　　//平衡流量

　　Balance()

　　{do

　　//获取各TRUNK的时延导数绝对值U，找到最大和最小导数绝对值的TRUNK

　　U0=| Dtr0(new)-Dtr0(old)|/|Ftr0(new)-Ftr0(old)|;

　　MAX=U0; MIN=U0

　　for(int j=1;j++;i　　 {

　　Uj=|Dtrj(new)-Dtrj(old)|/| Ftrj(new)-Ftrj(old)|;

　　If Uj>MAX

　　MAX= Uj;

　　k=j;

　　v=0;

　　elseIf Uj　　 MIN=Uj;

　　w=j;

　　v=0;

　　else v=1;

　　}

　　//将导数绝对值最大的TRUNK的保障VLAN流量转移fl/N至绝对值最小的TRUNK的保障VLAN

　　fvlan1k= fvlan1k - fl/N;

　　Ftrk= Ftr1 - fl/N;

　　fvlan1w= fvlan1w+ fl/N;

　　Ftrw= Ftrw+ fl/N;

　　Dtri(old)=Dtri(new);

　　Dtri(new)=ICMPi; //发送ICMP探测包、获取TRUNK的时延

　　}

　　While (v != 1)

　　for(int j=1;j++;i　　{Ftrj(old) = Ftrj(new);} }

　　上述算法中，各TRUNKi的保障VLAN的总流量增量为f l，将总流量增量f l分为N份，TRUNKj时延的导数的绝对值Uj=|Dtrj(new)-Dtrj(old)|/|Ftrj(new)-Ftrj(old)|。如果TRUNKj的导数的绝对值最大，TRUNKi的导数绝对值最小，则从VLAN1j移动f l/N流量到VLAN1j，反之则相反，直到各条TRUNK的时延变化率的绝对值相等。

　　实现流量均衡后，系统自动进入监测状态，通过发送ICMP探测报文监测各TRUNK路径的动态链路状态信息。

　　3.4 流量监测

　　每隔一段时间(这个时间最好是一个随机的时间，可以减少由于多个入口TRUNK在同一时间发现网络变化造成同步的影响)在每条TRUNK上发送探测包，发送的探测包不足链路上流量的百分之一，获取TRUNKj的时延Dtrj(new)。如果发现新的时延增量大于门限值，则回到流量平衡阶段。

　　采用适应性流量工程[7]能更有效地利用网络资源，使拥塞最小化。在两个节点之间多条平行的流量主干上进行负载分配是一个十分重要的问题。在许多情况下，两个节点之间的某业务量无法由任何一条单独的链路或路径来承担。然而该业务流量所需的资源可能低于网络中所有可用路径能够提供的总量。此时唯一的方法是将业务流量分解为一些流量子集，再将这些流量子集通过多条路径来加以传输。在交换式网络环境中，上述问题可以通过在两个节点之间发起多条TRUNK路径来解决。但要实现这一过程，必须要设计一种能够对多条平行的流量主干灵活地进行负载分配的技术。文中给出了MATE多路径自适应算法，该算法在多TRUNK路径之间分配流量，从而达到负载均衡化和拥塞最小化的目的。下一步工作将通过仿真平台[8]验证MATE算法解决多TRUNK路径流量均衡的有效性。

　　参考文献

　　[1] ELWALID A, CHENG Jin, LOW S, et al. MATE:MPLS Adaptive Traffic Engineering[J], IEEE 2001.

　　[2] AWDUCHE D, MALCOLM J, AGOGBUA J, et al. Requirements for traffic engineering over MPLS[S]. IETF RFC 2702, Sep.1999.

　　[3] Draft Standard IEEE 802.3z. Media Access Control(MAC)　Parameters, Physical Layer,Repeater and Management Parameters for1000Mb/s Operation[S].1998.

　　[4] IEEE Standard 802.1Q. Virtual Bridged Local Area Networks[S]. 1998.

　　[5] IEEE 802.1s/D7.Draft Supplement to Virtual Bridged Local AreaNetworks:Multiple Spanning Tree.IEEE Standard for Local and Metropolitan Area Networks[S], 2000.

　　[6] 刘军，雷振明.基于VLAN的以太网流量均衡选路算法[J]. 计算机工程，2003，(12).

　　[7] ALI M, CHIRUVOLU G, AN Ge. Traffic engineering in metro ethernet[J], IEEE Network, March/April 2005.

　　[8] 徐雷鸣，庞博,赵耀.NS与网络模拟[M]，北京：人民邮电出版社, 2003.

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。