Efficient IP-Address Lookup with a Shared Forwarding Table for Multiple Virtual Routers
2008 (English)In: 2008 ACM CoNEXT Conference: 4th International Conference on Emerging Networking EXperiments and Technologies, CoNEXT '08; Madrid; 9 December 2008 through 12 December 2008, 2008Conference paper (Refereed)
Virtual routers are a promising way to provide network services such as customerspecificrouting, 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, wepresent a small, shared data structure and a fast lookup algorithm that capitalize onthe commonality of IP prefixes between each FIB. Experiments with real packettraces and routing tables show that our approach achieves much lower memoryrequirements and considerably faster lookup times. Our prototype implementationin 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 forbuilding scalable routers that support virtualization.
Place, publisher, year, edition, pages
IP-address lookup; Virtual routers
IdentifiersURN: urn:nbn:se:kth:diva-9412DOI: 10.1145/1544012.1544033ScopusID: 2-s2.0-70350764027ISBN: 978-160558210-8OAI: oai:DiVA.org:kth-9412DiVA: diva2:113877
QC 201007262008-10-302008-10-302010-07-26Bibliographically approved