Abstract
Data center networks (DCNs) for 5G are expected to support a large number of bandwidth-hungry applications with exploding data volumes. Identifying the cause of link congestion between switch ports is critical for maintaining performance. This paper proposes two sketch-based algorithms, α-conservative update (α-CU) and P(d)-CU, to diagnose network congestion in real-time. By leveraging the inherent skewness of different network services, these methods achieve high estimation accuracy and low computational complexity. Experimental results on real DCN traces demonstrate a 50% reduction in estimation error and significant improvements in scalability compared to existing techniques.
The Challenge of 5G Network Monitoring
As 5G networks scale, DCNs must handle a massive influx of traffic from diverse applications. Identifying the specific "flow"—a sequence of packets between a source and destination—causing link congestion is a significant challenge. Traditional monitoring tools like NetFlow or sFlow rely on packet sampling, which often misses bursty "elephant flows"—the small fraction of high-volume flows responsible for the majority of network congestion.
To address this, researchers use compact data structures called sketches to summarize traffic. However, existing sketches face a "trilemma": they struggle to simultaneously provide high accuracy, low computational complexity, and high scalability. For instance, the popular Count-Min (CM) sketch is fast but prone to overestimation, while the Conservative Update (CU) sketch is more accurate but computationally expensive for high-speed 5G ports.
Proposed Sketch-Based Algorithms
The authors propose two enhancements to the Conservative Update (CU) approach to balance performance and accuracy:
- α-Conservative Update (α-CU): This probabilistic hybrid allows operators to tune the balance between speed and accuracy. For every update, the algorithm decides with probability α to perform a CU update and with probability 1−α to perform a faster CM update.
- Partitioned CU (P(d)-CU): This is the paper's primary innovation. Instead of a single large sketch, the authors partition the sketch vertically into sub-sketches dedicated to specific traffic types (e.g., HTTP, DNS). This prevents "mice" flows from one service from colliding with and corrupting the "elephant" counts of another.
- Real-time Moving Average: To handle sliding windows, they implement an exponential discounting factor (γ). This allows the system to maintain a real-time view of traffic without the memory overhead of storing multiple time-sliced sketches.
Experimental Evaluation and Insights
The study evaluates these algorithms using a real-world DCN trace from a commercial airline booking service, comprising over 29.6 million records. Analysis of this data confirmed that DCN traffic follows Zipf’s Law, where a tiny fraction of flows accounts for the vast majority of traffic volume.
Key Results
- Accuracy: P(d)-CU reduced the Average Relative Error (ARE) by at least 50% compared to the standard CU algorithm.
- Speed: P(d)-CU demonstrated an 18% reduction in compute time compared to CU, bringing it closer to the speed of the less accurate Count-Min sketch.
- Recall: All proposed algorithms achieved over 95% recall, successfully identifying the top elephant flows even with limited memory.
- Scalability: The memory cost remains fixed regardless of the number of flows, making the solution ideal for high-density 5G environments.
Conclusion
By incorporating service-aware partitioning and probabilistic updates, α-CU and P(d)-CU provide a scalable and efficient solution for real-time congestion diagnosis. The ability to isolate traffic types based on their skewness parameters allows for significantly higher accuracy without the computational penalties typically associated with high-fidelity network monitoring.
Summary updated