Efficient load balancing over asymmetric datacenter topologies

Datacenter networks are often structured as multi-rooted trees to provide high bisection bandwidth at low cost. To utilize the available bisection bandwidth, an efficient load balancing algorithm is required. Under symmetric network conditions, packet spraying is known to perform well, as it enables fine-grained (packet-level) load balancing over equal cost paths. However, packet spraying performs poorly in asymmetric topologies. To make packet spraying effective under asymmetry while retaining its simplicity, we propose SAPS, “Symmetric Adaptive Packet Spraying”, a Software-Defined Networking (SDN) based scheme that uses packet spraying over symmetric virtual topologies. SAPS is based on the key insight that if we provide each flow with a symmetric view of the network fabric, then packet spraying can produce near-optimal performance. Through simulations and testbed experiments, we evaluate SAPS. Over a variety of application workloads and asymmetric network scenarios, including single and multiple link failures, results indicate that SAPS performs well, e.g., under single link failure, outperforming state-of-the-art load balancing schemes by up to 61% for average flow completion times.