《rfc2992 等价多径算法的分析》由会员分享，可在线阅读，更多相关《rfc2992 等价多径算法的分析（5页珍藏版）》请在金锄头文库上搜索。
1、等价多径算法的分析（of 备忘录状态 本文档讲述了一种对其改进提出了讨论和建议。请参考最新版本的() 来获得本协议的标准化进程和状态，此备忘录的发布不受任何限制。版权注意版权归因特网协会（2000）所有，保留一切权利。摘要等价多径（在有多个等价路径的时候发送分组的一项路由技术。转发引擎用下一跳来区分这多个路径。在转发一个分组的时候路由器必须作出决策使用哪一条路径。本文档分析了一种决策的方法，其中包括对算法复杂度的分析和对改变下一跳路径时引起的流量分裂的分析。目 录1. 哈希门限（22. 复杂度 分裂（33. 其 算法的 54. 65. 参考文 66. 作 67. 版权 671. 哈希门限（希门
2、限是等价多径 中决 路由的下一跳的一种方法。路由器 对包 中决 流的 个 进 哈希 算（ 得 一个决策 （ 决策 的 分下一跳分“其中的一个区 。这，路由器 用在哪个区 中来决 下一跳的路由。作哈希门限的一个 ，对包 中决 流 的 （包的 和目的 ）进 一个， 得 一个16 特的决策 。 要 目的 有4个不的下一跳 ”，对16 特中分“一区 。 要使 会等，路由器 使 有，65536/4 16k。哪个区 包了这个决策 ，”的下一跳 。2. 分析”一个算法来进 下一跳的决策时， 这个 。一个是复杂度，是算法的 算量。个是分裂（是一个 个是 。由 算法的 特 是 哈希 有的，在 的分析中 不对这个
3、 讨。在 的分析中 个区 有的。 哈希 的 出是 分布的， 条路径 的流量分布是 分布的，这这个算法 等价多径（ 价多径（通 个区 分“不的来 ， 是这不在本文的 。 复杂度哈希门限算法的复杂度 分下 个分 不下一跳的区 分，决策 的 算和 决策 在哪一个区 中。算法中并 有制 用哪个哈希 来 算决策 。这一 的算法复杂度 决 哈希 的复杂度。 这一 的 算 在 其 要在 出决策 的作并 。由 个区 有的，对 区 的 算是 的。 用一个区 的 推出来。 面 证 ，对 的区 ，并不要存储 的 。了”下一跳， 必须确 决策 包在哪个区 里。因 个区 是，用一个简单的除法 确 出 属 哪个区 。区
4、/ 下一跳的个 区 号 决策 / 区 因此找 下一跳所要的时决 下一跳在存中的组织方式。最 的办法是用一个从0（1）开始 的 组来存放 个下一跳。分裂（似 路由一 不发生变化，其 会 。分裂（是用来 量有多少流量因路由器的某些变化， 的路由产生了变化。 分裂 义由 路由器原因而发生路由变化的流量占总流量的 。if or of is 更详细的 分裂及 何对类似考1。类似收 一个包 ，”最近最少使用的下一跳）出分裂的情况是 常频繁的，而且 路由器的变化无。显这跟哈希门限算法的情况不一。对一个 的流来说，只要 个区 的 不变，会始终”的下一跳。由 了 个区 的是的， 区 发生变化的唯一原因是增加 去
5、掉了一个下一跳。这时 个区 必须时增 缩，仍保持 整个决策 填满。 从下面的这个 开始进 分析。0123456701234567012345670123456701234567+ 1 | 2 | 3 | 4 | 5 |+ 1 | 2 | 4 | 5 |+123456789012345678901234567890123456789图 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 +
6、1/2 + 1/2 + 1/4) 3/10要注意的是加 一个新的区 的时候所产生的分裂和去掉一个区 是 的。是说， 只要考虑区 从，而区 从时的分裂流量的 是 的。0123456701234567012345670123456701234567+ 1 | 2 | 3 | 4 | 5 |+ 1 | 2 | 3 | 5 |+123456789012345678901234567890123456789图 2. 删除区 4的 在图2中，区 4被删除了。 面一，剩下的区 时增并且 移。区 2的1/4在属 区 1，区 3的1/2在属 区 2，区 4的3/4在属 区 3，并且区 4的1/4在属 区 5。由
7、 原来表整个流量的1/5，总体的分裂 是7/20。考虑一般的情况，去掉了区 K，剩下的增长。增长的流量是 分“在的，因此的变化1/N/(1/(N(。 的变化会引起除了两端外的其 区 发生 移。一个区 增了， 个区 朝 增长量。区 2中的1/(N(的流量包在区 1的变化中。区 3中的2/(N(的流量包在区 2中，这是因区 2 区 3的方 移了1/(N(又增了1/(N(。这的 程从两端开始，一 区 K。这 有了下面的 算公式 i (裂 = + (N)( / (N)( i=K+1常 因1/(N)(提出来，/ N 1 | |分裂 = | i + (|(N)(| / / | /1 i=K+1在用连续整
8、和的 算公式，一项(K)(2，项()/2，(K) + ()分裂 = )(公式中 看出K 近1和时候分裂 最。这一点 得 证 。 N常 ， 个因分解在合并 2K*K - 2K - 2 N*N + N= )(*K - K - N + 1= + )( 2(的项是常量， 其忽略。一项的分母是常量， 忽略。对一项导 ，得 K*K - (N+1)K)2K - (N+1)K(N+1)/2 式零。，N奇 时，(N+1)/2是一个整 ，而N偶 时，(N+1)/2不是整 。在这种情况下，KN/2N/21时分裂 最。因分裂 的表式是一个在1和 局最点的次多项式， 的最一 在两端 。K1裂 1/2。令K=(N+1)/
9、2，表式的1/4 + 1/(4*N)， 局最。因此， 的分裂 的 (1/4, 1/2。了减 造的分裂流量， 建议 新区 加在中而不是两端。3. 其 算法的 目还有其 的一些算法用来 下一跳决策。这些算法的复杂度和分裂 不一。这里只考虑其中的种算法， 在设 是 频繁分裂的（by 是说 下一跳的 集合不发生变化，路由会始终保持一 ）。这排除了”算法。 这里 考虑模重算法。模 决 流 （、目的 ）的 进 一个哈希 算， 对哈希 算的结再对N模， 决 了哪一个下一跳。模是所有这类算法中最的， 增加删除一个下一跳，所带来的分裂 是(N。模希门限算法是的。最高随 权重算法（某些方面 哈希门限算法有类似 ， 区 是不固 的。对 由器用 决 流 的 和下一跳一起作一个伪随 发生器的种，并用 来生一个权重。 ”权重最的个下一跳。使用 所带来的流量分裂 （加 去掉一个下一跳所带来的分裂 一般1/N）。时， 的缺点在 哈希门限算法更复杂， 代价更高。2中出了 一些算法的 的结。3中出了使用。因模希门限算法、对决 流 的包 进 一次哈希 算，在进 复杂度 时 哈希 算提出来不进 。 哈希 算不 够用 简单高效 ， 面的种方法必须重新进 考虑。哈希门限的查表作跟模最优情况下复杂度O(1)。HRW
