Scalable, Optimal Flow Routing in Datacenters via Local Link Balancing
Report ID: TR-943-12Author: Freedman, Michael J. / Ihm, Sunghwan / Sen, Siddhartha / Shue, David
Date: 2012-12-00
Pages: 12
Download Formats: |PDF|
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.