一种基于Trie转发表的虚拟路由IP查找方法

为了使路由器在有限的存储资源中支持更多的虚拟路由实例,提出一种基于多分支Trie的动态共享转发表结构,并在此结构上实现了相应的虚拟路由IP查找方法.该方法采用多比特位的IP查找,减少了转发表中结构性消耗及访存次数,同时该方法具有自适应性,能够根据已有的IP规则集,通过动态规划构造空间最优的Trie.仿真结果表明,与已有的共享转发表结构相比,该方法节约了大量的存储空间,并且能够实现快速的IP查找.     

基于前缀扩展的三级索引路由查找算法

根据路由表前缀扩展特性,采用特殊的结构构造索引表,提出了一种基于3级索引的储存表查找方法,进行流水线方式的并行查找。引入了缓冲池的思想,提出了一种改进的路由表更新方法,同时该算法支持动态更新。与基于压缩算法相比,该算法数据结构简单;与传统TCAM路由查找相比,可以节省约40％的功耗。此外,该算法在查找性能、路由更新和存储空间方面也有很大优势,能够达到最少访问一次存储器．最多需要访问3次实现处理一个IP数据包．     

用静态链表和逆序插入算法构成的动态查找表

目前的动态查找表都是树结构,对于结点量很大的情况,其所需存储空间过大且查找效率低的缺点突出.对此.文章设计了一种新的动态查找表,将有序静态链表结构与结点群"逆序插入"算法相结合,相比树结构动态查找表有两个优势:1.所需存储空间小;2.结点群的结点数越多,则动态查找效率越高.该方法的要点是:先将已有结点用静态链表构造出一个有序表,简称"主表".若某"结点群"要插入该主表中,需将该结点群用静态链表构造成一个有序"副表",然后用逆序算法对副表中各结点查找其在主表中的插入点,并从对应的插入点与主表进行链接,最后将链接好的主表和副表一次性收集到一个新的静态链表中.类似的"逆序删除"也可以删除整个副表的结点.     

一种快速IPv6路由查找方案

提出了一个可硬件实现的基于分段的快速IPv6路由查找方案.该方案支持快速的IP地址查找,并能有效地对路由前缀进行插入和删除操作.方案采用基于比特位置区分的压缩算法,与其它的 IPv6 路由查找方案相比较,所需存储器空间小,路由查找的平均时间少.如果采用SRAM流水线查找,可实现 125×106次/秒的查找速度.由于缺少实际的 IPv6路由前缀,该文生成了模拟路由前缀数据库.仿真试验结果表明:文章提出的方案具有合理的查找时间、空间和更新复杂度,容易硬件实现.     

高效Unicode／GB编码转换算法的设计和实现

为了在存储空间和运算能力严格受限的嵌入式系统中实现Unicode和GB2312编码的相互转换,设计了一种高效率的编码转换算法.该算法通过提取数据表中公共部分实现压缩存储,采用索引和二分法查找相结合的方式进行快速查找,和传统的转换算法相比约节省25%的存储空间,查找效率最高约提高3倍.该算法可在无操作系统支持的嵌入式系统中实现汉字编码之间的高效率的转换.     

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

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

基于TCAM技术的高速路由查找方案

基于TCAM技术提出一个高速路由查找方案。该方案可以达到每秒钟100M次的查找速度，满足OC48和OC192接口的线速转发要求。方案使用了索引表和映射表的二级结构存储路由的下一跳信息，大大减小了存储空间，同时对IPv6具有很好的扩展性。对TCAM的路由更新问题进行了讨论，提出一个最坏情况下O(W／2)的更新算法(形为前缀长度集合的数目)，有效地提高了TCAM的更新性能。     

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

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

CKDB-Tree:一种有效的高维动态索引结构

在高维数据空间中提出了一种新的索引结构:CKDB-Tree(Compact KDB-Tree),该索引结构采用一种新的分裂策略,在进行分裂时,引入插入安全点和删除安全点的概念,不仅考虑到将来的数据,而且对已经进行索引的数据也进行考虑;给出了CK-DB-Tree的定义以及节点结构的特点,针对CKDB-Tree,给出了相应的插入、查找、删除操作的算法;对该索引结构的存储性能进行定量分析和推理;最后经实验证明,CKDB-Tree是高维空间中一种有效的动态索引结构。     

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

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

A longest prefix first search tree for IP lookup

The IP lookup mechanism is a key issue, in the design of IP routers. IP lookup is an important action in a router, which finds the next hop of each incoming packet with a longest-prefix-match address in the routing table. This work places the routing table on a longest prefix first search tree, which is constructed as a heap-like structure by the prefix length. A router using this scheme has fewer memory accesses when executing IP lookup than a router designed according to the Trie [E. Fredkin, Trie Memory, Communication of the ACM 3 (1960) 490–500], Patricia [K. Sklower, A tree-based routing table for Berkeley Unix, in: Proceedings of the USENIX Conference, 1991, pp. 93–99] or Prefix tree [M. Berger, IP lookup with low memory requirement and fast update, in: Proceedings of IEEE High Performance Switching and Routing, 2003, pp. 287–291]. Some nodes of the proposed tree can include two entries of the routing table to decrease the number of tree nodes. For instance, a routing table with 163,695 entries can be held in the proposed tree with 156,191 nodes. Furthermore, an improved scheme is presented to partition a tree into several smaller trees. The simulation reveals that the scheme not only lowers the tree height effectively but also scales well to IPv6 addresses.     

Routing table partitioning for speedy packet lookups in scalable routers

Most of the high-performance routers available commercially these days equip each of their line cards (LCs) with a forwarding engine (FE) to perform table lookups locally. This work introduces and evaluates a technique for speedy packet lookups, called SPAL, in such routers. The BGP routing table under SPAL is fragmented into subsets which constitute forwarding tables for different FEs so that the number of table entries in each FE drops as the router grows. This reduction in the forwarding table size drastically lowers the amount of SRAM (e.g., L3 data cache) required in each LC to hold the trie constructed according to the prefix matching algorithm. SPAL calls for caching the lookup result of a given IP address at its home LC (denoted by LC/sub ho/, using the LR-cache), such that the result can satisfy the lookup requests for the same address from not only LC/sub ho/, but also other LCs quickly. Our trace-driven simulation reveals that SPAL leads to improved mean lookup performance by a factor of at least 2.5 (or 4.3) for a router with three (or 16) LCs, if the LR-cache contains 4K blocks. SPAL achieves this significant improvement, while greatly lowering the SRAM (i.e., the L3 data cache plus the LR-cache combined) requirement in each LC and possibly shortening the worst-case lookup time (thanks to fewer memory accesses during longest-prefix matching search) when compared with a current router without partitioning the routing table. It promises good scalability (with respect to routing table growth) and exhibits a small mean lookup time per packet. With its ability to speed up packet lookup performance while lowering overall SRAM substantially, SPAL is ideally applicable to the new generation of scalable high-performance routers.     

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

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

Fast IP routing lookups for high performance routers

The key to the success of the next generation IP networks to provide good services relies on the deployment of high performance routers to do fast IP routing lookups. In this paper, we propose a new algorithm for fast IP lookups using a so-called two-trie structure. The two-trie structure provides the advantages in that less memory space is required for representing a routing table than the standard trie while it still provides fast IP lookups. Based on the simulation result, the memory space can be saved around 27% over the standard trie while a lookup operation takes 1.6 memory accesses in the average case and 8 memory accesses in the worst case. Also, the structure is not based on any assumptions about the distribution of the prefix lengths in routing tables. Thus, increasing the lengths from 32 to 128 bit (from IPv4 to IPv6) does not affect the main structure.     

基于LSOT的高速IP路由查找算法

由于因特网速度不断提高、网络流量不断增加、路由表规模不断扩大，IP路由查找已经成为制约路由器性能的重要原因，因而受到广泛重视。目前人们已经提出几种算法用于解决IP路由查找问题，但均不能完全满足核心路由器的要求。该文提出一种基于LSOT的IP路由查找方法，它使用可变大小段表和偏移量表，能适应SRAM和FPGA芯片内存储器容量的变化，具有查找速度高、更新时间快、存储代价低、易于实现等特点，使用FPGA设计能满足10Gbps端口速率核心路由器环境的要求，使用ASIC设计能满足40Gbps端口速率核心路由器环境的要求。     

Fast binary and multiway prefix searches for packet forwarding

Backbone routers with tens-of-gigabits-per-second links are indispensable communication devices to deploy on the Internet. The IP lookup operation is the most critical task that must be improved in routers. In this paper, we first present a systematic method to compare prefixes of different lengths. The list of prefixes can then be sorted and stored in a sequential array, which is contrary to the linked lists used in most of trie-based structures. Next, fast binary and multiway prefix searches assisted by auxiliary prefixes are proposed. We also developed a 32-bit representation to encode the prefixes of different lengths. For the large routing tables currently available on the Internet, the proposed multiway prefix search can achieve the worst-case number of memory accesses of three and four if the sizes of the CPU cache lines are 64 bytes and 32 bytes, respectively. The IPv4 simulation results show that the proposed prefix searches outperform the existing IP lookup schemes in terms of lookup times and memory consumption. The simulations using IPv6 routing tables also show the performance advantages of the proposed binary prefix searches. We also analyze the performance of the existing lookup schemes by concurrently considering the lookup speed, the update speed, and the memory consumption. Although the update speed of the proposed prefix search is worse than the dynamic routing table schemes with log(N) complexity for a table of N prefixes, our analysis shows that the overall performance of the proposed binary prefix search outperforms all the existing schemes.     

XOR-Based Schemes for Fast Parallel IP Lookups

An IP router must forward packets at gigabit speed in order to guarantee a good quality of service. Two important factors make this task a challenging problem: (i) for each packet, the longest matching prefix in the forwarding table must be quickly computed; (ii) the routing tables contain several thousands of entries and their size grows significantly every year. Because of this, parallel routers have been developed which use several processors to forward packets. In this work we present a novel algorithmic technique which, for the first time, exploits the parallelism of the router also to reduce the size of the routing table. Our method is scalable and requires only minimal additional hardware. Indeed, we prove that any IP routing table T can be split into two subtables T₁ and T₂ such that: (a) |T₁| can be any positive integer k ≤ |T| and |T₂| ≤ |T| - k + 1; (b) the two routing tables can be used separately by two processors so that the IP lookup on T is obtained by simply XOR-ing the IP lookup on the two tables. Our method is independent of the data structure used to implement the lookup search and it allows for a better use of the processors L2 cache. For real routers routing tables, we also show how to achieve simultaneously: (a) |T₁| is roughly 7% of the original table T; (b) the lookup on table T₂ does not require the bestmatching prefix computation.     

LinuxIP路由查找算法研究

随着Internet技术的发展,尤其是网络带宽的不断扩展,在IP路由器中,当数据包达时,需要极快的路由查找速度,但现存的路由查找受其设计算法的限制,越来越难以满足这种需要,本文在分析了Linux下的路由查找机制的基础上,提出了一种改进的基于软件的高效率路由查找算法。     

基于异构网络处理平台的可配置并行路由查表算法研究

基于通用多核的网络转发性能难以满足高速网络流量线速处理的需求.软硬件结合的异构网络处理平台以其较高的性能和灵活性在网络处理领域得到广泛应用,但是如何基于异构平台实现高效的路由查表算法仍需进行深入研究,多核资源利用率低、共享冲突严重和访存次数多的问题是制约传统路由查表算法在异构网络处理平台实现性能提升的主要问题.为此,基于异构网络处理平台（network processing platform,简称NPP)提出一种可配置并行路由查表机制（configurable parallel lookup,简称CPL).CPL中的多线程并行查找和路由表的多副本存储技术在提高多核资源利用率的同时,实现了零冲突访问路由表项.此外,考虑到不同场景下路由前缀分布的差异,CPL支持通过配置对多级路由表的组织结构进行调整,从而有效地减少了路由表访问次数.最后在NPP上,对CPL和传统的查表算法进行性能测试和对比,验证了CPL的可用性和高效性.     

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

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