R. Guo and J.G. Delgado-Frias (USA)
High speed internet, compaction, route lookup.
Routing table lookup is an important operation in packet forwarding. The speed at which this operation is performed has a great influence on the overall performance of the network processors. Routing tables are usually stored in main memory with a large access time. Consequently, small fast cache memories have been used to improve access time. In this paper, we propose a novel routing table compaction scheme to reduce the size of routing table stored in ternary content addressable memory (TCAM) and improve cache hit rate. Two or more routing entries are compacted into one using don’t care element in TCAM. A small compacted routing table helps to increase cache hit rate; this in turn provides fast address lookups. We have evaluated the compaction scheme through extensive simulations involving IPv4 routing tables and traces. The original routing tables have been compacted over 60%. The cache hit rate has improved by up to 20% over the original tables depending on both cache size (number of cache entries) and traces. We have also analyzed the impact of port errors caused by caching technique, and chose sampling technique to alleviate this problem. The proposed scheme has been extended to IPv6 with similar results.
Important Links:
Go Back
