CuCoTrack: Cuckoo filter based connection tracking Articles uri icon

authors

  • REVIRIEGO VASALLO, PEDRO
  • PONTARELLI, SALVATORE
  • LEVY, GIL

publication date

  • July 2019

start page

  • 55

end page

  • 60

volume

  • 147

International Standard Serial Number (ISSN)

  • 0020-0190

Electronic International Standard Serial Number (EISSN)

  • 1872-6119

abstract

  • This paper introduces CuCoTrack, a cuckoo hash based data structure designed to efficiently implement connection tracking. The proposed scheme exploits the fact that queries always match one existing connection to compress the 5-tuple that identifies the connection. This significantly reduces the amount of memory needed to store the connections and also the memory bandwidth needed for lookups. CuCoTrack uses a dynamic fingerprint to avoid collisions thus ensuring that queries are completed in at most two memory accesses and facilitating a hardware implementation. The proposed scheme has been analyzed theoretically and validated by simulation. The results show that using 16 bits for the fingerprint is enough to avoid collisions in practical configurations. (C) 2019 Elsevier B.V. All rights reserved.

keywords

  • data structures; exact match; cuckoo filter; approximate membership check; connection tracking