等价多径算法的分析

《等价多径算法的分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、www.woxia.netNetworkWorkingGroupC.HoppsRequestforComments:2992NextHopTechnologiesCategory:InformationalNovember2000等价多径算法的分析（RFC2992——AnalysisofanEqual-CostMulti-PathAlgorithm）本备忘录状态本文档讲述了一种Internet通信的标准Internet跟踪协议,并对其改进提出了讨论和建议。请参考最新版本的"InternetOfficialProtocolStandards"(STD1)

2、来获得本协议的标准化进程和状态，此备忘录的发布不受任何限制。版权注意版权归因特网协会（2000）所有，保留一切权利。摘要等价多径（ECMP）是在有多个等价路径的时候发送分组的一项路由技术。转发引擎用下一跳来区分这多个路径。在转发一个分组的时候路由器必须作出决策使用哪一条路径。本文档分析了一种决策的方法，其中包括对算法复杂度的分析和对改变下一跳路径时引起的流量分裂的分析。目录1.哈希门限（HASH-THRESHOLD）22.分析22.1.复杂度22.2.分裂（Disruption）33.与其它算法的比较54.安全性问题65.参考文献66.作者地址67.版

3、权声明6致谢71.哈希门限（Hash-Threshold）哈希门限是等价多径问题中决定路由的下一跳的一种方法。路由器首先对包头中决定流向的各个域进行哈希运算（例如CRC16），得到一个决策码（key）。将决策码的可能取值空间划分成N个区域，给每个不同的下一跳分配其中的一个区域。这样，路由器就可以用根据决策码处在哪个区域中来决定下一跳的路由。作为哈希门限的一个例子，对包头中决定流向的域（包的源地址和目的地址）进行一个CRC16运算，然后得到一个16比特的决策码。假定要到达目的地址有4个不同的下一跳地址可供选择，对每个下一跳都在16比特空间中分配一块区域。

4、如果要使机会均等，路由器应当使每块区域都具有相同大小，即65536/4或者16k。哪个区域包含了这个决策码，就选择相应的下一跳地址。2.分析当选择一个算法来进行下一跳的决策时，我们关心这样几个问题。第一个是复杂度，也就是算法的运算量。第二个是分裂（disruption，也就是同一个数据包流改变其路由）。第三个是均衡。由于算法的均衡特性是与哈希函数直接有关的，在我们的分析中将不对这个问题做深入探讨。在我们的分析中我们假定各个区域都具有相同的大小。如果哈希函数的输出是平均分布的，那么各条路径上的流量分布也是平均分布的，这样这个算法就可以比较好地实现等价多路

5、过··走过···需要的时候记得回来看看····因为容易得到所以得不到大家的珍惜·即使这样我们也要做下去！·············我下资源网www.woxia.net径（ECMP）。非定价多径（non-equal-costmulti-path）可以通过给各个区域分配不同的大小来实现，但是这不在本文的范围之内。2.1.复杂度哈希门限算法的复杂度可以分成以下三个部分：不同下一跳的区域划分，决策码的计算和判断决策码在哪一个区域中。算法中并没有强制规定用哪个哈希函数来计算决策码。这一步的算法复杂度完全取决于哈希函数的复杂度。我们假定这一步的计算可以在硬件上与其

6、他需要在做出决策之前完成的操作并行完成。由于各个区域都具有相同的大小，对于区域边界的计算是很容易的。每一条边界都可以用第一个区域的边界推出来。后面我们将证明，对于同样大小的区域，并不需要存储它们的边界值。为了选择下一跳，我们必须确定决策码包含在哪个区域里。因为各个区域都是同样大小，我们用一个简单的除法就可以确定出它属于哪个区域。区域大小＝码空间大小/下一跳的个数区域号＝决策码/区域大小因此找到下一跳所需要的时间取决于下一跳在内存中的组织方式。最直接的办法是用一个从0（1）开始计数的数组来存放各个下一跳。2.2.分裂（Disruption）类似TCP的协

7、议在建立连接之后如果路由一直不发生变化，其性能会比较好。分裂（disruption）就是用来衡量有多少流量因为路由器的某些变化，它们的路由产生了变化。我们将分裂定义为由于路由器原因而发生路由变化的流量占总流量的比例。Thiscanbecomeimportantifoneormoreofthepathsisflapping.更详细的关于分裂以及它如何对类似TCP的协议产生影响的信息可参考[1]。类似round-robin的算法（接收到一个包以后，选择最近最少使用的下一跳）出现分裂的情况是非常频繁的，而且与路由器的变化无关。显然这跟哈希门限算法的情况不一样

8、。对于一个给定的流来说，只要各个区域的边界不变，就会始终选择相同的下一跳。由于我们规定了各个区