  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.
