rfc2992.txt

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

                           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: [phone]
   EMail: [e-mail]
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文档中文翻译计划