EAGER: Universal Sketches for Network Monitoring

网络管理是多方面的，包括一系列任务，包括流量工程、攻击和异常检测以及取证分析。 每个这样的管理任务都需要对感兴趣的不同应用级度量进行准确和及时的统计，例如流大小分布、“重打击者”（频繁出现的数据值）和熵度量，以及检测变化或异常模式。 自20世纪90年代中期创建该领域以来，流算法已经产生了许多重要的实际进展。 对于给定的数据集，这些技术通常使用一遍数据，并使用少量的内存来计算所需的统计数据。 一类被称为“草图”的随机算法为数据库、网络和其他需要处理大量数据的领域（如天文学）提供了许多实用的解决方案。 在初步工作中，PI与合作者引入了一种灵活的技术UnivMon（通用监控的缩写），通过利用流算法的最新理论进展来执行广泛的监控任务。 该项目的主要任务是显著提高UnivMon的理论基础。 UnivMon工具应该是一个特别有用的工件，可以让本科生接触流和网络监控概念。 PI还认为，该项目的主题为培养具有网络监控理论专业知识的研究生提供了一个引人注目的机会。 特别是，PI计划利用他现有的研究生水平的课程作为工具，以整合从这个研究项目的结果。虽然在数据流和草图的工作机构作出了重大贡献的网络监控，每个感兴趣的网络指标需要特殊用途的算法。 理想的监控框架将通过延迟绑定到感兴趣的特定应用程序来提供通用性，但同时提供估计这些指标所需的保真度。 同时实现通用性和高保真度一直是理论和实践中难以实现的目标。 通用流开发了一个单一的通用草图，它可以证明是准确的估计一大类功能。 从本质上讲，通用流的通用性使人们能够延迟将数据平面绑定到特定的监控任务，同时仍然提供与使用类似计算资源运行自定义草图相当（如果不是更好的话）的准确性。 为了实现实际部署所需的系统改进，该项目将试图通过解决以下开放问题来推进理论的状态：（1）扩展PI的初步技术以处理数据过期，从而允许在最近数据的窗口上维护统计数据;以及（2）构造用于计算通用草图的算法，其中存储器使用在最优的恒定因子内，精炼在最优的多对数因子内的先前结果。

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.