Scalable, Optimal Flow Routing in Datacenters via Local Link Balancing

Abstract:

Datacenter networks should support high network utilization. Yet
today?s routing is typically load agnostic, so large flows can starve
other flows if routed through overutilized links. Recent proposals
for datacenter routing, such as centralized scheduling or end-host
multi-pathing, do not offer optimal throughput, and they suffer from
scalability concerns and other limitations.

We observe that most datacenter networks have a symmetry property
that admits a better solution. We develop a simple, switchlocal
algorithm called LocalFlow that routes the maximum multicommodity
flow in these networks, while tolerating failures and
asymmetry. LocalFlow evades existing hardness results by allowing
flows to be fractionally split, but it minimizes the number of split
flows by considering the aggregate flow per destination and allowing
slack in the splitting. Through an optimization decomposition,
we show that LocalFlow, in conjunction with unmodifed end hosts?
TCP, achieves an optimal solution. Splitting flows presents several
new technical challenges that must be overcome in order to achieve
high accuracy, interact properly with TCP, and be implementable
on emerging standards for programmable, commodity switches.

LocalFlow acts independently on each switch. This makes it
highly scalable, allows it to adapt quickly to dynamic workloads,
and enables flexibility in the deployment of its control-plane scheduling
logic. We present detailed packet-level simulations that demonstrate
LocalFlow?s practicality and optimality, comparing it to a variety
of alternative schemes and configurations, using distributions
and traces from real datacenter workloads.