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

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.