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

　　互联网服务提供商正面临着设计网络为客户提供快速、可靠和区分服务的挑战。在计算网络成本的模式下，互联网流量工程成为实现这个目标的一种关键技术^[1]。根据IETF，互联网流量工程被定义为:在运行的IP网络上进行性能评估和性能优化的网络工程^[2]。更精确地讲，流量工程经常有效地将流量需求映射到网络拓扑，并自动调节这种映射关系以适应网络状态的变化。值得一提的是，流量工程是通过满足一些限定条件来实现整个运行网络的最高效率，而QoS路由的主要目标是满足某些给定的源-目的数据流的QoS限制，从这个角度讲，流量工程的意义更为广泛。
　　交换式网络的发展，尤其是交换式以太网技术的发展(如千兆以太网标准^[3]的提出)满足了高速网络的多" title="的多">的多种关键需求，以太网技术的应用范围已经由局域网(LAN)扩展到城域网(WAN)。以太网是采用基于生成树的路由算法，网络结构都简化为简单的树形结构。虚拟局域网(VLAN)^[4]及多生成树协议(MSTP)[5]的提出为以太网流量均衡的实现提供了条件。基于VLAN和MSTP的以太网流量均衡选路算法[6]通过控制VLAN与生成树拓扑的映射关系来实现业务流的选路，从而达到流量均衡的目的。但这种算法只是提高了有效链路" title="链路">链路的利用率及整个网络树形路径上的流量均衡，并没有解决网络中两个节点（尤其是汇聚节点）之间多条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链路。

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.