Building a high performance IP packet forwarding (PF) engine remains a challenge due to increasingly stringent throughput requirements and the growing sizes of IP forwarding tables.
The router has to match the incoming packet's IP address against the forwarding table.
The matching process has to be done in wire speed which is why scalability and low power consumption are features that PF engines must maintain.
It is common for PF engines to use hash tables; however, the classic hashing downsides have to be dealt with (e.g., collisions, worst case memory access time, ... etc.).
While open addressing hash tables, in general, provide good average case search performance, their memory utilization and worst case performance can degrade quickly due to collisions that leads to bucket overflows.
Set associative memory can be used for hardware implementations of hash tables with the property that each bucket of a hash table can be searched in one memory cycle.
Hence, PF engine architectures based on associative memory will outperform those based on the conventional Ternary Content Addressable Memory (TCAM) in terms of power and scalability.
The two standard solutions to the overflow problem are either to use some sort of predefined probing (e.g., linear or quadratic) or to use multiple hash functions.
This work presents two new hash schemes that extend both aforementioned solutions to tackle the overflow problem efficiently.
The first scheme is a hash probing scheme that is called Content-based HAsh Probing, or CHAP.
CHAP is a probing scheme that is based on the content of the hash table to avoid the classical side effects of predefined hash probing methods (i.e., primary and secondary clustering phenomena) and at the same time reduces the overflow.
The second scheme, called Progressive Hashing, or PH, is a general multiple hash scheme that reduces the overflow as well.
PH splits the prefixes into groups where each group is assigned one hash function, then reuse some hash functions in a progressive fashion to reduce the overflow.
We show by experimenting with real IP lookup tables that both schemes outperform other hashing schemes.
| Identifer | oai:union.ndltd.org:PITT/oai:PITTETD:etd-11192009-103639 |
| Date | 26 January 2010 |
| Creators | Hanna, Michel Nabil |
| Contributors | KyoungSoo Park, Steven Levitan, Sangyeun Cho, Rami Melhem |
| Publisher | University of Pittsburgh |
| Source Sets | University of Pittsburgh |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.library.pitt.edu/ETD/available/etd-11192009-103639/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to University of Pittsburgh or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0022 seconds