More Web Proxy on the site http://driver.im/

research-article

Augmenting anycast network flows

Authors:

Sebastian Brandt,

Klaus-Tycho Foerster,

Roger WattenhoferAuthors Info & Claims

ICDCN '16: Proceedings of the 17th International Conference on Distributed Computing and Networking

Article No.: 24, Pages 1 - 10

https://doi.org/10.1145/2833312.2833450

Published: 04 January 2016 Publication History

Abstract

Updating network flows in a real-world setting is a nascent research area, especially with the recent rise of Software Defined Networks. While augmenting s-t flows of a single commodity is a well-understood concept, we study updating flows in a multi-commodity setting: Given a directed network with flows of different commodities, how can the capacity of some commodities be increased, without reducing capacities of other commodities, when moving flows in the network in an orchestrated order? To this extent, we show how the notion of augmenting flows can be efficiently extended to multiple commodities for anycast applications.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows - theory, algorithms and applications. Prentice Hall, 1993.

Digital Library

[2]

M. Canini, P. Kuznetsov, D. Levin, and S. Schmid. Software transactional networking: concurrent and consistent policy composition. In N. Foster and R. Sherwood, editors, Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, HotSDN 2013, The Chinese University of Hong Kong, Hong Kong, China, August 16, 2013, pages 1--6. ACM, 2013.

Digital Library

[3]

M. Casado, N. Foster, and A. Guha. Abstractions for software-defined networks. Commun. ACM, 57(10):86--95, 2014.

Digital Library

[4]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009.

Digital Library

[5]

L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canad. J. Math, 8: 399--404, 1956.

[6]

L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, USA, 1962.

[7]

A. V. Goldberg, J. D. Oldham, S. A. Plotkin, and C. Stein. An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow. In R. E. Bixby, E. A. Boyd, and R. Z. Ríos-Mercado, editors, Integer Programming and Combinatorial Optimization, 6th International IPCO Conference, Houston, Texas, USA, June 22--24, 1998, Proceedings, volume 1412 of Lecture Notes in Computer Science, pages 338--352. Springer, 1998.

[8]

C. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, and R. Wattenhofer. Achieving high utilization with software-driven WAN. In D. M. Chiu, J. Wang, P. Barford, and S. Seshan, editors, ACM SIGCOMM 2013 Conference, SIGCOMM'13, Hong Kong, China, August 12--16, 2013, pages 15--26. ACM, 2013.

Digital Library

[9]

T. C. Hu. Multi-commodity network flows. Operations Research, 11(3):344--360, 1963.

Digital Library

[10]

A. Itai. Two-commodity flow. J. ACM, 25(4):596--611, 1978.

Digital Library

[11]

S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata, J. Wanderer, J. Zhou, M. Zhu, J. Zolla, U. Hölzle, S. Stuart, and A. Vahdat. B4: experience with a globally-deployed software defined wan. In D. M. Chiu, J. Wang, P. Barford, and S. Seshan, editors, ACM SIGCOMM 2013 Conference, SIGCOMM'13, Hong Kong, China, August 12--16, 2013, pages 3--14. ACM, 2013.

Digital Library

[12]

X. Jin, H. H. Liu, R. Gandhi, S. Kandula, R. Mahajan, M. Zhang, J. Rexford, and R. Wattenhofer. Dionysus: Dynamic scheduling of network updates. In F. E. Bustamante, Y. C. Hu, A. Krishnamurthy, and S. Ratnasamy, editors, ACM SIGCOMM 2014 Conference, SIGCOMM'14, Chicago, USA, August 17--22, 2014, pages 539--550. ACM, 2014.

Digital Library

[13]

L. G. Khachian. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR, 244: 1093--1096, 1979. English translation in Soviet Math. Dokl. 20, 191--194, 1979.

[14]

H. H. Liu, X. Wu, M. Zhang, L. Yuan, R. Wattenhofer, and D. A. Maltz. zUpdate: updating data center networks with zero loss. In D. M. Chiu, J. Wang, P. Barford, and S. Seshan, editors, ACM SIGCOMM 2013 Conference, SIGCOMM'13, Hong Kong, China, August 12--16, 2013, pages 411--422. ACM, 2013.

Digital Library

[15]

R. Mahajan and R. Wattenhofer. On consistent updates in software defined networks. In D. Levine, S. Katti, and D. Oran, editors, Twelfth ACM Workshop on Hot Topics in Networks, HotNets-XII, College Park, MD, USA, November 21--22, 2013, pages 20:1--20:7. ACM, 2013.

Digital Library

[16]

J. McClurg, H. Hojjat, P. Cerný, and N. Foster. Efficient synthesis of network updates. In D. Grove and S. Blackburn, editors, Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, OR, USA, June 15--17, 2015, pages 196--207. ACM, 2015.

Digital Library

[17]

T. Mizrahi and Y. Moses. Time-based updates in software defined networks. In N. Foster and R. Sherwood, editors, Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, HotSDN 2013, The Chinese University of Hong Kong, Hong Kong, China, August 16, 2013, pages 163--164. ACM, 2013.

Digital Library

[18]

T. Mizrahi and Y. Moses. On the necessity of time-based updates in SDN. In R. Sherwood, editor, Open Networking Summit 2014, ONS 2014, Santa Clara, CA, USA, March 2--4, 2014. USENIX, 2014.

[19]

T. Mizrahi, O. Rottenstreich, and Y. Moses. Timeflip: Scheduling network updates with timestamp-based TCAM ranges. In 2015 IEEE Conference on Computer Communications, INFOCOM 2015, Kowloon, Hong Kong, April 26 -- May 1, 2015, pages 2551--2559. IEEE, 2015.

[20]

A. Noyes, T. Warszawski, P. Cerný, and N. Foster. Toward synthesis of network updates. In B. Finkbeiner and A. Solar-Lezama, editors, Proceedings Second Workshop on Synthesis, SYNT 2013, Saint Petersburg, Russia, July 13th and July 14th, 2013., volume 142 of EPTCS, pages 8--23, 2014.

[21]

M. Reitblatt, N. Foster, J. Rexford, C. Schlesinger, and D. Walker. Abstractions for network update. In L. Eggert, J. Ott, V. N. Padmanabhan, and G. Varghese, editors, ACM SIGCOMM 2012 Conference, SIGCOMM '12, Helsinki, Finland - August 13-17, 2012, pages 323--334. ACM, 2012.

Digital Library

[22]

M. Reitblatt, N. Foster, J. Rexford, and D. Walker. Consistent updates for software-defined networks: change you can believe in! In H. Balakrishnan, D. Katabi, A. Akella, and I. Stoica, editors, Tenth ACM Workshop on Hot Topics in Networks (HotNets-X), HOTNETS '11, Cambridge, MA, USA - November 14-15, 2011, page 7. ACM, 2011.

Digital Library

[23]

W. Rothfarb, N. P. Shein, and I. T. Frisch. Common terminal multicommodity flow. Operations Research, 16(1):202--205, 1968.

Digital Library

[24]

A. Tanenbaum and D. Wetherall. Computer Networks (5th Edition). Pearson Prentice Hall, 2010.

Digital Library

[25]

L. Zhang, C. Wu, Z. Li, C. Guo, M. Chen, and F. C. M. Lau. Moving big data to the cloud: An online cost-minimizing approach. IEEE Journal on Selected Areas in Communications, 31(12):2710--2721, 2013.

Cited By

Zheng JXu HChen GDai HWu J(2019)Congestion-Minimizing Network Update in Data CentersIEEE Transactions on Services Computing10.1109/TSC.2016.263151912:5(800-812)Online publication date: 1-Sep-2019
https://doi.org/10.1109/TSC.2016.2631519
Brandt SForster KWattenhofer R(2016)On consistent migration of flows in SDNsIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications10.1109/INFOCOM.2016.7524332(1-9)Online publication date: Apr-2016
https://doi.org/10.1109/INFOCOM.2016.7524332
Forster KMahajan RWattenhofer R(2016)Consistent updates in software defined networks: On dependencies, loop freedom, and blackholes2016 IFIP Networking Conference (IFIP Networking) and Workshops10.1109/IFIPNetworking.2016.7497232(1-9)Online publication date: May-2016
https://doi.org/10.1109/IFIPNetworking.2016.7497232
Show More Cited By

Index Terms

Augmenting anycast network flows
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
2. Networks
  1. Network services
    1. Network management

Recommendations

Single-source k-splittable min-cost flows

Motivated by a famous open question on the single-source unsplittable minimum cost flow problem, we present a new approximation result for the relaxation of the problem where, for a given number k, each commodity must be routed along at most k paths.
Unsplittable anycast flow problem: formulation and algorithms
ICCS'06: Proceedings of the 6th international conference on Computational Science - Volume Part I

Our discussion in this article centers on a new optimization problem called unsplittable anycast flow problem (UAFP). We are given a directed network with arc capacities and a set of anycast requests. Anycast is a one-to-one-of-many delivery technique ...
Degree-constrained network flows
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

A d-furcated flow is a network flow whose support graph has maximum out degree d. Take a single-sink multi-commodity flow problem on any network and with any set of routing demands. Then we show that the existence of feasible fractional flow with node ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDCN '16: Proceedings of the 17th International Conference on Distributed Computing and Networking

January 2016

370 pages

ISBN:9781450340328

DOI:10.1145/2833312

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 January 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Microsoft Research

Conference

ICDCN '16

ICDCN '16: 17th International Conference on Distributed Computing and Networking

January 4 - 7, 2016

Singapore, Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
70
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zheng JXu HChen GDai HWu J(2019)Congestion-Minimizing Network Update in Data CentersIEEE Transactions on Services Computing10.1109/TSC.2016.263151912:5(800-812)Online publication date: 1-Sep-2019
https://doi.org/10.1109/TSC.2016.2631519
Brandt SForster KWattenhofer R(2016)On consistent migration of flows in SDNsIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications10.1109/INFOCOM.2016.7524332(1-9)Online publication date: Apr-2016
https://doi.org/10.1109/INFOCOM.2016.7524332
Forster KMahajan RWattenhofer R(2016)Consistent updates in software defined networks: On dependencies, loop freedom, and blackholes2016 IFIP Networking Conference (IFIP Networking) and Workshops10.1109/IFIPNetworking.2016.7497232(1-9)Online publication date: May-2016
https://doi.org/10.1109/IFIPNetworking.2016.7497232
Forster KWattenhofer R(2016)The Power of Two in Consistent Network Updates: Hard Loop Freedom, Easy Flow Migration2016 25th International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2016.7568583(1-9)Online publication date: Aug-2016
https://doi.org/10.1109/ICCCN.2016.7568583

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents