Cache Replacement Policies for IP Address Lookups

R. Guo, J.G. Delgado-Frias (USA), and S. Wong (The Netherlands)


Communication system, cache management, route lookup.


In IP routing, the routing table lookup is a very important operation and the speed in which it is performed determines the overall performance of Internet processors. Consequently, caching schemes are implemented in such processors to speed up these operations. A well-known factor affecting the performance of caches is the replacement policy, which decides which entry in the cache to be replaced with a new one. In this paper, we propose two new cache replacement policies, namely LAR (Least Access and Recently used) and RLAI (Relatively Least Average Interval). With regard to the common LRU (Least Recently Used) replacement policy, our policies take an additional parameter into account to evict the relative inactivity of cache entries. We first evaluated both policies through extensive simulation based on IPv4 routing information; we have observed both of them improved the cache hit rate almost up to 5.73%, as compared with LRU. Then we extended to apply them on IPv6 routing, and it turns out that the LAR shows the hit rate increasing up to 2.35%, and the improvement of RLAI is up to 2.58% over LRU. Consequently the proposed replacement policies achieve better performance for both IPv4 and IPv6 routing.

Important Links:

Go Back