Skip to main content

Brief Announcement: Bridging the Theory-Practice Gap in Multi-commodity Flow Routing

Author(s): Sen, Siddhartha; Ihm, Sunghwan; Ousterhout, Kay; Freedman, Michael J

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1sv71
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSen, Siddhartha-
dc.contributor.authorIhm, Sunghwan-
dc.contributor.authorOusterhout, Kay-
dc.contributor.authorFreedman, Michael J-
dc.date.accessioned2021-10-08T19:50:32Z-
dc.date.available2021-10-08T19:50:32Z-
dc.date.issued2011en_US
dc.identifier.citationSen, Siddhartha, Sunghwan Ihm, Kay Ousterhout, and Michael J. Freedman. "Brief announcement: Bridging the theory-practice gap in multi-commodity flow routing." In International Symposium on Distributed Computing (2011): pp. 205-207. doi:10.1007/978-3-642-24100-0_20en_US
dc.identifier.urihttps://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.446.1391&rep=rep1&type=pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1sv71-
dc.description.abstractIn 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 ๎ˆท={(๐‘ ๐‘–,๐‘ก๐‘–,๐‘‘๐‘–)} . 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.en_US
dc.format.extent205 - 207en_US
dc.language.isoen_USen_US
dc.relation.ispartofInternational Symposium on Distributed Computingen_US
dc.rightsAuthor's manuscripten_US
dc.titleBrief Announcement: Bridging the Theory-Practice Gap in Multi-commodity Flow Routingen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1007/978-3-642-24100-0_20-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
TheoryPrac.pdf89.24 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.