An Associative Ternary Cache for IP Routing

J.J. Rooney, J.G. Delgado-Frias, and D.H. Summerville (USA)


Internet IP routing, IPv4, Cache memory, Content Addressable Memory, Ternary memory.


In this paper we present a study of an associative cache for Internet IP routing. An output port assignment requires one cache memory access when the assignment is found in cache. The cache array is divided into sets that are of variable size; all entries within a set have the same prefix size. Our study shows that an associative ternary cache provides an output port at the speed of one memory access with a very high hit rate. For an 8K-entry cache the hit rate ranges from 97.62% to 99.67% on traces of 0.2 to 3.5 million addresses. A port error occurs when the port selected by the cache differs from the port that would have been selected from the routing table. The worst port error rate is 0.52%, and is reduced to 0.05% with the use of a sampling technique.

Important Links:

Go Back