Document Open Access Logo

Local Fast Segment Rerouting on Hypercubes

Authors Klaus-Tycho Foerster , Mahmoud Parham , Stefan Schmid , Tao Wen

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.13.pdf
  • Filesize: 1.32 MB
  • 17 pages

Document Identifiers

Author Details

Klaus-Tycho Foerster
  • University of Vienna, Vienna, Austria
Mahmoud Parham
  • University of Vienna, Vienna, Austria
Stefan Schmid
  • University of Vienna, Vienna, Austria
Tao Wen
  • University of Electronic Science and Technology of China, Chengdu, China

Funding

  • Parham, Mahmoud: Contact and main author.

Cite As Get BibTex

Klaus-Tycho Foerster, Mahmoud Parham, Stefan Schmid, and Tao Wen. Local Fast Segment Rerouting on Hypercubes. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.OPODIS.2018.13

Abstract

Fast rerouting is an essential mechanism in any dependable communication network, allowing to quickly, i.e., locally, recover from network failures, without invoking the control plane. However, while locality ensures a fast reaction, the absence of global information also renders the design of highly resilient fast rerouting algorithms more challenging. In this paper, we study algorithms for fast rerouting in emerging Segment Routing (SR) networks, where intermediate destinations can be added to packets by nodes along the path. Our main contribution is a maximally resilient polynomial-time fast rerouting algorithm for SR networks based on a hypercube topology. Our algorithm is attractive as it preserves the original paths (and hence waypoints traversed along the way), and does not require packets to carry failure information. We complement our results with an integer linear program formulation for general graphs and exploratory simulation results.

Subject Classification

ACM Subject Classification
  • Networks → Routing protocols
  • Networks → Network reliability
  • Theory of computation → Design and analysis of algorithms
Keywords
  • segment routing
  • local fast failover
  • link failures

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, Mahmoud Parham, and Stefan Schmid. Waypoint Routing in Special Networks. In Proc. IFIP Networking, 2018. Google Scholar
  2. Saeed Akhoondian Amiri, Klaus-Tycho Foerster, Riko Jacob, and Stefan Schmid. Charting the Algorithmic Complexity of Waypoint Routing. CCR, 48(1):42-48, 2018. URL: http://dx.doi.org/10.1145/3211852.3211859.
  3. Alia K Atlas and Alex Zinin. Basic specification for IP fast-reroute: loop-free alternates. IETF RFC 5286, 2008. Google Scholar
  4. François Aubry, David Lebrun, Stefano Vissicchio, Minh Thanh Khong, Yves Deville, and Olivier Bonaventure. Scmon: Leveraging segment routing to improve network monitoring. In Proc. IEEE INFOCOM, 2016. Google Scholar
  5. Randeep Bhatia, Fang Hao, Murali Kodialam, and TV Lakshman. Optimized network traffic engineering using segment routing. In IEEE INFOCOM, 2015. Google Scholar
  6. Michael Borokhovich and Stefan Schmid. How (Not) to Shoot in Your Foot with SDN Local Fast Failover: A Load-Connectivity Tradeoff. In OPODIS, 2013. Google Scholar
  7. Costas Busch, Srikanth Surapaneni, and Srikanta Tirthapura. Analysis of link reversal routing algorithms for mobile ad hoc networks. In Proc. ACM SPAA. ACM, 2003. URL: http://dx.doi.org/10.1145/777412.777446.
  8. Marco Canini, Petr Kuznetsov, Dan Levin, and Stefan Schmid. A Distributed and Robust SDN Control Plane for Transactional Network Updates. In Proc. IEEE INFOCOM, 2015. Google Scholar
  9. B. Carpenter and S. Brim. Middleboxes: Taxonomy and Issues. RFC 3234, RFC Editor, February 2002. URL: http://www.rfc-editor.org/rfc/rfc3234.txt.
  10. 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. URL: http://dx.doi.org/10.1109/TNET.2016.2619398.
  11. 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. URL: http://dx.doi.org/10.1109/INFOCOM.2016.7524552.
  12. Hongsik Choi, Suresh Subramaniam, and Hyeong-Ah Choi. On double-link failure recovery in WDM optical networks. In Proc. IEEE INFOCOM, 2002. URL: http://dx.doi.org/10.1109/INFCOM.2002.1019327.
  13. Luca Davoli, Luca Veltri, Pier Luigi Ventre, Giuseppe Siracusano, and Stefano Salsano. Traffic engineering with segment routing: SDN-based architectural design and open source implementation. In Proc. EWSDN, 2015. Google Scholar
  14. Fabien Duchêne, David Lebrun, and Olivier Bonaventure. SRv6Pipes: enabling in-network bytestream functions. In Proc. IFIP Networking, 2018. Google Scholar
  15. 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
  16. Gábor Enyedi, Gábor Rétvári, and Tibor Cinkler. A novel loop-free IP fast reroute algorithm. In Meeting of the European Network of Universities and Companies in Information and Communication Engineering, pages 111-119. Springer, 2007. Google Scholar
  17. Joan Feigenbaum et al. BA: On the resilience of routing tables. In Proc. ACM PODC, 2012. Google Scholar
  18. ETSI. Network Functions Virtualisation. In White Paper, 2013. Google Scholar
  19. Nick Feamster, Jennifer Rexford, and Ellen Zegura. The road to SDN: an intellectual history of programmable networks. ACM SIGCOMM CCR, 44(2):87-98, 2014. Google Scholar
  20. Clarence Filsfils, Pierre François, Stefano Previdi, Bruno Decraene, Stephane Litkowski, Martin Horneffer, Igor Milojevic, Rob Shakir, Saku Ytti, Wim Henderickx, Jeff Tantsura, Sriganesh Kini, and Edward Crabbe. Segment Routing Architecture. In Segment Routing Use Cases, IETF Internet-Draft, 2014. Google Scholar
  21. Clarence Filsfils, Nagendra Kumar Nainar, Carlos Pignataro, Juan Camilo Cardona, and Pierre Francois. The segment routing architecture. In IEEE GLOBECOM, 2015. Google Scholar
  22. 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
  23. Klaus-Tycho Foerster, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan. Local Fast Failover Routing With Low Stretch. ACM SIGCOMM CCR, 1:35-41, January 2018. Google Scholar
  24. Klaus-Tycho Foerster, Yvonne Anne Pignolet, Stefan Schmid, and Gilles Trédan. Local Fast Failover Routing With Low Stretch. CCR, 48(1):35-41, 2018. URL: http://dx.doi.org/10.1145/3211852.3211858.
  25. 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.
  26. Pierre François, Clarence Filsfils, John Evans, and Olivier Bonaventure. Achieving sub-second IGP convergence in large IP networks. CCR, 35(3):35-44, 2005. URL: http://dx.doi.org/10.1145/1070873.1070877.
  27. Eli M. Gafni and Dimitri P. Bertsekas. Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology. IEEE Transactions on Communications, 29(1):11-18, January 1981. Google Scholar
  28. Phillipa Gill, Navendu Jain, and Nachiappan Nagappan. Understanding network failures in data centers: measurement, analysis, and implications. In ACM SIGCOMM CCR, volume 41, pages 350-361, 2011. Google Scholar
  29. Alessio Giorgetti, Piero Castoldi, Filippo Cugini, Jeroen Nijhof, Francesco Lazzeri, and Gianmarco Bruno. Path encoding in segment routing. In Proc. IEEE GLOBECOM, 2015. Google Scholar
  30. Chuanxiong Guo, Guohan Lu, Dan Li, Haitao Wu, Xuan Zhang, Yunfeng Shi, Chen Tian, Yongguang Zhang, and Songwu Lu. BCube: a high performance, server-centric network architecture for modular data centers. In Proc. ACM SIGCOMM, 2009. Google Scholar
  31. Anupam Gupta, Amit Kumar, and Rajeev Rastogi. Traveling with a pez dispenser (or, routing issues in mpls). SIAM Journal on Computing, 34(2):453-474, 2005. Google Scholar
  32. Prashanth Hande, Mung Chiang, Robert Calderbank, and Sundeep Rangan. Network pricing and rate allocation with content-provider participation. In Proc. IEEE INFOCOM, 2010. Google Scholar
  33. Ed Harrison, Adrian Farrel, and Ben Miller. Protection and restoration in MPLS networks. Data Connection White Paper, 2001. Google Scholar
  34. Renaud Hartert, Stefano Vissicchio, Pierre Schaus, Olivier Bonaventure, Clarence Filsfils, Thomas Telkamp, and Pierre Francois. A declarative and expressive approach to control forwarding paths in carrier-grade networks. In ACM SIGCOMM CCR, volume 45, pages 15-28, 2015. Google Scholar
  35. Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Vijay Gill, Mohan Nanduri, and Roger Wattenhofer. Achieving high utilization with software-driven WAN. In Proc. ACM SIGCOMM, 2013. Google Scholar
  36. Jesper Stenbjerg Jensen, Troels Beck Krogh, Jonas Sand Madsen, Stefan Schmid, Jiri Srba, and Marc Tom Thorgersen. P-Rex: Fast Verification of MPLS Networks with Multiple Link Failures. In Proc. ACM CoNEXT, 2018. Google Scholar
  37. Karthik Lakshminarayanan, Matthew Caesar, Murali Rangan, Tom Anderson, Scott Shenker, and Ion Stoica. Achieving convergence-free routing using failure-carrying packets. In Proceedings of the ACM SIGCOMM 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Kyoto, Japan, August 27-31, 2007, pages 241-252. ACM, 2007. URL: http://dx.doi.org/10.1145/1282380.1282408.
  38. David Lebrun. Reaping the Benefits of IPv6 Segment Routing. PhD thesis, UCLouvain / ICTEAM / EPL, October 2017. Google Scholar
  39. David Lebrun. Virtual networks testing framework (Nanonet). https://github.com/segment-routing/nanonet, February 2017.
  40. David Lebrun and Olivier Bonaventure. Implementing IPv6 Segment Routing in the Linux Kernel. In Proc. ACM ANRW, 2017. Google Scholar
  41. David Lebrun, Mathieu Jadin, François Clad, Clarence Filsfils, and Olivier Bonaventure. Software Resolved Networks: Rethinking Enterprise Networks with IPv6 Segment Routing. In Proc. ACM SOSR, 2018. Google Scholar
  42. Ming-Chieh Lee and Jang-Ping Sheu. An Efficient Routing Algorithm Based on Segment Routing in Software-defined Networking. Comput. Netw., 103(C):44-55, July 2016. Google Scholar
  43. Hongqiang Harry Liu, Srikanth Kandula, Ratul Mahajan, Ming Zhang, and David Gelernter. Traffic engineering with forward fault correction. In Proc. ACM SIGCOMM, 2014. Google Scholar
  44. Junda Liu, Aurojit Panda, Ankit Singla, Brighten Godfrey, Michael Schapira, and Scott Shenker. Ensuring Connectivity via Data Plane Mechanisms. In Proc. USENIX NSDI, 2013. Google Scholar
  45. Grzegorz Malewicz, Alexander Russell, and Alexander A. Shvartsman. Distributed scheduling for disconnected cooperation. Distributed Computing, 18(6):409-420, 2005. Google Scholar
  46. Athina Markopoulou, Gianluca Iannaccone, Supratik Bhattacharyya, Chen-Nee Chuah, Yashar Ganjali, and Christophe Diot. Characterization of failures in an operational IP backbone network. IEEE/ACM Trans. Netw., 16(4):749-762, 2008. URL: http://dx.doi.org/10.1145/1453698.1453699.
  47. Srihari Nelakuditi, Sanghwan Lee, Yinzhe Yu, Zhi-Li Zhang, and Chen-Nee Chuah. Fast local rerouting for handling transient link failures. IEEE/ACM Trans. Netw, 15(2):359-372, 2007. Google Scholar
  48. Mohammad Noormohammadpour and Cauligi S Raghavendra. Datacenter Traffic Control: Understanding Techniques and Tradeoffs. IEEE Communications Surveys &Tutorials, 20(2):1492-1525, 2017. Google Scholar
  49. Eunseuk Oh, Hongsik Choi, and Jong-Seok Kim. Double-Link Failure Recovery in WDM Optical Torus Networks. In Information Networking, Networking Technologies for Broadband and Mobile Networks, International Conference ICOIN, 2004. Google Scholar
  50. P. Pan, G. Swallow, and A. Atlas. Fast Reroute Extensions to RSVP-TE for LSP Tunnels. RFC 4090, RFC Editor, May 2005. Google Scholar
  51. Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan. Load-Optimal Local Fast Rerouting for Dependable Networks. In Proc. IEEE/IFIP DSN, 2017. Google Scholar
  52. Y. Saad and M. H. Schultz. Topological properties of hypercubes. IEEE Transactions on Computers, 37(7):867-872, July 1988. Google Scholar
  53. Yousef Saad and Martin H. Schultz. Data Communication in Hypercubes. J. Parallel Distrib. Comput., 6(1):115-135, 1989. URL: http://dx.doi.org/10.1016/0743-7315(89)90045-2.
  54. Stefano Salsano, Luca Veltri, Luca Davoli, Pier Luigi Ventre, and Giuseppe Siracusano. PMSR—Poor Man’s Segment Routing, a minimalistic approach to Segment Routing and a Traffic Engineering use case. In Proc. IEEE/IFIP NOMS, 2016. Google Scholar
  55. Stefan Schmid and Jiri Srba. Polynomial-Time What-If Analysis for Prefix-Manipulating MPLS Networks. In Proc. IEEE INFOCOM, 2018. Google Scholar
  56. Aman Shaikh, Chris Isett, Albert Greenberg, Matthew Roughan, and Joel Gottlieb. A case study of OSPF behavior in a large enterprise network. In Proc. ACM SIGCOMM Workshop on Internet Measurment, 2002. Google Scholar
  57. Lu Shen, Xi Yang, and Byrav Ramamurthy. Shared risk link group (SRLG)-diverse path provisioning under hybrid service level agreements in wavelength-routed optical mesh networks. IEEE/ACM Transactions on Networking (ToN), 13(4):918-931, 2005. Google Scholar
  58. Abhinav Kumar Singh, Ravindra Singh, and Bikash C. Pal. Stability Analysis of Networked Control in Smart Grids. IEEE Trans. Smart Grid, 6(1):381-390, 2015. URL: http://dx.doi.org/10.1109/TSG.2014.2314494.
  59. Brent Stephens, Alan L. Cox, and Scott Rixner. Plinko: Building Provably Resilient Forwarding Tables. In Proc. 12th ACM HotNets, 2013. Google Scholar
  60. Brent Stephens, Alan L Cox, and Scott Rixner. Scalable Multi-Failure Fast Failover via Forwarding Table Compression. SOSR. ACM, 2016. Google Scholar
  61. János Tapolcai, Balázs Vass, Zalán Heszberger, József Bıró, David Hay, Fernando A Kuipers, and Lajos Rónyai. A Tractable Stochastic Model of Correlated Link Failures Caused by Disasters. In Proc. IEEE INFOCOM, 2018. Google Scholar
  62. Frederic Trate. Bringing Segment Routing and IPv6 together, August 2016. URL: https://blogs.cisco.com/sp/bringing-segment-routing-and-ipv6-together.
  63. George Trimponias, Yan Xiao, Hong Xu, Xiaorui Wu, and Yanhui Geng. On Traffic Engineering with Segment Routing in SDN based WANs. arXiv preprint arXiv:1703.05907, 2017. Google Scholar
  64. Emmanouel A. Varvarigos and Dimitri P. Bertsekas. Performance of hypercube routing schemes with or without buffering. IEEE/ACM Trans. Netw., 2(3):299-311, 1994. URL: http://dx.doi.org/10.1109/90.311628.
  65. Junling Wang and Srihari Nelakuditi. IP fast reroute with failure inferencing. In Proc. SIGCOMM Workshop on Internet Network Management, pages 268-273, 2007. Google Scholar
  66. Ye Wang, Hao Wang, Ajay Mahimkar, Richard Alimi, Yin Zhang, Lili Qiu, and Yang Richard Yang. R3: resilient routing reconfiguration. In Proc. ACM SIGCOMM, 2010. Google Scholar
  67. Christo Wilson, Hitesh Ballani, Thomas Karagiannis, and Antony I. T. Rowstron. Better never than late: meeting deadlines in datacenter networks. In Proc. ACM SIGCOMM, 2011. Google Scholar
  68. Baobao Zhang, Jianping Wu, and Jun Bi. RPFP: IP fast reroute with providing complete protection and without using tunnels. In Proc. IWQoS, 2013. 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