EMOMA: Exact Match in One Memory Access Articles uri icon

authors

  • PONTARELLI, SALVATORE
  • REVIRIEGO VASALLO, PEDRO
  • MITZENMACHER, MICHAEL

publication date

  • November 2018

start page

  • 2120

end page

  • 2133

issue

  • 11

volume

  • 30

International Standard Serial Number (ISSN)

  • 1041-4347

Electronic International Standard Serial Number (EISSN)

  • 1558-2191

abstract

  • An important function in modern routers and switches is to perform a lookup for a key. Hash-based methods, and in particular cuckoo hash tables, are popular for such lookup operations, but for large structures stored in off-chip memory, such methods have the downside that they may require more than one off-chip memory access to perform the key lookup. Although the number of off-chip memory accesses can be reduced using on-chip approximate membership structures such as Bloom filters, some lookups may still require more than one off-chip memory access. This can be problematic for some hardware implementations, as having only a single off-chip memory access enables a predictable processing of lookups and avoids the need to queue pending requests. We provide a data structure for hash-based lookups based on cuckoo hashing that uses only one off-chip memory access per lookup, by utilizing an on-chip pre-filter to determine which of multiple locations holds a key. We make particular use of the flexibility to move elements within a cuckoo hash table to ensure the pre-filter always gives the correct response. While this requires a slightly more complex insertion procedure and some additional memory accesses during insertions, it is suitable for most packet processing applications where key lookups are much more frequent than insertions. An important feature of our approach is its simplicity. Our approach is based on simple logic that can be easily implemented in hardware, and hardware implementations would benefit most from the single off-chip memory access per lookup.

subjects

  • Telecommunications

keywords

  • hash tables; bloom filters; external memory access