The IP lookup in internet routers requires implementation of the longest prefix
match algorithm. The software or hardware implementations of routing trie based
approaches require several memory accesses in order to perform a single memory
lookup, which limits the throughput considerably. On the other hand, IP lookup
throughput requirements have been continuously increasing. This has led to ternary
content addressable memory(TCAM) based IP lookup engines which can perform
a single lookup every cycle. TCAM lookup engines are very power hungry due to
the large number of entries which need to be simultaneously searched. This has
led to two disparate streams of research into power reduction techniques. The first
research stream focuses on the routing table compaction using logic minimization
techniques. The second stream focuses on routing table partitioning. This work
proposes to bridge the gap by employing strategies to combine these two leading state
of the art schemes. The existing partitioning algorithms are generally employed on
a binary routing trie precluding their application to a compacted routing table. The
proposed scheme employs a ternary routing trie to facilitate the representation of the
minimized routing table in combination with the ternary trie partitioning algorithm.
The combined scheme offers up to 50% reduction in silicon area while maintaining
the power economy of the partitioning scheme.
Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/4694 |
Date | 25 April 2007 |
Creators | Ahmad, Seraj |
Contributors | Mahapatra, Rabi N. |
Publisher | Texas A&M University |
Source Sets | Texas A and M University |
Language | en_US |
Detected Language | English |
Type | Book, Thesis, Electronic Thesis, text |
Format | 378738 bytes, electronic, application/pdf, born digital |
Page generated in 0.0014 seconds