Sketching the data center network traffic

Data center networks are expected to support emerging types of bandwidth-hungry applications to perform real-time search and data analysis. They impose significant challenges to identify the cause of congestion down to the flow level on a physical port of a switch/router in real time with high accuracy, low computational complexity and good scalability with the exploding data. In this article, we propose two sketch-based algorithms, called α-CU and P(d)-CU, based on the existing Conservative Update (CU) approach. α-CU adds no extra implementation cost to traditional CU, but successfully trades off the achieved error with time complexity. P(d)-CU fully considers the amount of skew for different network services to aggregate traffic statistics of each service type at individual horizontally partitioned sketches. We also introduce a way to produce the real-time moving average of the reported results. The effectiveness of the proposed algorithms is verified by sufficient experiments by a real DCN trace.