Network measurement probes the underlying network to support upper-level decisions such as network management, network update, network maintenance, network defense and beyond. Due to the massive, speedy, unpredictable features of network flows, sketches are widely implemented in measurement nodes to record the frequency or estimate the cardinality of flows approximately. At their cores, sketches usually maintain one or multiple counter array(s), and relies on hash functions to select the counter(s) for each flow. Then the space-efficient sketches from the distributed measurement nodes are aggregated to provide statistics of the undergoing flows. Currently, tremendous redesigns and optimizations have been proposed to further improve the sketches for better network measurement performance. However, the existing reviews or surveys mainly focus on one particular aspect of measurement tasks. Researchers and engineers in the network measurement community desire an all-in-one survey which covers the whole processing pipeline of sketch-based network measurement. To this end, we present the first comprehensive survey in this area. We first introduce the preparation of flows for measurement, then detail the most recent investigations of design, aggregation, decoding, application and implementation of sketches for network measurement. To summary the existing efforts, we conduct an in-depth study of the existing literature, covering more than 80 sketch designs and optimization strategies. Furthermore, we conduct a comprehensive analysis and qualitative/quantitative comparison of the sketch designs. Finally, we highlight the open issues for future sketch-based network measurement research.
翻译:网络测量探索基本网络,以支持诸如网络管理、网络更新、网络维护、网络防御等高层决策。由于网络流动的庞大、迅速和不可预测的特征,在测量节点中广泛执行草图,以记录流动的频率或估计其基本程度。在核心方面,草图通常保持一个或多个反面阵列,并依靠散列功能为每次流动选择计数器。然后,对分布式测量节点的空间高效草图进行汇总,以提供流动数据。目前,提出了巨大的重新设计和优化,以进一步改进网络测量业绩的草图。然而,现有的审查或调查主要侧重于测量任务的一个特定方面。网络测量社区的研究人员和工程师希望进行一次全方位调查,涵盖基于素描网络测量的整个处理管道。为此目的,我们提出该领域的第一次全面调查。我们首先介绍流动的公开调查,然后详细介绍对网络计量工作进行的设计、汇总、分解、应用和执行的最新调查。此外,我们还要对目前进行的一项深度研究/定性分析。我们最后要对现有的草图进行了80项研究,我们还要进行一项深度研究。