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

research-article

Open access

Capacity-efficient and uncertainty-resilient backbone network planning with hose

Authors:

Satyajeet Singh Ahuja,

Vinayak Dangui,

Abishek Gopalan,

Ying ZhangAuthors Info & Claims

SIGCOMM '21: Proceedings of the 2021 ACM SIGCOMM 2021 Conference

Pages 547 - 559

https://doi.org/10.1145/3452296.3472918

Published: 09 August 2021 Publication History

Abstract

This paper presents Facebook's design and operational experience of a Hose-based backbone network planning system. This initial adoption of the Hose model in network planning is driven by the capacity and demand uncertainty pressure of backbone expansion. Since the Hose model abstracts the aggregated traffic demand per site, peak traffic flows at different times can be multiplexed to save capacity and buffer traffic spikes. Our core design involves heuristic algorithms to select Hose-compliant traffic matrices and cross-layer optimization between the optical and IP networks. We evaluate the system performance in production and share insights from years of production experience. Hose-based network planning can save 17.4% capacity and drops 75% less traffic under fiber cuts. As the first study of Hose in network planning, our work has the potential to inspire follow-up research.

Supplementary Material

ganjali-public-review (379-public-review.pdf)

Capacity-Efficient and Uncertainty-Resilient Backbone Network Planning with Hose: Public Review

Download
68.34 KB

MP4 File (video-presentation.mp4)

Conference Presentation Video

Download
235.05 MB

References

[1]

[n. d.]. FICO Xpress Optimization. ([n. d.]). https://www.fico.com/en/products/fico-xpress-optimization

[2]

[n. d.]. TAO: The power of the graph. ([n. d.]). https://engineering.fb.com/2013/06/25/core-data/tao-the-power-of-the-graph/

[3]

R. Andersen, F. Chung, A. Sen, and G. Xue. 2004. On Disjoint Path Pairs with Wavelength Continuity Constraint in WDM Networks. IEEE INFOCOM (2004).

[4]

Hitesh Ballani, Paolo Costa, Thomas Karagiannis, and Ant Rowstron. 2011. Towards Predictable Datacenter Networks. In Proceedings of the ACM SIGCOMM 2011 Conference. Association for Computing Machinery, New York, NY, USA, 12.

Digital Library

[5]

Ajay Kumar Bangla, Alireza Ghaffarkhah, Ben Preskill, Bikash Koley, Christoph Albrecht, Emilie Danna, Joe Jiang, and Xiaoxue Zhao. 2015. Capacity Planning for the Google Backbone Network. In ISMP 2015 (International Symposium on Mathematical Programming).

[6]

C Bradford Barber, David P Dobkin, and Hannu Huhdanpaa. 1996. The Quickhull Algorithm for Convex Hulls. ACM Transactions on Mathematical Software (TOMS) 22, 4 (1996), 469--483.

Digital Library

[7]

Haesun Byun and Meejeong Lee. 2007. Extensions to P2MP RSVP-TE for VPN-specific State Provisioning with Fair Resource Sharing. Comput. Commun. 30, 18 (Dec. 2007), 3736--3745. 0140-3664

[8]

Mosharaf Chowdhury, Yuan Zhong, and Ion Stoica. 2014. Efficient Coflow Scheduling with Varys. 44, 4 (2014).

[9]

N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, and J. E. V. der Merwe. 1999. A Flexible Model for Resource Management in Virtual Private Networks. ACM Sigcomm, San Diego, California, USA (1999).

[10]

Friedrich Eisenbrand and Edda Happ. 2006. Provisioning a Virtual Private Network Under the Presence of Non-communicating Groups. In Proceedings of the 6th Italian Conference on Algorithms and Complexity (CIAC'06). 105--114.

Digital Library

[11]

Shimon Even, Alon Itai, and Adi Shamir. 1975. On The Complexity of Time Table and Multi-commodity Flow Problems. In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975). IEEE, 184--193.

[12]

Uriel Feige. 1998. A Threshold of ln n for Approximating Set Cover. Journal of the ACM (JACM) 45, 4 (1998), 634--652.

Digital Library

[13]

J. A. Fingerhut, S. Suri, and J. S. Turner. 1997. Designing Least-cost Nonblocking Broadband Networks. Journal of Algorithms 24, 2 (Aug. 1997), 287--309.

Digital Library

[14]

Albert Greenberg, James R. Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A. Maltz, Parveen Patel, and Sudipta Sengupta. 2009. VL2: A Scalable and Flexible Data Center Network. In Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication. Association for Computing Machinery, New York, NY, USA, 12.

Digital Library

[15]

Anupam Gupta, Jon Kleinberg, Amit Kumar, Rajeev Rastogi, and Bulent Yener. 2001. Provisioning a Virtual Private Network: A Network Design Problem for Multicommodity Flow. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing (STOC '01). 389--398.

Digital Library

[16]

M Rashidul Islam and M Hanif Chaudhry. 1998. Modeling of Constituent Transport in Unsteady Flows in Pipe Networks. Journal of Hydraulic Engineering 124, 11 (1998), 1115--1124.

[17]

Simon Kassing, Asaf Valadarsky, Gal Shahaf, Michael Schapira, and Ankit Singla. 2017. Beyond Fat-Trees without Antennae, Mirrors, and Disco-Balls. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication. Association for Computing Machinery, New York, NY, USA.

Digital Library

[18]

Lucian Popa, Gautam Kumar, Mosharaf Chowdhury, Arvind Krishnamurthy, Sylvia Ratnasamy, and Ion Stoica. 2012. FairCloud: Sharing the Network in Cloud Computing. SIGCOMM Comput. Commun. Rev. 42, 4 (Aug. 2012).

Digital Library

[19]

Henrique Rodrigues, Jose Renato Santos, Yoshio Turner, Paolo Soares, and Dorgival Guedes. 2011. Gatekeeper: Supporting Bandwidth Guarantees for Multi-Tenant Datacenter Networks. In Proceedings of the 3rd Conference on I/O Virtualization. USENIX Association, USA.

[20]

Thomas Rothvoß and Laura Sanità. 2009. On the Complexity of the Asymmetric VPN Problem. In Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX '09 / RANDOM '09). Springer-Verlag, Berlin, Heidelberg, 326--338.

Digital Library

[21]

Daniel Semrau and Polina Bayvel. 2018. The Gaussian Noise Model in the Presence of Inter-channel Stimulated Raman Scattering. Journal of Lightwave Technology 36, 14 (2018), 3046--3055.

[22]

Kaushik Veeraraghavan, Justin Meza, Scott Michelson, Sankaralingam Panneerselvam, Alex Gyori, David Chou, Sonia Margulis, Daniel Obenshain, Shruti Padmanabha, Ashish Shah, Yee Jiun Song, and Tianyin Xu. 2018. Maelstrom: Mitigating Datacenter-level Disasters by Draining Interdependent Traffic Safely and Efficiently. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). USENIX Association, Carlsbad, CA, 373--389.

[23]

Shu Zhang and Ulrich Killat. 2011. Multiple-layer Network Planning with Scenario-based Traffic Forecast. In Proceedings of the 17th International Conference on Energy-aware Communications. 77--88.

Digital Library

[24]

Y. Zhang and Z. Ge. 2005. Finding Critical Traffic Matrices. In 2005 International Conference on Dependable Systems and Networks (DSN'05). 188--197.

Cited By

Petale SKnapińska AErbayat ELechowicz PWalkowiak KLin SMatsuura MHasegawa HSubramaniam S(2024)PRODIGY+: a robust progressive upgrade approach for elastic optical networksJournal of Optical Communications and Networking10.1364/JOCN.52539216:9(E48)Online publication date: 15-Aug-2024
https://doi.org/10.1364/JOCN.525392
Kataria BLNU PBothra RGandhi RBhattacherjee DPadmanabhan VAtov IRamakrishnan SChaturmohta SKotipalli CLiang RSueda KHe XHinton K(2024)Saving Private WAN: Using Internet Paths to Offload WAN Traffic in Conferencing ServicesProceedings of the ACM on Networking10.1145/36964042:CoNEXT4(1-22)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1145/3696404
Zhang YZhang HCong PWang W(2024)ROND: Rethinking Overlay Network Design with Underlay Network AwarenessProceedings of the ACM on Networking10.1145/36562982:CoNEXT2(1-22)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3656298
Show More Cited By

Index Terms

Capacity-efficient and uncertainty-resilient backbone network planning with hose
1. Networks
  1. Network performance evaluation
    1. Network experimentation
  2. Network services
    1. Network management

Recommendations

Capacity planning in IP Virtual Private Networks under mixed traffic
Selected papers from the 3rd international workshop on QoS in multiservice IP networks (QoS-IP 2005)

A new mechanism for capacity planning of a Virtual Private Network, carrying both Quality of Service (QoS) and Best-Effort (BE) IP traffic is introduced. The link bandwidth allocation in the network is based on a hybrid combination of analytical and ...
Hose-based cross-layer backbone network design with Benders decomposition
ACM SIGCOMM '23: Proceedings of the ACM SIGCOMM 2023 Conference

Network design is the process of dimensioning IP capacity over an optical network infrastructure to satisfy a given set of demands and reliability constraints. Specifically, we consider the problem of hose-based cross-layer network design, which seeks to ...
FlexWAN: Software Hardware Co-design for Cost-Effective and Resilient Optical Backbones
ACM SIGCOMM '23: Proceedings of the ACM SIGCOMM 2023 Conference

The rising demand for WAN capacity driven by the rapid growth of inter-data center traffic poses new challenges for costly optical networks. Today cloud providers rely on fixed optical backbones, where all hardware devices operate on a rigid spectrum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '21: Proceedings of the 2021 ACM SIGCOMM 2021 Conference

August 2021

868 pages

ISBN:9781450383837

DOI:10.1145/3452296

General Chairs:
Fernando Kuipers
Delft University of Technology
,
Matthew Caesar
University of Illinois at Urbana-Champaign

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 August 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGCOMM '21

Sponsor:

SIGCOMM

SIGCOMM '21: ACM SIGCOMM 2021 Conference

August 23 - 27, 2021

Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
1,704
Total Downloads

Downloads (Last 12 months)280
Downloads (Last 6 weeks)59

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Petale SKnapińska AErbayat ELechowicz PWalkowiak KLin SMatsuura MHasegawa HSubramaniam S(2024)PRODIGY+: a robust progressive upgrade approach for elastic optical networksJournal of Optical Communications and Networking10.1364/JOCN.52539216:9(E48)Online publication date: 15-Aug-2024
https://doi.org/10.1364/JOCN.525392
Kataria BLNU PBothra RGandhi RBhattacherjee DPadmanabhan VAtov IRamakrishnan SChaturmohta SKotipalli CLiang RSueda KHe XHinton K(2024)Saving Private WAN: Using Internet Paths to Offload WAN Traffic in Conferencing ServicesProceedings of the ACM on Networking10.1145/36964042:CoNEXT4(1-22)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1145/3696404
Zhang YZhang HCong PWang W(2024)ROND: Rethinking Overlay Network Design with Underlay Network AwarenessProceedings of the ACM on Networking10.1145/36562982:CoNEXT2(1-22)Online publication date: 13-Jun-2024
https://dl.acm.org/doi/10.1145/3656298
Liu XZhao SCui YWang XSekar VYu MSeneviratne AVeitch D(2024)FIGRET: Fine-Grained Robustness-Enhanced Traffic EngineeringProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672258(117-135)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672258
Zhao PYou JYuan X(2024)Circling Reduction Algorithm for Cloud Edge Traffic Allocation Under the 95th Percentile BillingIEEE/ACM Transactions on Networking10.1109/TNET.2024.341564932:5(4254-4269)Online publication date: Oct-2024
https://doi.org/10.1109/TNET.2024.3415649
Liu CAggarwal VLan TGeng NYang YXu MLi Q(2024)FERN: Leveraging Graph Attention Networks for Failure Evaluation and Robust Network DesignIEEE/ACM Transactions on Networking10.1109/TNET.2023.331167832:2(1003-1018)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3311678
Higashimori KTanaka TInuzuka FOhara TInoue T(2023)Key physical topology features for optical backbone networks via a multilayer correlation analysisJournal of Optical Communications and Networking10.1364/JOCN.47986615:5(B23)Online publication date: 14-Apr-2023
https://doi.org/10.1364/JOCN.479866
Liu CAggarwal VLan TGeng NYang YXu M(2023)Machine Learning for Robust Network Design: A New PerspectiveIEEE Communications Magazine10.1109/MCOM.002.220067061:10(86-92)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1109/MCOM.002.2200670
Ma HHuang XRuan KZhu Y(2023)SW-Informer: A Seasonal-Trend Decomposition and Wavelet Fusion Informer Approach for IP Network Traffic Prediction2023 IEEE 11th International Conference on Information, Communication and Networks (ICICN)10.1109/ICICN59530.2023.10392594(278-282)Online publication date: 17-Aug-2023
https://doi.org/10.1109/ICICN59530.2023.10392594
Petale SLin SMatsuura MHasegawa HSubramaniam S(2023)PRODIGY: A Progressive Upgrade Approach for Elastic Optical NetworksGLOBECOM 2023 - 2023 IEEE Global Communications Conference10.1109/GLOBECOM54140.2023.10437935(2129-2134)Online publication date: 4-Dec-2023
https://doi.org/10.1109/GLOBECOM54140.2023.10437935
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents