The Taub Faculty of Computer Science Events and Talks

In this talk we will present improvements to the accuracy, memory and speed of counting algorithms. Counters are one of the most basic building blocks in networking, big data analytics and other fields. To cope with increasing line rates, counters must be accessed quickly and be kept on small fast memory. Further, to reach concise and exhaustive conclusions about data, accurate estimations must be kept for large numbers of counters. We first present a closed form representation of the optimal estimation function, which was previously known only in recursive form. Previous works were able to use this function to optimize the largest counter in an array of counters, but they compromised the accuracy of smaller counters in the array to do so. We introduce Independent Counter Estimation Buckets (ICE-Buckets), which improves the accuracy of all counters, large and small. Finally, we improve the speed of traffic volume estimation for elephant flows. We present the first asymptotically optimal algorithm for solving this problem in terms of both space and time complexity. This improves previous approaches, which can monitor the number of packets in a heavy hitter flow in optimal time but not the number of bytes in an elephant flow. We evaluate our work on real packet traces, demonstrating an up to X2.5 speedup compared to the best alternative.