Sketching Big Network Data

The Internet has moved into the era of big network data. It presents both opportunities and technical challenges for traffic measurement functions monitoring per-flow properties, which have important applications in intrusion detection, resource management, billing and capacity planning, as well as big data analytics. Due to the practical need of processing network data in high volume and high speed, past research has strived to reduce the memory and processing overhead when measuring a large number of flows. One important thread of research in this area is based on sketches, such as the FM sketches, the LogLog sketches, and the HyperLogLog sketches. Each sketch requires multiple bits and many sketches are needed for each flow, which results in significant memory overhead. In this talk, we present a new method of virtual maximum likelihood sketches to reduce memory consumption. It embodies several new design constructs, including (1) virtual sketches that use no more than two bits per sketch on average, and (2) virtual sketch vectors that monitor all flows together with a joint data structure. Not only can the new method provide per-flow measurement with a memory of just 1 bit per flow, but also it can support differentiated services that give flows of high priorities better precision in their measurements. We also show how this research can be extended along space/time/function/application dimensions.