{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:50:41Z","timestamp":1743087041309,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030720155"},{"type":"electronic","value":"9783030720162"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:00:00Z","timestamp":1616198400000},"content-version":"vor","delay-in-days":78,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>To ensure a high availability, communication networks provide resilient routing mechanisms that quickly change routes upon failures. However, a fundamental algorithmic question underlying such mechanisms is hardly understood: how to verify whether a given network reroutes flows along<jats:italic>feasible<\/jats:italic>paths, without violating capacity constraints, for up to<jats:italic>k<\/jats:italic>link failures? We chart the algorithmic complexity landscape of resilient routing under link failures, considering shortest path routing based on link weights as e.g. deployed in the ECMP protocol. We study two models: a<jats:italic>pessimistic<\/jats:italic>model where flows interfere in a worst-case manner along equal-cost shortest paths, and an<jats:italic>optimistic<\/jats:italic>model where flows are routed in a best-case manner, and we present a complete picture of the algorithmic complexities. We further propose a strategic search algorithm that checks only the critical failure scenarios while still providing correctness guarantees. Our experimental evaluation on a benchmark of Internet and datacenter topologies confirms an improved performance of our strategic search by several orders of magnitude.<\/jats:p>","DOI":"10.1007\/978-3-030-72016-2_22","type":"book-chapter","created":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T22:03:37Z","timestamp":1616191417000},"page":"411-429","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Resilient Capacity-Aware Routing"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Schmid","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Schnepf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Srba","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,20]]},"reference":[{"key":"22_CR1","unstructured":"Carolyn\u00a0Jane Anderson, Nate Foster, Arjun Guha, Jean-Baptiste Jeannin, Dexter Kozen, Cole Schlesinger, and David Walker. Netkat: Semantic foundations for networks. Acm sigplan notices, 49(1):113\u2013126, 2014."},{"key":"22_CR2","unstructured":"Ron Banner and Ariel Orda. Multipath routing algorithms for congestion minimization. In IEEE\/ACM Transactions on Networking (TON), volume\u00a015, pages 92\u2013122, 02 2005."},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Cristina Bazgan, Andr\u00e9 Nichterlein, and Rolf Niedermeier. A refined complexity analysis of finding the most vital edges for undirected shortest paths. In Vangelis\u00a0Th. Paschos and Peter Widmayer, editors, International Conference on Algorithms and Complexity, volume 9079 of LNCS, pages 47\u201360. Springer, 2015.","DOI":"10.1007\/978-3-319-18173-8_3"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Ryan Beckett, Ratul Mahajan, Todd Millstein, Jitendra Padhye, and David Walker. Don\u2019t mind the gap: Bridging network-wide objectives and device-level configurations. In Proceedings of the 2016 ACM SIGCOMM Conference, pages 328\u2013341, 2016.","DOI":"10.1145\/2934872.2934909"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Bi, C.\u00a0W. Tan, and A.\u00a0Tang. Network utility maximization with path cardinality constraints,. In Proceedings of the 35th Annual IEEE International Conference on Computer Communications (IEEE INFOCOM 2016), 2016.","DOI":"10.1109\/INFOCOM.2016.7524408"},{"key":"22_CR6","unstructured":"Martin\u00a0Nyx Brain, James\u00a0H. Davenport, and Alberto Griggio. Benchmarking solvers, SAT-style. In Proceedings of the 2nd International Workshop on Satisfiability Checking and Symbolic Computation co-located with the 42nd International Symposium on Symbolic and Algebraic Computation (ISSAC\u201917), volume 1974 of CEUR, pages 1\u201315. CEUR-WS.org, 2017."},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Zhiruo Cao, Zheng Wang, and Ellen Zegura. Performance of hashing-based schemes for internet load balancing. In Proceedings of IEEE INFOCOM 2000., volume\u00a01, pages 332\u2013341. IEEE, 2000.","DOI":"10.1109\/INFCOM.2000.832203"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Yiyang Chang, Chuan Jiang, Ashish Chandra, Sanjay Rao, and Mohit Tawarmalani. Lancet: Better network resilience by designing for pruned. SIGMETRICS Perform. Eval. Rev., 48(1):53\u201354, July 2020.","DOI":"10.1145\/3410048.3410079"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Charles E. Leiserson. Fat-trees: Universal networks for hardware-efficient supercomputing. volume\u00a034, pages 892\u2013901, 1985.","DOI":"10.1109\/TC.1985.6312192"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"M.\u00a0Chiesa, G.\u00a0Kindler, and M.\u00a0Schapira. Traffic engineering with equal-cost-multipath: An algorithmic perspective,. In IEEE\/ACM Transactions on Networking, vol. 25, no. 2, pp. 779-792, 2017.","DOI":"10.1109\/TNET.2016.2614247"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Stephen\u00a0A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64(1):2 \u2013 22, 1985.","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Eliezer Dekel, David Nassimi, and Sartaj Sahni. Parallel matrix and graph algorithms. SIAM Journal on Computing, 10(4):657\u2013675, 1981.","DOI":"10.1137\/0210049"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Camil Demetrescu, Mikkel Thorup, Rezaul Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput., 37:1299\u20131318, 01 2008.","DOI":"10.1137\/S0097539705429847"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Jack Edmonds and Richard\u00a0M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. 19(2):248\u2013264, 1972.","DOI":"10.1145\/321694.321699"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Ahmed El-Hassany, Petar Tsankov, Laurent Vanbever, and Martin Vechev. Network-wide configuration synthesis. In International Conference on Computer Aided Verification, pages 261\u2013281. Springer, 2017.","DOI":"10.1007\/978-3-319-63390-9_14"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Bernard Fortz. Internet traffic engineering by optimizing OSPF weights. In in Proc. IEEE INFOCOM, pages 519\u2013528, 2000.","DOI":"10.1109\/INFCOM.2000.832225"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Bernard Fortz, Jennifer Rexford, and Mikkel Thorup. Traffic engineering with traditional IP routing protocols. IEEE Comm. Magazine, 40(10):118\u2013124, 2002.","DOI":"10.1109\/MCOM.2002.1039866"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Bernard Fortz and Mikkel Thorup. Optimizing OSPF\/IS-IS weights in a changing world. IEEE Journal on Selected Areas in Communications (JSAC), 20(4):756\u2013767, 2002.","DOI":"10.1109\/JSAC.2002.1003042"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Bernard Fortz and Mikkel Thorup. Increasing internet capacity using local search. Computational Optimization and Applications, 29(1):13\u201348, 2004.","DOI":"10.1023\/B:COAP.0000039487.35027.02"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Nate Foster, Dexter Kozen, Konstantinos Mamouras, Mark Reitblatt, and Alexandra Silva. Probabilistic NetKAT. In Peter Thiemann, editor, Programming Languages and Systems (ESOP\u201916), volume 9632 of LNCS, pages 282\u2013309. Springer, 2016.","DOI":"10.1007\/978-3-662-49498-1_12"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Pierre Francois, Clarence Filsfils, John Evans, and Olivier Bonaventure. Achieving sub-second igp convergence in large IP networks. ACM SIGCOMM Computer Communication Review, 35(3):35\u201344, 2005.","DOI":"10.1145\/1070873.1070877"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Albert Greenberg, James\u00a0R Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David\u00a0A Maltz, Parveen Patel, and Sudipta Sengupta. Vl2: a scalable and flexible data center network. In Proceedings of the ACM SIGCOMM 2009 conference on Data communication, pages 51\u201362, 2009.","DOI":"10.1145\/1594977.1592576"},{"key":"22_CR23","unstructured":"Chuanxiong Guo, Guohan Lu, Dan Li, Haitao Wu, Xuan Zhang, Yunfeng Shi, Chen Tian, Yongguang Zhang, Songwu Lu, and Guohan Lv. Bcube: A high performance, server-centric network architecture for modular data centers. In ACM SIGCOMM. Association for Computing Machinery, Inc., August 2009."},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Christian Hopps et\u00a0al. Analysis of an equal-cost multi-path algorithm. Technical report, RFC 2992, November, 2000.","DOI":"10.17487\/rfc2992"},{"key":"22_CR25","unstructured":"Jesper\u00a0Stenbjerg Jensen, Troels\u00a0Beck Kr\u00f8gh, Jonas\u00a0Sand Madsen, Stefan Schmid, Ji\u0159\u00ed Srba, and Marc\u00a0Tom Thorgersen. P-Rex: Fast verification of MPLS networks with multiple link failures. In Proc. 14th International Conference on emerging Networking EXperiments and Technologies (CoNEXT), pages 217\u2013227, 2018."},{"key":"22_CR26","doi-asserted-by":"crossref","unstructured":"P.G. Jensen, D.\u00a0Kristiansen, S.\u00a0Schmid, M.K. Schou, B.C. Schrenk, and J.\u00a0Srba. Aalwines: A fast and quantitative what-if analysis tool for mpls networks. In Proceedings of the 16th International Conference on Emerging Networking EXperiments and Technologies (CoNEXT\u201920), pages 474\u2013481. ACM, 2020.","DOI":"10.1145\/3386367.3431308"},{"key":"22_CR27","doi-asserted-by":"crossref","unstructured":"Donald\u00a0B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of ACM, 24(1):1\u201313, 1977.","DOI":"10.1145\/321992.321993"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Simon Knight, Hung Nguyen, Nickolas Falkner, Rhys Bowden, and Matthew Roughan. The internet topology Zoo. Selected Areas in Communications, IEEE Journal on, 29:1765 \u2013 1775, 11 2011.","DOI":"10.1109\/JSAC.2011.111002"},{"key":"22_CR29","unstructured":"Kim\u00a0G. Larsen, Stefan Schmid, and Bingtian Xue. WNetKAT: A weighted SDN programming and verification language. In Proc. 20th International Conference on Principles of Distributed Systems (OPODIS), 2016."},{"key":"22_CR30","doi-asserted-by":"crossref","unstructured":"John Moy et\u00a0al. OSPF version 2. 1998.","DOI":"10.17487\/rfc2328"},{"key":"22_CR31","doi-asserted-by":"crossref","unstructured":"Sebastian Orlowski and Michal Pioro. Complexity of column generation in network design with path-based survivability mechanism. Networks, 59:132 \u2013 147, 01 2012.","DOI":"10.1002\/net.20484"},{"key":"22_CR32","unstructured":"Aurojit Panda, Ori Lahav, Katerina Argyraki, Mooly Sagiv, and Scott Shenker. Verifying reachability in networks with mutable datapaths. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201917), pages 699\u2013718, 2017."},{"key":"22_CR33","unstructured":"Christos\u00a0M. Papadimitriou. Computational complexity. Addison-Wesley, Reading, Massachusetts, 1994."},{"key":"22_CR34","doi-asserted-by":"crossref","unstructured":"J.\u00a0S. Provan and D.\u00a0R. Shier. A paradigm for listing (s, t)-cuts in graphs. Algorithmica, 15(4):351\u2013372, apr 1996.","DOI":"10.1007\/BF01961544"},{"key":"22_CR35","doi-asserted-by":"crossref","unstructured":"V.\u00a0Ramachandran. The complexity of minimum cut and maximum flow problems in an acyclic network. 17(4):387\u2013392, 1987.","DOI":"10.1002\/net.3230170403"},{"key":"22_CR36","unstructured":"Baruch Schieber, Amotz Bar-Noy, and Samir Khuller. The complexity of finding most vital arcs and nodes. Technical report, USA, 1995."},{"key":"22_CR37","doi-asserted-by":"publisher","unstructured":"S.\u00a0Schmid, N.\u00a0Schnepf, and J.\u00a0Srba. Reproducibility Package for TACAS\u201921 Paper Resilient Capacity-Aware Routing, January 2021. https:\/\/doi.org\/10.5281\/zenodo.4421365.","DOI":"10.5281\/zenodo.4421365"},{"key":"22_CR38","doi-asserted-by":"crossref","unstructured":"S.\u00a0Schmid and J.\u00a0Srba. Polynomial-time what-if analysis for prefix-manipulating MPLS networks. In Proc. IEEE INFOCOM, pages 1799\u20131807. IEEE, 2018.","DOI":"10.1109\/INFOCOM.2018.8486261"},{"key":"22_CR39","unstructured":"Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., USA, 1986."},{"key":"22_CR40","doi-asserted-by":"crossref","unstructured":"A.\u00a0Valadarsky, G.\u00a0Shahaf, M.\u00a0Dinitz, and M.\u00a0Schapira. Xpander: Towards optimal-performance datacenters. In CoNEXT, pages 205\u2013219. ACM, 2016.","DOI":"10.1145\/2999572.2999580"},{"key":"22_CR41","doi-asserted-by":"crossref","unstructured":"Yaron Velner, Kalev Alpernas, Aurojit Panda, Alexander Rabinovich, Mooly Sagiv, Scott Shenker, and Sharon Shoham. Some complexity results for stateful network verification. In Proc. of TACAS\u201916, pages 811\u2013830. Springer, 2016.","DOI":"10.1007\/978-3-662-49674-9_51"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-72016-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T11:51:47Z","timestamp":1724673107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-72016-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030720155","9783030720162"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-72016-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 March 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/tacas","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"141","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference changed to an online format due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}