Cache Reference Behavior of Three IP Routing Table Lookup Algorithms

摘要

The algorithms for address lookups in IP forwarding are one of the key components of Internet routers. Recent efforts have focused on making these algorithms faster in order to improve router performance. In this work, however, we consider the cache reference behavior of these algorithms rather than their execution speed. This is motivated by the rapid increase in the use of virtual private networks (VPNs), and the requirement to support large numbers - tens to hundreds - of forwarding processes on a single physical router. If a 256 KB data cache with 4-way associativity and 32 byte lines is dedicated to IP lookups, our results show that it is feasible to run only 10 to 15 instances of any of the current high-performance lookup algorithms, assuming that cache miss rates of less than 1% are required.