CTS Sketch: A Sketch Scheme for Precise Identification of Top-k Flows Combined with SDN
Xiaolin Yang, Kai Yang, Hao Zhang, Ge Jin, Yifei Lu · 2024
Identifying elephant flows in a network is crucial for network traffic measurement, significantly impacting congestion control optimization, anomaly detection, and traffic engineering. With increasing network link rates and limited on-chip storage space, existing algorithms face severe challenges in maintaining measurement accuracy. To address these issues, Sketch data structures have emerged, allowing the recording of all traffic characteristics within limited on-chip storage. However, due to the approximate nature of Sketch, its measurement accuracy often falls short of high precision requirements. In this paper, we propose a Sketch algorithm combined with an SDN (Software-defined Networking) controller, termed CTS (Combine the Two-Stage SDN) Sketch, to enhance the accuracy of identifying top-k elephant flows through additional filtering. Furthermore, we conduct measurements exclusively at edge switches, uploading the distributed Sketch measurement results to the controller to reduce the load on central devices. By leveraging the advantages of edge computing, we capture and process traffic information promptly. Experimental results show that CTS Sketch achieves an accuracy rate of 99.99% with relatively small memory capacity, reducing error by approximately three orders of magnitude compared to existing algorithms.