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

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

采用分段哈希方法的IPv6路由查找算法研究

分析了现有IPv4路由表查找算法和IPv6地址的特性以及主干网路由表的前缀分布特点,借鉴LFT哈希表结构简单、查找快速的特点,提出了以32bits为查找路由前缀起点的分段哈希表和多分支Tile树相结合的IPv6路由查找算法.该算法结构简单、查找效率高、易于更新,多数情况下只需一次内存访问就可查找到路由信息,提高了IPv6主干网路由器转发速度,以满足下一代互联网IPv6发展的需求.     

路由查找算法研究综述

随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps～10Gbps.这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀匹配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了各种查找算法,并对它们进行了详细的分析和比较,最后指出了进一步的研究方向.     

基于压缩Trie树的以太网地址查找结构

介绍了一种基于hash表和压缩trie树的查找与更新方法,每个hash桶中的4个地址节点按照trie树的方式组织,并压缩成一个25位字。基于FPGA实现时查找速度为133MSPS,IXP1200的一个微引擎每秒可完成1M次转发表更新。与采用片上嵌入式存储器的以太网交换芯片相比,查找过程可以减少一半的存储器访问带宽,转发表可放置到大容量片外存储器中,从而减少交换芯片面积和成本,显著降低hash表的冲突率。     

一种基于哈希表和Trie树的快速IP路由查找算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。论文提出了一种基于8比特的前向查找表(LFT)和7比特的简单二进制回退查找Trie树(HBT)的IP路由查找算法。算法综合考虑了IP地址的分布特点,兼顾了查找速度、存储空间利用、硬件实现,以及向IPv6过渡等几个因素。具有算法简单、查找速度较快、存储空间利用率较高、易于扩展和便于硬件实现等特点。     

高速路由器中基于树型结构路由查找算法的研究与实现

本文在比较各种基于树型结构查找算法的基础上提出了一种改进的路由查找算法,该算法具有查找速度快、所需存储空间小、更新速度快、硬件实现简单等特点,能够满足10Gbps核心路由器环境的要求。     

Trie树路由查找算法在网络处理器中的实现

Trie树数据结构的实现方法灵活,所需存储器空间小,是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s线速度网络处理器中微引擎的设计要求,提出一种基于最优平衡、多层存储的Trie树路由查找算法。建立一种平衡的压缩树结构,将该树中相邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度,以空间换取时间,从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现Trie路由查找算法,实验结果表明,单个微引擎的查找速度为4.4 Mb/s,能达到节省存储空间、提高查找效率的效果。     

一种改进的IPV6最长前缀匹配路由查找算法

本文就是在研究已有算法的基础上,结合IPv6地址的特征以及路由表中前缀的分布规律,提出了一种改进的、基于索引表和Trie树的查找算法,该算法在时间复杂度和空间复杂度上表现出了较好的性能。     

一种基于Trie的IPv6路由查找方案

随着Internet的迅猛发展,IPv6技术必将成为主流.于是,如何高效地在路由表中查找匹配128位IPv6地址,成为了IPv6 技术发展的一大制约因素.经大量研究表明,Trie数据结构是实现高速路由查找和报文转发的关键.结合IPv6的地址结构特点,设计出基于Trie数据结构的查找算法,提高了路由查找效率以及报文转发速度.     

散列索引多分支Trie树快速路由查找算法

路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树。在这种结构中进行IP路由查找,其存储器访问次数最多为7次,而且还具有易于更新、易于扩展等特点。     

基于二分法搜索hash表的快速IP路由查找算法

路由器设计中,ＩＰ地址的路由查找算法设计很重要,算法的性能将直接影响路由器的性能。本文对Ｗａｌｄｖｏｇｅｌ等人提出的二分法查找ｈａｓｈ表算法进行了改进,使路由查找效率从至多５次ｈａｓｈ表访问减少为至多３次ｈａｓｈ表访问。     

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

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

一种新的IP路由表快速搜索技术

随着因特网的飞速发展以及128位地址的IPv6的出现,路由表变得日益庞大,这给IP目标地址的查找速度提出了更高的要求。另外最长前缀匹配技术的出现使过去传统哈希搜索技术不再适用。为此,论文针对现有IP查找技术的缺点和不足,提出了一种新的二叉搜索算法。文中还对新的路由表数据结构进行了详细描述,并给出了该算法的一种软件实现方案。这种算法具有良好的可扩展性,不需要对现有协议进行改动,在实践中证明其具有良好的报文转发性能。     

快速IPv6路由查表算法

IPv6网络能够提供高质量服务的关键在于设计出能够进行快速查表的高性能的路由器。由于需要进行最长前缀匹配,路由表的查找与更新向来是高速路由器的瓶颈。在IPv6网络中,地址从IPv4的32位扩展到128位,进行最长前缀匹配变得更加困难。该文主要根据Nen-FuHuang等提出的IPv4算法提出一种基于IPv6地址分布的IPv6的路由查表算法。该算法每次查表最多只需要访问三次存储器,而且使用的存储器比较小,仅需要2M多字节。     

最长前缀匹配查找的索引分离trie树结构及其算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。索引分离trie树结构建立了具有k比特的一级索引,m比特的二级索引和步宽为s、最大深度为m/s的多分支trie树结构。在这种数据结构中进行最长前缀匹配查找的算法复杂度为:O(m/s+2)。它具有算法简单、查找速度快、易于更新、便于向IPv6过渡等特点,是一种综合性能较好的快速最长前缀匹配查找算法。     

命名数据网络中基于Hash映射的命名检索

命名数据网络(NDN)是一种以内容为中心的新型网络架构,可有效提高网络资源的共享利用率。但与传统的IPv4、IPv6相比,NDN命名的长度更长且具有可变性,因此实现NDN中命名的快速检索对提高网络性能具有重要作用。为此,提出一种基于Hash映射的分治命名检索方法,将命名分解为组件并进行CRC32映射后分别存储在相应的Hash表中,对Hash表中的数据进行快速排序后使用二分查找定位Hash值,并利用排序后Hash表的递增数据结构进行Hash冲突的快速检测,通过对Hash值添加标志位的方法解决冲突问题。实验结果表明,相比建立命名前缀树的检索方法,该分治命名检索方法可将NDN命名的存储空间压缩近65%,并且大幅提升了检索速度。     

一种基于Hash表的XML模式快速提取算法

为快速获取XML文档的模式信息,提出一种基于Hash表的XML模式提取算法。该算法首先将XML文档转换为一棵XML文档树;然后遍历这棵文档树,将相关模式信息存储到一个Hash表中;最后,对Hash表中的信息进行处理,得到XML模式的DTD表示形式。将文中的算法用VC++实现,实验结果表明该方法是可行有效的,而且在保证XML模式提取结果正确性的同时,还有效地简化了模式表示形式。