˖ڍመڙጲ
依据被动测量的链路负载均衡
戴惠辰 ，黎阳 ，卢建元 ，邰冬哲 ，刘斌
清华大学计算机科学与技术系，北京 邮编100084
摘要：
目前绝大多数的流量工程方法均离线操作，它们在小时或者更长的时间粒度上响应流量变化，
这对于实时网络应用（例如流媒体、VoIP、IPTV）是远远不够及时的。一些在线的流量工程
方法已经被提出以应对这一问题，但是这些方法均有缺陷，比如需要MPLS的支持、复杂的稳
定性机制、或者额外的探测包和广告包。本文提出LAMP——一种实时在线的流量工程方法在
多条路径之间实现负载均衡。LAMP把流量从高利用率的链路转移到低利用率的链路上，转移
的依据是以被动方式收集的信息，包括RTT和链路利用率。LAMP不需要周期性地探测网络，
不需要路由器之间的大量通信，更不需要对输入的流量和网络拓扑做任何假设。评估结果表
明LAMP能够有效降低链路利用率，而且具有良好的稳定性。
关键词：计算机网络；在线流量工程；被动测量；多路径路由；负载均衡
中图分类号：
LAMP: Load Adaptation based on Measuring
Passively
Huichen Dai , Yang Li , Jianyuan Lu , Dongzhe Tai , Bin Liu
Department of Computer Science and Technology, Tsinghua University, Beijing 100084
Abstract:
The majority of current Tra�c Engineering (TE) methods operate o�ine, they respond to
changes in tra�c demands at the timescale of hours or even longer. Obviously, it is too late
for real time applications, such as such as Streaming Media, VoIP and IPTV. Some online TE
methods have been proposed to address this problem, but they all share some common
vulnerabilities, . requirement of MPLS support, complicated mechanisms for stability, or
requirement of extra probing and advertising packets. Faced with these issues, we propose
LAPM { an online TE method that balances the load among multiple paths according to the
information (Round Trip Time and link utilization) passively collected. LAMP alleviates
congestions by shifting the overspill tra�c from over-utilized links to low-utilized links, but it
does not need to periodically probe the network or require excessive communications between
基金项目： 教育部博士点基金(20100002110051)
作者简介： 戴惠辰（1988-），男，博士研究生，主要研究方向：路由器体系结构，信息中心网络，流量工
程。Email: dhc10@。黎阳（1989-），男，博士研究生，主要研究方向：网络测量，软件定义
网络。Email: liyang-12@。卢建元（1988-），男，博士研究生，主要研究方向：路由器体系结
构。Email: lu-jy11@。邰冬哲（1990-），男，硕士研究生，主要研究方向：路由查找。Email:
tdz09@ 通信作者：刘斌（1964-），男，教授，博士生导师，主要研究方向：高性能交换机和路由器，
网络处理器，信息中心网络，流量测量，网络安全和节能。
- 1 -
˖ڍመڙጲ
routers, nor does it make any assumption on input tra�c (Tra�c Matrix) and network
topology. Moreover, it does not need MPLS support and can be implemented over existing
routing protocols. Evaluation results show that LAMP can e�ectively reduce link utilizations,
and meanwhile maintain favourable stability.
Key words: Computer Networks; Online Tra�c Engineering; Passive Measuring; Multipath
Routing; Load Balance
0 引言
网络服务提供商（ISP）总是希望能够最大化地利用现有设施以最大化其利润，这触发了
大量研究来最优化路由系统。（路由系统负载把数据包从源点传递到终点。）这些工作就是流量
工程，流量工程通过分析、预测和调节在网络上传播的数据来优化网络的性能。一般地，流量
工程可以形式化地表述为最小化网络的最大利用率问题。
一般地，流量工程方法均离线操作，这意味着这些方法均衡的是在长时间粒度上平均的流
量，时间粒度可能会达到多个小时，甚至几周或者几个月。截至目前，各种各样的流量工程方
法被提出，其中最流行的方法往往需要采用MPLS隧道 [1]，或者采用优化的域内路由协议链路
权值 [2, 3, 4, 5, 6]。同时，很多其他方法 [1, 4, 5, 7, 8, 9] 致力于求解最小化链路的最大利用里
这一问题，这些方法一般假设流量矩阵是已知的。但是在实际中，流量矩阵已经被证明是难以
测量的 [10, 11]。
虽然离线流量工程的作用非常明显，但是目前互联网上的应用，例如流媒体、VoIP、
IPTV以及分布式的游戏给路由带来了更加严峻的考验。在长时间粒度上达到良好的平均性能
已经不够了，路由器应当检测并相应网络中的拥塞。为了提供更佳的用户体验，ISP迫切需要
路由器能够自动把流量切换到状况更好的路径上。而且，离线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] and REPLEX [14]）；
4. 需要周期性地向网络中发出探测包以测量反馈变量的值，这会向网络中注入大量的额外
流量，而且会在在拥塞时注入更多（MATE [13], TeXCP [12] and REPLEX [14]）；或者，
广播新的链路权值供路由协议重新进行最短路径计算（Homeostasis [15]）；
- 2 -
˖ڍመڙጲ
5. 为了过分追求简单性而放弃性能的提升（Homeostasis [15]）；
6. 只有流量的入口路由器才能响应网络拥塞（MATE [13], TeXCP [12] and REPLEX [14]），
路径上中间其他的路由器则不可以；
为了解决这些问题，本文提出了在线TE方法LAMP（Load Adaptation based on Measur-
ing Passively），该方法利用到达每个终点的多条权值非相等路径，自适应地把流量分配到这些
路径上。分配的依据是被动收集的信息——RTT和链路利用率。所以，LAMP方法的关键组成
部分有：多路径路由、拥塞检测以及负载均衡。多路径路由的前提条件是多路径的存在，所以
我们的首要任务是丰富路径的多样性。
在域内（intra-domain），我们采用和域内路由协议（比如OSPF，ISIS）相同的链路权
值来计算前N条最短路径，然后为路由表中的每一个终点1安装至多N个下一跳节点。这样，
LAMP无需路由器交换额外的链路权值，因而可以无缝地在现有的域内路由协议上运行。在阈
间（inter-domain），由于实际上的阈间路由协议BGP为每一个终点只会挑选和发布一条路径，
因此BGP的路径多样性很差。然后幸运的是，许多研究已经展开了对BGP的研究和扩展，并
且丰富了BGP的路径多样性，例如Dual-BGP [16], R-BGP [17]以及MIRO [18]。
LAMP采用两个度量——RTT和链路利用率——来进行拥塞检测，因为这两个度量非常重
要而且易于获得。RTT可以采用 [19, 20]提出的完全被动的方式来测量，不需要向网络中注入
任何流量。链路的利用率可以被与其连接的路由器直接测量，也不需要任何额外的数据包。
当RTT增长过快或者链路利用率过高时，我们认为拥塞出现。一旦某个路由器检测到了拥塞，
该路由器把流量从高利用率的链路转移到低利用率的链路以缓解或者消除拥塞。为了避免同一
个流内的数据包重排序，我们在重新分配流量时以流2作为单位。
与MATE、TeXCP和REPLEX不同的是，LAMP不但允许流量的入口路由器相应拥塞，也
允许路径上的其他路由器相应拥塞。如果某一个路由器不具备多路径信息，或者拥塞太严重以
至于它不能缓解，改路由器将通知它的上游邻居路由器减少转发给它的流量。而且，LAMP不
对输入的流量和拓扑做任何假设，在输入流量和拓扑发生改变的情况下LAMP也不会出现抖
动。
总之，LAMP通过多条路径之间的负载均衡同时降低链路利用率和延时，而且具有良好的
稳定性。特别地，本文拥有以下创新点：
1. 我们提出了LAMP——一种简单有效的在线TE方法，该方法利用被动测量的信息在多条
路径之间进行负载均衡；
2. LAMP能够运行在现有的路由协议之上；
3. LAMP不采用反馈变量，因而不需要周期性的探测包或者复杂的机制来维持稳定性；
4. LAMP在必要时会把拥塞情况通知上游的邻居路由器；评估结果表明和现有的在线TE方
法相比，LAMP拥有更佳的性能更低的代价。
1一般地，在路由表中的一个IP前缀代表一个终点。
2一个流由五元组定义: <源IP地址，源端口，目的IP地址，目的端口，协议号>。
- 3 -
˖ڍመڙጲ
本文的结构如下：第1章简单介绍LAMP的基本思想，第2章阐述LAMP的详细设计，第3章
评估LAMP并和其他TE方案进行比较。第4章调研了相关工作，第5章进行总结。
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或者链路利用率当作了反馈变量（例
如[14, 12]把延时当作反馈变量），而反馈变量的使用非常容易导致抖动的发生。考虑以下情
形：两条链路a和b被用于负载均衡，延时d被用作反馈变量。当路径a上的延时da很长时，一
部分流量被转移到路径b上，随即da下降db上升。因而，流量又会从路径b 转移到路径a上，这
- 4 -
˖ڍመڙጲ
A B C D E
I J
F G
H
congested link
detour
congested link
signaling
packet
图 1: LAMP简单示例.
又会导致da升高db降低，如此反复。这是一个简单但是典型的由于反馈变量存在而导致抖动
的例子。[14, 12]面临着这种抖动，因此一些复杂的机制被引入以解决抖动问题，例如[14]中
的Wardrop和[12]中的XCP。由于LAMP不适用反馈变量，因而从根本上杜绝了抖动问题的发
生。
一个应用LAMP的简单例子如图1所示，其中每一台路由器都运行LAMP。节点A和H两者
都向节点E发送流量，路径分别为A ! B ! C ! D ! E 和H ! I ! C ! D ! E。在本
例中，路径E A与A E，以及E H 与H E是对称的（并不是严格要求）。假设链
路<C;D> 上出现了拥塞（原因可能是<C;D>的带宽不够或者流量太大），那么路由器C利用
经过C的流量测量的RTT会增加，链路利用率也会升高。因而，路由器C检测到了拥塞，然后
通过把链路<C;D>上的流量往链路C ! G! E上转移以实现流量均衡。这样，拥塞被缓解甚
至消除。
我们接着假设链路<C;D>上的拥塞非常严重以至于路由器C的出口链路（链路<C;D>
和<C;G>）在进行了流量均衡之后利用率依然超过了阈值。在这种情况下，路由器C通知上
一跳的邻居路由器B和I（如图1中的箭头所示），然后路由器B也开始进行负载均衡，以此类
推。
如果拥塞是由于一条路径上的多条链路流量负载很高，但是利用率均未超过阈值，此
时LAMP设定只有流量的入口路由器可以响应拥塞，因为只有入口路由器可以把流量导入一条
完全不同的路径。
最后，LAMP适用于域内和域间环境，图1所示的环境既可以是域内的，也可以是域间
的。
2 LAMP详细设计
本章将详细阐述LAMP设计，首先介绍的是测量RTT的被动方法，然后我们描述LAMP的
关键功能：拥塞检测、多路径路由和负载均衡。
被动测量RTT的方法
被动测量RTT的方法在[19, 20]中提出，并且被证明可行。本文直接利用这种方法来计
算RTT，而不用关心路由是否对称。此前，RTT已经有了很广泛的用途，包括：1）为一条链
路上分配的缓存取决于该链路上TCP连接的RTT[21, 22]；2）RTT的估算有利于活跃队列的管
理 [23]; 3）RTT能够帮助判定由于拥塞引起的无响应[24, 25]。
- 5 -
˖ڍመڙጲ
SYN
ACK
SYN
-ACK
Caller Callee
RTT
Router
packets seen by the router
packets not seen by the router
time time
(a) 被 动RTT测 量： SYN-
ACK（SA）方法。
SYN
ACK
SYN-
ACK
Caller CalleeRouter
packets seen by the router
packets not seen by the router
time time
Request
Data
RTT
Data
1st bu
rst
2nd b
urst
ACK
(b) 被动RTT测量：慢启动方
法（SS）。
图 2: 路由器上的RTT被动测量.
下面我们简述[19]提出的被动测量RTT的方法。最基本的技术包括SYN-ACK（SA）测量
和Slow-Start（SS）测量，分别在图2(a)和图2(b)3中所示。由于非对称路由的普遍存在，一台
路由器很有可能只看到两台主机之间的单向流，可能是从发起方到接收方，或者从接收方到发
起方。SA测量方法适用于前者，SS测量方法适用于后者。
在发起方到接收方的流中，SA方法利用三次握手交换的包完成对RTT的测量。基本想法
是测量最后一个SYN包和第一个ACK包之间的时间差，这个时间差就是RTT，如图2(a)所示。
SS方法测量的是从接收方到发起方的流，基本想法是第一个和第二个流量突发之间的时间差
与RTT非常接近，如图2(b))所示。
拥塞检测
RTT被测量出来之后，我们利用RTT和链路利用率（链路利用率可以由路由器直接获得）
来检测拥塞。首先我们定义本文中的拥塞：如果某条路径上的一条或者几跳链路的利用率超过
了预先设定的阈值�，或者该路径上的RTT的增长也超过了预先设定的阈值�，那么这一条路
径是拥塞的。
对一台路由器而言，同一时刻有大量的TCP流经过该路由器，那么该路由器可以利用上
述的测量RTT的方法来测量RTT。用X表示RTT的值，X(t; f)表示流f在t时刻的RTT。我们
根据下一跳的不同把RTT分组，相同的下一跳分在同一组。因此X也应当把下一跳作为一个
参数，那么我们得到X(t; f; h)，这表示流f在时刻t下一跳为h时的RTT。虽然下一跳h可以由
流f查路由表获得，为了清楚起见，这里我们仍然把h作为X 的一个参数。
对于下一跳为h的流f来说，在t1时刻我们可以测量其RTT，用X(ti; f; h)表示。这样，
流f在不同时刻的一系列RTT可以用X(t0; f; h); � � �; X(ti�1; f; h); X(ti; f; h); X(ti+1; f; h); � � �来
表示。我们希望利用RTT的增长率来检测拥塞，而计算RTT增长率由两种方法：
3我们从[19] 中引用了这两幅图。
- 6 -
˖ڍመڙጲ
1.首先计算每个流的RTT增长率，然后为每个“下一跳”计算平均RTT增长率。流f的RTT增
长率为：
rf =
�X
X
=
X(ti; f; h)�X(ti�1; f; h)
X(ti�1; f; h)
(1)
所以下一跳h在ti时刻RTT的平均增长率为：
Rh = E(rf ) = E[
X(ti; f; h)�X(ti�1; f; h)
X(ti�1; f; h)
] (2)
其中所有的流f都有相同的下一跳h。
2. First calculate the average RTT increment of each next-hop, then the average incre-
mental ratio of each next-hop. For each next-hop h, the average incremental ratio of RTT at
time ti is:
2.首先计算每个下一跳的平均RTT增长值，然后计算每个下一跳的平均增长率。对于一个
下一跳h，在t1时刻其平均RTT增长率为：
Rh =
E[X(ti; f; h)]� E[X(ti�1; f; h)]
E[X(ti�1; f; h)]
(3)
其中所有的流f都有相同的下一跳h。
如上文所述，判断拥塞的条件是：Rh > � jj �h > �。（�h是下一跳链路的利用率。）该表
达式的“或”操作的对象是两个不等式，这两个不等式任意一个为“真”都可以判断拥塞的存
在，而不用关心另一个不等式的值。但是，单独任意一个不等式在有些情况下并不能检测到拥
塞的存在。例如Rh > �可以指出输出链路上的拥塞，但是不能检测出由路径上多条相对负载较
重的链路造成的拥塞（这些链路的利用率均未超过阈值）。实际上，这种情况可以由�h > �来
预测，但是该不等式不能指出拥塞发生的地点。所以我们需要把二者结合起来以做出更准确的
拥塞检测。
需要指出的是，虽然我们一再使用“流f的RTT”这样的表达方式，但是RTT只有对
于TCP连接是有意义的。但是，由于RTT的测量方法只能观察到TCP连接的一个单向流，从发
起方到接受方，或者从接收方到发起方。所以，为了表述的简单，我们虽然说“流f的RTT”，
但是实际表达的是该RTT 属于某一个TCP连接，而且f是该连接的一个单向流。
在三种情况下表达式Rh > �jj�h > �的值为“真”：
1）仅Rh > �为“真”；
2）仅�h > �为“真”；
3）Rh > �和�h > �均为“真”。
对于情形1）来说，路由器能够检测到拥塞，但是不知道拥塞具体发生在哪条链路上，甚
至是由于一条链路上的多条负载较重的链路造成的（这些链路的利用率均未超过阈值）。所以，
如果该路由器是流量的入口路由器，那么负载均衡操作就被触发，否则该路由器不进行任何操
作。对于情形2）和3）来说，与该路由器直接连接的链路发生了拥塞，针对该链路的下一跳进
行负载均衡。如果拥塞很严重该路由器不能有效缓解，那么该路由器将通知上游的邻居路由器
以减少向该路由器转发的流量，以此类推。
- 7 -
˖ڍመڙጲ
多路径路由
“多路径”的意思是在源点和终点之间有多余一条的路径，多路径是负载均衡的关键因
素。在域内，OSPF已经支持相等权值的多路径路由（Equal-Cost Multi-Path），但我们在本文
中寻求除此以外的多路径。实现多路径的方法是不限定流量一定在最短路径上转发。目前部署
最广泛的域内路由协议OSPF维护域内的完整拓扑结构。依据拓扑结构和OSPF链路权值的度
量，我们可以计算出源点和终点之间的所有路径，从最短路径到最长路径。但是，我们并不需
要所有的路径，在LAMP中，每台路由器为每个终点安装至多N个下一跳，对应前N条最短路
径。
一种简单的计算至多N个下一跳的方法是：只向离终点更近的节点发送流量。如果向距
离终点更远的节点发送流量有可能会导致路径回环。我们定义节点i和j之间的距离为i和j之间
最短路径的长度，用d(i; j)来表示。假设节点k是节点i的邻居，如果d(i; j) > d(k; j)，那么k就
是i到j的一个可行的下一跳。（由于我们采用和OSPF相同的路径权值度量，我们不需要路由器
之间额外的信息交换，因而也不需要向网络中注入额外的流量。）
应当指出的是，即使i和j之间存在N条物理链路，有非常大的可能性源点i不能找到终
点j找到N个下一跳，因为有些下一跳对应的路径的长度比当前节点距离终点的路径要长。一
个极端的例子是距离终点（假设终点是t）最近的邻居节点（假设该节点是s），由于没有邻居
节点比s更和终点t接近了，节点s只有一个下一跳到终点t，其实就是终点t本身。
最常用的域间路由协议是BGP，由于BGP只选择并传播单条路径，BGP的多路径特征
很差。幸运的是，已经有非常多的工作对BGP的多路径特性进行了研究并且达到了更佳
的BGP多路径属性，例如Dual-BGP[16]，R-BGP[17]和MIRO[18]等等。我们直接利用这些工
作来更加便捷地寻找域间的多路径。
流量均衡
截至目前，我们已经描述了检测拥塞和增加路径多样性的方法。本小节将介绍负载均衡方
法。RON[26]已经证明了通过把流量导入其他路径可以有效缓解甚至消除拥塞。但是何时转移
流量以及向哪条链路上转移流量这些问题并没有被很好地解决，下面我们针对这些问题提出解
决方案。
目前的路由协议对数据平面是拥塞是无感知的，只会对网络拓扑的变化做出相应。在我们
的解决方案中，路由器能够感知数据平面的拥塞并能够通过负载均衡缓解这一问题，延时也能
够同时降低。而且为了避免TCP包重排序问题，我们以流为粒度进行负载均衡。
负载均衡策略
一般地，拥有相同终点的流都会选择同一条路径——最短路径，我们称之为主路径。剩余
的N � 1条路径被称为备用路径。在LAMP的负载均衡策略中，N条路径的地位不是平等的，
基本的思路是：主路径拥有最高的优先级，只要主路径的下一跳链路利用率低于阈值�，我们
会仅使用主路径。一旦主路径的下一跳链路利用率高于�，流量就会在剩余的N � 1条备用路径
- 8 -
˖ڍመڙጲ
上负载均衡。这N条路径是根据OSPF的路径权值计算出来的，在负载均衡时它们的排序依据
它们对应的下一跳链路的利用率。利用率越低，排名越靠前。下文将述及，我们还会依据这个
排序选择负载均衡的链路。
我们之所以把链路利用率作为对下一跳排序的依据，是因为当我们进行负载均衡时，我们
希望能够降低由于排队和拥塞造成的延时（以及丢包率）。当链路利用率低于阈值时，包队列
很短所以排队时延可以忽略不计。但是一旦链路利用率超过阈值，包队列的长度快速增加因而
时延也迅速增加。所以，在选择下一跳进行流量均衡时，我们优先选择低利用率的链路，这意
味着此时这条链路上是没有拥塞的。
负载均衡是由路由器进行的，现在已有多种经典的负载均衡的方法，例如平均分配
（EqualSplit），最轻负载（LeastLoaded），按序选择（LoadOrder）等等。在本文中，我们也提
出流量均衡的方法：按权值分配（WeightedSplit），然后把该方法和经典的方法进行比较。
1. 平均分配（EqualSplit）：在所有的备用链路上平均分配超出阈值的流量；
2. 最轻负载（LeastLoaded）：把超出阈值的流量全部转移到负载最轻的下一跳链路上；
3. 按序选择（LoadOrder）：先把超出阈值的流量全部转移到负载最轻的下一跳链路上，如
果该链路因为转移来的流量其利用率超过阈值�，此时负载第二轻的备用路径成为了负载
最轻的路径，那么继续把超出阈值�的流量转移到负载最轻的路径上，如此反复。
4. 按权值分配（WeightedSplit）：超出阈值的流量被分配到所有的备用链路上，每条路径分
配到的流量与其当前的链路利用率成负相关。
LAMP采用了按权值分配（WeightedSplit）的方法，所有的这些负载均衡方法都会这
第3章中被评估和比较。
通知上一跳邻居路由器
如果某路由器不能缓解拥塞，原因可能是该路由器不包含某个终点的多路径信息，或者是
所有的备用路径也都超过它们的利用率阈值了。此时，LAMP允许路由器通知上游的邻居路由
器，然后上游路由器就可以也通过负载均衡减少发往该路由器的流量。该方法在多路径信息缺
乏或者负载很高的路由器上很有效，我们将在第3章中评估该方法。
以流为单位进行操作
我们希望极力避免同一个流的包被转发到多条路径上，因为这会导致TCP包的重排序，并
触发TCP慢启动算法，这将严重影响TCP的性能。很多方法都被提出以保证同一个流的包被
转发到相同的下一跳，例如哈希方法（hashing）。
随着OpenFlow[27]和SDN[28]的提出，这一问题有了更好的解决方法。OpenFlow[27]和SDN[28]均
以流为单位进行操作。由于OpenFlow/SDN 交换机具有可编程性，我们可以通过编程定义我
们自己对流的操作。伴随着OpenFlow/SDN 交换机带来的增强的流操作性能，我们的负载均
衡方案会有得到强劲的支持（但OpenFlow/SDN 交换机并不是LAMP必须使用的设备）。
- 9 -
˖ڍመڙጲ
稳定性
网络流量在多条路径之间来回切换被称为抖动，抖动的存在会减弱网络的稳定性。同时稳
定性也是任何一个TE方法都必须面对的问题。在TE中，稳定性被严格地定义为：在输入流量
稳定的情况下，每条链路上的流量渐近地收敛至稳定速率。
LAMP拥有非常好的稳定性，因为LAMP不需要自适应任何反馈变量，比如路径的利用
率4，延时以及权值。自适应这些变量需要负载的机制来保证稳定性。LAMP仅仅在数据平面
根据链路的利用率进行负载均衡，这一操作不涉及任何反馈变量，因而能够保证控制平面的稳
定性。
3 评估
在本章，我们评估了LAMP算法的性能并且与其他流量工程算法进行了比较。评估方法是
我们首先验证了被动RTT测量方法的有效性。之后，我们给定一个拓扑和流量矩阵，测量在
没有使用流量工程的情况下LAMP算法的链路利用率。然后，我们比较了在使用了负载均衡方
法但是没有和上游邻居节点通信的情况下，如Homeostasis [15]，LAMP算法的性能提升。我
们也算出了LAMP算法的路径拉伸 （在下文定义）。实验中使用的拓扑是EBONE（AS1755）
的Rocketfuel [29]，包括172个路由器和763个边缘；流量矩阵遵照重力模型[30]来生成。我们实
验中的RTT增量阈值和链路利用率阈值被分别设置为和。每个路由器为每个终点设置有
至多N=5个下一跳。
评估结果
RTT测量
为了测量RTT时间，我们从中国教育科研网（CERNET）捕获了一个5分钟的trace，然
后利用被动测量方法测量了RTT的值。因为我们的trace是在一个网关处取得，我们也可以利
用传统方法来测量RTT时间，例如：在三次握手过程中，匹配TCP SYN包和SYN ACK包。
进一步，我们通过对比两种方法的结果来验证被动RTT测量方法的准确性。我们定义RTT比
值为RTTc/RTTp，其中RTTc表示传统测量方法的RTT测量结果，RTTp表示被动测量方法
的RTT测量结果。图3展示了每个流利用两种方法测得的RTT比值。RTT比值被按照递增来排
列，明显结果都在附近，这表明两种RTT测量方法结果非常接近。
使用/未使用负载均衡的链路利用率分布
我们通过比较在使用和未使用LAMP算法的情况下EBONE（AS1755）的Rocketfuel拓扑
结构中所有链路的链路利用率的分布来评估LAMP算法的有效性和性能。结果如图6所示。当
没有采用负载均衡算法时，对应的曲线表明40衡算法时相比，LAMP将流量从高利用率链路
转移到了低利用率链路。并且LAMP比其他负载均衡算法性能更好，它能够将流量在多条链
4路径的利用率被定义为路径上所有链路中的最高利用率[12, 14]。
- 10 -
˖ڍመڙጲ
0 100 200 300 400 500 600 700 800 900 1000 1100 1200
R
T
T
r
a
ti
o
# of flows
图 3: 传统方法和被动方法测得
的RTT之间的比值。
P
a
th
S
tr
e
tc
h
TM
Path Stretch
图 4: 路径拉伸。
0
2
4
6
8
10
12
A
c
c
u
m
u
la
te
d
L
o
a
d
A
d
a
p
ta
ti
o
n
T
im
e
s
Average Relative Input Load
Accumulated Load Adaptation Times
图 5: 抖动
路上更均匀的分配。因此，LAMP算法使用了更多的链路，并且每条链路的利用率都更低。
值得指出的是这些图中，链路利用率会超过1，这是因为我们在每一轮负载均衡之前收集链
路利用率信息。这之后，某条链路上溢出的流量会被负载均衡器分配到多条链路上（当前链
路也被包括在内）。如果在负载均衡后链路利用率仍然超过1，多出的流量会被丢弃。我们采
用了这种统计学方法来更好的反应负载均衡算法的性能。并且我们能看到，链路的负载越高
（TM=�），当LAMP未使用时利用率超过1的链路越多。
加入与上游邻居节点通信后的性能
随后，我们通过计算与仅使用本地负载均衡的情况，如Homeostasis，相比链路利用率的
减少，来测量加入与上游邻居节点通信后的性能。在不同TM下减少的链路利用率的分布如
图7所示，其中注意负值表示链路利用率增加。这些图指出，在通信机制被加入后，利用率
在60利用率增大了。链路利用率增大的原因是邻居路由器在负载均衡过程中将一些流量迁移到
了链路利用率较低的链路。因此，与上游邻居节点通信这个机制确实能够均衡流量并且降低链
路利用率。根据图7，我们能够进一步得出按权值分配负载均衡方法实现的链路利用率降低幅
度不是最大的。这是因为按权值分配方法在甚至不使用与上游邻居节点通信机制的情况下，也
能取得很好的性能；当通信机制被采用后，这种方法的性能提升空间比其他方法更小。
链路拉伸
我们定义链路拉伸为备用路径和最短路径之比。显而易见地，把流量分割到备用路径会导
致分组沿着非最短路径传输。流量拉伸被用来反映与最短路径相比，备用路径更长了多少，如
图4所示。曲线表明备用路径仅仅比最短路径长一点。直观地，链路拉伸应该随着TM增大而增
大。然而，因为TM遵循重力模型，对于同一个TM负载，每一条链路的利用率都不同。因此，
负载均衡器表现得不同，导致了链路拉伸值的抖动。
抖动
我们测量了我们的按权值分配算法的调整次数。如前面多次提到的，LAMP没有任何的反
馈变量，因此它面对流量抖动十分的稳定。图5表示了没有反馈变量，当TM负载增加时的调整
时间。这表明了LAMP十分的稳定，因为LAMP算法在负载增大时只对负载进行一定次数的均
- 11 -
˖ڍመڙጲ
0 1 2 3 4 50
1
Link Utilization
CD
F
Without Load−Balance
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(a) TM=
0 1 2 3 4 50
1
Link Utilization
CD
F
Without Load−Balance
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(b) TM=
0 1 2 3 4 50
1
Link Utilization
CD
F
Without Load−Balance
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(c) TM=
0 1 2 3 4 5 60
1
Link Utilization
CD
F
Without Load−Balance
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(d) TM=
0 1 2 3 4 50
1
Link Utilization
CD
F
Without Load−Balance
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(e) TM=
0 1 2 3 4 5 60
1
Link Utilization
CD
F
Without Load−Balance
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(f) TM=
图 6: 在不同的TM下，不同的负载均衡方法达到的链路利用率分布。
衡，并且流量从来不会在一系列下一跳链路间来回切换。注意到X轴是平均相对输入，表示每
一条链路上的负载会变化，并且一些链路会触发负载均衡过程。
通信开销
最后，我们通过测量用于探测和信息交换的通信分组个数来评估LAMP算法和其他方法的
通信开销。如表5所示，LAMP算法的开销最低，并且那些通信分组都被用来与上游邻居路由
器通信。Homeostasis 的开销来源于每个路由器通过泛洪来得到路由器之间的距离（通过传输
时延来表示）；而REPLEX和TeXCPA算法只须在每对节点之间进行一轮的探针分组发送。所
有这些方法的通信分组开销都是利用Rocketfuel网络拓扑测量得到的。
表 1: 通信开销
TE方法 LAMP Homeostasis REPLEX&TeXCP
包的数量 14,983 233,060 58,824
4 相关工作
当前，关于流量工程的论文已发表多篇，诸如[1, 2, 3, 5, 13, 31]，在这里我们无法详尽的
列出所有相关文章。下面，我们调研一些比较著名的工作，然后将我们的工作与其进行了详细
的比较。
- 12 -
˖ڍመڙጲ
− 0 10
1
Traffic Load
CD
F
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(a) TM=
− 0 1
1
Traffic Load
CD
F
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(b) TM=
−1 − 0 1
1
Traffic Load
CD
F
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(c) TM=
−1 − 0 1 20
1
Traffic Load
CD
F
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(d) TM=
−1 − 0 1
1
Traffic Load
CD
F
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(e) TM=
− 0 1 20
1
Traffic Load
CD
F
EqualSplit
LoadOrder
LeastLoaded
WeightedSplit (LAMP)
(f) TM=
图 7: 由于通知上游邻居路由器而降低的链路利用率的分布。
流量工程（TE）通过对网络进行分析、预测、并规范网络数据传输的行为来优化网络性
能。具体的来说，流量工程的目标就是利用有限的可用资源路由尽可能多的数据流量。一般来
讲，流量工程的方法一般都是基于离线数据的，即这些流量数据一般都是通过提前在网络当中
进行一段时间的监测得到的，测量的时间规模一般为几个小时，有的时候规模可能达到几周或
者几个月。然后，通过对中心点的数据结果进行观察和分析，从而得出结论。这里的中心点指
的是流量工程方法（如负载均衡及流量重新路由等等）发挥作用的节点、路由策略被调整的节
点（例如为了计算最短路径而对OSPF/ISIS的链路权重进行重新计算等等）、以及MPLS隧道
被应用的节点。然后，流量工程的机制以及调整之后的路由策略将会一直在网络当中运行，直
至TE被重新启动，或者路由发生故障。这些流量工程机制对于运营商解决长期变化的流量需
求（如昼夜变化）有很大的意义。
TE不可能与多路径的负载平衡相分离，因为其进行的前提就是具有多路径的信息。文
章[32]当中提出了一种全新的原始路由方案，名字叫做路径拼接（Path Splicing），这种方法
能够为域内路由或者域间路由提供大量的可选路径。文章[16]当中提出了DualBGP方法，这
种方法在同一台路由器上面运行多个BGP实例，然后通过计算这几个不同的实例计算出互补
的BGP路径。另外一种解决方案是文章[17]当中所介绍的R-BGP方案。R-BGP方法通过提前计
算几个故障转移路径来保证在BGP收敛情况下，只要一个域与目的地点之间存在策略标准路
径，那么这个域就不会和任意的目的地址失去连接。文章[18]当中的MIRO算法则提出了一种
多路径域间路由协议。在这种方法当中，路由器通过存在的BGP协议来获取默认的路由路径，
这样任意的连个域就可以通过协商来利用它们所需要的路径。上面这些方法我们都可以加以
利用，从而增强域间路径的多样性。流量工程往往需要根据给定的预计流量矩阵来优化路由流
- 13 -
˖ڍመڙጲ
量。我们可以通过直接或者间接的方法来获取流量矩阵。在流级别的数据测量是可以直接进行
的情况下，我们可以通过[6]当中的方法直接测量准确的流量矩阵。然而，这种准确测量方法对
于基础设施有着较高的要求，高昂的成本使其不可能大规模的部署。当直接测量不可行的时
候，我们还可以通过间接的数据（例如链路的测量数据）估测出来相应的流量矩阵。但是这种
方法面临着很多挑战[10]，而且这种估计方法也可能会造成错误[11]。正如上文所述，一些早期
的TE方案通过动态的调整计算最短路径时的链路权重来适应负载的变化[4, 5, 7, 8, 9, 33, 34]。
然而，单个链路的权重调整将会导致最短路径的重新计算，而且相应的路由协议必须再次进行
收敛。在收敛的过程当中则可能会造成路由环路以及数据包丢失，从而导致服务质量下降。而
且，改变链路的权重也很有可能影响BGP路由的稳定性，因为BGP路径的选择由链路权重和
策略共同影响，因此对于链路权重的改变必须十分谨慎。显而易见，每几个小时运行一次的离
线方式不能很好的应对实时网络当中的流量突发。流量的突然变化可能有很多原因，例如突发
访问、BGP重新路由以及昼夜流量流动。此外，当前的TE通过预先计算替代路径来应对网络
故障，但是这种处理方法仅仅适用于部分网络故障集合。尽管网络本身提供了足够的容量来处
理拥塞，在处理集合之外的不可预计的拥塞上面，这种方法可能不会有效果。
研究人员已经意识到了离线TE机制缺陷。为了弥补这些缺陷，一些基于在线的TE方法
被广泛的提出[12, 13, 14]。这些方法可以应用于基于当前网络架构的实时流量工程当中，这
些在线的流量工程可以很好的应对流量需求的实时变化。事实上，在线TE的思想并不是最
近才出现的，这种思想可以追溯到最初的Arpanet。最早的负载自适应路由策略在Arpanet当
中就已经得到应用[35, 36]，但是后来由于分布式路由器的决策冲突导致震荡，这些方法
被证明在稳定性和性能上都有一定的缺陷。类似于MATE[13]、REPLEX[14]、TeXCP[12]以
及Homeostasis[15]等方法，我们提出的LAMP方法也是一个基于在线方式的TE方法，下面我
们将会对LAMP方法和其他的方法进行比较。[12, 13, 14, 15]这四种方法都是基于一些实时的
反馈数据、利用输入和输出节点之间的多路径来平衡负载。它们通过利用网络当中的可选路
径，并调整同一输入输出节点之间不同路径的流量分布来优化整个网络的利用率，但是这些方
法都面临着各种问题。
1）MATE以及TeXCP两种方法当中显示路由的进行都需要多标签协议转换（MPLS）的
支持，因此也就只能在MPLS网络当中进行应用。然而很多的网络运营商并没有使用MPLS，
同时，通过自治域边界的MPLS路径也面临着很多已知问题，因此它们的使用范围受到了很大
的限制。LAMP方法则没有在网络的路由架构上面作出假设，因此LAMP可以部署在现有的域
内以及域间路由协议上面。
2）MATE[13]，REPLEX[14]以及TeXCP[12]都遵循以下的规则：首先，一个负载平衡器
测量网络的状态（延迟和路径利用率）并把测量的结果当做反馈变量来处理；其次，负载平衡
器将流量从一个链路转移到另外一个链路上面，尽量减少链路利用率；第三，只有入口节点的
路由器可以进行负载自适应，而路径上的中间路由器则不可以；最后，反馈变量是入口路由器
通过周期性的发送试探数据包获得的，这一周期的大小很难确定。同时，也正是由于反馈变量
的存在，这一系统有着强烈的震荡趋势，因此必须采取一些复杂的措施来避免震荡。
3）MATE方法还假设存路由器知道网络的整体数据，而LAMP方法只是通过被动的收集
- 14 -
˖ڍመڙጲ
来获取这些数据。相比之下，LAMP算法：a）不需要对流量矩阵进行估计（流量需求），b）
不发送任何探测的数据包，c）中间路由器可以应对拥塞，d）不需要反馈变量，e）稳定。
文章[15]当中的Homeostasis方法是一种仅仅基于路由器本地信息从而在几条路径上进行
负载均衡的自适应方法。与LAMP方法类似，这种方法不涉及主动探测或反馈变量，但是
与LAMP算法相比，这种方法还是存在着很大的不足。首先，它根据传播延迟来计算最短路
径，这就需要每个路由器通告其传播延迟；其次仅仅使用本地信息不能检测出多准高负载5 连
接造成的拥塞；第三，安装LAMP的路由器在由于缺少多路径信息或严重堵塞从而不能缓解自
身拥塞的时候，可以给其上游路由器发送一个信号，这是Homeostasis方法所不能的。
5 结论
本文提出了一种在线实时的流量工程方法——LAMP。LAMP能够通过把流量从高利用率
的链路转移到低利用率的链路（备用链路）上来响应拥塞，即负载均衡。负载均衡的依据是被
动方式测量的信息。LAMP解决了在目前的在线和离线流量工程方法中常见的几个问题。评估
结果显示，LAMP能够有效的降低链路利用率，具有良好的稳定性。而且LAMP选择的备用路
径的长度仅仅比最短路径略长，最后LAMP的通信开销和其他方法相比是最小的。
参考文献（References）
[1] X. Xiao, A. Hannan, B. Bailey, and L. Ni, \Tra�c engineering with MPLS in the internet,"
[J] in IEEE Network Magazine, 2000.
[2] H. Wang, H. Xie, L. Qiu, Y. R. Yang, Y. Zhang, and A. Greenberg, \Cope: Tra�c engi-
neering in dynamic networks," [A] in In Proc. SIGCOMM, 2006.
[3] B. Fortz, J. Rexford, and M. Thorup, \Tra�c engineering with traditional ip routing pro-
tocols," [J] in IEEE Communication Magazine, 2002.
[4] B. Fortz and M. Thorup, \Optimizing ospf/is-is weights in a changing world," [j] IEEE
Journal on Selected Areas in Communications (JSAC), vol. 20, 2002.
[5] B. Fortz and M. Thorup, \Internet tra�c engineering by optimizing ospf weights," [A] in
Proc. IEEE INFOCOM, 2000.
[6] A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True, \Deriving
tra�c demands for operational ip networks: Methodology and experience," [J] IEEE/ACM
Transactions on Networking (TON), vol. 9, pp. 265 { 279, 2001.
[7] A. Sridharan and R. Guerin, \Making igp routing robust to link failures," [A] in Proc. of
Networking, 2005.
5负载流量非常接近相应的阈值，但是尚未达到阈值。
- 15 -
˖ڍመڙጲ
[8] D. Xu, M. Chiang, and J. Rexford, \Deft: Distributed exponentially-weighted
ow split-
ting," [A] in Proc. of IEEE INFOCOM, 2007.
[9] ahai Xu, M. Chiang, and J. Rexford, \Dlink-state routing with hop-by-hop forwarding can
achieve optimal tra�c engineering," [A] in Proc. of IEEE INFOCOM, 2008.
[10] M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates, and Y. Zhang., \Expe-
rience in measuring internet backbone tra�c variability: Models, metrics, measurements
and meaning," [A] in Proc. of International Teletra�c Congress (ITC-18), 2003.
[11] M. Roughan, M. Thorup, and Y. Zhang, \Tra�c engineering with estimated tra�c ma-
trices," in Proc. of ACM SIGCOMM conference on Internet measurement (IMC), [A] pp.
248 { 258, 2003.
[12] S. Kandula, D. Katabi, B. Davie, and A. Charny, \Walking the tightrope: responsive yet
stable tra�c engineering," [A] in Proc. ACM SIGCOMM, 2005.
[13] A. Elwalid, C. Jin, S. Low, and I. Widjaja, \Mate:mpls adaptive tra�c engineering," [A]
in Proc. IEEE INFOCOM, 2001.
[14] S. Fischer, N. Kammenhuber, and A. Feldmann, \Replex: dynamic tra�c engineering
based on wardrop routing policies," [A] in Proc. of CoNext, 2006.
[15] A. Kvalbein, C. Dovrolis, and C. Muthu, \Multipath load-adaptive routing: putting the
emphasis on robustness and simplicity," [A] in Proc. of IEEE ICNP, 2009.
[16] Y. Liao, L. Gao, R. Guerin, and Z.-L. Zhang, \Reliable interdomain routing through mul-
tiple complementary routing processes," [A] in Proc. of ACM CoNEXT, 2008.
[17] N. Kushman, S. Kandula, D. Katabi, and B. M. Maggs, \R-bgp: Staying connected in a
connected world," [a] in Proc. of 4th USENIX NSDI, 2007.
[18] W. Xu and J. Rexford, \Miro: Multi-path interdomain routing," [A] in Proc. of ACM
SIGCOMM, 2006.
[19] H. Jiang and C. Dovrolis, \Passive estimation of tcp round-trip times," [J] ACM SIG-
COMM CCR, vol. 32, pp. 75 { 88, 2002.
[20] B. Veal, K. Li, and D. Lowenthal, \New methods for passive estimation of tcp round-trip
times," [J] Lecture Notes in Computer Science, vol. 3431, pp. 121{134, 2005.
[21] C. Villamizar and C. Song, \High performance tcp in ansnet," [J] ACM SIGCOMM Com-
puter Communication Review, vol. 20, pp. 45 { 60, 1994.
[22] R. Morris, \Scalable tcp congestion control," [A] in Proc. of INFOCOM, 2000.
- 16 -
˖ڍመڙጲ
[23] V. Misra, W.-B. Gong, and D. Towsley, \Fluid-based analysis of a network of aqm routers
supporting tcp
ows with an application to red," [A] in Proc. ACM SIGCOMM, 2000.
[24] S. Floyd and K. Fall, \Promoting the use of end-to-end congestion control in the internet,"
[J] IEEE/ACM Transactions on Networking (TON), vol. 7, pp. 458 { 672, 1999.
[25] R. Mahajan, S. Floyd, and D. Wetherall, \Controlling high-bandwidth
ows at the con-
gested router," [A] in Proc. IEEE ICNP, 2001.
[26] D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, \Resilient overlay networks,"
[A] in Proc. of ACM SOSP, 2001.
[27] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S.
Shenker, and J. Turner, \Open
ow white paper { open
ow: Enabling innovation in campus
networks," [OL] 2008.
[28] \ONF white paper { software-de�ned networking: The new norm for networks," [OL] ONF
Market Education Committee, 2012.
[29] Rocketfuel, [OL] \
rocketfuel/."
[30] M. Roughan, \Simplifying the synthesis of internet tra�c matrices," [J] ACM SIGCOMM
Computer Communication Review (CCR), vol. 35, pp. 93{96, 2005.
[31] D. Basak, H. T. Kaur, and S. Kalyanaraman, \Tra�c engineering techniques and algo-
rithms for the internet," [OL] 2002.
[32] M. Motiwala, M. Elmore, N. Feamster, and S. Vempala, \Path splicing," [A] in Proc. of
ACM SIGCOMM, 2008.
[33] B. Fortz and M. Thorup, \Robust optimization of ospf/is-is weights," [A] in Proc. Inter-
national Network Optimization Conference, 2003, pp. 225{230.
[34] W. Hao and R. Ito, \Dynamics of load-sensitive adaptive routing," [A] in Proc. IEEE
International Conference on Communications (ICC), 2005.
[35] A. Khanna and J. Zinky, \The revised arpanet routing metric," [A] in Proc. of ACM
SIGCOMM, 1989.
[36] J. M. McQuillan, I. Richer, and E. C. Rosen, \The new routing algorithm for the arpanet,"
[J] IEEE Transactions on Communications, vol. 28, p. 711C719, 1980.
- 17 -
