Routing prefix caching in network processor design

Cache has been time proven to be a very effective technique to improve memory access speed. It is based on the assumption that enough locality exists in memory access patterns, i.e., there is a high probability that an entry will be accessed again shortly after. However, it is questionable whether Internet traffic has enough locality, especially in the high speed backbone, to justify the use of cache for routing table lookup. We believe there is enough locality if routing prefixes are cached instead of individual IP addresses. This paper is the first to evaluate the effectiveness of caching on routing prefix. We propose an on-chip routing prefix cache design for the network processor. The control-path processor is used in our design to fulfill missed cache requests. In order to guarantee the correct lookup result, it is important that the control-path processor only returns cacheable routing prefixes. We present three implementations that all guarantee the correct lookup result. Simulation results show that our cache design performs much better than an IP address cache, even after factoring in the extra complexity involved