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

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

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

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

基于完全无冲突哈希的IP数据包分类算法研究

介绍了IP分类技术研究的最新成果,以及IP分类的典型算法。提出了一种基于完全无冲突哈希和跳转表Trie树(NHJTTT:Nol-collisionHashandJumpingTableTrie-Tree)的IP分类算法,通过分析比较,该文提出的算法无论是时间性能还是空间性能均优于GridofTries算法,文章通过仿真给出了最终的分类效果。最后该文对提出的算法在虚拟环境下作了评判。     

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

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

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

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

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

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

基于无冲突哈希Trie树的IP分类算法的研究

本文提出了一种基于无冲突哈希Trie树的IP分类算法。该算法不仅克服了GridofTries算法在多维IP分类方面的局限性，而且在时间和空闻性能上都优于GridofTries，是目前时间复杂性和空间复杂性方面综合性能比较好的分类算法。     

使用Hash表和树位图的两级IPv6地址查找算法

为了提高IPv6地址查找效率,在分析IPv6路由前缀长度分布规律的基础上,提出了基于哈希表及树位图(Tree-bitmap)的两级IPv6地址查找算法.算法将长度为16,32,48和64比特的前缀分别存储在4个Hash表中,其余前缀的前16,32和48比特利用已有的Hash表存储,剩余的不足16比特的部分前缀利用树位图存储,并将树位图的入口地址保存在Hash表中.IP地址查找时在Hash表和树位图中进行两级查找.实验表明,该查找算法的平均内存访问次数为1～2,最坏情况下为7,适用于高速IPv6地址查找.     

基于无冲突哈希Trie树的IP分类算法的研究

本文提出了一种基于无冲突哈希Trie树的IP分类算法。该算法不仅克服了GridofTries算法在多维IP分类方面的局限性,而且在时间和空间性能上都优于Grid of Tries,是目前时间复杂性和空间复杂性方面综合性能比较好的分类算法。     

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

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

VOIP系统中地址映射表查询算法的研究与实现

基于十叉树的存储结构及其查询的方法，提出了适用于COID的地址映射表查询算法，设计了地址映射表的数据类型与存储结构，并对几种不同的地址映射表的查算法进行了研究，试验表明，采用树形存储结构构成的地址映射表，其相应的查算法可以获得较短的耗费时间。     

用于控制器保护的防火墙规则的三叉树算法

为提高防火墙安全规则的查找速度,提出了一种面向IP地址集合处理的时间复杂度为O([log32N])的三叉树查找算法,N为安全规则数。用空间分析法解决规则冲突,并给出规则树的生成算法,该方法适用于控制应用的可靠性分析和安全完整性等级验证的要求。     

多组共享式应用层组播算法

利用单播传输路径的重叠特性所构建的叠加组播树可以部分模拟IP层的有源组播,而单组会话中成员主机在网络中分布的不足可以通过多组会话中的主机来弥补。该文根据这一特点提出了一种基于多组会话成员共享的应用层组播算法,该方法采用了源主机和接收主机之间的单播传输路径和多组协作机制,为每个组播源建立单独的组播树。通过模型分析,该文算法所构建的组播树可以比单组会话计算方法获得较大优势的链路利用率。     

基于短前缀长度分割的高速二维分组分类算法

分组分类是路由器根据IP分组的多个域，从分类器数据库中匹配每个输入分组，确定分组转发规则的技术，分类器为实现因特网新业务提供了统一的方式，这些新业务包括：防火墙，网络地址翻译等，二维分组分类问题在未来的因特网体系结构中占有十分重要的地位，目前，人们已经提出了几种分组分类算法，但没有一种是理想的，提出基于短前缀长度分割的二维分组分类算法，它使用短前缀长度分割（SPLS）技术对分类器集合进行分割，使得分割后的小分类器子集合可以使用巳有快速IP路由查找方法进行查找，实现时以多叉树作为基本数据结构，实验显示它具有存储需求小，平均查询时间快，更新时间快，适合于大的分类器等特点，是一种较好的二维分组分类算法。     

基于用户行为分析的应用层组播树生成算法

应用层组播采用终端主机转发数据的方式,在一对多的媒体内容分发方面具有广阔的应用前景．与IP组播相比,应用层组播具有灵活和易实施的特点,但是因为终端主机可以自由地退出组播树,应用层组播也存在数据传递易中断的缺点,这对实时性要求严格的视频直播应用的影响尤为严重．通过对超过1000万条实际视频直播系统的真实用户记录进行统计分析,发现用户平均剩余在线时间随着已经在线时间的增大而增大,并据此提出了一种适用于视频直播的应用层组播树生成算法．模拟结果表明,算法对减少视频直播应用下应用层组播树的数据传递中断次数有明显作用．     

基于代理的覆盖网组播生成树算法研究

利用覆盖网组播技术构建组播服务平台是一种可行的提供组播服务的方案.基于代理的覆盖网组播兼具覆盖网组播的灵活性和IP组播的高效性的特点.结合节点的带宽、处理延迟和节点间的通信延迟给出一个完善的基于代理的覆盖网组播模型,根据此模型设计了求节点度受限的具有最小平均延迟的组播转发树生成算法.探讨了主机节点在进行数据分组复制转发时的转发顺序对平均延迟的影响,给出并证明了主机节点对数据分组复制转发的最优策略.通过仿真实验验证了所给算法和最优复制转发策略的有效性.     

IP子网物理拓扑结构发现研究

将IP子网的拓扑结构看做一棵拓扑树,对互连的交换机的地址转发表中的交换机的MAC地址进行了分析,给出一组判定定理用以确定交换机间的连接关系。基于上述定理,提出了一个新的自顶向下的拓扑发现算法,该算法能够利用地址转发表构造出整个网络拓扑结构。与已有的物理拓扑发现算法相比,该算法具有高效、实用的优点。     

An efficient IP address lookup algorithm based on a small balanced tree using entry reduction

Due to a tremendous increase in internet traffic, backbone routers must have the capability to forward massive incoming packets at several gigabits per second. IP address lookup is one of the most challenging tasks for high-speed packet forwarding. Some high-end routers have been implemented with hardware parallelism using ternary content addressable memory (TCAM). However, TCAM is much more expensive in terms of circuit complexity as well as power consumption. Therefore, efficient algorithmic solutions are essentially required to be implemented using network processors as low cost solutions.Among the state-of-the-art algorithms for IP address lookup, a binary search based on a balanced tree is effective in providing a low-cost solution. In order to construct a balanced search tree, the prefixes with the nesting relationship should be converted into completely disjointed prefixes. A leaf-pushing technique is very useful to eliminate the nesting relationship among prefixes [V. Srinivasan, G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems 17 (1) (1999) 1-40]. However, it creates duplicate prefixes, thus expanding the search tree.This paper proposes an efficient IP address lookup algorithm based on a small balanced tree using entry reduction. The leaf-pushing technique is used for creating the completely disjointed entries. In the leaf-pushed prefixes, there are numerous pairs of adjacent prefixes with similarities in prefix strings and output ports. The number of entries can be significantly reduced by the use of a new entry reduction method which merges pairs with these similar prefixes. After sorting the reduced disjointed entries, a small balanced tree is constructed with a very small node size. Based on this small balanced tree, a native binary search can be effectively used in address lookup issue. In addition, we propose a new multi-way search algorithm to improve a binary search for IPv4 address lookup. As a result, the proposed algorithms offer excellent lookup performance along with reduced memory requirements. Besides, these provide good scalability for large amounts of routing data and for the address migration toward IPv6. Using both various IPv4 and IPv6 routing data, the performance evaluation results demonstrate that the proposed algorithms have better performance in terms of lookup speed, memory requirement and scalability for the growth of entries and IPv6, as compared with other algorithms based on a binary search.     

按需分枝组播

在分析总结目前IP组播路由研究的主要成果基础上,提出了一个新的组播路由方案,按需分枝组播.它采用了一种全新的组播树维护方式,即组播树由树上的部分节点(关键节点)维护,不同于现有的组播树由所有树上节点维护的方式,从而节省了网络资源.     

基于模糊匹配策略的城市中文地址编码系统

在研究空间数据地址编码技术的基础上,根据城市地址数据库特定存储格式,选取适于城市中文地址的切分方案,提出一种基于K叉地址树的模糊匹配策略,将地址数据以K叉树形式进行存储。采用分支定界思想探测并排除无效匹配结点,并应用模糊规则对匹配结果进行评价及筛选,从而提高地址匹配的效率和准确度。应用杭州市1∶10 000矢量地图数据验证了该编码系统的有效性。