Efficient IP Routing Lookups for High-Performance Routers

Abstract

The forwarding performance of a router is a critical issue in the Internet. With the ever increasing number of computers in the Internet, the size of the routing table is becoming extremely large. Hence, the IP lookup process becomes a performance bottleneck in a router. In this paper, we propose the multi-level table access and compression schemes for fast IP table lookups in the forwarding engine of a router. With our design, the size of the forwarding table is significantly reduced, and it is possible to fit the entire table in a 256 KB cache memory. Hence, we can speed up route lookups with low memory access latency. In order to avoid excessive complexity, we also try to reduce the operations of table lookups. Our operation of the table lookup takes only a few memory references for each route lookup, and therefore millions of lookups per second can be easily achieved. The simulation results show that our high-performance design is efficient.