A survey of sketches in traffic measurement: Design, Optimization, Application and Implementation

• DOI: 10.48550/arxiv.2012.07214
• Publication Date: 2020-01-01
• Authors: Shangsen Li; Lailong Luo; Deke Guo; Qianzhen Zhang; Pengtao Fu
• Keywords: Sketch; Network monitoring; Cardinality (data modeling)

Network measurement probes the underlying network to support upper-level decisions such as management, update, maintenance, defense and beyond. Due massive, speedy, unpredictable features of flows, sketches are widely implemented in nodes approximately record frequency or estimate cardinality flows. At their cores, usually maintain one multiple counter array(s), rely on hash functions select counter(s) for each flow. Then space-efficient from distributed aggregated provide statistics undergoing Currently, tremendous redesigns optimizations have been proposed improve better performance. However, existing reviews surveys mainly focus particular aspect tasks. Researchers engineers community desire an all-in-one survey that covers entire processing pipeline sketch-based measurement. To this end, we present first comprehensive area. We introduce preparation flows measurement, then detail most recent investigations design, aggregation, decoding, application implementation summarize efforts, carry out in-depth study literature, covering more than 90 sketch designs optimization strategies. Furthermore, conduct a analysis qualitative/quantitative comparison designs. Finally,we highlight open issues future research.