Dynamic pipelining: making IP-lookup truly scalable

ABSTRACT

A truly scalable IP-lookup scheme must address five challenges of scalability, namely: routing-table size, lookup throughput, implementation cost, power dissipation, and routing-table update cost. Though several IP-lookup schemes have been proposed in the past, none of them do well in all the five scalability requirements. Previous schemes pipeline tries by mapping trie levels to pipeline stages. We make the fundamental observation that because this mapping is static and oblivious of the prefix distribution, the schemes do not scale well when worst-case prefix distributions are considered. This paper is the first to meet all the five requirements in the worst case. We propose scalable dynamic pipelining (SDP) which includes three key innovations: (1) We map trie nodes to pipeline stages based on the node height. Because the node height is directly determined by the prefix distribution, the node height succinctly provides sufficient information about the distribution. Our mapping enables us to prove a worst-case per-stage memory bound which is significantly tighter than those of previous schemes. (2) We exploit our mapping to propose a novel scheme for incremental route-updates. In our scheme a route-update requires exactly and only one write dispatched into the pipeline. This route-update cost is obviously the optimum and our scheme achieves the optimum in the worst case. (3) We achieve scalability in throughput by simultaneously pipelining at the data-structure level and the hardware level. SDP naturally scales in power and implementation cost. We not only present a theoretical analysis but also evaluate SDP and a number of previous schemes using detailed hardware simulation. Compared to previous schemes, we show that SDP is the only scheme that scales well in all the five requirements.

REFERENCES

• 1: Anindya Basu and Girija Narlikar. Fast Incremental Updates for Pipelined Forwarding Engines. In Proceedings of INFOCOM '03, 2003.
• 2: CACTI. http://research.compaq.com/wrl/people/jouppi/CACTI.html
• 3: Mikael Degermark , Andrej Brodnik , Svante Carlsson , Stephen Pink, Small forwarding tables for fast routing lookups, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.3-14, September 14-18, 1997, Cannes, France
• 4: Will Eatherton , George Varghese , Zubin Dittia, Tree bitmap: hardware/software IP lookups with incremental updates, ACM SIGCOMM Computer Communication Review, v.34 n.2, April 2004 [doi>10.1145/997150.997160]
• 5: Mathew Gray. Internet Growth Summary. http://www.mit.edu/people/mkgray/net/internet-growth-summary.html, 1996.
• 6: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 7: V. Kumar, T. Lakshman and D. Stiliadis. Beyond Best Effort: Router Architectures for Differentiated Services of Tomorrow's Internet. IEEE Communications Magazine 36(5) 152--164, 1998
• 8: Integrated Device Technology, Inc. http://www.idt.com.
• 9: Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
• 10: NetLogic Microsystems, Inc. http://www.netlogicmicro.com.
• 11: S. Nilsson , G. Karlsson, Fast address look-up for internet routers, Proceedings of the IFIP TC6/WG6.2 Fourth International Conference on Broadband Communications: The future of telecommunications, p.11-22, April 01-03, 1998
• 12: Routing Information Service. http://www.ris.ripe.net.
• 13: Devavrat Shah , Pankaj Gupta, Fast Updating Algorithms for TCAMs, IEEE Micro, v.21 n.1, p.36-47, January 2001 [doi>10.1109/40.903060 ]
• 14: Sandeep Sikka , George Varghese, Memory-efficient state lookups with fast updates, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.335-347, August 28-September 01, 2000, Stockholm, Sweden
• 15: Timothy Sherwood , George Varghese , Brad Calder, A pipelined memory architecture for high throughput network processors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 16: K. Sklower. A Tree-Based Routing Table for Berkeley Unix. In Proceedings of the 1991 Winter Usenix Conference. 1991.
• 17: V. Srinivasan , G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems (TOCS), v.17 n.1, p.1-40, Feb. 1999 [doi>10.1145/296502.296503]
• 18: Alan Tammel. How to Survive as an ISP. In Proceedings of Networld Interop 97, 1997.
• 19: F. Zane, G. Narlikar and A. Basu. CoolCAMs: Power-Efficient TCAMs for Forwarding Engines. In Proceedings of INFOCOM '03, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

General Terms:
Algorithms, Design, Performance

Keywords:
IP-lookup, longest prefix matching, pipelined, scalable, tries