Brief announcement: Bridging the theory-practice gap in multi-commodity flow routing

Siddhartha Sen, Sunghwan Ihm, Kay Ousterhout, Michael J. Freedman

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

Abstract

In the concurrent multi-commodity flow problem, we are given a capacitated network G = (V,E) of switches V connected by links E, and a set of commodities K = {(si, ti, di)}. The objective is to maximize the minimum fraction λ of any demand d i that is routed from source s i to target t i . This problem has been studied extensively by the theoretical computer science community in the sequential model (e.g., [4]) and in distributed models (e.g., [2,3]). Solutions in the networking systems community also fall into these models (e.g., [1,6,5]), yet none of them use the state-of-the-art algorithms above. Why the gap between theory and practice? This work seeks to answer and resolve this question. We argue that existing theoretical models are ill-suited for real networks (§2) and propose a new distributed model that better captures their requirements (§3). We have developed optimal algorithms in this model for data center networks (§4); making these algorithms practical requires a novel use of programmable hardware switches. A solution for general networks poses an intriguing open problem.

Original languageEnglish (US)
Title of host publicationDistributed Computing - 25th International Symposium, DISC 2011, Proceedings
Pages205-207
Number of pages3
DOIs
StatePublished - Nov 2 2011
Event25th International Symposium on Distributed Computing, DISC 2011 - Rome, Italy
Duration: Sep 20 2011Sep 22 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6950 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other25th International Symposium on Distributed Computing, DISC 2011
CountryItaly
CityRome
Period9/20/119/22/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Brief announcement: Bridging the theory-practice gap in multi-commodity flow routing'. Together they form a unique fingerprint.

  • Cite this

    Sen, S., Ihm, S., Ousterhout, K., & Freedman, M. J. (2011). Brief announcement: Bridging the theory-practice gap in multi-commodity flow routing. In Distributed Computing - 25th International Symposium, DISC 2011, Proceedings (pp. 205-207). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6950 LNCS). https://doi.org/10.1007/978-3-642-24100-0_20