论文部分内容阅读
随着计算机技术和通信技术的快速发展,网络规模不断扩大,Internet用户对网络带宽提出了更高的要求,制约网络带宽的关键因素在于路由器路由查找和分组转发的速度。路由器基于待转发数据包的目的IP地址进行路由查找,根据最长前缀匹配规则,在转发信息表(FIB:Forwarding Information Base)中查询下一跳端口。路由器的内存和CPU资源有限,随着FIB表项个数的不断增加,设计高效准确的路由查找算法是提升路由器转发效率的核心和关键。“基于Bloom Filter的路由查找算法(简称为PBF算法)”是一个将Bloom Filter和Trie树应用到路由查找中的高效算法,但是由于Bloom Filter存在“假阳性”,必须要针对Bloom Filter考察出来的前缀(称这些前缀为“候选前缀”)到片外对比出在FIB表中存在匹配项且长度最长的前缀,影响了路由查找的效率,随着FIB表项个数的增加,PBF算法效率变得越来越低。为了在路由查找时探测出比PBF算法更少的候选前缀,减少由于Bloom Filter假阳性造成的不必要的片外内存访问次数,提高路由器路由查找速度,本文提出并实现了基于pivot-pushing和Bloom Filter的快速路由查找算法(简称为PP&BF算法)。PP&BF算法对根据FIB表在片外构建的原始Trie树的某一层(假设为第p层)进行pivot-pushing操作,实现对Trie树的优化;在进行路由查找时,利用针对优化后的Trie树第p层上的“空心节点”(空心节点代表的网络前缀在FIB表中不存在对应的表项)构建的Bloom Filter的返回值,探测出待查IP地址在FIB表中最长匹配前缀的长度范围,选出比PBF算法更少的候选前缀,达到了减少不必要的片外内存访问次数,提高路由器路由查找速度的目的。经过试验和理论分析确定参数p最优的值后,针对PBF算法和本文提出的PP&BF算法进行了大量对比试验,实验结果表明:PP&BF算法的查询效率要优于PBF算法,在要求算法平均片外访问次数不高于1.003的前提下,PP&BF算法相比PBF算法可以节约10%以上的片上存储空间。