EAGER: Universal Sketches for Network Monitoring

EAGER：网络监控通用草图

• 批准号: 1650041
• 负责人: Vladimir Braverman
• 金额: $ 10万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1650041&HistoricalAwards=false
• 关键词: EAGER; Universal; Sketches; 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.

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

项目成果

Streaming symmetric norms via measure concentration

• DOI: 10.1145/3055399.3055424
• 发表时间: 2015-11
• 期刊: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Jarosław Błasiok;Vladimir Braverman;Stephen R. Chestnut;Robert Krauthgamer;Lin F. Yang

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows

• DOI: 10.4230/lipics.approx-random.2018.7
• 发表时间: 2018-05
• 期刊: ArXiv
• 作者: V. Braverman;Elena Grigorescu;Harry Lang;David P. Woodruff;Samson Zhou

Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order

• 发表时间: 2016-09
• 作者: V. Braverman;Stephen R. Chestnut;Robert Krauthgamer;Yi Li;David P. Woodruff;Lin F. Yang

Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams

仅插入流的度量 k 中值的精确低空间近似

• 发表时间: 2017
• 期刊: Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2017
• 作者: Braverman, Vladimir;Lang, Harry;Levin, Keith
• 通讯作者: Levin, Keith

ASAP: Fast, Approximate Graph Pattern Mining at Scale

• 发表时间: 2018
• 作者: A. Iyer;Zaoxing Liu;Xin Jin;S. Venkataraman;V. Braverman;I. Stoica