EAGER: Universal Sketches for Network Monitoring

点击翻译按钮获取中文摘要

Network management is multi-faceted and encompasses a range of tasks including traffic engineering, attack and anomaly detection, and forensic analysis. Each such management task requires accurate and timely statistics on different application-level metrics of interest, such as the flow size distribution, "heavy hitters" (frequently occurring data values), and entropy measures, as well as the detection of changes or unusual patterns. Streaming algorithms have generated many important practical advances since the creation of the field in the mid 1990s. For a given data set, these techniques typically use one pass over the data, and use a small amount of memory to compute a desired statistic. A class of randomized algorithms known as "sketches" has contributed to many practical solutions for databases, networks, and other domains which entail processing large amounts of data, such as astronomy. In preliminary work, the PI with collaborators introduced a flexible technique, UnivMon (short for Universal Monitoring), for a wide range of monitoring tasks by leveraging recent theoretical advances in streaming algorithms. The main task of this project is to significantly improve the theoretical foundations of UnivMon. The UnivMon tool should be a particularly useful artifact for exposing undergraduate students to streaming and network monitoring concepts. The PI also believes that the topic of this project presents a compelling opportunity for developing graduate students with expertise in the theory of network monitoring. In particular, the PI plans to leverage his existing graduate-level course offerings as vehicles to integrate findings from this research project.While the body of work in data streaming and sketching has made significant contributions to network monitoring, each network metric of interest requires special purpose algorithms. An ideal monitoring framework would offer generality by delaying the binding to specific applications of interest but at the same time providing the required fidelity for estimating these metrics. Achieving generality and high fidelity simultaneously has been an elusive goal both in theory and in practice. Universal streaming develops a single universal sketch which is provably accurate for estimating a large class of functions. In essence, the generality of universal streaming enables one to delay binding the data plane to specific monitoring tasks, while still providing accuracy that is comparable to (if not better than) running custom sketches using similar compute resources. To accomplish the system improvements needed for practical deployment, the project will attempt to advance the state of the theory by solving the following open problems: (1) extending the PI's preliminary techniques to handle data expiration, thus allowing the maintenance of statistics over a window of recent data; and (2) constructing algorithms for computing universal sketches with memory usage within a constant factor of optimal, refining previous results that are within a polylogarithmic factor of optimal.