  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 reduces significantly 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.
