Name
Abstract | ||
|---|---|---|
Internet routers conduct routing table (RT) lookup based on thedestination IP address of the incoming packet to decide whichoutput port to forward the packet. Ternary content-addressiblememories (TCAM) uses parallelism to achieve lookup in a singlecycle. One of the major drawbacks of TCAM is its high-powerconsumption. Trie-based architecture has been proposed to reduceTCAM power consumption. The idea is to use an index TCAM to selectone of many data TCAM blocks for lookup. However, power reductionis limited by the size of the index TCAM, which is always enabledfor search. In this paper we develop a simple but effectivetrie-partitioning algorithm to reduce the index TCAM size, whichachieves better reduction in power consumption, and at the sametime guarantees full TCAM space utilization. We compared ouralgorithm (LogSplit) with PostOrderSplit (IEEE INFOCOM,2003). For two real-world RTs (AADS and PAIX), the size of theindex TCAM generated by LogSplit is 55-70% of that generated byPostOrderSplit; the largest power reduction factor of LogSplit is41 for AADS and 68 for PAIX, while the largest power reductionfactor of PostOrderSplit is 33 for AADS and 52 for PAIX. Theimprovement is even more significant in the worst case: the size ofthe index TCAM generated by LogSplit is 18-30% of that generated byPostOrderSplit for IPv4, and less than 1% of that generated byPostOrderSplit for IPv6; the largest power reduction factor ofLogSplit is 173 for both IPv4 and IPv6, while the largest powerreduction factor of PostOrderSplit is only 82 for IPv4 and 41 forIPv6. Copyright © 2007 John Wiley & Sons, Ltd. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1002/dac.v21:2 | Int. J. Communication Systems |
Keywords | Field | DocType |
data tcam block,index tcam,power-efficient tcams,theindex tcam,size ofthe index tcam,logsplit is41,index tcam size,trie partitioning algorithm,power consumption,largest power reduction factor,largest power reductionfactor,full tcam space utilization,tcam,power efficiency,packet forwarding | IPv4,Content-addressable memory,Computer science,Computer network,Real-time computing,IS-41,Routing table,Trie,Packet forwarding,Parallel computing,Network packet,Algorithm,Router | Journal |
Volume | Issue | ISSN |
21 | 2 | 1074-5351 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
1 | ||