依据被动测量的链路负载均衡

摘  要：研究提出了一种实时在线的流量工程方法在多条路径之间实现负载均衡，即LAMP（load adaptation based on measuring passively）. LAMP将流量从高利用率的链路转移到低利用率的链路上，转移的依据是以被动方式收集的信息，包括数据包往返时延（round trip time，RTT）和链路利用率。LAMP不需要周期性地探测网络，不需要路由器之间的大量通信，更不需要对输入的流量和网络拓扑做任何假设。评估结果表明，LAMP能够有效降低链路利用率，而且具有良好的稳定性。

关键词：计算机网络；在线流量工程；被动测量；多路径路由；负载均衡

 

1 引言

    互联网服务提供商（internet service provider，ISP）总是希望能够最大化地利用现有设施以最大化其利润，这触发了大量研究[1~9]来最优化路由系统（路由系统负载把数据包从源点传递到终点）。这些工作就被称为流量工程，流量工程通过分析、预测和调节在网络上传播的数据来优化网络的性能。一般地，流量工程可以形式化地表述为最小化网络的最大利用率问题。流量工程方法均离线操作，这意味着这些方法均衡的是在长时间粒度上的平均流量，时间粒度可能会达到多个小时，甚至几周或者几个月。截至目前，很多流量工程方法被提出，其中最流行的方法往往需要采用多协定标签交换（multiple protocol label switching，MPLS）隧道[1]，或者采用优化的域内路由协议链路权值[2~6]。同时，很多其他方法[1, 4~5, 7~9]致力于求解最小化链路的最大利用率这一问题，这些方法一般假设流量矩阵已知。但是在实际中，流量矩阵已经被证明是难以测量的[10~11]。

    虽然离线流量工程的作用非常明显，但是目前互联网上的应用，例如，流媒体、网络语音业务（voice over internet protocol，VoIP）、网络电视（internet protocol television，IPTV）以及分布式的网络游戏给路由带来了更加严峻的考验。在长时间粒度上达到良好的平均性能已经不够，路由器应当检测并响应网络中的拥塞。为了提供更佳的用户体验，ISP迫切需要路由器能够自动将流量切换到状况更好的路径上。而且，离线流量工程（traffic engineering，TE）方法只能对特定类型的状况预先计算备用路由方案。一旦出现新的问题，即使网络有足够的能力来处理这些问题，离线TE也无能为力[12]。

    面临这些挑战，研究自然而然地转向在线TE，在线TE方法能够响应实时的流量变化和路由失效。现在一些在线TE的方法已经被提出，包括MATE [13]，TeXCP [12]，REPLEX [14]和Homeostasis [15]。但是，这些方法都面临这一些问题，例如：1）假设全局的网络信息是已知的（MATE [13]）。2）需要MPLS的支持（MATE[13]和TeXCP [12]）。3）为了实现流量自适应负载均衡而需要反馈，但是反馈会带来抖动问题，因为需要复杂的机制以维持稳定性（MATE [13]，TeXCP[12]和REPLEX [14]）。4）需要周期性地向网络中发出探测包以测量反馈变量的值，这会向网络中注入大量的额外流量，而且会在在拥塞时注入更多（MATE [13]，TeXCP[12]和REPLEX [14]）；或者，广播新的链路权值供路由协议重新进行最短路径计算（Homeostasis [15]）。

    为解决这些问题，提出了在线TE方法——LAMP，该方法利用到达每个终点的多条权值非相等路径，自适应地把流量分配到这些路径上。分配的依据是被动收集的信息——RTT和链路利用率。所以，LAMP方法的关键组成部分有：多路径路由、拥塞检测和负载均衡。多路径路由的前提是多路径的存在，幸运的是这方面已有广泛研究。在域内（intro-domin），我们可以计算前N条最短路径，然后为路由表中的每一个重点分配至多N个下一跳。在域间（inter-domain）, 许多研究已经展开了对域间路由协议BGP的研究和扩展，并且丰富了BGP的路径多样性，例如Dual-BGP[16], R-BGP[17]和MIRO[18]。LAMP采用RTT和链路利用率两个度量进行拥塞检测，因为这两个度量非常重要而且易于获得。RTT可以采用提出的完全被动方式[19~20]测量，不需要向网络中注入任何流量。链路的利用率可以被与其连接的路由器直接测量，也不需要任何额外的数据包。当RTT增长过快或链路利用率过高时，认为拥塞出现。一旦某个路由器检测到了拥塞，该路由器把流量从高利用率的链路转移到低利用率的链路以缓解或消除拥塞。为了避免同一个流内的数据包重排序，在重新分配流量时以流?[?一个流由五元组定义：<源IP地址，源端口，目的IP地址，目的端口，协议号>]作为单位。

    总之，LAMP通过多条路径之间的负载均衡同时降低链路利用率和延时，而且具有良好的稳定性。特别地，研究拥有以下创新点：1）提出了LAMP——一种简单有效的在线TE方法，该方法利用被动测量的信息在多条路径之间进行负载均衡；2）LAMP能够运行在现有的路由协议之上；3）LAMP不采用反馈变量，因而不需要周期性的探测包或复杂的机制来维持稳定性；4）LAMP在必要时会把拥塞情况通知上游的邻居路由器。评估结果表明，与现有在线TE方法相比，LAMP拥有更佳的性能和更低的代价。

1 概述依据被动测量的流量均衡方法

    LAMP的基本设计为：LAMP把流量从高利用率的链路转移到低利用率的链路以应对突发的流量以达到负载均衡的目的。负载均衡的依据是本地被动测量得到的信息，包括RTT和链路利用率。如果一个路由器不包含多路径信息或者不能有效缓解严重的拥塞，该路由器通知上游的邻居路由器以减少向它转发的流量。下面将描述RTT是如何测量和使用，以及如何在多路径之间进行流量均衡，以及为什么LAMP是稳定的。

    1）被动RTT测量：利用已有的流量（尤其是TCP包）被动地测量TCP流的RTT. RTT是传输时延、传播时延、排队时延等的总和，它反映了一条路径的质量。一台路由器可以以完全被动的方式测量一个流的RTT，不需要向网络中注入任何探测包。这种被动测量的方法已经在先前的研究中提出[19~20]，这里将直接利用该方法。

    2）每一个连接都有RTT，如果多个连接终点IP地址属于同一个IP前缀，那么这些连接将共享相同的下一跳地址，因而这些连接的RTT可以通过相同的下一跳链路测量。但是由于不同路径的最后几跳不相同，因此这些连接的RTT绝对值并不相同。但幸运的是，LAMP关注的并不是RTT的绝对值，而是RTT的增长量或者减少量。

    3）拥塞检测原理：如果非常接近一台路由器的下游链路，或该路由器的下一跳链路（直接与该路由器相连）正处于拥塞中，那么对应的RTT会增加并且链路利用率升高。将所有的RTT按照下一跳分组，相同下一跳的RTT分在同一组中。下一跳链路上的拥塞会导致那条链路上的RTT统一增加。据此，得出了判断拥塞的条件是：ΔRTT/RTT>?或者?>?，其中，?为链路利用率；?，?为阈值。表面上，RTT和链路利用率都可以预测拥塞，但二者均需要的原因是RTT的增长可以表明拥塞的出现，但是不能指出拥塞发生的具体链路，而链路利用率却可以。但是链路利用率却不能一直预测拥塞，考虑这种情况：多条链路的利用率都很高，但是均未超过阈值。此时，链路利用率不能预测潜在拥塞的存在，但RTT可以。所以，仅依靠RTT和链路利用率之一是不够的，二者同时需要。

    4）在检测到拥塞之后，如果当前路由器拥有多路径信息，那么就在多条路径之间进行负载均衡。否则，该路由器将该状况通知上游的邻居路由器。一旦收到了这类通知，路由器将在多条链路之间进行负载均衡，如此反复。

    5）为了避免抖动，当RTT和或链路利用率降低时，并不把ΔRTT/RTT<?或者? <?作为将流量转移到对应链路上的依据，而是保持当前的流量分配方式不变。实际上，这样的操作在先前的工作中非常常见，这就把RTT或者链路利用率当作了反馈变量（例如文献[12]、[14]将延时当作反馈变量），而反馈变量的使用非常容易导致抖动的发生。考虑以下情形：2条链路?和?被用于负载均衡，延时?被用作反馈变量。当路径?上的延时da很长时，一部分流量被转移到路径?上，随即da下降，db上升。因而，流量又会从路径?转移到路径?上，这又会导致da升高db降低，如此反复。这是一个简单但是典型的由于反馈变量存在而导致抖动的例子。文献[12]、[14]面临着这种抖动，因此一些复杂的机制被引入以解决抖动问题，例如，文献[12]中的XCP和文献[14]中的Wardrop. 由于LAMP不适用反馈变量，因而从根本上杜绝了抖动问题的发生。

    一个应用LAMP的简单例子如图1所示，其中每一台路由器都运行LAMP. 节点?和?两者都向节点?发送流量，路径分别为?→? →? →?→?和?→?→?→?→?. 在本例中，路径???与???，以及???与???是对称的（并不是严格要求）。假设链路<?，?>上出现了拥塞（原因可能是<?，?>的带宽不够或者流量太大），那么路由器?利用经过?的流量测量的RTT会增加，链路利用率也会升高。因而，路由器?检测到了拥塞，然后通过将链路<?，?>上的流量往链路?→?→?上转移以实现流量均衡。这样，拥塞可以被缓解甚至消除。

 

    接着假设链路<?，?>上的拥塞非常严重以至于路由器?的出口链路（链路<?，?>和<?，?>）在进行了流量均衡之后利用率依然超过了阈值。在这种情况下，路由器?通知上一跳的邻居路由器?和?（如图1中箭头所示），然后路由器?也开始进行负载均衡，以此类推。

    如果拥塞是由于一条路径上的多条链路流量负载很高，但是利用率均未超过阈值，此时LAMP设定只有流量的入口路由器可以响应拥塞，因为只有入口路由器可以把流量导入一条完全不同的路径。

    最后，LAMP适用于域内和域间环境，图1所示的环境既可以是域内的，也可以是域间的。

 

2 LAMP详细设计

2.1 被动测量RTT的方法

    被动测量RTT的方法在文献[19]、[20]中提出，并且被证明可行。这里直接利用这种方法计算RTT，而不用关心路由是否对称。此前，RTT已经有了很广泛的用途，包括：1）一条链路上分配的缓存取决于该链路上TCP连接的RTT[21~22]；2）RTT的估算有利于活跃队列的管理[23]；3）RTT能够帮助判定由于拥塞引起的无响应[24~25]。

    下面简述文献[19]提出的被动测量RTT的方法。最基本的技术包括SYN-ACK（SA）测量和Slow-Start（SS）测量，分别如图2a和图2b所示[19]。由于非对称路由的普遍存在，一台路由器很有可能只看到2台主机之间的单向流，可能是从发起方到接收方，或者从接收方到发起方。SA测量方法适用于前者，SS测量方法适用于后者。

    在发起方到接收方的流中，SA方法利用3次握手交换的包完成对RTT的测量。基本想法是测量最后一个SYN包和第一个ACK包之间的时间差，这个时间差就是RTT，如图2a所示。SS方法测量的是从接收方到发起方的流，基本想法是第一个和第二个流量突发之间的时间差与RTT非常接近，如图2b所示。

 

2.2 拥塞检测

    RTT被测量出来后，利用RTT和链路利用率（链路利用率可以由路由器直接获得）检测拥塞。首先定义拥塞：如果某条路径上的一条或者几条链路的利用率超过了预先设定的阈值?，或者该路径上的RTT增长也超过了预先设定的阈值?，那么这一条路径是拥塞的。

    对一台路由器而言，同一时刻有大量的TCP流经过该路由器，那么该路由器可以利用上述测量RTT的方法测量。用X表示RTT的值，X(?，?)表示流?在?时刻的RTT。根据下一跳的不同把RTT分组，相同的下一跳分在同一组。因此，?也应当把下一跳作为一个参数，那么得到?(?, ?, ?)，这表示流?在时刻?下一跳为?时的RTT. 虽然下一跳?可以由流?查路由表获得，为了清楚起见，这里仍然把?作为?的一个参数。

    对于下一跳为?的流?来说，在?1时刻可以测量其RTT，用?(??, ?, ?)表示。这样，流?在不同时刻的一系列RTT可以用?(?0, ?, ?), ? ? ?,?(???1, ?, ?),?(??, ?, ?),?(??+1, ?, ?)表示。希望利用RTT的增长率检测拥塞，而计算RTT增长率有2种方法：

    1）首先计算每个流的RTT增长率，然后为每个下一跳计算平均RTT增长率。

    2）首先计算每个下一跳的平均RTT增长值，然后计算每个下一跳的平均增长率。

    如上文所述，判断拥塞的条件是?? >?∣∣?? > ?. 其中，??为下一跳链路的利用率。该表达式的“或”操作的对象是2个不等式，这2个不等式任意一个为“真”都可以判断拥塞的存在，而不用关心另一个不等式的值。但是，单独任意一个不等式在有些情况下并不能检测到拥塞的存在。例如，??>?可以指出输出链路上的拥塞，但是不能检测出由路径上多条相对负载较重的链路造成的拥塞（这些链路的利用率均未超过阈值）。实际上，这种情况可以由??>?预测，但是该不等式不能指出拥塞发生的地点。所以需要将二者结合起来以做出更准确的拥塞检测。

    需要指出的是，虽然研究一再使用“流?的RTT”这样的表达方式，但是RTT只有对于TCP连接是有意义的。但是，由于RTT的测量方法只能观察到TCP连接的一个单向流，从发起方到接受方，或者从接收方到发起方。所以，为了表述简单，虽然说“流?的RTT”，但是实际表达的是该RTT属于某一个TCP连接，而且?是该连接的一个单向流。

    在以下3种情况下表达式?? >?∣∣?? > ?的值为真：1）仅?? >?为真；2）仅??>?为真；3）??>?和??>?均为真。

    对于情形1）来说，路由器能够检测到拥塞，但是不知道拥塞具体发生在哪条链路上，甚至是由于一条链路上的多条负载较重的链路造成（这些链路的利用率均未超过阈值）。所以，如果该路由器是流量的入口路由器，那么负载均衡操作就被触发，否则该路由器不进行任何操作。对于情形2）和3）来说，与该路由器直接连接的链路发生了拥塞，针对该链路的下一跳进行负载均衡。如果拥塞很严重，该路由器不能有效缓解，那么该路由器将通知上游的邻居路由器以减少向该路由器转发的流量，以此类推。

2.3 多路径路由

    多路径指在源点和终点之间有多于一条的路径，多路径是负载均衡的关键因素。在域内，OSPF已经支持相等权值的多路径路由（equal-cost multi-path），但这里寻求除此以外的多路径。实现多路径的方法是不限定流量一定在最短路径上转发。目前，部署最广泛的域内路由协议OSPF维护域内的完整拓扑结构。依据拓扑结构和OSPF链路权值的度量，可以计算出源点和终点之间的所有路径，从最短路径到最长路径。但是，这里并不需要所有的路径，在LAMP中，每台路由器为每个终点安装至多?个下一跳，对应前?条最短路径。

    一种简单的计算至多?个下一跳的方法是：只向离终点更近的节点发送流量。如果向距离终点更远的节点发送流量有可能会导致路径回环。定义节点?和?之间的距离为?和?之间最短路径的长度，用?(?，?)表示。假设节点?是节点?的邻居，如果?(?，?)>?(?，?)，那么?就是?到?的一个可行的下一跳（由于采用与OSPF相同的路径权值度量，不需要路由器之间额外的信息交换，因而也不需要向网络中注入额外的流量）。应当指出的是，即使?和?之间存在?条物理链路，有非常大的可能性源点?不能找到终点?，找到?个下一跳，因为有些下一跳对应的路径长度比当前节点距离终点的路径要长。一个极端的例子是距离终点（假设终点是?）最近的邻居节点（假设该节点是?），由于没有邻居节点比?更与终点?接近了，节点?只有一个下一跳到终点?，其实就是终点?本身。最常用的域间路由协议是BGP，由于BGP只选择并传播单条路径，BGP的多路径特征很差。幸运的是，已经有非常多的工作对BGP的多路径特性进行了研究并且达到了更佳的BGP多路径属性，例如Dual-BGP[16]，R-BGP[17]和MIRO[18]等。这里直接利用这些工作更加便捷地寻找域间的多路径。

2.4 流量均衡

    文献[26]中已经证明了通过把流量导入其他路径可以有效缓解甚至消除拥塞。但是何时转移流量以及向哪条链路上转移流量这些问题并没有被很好地解决，下面针对这些问题提出解决方案。目前的路由协议对数据平面是拥塞是无感知的，只会对网络拓扑的变化做出相应。在研究的解决方案中，路由器能够感知数据平面的拥塞并能够通过负载均衡缓解这一问题，延时也能够同时降低。而且为了避免TCP包重排序问题，以流为粒度进行负载均衡。

2.4.1 负载均衡策略

    一般地，拥有相同终点的流都会选择同一条路径——最短路径，这里称之为主路径。剩余的??1条路径被称为备用路径。在LAMP的负载均衡策略中，?条路径的地位不平等，基本的思路是：主路径拥有最高的优先级，只要主路径的下一跳链路利用率低于阈值?，会仅使用主路径。一旦主路径的下一跳链路利用率高于?，流量就会在剩余的??1条备用路径负载均衡。这?条路径根据OSPF的路径权值计算，在负载均衡时它们的排序依据对应的下一跳链路利用率。利用率越低，排名越靠前。

    之所以把链路利用率作为对下一跳排序的依据，是因为当进行负载均衡时，希望能够降低由于排队和拥塞造成的延时和丢包率。当链路利用率低于阈值时，包队列很短，所以排队时延可以忽略不计。但是一旦链路利用率超过阈值，包队列的长度快速增加因而时延也迅速增加。所以，在选择下一跳进行流量均衡时，优先选择低利用率的链路，这意味着此时这条链路上是没有拥塞的。

    负载均衡由路由器进行，现在已有多种经典的负载均衡方法，例如平均分配（equal split），最轻负载（least loaded），按序选择（load order）等。这里提出流量均衡的方法是按权值分配（weighted split）法，然后将该方法与经典的方法进行比较。

    1）平均分配：在所有的备用链路上平均分配超出阈值的流量；

    2）最轻负载：把超出阈值的流量全部转移到负载最轻的下一跳链路上；

    3）按序选择：先把超出阈值的流量全部转移到负载最轻的下一跳链路上，如果该链路因为转移来的流量其利用率超过阈值?，此时负载第二轻的备用路径成为负载最轻的路径，那么继续把超出阈值?的流量转移到负载最轻的路径上，如此反复。

    4）按权值分配：超出阈值的流量被分配到所有的备用链路上，每条路径分配到的流量与其当前的链路利用率成负相关。LAMP采用了按权值分配的方法。

2.4.2 通知上一跳邻居路由器

    如果某路由器不能缓解拥塞，原因可能是该路由器不包含某个终点的多路径信息，或者是所有备用路径也都超过它们的利用率阈值。此时，LAMP允许路由器通知上游的邻居路由器，然后上游路由器也可以通过负载均衡减少发往该路由器的流量。该方法在多路径信息缺乏或者负载很高的路由器上很有效。

2.4.3 以流为单位进行操作

    研究希望极力避免同一个流的包被转发到多条路径上，因为这会导致TCP包的重排序，并触发TCP慢启动算法，这将严重影响TCP的性能。很多方法都被提出以保证同一个流的包被转发到相同的下一跳，例如哈希方法（Hashing）。随着OpenFlow[27]和SDN[28]的提出，这一问题有了更好的解决方法。OpenFlow[27]和SDN[28]均以流为单位进行操作。由于OpenFlow/SDN交换机具有可编程性，可以通过编程定义对流的操作。伴随着OpenFlow/SDN交换机带来的增强流操作性能，负载均衡方案会有得到强劲的支持（但OpenFlow/SDN交换机并不是LAMP必须使用的设备）。

2.4.4 稳定性

    网络流量在多条路径之间来回切换被称为抖动，抖动的存在会减弱网络的稳定性。同时稳定性也是任何一个TE方法都必须面对的问题。在TE中，稳定性被严格地定义为：在输入流量稳定的情况下，每条链路上的流量渐近地收敛至稳定速率。

    LAMP拥有非常好的稳定性，因为LAMP不需要自适应任何反馈变量，比如路径的利用率?[? 路径的利用率被定义为路径上所有链路中的最高利用率[12, 14]]，延时和权值。自适应这些变量需要负载的机制保证稳定性。LAMP仅仅在数据平面根据链路的利用率进行负载均衡，这一操作不涉及任何反馈变量，因而能够保证控制平面的稳定性。

 

3 评估

    研究评估了LAMP算法的性能，且与其他流量工程算法进行了比较。评估方法是首先验证了被动RTT测量方法的有效性。之后，给定一个拓扑和流量矩阵，测量在没有使用流量工程的情况下，LAMP算法的链路利用率。然后，比较了在使用了负载均衡方法但是没有与上游邻居节点通信的情况下，Homeostasis[15]，LAMP算法的性能提升，也算出了LAMP算法的路径拉伸。实验中，使用的拓扑是EBONE（AS1755）的Rocketfuel[29]，其包括172个路由器和763个边缘；流量矩阵遵照重力模型[30]生成。实验中的RTT增量阈值和链路利用率阈值被分别设置为0.5和0.8. 每个路由器为每个终点设置有至多N=5个下一跳。

3.1 评估结果

3.1.1 RTT测量

    为测量RTT时间，从中国教育科研网（CERNET）捕获了一个5 min的trace，然后利用被动测量方法测量RTT值。因为这里的trace是在一个网关处取得，也可以利用传统方法测量RTT时间，例如：在3次握手过程中，匹配TCP SYN包和SYN ACK包。进一步，通过对比2种方法的结果验证被动RTT测量方法的准确性。定义RTT比值为RTTc/RTTp，其中RTTc为传统测量方法的RTT测量结果，RTTp为被动测量方法的RTT测量结果。图3展示了每个流利用2种方法测得的RTT比值。RTT比值按照递增排列，结果均在1.0附近，这表明2种RTT测量方法结果非常接近。

3.1.2 使用/未使用负载均衡的链路利用率分布

    通过比较在使用和未使用LAMP算法情况下，EBONE（AS1755）的Rocketfuel拓扑结构中所有链路的利用率分布评估LAMP算法的有效性和性能，结果如图4所示。当没有采用负载均衡算法时，对应的曲线表明：40%~60%甚至更多的链路利用率为0，而其他链路有很高的链路利用率。与未使用负载均衡算法时相比，LAMP将流量从高利用率链路转移到了低利用率链路。并且LAMP比其他负载均衡算法性能更好，它能够将流量在多条链路上均匀分配。因此，LAMP算法使用了更多的链路，并且每条链路的利用率都更低。值得指出的是这些图中（图4a?图4f），链路利用率会超过1，这是因为在每一轮负载均衡之前收集链路利用率信息。这之后，某条链路上溢出的流量会被负载均衡器分配到多条链路上（当前链路也被包括在内）。如果在负载均衡后链路利用率仍然超过1，多出的流量会被丢弃。采用这种统计学方法可以更好地反应负载均衡算法的性能。并且能看到，链路的负载越高（TM=0.5?1.0），当LAMP未使用时利用率超过1的链路越多。

3.1.3 加入与上游邻居节点通信后的性能

    随后，通过计算引入与上游邻居节点通信这一机制后，链路利用率降低的幅度来评估该机制的性能。为了突出该性能，我们把该机制下链路利用率降低的幅度与仅使用本地负载均衡（如Homeostasis）时链路利用率降低的幅度进行了对比。在不同TM下减少的链路利用率的分布如图5所示，其中注意负值表示链路利用率增加。由图5可以看出，在通信机制被加入后，利用率在60%?70%的链路的数量减小了，同时剩下的链路的利用率增大了。链路利用率增大的原因是邻居路由器在负载均衡过程中将一些流量迁移到了链路利用率较低的链路。因此，与上游邻居节点通信这个机制确实能够均衡流量并且降低链路利用率。根据图5，能够进一步得出按权值分配负载均衡方法实现的链路利用率降低幅度不是最大的。这是因为按权值分配方法在甚至不使用与上游邻居节点通信机制的情况下，也能取得很好的性能；当通信机制被采用后，这种方法的性能提升空间比其他方法更小。

3.1.4 链路拉伸

    定义链路拉伸为备用路径与最短路径之比。显然，将流量分割到备用路径会导致分组沿非最短路径传输。流量拉伸用来反映与最短路径相比，备用路径更长了多少，如图6所示。曲线表明备用路径仅比最短路径长了一点。直观地，链路拉伸应该随TM增大而增大。然而，因为TM遵循重力模型，对于同一个TM负载，每一条链路的利用率都不同。因此，负载均衡器表现不同，导致了链路拉伸值的抖动。

3.1.5 抖动

    测量了按权值分配算法的调整次数。如前面多次提到，LAMP没有任何反馈变量，因此，其面对流量抖动十分稳定。图7表明无反馈变量，当TM负载增加时的调整次数。这表明LAMP十分的稳定，因为LAMP算法在负载增大时只对负载进行一定次数的均衡，并且流量从来不会在一系列下一跳链路间来回切换。注意到x轴是平均相对输入，表示每一条链路上的负载会变化，并且一些链路会触发负载均衡过程。

3.1.6 通信开销

    最后，通过测量用于探测和信息交换的通信分组个数评估LAMP算法和其他方法的通信开销。如表1所示，LAMP算法的开销最低，并且那些通信分组都被用来与上游邻居路由器通信。Homeostasis的开销来源于每个路由器通过泛洪得到的路由器之间的距离（通过传时延表示）；而REPLEX和TeXCPA算法只需在每对节点之间进行一轮的探针分组发送。所有这些方法的通信分组开销均利用Rocketfuel网络拓扑测量得到。

 

 

4 相关工作

    当前，关于流量工程的研究已有很多[1~3, 5, 13, 31]，在这里无法详尽地列出所有相关文献。研究调研了一些比较著名的工作，然后将课题组的工作与其进行了详细的比较。

   TE通过对网络进行分析、预测，并规范网络数据传输的行为优化网络性能。具体来说，TE的目标是利用有限可用资源路由的尽可能多的数据流量。一般来说，TE的方法一般基于离线数据，即这些流量数据一般都是通过提前在网络中进行一段时间的监测得到，测量时间规模一般为几个小时，有时候规模可能达到几周或几个月。然后，通过对中心点的数据结果进行观察和分析，从而得出结论。这里的中心点指的是TE方法（如负载均衡及流量重新路由等）发挥作用的节点、路由策略被调整的节点（例如，为计算最短路径而对OSPF/ISIS的链路权重进行重新计算等），以及MPLS隧道被应用的节点。然后，TE的机制及调整后的路由策略将会一直在网络中运行，直至TE被重新启动，或者路由发生故障。这些TE机制对运营商解决长期变化的流量需求（如昼夜变化）有很大意义。

    TE不可能与多路径的负载平衡分离，因为其进行的前提就是具有多路径的信息。文献[32]提出了一种全新的原始路由方案，称为路径拼接（path splicing），这种方法能够为域内路由或域间路由提供大量可选路径。文献[16]提出了DualBGP方法，这种方法在同一台路由器上运行多个BGP实例，然后通过计算这几个不同实例计算出互补的BGP路径。另外一种解决方案是文献[17]中介绍的R-BGP方案。R-BGP方法通过提前计算几个故障移路径以保证在BGP收敛情况下，只要一个域与目的地点之间存在策略标准路径，那么这个域就不会与任意目的地址失去连接。文献[18]的MIRO算法则提出了一种多路径域间路由协议。在这种方法中，路由器通过现有的BGP协议获取默认的路由路径，而且任意的2个域可以通过协商计算它们之间的额外路径。以上这些方法都可以加以利用，从而增强域间路径的多样性。TE往往需要根据给定的预计流量矩阵优化路由流量。可以通过直接或者间接的方法获取流量矩阵。在流级别的数据测量是可以直接进行的情况下，可以通过文献[6]的方法直接测量准确的流量矩阵。然而，这种准确测量方法对于基础设施有着较高的要求，高昂的成本使其不可能大规模部署。当直接测量不可行时，还可以通过间接数据（例如链路的测量数据）估测出相应的流量矩阵。但是这种方法面临着很多挑战[10]，而且这种估计方法也可能会造成错误[11]。正如上文所述，一些早期的TE方案通过动态调整计算最短路径时的链路权重以适应负载变化[4~5, 7~9, 33~34]。

    然而，单个链路的权重调整将会导致最短路径的重新计算，而且相应的路由协议必须再次进行收敛。在收敛的过程中则可能会造成路由环路和数据包丢失，从而导致服务质量下降。而且，改变链路的权重也很有可能影响BGP路由的稳定性，因为BGP路径的选择由链路权重和策略共同影响，因此对于链路权重的改变必须十分谨慎。显然，每几个小时运行一次的离线方式不能很好地应对实时网络中的流量突发。流量的突然变化可能有很多原因，例如突发访问、BGP重新路由和昼夜流量流动。此外，当前的TE通过预先计算替代路径应对网络故障，但是这种处理方法仅适用于部分网络故障集合。尽管网络本身提供了足够的容处理拥塞，在处理集合之外的不可预计拥塞上面，这种方法可能不会有效果。

    研究人员已经意识到了离线TE机制的缺陷。为了弥补这些缺陷，一些基于在线的TE方法被广泛提出[12~14]。这些方法可以应用于基于当前网络架构的实时流量工程中，这些在线的TE可以很好地应对流量需求的实时变化。事实上，在线TE的思想并不是最近才出现，这种思想可以追溯到最初的Arpanet. 最早的负载自适应路由策略在Arpanet中就已经得到应用[35~36]，但后来由于分布式路由器的决策冲突导致震荡，这些方法被证明在稳定性和性能上都有一定的缺陷。类似于MATE[13]，REPLEX[14]，TeXCP[12]以Homeostasis[15]等方法，研究提出的LAMP方法也是一个基于在线方式的TE方法，下面将会对LAMP方法与其他方法进行比较。这4种方法[12~15]都是基于一些实时的反馈数据、利用输入和输出节点之间的多路径平衡负载。它们通过利用网络中的可选路径，并调整同一输入输出节点之间不同路径的流量分布优化整个网络的利用率，但是这些方法都面临着各种问题。

    1）MATE及TeXCP 2种方法中，显示路由的进行都需要多标签协议转换（multiple protocol label switching，MPLS）的支持，因此也就只能在MPLS网络中应用。然而很多网络运营商并没有使用MPLS，同时，通过自治域边界的MPLS路径也面临着很多已知问题，因此其使用范围受到了很大限制。LAMP方法则没有在网络的路由架构上作出假设，因此LAMP可以部署在现有的域内以及域间路由协议上。

    2）MATE[13]，REPLEX[14]及TeXCP[12]都遵循以下的规则：首先，一个负载平衡器测量网络的状态（延迟和路径利用率），并把测量结果当做反馈变量处理；其次，负载平衡器将流量从一个链路转移到另一个链路上，尽量减少链路利用率；第三，只有入口节点的路由器可以进行负载自适应，而路径上的中间路由器则不可以；最后，反馈变量是入口路由器通过周期性的发送试探数据包获得，这一周期的大小很难确定。同时，也正是由于反馈变量的存在，这一系统有着强烈的震荡趋势，因此必须采取一些复杂的措施避免震荡。

   3）MATE方法还假设存在路由器知道网络的整体数据，而LAMP方法只是通过被动的收集获取这些数据。相比之下，LAMP算法：①不需要对流量矩阵进行估计（流量需求）；②不发送任何探测的数据包；③中间路由器可以应对拥塞；④不需要反馈变量；⑤稳定。文献[15]中的Homeostasis方法是一种仅基于路由器本地信息从而在几条路径上进行负载均衡的自适应方法。与LAMP方法类似，这种方法不涉及主动探测或反馈变量，但是与LAMP算法相比，这种方法还存在着很大不足。首先，它根据传播延迟计算最短路径，这就需要每个路由器通告其传播延迟；其次仅使用本地信息不能检测出多准高负载?[? 负载流量非常接近相应的阈值，但是尚未达到阈值。]连接造成的拥塞；第三，安装LAMP的路由器在由于缺少多路径信息或严重堵塞从而不能缓解自身拥塞时，可以给其上游路由器发送一个信号，这是Homeostasis方法所不能的。

 

5 结论

    研究提出了一种在线实时的流量工程方法——LAMP. LAMP能够通过将流量从高利用率的链路转移到低利用率的链路（备用链路）以响应拥塞，即负载均衡。负载均衡的依据是被动方式测量的信息。LAMP解决了目前在线和离线TE方法中常见的几个问题。评估结果显示，LAMP能够有效降低链路利用率，具有良好的稳定性。而且LAMP选择的备用路径长度仅比最短路径略长，最后LAMP的通信开销与其他方法相比最小。

 

 

 

参考文献 (References)

[1] XIAO X, HANNAN A, BAILEY B, et al. Tra?c engineering with MPLS in the internet[J] IEEE Network, 2000, 14(2): 28-33.

[2] WANG H, XIE H, QIU L, et al. Cope: tra?c engineering in dynamic networks[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(4): 99-110.

[3] FORTZ B, REXFORD J, THORUP M. Tra?c engineering with traditional IP routing protocols[J]. IEEE Communications Magazine, 2002, 40(10): 118-124.

[4] 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.

[5] FORTZ B, THORUP M. Internet tra?c engineering by optimizing OSPF weights[C] IEEE. in Proceedings of IEEE INFOCOM, 特拉维夫,以色列，: IEEE, 2000: 519-528.

[6] FELDMANN A, GREENBERG A, LUND C, et al. Deriving tra?c demands for operational IP networks: methodology and experience[J]. IEEE/ACM Transactions on Networking(ToN), 2001, 9(3): 265-280.

[7] SRIDHARAN A, GU?ERIN R. Making IGP routing robust to link failures[C] Springer. Networking, Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems. 柏林，海德尔堡Springer, 2005: 634-646.

[8] XU D, CHIANG M, REXFORD J. DEFT: distributed exponentially-weighted ?ow splitting[C] IEEE. in Proceedings of IEEE INFOCOM. 安克雷奇,阿拉斯加,美国IEEE, 2007: 71-79.

[9] XU D, CHIANG M, REXFORD J. Link-state routing with hop-by-hop forwarding can achieve optimal tra?c engineering[J]. IEEE/ACM Transactions on Networking(TON), 2011, 19(6): 1717-1730.

[10] Roughan M, Greenberg A, Kalmanek C, et al. Experience in measuring backbone tra?c variability: models, metrics, measurements and meaning[C] ACM. In Proceedings of ACM SIGCOMM Workshop on Internet Measurment. 匹兹堡，费城，美国: ACM, 2002: 91-92.

[11] ROUGHAN M, THORUP M, ZHANG Y. Tra?c engineering with estimated tra?c matrices[C] ACM. In Proceedings of ACM SIGCOMM Conference on Internet Measurement. 迈阿密，佛罗里达，美国ACM, 2003: 248-258.

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

[13] ELWALID A, JIN C, LOW S, et al. MATE: MPLS adaptive tra?c engineering[C] IEEE. In Proceedings of IEEE INFOCOM. 安克雷奇，阿拉斯加，美国: IEEE, 2001: 1300-1309.

[14] FISCHER S, KAMMENHUBER N, FELDMANN A. REPLEX: dynamic tra?c engineering based n wardrop routing policies[C] ACM. In Proceedings of ACM CoNEXT. 里斯本，葡萄牙. ACM, 2006: 1-14.

[15] KVALBEIN A, DOVROLIS C, MUTHU C. Multipath load-adaptive routing: putting the emphasis on robustness and simplicity[C] IEEE. In Proceedings of IEEE International Conference on Network Protocols (ICNP). 普林斯顿，新泽西，美国: IEEE, 2009: 203-212.

[16] LIAO Y, GAO L, GUERIN R, et al. Reliable interdomain routing through multiple complementary routing processes[C] ACM. In Proceedings of ACM CoNEXT. 马德里，西班牙: ACM, 2008: 68-79.

[17] Kushman N, Kandula S, Katabi D, et al. R-BGP: staying connected in a connected world[C]// USENIX. In Proceedings of USENIX Symposium on Networked Systems Design & Implementation (NSDI). 坎布里奇，马萨诸塞，美国Cambridge, MA: USENIX. 2007: 341-354.

[18] XU W, REXFORD J. MIRO: multi-path interdomain routing[C] ACM. In Proceedings of ACM SIGCOMM. 比萨，意大利: ACM, 2006: 171-182.

[19] JIANG H, DOVROLIS C. Passive estimation of TCP round-trip times[J]. ACM SIGCOMM Computer Communication Review, 2002, 32(3): 75-88.

[20] VEAL B, LI K, LOWENTHAL D. New methods for passive estimation of TCP round-trip times[J]. Lecture Notes in Computer Science, 2005, 3431: 121-134.

[21] VILLAMIZAR C, SONG C. High performance TCP in ANSNET[J]. ACM SIGCOMM Computer Communication Review, 1994, 24(5): 45-60.

[22] MORRIS R. Scalable TCP congestion control[C] IEEE. In Proceedings of IEEE INFOCOM. 特拉维夫,以色列: IEEE, 2000: 1176-1183.

[23] MISRA V, GONG W B, TOWSLEY D. Fluid-based analysis of a network of aqm routers supporting TCP ?ows with an application to red[J]. ACM SIGCOMM Computer Communication Review, 2000, 30(4): 151-160.

[24] FLOYD S, FALL K. Promoting the use of end-to-end congestion control in the internet[J]. IEEE/ACM Transactions on Networking (TON), 1999, 7(4): 458-472.

[25] MAHAJAN R, FLOYD S, WETHERALL D. Controlling high-bandwidth ?ows at the congested router[C] IEEE. In Proceedings of IEEE International Conference on Network Protocols (ICNP). 河滨，加利福利亚，美国 IEEE, 2001: 192-201.

[26] ANDERSEN D, BALAKRISHNAN H, KAASHOEK F, et al. Resilient overlay networks[C] ACM. In Proceedings of ACM SOSP. 班夫，加拿大: ACM. 2001: 131-145.

[27] McKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. Open?ow: enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[28] ONF Market Education Committee. ONF white paper-software-de?ned networking:the new norm for networks， 2010， 访问日期：2014-07-19. [OL]. https://www.opennetworking.org/images/stories/downloads/sdn-resources/white-papers/wp-sdn-newnorm.pdf

[29] University of Washington, Rocketfuel. 西雅图，华盛顿州，美国，2002，访问日期：2014-07-19 [OL]. http://www.cs.washington.edu/research/networking/rocketfuel/

[30] ROUGHAN M. Simplifying the synthesis of internet tra?c matrices[J]. ACM SIGCOMM Computer Communication Review, 2005, 35(5): 93-96.

[31] BASAK D, KAUR H T, KALYANARAMAN S. Tra?c engineering techniques and algorithms for the internet[J]. Technical Report, Rensselear Polytechnic Institution, Tech. Rep, 2002.

[32] MOTIWALA M, ELMORE M, FEAMSTER N, et al. Path splicing[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(4): 27-38.

[33] FORTZ B, THORUP M, et al. Robust optimization of OSPF/IS-IS weights[C]//IFORS. In Proceedings of International Network Optimization Conference. 巴黎，法国: IFORS. 2003: 225-230.

[34] WANG H, ITO M R. Dynamics of load-sensitive adaptive routing//[C] IEEE. in Proceedings IEEE International Conference on Communications.迈阿密，佛罗里达，美国. IEEE, 2005: 213-217.

[35] KHANNA A, ZINKY J. The revised ARPANET routing metric[J]. ACM SIGCOMM Computer Communication Review, 1989, 19(4): 45-56.

[36] McQUILLAN J M, RICHER I, ROSEN E. The new routing algorithm for the ARPANET[J]. IEEE Transactions on Communications, 1980, 28(5): 711-719.