R. Guo and J.G. Delgado-Frias (USA)
Victim cache, randomly selected index, pipelining, and hit rate.
In this paper, we study several novel schemes and their pipelined implementation to improve the performance of lookups in Internet routers. These schemes are all based on cache architecture that stores most frequently used forwarding information. One scheme uses a victim cache (VC) to save the entries discarded by the main cache. Another uses randomly selected index (RSI) to redirect indexes away from those entries that have a large potential of having conflict misses. The last scheme uses a combination of these two schemes. By using pipelining, the throughput is greatly increased. Through simulations of IPv6 traces, these three techniques have shown to reduce conflict misses effectively. The hit rate of direct mapped cache is increased from 2% to 10% depending on the address trace. The results are very close to a fully associative cache of the same size. Since simpler cache schemes could help to reduce the memory access time and pipeline helps to increase the clock rate, this leads to a high throughput. This is of particular importance for next generation IP address, IPv6, which has a length of 128 bits. If choosing inexpensive SRAM (or even DRAM) as cache, the router with the above schemes also satisfies the line speed requirement of the current and future routers.
Important Links:
Go Back
