等价多径算法的分析( 三 )

那么
(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-NKN 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.与其它算法的比较
目前还有其它的一些算法用来做下一跳决策。这些算法的复杂度和分裂比例都不大一样。
我们这里只考虑其中的几种算法，它们在设计上是非频繁分裂的（notdisruptivebydesign，
也就是说假如下一跳的可能集合不发生变化，路由就会始终保持一致）。这就排除了
round-robin算法和随机选择算法。我们这里将考虑模N算法和最高随机权重算法。
模N算法是哈希门限算法的一种简单特例。给定N个下一跳，对数据包头中决定流向（源、
目的地址）的域进行一个哈希运算，然后对哈希运算的结果再对N取模，然后根据这个结果
直接就决定了选取哪一个下一跳。模N算法的分裂比例是所有这类算法中最大的，假如增加
或删除一个下一跳，所带来的分裂比例是(N-1)/N 。模N算法的复杂度与哈希门限算法是相当
的。
最高随机权重算法（Highestrandomweight,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算法实现起来代价太大的时候，显然还是应该选择哈希门限算法，