Summarizing data center network traffic by partitioned conservative update

Applications like search and massive data analysis running bandwidth-hungry algorithms like MapReduce in data center networks (DCNs) may lead to link congestion. Thus it is important to identify the source of congestions in real-time. In this letter, we propose a sketch-based data structure, called "P(d)-CU", to estimate the aggregated/summarized flow statistics over time that guarantees high estimation accuracy with low computational complexity, and scales well with the increase of input data size. Considering the amount of skew for flows of different network services, it partitions a two-dimensional array of counters along its depth as an enhancement to the existing Conservative Update (CU) mechanism. We show its superior performance by theoretical analysis and sufficient experimental results on a real DCN trace.