{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:30:51Z","timestamp":1758270651649,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,4,27]],"date-time":"2018-04-27T00:00:00Z","timestamp":1524787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2018,4,27]]},"abstract":"<jats:p>Modern computer networks support interesting new routing models in which traffic flows from a source sto a destination t can be flexibly steered through a sequence of waypoints, such as (hardware) middleboxes or (virtualized) network functions (VNFs), to create innovative network services like service chains or segment routing. While the benefits and technological challenges of providing such routing models have been articulated and studied intensively over the last years, less is known about the underlying algorithmic traffic routing problems.<\/jats:p>\n          <jats:p>The goal of this paper is to provide the network community with an overview of algorithmic techniques for waypoint routing and also inform about limitations due to computational hardness. In particular, we put the waypoint routing problem into perspective with respect to classic graph theoretical problems. For example, we find that while computing a shortest path from a source s to a destination t is simple (e.g., using Dijkstra's algorithm), the problem of finding a shortest route from s to t via a single waypoint already features a deep combinatorial structure.<\/jats:p>","DOI":"10.1145\/3211852.3211859","type":"journal-article","created":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T11:58:18Z","timestamp":1525089498000},"page":"42-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Charting the Algorithmic Complexity of Waypoint Routing"],"prefix":"10.1145","volume":"48","author":[{"given":"Saeed Akhoondian","family":"Amiri","sequence":"first","affiliation":[{"name":"MPI Saarland, Germany"}]},{"given":"Klaus-Tycho","family":"Foerster","sequence":"additional","affiliation":[{"name":"Aalborg University, Denmark"}]},{"given":"Riko","family":"Jacob","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Denmark"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2018,4,27]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_4"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993854"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095255"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_18"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.29"},{"key":"e_1_2_1_6_2","volume-title":"oct","author":"White Paper SI.","year":"2013","unstructured":"ET SI. Network functions virtualisation \u2013 introductory white paper. White Paper , oct 2013 . ETSI. Network functions virtualisation \u2013 introductory white paper. White Paper, oct 2013."},{"key":"e_1_2_1_7_2","volume-title":"Proc. SSS","author":"Even G.","year":"2016","unstructured":"G. Even , M. Medina , and B. Patt-Shamir . Online path computation and function placement in sdns . In Proc. SSS , 2016 . G. Even, M. Medina, and B. Patt-Shamir. Online path computation and function placement in sdns. In Proc. SSS, 2016."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48314-6_24"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2015.7417124"},{"key":"e_1_2_1_10_2","volume-title":"Proc. ALGOCLOUD","author":"Foerster K.-T.","year":"2017","unstructured":"K.-T. Foerster , M. Parham , and S. Schmid . A walk in the clouds: Routing through vnfs on bidirected networks . In Proc. ALGOCLOUD , 2017 . K.-T. Foerster, M. Parham, and S. Schmid. A walk in the clouds: Routing through vnfs on bidirected networks. In Proc. ALGOCLOUD, 2017."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2785956.2787495"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120306"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2342356.2342359"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.07.004"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.09.015"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/2190621"},{"key":"e_1_2_1_18_2","volume-title":"Proc. USENIX ATC","author":"Levin D.","year":"2014","unstructured":"D. Levin , M. Canini , S. Schmid , F. Schaffert , and A. Feldmann . Panopticon: Reaping the benefits of incremental SDN deployment in enterprise networks . In Proc. USENIX ATC , 2014 . D. Levin, M. Canini, S. Schmid, F. Schaffert, and A. Feldmann. Panopticon: Reaping the benefits of incremental SDN deployment in enterprise networks. In Proc. USENIX ATC, 2014."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90024-7"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2875951.2875956"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25258-2_8"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.12.003"},{"key":"e_1_2_1_23_2","first-page":"283","volume-title":"Research Trends in Combinatorial Optimization","author":"Naves G.","unstructured":"G. Naves and A. Seb\u00f6 . Multiflow feasibility: An annotated tableau . In W. J. Cook, L. Lov\u00e1sz, and J. Vygen, editors, Research Trends in Combinatorial Optimization , pages 261\u2013 283 . Springer, 2008. G. Naves and A. Seb\u00f6. Multiflow feasibility: An annotated tableau. In W. J. Cook, L. Lov\u00e1sz, and J. Vygen, editors, Research Trends in Combinatorial Optimization, pages 261\u2013283. Springer, 2008."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674989"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_26_2","volume-title":"Service chain and virtual network embeddings: Approximations using randomized rounding. arXiv preprint","author":"Rost M.","year":"2016","unstructured":"M. Rost and S. Schmid . Service chain and virtual network embeddings: Approximations using randomized rounding. arXiv preprint , 2016 . M. Rost and S. Schmid. Service chain and virtual network embeddings: Approximations using randomized rounding. arXiv preprint, 2016."},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90158-2"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040204"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140209"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)E0177-Z"}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3211852.3211859","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3211852.3211859","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:17Z","timestamp":1750287257000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3211852.3211859"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,27]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,4,27]]}},"alternative-id":["10.1145\/3211852.3211859"],"URL":"https:\/\/doi.org\/10.1145\/3211852.3211859","relation":{},"ISSN":["0146-4833"],"issn-type":[{"type":"print","value":"0146-4833"}],"subject":[],"published":{"date-parts":[[2018,4,27]]},"assertion":[{"value":"2018-04-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}