CS-Sketch: Compressive Sensing Enhanced Sketch for Full Traffic Measurement

Traffic measurement is crucial for lots of network applications such as network management, anomaly detection, and traffic engineering. Although existing Sketch-based algorithms have made lots of efforts for traffic measurement, they can only perform accurate measurements of the elephant flows while badly on the mice flows. Inspired by Compressive Sensing(CS), we design a lightweight traffic measurement framework CS-Sketch which looks flow size vector of all flows as a signal vector and compresses it to a measurement vector through a sensing matrix. Two main techniques are proposed. In the switch side, we construct a sparse 0-1 sensing matrix through the linear hash mapping operations based on the CM-Sketch, which can inherit the advantages of CM-Sketch to track the flow size when packets come with lightweight update operations. In the data center side, to accurately estimate the flow size of each flow through the measurement vector at high speed, we propose a fast implementation of the OMP algorithm based on the efficient inverse Cholesky factorization. We have performed extensive experiments to compare our CS-Sketch with the state-of-art Sketch-based solutions by using three real-world datasets. Our evaluations demonstrate that our CS-Sketch can achieve the highest accurate full traffic measurement with the lowest computational and communication costs, where the reconstruction relative error of 99.86% flow is less than 0.1%.

I. Introduction

Traffic measurement is vitally essential in network fields [1], [2], [3], [4], [5]. To better support various network operations and management tasks, such as network diagnosis [6], [7], anomaly detection [8], [9], [10], [11], it requires a full traffic measurement that can accurately measure the size of each flow (e.g., source/destination IP, source/destination port, and protocol) in each device (e.g., switches). Existing studies have made lots of efforts for traffic measurement, which can be roughly divided into the following two categories.