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.     

Large-scale SRAM-based IP lookup architectures using compact trie search structures

SRAM-based pipelined architectures for high-speed IP lookup using Field Programmable Gate Arrays (FPGAs) has recently attracted a great deal of attention from researchers. Due to the limited amount of on-chip memory and the number of I/O pins of FPGAs, compact data structures providing high memory efficiency are in great demand.     

IP报文分类算法概述

Internet的高速发展要求提供高性能的P流分类算法以更好地为防火墙、QoS、流量工程、资源预留、网络地址转换等提供服务。由于IP报文分类算法的多域特征,因此其具有相当的难度。研究者提出了很多报文分类算法,本文将这些算法概括为5类：基于Trie树的算法、基于空间分割的算法、启发式算法、基于硬件实现的算法和其他算法,并对IP报文分类算法的思想、原理和过程进行了介绍和分析,说明了这些算法之间的联系,并对这些算法在搜索和更新的时间性能、空间性能、适用性范围和优缺点等进行了分析和比较。作为总结,本文还对IP报文分类算法研究的方法和趋势进行了分析和总结。     

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

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

Build shape-shifting tries for fast IP lookup in O(n) time

Most data structures for packet forwarding are optimized for IPv4, and less capable of handling IPv6 routing tables. Shape-Shifting Trie (SST) is specifically designed to be scalable to IPv6. To reduce the worst-case lookup time that is proportional to the height of SST, it is desirable to construct a minimum-height SST. Breadth-First Pruning (BFP) algorithm takes O(n²) time to construct a minimum-height SST, where n is the number of nodes in the binary trie corresponding to the routing table. In this paper, we propose a Post-Order Minimum-Height Pruning (POMHP) algorithm that takes only O(n) time to construct a minimum-height SST. We further propose nodes merging algorithm to cut down SST size without affecting SST height.     

高速IP路由器技术

文中介绍了两种应用于INTERNET网络的技术:吉比特路由器和IP交换,包括它们的基本原理和优点。这些技术将在今后的网络世界中起到重要作用。     

IP分类技术研究综述

作为网络互联的核心设备，路由器必须以吉比特乃至更高的速度对IP包进行处理，网络应用的发展要求路由器除了具备传统的路由转发功能之外，还必须有能力支持防火墙，提供QoS，流量计费等一系列功能，这些都要求路由器根据包头对IP包进行分类，根据分类完成数据包的不同处理，本文全面地介绍了IP分类技术研究的最新成果，总结了解决IP分类问题的一般思想和并详细介绍了IP分类的典型算法，本文对其中三种算法在虚拟环境下做了评测，比较了它们的优缺点，最后指出了进一步的研究方向。     

IP地址查找算法的分析

由于lnternet中通信量的迅速增加。千兆网已被越来越多地采用。为了处理千兆／s的通信速度,中心路由器必须能够每秒转发几百万个包。因而快速的IP地址查找。就成为获得所需的数据包转发率的关键。文章分析了几种高效的IP地址查找算法,并从查找速度、可量测性、更新速度方面。对它们的性能进行了比较。     

基于前驱查找的快速IP路由查找和更新方案

路由器的转发速率通常受限于选择路由的速度,因此路由查找和更新的方法在路由器设计中至关重要。文章提出了一种可硬件实现的快速IP路由查找和更新方法,将IP前缀匹配等价为地址范围搜索,采用B-树结构存储路由表。这种方案对存储要求较低,仅由小容量的片上SRAM和片外DRAM构成。实验表明,该方案在简单硬件支持下就能够达到OC-48的转发要求。     

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

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

IPv6下路由器快速路径查找算法

在IPv6下由于地址长度的增加,路由器的处理负担更重,要求更高,目前很多已有的算法扩展到IPv6后无法适应新的需求。因而提出了一套IPv6 的快速路径查找机制,利用中间的Hash Table(HT32)来达到快速查找的索引。本方法可以加速路由器处理网络封包,提升网络速度。     

一种新的确定性包标记IP追踪算法的研究

目前的IP追踪都是基于反向完整路径追踪,反向完整路径追踪需要ISP的配合,而要取得所有的ISP的配合是一件困难的事情,在这这里提出一种新的基于确定性包标记技术的IP追踪算法,这种实现需要很少的带宽和处理的花费,可以追踪由单个数据包产生的DOS攻击,而且不需揭示网络拓扑的内在结构。     

Leaf-TCAM:一种并行IP路由查找方法及性能分析

分析了互联网路由表和路由更新的特征,提出了一种基于叶子节点进行路由表分区的并行IP路由查找方法Leaf-TCAM,分区子表按照流量特征在K个TCAM芯片中进行均衡分布。分析表明,该路由查找方法在引入0.1*(K-1)冗余的前提下具有K-1倍加速因子。该方法无需进行前缀扩展,90%以上的路由前缀无需排序,可以采用随机更新;同时还具有分区均匀、分区溢出代价小等特点,而功耗只有传统单片方案的12%。     

一种基于跳转表的多维IP分类算法

网络应用的发展要求路由器必须有能力支持防火墙、提供QoS、流量计费等一系列功能,这些功能都要求路由器对IP包进行分类来完成对数据包的不同处理,本文提出的算法直接从多维IP分别问题入手,经过一个跳转表,把多维IP分类问题转化为二维的IP分类问题,从而提高了分类速度,该算法可以充分发挥二维分类算法高效率的特点,从而可以极大地提高多维分类的速度。     

高速网络路由器IP报文转发技术的研究与实现

随着Internet的迅猛发展,高性能网络路由器在新一代高速IP网络中发挥着巨大的作用。而制约高性能网络路由器性能的瓶颈之一是IP报文的转发速度。针对当前先进的路由器体系结构,介绍了一种快速IP报文转发部件的设计方法及实现。     

基于双端口SRAM的网闸设计

物理隔离网闸是一种应用级的安全隔离系统,主要用来解决网络安全所带来的问题。基于双端口SRAM的物理网闸隔离系统采用双端口SRAM作为数据交换区,内外网处理单元通过设备驱动接口实现交换区数据的同步访问。该系统具备数据交换快,安全性能高等特点。     

基于可变大小偏移量表的高速IP路由查找算法

由于因特网速度的不断提高、网络流量的不断增加和路由表规模的不断扩大,IP路由查找已经成为制约核心路由器性能的主要瓶颈。目前已有几种解决高速IP路由查找问题的算法,但均不能完全满足核心路由器的要求。本文提出了一种基于可变大小偏移量表的IP路由查找方法,它具有查找速率高、更新时间快、存储代价低、易于实现等特点,能
能满足10Gbps核心路由器环境的要求。     

TCAM architecture for IP lookup using prefix properties

In modern IP routers, Internet protocol (IP) lookup forms a bottleneck in packet forwarding because the lookup speed cannot catch up with the increase in link bandwidth. Ternary content-addressable memories (TCAMs) have emerged as viable devices for designing high-throughput forwarding engines on routers. Called ternary because they store don't-care states in addition to 0s and 1s, TCAMs search the data (IP address) in a single clock cycle. Because of this property, TCAMs are particularly attractive for packet forwarding and classifications. Despite these advantages, large TCAM arrays have high power consumption and lack scalable design schemes, which limit their use. We propose a two-level pipelined architecture that reduces power consumption through memory compaction and the selective enablement of only a portion of the TCAM array. We also introduce the idea of prefix aggregation and prefix expansion to reduce the number of routing-table entries in TCAMs for IP lookup. We also discuss an efficient incremental update scheme for the routing of prefixes and provide empirical equations for estimating memory requirements and proportional power consumption for the proposed architecture.     

基于网络处理器的IP路由器的方案设计*

介绍了网络处理器硬件结构和软件开发平台,提出了基于网络处理器的16端口IP路由器的设计及其性能分析,重点说明了微引擎中接收和发送线程的微代码流程以及系统内资源的分配管理。     

校园网中防IP盗用实例

结合实例。介绍通过绑定静态ARP表、绑定交换机端口、设置防火墙与代理服务器和安装过滤路由器等具体方法来有效防范校园网中IP的盗用。