Per-packet load-balanced, low-latency routing for clos-based data center networks

TLDR

Clos‑based networks such as Fat‑tree and VL2 are widely deployed in data centers, yet per‑flow routing leads to low utilization and a long latency tail. This work proposes a per‑packet round‑robin routing algorithm, Digit‑Reversal Bouncing (DRB), to improve load balancing in these topologies. DRB is implemented as a per‑packet round‑robin scheme that can be deployed on commodity switches. DRB achieves perfect packet interleaving, keeps queues bounded and re‑sequencing buffers small even at 100 % load, and experiments on a 54‑server Fat‑tree confirm its resilience to failures and graceful performance degradation.

Abstract

Clos-based networks including Fat-tree and VL2 are being built in data centers, but existing per-flow based routing causes low network utilization and long latency tail. In this paper, by studying the structural properties of Fat-tree and VL2, we propose a per-packet round-robin based routing algorithm called Digit-Reversal Bouncing (DRB). DRB achieves perfect packet interleaving. Our analysis and simulations show that, compared with random-based load-balancing algorithms, DRB results in smaller and bounded queues even when traffic load approaches 100%, and it uses smaller re-sequencing buffer for absorbing out-of-order packet arrivals. Our implementation demonstrates that our design can be readily implemented with commodity switches. Experiments on our testbed, a Fat-tree with 54 servers, confirm our analysis and simulations, and further show that our design handles network failures in 1-2 seconds and has the desirable graceful performance degradation property.