The Taub Faculty of Computer Science Events and Talks

Monitoring network traffic is an important building block for various management and security systems. In typical settings, the number of active flows in a network node is much larger than the number of available monitoring resources and there is no practical way to maintain "per-flow" state at the node. This situation gave rise to the recent interest in streaming algorithms where complex data structures are used to perform monitoring tasks like identifying the top-$k$ flows, Heavy Hitter (HH) flows and the Hierarchical Heavy Hitter (HHH) flows using a constant amount of memory. However, these solutions require complicated "per-packet" operations, which are not feasible in current hardware or software network nodes. In this talk we will present three different papers each studies the ability to solve a specific monitoring task in a practical manner, i.e. while using a constant amount of memeory not realted to the number of active flows, while performing at most a $O(1)$ per packe" operation and deployable on off the shelf netowrk gear. The first paper studies the detection of the top-k flows by using efficient built-in counters available in current network devices. The second paper studies the detection of the HHH flows and proposes a constant-time algorithm for detecting the HHH that does not have any convergence requirements and achieves comparable results to tate of the art. The last paper stuides the detection of HH flows and presents a practical algorithm that requires a constant amount of memory (not related to the number of flows or the number of packets) and performs at most $O(1)$ operation per packet to keep with line rate speed.