TY - GEN

T1 - Brief announcement

T2 - 25th International Symposium on Distributed Computing, DISC 2011

AU - Sen, Siddhartha

AU - Ihm, Sunghwan

AU - Ousterhout, Kay

AU - Freedman, Michael J.

PY - 2011/11/2

Y1 - 2011/11/2

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

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

UR - http://www.scopus.com/inward/record.url?scp=80055027981&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80055027981&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-24100-0_20

DO - 10.1007/978-3-642-24100-0_20

M3 - Conference contribution

AN - SCOPUS:80055027981

SN - 9783642240997

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 205

EP - 207

BT - Distributed Computing - 25th International Symposium, DISC 2011, Proceedings

Y2 - 20 September 2011 through 22 September 2011

ER -