Spatial Sketch Configuration for Traffic Measurement in Software Defined Networks

Da Yao, Hongli Xu, Haibo Wang, Liusheng Huang, Huaqing Tu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


Flow-level traffic statistics information plays a vital role for many applications, such as network management, attack detection and packet engineering. Compared with TCAM-based counting and packet sampling, sketches can provide flow-level traffic estimation with bounded error using compact data structures, thus have been widely used for traffic measurement. Under many practical applications, several different sketches should be deployed on each switch to support various requirements of traffic measurement. If each arrival packet is measured by all sketches on a switch (i.e., without sketch configuration), it may lead to redundant measurement, and cost massive CPU resource, especially with increasing traffic amount. Due to limited computing capacity on most commodity switches, heavy traffic measurement overhead will seriously interfere with the basic rule operations, especially when some switches need to deal with many new-arrival flows or update routes of existing flows. To address this challenge, we propose a spatial sketch configuration problem for the general case. As a case study, we present optimal sketch configuration for proportional fairness with per-switch computing capacity constraint (SCP), so that each sketch can measure enough flows without unduly restricting the number of flows measured by other sketches in the network. Due to the NP-hardness of this problem, a greedy-based algorithm with approximation ratio 1/3 is presented, and its time complexity is analyzed. We implement the proposed sketch configuration solution on the platform. The extensive simulation results and the experimental results show that the proposed algorithm can measure traffic of 44%–91% more flows compared with the existing solutions with CPU resource constraint.

Original languageEnglish
Title of host publicationWireless Algorithms, Systems, and Applications - 16th International Conference, WASA 2021, Proceedings
EditorsZhe Liu, Fan Wu, Sajal K. Das
Number of pages15
StatePublished - 2021
Event16th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2021 - Nanjing, China
Duration: Jun 25 2021Jun 27 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12939 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2021

Bibliographical note

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.


  • Approximation
  • Flow-level statistics
  • Sketch configuration
  • Software defined networks
  • Traffic measurement

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Spatial Sketch Configuration for Traffic Measurement in Software Defined Networks'. Together they form a unique fingerprint.

Cite this