TY - GEN
T1 - Scalable, optimal flow routing in datacenters via local link balancing
AU - Sen, Siddhartha
AU - Shue, David
AU - Ihm, Sunghwan
AU - Freedman, Michael J.
PY - 2013
Y1 - 2013
N2 - 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. Even recent proposals like centralized scheduling or end-host multi-pathing give suboptimal throughput, and they suffer from poor scalability and other limitations. We present a simple, switch-local algorithm called LocalFlow that is optimal (under standard assumptions), scalable, and practical. Although LocalFlow may split an individual flow (this is necessary for optimality), it does so infrequently by considering the aggregate flow per destination and allowing slack in distributing this flow. We use an optimization decomposition to prove Local-Flow's optimality when combined with unmodified end hosts' TCP. Splitting flows presents several new technical challenges that must be overcome in order to interact efficiently with TCP and work on emerging standards for programmable, commodity switches. Since LocalFlow acts independently on each switch, it is highly scalable, adapts quickly to dynamic workloads, and admits flexible deployment strategies. We present detailed packet-level simulations comparing LocalFlow to a variety of alternative schemes, on real datacenter workloads.
AB - 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. Even recent proposals like centralized scheduling or end-host multi-pathing give suboptimal throughput, and they suffer from poor scalability and other limitations. We present a simple, switch-local algorithm called LocalFlow that is optimal (under standard assumptions), scalable, and practical. Although LocalFlow may split an individual flow (this is necessary for optimality), it does so infrequently by considering the aggregate flow per destination and allowing slack in distributing this flow. We use an optimization decomposition to prove Local-Flow's optimality when combined with unmodified end hosts' TCP. Splitting flows presents several new technical challenges that must be overcome in order to interact efficiently with TCP and work on emerging standards for programmable, commodity switches. Since LocalFlow acts independently on each switch, it is highly scalable, adapts quickly to dynamic workloads, and admits flexible deployment strategies. We present detailed packet-level simulations comparing LocalFlow to a variety of alternative schemes, on real datacenter workloads.
KW - Datacenter networks
KW - Flow routing
KW - Local algorithms
KW - Optimization decomposition
UR - http://www.scopus.com/inward/record.url?scp=84893376415&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893376415&partnerID=8YFLogxK
U2 - 10.1145/2535372.2535397
DO - 10.1145/2535372.2535397
M3 - Conference contribution
AN - SCOPUS:84893376415
SN - 9781450321013
T3 - CoNEXT 2013 - Proceedings of the 2013 ACM International Conference on Emerging Networking Experiments and Technologies
SP - 151
EP - 162
BT - CoNEXT 2013 - Proceedings of the 2013 ACM International Conference on Emerging Networking Experiments and Technologies
PB - Association for Computing Machinery
T2 - 2013 9th ACM International Conference on Emerging Networking Experiments and Technologies, CoNEXT 2013
Y2 - 9 December 2013 through 12 December 2013
ER -