IEEE/ACM Transactions on Networking · 2013 · 20 citations · 20 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureComputer NetworksData StructuresLookup TablesNetwork-on-chip DesignRoutingRouting ArchitectureContent-addressable MemoryLookup Table ArchitecturesLookup Table DesignMicro Hybrid ArchitectureRandom-access MemoryStatic Random-access MemoryStatic Random-access Memory DesignVirtual Router
As network link rates are being pushed beyond 40 Gb/s, IP lookup in high-speed routers is moving to hardware. The ternary content addressable memory (TCAM)-based IP lookup engine and the static random access memory (SRAM)-based IP lookup pipeline are the two most common ways to achieve high throughput. However, route updates in both engines degrade lookup performance and may lead to packet drops. Moreover, there is a growing interest in virtual IP routers where more frequent updates happen. Finding solutions that achieve both fast lookup and low update overhead becomes critical. In this paper, we propose a hybrid IP lookup architecture to address this challenge. The architecture is based on an efficient trie partitioning scheme that divides the forwarding information base (FIB) into two prefix sets: a large disjoint leaf prefix set mapped into an external TCAM-based lookup engine and a small overlapping prefix set mapped into an on-chip SRAM-based lookup pipeline. Critical optimizations are developed on both IP lookup engines to reduce the update overhead. We show how to extend the proposed hybrid architecture to support virtual routers. Our implementation shows a throughput of 250 million lookups per second (equivalent to 128 Gb/s with 64-B packets). The update overhead is significantly lower than that of previous work, the memory consumption is reasonable, and the utilization ratio of most external TCAMs is up to 100%.
20
Fast updating algorithms for TCAM
Devavrat Shah, Pravir Singh Gupta · IEEE Micro · 2001 · 197 citations
Routing table compaction in ternary CAM
Huan Liu · IEEE Micro · 2002 · 131 citations