Academic
Publications
CHAP: Enabling Efficient Hardware-Based Multiple Hash Schemes for IP Lookup

CHAP: Enabling Efficient Hardware-Based Multiple Hash Schemes for IP Lookup,10.1007/978-3-642-01399-7_59,Michel Hanna,Socrates Demetriades,Sangyeun Ch

CHAP: Enabling Efficient Hardware-Based Multiple Hash Schemes for IP Lookup   (Citations: 3)
BibTex | RIS | RefWorks Download
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.
Conference: Networking - Networking , pp. 756-769, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The class of hash-based hardware packet forwarding engines has become popular recently [9,10,11]...

    Michel Hannaet al. A Novel Scalable IPv6 Lookup Scheme Using Compressed Pipelined Tries

    • ...153 time complexity bounds [8, 6, 9, 21]. These solutions were subsequently modified and extended to enhance their performance [17, 18, 24]...
    • ...The left corner of Figure 1 shows how a row may be divided into entries (cells) to store prefixes, their length and their port number for the PF application [3, 8]...
    • ...In the latter case, the shorter prefixes are kept in a small fast memory that is searched in parallel with the main lookup table [8]...
    • ...To be able to stop at the first matching prefix during search in a PF restricted multiple hashing system, we store the prefixes according to their length from the longest to the shortest [8]...
    • ...Content-based HAsh Probing (CHAP) for the PF application [8]...
    • ...While regular probing uses predetermined o!sets to solve that problem, CHAP [8] uses a mix of restricted multiple hash functions (all use the most significant 16 bits) and probing in the following probing sequence: h0(k),h1(k),···,hH"1 (k)," 0[h0(k)], " 1[h1(k)],···," m"1 [hH"1 (k)] (1)...
    • ...Figure 10 shows CHAP(3,3) when m = H = 3. As presented in [8], CHAP uses restricted multiple hash functions where each function takes the most significant 16 bits; we apply our PH scheme to enhance CHAP performance...

    Michel Hannaet al. Progressive hashing for packet processing using set associative memory

Sort by: