Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

CHAP : Enabling efficient hardware-based multiple hash schemes for IP lookup

Hanna, M and Demetriades, S and Cho, S and Melhem, R (2009) CHAP : Enabling efficient hardware-based multiple hash schemes for IP lookup. UNSPECIFIED. UNSPECIFIED.

[img]
Preview
PDF (CS TR 08 161)
Primary Text
Available under License : See the attached license file.

Download (341kB) | Preview
[img] Plain Text (licence)
Available under License : See the attached license file.

Download (1kB)

Abstract

Building a high performance IP lookup engine remains a challenge due to increasingly stringent throughput requirements and the growing size of IP tables. An emerging approach for IP lookup is the use of set associative memory architecture, which is basically a hardware implementation of an open addressing hash table with the property that each row of the hash table can be searched in one memory cycle. 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 bucket overflows. This paper presents a new simple hash probing scheme called CHAP (Content-based HAsh Probing) that tackles the hash overflow problem. In CHAP, the probing is based on the content of the hash table, thus avoiding the classical side effects of probing. We show through experimenting with real IP tables how CHAP can effectively deal with the overflow. © IFIP International Federation for Information Processing 2009.


Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: Monograph (UNSPECIFIED)
Status: Published
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Hanna, M
Demetriades, S
Cho, S
Melhem, Rmelhem@cs.pitt.eduMELHEM
Date: 17 July 2009
Date Type: Publication
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Journal or Publication Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume: 5550 L
Page Range: 756 - 769
Event Type: Conference
DOI or Unique Handle: 10.1007/978-3-642-01399-7_59
Institution: University of Pittsburgh
Department: Computer Science
Schools and Programs: Dietrich School of Arts and Sciences > Computer Science
Dietrich School of Arts and Sciences > Computer Science > Computer Science Technical Reports
Refereed: No
ISBN: 9783642013980
ISSN: 0302-9743
University of Pittsburgh Series: Computer Science Technical Reports
Other ID: CS TR 08 161
Date Deposited: 12 Mar 2013 18:11
Last Modified: 27 Sep 2022 10:55
URI: http://d-scholarship.pitt.edu/id/eprint/17760

Metrics

Monthly Views for the past 3 years

Plum Analytics

Altmetric.com


Actions (login required)

View Item View Item