Hash tables (HTs) are used to implement various lookup schemes and they need
to be efficient in terms of speed, space utilization, and power consumptions. For IP
lookup, the hashing schemes are attractive due to their deterministic O(1) lookup
performance and low power consumptions, in contrast to the TCAM and Trie based
approaches. As the size of IP lookup table grows exponentially, scalable lookup
performance is highly desirable. For next generation high-speed routers, this is a
vital requirement when IP lookup remains in the critical data path and demands a
predictable throughput. However, recently proposed hash schemes, like a Bloomier
filter HT and a Fast HT (FHT) suffer from a number of flaws, including setup failures,
update overheads, duplicate keys, and pointer overheads. In this dissertation, four
novel hashing schemes and their architectures are proposed to address the above
concerns by using pipelined Bloom filters and a Fingerprint filter which are designed
for a memory-efficient approximate match. For IP lookups, two new hash schemes
such as a Hierarchically Indexed Hash Table (HIHT) and Fingerprint-based Hash
Table (FPHT) are introduced to achieve a a perfect match is assured without pointer
overhead. Further, two hash mechanisms are also proposed to provide memory and
power efficient lookup for packet processing applications.
Among four proposed schemes, the HIHT and the FPHT schemes are evaluated for their performance and compared with TCAM and Trie based IP lookup schemes.
Various sizes of IP lookup tables are considered to demonstrate scalability in terms
of speed, memory use, and power consumptions. While an FPHT uses less memory
than an HIHT, an FPHT-based IP lookup scheme reduces power consumption by a
factor of 51 and requires 1.8 times memory compared to TCAM-based and trie-based
IP lookup schemes, respectively. In dissertation, a multi-tiered packet classifier has
been proposed that saves at most 3.2 times power compared to the existing parallel
packet classifier.
Intrinsic hashing schemes lack of high throughput, unlike partitioned Ternary
Content Addressable Memory (TCAM)-based scheme that are capable of parallel
lookups despite large power consumption. A hybrid CAM (HCAM) architecture has
been introduced. Simulation results indicate HCAM to achieve the same throughput
as contemporary schemes while it uses 2.8 times less memory and 3.6 times less power
compared to the contemporary schemes.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2009-05-364 |
| Date | 2009 May 1900 |
| Creators | Yu, Heeyeol |
| Contributors | Mahapatra, Rabi |
| Source Sets | Texas A and M University |
| Language | English |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | application/pdf |
Page generated in 0.0019 seconds