rfc2992.txt

本程序为在linux下实现FTP传输文件的实现

组织：中国互动出版网（http://www.china-pub.com/）
RFC文档中文翻译计划（http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：[e-mail]
译者：范晨 (fanchen  [e-mail])
译文发布时间：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。这样我们就有了下面的计
算公式：