Congestion-Aware Load Balancing in Data Center Networks

Abstract

Data center networks often use multi-rooted Clos topologies to provide a large number of equal-cost paths between two hosts. Load balancing traffic among the paths is important for high performance and low latency.

However, it is well known that ECMP—the de facto load balancing scheme—performs poorly in data center networks. The main culprit of ECMP’s problems is its congestion agnostic nature, which fundamentally limits its ability to deal with network dynamics. Distributed congestion-aware load balancing is a promising solution in which switches monitor congestion levels of each path and direct flows to less congested paths. The crux of designing a congestion-aware load balancing protocol is that we need to know real-time (in the order of RTT) congestion information from all paths between the flow’s source and destination. It is challenging to acquire global congestion information for a large scale network.

In this thesis, we present two novel distributed congestion-aware load balancing protocols for data center networks.

• Expeditus: a distributed congestion-aware load balancing protocol targeted at general 3-tier Clos topologies. It uses simple local information collection, where a switch only monitors its egress and ingress links loads. It further employs a novel two-stage path selection mechanism to aggregate relevant information across switches and make path selection decision.

• Luopan: a sampling based load balancing protocol that operates at flowcell granularity. It periodically samples a few paths for each destination switch and directs flowcells to the least congested one. It could be applied to more general topologies and is robust to topological asymmetries.

We evaluate them with prototype experiments, as well as large-scale packet-level ns-3 simulations using empirical flow size distributions from production networks. The experiment results demonstrate that Expeditus and Luopan greatly reduce tail flow completion times (FCT) for mice flows and mean FCT for medium and elephant flows.

Date of Award	20 Aug 2018
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Hong XU (Supervisor) & Cong WANG (Co-supervisor)