A fast multicast IP-routing lookup scheme

This paper proposes a fast multicast IP-routing lookup scheme, which adopts a compression bit map conception for forwarding information. The proposed scheme can achieve fast address lookup speed and reasonable forwarding table size.     

A TCAM-based distributed parallel IP lookup scheme and performance analysis

Using ternary content addressable memory (TCAM) for high-speed IP address lookup has been gaining popularity due to its deterministic high performance. However, restricted by the slow improvement of memory accessing speed, the route lookup engines for next-generation terabit routers demand exploiting parallelism among multiple TCAM chips. Traditional parallel methods always incur excessive redundancy and high power consumption. We propose in this paper an original TCAM-based IP lookup scheme that achieves both ultra-high lookup throughput and optimal utilization of the memory while being power-efficient. In our multi-chip scheme, we devise a load-balanced TCAM table construction algorithm together with an adaptive load balancing mechanism. The power efficiency is well controlled by decreasing the number of TCAM entries triggered in each lookup operation. Using four 133 MHz TCAM chips and given 25% more TCAM entries than the original route table, the proposed scheme achieves a lookup throughput of up to 533 MPPS while remains simple for ASIC implementation.     

High-speed IP routing with binary decision diagrams based hardware address lookup engine

With a rapid increase in the data transmission link rates and an immense continuous growth in the Internet traffic, the demand for routers that perform Internet protocol packet forwarding at high speed and throughput is ever increasing. The key issue in the router performance is the IP address lookup mechanism based on the longest prefix matching scheme. Earlier work on fast Internet protocol version 4 (IPv4) routing table lookup includes, software mechanisms based on tree traversal or binary search methods, and hardware schemes based on content addressable memory (CAM), memory lookups and the CPU caching. These schemes depend on the memory access technology which limits their performance. The paper presents a binary decision diagrams (BDDs) based optimized combinational logic for an efficient implementation of a fast address lookup scheme in reconfigurable hardware. The results show that the BDD hardware engine gives a throughput of up to 175.7 million lookups per second (Ml/s) for a large AADS routing table with 33 796 prefixes, a throughput of up to 168.6 Ml/s for an MAE-West routing table with 29 487 prefixes, and a throughput of up to 229.3 Ml/s for the Pacbell routing table with 6822 prefixes. Besides the performance of the scheme, routing table update and the scalability to Internet protocol version 6 (IPv6) issues are discussed.     

A priority TCAM IP-routing lookup scheme

A priority TCAM IP-routing lookup scheme, which combines a priority ternary content addressable memory (TCAM) technique with a compact IP-routing lookup scheme, is proposed in this paper. It not only completes an IP-routing lookup with two memory accesses but also achieves small lookup table size and fast table reconstruction time.     

Scalable IP lookup for Internet routers

Internet protocol (IP) address lookup is a central processing function of Internet routers. While a wide range of solutions to this problem have been devised, very few simultaneously achieve high lookup rates, good update performance, high memory efficiency, and low hardware cost. High performance solutions using content addressable memory devices are a popular but high-cost solution, particularly when applied to large databases. We present an efficient hardware implementation of a previously unpublished IP address lookup architecture, invented by Eatherton and Dittia (see M.S. thesis, Washington Univ., St. Louis, MO, 1998). Our experimental implementation uses a single commodity synchronous random access memory chip and less than 10% of the logic resources of a commercial configurable logic device, operating at 100 MHz. With these quite modest resources, it can perform over 9 million lookups/s, while simultaneously processing thousands of updates/s, on databases with over 100000 entries. The lookup structure requires 6.3 bytes per address prefix: less than half that required by other methods. The architecture allows performance to be scaled up by using parallel fast IP lookup (FIPL) engines, which interleave accesses to a common memory interface. This architecture allows performance to scale up directly with available memory bandwidth. We describe the tree bitmap algorithm, our implementation of it in a dynamically extensible gigabit router being developed at Washington University in Saint Louis, and the results of performance experiments designed to assess its performance under realistic operating conditions.     

多分枝trie树路由查找算法研究

为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP 路由算法的基础上,提出一种基于多分枝trie树的改进路由查找算法.在多分枝trie树中取消前缀查找,组成一个大的中间结点.在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示.仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用.     

基于分割多分枝Trie树的并行路由查找算法

为解决在多核处理器平台下路由器报文转发时路由查找速度慢的“瓶颈”问题,提出了一种基于分割的多分枝 Trie树的并行路由查找算法。该算法将一棵多分枝 Trie 树根据处理器的核数分割成若干子树,每棵子树又构成一棵单独的多分枝Trie树,子树中取消了前缀查找,采取组成一个大中间节点的方式,在中间节点之间采用固定步长查询,中间节点内部采用二进制Trie树来表示。实验结果表明,该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点,同时适用于IPv4和 IPv6地址。     

多分枝trie树路由查找算法研究

为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP路由算法的基础上．提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀查找,组成一个大的中间结点。在中间结点之间采用多分支步长查询,中间结点的内部使用二进制trie树来表示。仿真结果表明,改进的多分支trie树具有访存次数少,查询速度快,占用存储空间少,更新开销小等特点,并且对IPv4和IPv6地址都可以适用。     

QoS multicast routing scheme using QGA in IP/DWDM networks

This article studies multi-constraints least-cost multicast routing problem in internet protocol over dense wavelength division multiplexing （IP/DWDM） networks. To address this problem, an individual-difference-based quantum genetic algorithm （IDQGA） is proposed. This algorithm considers individual differences among chromosomes by introducing an adaptive rotation angle step determination scheme and a grouping-based quantum mutation operation. Simulations are conducted over network topologies. The results indicate that compared with other heuristic algorithms, IDQGA has better optimal performance on solving quality of service （QoS） multicast routing problem in IP/DWDM networks and is characterized by strong robustness, high success ratio and excellent capability on global searching.     

Survey and taxonomy of IP address lookup algorithms

Due to the rapid growth of traffic in the Internet, backbone links of several gigabits per second are commonly deployed. To handle gigabit-per-second traffic rates, the backbone routers must be able to forward millions of packets per second on each of their ports. Fast IP address lookup in the routers, which uses the packet's destination address to determine for each packet the next hop, is therefore crucial to achieve the packet forwarding rates required. IP address lookup is difficult because it requires a longest matching prefix search. In the last couple of years, various algorithms for high-performance IP address lookup have been proposed. We present a survey of state-of-the-art IP address lookup algorithms and compare their performance in terms of lookup speed, scalability, and update overhead     

一种基于分段压缩的IPv6路由查找算法

提出了一种基于分段压缩的快速IPv6路由查找算法。与文献中的LLCAT算法相比，该算法节省了存储空间，当某扩展节点的表项所对应的前缀数量小于预先设定的值时，前缀不再扩展而使用压缩算法。同时，最坏情况下算法的查找时间和更新复杂度基本没有改变。仿真试验结果表明：算法的平均查找时间和消耗的存储器容量都优于LLCAT算法。     

High speed IP address lookup architecture using hashing

One of the most important design issues for IP routers responsible for datagram forwarding in computer networks is the route-lookup mechanism. In this letter, we explore a practical IP address lookup scheme which converts the longest prefix matching problem into the exact matching problem. In the proposed architecture, the forwarding table is composed of multiple SRAM, and each SRAM represents an address lookup table in a single prefix. Hashing functions are applied to each address lookup table in order to find out matching entries in parallel, and the entry matched with the longest prefix among them is selected. Simulation using data from the MAE-WEST router shows that a large routing table with 37000 entries is compacted to a forwarding table of 189 kbytes in the proposed scheme and achieves one route lookup every two memory accesses in average.     

Efficient construction of multibit tries for IP lookup

Srinivasan and Varghese (see ACM Trans. Comput. Syst., p.1-40, 1999) have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose dynamic programming algorithms to determine the strides of optimal multibit fixed-stride and variable-stride tries. We improve on these algorithms by providing alternative dynamic programming formulations for both fixed- and variable-stride tries. While the asymptotic complexities of our algorithms are the same as those for the corresponding algorithms of Srinivasan and Varghese, experiments using real IPv4 routing table data indicate that our algorithms run considerably faster. Our fixed-stride trie algorithm is two to four times faster on a SUN workstation and 1.5 to three times faster on a Pentium IV PC. On a SUN workstation, our variable-stride trie algorithm is between two and 17 times faster than the corresponding algorithm of Srinivasan and Varghese; on a Pentium IV PC, our algorithm is between three and 47 times faster. An added feature of our variable-stride trie algorithm is the ability to insert and delete prefixes taking a fraction of the time needed to construct an optimal variable-stride trie "from scratch".     

F-TPR: fine two-phase IP routing scheme over shortest paths for hose model

This letter proposes an IP-based finely-distributed routing scheme based on two-phase routing (TPR) over shortest paths for the hose model. It is called the fine-TPR (F-TPR) scheme. Compared to the original TPR, F-TPR distributes traffic from a source node to intermediate nodes more finely, where the distribution ratio is determined for each source-destination pair. To determine an optimum set of the distribution ratios, we successfully formulate our problem as a quadratic constraint programming (QCP) formulation that can be solved by using a mathematical programming solver. Numerical results show that F-TPR greatly outperforms TPR and its performance approaches that provided by the sophisticated traffic engineering (TE) scheme of multi-protocol label switching (MPLS-TE).     

SLEA: a novel scheme for routing in overlay IP/WDM networks

This paper studies the routing problems in Internet protocol/wavelength-division-multiplexing (IP/WDM) networks based on the overlay routing algorithm (ORA) and the integrated routing algorithm (IRA), respectively. Although IRA usually outperforms ORA in terms of blocking performance, IRA exhibits disadvantages in control information exchange, network privacy issue, and wavelength port efficiency. In this paper, a new mechanism called the short lightpath establishment approach (SLEA) is proposed for ORA in order to tackle the problems in IRA and achieve similar (or even better) network performance at the same time. The main idea of SLEA is to ensure that each new lightpath created by ORA is restricted by an optical hop constraint when a subwavelength-granularity connection is routed in the optical layer. It follows that SLEA essentially avoids per-connection-based greedy treatment and improves network wide resource utilization by eliminating inefficient long optical bypasses. To implement SLEA in ORA, the Dijsktra's algorithm has been modified based on an extended layered graph model. SLEA does not introduce any additional signaling and computational complexity. The analysis and simulation in this paper show that there exists an optimal optical hop constraint for each particular network configuration such that SLEA-based ORA (SLEA-ORA) can efficiently utilize the network resource of concern. As a result, with the optimal optical hop constraint, SLEA-ORA could outperform ORA and IRA in terms of the bandwidth-blocking ratio (BBR) and the average number of IP hops of label-switched paths (LSPs).     

A novel IP-routing lookup scheme and hardware architecture formultigigabit switching routers

One of the pertinent design issues for new generation IP routers is the route-lookup mechanism. For each incoming IP packet, the IP routing is required to perform a longest-prefix matching on the route lookup in order to determine the packet's next hop. This study presents a fast unicast route-lookup mechanism that only needs tiny SRAM and can be implemented using a hardware pipeline. The forwarding table, based on the proposed scheme, is small enough to fit into a faster SRAM with low cost. For example, a large routing table with 40000 routing entries can be compacted into a forwarding table of 450-470 kbytes costing less than US$30. Most route lookups need only one memory access; no lookup needs more than three memory accesses. When implemented using a hardware pipeline, the proposed mechanism can achieve one routing lookup every memory access. With current 10-ns SRAMs, this mechanism furnishes approximately 100×10⁶ routing lookups/s, which is much faster than any current commercially available routing-lookup scheme     

应用单纯形算法解决动态路由问题

探讨了如何在长途电话交换网中应用单纯形算法解决动态路由问题，并介绍了算法运行情况和运行结果。单纯形算法能够在很短的时间内得到质量很好的全局优化的路由方案。     

基于VHDL语言的快速查表电路

介绍了用超高速集成电路硬件描述语言(VHDL),设计数字集成系统中快速查表电路的方案,这种查表算法具有并行运行的特点,并能够同时查找多种参数.该查表电路用FPGA予以实现.     

Reconfigurable finite-state machine based IP lookup engine for high-speed router

Internet protocol (IP) address lookup is one of the major performance bottlenecks in high-end routers. This paper presents an architecture for an IP address lookup engine based on programmable finite-state machines (FSMs). The IP address lookup problem can be translated into the implementation of a large FSM. Our hardware engine is then used to implement this FSM using a structured approach, in which the large FSM is broken down into a set of smaller FSMs which are then mapped into reconfigurable hardware blocks. The design of our hardware engine is based on a regular and well structured architecture, which is easy to scale. Our simulation results demonstrate that the FSM based architecture can easily scale to wire speed performance at OC-192 rates. Unlike previous approaches, the performance of our architecture is not constrained by memory bandwidth and is, therefore, in principle scalable with very large scale integration technology.     

并行网络模拟中的远程路由计算和查找方法

提出了一种基于边界路由器的远程路由计算和查找方法，以边界路由器为核心计算远程路由信息，查找时通过路径长度比较实现最短路径的选择。该方法有效降低了远程路由表规模，提高了并行模拟器的运行效率。与PDNS相比，远程路由表规模缩减90％，初始化占用内存节省约20％，模拟运行时间减少25％。