Document Open Access Logo

Maximally Resilient Replacement Paths for a Family of Product Graphs

Authors Mahmoud Parham , Klaus-Tycho Foerster , Petar Kosic , Stefan Schmid

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.26.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Author Details

Mahmoud Parham
  • University of Vienna, Faculty of Computer Science, Vienna, Austria
Klaus-Tycho Foerster
  • University of Vienna, Faculty of Computer Science, Vienna, Austria
Petar Kosic
  • University of Vienna, Faculty of Computer Science, Vienna, Austria
Stefan Schmid
  • University of Vienna, Faculty of Computer Science, Vienna, Austria

Funding

Research (in part) supported by the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024.

Cite As Get BibTex

Mahmoud Parham, Klaus-Tycho Foerster, Petar Kosic, and Stefan Schmid. Maximally Resilient Replacement Paths for a Family of Product Graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.OPODIS.2020.26

Abstract

Modern communication networks support fast path restoration mechanisms which allow to reroute traffic in case of (possibly multiple) link failures, in a completely decentralized manner and without requiring global route reconvergence. However, devising resilient path restoration algorithms is challenging as these algorithms need to be inherently local. Furthermore, the resulting failover paths often have to fulfill additional requirements related to the policy and function implemented by the network, such as the traversal of certain waypoints (e.g., a firewall). 
This paper presents local algorithms which ensure a maximally resilient path restoration for a large family of product graphs, including the widely used tori and generalized hypercube topologies. Our algorithms provably ensure that even under multiple link failures, traffic is rerouted to the other endpoint of every failed link whenever possible (i.e. detouring failed links), enforcing waypoints and hence accounting for the network policy. The algorithms are particularly well-suited for emerging segment routing networks based on label stacks.

Subject Classification

ACM Subject Classification
  • Networks → Routing protocols
  • Computer systems organization → Dependable and fault-tolerant systems and networks
  • Mathematics of computing → Graph algorithms
Keywords
  • Product Graphs
  • Resilience
  • Failures
  • Routing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Saeed Akhoondian Amiri, Klaus-Tycho Foerster, Riko Jacob, and Stefan Schmid. Charting the algorithmic complexity of waypoint routing. Comput. Commun. Rev., 48(1):42-48, 2018. Google Scholar
  2. Alia K Atlas and Alex Zinin. Basic specification for IP fast-reroute: loop-free alternates. IETF RFC 5286, 2008. Google Scholar
  3. Michael Borokhovich and Stefan Schmid. How (not) to shoot in your foot with SDN local fast failover: A load-connectivity tradeoff. In Proc. OPODIS, 2013. Google Scholar
  4. B. Carpenter and S. Brim. Middleboxes: Taxonomy and issues. RFC 3234, RFC Editor, February 2002. URL: http://www.rfc-editor.org/rfc/rfc3234.txt.
  5. Marco Chiesa, Andrei V. Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Schapira, and Scott Shenker. On the resiliency of randomized routing against multiple edge failures. In Proc. ICALP, 2016. Google Scholar
  6. Marco Chiesa, Andrzej Kamisiński, Jacek Rak, Gábor Rétvári, and Stefan Schmid. A Survey of Fast Recovery Mechanisms in the Data Plane. TechRxiv, 2020. URL: https://www.techrxiv.org/articles/preprint/Fast_Recovery_Mechanisms_in_the_Data_Plane/12367508.
  7. Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrovic, Andrei V. Gurtov, Aleksander Madry, Michael Schapira, and Scott Shenker. On the resiliency of static forwarding tables. IEEE/ACM Trans. Netw., 25(2):1133-1146, 2017. Google Scholar
  8. Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrovic, Aurojit Panda, Andrei V. Gurtov, Aleksander Madry, Michael Schapira, and Scott Shenker. The quest for resilient (static) forwarding tables. In Proc. IEEE INFOCOM, 2016. Google Scholar
  9. Hongsik Choi, Suresh Subramaniam, and Hyeong-Ah Choi. On double-link failure recovery in WDM optical networks. In Proc. IEEE INFOCOM, 2002. Google Scholar
  10. Theodore Elhourani, Abishek Gopalan, and Srinivasan Ramasubramanian. IP fast rerouting for multi-link failures. IEEE/ACM Trans. Netw, 24(5):3014-3025, 2016. Google Scholar
  11. ETSI. Network functions virtualisation. In White Paper, 2013. Google Scholar
  12. Joan Feigenbaum, Brighten Godfrey, Aurojit Panda, Michael Schapira, Scott Shenker, and Ankit Singla. Brief announcement: on the resilience of routing tables. In Proc. ACM PODC, 2012. Google Scholar
  13. Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan. On the feasibility of perfect resilience with local fast failover. In Proc. APOCS, 2021. Google Scholar
  14. Klaus-Tycho Foerster, Andrzej Kamisinski, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Trédan. Bonsai: Efficient fast failover routing using small arborescences. In Proc. IEEE/IFIP DSN, 2019. Google Scholar
  15. Klaus-Tycho Foerster, Andrzej Kamisinski, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Trédan. Improved fast rerouting using postprocessing. In Proc. IEEE SRDS, 2019. Google Scholar
  16. Klaus-Tycho Foerster, Mahmoud Parham, Marco Chiesa, and Stefan Schmid. TI-MFA: keep calm and reroute segments fast. In Global Internet Symposium (GI), 2018. Google Scholar
  17. Klaus-Tycho Foerster, Mahmoud Parham, Stefan Schmid, and Tao Wen. Local fast segment rerouting on hypercubes. In Proc. OPODIS, 2018. Google Scholar
  18. Klaus-Tycho Foerster, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Trédan. Local fast failover routing with low stretch. Comput. Commun. Rev., 48(1):35-41, 2018. Google Scholar
  19. Klaus-Tycho Foerster, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Trédan. Casa: Congestion and stretch aware static fast rerouting. In Proc. IEEE INFOCOM, 2019. Google Scholar
  20. Pierre François, Clarence Filsfils, Ahmed Bashandy, and Bruno Decraene. Topology Independent Fast Reroute using Segment Routing. Internet-Draft draft-francois-segment-routing-ti-lfa-00, Internet Engineering Task Force, November 2013. URL: https://datatracker.ietf.org/doc/html/draft-francois-segment-routing-ti-lfa-00.
  21. Pierre François, Clarence Filsfils, John Evans, and Olivier Bonaventure. Achieving sub-second IGP convergence in large IP networks. Comput. Commun. Rev., 35(3):35-44, 2005. Google Scholar
  22. Karthik Lakshminarayanan, Matthew Caesar, Murali Rangan, Tom Anderson, Scott Shenker, and Ion Stoica. Achieving convergence-free routing using failure-carrying packets. In Proc. ACM SIGCOMM, 2007. Google Scholar
  23. Eunseuk Oh, Hongsik Choi, and Jong-Seok Kim. Double-link failure recovery in WDM optical torus networks. In Proc. ICOIN, 2004. Google Scholar
  24. P. Pan, G. Swallow, and A. Atlas. Fast reroute extensions to RSVP-TE for LSP tunnels. RFC 4090, RFC Editor, May 2005. Google Scholar
  25. Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan. Load-optimal local fast rerouting for resilient networks. In Proc. IEEE/IFIP DSN, 2017. Google Scholar
  26. Stefan Schmid and Jiri Srba. Polynomial-time what-if analysis for prefix-manipulating mpls networks. In Proc. IEEE INFOCOM, 2018. Google Scholar
  27. Brent Stephens, Alan L. Cox, and Scott Rixner. Plinko: Building provably resilient forwarding tables. In Proc. ACM HotNets, 2013. Google Scholar
  28. Brent Stephens, Alan L Cox, and Scott Rixner. Scalable multi-failure fast failover via forwarding table compression. SOSR. ACM, 2016. Google Scholar
  29. Baohua Yang, Junda Liu, Scott Shenker, Jun Li, and Kai Zheng. Keep forwarding: Towards k-link failure resilient routing. In Proc. IEEE INFOCOM, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact