云南龙网

  1. 首页 > 云知道 > >

等价多径算法的分析

云知道

【等价多径算法的分析】本备忘录状态
本文档讲述了一种Internet通信的标准Internet跟踪协议,并对其改进提出了讨论和建
议 。请参考最新版本的"InternetOfficialProtocolStandards"(STD1)来获得本协议的
标准化进程和状态，此备忘录的发布不受任何限制 。
版权注重
版权归因特网协会（2000）所有，保留一切权利 。
摘要
等价多径（ECMP）是在有多个等价路径的时候发送分组的一项路由技术 。转发引擎用下
一跳来区分这多个路径 。在转发一个分组的时候路由器必须作出决策使用哪一条路径 。本文
档分析了一种决策的方法，其中包括对算法复杂度的分析和对改变下一跳路径时引起的流量
分裂的分析 。
目录
1.哈希门限（HASH-THRESHOLD） 2
2.分析 2
2.1.复杂度 2
2.2.分裂（Disruption） 3
3.与其它算法的比较 5
4.安全性问题 6
5.参考文献 6
6.作者地址 6
7.版权声明 6
致谢 7
1.哈希门限（Hash-Threshold）
哈希门限是等价多径问题中决定路由的下一跳的一种方法 。路由器首先对包头中决定流
向的各个域进行哈希运算（例如CRC16），得到一个决策码（key） 。将决策码的可能取值空
间划分成N个区域，给每个不同的下一跳分配其中的一个区域 。这样，路由器就可以用根据
决策码处在哪个区域中来决定下一跳的路由 。
作为哈希门限的一个例子，对包头中决定流向的域（包的源地址和目的地址）进行一个
CRC16运算，然后得到一个16比特的决策码 。假定要到达目的地址有4个不同的下一跳地址
可供选择，对每个下一跳都在16比特空间中分配一块区域 。假如要使机会均等，路由器应当
使每块区域都具有相同大小，即65536/4或者16k 。哪个区域包含了这个决策码，就选择相
应的下一跳地址 。
2.分析
当选择一个算法来进行下一跳的决策时，我们关心这样几个问题 。第一个是复杂度，也
就是算法的运算量 。第二个是分裂（disruption，也就是同一个数据包流改变其路由） 。第
三个是均衡 。由于算法的均衡特性是与哈希函数直接有关的，在我们的分析中将不对这个问
题做深入探讨 。
在我们的分析中我们假定各个区域都具有相同的大小 。假如哈希函数的输出是平均分布
的，那么各条路径上的流量分布也是平均分布的，这样这个算法就可以比较好地实现等价多
径（ECMP） 。非定价多径（non-equal-costmulti-path）可以通过给各个区域分配不同的大
小来实现，但是这不在本文的范围之内 。
2.1.复杂度
哈希门限算法的复杂度可以分成以下三个部分：不同下一跳的区域划分，决策码的计算
和判定决策码在哪一个区域中 。
算法中并没有强制规定用哪个哈希函数来计算决策码 。这一步的算法复杂度完全取决于
哈希函数的复杂度 。我们假定这一步的计算可以在硬件上与其他需要在做出决策之前完成的
操作并行完成 。
由于各个区域都具有相同的大小，对于区域边界的计算是很轻易的 。每一条边界都可以
用第一个区域的边界推出来 。后面我们将证实，对于同样大小的区域，并不需要存储它们的
边界值 。
为了选择下一跳，我们必须确定决策码包含在哪个区域里 。因为各个区域都是同样大小，
我们用一个简单的除法就可以确定出它属于哪个区域 。
区域大小＝码空间大小/下一跳的个数
区域号＝决策码/区域大小
因此找到下一跳所需要的时间取决于下一跳在内存中的组织方式 。最直接的办法是用一

推荐阅读


上一篇：最低工资怎么规定的

下一篇：抖音认证申请公函怎么上传