The Taub Faculty of Computer Science Events and Talks

Counting network flows’ statistics is at the heartof network monitoring, network security, and similar networkfunctionalities.Virtualization in datacenters as well as networkfunction virtualization (NFV) trends push traditional hardwareimplementations intovirtual switchesrunning as software onthe host’s CPU.The problem is that Bloom filter based datastructures for maintaining flows’ statistics such as count-minsketch and spectral Bloom filter are not optimal for softwareimplementations. TinyTable is a recent alternative which wasshown to be better adapted for being run in software, as itonly computes a single hash function, only accesses a singlecache line per operation, and consumes significantly less space,making it easier to maintain the entire data structure in cache.Yet, the original construction of TinyTable is sequential, whilemodern CPUs are multi-core and multi-threaded.This paper closes this gap by designing a concurrent version of TinyTable.Our implementation is externally lock-free, and exhibits goodspeedups.It particular, our construction can handle the levelof throughput expected in modern virtual switches