EAGER: Universal Sketches for Network Monitoring

网络管理是多方面的，包括一系列任务，包括流量工程、攻击和异常检测以及取证分析。每项这样的管理任务都需要有关不同应用程序级别相关指标的准确和及时的统计数据，例如流量大小分布、“重量级”(频繁出现的数据值)和熵度量，以及对变化或异常模式的检测。自20世纪90年代中期该领域创立以来，流传输算法已经产生了许多重要的实用进展。对于给定的数据集，这些技术通常使用一次遍历数据，并使用少量内存来计算所需的统计数据。一类被称为“草图”的随机化算法为数据库、网络和其他需要处理大量数据的领域(如天文学)提供了许多实用的解决方案。在初步工作中，与合作者合作的PI引入了一种灵活的技术-UnivMon(通用监控的缩写)，通过利用流传输算法中最新的理论进步，用于广泛的监控任务。该项目的主要任务是显著改善UnivMon的理论基础。UnivMon工具应该是让本科生接触流媒体和网络监控概念的一个特别有用的工具。国际和平研究所还认为，这个项目的主题为培养具有网络监测理论专业知识的研究生提供了一个令人信服的机会。特别是，PI计划利用他现有的研究生级别的课程作为工具来整合来自此研究项目的结果。虽然数据流和草图方面的工作对网络监控做出了重大贡献，但每个感兴趣的网络指标都需要特殊用途的算法。一个理想的监测框架将通过延迟绑定到感兴趣的特定应用程序来提供一般性，但同时提供估计这些指标所需的保真度。在理论和实践中，同时实现通用性和高保真度一直是一个难以实现的目标。Universal Stream开发了一个单一的通用草图，该草图被证明对于估计一大类函数是准确的。本质上，通用流的一般性使人们能够延迟将数据平面绑定到特定监控任务，同时仍然提供与使用类似计算资源运行定制草图相当(如果不是更好)的准确性。为了完成实际部署所需的系统改进，该项目将试图通过解决以下悬而未决的问题来推动理论的发展：(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.