大容量高带宽路由查找算法设计与FPGA实现

为了解决目前IP路由查表大容量和高吞吐需求的同时,实现低硬件资源成本,提出一种大容量高带宽IP路由查表算法,并完成FPGA实现。算法将FIB表项的存储映射为字典树的数据结构,进行路径压缩和级别压缩以节省存储资源。将字典树根节点信息存储在片内SRAM,子树节点存储于片外DRAM。查找时,在芯片硬件内采用流水线方式优化资源负载均衡,实现片外DRAM的一次访问即可得到结果,实现了单周期线速查表,并支持增量更新。该算法通过FPGA设计实现,并进行仿真和实机验证。结果表明,该方案可同时支持大容量IPv4和IPv6 FIB表项并行查找,与现有方案相比,做到了更大容量、更高带宽和更低成本。

可扩展路由器FIB表分解存储模型

FIB表急剧增长是互联网高速发展面临的重要问题之一,FIB表分解存储能有效解决该问题.现有的SPAL技术将FIB表较均匀地分解存储在不同线卡,但仍然存在较多的表项冗余存储现象,并且实现复杂.对此设计了一种新型的转发表分解存储模型(Decomposed Storage of FIB,DSF),它依据IP前缀的前若干bit位实现线卡对转发表的分解存储,并只带来极少的冗余存储.DSF的改进方案———EDSF,更可使各线卡非常均衡地完成分解存储.提出的分解存储模型缓解了FIB表项急剧增长问题的解决压力,同时大大节省了硬件资源.对于线卡数量更多的可扩展路由器尤为适合.通过对当前运营的路由表的分解存储实验研究及与其它方案的比较,验证了文中模型良好的存储性能.

一种前缀长度二分查找的改进算法

在研究路由表地址前缀分布特点的基础上,提出了前缀长度二分查找方案。该方案采用前缀扩展技术,将前缀数量相对稀少的若干种前缀合并成一种,降低了查找树的高度,减少了存储器访问次数,提高了查找速度,分析了一种实用的Marker存储算法,探讨了IPv6的路由查找问题。

面向自治系统间IP前缀劫持的一种无证书安全防范机制

自治系统间的IP前缀劫持是互联网安全的重大威胁.目前基于非对称密码学的前缀劫持防范机制都无可避免地面临复杂的公钥证书存储管理问题或者密钥托管问题,并且在前缀源自治系统在线验证时计算量太大,难以在实际中布署实施.本文提出的这种防范机制,采用公钥自证明签名方案进行前缀源自治系统的验证,无需公钥证书和密钥托管,可从多方面提高防范机制的性能,有望促进IP前缀劫持防范机制的实际布署实施.

基于Hash和二叉树的路由表查找算法

提出了一种基于Hash和二叉树的路由表查找算法,这一算法可以满足OC-768的转发要求,支持超过10万条前缀的大规模路由表,并且在路由表更新时,只有少量的存储器需要被改写.仿真结果显示,对于一个149 458条前缀的路由表,算法仅需要2 MB存储器,如果采用200 MHz的存储器芯片,平均的查找速度可以达到100 M次/秒.

基于Bloom滤波器的快速路由查找方法

针对IP路由查找中的最长前缀匹配问题,提出了一种基于Bloom滤波器的快速路由查找方法。首先,通过建立首字节索引表,减少了需要并行查询的Bloom滤波器的数量。其次,基于IP地址前缀长度分布的不均匀性对Bloom滤波器组的设置进行了优化,降低了查询过程对Bloom滤波器总数的需求。最后,将基本Bloom滤波器位向量中的每一比特位与一个计数器相关联,实现了对路由更新的支持。理论分析表明,与现有方法相比,利用该方法进行路由查找可以实现更低的选路表平均探测次数,并在最坏情况下具有更低的平均探测次数上界。实验结果验证了该方法的有效性及相关理论分析的正确性。

基于快速搜索树的路由查表算法

根据路由表中前缀的分布特点,将路由集合分割成几个子集,然后分别针对每个子集建立搜索树来实现路由查表。借助哈希压缩索引表使搜索树的深度降低到3,加快了搜索树的查找速度。而BloomFilters的应用,使几乎平均一次搜索树的查找就可以完成一次路由查表。该算法可以满足OC768链路的处理速度要求,支持达106数量级的路由表项,适于硬件流水线方式实现,具有很高的实用价值。这种方法用到IPv6同样可以收到很好的效果。

基于分段地址结构的快速路由查找算法

根据IPV6地址结构和骨干路由表特点,分析了原有路由查找算法,基于IPV6的掩码长度和分段地址,采用Hash表和多分支Trie树结构,提出了一种快速的IPV6路由查找算法。根据分段地址和掩码将最常用到的路由前缀按前缀长度设置Hash表,并将前缀值有序存放在表结点中。不仅可以进行前缀长度的二分查找,同时又是其它前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。实践证明该算法具有较好的时空效率,可以较好地提高路由查找速度。

一种新的二分路由查找方法

分析路由表前缀间的覆盖关系特征,证明了前缀覆盖级别集合符合二分查找特性,提出一种基于前缀覆盖级别的二分路由查找算法,和传统基于前缀长度或者前缀值的线性或者二分查找算法相比,在查找性能、路由更新和存储空间方面具有优势,本方法可以在O(log2m ax_level+1)个TCAM时钟周期内完成1次路由查找,其中m ax_level为最大的前缀覆盖级别,目前m ax_level不超过7;本方法无需前缀扩展和排序,支持路由增量更新;另外,传统TCAM路由查找相比,可以节省功耗约50%.

基于哈希表的最长前缀匹配算法改进

在实际应用中经常需要查找某IP地址其在数据库中对应的真实的物理地址,而数据库的数据量往往很大,显然直接去查询数据库不能满足大量数据以及高速查找的要求。在最长前缀匹配算法的基础上,提出了一种基于哈希查找表的IP地址查找算法。将数据库中的信息建立为一个哈希表,并将点分十进制IP地址的部分前缀作为键值,映射到哈希表中的一条记录,从而得到所需的信息。最后用C#语言实现了该算法,实验表明该算法具有很高的效率。

自相似活跃子网前缀空间的路由查找

IP地址查询是路由器的基本工作,活跃IP和子网前缀地址空间是重尾分布且自相似的,而针对这种重尾分布的IP地址和前缀可以用于对路由查找进行统计优化.文章分析并验证了活跃IP地址空间的特点和子网前缀空间分形自相似特性,活跃IP的子网前缀在不同的聚类规模上的次序统计量服从Pareto分布,主干路由表项的次序统计量也近似服从Pareto分布.该文提出了一种基于活跃度排序的路由逐次查找算法———SOSL,对IP地址查询进行了优化,在该文的模拟实验中,活跃路由表的规模、刷新周期和活跃度判定下限间存在一些对数线性关系,使得作者可以以很小的活跃路由表来实现全部路由查找需求的99%;为SOSL实现中最关键的活跃路由表排序问题提出了一个基于计数器溢出的方案,复杂度为O(1).对比发现该文的算法与TCAM结合能够提高TCAM的效率,高效地控制活跃路由表的规模,易于硬件实现.

一种基于最长前缀匹配的分段式IP查表方法

基于最长前缀匹配,本文提出了一种新的IP转发表搜索方法。该方法在实现过程中依赖的主要硬件是一片逻辑控制器以及高速的DDRII(Double Date RateⅡ)SDRAM(Synchronous Dynamic Random Access Memory)。依据研究IP地址前缀所得出的规律,将IP地址前缀存储到DDRII中。该搜索方法能够将搜索时间限制在两个DDRII读周期之内,不超过4ns;同时保证转发表更新时间小于512ns。

IP路由缓存技术研究

针对目前用于IP路由查找的地址缓存技术和前缀缓存技术的局限性,分析了骨干网路由表前缀重叠特征,提出了一种基于阈值的IP路由缓存方法,该方法结合了地址缓存和前缀缓存技术,无需进行前缀扩展,克服了地址缓存技术缓存空间要求过大、前缀缓存技术无法缓存内部前缀节点的问题,在缓存空间、缓存命中率、缓存公平性以及路由增量更新方面具有优势;仿真实验表明对于路由条目超过260000的路由表,缓存空间大小为30000,选择阈值K=4时97%以上的节点可实现1:1缓存,其余节点采用地址缓存,缓存失效率小于0.02,可以用小的缓存空间实现高速线速转发.

一种基于BGP路由控制网络优化仿真设计

介绍了多种BGP的路由控制工具.在eNSP仿真环境下,设计网络拓扑,部署BGP协议,采用多种路由控制技术,实现BGP路由的精确引入、路由过滤、属性选路等高级路由控制,对配置过程、配置命令进行分析,并给出明确的验证结果.实践证明,仿真实验可以用来指导实物环境下的网络设备配置,有效解决实际网络中BGP协议部署的相关问题.

聚合Nyberg-Rueppel签名数据的一种源自治系统认证方法

IP前缀劫持对互联网安全构成重大威胁.为防范IP前缀劫持,公认的有效手段之一是基于数字签名进行源自治系统认证.由于带宽容量问题,传统的源自治系统认证机制不能支持认证信息的在线发布和验证.为支持认证信息的在线发布和验证,应尽可能降低地址证明创建和验证过程中需要在线传送的数据量.本文充分利用Nyberg-Rueppel签名的特点,将地址证明创建过程中产生的大部分数据进行聚合以降低需要在线传输的数据量,以期克服源自治系统在线验证的带宽障碍,给出了算法完成系统初始化、地址证明的创建、以及地址证明的验证.这种机制所涉及的认证信息字节长度短,约为426 Bytes.由于大幅度降低认证信息的字节长度,本机制能够支持源自治系统认证信息的在线发布和验证.

基于有限前缀扩展和多Hash函数的动态IP路由查找算法

该算法根据IP路由表的分布特征将前缀有限扩展为三种长度,并用算法所提出的最大熵判定法选取多个Hash函数,将扩展后的前缀映射到三个Hash表的不同级别.在查找过程中算法根据三个Hash表的命中率动态计算查找代价,并据此调整对三个Hash表的搜索顺序.算法支持增量更新,适于软件实现和硬件流水实现.实验表明,对128K前缀的真实转发表算法仅约需3.7M字节,平均每次查找仅需约1.1次访存,而且路由更新时间较小.

一种新的快速IPv6路由查找算法

在分析原有查找算法的基础上,结合IPv6地址结构和骨干路由表特点,提出一种新的快速IPv6路由查找算法。基于Hash表和多分支Trie树结构,将最常用到的路由前缀按前缀长度放置在Hash表中,并按前缀值有序存放在表结点中,不仅可以进行最常用前缀的二分查找,同时又是其他前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。分析及测试证明该算法具有很好的时间效率,更新速度很快。

IP地址分配方法的探究与改进

本文通过对无分类编址的IP地址进行子网划分的探究，总结出了两种子网Ip分配方法，并对两种方法的优缺点进行研究，着重指出了存在的问题，最后提出了两种方法相结合的改进意见，并通过例证验证了改进后的效率。

高性能路由器FIB压缩方法

高性能IP路由器使用复杂的转发表查找算法优化查找时间、存储空间和更新时间.在对ORTC压缩算法及信息熵理论研究的基础上,提出了一种基于多位特里算法,通过消除信息冗余的方式实现对FIB的压缩方法.该方法具有不改变路由语义和外部路由器行为特征,在典型的路由器应用环境下,可以节省约50%的存储空间,路由查找效率可提高25%.

基于多分支优先级树的IP路由查找算法

针对现有路由表查找方法效率低的问题,提出了一种基于多分支优先级树的数据查找算法。该算法将优先级较高的前缀依次存储在原多分支树的虚节点上,将需要进行扩展的前缀存储在辅助存储结构中,从而在路由查找时,该方法可在内部节点找到最长前缀匹配而无需查找到叶子节点,同时避免了在路由表更新时对路由表的重建。仿真结果表明,提出的查找算法能够有效减少在对路由表查找、插入和删除操作所需的内存访问次数,并大幅度地提高路由查找及其更新速率。