RFC2992 等值多-路径算法的分析

组织：中国互动出版网（http://www.china-pub.com/）
RFC文档中文翻译计划（http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：ouyang@china-pub.com
译者：范晨 (fanchen  fan-chen@china.com)
译文发布时间：2001-10-11
版权：本中文翻译文档版权归中国互动出版网所有。可以用于非商业用途自由转载，但必须
保留本文档的翻译及版权信息。


Network Working Group                                            C. Hopps
Request for Comments: 2992                           NextHop Technologies
Category: Informational                                     November 2000

等价多径算法的分析
（RFC2992――Analysis of an Equal-Cost Multi-Path Algorithm）

本备忘录状态 
本文档讲述了一种Internet通信的标准Internet跟踪协议,并对其改进提出了讨论和建
议。请参考最新版本的"Internet Official Protocol Standards" (STD 1) 来获得本协议的
标准化进程和状态，此备忘录的发布不受任何限制。
版权注意
版权归因特网协会（2000）所有，保留一切权利。
摘要
等价多径（ECMP）是在有多个等价路径的时候发送分组的一项路由技术。转发引擎用下
一跳来区分这多个路径。在转发一个分组的时候路由器必须作出决策使用哪一条路径。本文
档分析了一种决策的方法，其中包括对算法复杂度的分析和对改变下一跳路径时引起的流量
分裂的分析。

目  录
1. 哈希门限（HASH-THRESHOLD）	2
2. 分析	2
2.1.  复杂度	2
2.2. 分裂（Disruption）	3
3. 与其它算法的比较	5
4.  安全性问题	6
5.  参考文献	6
6.  作者地址	6
7.  版权声明	6
致谢	7

1. 哈希门限（Hash-Threshold）
哈希门限是等价多径问题中决定路由的下一跳的一种方法。路由器首先对包头中决定流
向的各个域进行哈希运算（例如CRC16），得到一个决策码（key）。将决策码的可能取值空
间划分成N个区域，给每个不同的下一跳分配其中的一个区域。这样，路由器就可以用根据
决策码处在哪个区域中来决定下一跳的路由。
作为哈希门限的一个例子，对包头中决定流向的域（包的源地址和目的地址）进行一个
CRC16运算，然后得到一个16比特的决策码。假定要到达目的地址有4个不同的下一跳地址
可供选择，对每个下一跳都在16比特空间中分配一块区域。如果要使机会均等，路由器应当
使每块区域都具有相同大小，即65536/4或者16k。哪个区域包含了这个决策码，就选择相
应的下一跳地址。
2. 分析
当选择一个算法来进行下一跳的决策时，我们关心这样几个问题。第一个是复杂度，也
就是算法的运算量。第二个是分裂（disruption，也就是同一个数据包流改变其路由）。第
三个是均衡。由于算法的均衡特性是与哈希函数直接有关的，在我们的分析中将不对这个问
题做深入探讨。
在我们的分析中我们假定各个区域都具有相同的大小。如果哈希函数的输出是平均分布
的，那么各条路径上的流量分布也是平均分布的，这样这个算法就可以比较好地实现等价多
径（ECMP）。非定价多径（non-equal-cost multi-path）可以通过给各个区域分配不同的大
小来实现，但是这不在本文的范围之内。
2.1.  复杂度
哈希门限算法的复杂度可以分成以下三个部分：不同下一跳的区域划分，决策码的计算
和判断决策码在哪一个区域中。
算法中并没有强制规定用哪个哈希函数来计算决策码。这一步的算法复杂度完全取决于
哈希函数的复杂度。我们假定这一步的计算可以在硬件上与其他需要在做出决策之前完成的
操作并行完成。
由于各个区域都具有相同的大小，对于区域边界的计算是很容易的。每一条边界都可以
用第一个区域的边界推出来。后面我们将证明，对于同样大小的区域，并不需要存储它们的
边界值。
为了选择下一跳，我们必须确定决策码包含在哪个区域里。因为各个区域都是同样大小，
我们用一个简单的除法就可以确定出它属于哪个区域。
区域大小 ＝ 码空间大小 / 下一跳的个数
区域号 ＝ 决策码 / 区域大小
因此找到下一跳所需要的时间取决于下一跳在内存中的组织方式。最直接的办法是用一
个从0（1）开始计数的数组来存放各个下一跳。
2.2. 分裂（Disruption）
类似TCP的协议在建立连接之后如果路由一直不发生变化，其性能会比较好。分裂
（disruption）就是用来衡量有多少流量因为路由器的某些变化，它们的路由产生了变化。
我们将分裂定义为由于路由器原因而发生路由变化的流量占总流量的比例。This can become 
important if one or more of the paths is flapping. 更详细的关于分裂以及它如何对类
似TCP的协议产生影响的信息可参考[1]。
类似round-robin的算法（接收到一个包以后，选择最近最少使用的下一跳）出现分裂
的情况是非常频繁的，而且与路由器的变化无关。显然这跟哈希门限算法的情况不一样。对
于一个给定的流来说，只要各个区域的边界不变，就会始终选择相同的下一跳。
由于我们规定了各个区域的大小是相同的，那么区域边界发生变化的唯一原因就是增加
或者去掉了一个下一跳。这时各个区域就必须同时增大或者缩小，仍然保持将整个决策码空
间填满。我们从下面的这个例子开始进行分析。

              0123456701234567012345670123456701234567
             +-------+-------+-------+-------+-------+
             |   1   |   2   |   3   |   4   |   5   |
             +-------+-+-----+---+---+-----+-+-------+
             |    1    |    2    |    4    |    5    |
             +---------+---------+---------+---------+
              0123456789012345678901234567890123456789
              图 1. 删除区域3的前后
在图1中，区域3被删除了。剩下的区域同时增大并且平移，将整个码空间仍然填满。
这时区域2中的1/4现在属于区域1，区域3的1/2现在属于区域2，区域3的另1/2属于区
域4，还有区域4的1/4属于区域5。原来每个区域都代表流量的1/5，那么整个的分裂比例
可以计算为
1/5*(1/4 + 1/2 + 1/2 + 1/4) 即 3/10
需要注意的是当加入一个新的区域的时候所产生的分裂和去掉一个区域是完全相同的。
也就是说，我们只需要考虑区域数从N变化到N-1时所产生的分裂流量的比例，而区域数从
N-1变到N时的分裂流量的比例是完全相同的。

              0123456701234567012345670123456701234567
             +-------+-------+-------+-------+-------+
             |   1   |   2   |   3   |   4   |   5   |
             +-------+-+-----+---+---+-----+-+-------+
             |    1    |    2    |    3    |    5    |
             +---------+---------+---------+---------+
              0123456789012345678901234567890123456789
              图 2. 删除区域4的前后

在图2中，区域4被删除了。与前面一样，剩下的区域同时增大并且相应平移。区域2
的1/4现在属于区域1，区域3的1/2现在属于区域2，区域4的3/4现在属于区域3，并且
区域4的1/4现在属于区域5。由于原来每个区域代表整个流量的1/5，总体的分裂比例是
7/20。
考虑一般的情况，去掉了区域K，剩下的N-1个区域平均增长。增长的流量是平均分配在N-1
个区域中的，因此每个区域的大小的变化为1/N/(N-1)或1/(N(N-1))。大小上的变化会引起
除了两端以外的其它区域发生平移。第一个区域增大了，那么第二个区域就朝向K移动了相
应的增长量。区域2中的1/(N(N-1))的流量包含在区域1的大小变化之中。区域3中的
2/(N(N-1))的流量包含在区域2之中，这是因为区域2向区域3的方向平移了1/(N(N-1))又
增大了1/(N(N-1))。这样的过程从两端开始，一直到到达区域K。这样我们就有了下面的计
算公式：

                           K-1              N
                           ---    i        ---  (i-K)
             分裂比例   =  \     ---    +  \     ---
                           /   (N)(N-1)    /   (N)(N-1)
                           ---             ---
                           i=1            i=K+1

   将常数因子1/((N)(N-1))提出来，

                                /  K-1         N        \
                          1     |  ---        ---       |
           分裂比例  =   ---    |  \    i  +  \   (i-K) |
                       (N)(N-1) |  /          /         |
                                \  ---        ---       /
                                     1        i=K+1

我们现在用连续整数和的计算公式，第一项为(K)(K-1)/2，第二项为(N-K)(N-K+1)/2，
那么

                             (K-1)(K) + (N-K)(N-K+1)
                分裂比例   = -----------------------
                                   2(N)(N-1)

从公式中可以看出当K接近1和N的中间的时候分裂比例最小。这一点可以很容易得到
证明。假定N为常数，先将各个因子分解在合并：

                            2K*K - 2K - 2NK + N*N + N
                          = -------------------------
                                    2(N)(N-1)

                             K*K - K - NK      N + 1
                          = --------------  + -------
                               (N)(N-1)        2(N-1)

上式的第二项是常量，可以将其忽略。第一项的分母也是常量，也可以忽略。对第一项
取导数，得到：
                             d
                             -- (K*K - (N+1)K)
                             dk

                             = 2K - (N+1)

当K为(N+1)/2上式为零。
当然，K必须是一个整数。当N为奇数时，(N+1)/2是一个整数，然而当N为偶数时，(N+1)/2
不是整数。在这种情况下，当K为N/2或N/2＋1时分裂比例最小。
因为分裂比例的表达式是一个在1和N的中点处取全局最小点的二次多项式，那么它的
最大值一定在两端处取到。当K为1或N时，分裂比例为1/2。
令K=(N+1)/2，表达式的值为1/4 + 1/(4*N)，为全局最小值。因此，可能的分裂比例的
取值范围为(1/4, 1/2]。
为了减小可能造成的分裂流量，我们建议将新区域加在中间而不是两端。
3. 与其它算法的比较
目前还有其它的一些算法用来做下一跳决策。这些算法的复杂度和分裂比例都不大一样。
我们这里只考虑其中的几种算法，它们在设计上是非频繁分裂的（not disruptive by design，
也就是说如果下一跳的可能集合不发生变化，路由就会始终保持一致）。这就排除了
round-robin算法和随机选择算法。我们这里将考虑模N算法和最高随机权重算法。
模N算法是哈希门限算法的一种简单特例。给定N个下一跳，对数据包头中决定流向（源、
目的地址）的域进行一个哈希运算，然后对哈希运算的结果再对N取模，然后根据这个结果
直接就决定了选取哪一个下一跳。模N算法的分裂比例是所有这类算法中最大的，如果增加
或删除一个下一跳，所带来的分裂比例是(N-1)/N。模N算法的复杂度与哈希门限算法是相当
的。
最高随机权重算法（Highest random weight, HRW）在某些方面与哈希门限算法有类似
之处，比如区域大小都是不固定的。对于每个下一跳，路由器用数据包头中决定流向的域和
下一跳一起作为一个伪随机数发生器的种子，并用它来生成一个权重。然后选择权重最大的
那个下一跳。使用HRW的好处在于它所带来的流量分裂很小（加入或去掉一个下一跳所带来
的分裂比例一般为1/N）。同时，它的缺点在于它比哈希门限算法更复杂，实现代价更高。
[2]中给出了HRW算法与其它一些算法的比较的结果。[3]中给出了使用HRW的一个例子。
因为模N算法、哈希门限算法、HRW算法都要对决定流向的包头域进行一次哈希运算，
我们在进行复杂度比较时可以将哈希运算提出来不进行比较。如果哈希运算不能够用硬件简
单高效地实现，那么上面的几种方法都必须重新进行考虑。
哈希门限的查表操作跟模N操作一样，最优情况下复杂度为O(1)。HRW的查表操作的复
杂度为O(N)。
流量分裂的表现与复杂度相反。HRW最好，分裂因子为1/N。哈希门限的分裂因子在1/4
和1/2之间。模N算法的分裂因子为(N-1)N。
如果HRW下一跳选择过程的复杂度可以接收的话，我们认为可以在它和哈希门限算法进
行选择。它可以应用于类似这样的情况，路由器中保存了每个流的状态，这样就不需要频繁
进行下一跳决策。
当然，如果发现HRW算法实现起来代价太大的时候，显然还是应该选择哈希门限算法，
因为它的复杂度与模N算法一样但是流量分裂要小一些。
4.  安全性问题
   本文档时对ECMP路由决策的一个算法的分析，与Internet体系结构的安全性没有直接的
关系。
5.  参考文献
   [1]  Thaler, D. and C. Hopps, "Multipath Issues in Unicast and
        Multicast", RFC 2991, November 2000.

   [2]  Thaler, D. and C.V. Ravishankar, "Using Name-Based Mappings to
        Increase Hit Rates", IEEE/ACM Transactions on Networking,
        February 1998.

   [3]  Estrin, D., Farinacci, D., Helmy, A., Thaler, D., Deering, S.,
        Handley, M., Jacobson, V., Liu, C., Sharma, P. and L. Wei,
        "Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol
        Specification", RFC 2362, June 1998.
6.  作者地址
   Christian E. Hopps
   NextHop Technologies, Inc.
   517 W. William Street
   Ann Arbor, MI 48103-4943
   U.S.A

   Phone: +1 734 936 0291
   EMail: chopps@nexthop.com
7.  版权声明
   版权归Internet协会所有（1999）。保留所有权利。
   本文及其译本可以提供给其他任何人，可以准备继续进行注释，可以继续拷贝、出版、发
布，无论是全部还是部分，没有任何形式的限制，不过要在所有这样的拷贝和后续工作中提
供上述声明和本段文字。无论如何，本文档本身不可以做任何的修改，比如删除版权声明或
是关于Internet协会、其他的Internet组织的参考资料等。除了是为了开发Internet标准
的需要，或是需要把它翻译成除英语外的其他语言的时候，在这种情况下，在Internet标准
程序中的版权定义必须被附加其中。
   上面提到的有限授权允许永远不会被Internet协会或它的继承者或它的下属机构废除。
   本文档和包含在其中的信息以"As is"提供给读者，Internet社区和Internet工程任务
组不做任何担保、解释和暗示，包括该信息使用不破坏任何权利或者任何可商用性担保或特
定目的。
致谢
   Internet协会当前为RFC编辑提供了资助，对此表示感谢。
RFC2992―Analysis of an Equal-Cost Multi-Path Algorithm                   等价多径算法的分析


1
RFC文档中文翻译计划