High Performance IP Routing Table Lookup using CPU Caching

Wire-speed IP (Internet Protocol) routers require very fast routing table lookup for in-coming IP packets. The routing table lookup operation is time consuming because the part of an IP address used in the lookup, i.e., the network address portion, is variable in length. This paper describes the routing table lookup algorithm used in a cluster-based parallel IP router project called Suez. The innovative aspect of this algorithm is its abil-ity to use CPU caching hardware to perform routing table caching and lookup directly. By running a detailed simulation model that incorporates the performance e ects of the CPU memory hierarchy against a packet trace collected from a major network router, we show that the overall performance of the proposed algorithm can reach 87.87 million lookups per second for a 500-MHz Alpha processor with a 16-KByte L1 cache and a 1-MByte L2 cache. This result is one to two orders of magnitude faster than previ-ously reported results on software-based routing table lookup implementations. This paper also reports the performance impacts of various architectural parameters in the proposed scheme and its storage costs.