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

个从0（1）开始计数的数组来存放各个下一跳。
2.2.分裂（Disruption）
类似TCP的协议在建立连接之后假如路由一直不发生变化，其性能会比较好。分裂
（disruption）就是用来衡量有多少流量因为路由器的某些变化，它们的路由产生了变化。
我们将分裂定义为由于路由器原因而发生路由变化的流量占总流量的比例。Thiscanbecome
importantifoneormoreofthepathsisflapping.更具体的关于分裂以及它如何对类
似TCP的协议产生影响的信息可参考[1] 。
类似round-robin的算法（接收到一个包以后，选择最近最少使用的下一跳）出现分裂
的情况是非常频繁的，而且与路由器的变化无关。显然这跟哈希门限算法的情况不一样。对
于一个给定的流来说，只要各个区域的边界不变，就会始终选择相同的下一跳。
由于我们规定了各个区域的大小是相同的，那么区域边界发生变化的唯一原因就是增加
或者去掉了一个下一跳。这时各个区域就必须同时增大或者缩小，仍然保持将整个决策码空
间填满。我们从下面的这个例子开始进行分析。
0123456701234567012345670123456701234567
------- ------- ------- ------- -------
12345
------- - ----- --- --- ----- - -------
1245
--------- --------- --------- ---------
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
------- ------- ------- ------- -------
12345
------- - ----- --- --- ----- - -------
1235
--------- --------- --------- ---------
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-1N
---i---(i-K)
分裂比例=--- ---
/(N)(N-1)/(N)(N-1)
------
i=1i=K 1
将常数因子1/((N)(N-1))提出来，
/K-1N
1------
分裂比例=---i (i-K)
(N)(N-1)//
------/
1i=K 1
我们现在用连续整数和的计算公式，第一项为(K)(K-1)/2，第二项为(N-K)(N-K 1)/2，