New Caching Scheme for Routing Table Lookups
Original Publication Date: 2001-Aug-19
Included in the Prior Art Database: 2003-Jun-20
Introduction IP Forwarding is the process in which an Internet router uses the IP destination address of an incoming packet to search a routing table according to a longest-matching prefix search in order to determine the next router (i.e., next hop) to which the packet has to be forwarded to. The high search rates required by the increasing link speeds (OC-192, OC-768, etc.) force the IP forwarding function to use fast but expensive memory such as embedded DRAM and SRAM, having only limited storage capacity. In addition, routing tables are growing at exponential rates. These two trends have driven several research efforts towards lookup schemes using memory hierarchies similar as in general-purpose computers (e.g., L1/L2 caches, main memory). Some earlier schemes were based on conventional processor caches, which were indexed by the full 32-bit IPv4 destination address. With these schemes, the cache is searched using an exact-match operation. A longest-matching prefix search is only performed on the complete data structure in the main memory upon a cache-miss. More recent projects focus on caches that are searched using prefix-match rather than exact-match as this appears to be much more efficient. These projects store variable-length prefixes in the cache instead of 32-bit IPv4 addresses, and perform cache control at the corresponding granularity (e.g., maintaining information to determine the least-recently-used prefix for a replacement operation).