Sketching Big Network Data

Friday, November 13, 2015 - 14:30
HH 108
Dr. Shigang Chen

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.


Dr. Shigang Chen ( is a professor with Department of Computer and Information Science and Engineering at University of Florida. He received his B.S. degree in computer science from University of Science and Technology of China in 1993. He received M.S. and Ph.D. degrees in computer science from University of Illinois at Urbana-Champaign in 1996 and 1999, respectively. After graduation, he had worked with Cisco Systems for three years before joining University of Florida in 2002. He served on the technical advisory board for Protego Networks Inc. in 2002-2003 and as CTO for Chance Media Inc. during 2012-2014. His research interests include computer networks, Internet security, wireless communications, and distributed computing. He published 150 peer-reviewed journal/conference papers. He received IEEE Communications Society Best Tutorial Paper Award and NSF CAREER Award. He holds 12 US patents. He is an associate editor for IEEE/ACM Transactions on Networking, and served as editors for a number of other journals. He served in various chair positions or as committee members for numerous conferences. He is a senior member of IEEE.