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.     

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     

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     

All-optical tree-based greedy router using optical logic gates and optical flip-flops

Due to ever-increasing throughput demands, the lookup in conventional IP routers based on longest prefix matching is becoming a bottleneck. Additionally, the scalability of current routing protocols is limited by the size of the routing tables. Geometric greedy routing is an alternative to IP routing which replaces longest prefix matching with a simple calculation employing only local information for packet forwarding. For the first time, in this paper we propose a novel and truly all-optical geometric greedy router based on optical logic gates and optical flip-flops. The circuit of the router is constructed through the interconnection of SOAs and directional couplers. The successful functionality of the proposed router is verified through simulation. The circuit enables high data rate throughput.     

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.     

Performance Improvement of Two-Dimensional Packet Classification by Filter Rephrasing

Packet classification categorizes incoming packets into multiple forwarding classes in a router based on predefined filters. It is important in fulfilling the requirements of differentiated services. To achieve fast packet classification, a new approach, namely ldquofilter rephrasing,rdquo is proposed to encode the original filters by exploiting the hierarchical property of the filters. Filter rephrasing could dramatically reduce the search and storage complexity incurred in packet classification. We incorporate a well-known scheme-rectangle search-with filter rephrasing to improve the lookup speed by at least a factor of 2 and decreases 70% of the storage expenses. As compared with other existing schemes, the proposed scheme exhibits a better balance between speed, storage, and computation complexity. Consequently, the scalable effect of filter rephrasing is suitable for backbone routers with a great number of filters.     

Arranging multicast forwarding table in class sequence in ternary-cam for line-speed lookup

PIM-SM (Protocol Independent Multicast-Sparse Mode) is a main multicast routing protocol in the IPv6 (Internet Protocol version 6). It can use either a shared tree or a shortest path tree to deliver data packets, consequently the multicast IP lookup engine requires, in some cases, two searches to get a correct lookup result according to its multicast forwarding rule, and it may result in a new requirement of doubling the lookup speed of the lookup engine. The ordinary method to satisfy this requirement in TCAM (Ternary Content Addressable Memory) based lookup engines is to exploit parallelism among multiple TCAMs. However, traditional parallel methods always induce more resources and higher design difficulty. We propose in this paper a novel approach to solve this problem. By arranging multicast forwarding table in class sequence in TCAM and making full use of the intrinsic characteristic of the TCAM, our approach can get the right lookup result with just one search and a single TCAM, while keeping the hardware of lookup engine unchanged. Experimental results have shown that the approach make it possible to satisfy forwarding IPv6 multicast packets at the full link rate of 20 Gb/s with just one TCAM with the current TCAM chip.     

并行网络模拟中远程路由策略的研究

首先对并行网络模拟所采用的远程路由策略进行了分析研究,之后提出了基于优化边界的远程路由策略.该策略用边界路由器ID取代目的IP地址作为路由转发方式,有效地提高了路由查询速度.同时,通过树区域收缩、后连节点去重和边界路由器去重3种方法降低了内存的占用量.基于PDNS的实验结果表明,相对于基于边界路由器的远程路由策略,该方法降低了85％的内存使用量,并减少了75％的模拟时间.     

High-performance architectures for IP-based multihop 802.11 networks

The concept of a forwarding node, which receives packets from upstream nodes and then transmits these packets to downstream nodes, is a key element of any multihop network, wired or wireless. While high-speed IP router architectures have been extensively studied for wired networks, the concept of a "wireless IP router" has not been addressed so far. We examine the limitations of the IEEE 802.11 MAC protocol in supporting a low-latency and high-throughput IP datapath comprising multiple wireless LAN hops. We first propose a wireless IP forwarding architecture that uses MPLS with modifications to 802.11 MAC to significantly improve packet forwarding efficiency. We then study further enhancements to 802.11 MAC that improve system throughput by allowing a larger number of concurrent packet transmissions in multihop 802.11-based IP networks. With 802.11 poised to be the dominant technology for wireless LANs, we believe a combined approach to MAC, packet forwarding, and transport layer protocols is needed to make high-performance multihop 802.11 networks practically viable.     

Demonstration of the highly reliable Hikari router network based on a newly developed disjoint path selection scheme

Integration of multiprotocol label switching functions and multiprotocol lambda switching functions can enhance the throughput of IP networks and remove bottlenecks that are derived from electrical packet processing. To enhance the packet forwarding capability, NTT proposed a photonic MPLS concept that includes MP/spl lambda/S, and demonstrated IP, MPLS, and photonic MPLS integrated router systems called the photonic MPLS router. This router system is now called the Hikari router. The word Hikari is Japanese meaning beam, light, lightwave, optical, photonic, and sunshine. The amount of IP data traffic has grown remarkably. Massive IP routers and flexible route control mechanisms are now required to cope with the increased amount of traffic. The Hikari router can offer two solutions utilizing photonic switching technologies, and photonic network operation and management technologies. The first solution is utilizing photonic switching technologies realized using optical-switch-based crossconnect systems. The other solution is realized using the MPLS and MP/spl lambda/S signaling protocol and photonic network protection functions. In this article we report on the implementation of the Hikari router systems, propose a newly developed disjoint path selection scheme for generalized MPLS networks with shared risk link group constraints, and demonstrate the signaling protocol and network protection functions. The demonstration system achieves a distributed optical path set-up/tear-down protocol with an extended constraint-based routing label distribution protocol. Fast self-healing through automatic protection switching and a new restoration scheme are also implemented. These functions are successfully implemented, and the performance is verified on a demonstration network. The protection switching scheme achieves protection in less than 20 ms, and the optical path restoration scheme achieves restoration in less than 500 ms.     

H‐LCFST: a hash lowest cost first search tree for flexible packet classification

Packet classification (PC) categorizes incoming packets into multiple forwarding classes in a router based on predefined filters. It is one of the most important enabling technologies for next generation network services, for example, firewall, quality of service routing, load balancing, and virtual private network. IPv6 technology has posed a great challenge on the wire‐speed router for the PC because of its longer IP addresses. In this paper, we propose a new algorithm to support both IPv4 and IPv6, called hash lowest cost first search tree (H‐LCFST) for the PC. The H‐LCFST combines the advantages of the hash tree and a novel LCFST to achieve a better lookup performance. More important, the H‐LCFST algorithm is able to utilize the features of distinct IPv4 and IPv6 classifiers and design corresponding data structure for different characteristics of the classifiers, with which it is able to avoid the performance degrade because of the longer address of the IPv6. The experiment results show that our proposed algorithm has only approximately seven times of memory accesses for the IPv4/IPv6 PC, which make it to be the fastest PC solutions so far. Moreover, it occupies extremely small memory and supports incremental update at the same time. Copyright © 2016 John Wiley & Sons, Ltd.     

Topology-assisted deterministic packet marking for IP traceback

A novel deterministic packet marking (DPM) for IP traceback against denial of service (DoS) and distributed denial of service (DDoS) attacks is presented, which features good scalability and high accuracy. In this scheme, an ingress router pre-calculates a Hash of its IP address and splits the Hash into several fragments. When marking a packet, the router randomly selects a fragment to mark into the packet. In the traceback stage the victim identifies the marked router with the help of the map of its upstream routers. Based on the map, the victim can identify a candidate ingress router after receiving only several marked packets. The scheme overcomes defects in previous deterministic packet marking schemes, where too much packets are required to recover a router and high false positive rate occurs in case of large-scale DDoS. Theoretical analysis, the pseudo code and experimental results are provided. The scheme is proved to be accurate and efficient and can handle large-scale DDoS attacks.     

TCAM快更新高速路由查找算法与实现

常用的单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性。本文提出并实现了一种独特的对前缀范围对分搜索的IPv4五步TCAM流水查找方法。突出特点是转发表不需排序,查找速率高,表覆更新快,查表连续性好,可满足IPv4核心路由器双OC-768（40Gbps）端口、48B包的线速转发。     

基于信任管理系统的可信路由器的设计与实现(英文)

This paper presents a scheme to perform QoS management and assure network security by using the trusted-router based on the Trust Management System.In this trusted-router,every IP packet is forwarded and queued by its trust value,which is the quantification of the network's expectation for this packet's and its owner's behavior in the network.We outline the algorithms to calculate the trust value of the trusted-router and the IP packet.We also introduce the trust-based QoS management algorithm and the deplo...     

Achieving Sub-50 Milliseconds Recovery Upon BGP Peering Link Failures

Recent measurements show that BGP peering links can fail as frequently as intradomain links and usually for short periods of time. We propose a new fast-reroute technique where routers are prepared to react quickly to interdomain link failures. For each of its interdomain links, a router precomputes a protection tunnel, i.e., an IP tunnel to an alternate nexthop which can reach the same destinations as via the protected link. We propose a BGP- based auto-discovery technique that allows each router to learn the candidate protection tunnels for its links. Each router selects the best protection tunnels for its links and when it detects an interdomain link failure, it immediately encapsulates the packets to send them through the protection tunnel. Our solution is applicable for the links between large transit ISPs and also for the links between multi-homed stub networks and their providers. Furthermore, we show that transient forwarding loops (and thus the corresponding packet losses) can be avoided during the routing convergence that follows the deactivation of a protection tunnel in BGP/MPLS VPNs and in IP networks using encapsulation.     

A fast IP routing lookup scheme

A major issue in router design for the next generation Internet is the fast IP address lookup mechanism. The existing scheme by Huang et al. (see Proc. IEEE INFOCOM'99, New York, NY, 1999) performs the IP address lookup in hardware in which the forwarding table can be compressed to fit into a reasonable-size SRAM, and a lookup can be accomplished in three memory accesses. We claim that with a little extra memory, it is able to further reduce the lookup time to two memory accesses     

T比特IPv4/v6高性能路由器设计与实现

互联网的高速发展,使得目前处于网络核心的路由器成为制约互联网可持续性发展的关键因素.随着网络新技术的引入和应用业务的增多,高性能路由器必须支持大容量、高吞吐率、低转发时延、IPv4/v6双协议栈和众多的路由协议.本文针对这些要求,详细阐述了T比特IPv4/v6高性能路由器的需求、系统设计、关键技术,为设计与实现高性能双协议栈路由器提供了一种可行的方案.     

Performance enhancement of IP forwarding by reducing routing tableconstruction time

In previous work, Lampson et al. (1999) proposed an IP lookup algorithm which performs binary searches on prefixes (BSP). The algorithm is attractive for IPv6 because of its bounded worst-case memory requirement. Although for the sake of fast forwarding, the cost paid for the slowing down insertion is reasonable, the performance of routing-table reconstruction in BGP is too time-consuming to handle the frequent route updates. In this letter, we propose a fast forwarding-table construction algorithm which can handle more than 3600 route updates per second. Moreover, it is simple enough to fulfill the need of fast packet forwarding     

中兴通讯IPv6核心路由器体系结构与关键技术

文章介绍了中兴通讯ZXR10 T1200 IPv6核心路由器,并阐述了该路由器实现的一些关键技术,如硬件体系结构、基于嵌入式实时多任务内核的ZXROS软件平台、高效的IPv6转发机制、IPv4向IPv6过渡技术等.ZXR10 T1200 IPv6核心路由器的研制成功,表明了中国已经具有研制核心路由器的能力,对推动中国高新技术产业、提升国家的国际竞争力和保障国家信息安全有非常重大的意义.