{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:05Z","timestamp":1750225685960,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,17]],"date-time":"2023-06-17T00:00:00Z","timestamp":1686960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","award":["10.47379\/ICT19045"],"award-info":[{"award-number":["10.47379\/ICT19045"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,17]]},"DOI":"10.1145\/3558481.3591080","type":"proceedings-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T22:22:03Z","timestamp":1685571723000},"page":"153-163","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A Tight Characterization of Fast Failover Routing: Resiliency to Two Link Failures is Possible"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2153-4250","authenticated-orcid":false,"given":"Wenkai","family":"Dai","sequence":"first","affiliation":[{"name":"University of Vienna, Vienna, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4635-4480","authenticated-orcid":false,"given":"Klaus-Tycho","family":"Foerster","sequence":"additional","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7798-1711","authenticated-orcid":false,"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"TU Berlin and University of Vienna, Berlin and Vienna, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,6,17]]},"reference":[{"key":"e_1_3_2_3_1_1","doi-asserted-by":"crossref","unstructured":"Mohammad Alizadeh Albert G. Greenberg David A. Maltz Jitendra Padhye Parveen Patel Balaji Prabhakar Sudipta Sengupta and Murari Sridharan. 2010. Data center TCP (DCTCP). In SIGCOMM. ACM.","DOI":"10.1145\/1851182.1851192"},{"key":"e_1_3_2_3_2_1","unstructured":"Anand Bhalgat Ramesh Hariharan Telikepalli Kavitha and Debmalya Panigrahi. 2008. Fast edge splitting and Edmonds' arborescence construction for unweighted graphs. In SODA."},{"key":"e_1_3_2_3_3_1","doi-asserted-by":"crossref","unstructured":"Prosenjit Bose Pat Morin Ivan Stojmenovic and Jorge Urrutia. 1999. Routing with guaranteed delivery in ad hoc wireless networks. In DIAL-M. ACM 48--55.","DOI":"10.1145\/313239.313282"},{"key":"e_1_3_2_3_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.08.026"},{"key":"e_1_3_2_3_5_1","unstructured":"Marco Chiesa Andrei V. Gurtov Aleksander Madry Slobodan Mitrovic Ilya Nikolaevskiy Michael Schapira and Scott Shenker. 2016. On the Resiliency of Randomized Routing Against Multiple Edge Failures. In ICALP."},{"key":"e_1_3_2_3_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2021.3063980"},{"key":"e_1_3_2_3_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2016.2619398"},{"key":"e_1_3_2_3_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.3045293"},{"key":"e_1_3_2_3_9_1","unstructured":"Cisco. 2017. Configuring BGP PIC Edge and Core for IP and MPLS."},{"key":"e_1_3_2_3_10_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition 3rd ed.). The MIT Press.","edition":"3"},{"volume-title":"Treewidth and Hyperbolicity of the Internet","author":"de Montgolfier Fabien","key":"e_1_3_2_3_11_1","unstructured":"Fabien de Montgolfier, Mauricio Soto, and Laurent Viennot. 2011. Treewidth and Hyperbolicity of the Internet. In NCA. IEEE Computer Society, 25--32."},{"key":"e_1_3_2_3_12_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel. 2012. Graph Theory, 4th Edition. Graduate texts in mathematics, Vol. 173. Springer.","edition":"4"},{"key":"e_1_3_2_3_13_1","doi-asserted-by":"crossref","unstructured":"Joan Feigenbaum Brighten Godfrey Aurojit Panda Michael Schapira Scott Shenker and Ankit Singla. 2012. Brief announcement: on the resilience of routing tables. In PODC. ACM.","DOI":"10.1145\/2332432.2332478"},{"key":"e_1_3_2_3_14_1","first-page":"1","article-title":"Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally","volume":"46","author":"Foerster Klaus-Tycho","year":"2020","unstructured":"Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tr\u00e9dan. 2020. Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally. In DISC. 46:1--46:3.","journal-title":"DISC."},{"volume-title":"Grafting Arborescences for Extra Resilience of Fast Rerouting Schemes","author":"Foerster Klaus-Tycho","key":"e_1_3_2_3_15_1","unstructured":"Klaus-Tycho Foerster, Andrzej Kamisinski, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tr\u00e9dan. 2021b. Grafting Arborescences for Extra Resilience of Fast Rerouting Schemes. In INFOCOM. IEEE, 1--10."},{"key":"e_1_3_2_3_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2020.2998019"},{"key":"e_1_3_2_3_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOMW.2018.8406885"},{"key":"e_1_3_2_3_18_1","volume-title":"Stefan Schmid, and Gilles Tr\u00e9dan.","author":"Foerster Klaus-Tycho","year":"2022","unstructured":"Klaus-Tycho Foerster, Juho Hirvonen Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tr\u00e9dan. 2022b. On the Price of Locality in Static Fast Rerouting. In DSN. IEEE."},{"key":"e_1_3_2_3_19_1","volume-title":"On the Feasibility of Perfect Resilience with Local Fast Failover. In Symposium on Algorithmic Principles of Computer Systems (APOCS).","author":"Foerster Klaus-Tycho","year":"2021","unstructured":"Klaus-Tycho Foerster, Juho Hirvonen, Yvonne Anne Pignolet, Stefan Schmid, and Gilles Tr\u00e9dan. 2021a. On the Feasibility of Perfect Resilience with Local Fast Failover. In Symposium on Algorithmic Principles of Computer Systems (APOCS)."},{"key":"e_1_3_2_3_20_1","volume-title":"Stefan Schmid, and Gilles Tr\u00e9dan.","author":"Foerster Klaus-Tycho","year":"2019","unstructured":"Klaus-Tycho Foerster, Yvonne Anne Pignolet, Stefan Schmid, and Gilles Tr\u00e9dan. 2019. CASA: Congestion and Stretch Aware Static Fast Rerouting. In INFOCOM. IEEE."},{"key":"e_1_3_2_3_21_1","first-page":"35","article-title":"Achieving sub-second IGP convergence in large IP networks","volume":"35","author":"Pierre Francc","year":"2005","unstructured":"Pierre Francc ois, Clarence Filsfils, John Evans, and Olivier Bonaventure. 2005. Achieving sub-second IGP convergence in large IP networks. ACM CCR, Vol. 35, 3 (2005), 35--44.","journal-title":"ACM CCR"},{"key":"e_1_3_2_3_22_1","doi-asserted-by":"crossref","unstructured":"Phillipa Gill Navendu Jain and Nachiappan Nagappan. 2011. Understanding network failures in data centers: measurement analysis and implications. In SIGCOMM. ACM.","DOI":"10.1145\/2018436.2018477"},{"volume-title":"LATIN 2018: Theoretical Informatics, Michael A","author":"Grossi Roberto","key":"e_1_3_2_3_23_1","unstructured":"Roberto Grossi, Andrea Marino, and Luca Versari. 2018. Efficient Algorithms for Listing k Disjoint st-Paths in Graphs. In LATIN 2018: Theoretical Informatics, Michael A. Bender, Mart\u00edn Farach-Colton, and Miguel A. Mosteiro (Eds.). Springer International Publishing, Cham, 544--557."},{"key":"e_1_3_2_3_24_1","unstructured":"ISO. 2002. Intermediate Ststem-to-Intermediate System (IS-IS) Routing Protocol. ISO\/IEC 10589."},{"key":"e_1_3_2_3_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11235-011-9582-5"},{"volume-title":"Evolution of IP Fast-Reroute Strategies","author":"Kamisi\u0144ski Andrzej","key":"e_1_3_2_3_26_1","unstructured":"Andrzej Kamisi\u0144ski. 2018. Evolution of IP Fast-Reroute Strategies. In RNDM. IEEE."},{"key":"e_1_3_2_3_27_1","unstructured":"Evangelos Kranakis Harvinder Singh and Jorge Urrutia. 1999. Compass routing on geometric networks. In CCCG."},{"key":"e_1_3_2_3_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2123916"},{"key":"e_1_3_2_3_29_1","doi-asserted-by":"crossref","unstructured":"Karthik Lakshminarayanan Matthew Caesar Murali Rangan Tom Anderson Scott Shenker and Ion Stoica. 2007. Achieving convergence-free routing using failure-carrying packets. In SIGCOMM. ACM 241--252.","DOI":"10.1145\/1282427.1282408"},{"key":"e_1_3_2_3_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.1011"},{"key":"e_1_3_2_3_31_1","unstructured":"Junda Liu Aurojit Panda Ankit Singla Brighten Godfrey Michael Schapira and Scott Shenker. 2013. Ensuring Connectivity via Data Plane Mechanisms. In NSDI."},{"key":"e_1_3_2_3_32_1","first-page":"1","article-title":"OSPF Version 2","volume":"2328","author":"Moy John","year":"1998","unstructured":"John Moy. 1998. OSPF Version 2. RFC, Vol. 2328 (1998), 1--244.","journal-title":"RFC"},{"key":"e_1_3_2_3_33_1","first-page":"1","article-title":"Fast Reroute Extensions to RSVP-TE for LSP Tunnels","volume":"4090","author":"Pan Ping","year":"2005","unstructured":"Ping Pan, George Swallow, and Alia Atlas. 2005. Fast Reroute Extensions to RSVP-TE for LSP Tunnels. RFC, Vol. 4090 (2005), 1--38.","journal-title":"RFC"},{"key":"e_1_3_2_3_34_1","doi-asserted-by":"crossref","unstructured":"J. Pap\u00e1n P. Sege\u010d M. Morav\u010d\u00edk M. Kont?ek L. Miku? and J. Uramov\u00e1. 2018. Overview of IP Fast Reroute Solutions. In ICETA.","DOI":"10.1109\/ICETA.2018.8572205"},{"key":"e_1_3_2_3_35_1","doi-asserted-by":"crossref","unstructured":"Oliver Schweiger Klaus-Tycho Foerster and Stefan Schmid. 2021. Improving the Resilience of Fast Failover Routing: TREE (Tree Routing to Extend Edge disjoint paths). In ANCS. ACM 1--7.","DOI":"10.1145\/3493425.3502747"},{"key":"e_1_3_2_3_36_1","doi-asserted-by":"crossref","unstructured":"Apoorv Shukla and Klaus-Tycho Foerster. 2021. Shortcutting Fast Failover Routes in the Data Plane. In ANCS. ACM 15--22.","DOI":"10.1145\/3493425.3502751"},{"key":"e_1_3_2_3_37_1","unstructured":"Switch Specification 1.3.1. 2013. OpenFlow. In https:\/\/opennetworking.org\/wp-content\/uploads\/2013\/04\/openflow-spec-v1.3.1.pdf."},{"key":"e_1_3_2_3_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(74)90003-9"},{"key":"e_1_3_2_3_39_1","doi-asserted-by":"crossref","unstructured":"Balajee Vamanan Jahangir Hasan and T. N. Vijaykumar. 2012. Deadline-aware datacenter tcp (D2TCP). In SIGCOMM. ACM.","DOI":"10.1145\/2342356.2342388"},{"key":"e_1_3_2_3_40_1","volume-title":"Keep Forwarding: Towards k-link failure resilient routing","author":"Yang Baohua","year":"2014","unstructured":"Baohua Yang, Junda Liu, Scott Shenker, Jun Li, and Kai Zheng. 2014. Keep Forwarding: Towards k-link failure resilient routing. In INFOCOM. IEEE."},{"key":"e_1_3_2_3_41_1","volume-title":"Katz","author":"Zats David","year":"2012","unstructured":"David Zats, Tathagata Das, Prashanth Mohan, Dhruba Borthakur, and Randy H. Katz. 2012. DeTail: reducing the flow completion time tail in datacenter networks. In SIGCOMM. ACM."}],"event":{"name":"SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Orlando FL USA","acronym":"SPAA '23"},"container-title":["Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591080","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3558481.3591080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:06Z","timestamp":1750178826000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3558481.3591080"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,17]]},"references-count":41,"alternative-id":["10.1145\/3558481.3591080","10.1145\/3558481"],"URL":"https:\/\/doi.org\/10.1145\/3558481.3591080","relation":{},"subject":[],"published":{"date-parts":[[2023,6,17]]},"assertion":[{"value":"2023-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}