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

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

完全无冲突散列IP分类算法研究

介绍了IP分类技术研究的最新成果，以及IP分类的典型算法。提出了一种基于完全无冲突散列(hash)和跳转表Trie树(NHJTTT)的IP分类算法，通过分析比较，本文提出的算法无论是时问性能还是空间性能均优于无冲突散列查找算法和Grid of Tries算法，文中通过仿真给出了最终的分类效果。最后对提出的算法在虚拟环境下做了评判。     

基于跳转表Trie树的IP分类算法

介绍了IP分类技术研究的最新成果及IP分类的典型算法，提出了一种基于跳转表Trie树JTTT的IP分类算法，通过分析比较，该算法无论是时间性能还是空间性能均优于位图交叉算法。同时，FPGA技术的飞速发展和数据处理速度的提高，使得可以用FPGA和SRAM进行处理，文中通过仿真给出了最终的分类效果，最后对提出的算法在虚拟环境下作了评判。     

一种基于哈希和跳转表的IP分类算法

文章介绍了IP分类技术研究的最新成果,以及IP分类的典型算法。提出了一种基于哈希(Hash)和跳转表Trie树JTTT(JumpingTableTrie-Tree)的IP分类算法,该算法和核心有两点:一是将源/目的端口和协议三域构造成一个哈希函数,因为该三域的交叉组合较少;二是将源/目的IP地址分割为两块构成跳转表和Trie树。通过分析比较,文章提出的算法无论是时间性能还是空间性能均优于GridofTries算法,文中通过仿真给出了最终的分类效果。最后该文对提出的算法在虚拟环境下做了评判。     

基于Trie树的哈希表

受到AC算法与链式哈希的启发,提出了一种基于Trie树的哈希表。该算法通过增加一个后继状态计数器,能够为后续的查找等运算提供更加简单和快速的信息。分析与实验表明该算法具有较高的效率、较强的稳定性,且降低了能耗。     

路由查找算法研究综述

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

利用频率特征的Trie树索引快速构造算法

随着物联网技术的日益成熟和云计算标准的确立以及各种智能终端的大规模出现,互联网数据呈指数增加,为数据建立索引至关重要,为此提出一种基于词频的Trie树索引快速构造算法,首先对索引字符串进行排序,然后对排序文件进行预处理,预处理生成一个三元组,分别由相同字符横向偏移、纵向偏移及字符组成. 快速算法依次扫描预处理数据的每一列,根据三元组的偏移跳过相同的字符前缀. 实验结果显示,本算法的时间明显少于传统构造算法,优于Aoe的双数组Trie构造算法.     

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

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

A Non-Collision Hash Trie-Tree Based Fast IP Classification Algorithm

With the developemnt of network applications,routers must support such functions as firewalls,provision of QoS,traffic billing,etc.All these functions need the classification of IP packets,according to how different the packetes are processd subsequently,which is determined.In this article,a novle IP classification algorithm is proposed based on the Grid of Tries algorithm.The new algorithm not only eliminates original limitations in th case of multiple fields but also shows better performance in regard to both and space.It has better overall performance than many other algorithms.     

一种适用于多维的快速IP分类算法

网络应用的发展要求路由器必须有能力支持防火墙、提供QoS、流量计费等一系列功能,这些功能都要求路由器对IP包进行分类以完成对数据包的不同处理.在Grid of Tries算法的基础上,提出了一种新的IP分类算法.该算法不仅克服了Grid of Tries算法在多维IP分类方面的局限性,而且在时间和空间性能上都优于Grid ofTries,是目前综合性能比较好的分类算法.