Efficient flow sampling with back-annotated Cuckoo hashing

One of the applications of network traffic monitoring is to detect anomalies and security threats. Due to the huge number of packets that traverse networks, monitoring is typically implemented by sampling the traffic. Sampling can be done per packet or per flow. For flow sampling, the decision to select a flow can be purely random or based on some properties of the flows. In this later case, each incoming packet has to be compared against the set of flows being monitored to determine if the packet belongs to any of those flows. This matching can be implemented using a content addressable memory (CAM) or hash based data structures. Among those, one option is Cuckoo hashing that provides good memory utilization and a deterministic worst number of memory accesses. However, in the case of flow sampling, most packets will not belong to any of the flows being monitored. Therefore, all tables will be accessed and the worst case number of accesses will be required thus reducing throughput. In this letter, a technique to reduce the average number of accesses to search for items that are not stored in the Cuckoo hash is proposed and evaluated. The results show that the proposed scheme can significantly reduce the average number of accesses in a flow sampling application. This means that the technique can be used to increase the throughput substantially.