{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T08:02:43Z","timestamp":1764403363130,"version":"3.44.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"CoNEXT2","license":[{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62072047"],"award-info":[{"award-number":["62072047"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006374","name":"Beijing Nova Program","doi-asserted-by":"publisher","award":["2023140"],"award-info":[{"award-number":["2023140"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62172054"],"award-info":[{"award-number":["62172054"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Netw."],"published-print":{"date-parts":[[2024,6,13]]},"abstract":"<jats:p>Overlay network is an effective way for constructing end-to-end high-quality network services. Service Overlay Network (SON) leverages existing data transmission infrastructure to offer overlay network as network services, which provides flexibility and controllability for deploying value-added services. In this paper, we study the overlay topology design problem of SON deployment, that is, purchasing bandwidth with certain Quality of Service (QoS) guarantees in the underlay network, and building a logical overlay network that adapts to communication requirements with guaranteed reliability. The challenge lies in the difficulty of designing an overlay network with adaptability for dynamic of traffic requirement and uncertainty of underlay network failures. Traditional methods lack the underlay network view and rarely consider network failure scenarios, making it difficult to achieve global optimization. We mathematically formulate the minimum-cost overlay network design problem with network reliability constraints. Then, we propose a novel method, ROND, that samples critical traffic matrices to capture the dynamic of traffic patterns and generates failure scenarios to characterize the volatility of underlay network for avoiding significant network reconfiguration. On this basis, we simplify overlay network design problem and solve it iteratively, thereby minimizing the transmission cost as much as possible while ensuring the network performance. Extensive experimental results demonstrate that ROND is cost-effective and performance-guaranteed.<\/jats:p>","DOI":"10.1145\/3656298","type":"journal-article","created":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T09:54:11Z","timestamp":1718272451000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["ROND: Rethinking Overlay Network Design with Underlay Network Awareness"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0135-8915","authenticated-orcid":false,"given":"Yuchao","family":"Zhang","sequence":"first","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3711-0815","authenticated-orcid":false,"given":"Huahai","family":"Zhang","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0563-745X","authenticated-orcid":false,"given":"Peizhuang","family":"Cong","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6418-8087","authenticated-orcid":false,"given":"Wendong","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing University of Posts and Telecommunications, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2024,6,13]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2022. Huawei SD-WAN solution. https:\/\/support.huawei.com\/enterprise\/zh\/doc\/EDOC1100212003"},{"key":"e_1_2_1_2_1","unstructured":"2023. GUROBI. https:\/\/www.gurobi.com\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452296.3472918"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359664"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502048"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777437"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.32"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341302.3342069"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2015.55"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2260867"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935783"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.820436"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2014"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2006.139"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2987443.2987483"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934872.2934891"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j"},{"key":"e_1_2_1_18_1","volume-title":"Improving the Reliability of Internet Paths with One-hop Source Routing. In 6th Symposium on Operating System Design and Implementation (OSDI 2004","author":"Gummadi P. Krishna","year":"2004","unstructured":"P. Krishna Gummadi, Harsha V. Madhyastha, Steven D. Gribble, Henry M. Levy, and David Wetherall. 2004. Improving the Reliability of Internet Paths with One-hop Source Routing. In 6th Symposium on Operating System Design and Implementation (OSDI 2004), San Francisco, California, USA, December 6--8, 2004, Eric A. Brewer and Peter Chen (Eds.). USENIX Association, 183--198. http:\/\/www.usenix.org\/events\/osdi04\/tech\/gummadi.html"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386367.3431318"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3565287.3610274"},{"key":"e_1_2_1_21_1","volume-title":"Skyplane: Optimizing Transfer Cost and Throughput Using Cloud-Aware Overlays. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)","author":"Jain Paras","year":"2023","unstructured":"Paras Jain, Sam Kumar, SarahWooders, Shishir G. Patil, Joseph E. Gonzalez, and Ion Stoica. 2023. Skyplane: Optimizing Transfer Cost and Throughput Using Cloud-Aware Overlays. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). USENIX Association, Boston, MA, 1375--1389."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--72606--7_61"},{"key":"e_1_2_1_23_1","volume-title":"Snoeren","author":"Kompella Ramana Rao","year":"2005","unstructured":"Ramana Rao Kompella, Jennifer Yates, Albert G. Greenberg, and Alex C. Snoeren. 2005. IP Fault Localization Via Risk Modeling. In 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005), May 2--4, 2005, Boston, Massachusetts, USA, Proceedings, Amin Vahdat and David Wetherall (Eds.). USENIX. http:\/\/www.usenix.org\/events\/ nsdi05\/tech\/kompella.html"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1165389.945473"},{"key":"e_1_2_1_25_1","volume-title":"19th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2022","author":"Krishnaswamy Umesh","year":"2022","unstructured":"Umesh Krishnaswamy, Rachee Singh, Nikolaj S. Bj\u00f8rner, and Himanshu Raj. 2022. Decentralized cloud wide-area network traffic engineering with BLASTSHIELD. In 19th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2022, Renton, WA, USA, April 4--6, 2022, Amar Phanishayee and Vyas Sekar (Eds.). USENIX Association, 325--338. https:\/\/www.usenix.org\/conference\/nsdi22\/presentation\/krishnaswamy"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824795.1824800"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354513"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1453698.1453699"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2310735"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1842733.1842736"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5061998"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 3rd International Network Optimization Conference (INOC 2007","author":"Orlowski S.","year":"2009","unstructured":"S. Orlowski, M. Pi\u00f3ro, A. Tomaszewski, and R. Wess\u00e4ly. 2007. SNDlib 1.0--Survivable Network Design Library. In Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium. https:\/\/opus4.kobv. de\/opus4-zib\/frontdoor\/deliver\/index\/docId\/958\/file\/ZR-07--15.pdf http:\/\/sndlib.zib.de, extended version accepted in Networks, 2009.."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20371"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1618562.1618584"},{"key":"e_1_2_1_35_1","volume-title":"19th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2022","author":"Sharma Harsha","year":"2022","unstructured":"Harsha Sharma, Parth Thakkar, Sagar Bharadwaj, Ranjita Bhagwan, Venkata N. Padmanabhan, Yogesh Bansal, P. Vijay Kumar, and Kathleen Voelbel. 2022. Optimizing Network Provisioning through Cooperation. In 19th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2022, Renton, WA, USA, April 4--6, 2022, Amar Phanishayee and Vyas Sekar (Eds.). USENIX Association, 1179--1194. https:\/\/www.usenix.org\/conference\/nsdi22\/presentation\/sharma"},{"key":"e_1_2_1_36_1","volume-title":"Cost-effective Cloud Edge Traffic Engineering with Cascara. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)","author":"Singh Rachee","year":"2021","unstructured":"Rachee Singh, Sharad Agarwal, Matt Calder, and Paramvir Bahl. 2021. Cost-effective Cloud Edge Traffic Engineering with Cascara. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21). USENIX Association, 201--216. https:\/\/www.usenix.org\/conference\/nsdi21\/presentation\/singh"},{"key":"e_1_2_1_37_1","volume-title":"Overlay Networks: An Akamai Perspective.","author":"Sitaraman Ramesh K.","year":"2014","unstructured":"Ramesh K. Sitaraman, Mangesh Kasbekar, Woody Lichtenstein, and Manish Jain. 2014. Overlay Networks: An Akamai Perspective."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2022.3155475"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111322.1111341"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOMW.2019.8845208"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.93"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354512"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM41043.2020.9155503"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications. 1--12","author":"Zhang H.","year":"2006","unstructured":"H. Zhang, J. Kurose, and D. Towsley. 2006. Can an Overlay Compensate for a Careless Underlay?. In Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications. 1--12. https:\/\/doi.org\/10.1109\/ INFOCOM.2006.323"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485983.3494843"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2021.3054924"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQoS57198.2023.10188706"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS51040.2020.00100"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452296.3472902"},{"key":"e_1_2_1_50_1","volume-title":"16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)","author":"Zhuo Danyang","year":"2019","unstructured":"Danyang Zhuo, Kaiyuan Zhang, Yibo Zhu, Hongqiang Harry Liu, Matthew Rockett, Arvind Krishnamurthy, and Thomas Anderson. 2019. Slim: OS Kernel Support for a Low-Overhead Container Overlay Network. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). Boston, MA, 331--344."}],"container-title":["Proceedings of the ACM on Networking"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656298","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656298","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T20:13:11Z","timestamp":1755979991000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656298"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,13]]},"references-count":50,"journal-issue":{"issue":"CoNEXT2","published-print":{"date-parts":[[2024,6,13]]}},"alternative-id":["10.1145\/3656298"],"URL":"https:\/\/doi.org\/10.1145\/3656298","relation":{},"ISSN":["2834-5509"],"issn-type":[{"type":"electronic","value":"2834-5509"}],"subject":[],"published":{"date-parts":[[2024,6,13]]},"assertion":[{"value":"2024-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}