Applications of sketches in network traffic measurement: A survey

Hui Han, Zheng Yan*, Xuyang Jing, Witold Pedrycz

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review


Accurate and timely network traffic measurement is essential for network status monitoring, network fault analysis, network intrusion detection, and network security management. With the rapid development of the network, massive network traffic brings severe challenges to network traffic measurement. However, existing measurement methods suffer from many limitations for effectively recording and accurately analyzing big-volume traffic. Recently, sketches, a family of probabilistic data structures that employ hashing technology for summarizing traffic data, have been widely used to solve these problems. However, current literature still lacks a thorough review on sketch-based traffic measurement methods to offer a comprehensive insight on how to apply sketches for fulfilling various traffic measurement tasks. In this paper, we provide a detailed and comprehensive review on the applications of sketches in network traffic measurement. To this end, we classify the network traffic measurement tasks into four categories based on the target of traffic measurement, namely cardinality estimation, flow size estimation, change anomaly detection, and persistent spreader identification. First, we briefly introduce these four types of traffic measurement tasks and discuss the advantages of applying sketches. Then, we propose a series of requirements with regard to the applications of sketches in network traffic measurement. After that, we perform a fine-grained classification for each sketch-based measurement category according to the technologies applied on sketches. During the review, we evaluate the performance, advantages and disadvantages of current sketch-based traffic measurement methods based on the proposed requirements. Through the thorough review, we gain a number of valuable implications that can guide us to choose and design proper traffic measurement methods based on sketches. We also review a number of general sketches that are highly expected in modern network systems to simultaneously perform multiple traffic measurement tasks and discuss their performance based on the proposed requirements. Finally, through our serious review, we summarize a number of open issues and identify several promising research directions.

Original languageEnglish
Pages (from-to)58-85
Number of pages28
JournalInformation Fusion
Early online dateJan 2022
Publication statusPublished - Jun 2022
MoE publication typeA1 Journal article-refereed


  • Cardinality estimation
  • Change anomalies
  • Flow size estimation
  • Network traffic measurement
  • Persistent spreader detection
  • Sketches


Dive into the research topics of 'Applications of sketches in network traffic measurement: A survey'. Together they form a unique fingerprint.

Cite this