Spatial Sketch Configuration for Traffic Measurement in Software Defined Networks

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.