Reducing cache miss ratio for routing prefix cache

Because of rapid increase in link capacity, an Internet router has to complete routing lookup function in a much shorter amount of time in order to keep up with the line rate. Many fast routing lookup algorithms have been proposed in the past. Because most of them require some memory accesses, their lookup speed is limited by memory access speed. IP address caching has been used to improve upon existing routing lookup algorithms by storing the most recently referenced IP address. Most recently, routing prefix caching has been proposed to increase caching effectiveness. In this paper, we evaluate techniques to further reduce cache miss ratio, thereby, increase caching effectiveness for a routing prefix cache. We first study the effect of routing. table compaction, which reduces the routing table size. Then we propose and evaluate a new cache replacement policy that outperforms both least recently used and least frequently used replacement policy. The experiment result shows that up to 39% percent reduction in cache miss ratio could be achieved. It further proves that routing prefix cache has the potential to greatly outperform IP address cache.