Efficient IP-address lookup with a shared forwarding table for multiple virtual routers

Research output: Chapter in Book/Report/Conference proceedingConference contribution

50 Scopus citations

Abstract

Virtual routers are a promising way to provide network services such as customer-specific routing, policy-based routing, multi-topology routing, and network virtulization. However, the need to support a separate forwarding information base (FIB) for each virtual router leads to memory scaling challenges. In this paper, we present a small, shared data structure and a fast lookup algorithm that capitalize on the commonality of IP prefixes between each FIB. Experiments with real packet traces and routing tables show that our approach achieves much lower memory requirements and considerably faster lookup times. Our prototype implementation in the Click modular router, running both in user space and in the Linux kernel, demonstrates that our data structure and algorithm are an interesting solution for building scalable routers that support virtualization.

Original languageEnglish (US)
Title of host publicationProceedings of 2008 ACM CoNEXT Conference - 4th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT '08
DOIs
StatePublished - Dec 1 2008
Event2008 ACM CoNEXT Conference - 4th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT '08 - Madrid, Spain
Duration: Dec 9 2008Dec 12 2008

Publication series

NameProceedings of 2008 ACM CoNEXT Conference - 4th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT '08

Other

Other2008 ACM CoNEXT Conference - 4th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT '08
CountrySpain
CityMadrid
Period12/9/0812/12/08

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Keywords

  • IP-address lookup
  • Virtual routers

Fingerprint Dive into the research topics of 'Efficient IP-address lookup with a shared forwarding table for multiple virtual routers'. Together they form a unique fingerprint.

  • Cite this

    Fu, J., & Rexford, J. L. (2008). Efficient IP-address lookup with a shared forwarding table for multiple virtual routers. In Proceedings of 2008 ACM CoNEXT Conference - 4th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT '08 [21] (Proceedings of 2008 ACM CoNEXT Conference - 4th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT '08). https://doi.org/10.1145/1544012.1544033