Scalable, optimal flow routing in datacenters via local link balancing

Siddhartha Sen, David Shue, Sunghwan Ihm, Michael J. Freedman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

71 Scopus citations

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. 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.

Original languageEnglish (US)
Title of host publicationCoNEXT 2013 - Proceedings of the 2013 ACM International Conference on Emerging Networking Experiments and Technologies
PublisherAssociation for Computing Machinery
Pages151-162
Number of pages12
ISBN (Print)9781450321013
DOIs
StatePublished - 2013
Event2013 9th ACM International Conference on Emerging Networking Experiments and Technologies, CoNEXT 2013 - Santa Barbara, CA, United States
Duration: Dec 9 2013Dec 12 2013

Publication series

NameCoNEXT 2013 - Proceedings of the 2013 ACM International Conference on Emerging Networking Experiments and Technologies

Other

Other2013 9th ACM International Conference on Emerging Networking Experiments and Technologies, CoNEXT 2013
CountryUnited States
CitySanta Barbara, CA
Period12/9/1312/12/13

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications

Keywords

  • Datacenter networks
  • Flow routing
  • Local algorithms
  • Optimization decomposition

Fingerprint Dive into the research topics of 'Scalable, optimal flow routing in datacenters via local link balancing'. Together they form a unique fingerprint.

  • Cite this

    Sen, S., Shue, D., Ihm, S., & Freedman, M. J. (2013). Scalable, optimal flow routing in datacenters via local link balancing. In CoNEXT 2013 - Proceedings of the 2013 ACM International Conference on Emerging Networking Experiments and Technologies (pp. 151-162). (CoNEXT 2013 - Proceedings of the 2013 ACM International Conference on Emerging Networking Experiments and Technologies). Association for Computing Machinery. https://doi.org/10.1145/2535372.2535397