User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Robustly disjoint paths with segment routing

Primary tabs

download
  • Open access
  • PDF
  • 813.80 K
Aubry, François [UCL] Vissicchio, Stefano Bonaventure, Olivier [UCL] Deville, Yves [UCL]

Motivated by conversations with operators and by possibilities to unlock future Internet-based applications, we study how to enable Internet Service Providers (ISPs) to reliably offer connectivity through disjoint paths as an advanced, value-added service. As ISPs are increasingly deploying Segment Routing (SR), we focus on implementing such service with SR. We introduce the concept of robustly disjoint paths, pairs of paths that are constructed to remain disjoint even after an input set of failures, with no external intervention (e.g., configuration change). We extend the routing theory, study the problem complexity, and design efficient algorithms to automatically compute SR-based robustly disjoint paths. Our algorithms enable a fully automated approach to offer the disjoint-path connectivity, based on configuration synthesis. Our evaluation on real topologies shows that such an approach is practical, and scales to large ISP networks.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès libre
Publication date 2018
Language Anglais
Conference "the 14th International Conference on emerging Networking EXperiments and Technologies", Heraklion, Greece (du 4/12/2018 au 7/12/2018)
Peer reviewed yes
Host document "Proceedings of the 14th International Conference on emerging Networking EXperiments and Technologies - CoNEXT '18" (ISBN : 9781450360807)
Publisher ACM Press
Publication status Publié
Affiliation UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Keywords Segment Routing ; algorithms
Links
  1. R. White and D. Donohue. Art of Network Architecture, The: Business-Driven Design. Cisco Press, 2014.
  2. Watson D., Jahanian F., Labovitz C., Experiences with monitoring ospf on a regional service provider network, 10.1109/icdcs.2003.1203467
  3. Vygen Jens, NP-completeness of some edge-disjoint paths problems, 10.1016/0166-218x(93)e0177-z
  4. D. Voyer. CO/DC Network Transformation. MPLS World Congress, 2017.
  5. J.-P. Vasseur, M. Pickavet, and P. Demeester. Network recovery: Protection and Restoration of Optical, SONET-SDH, IP, and MPLS. Elsevier, 2004.
  6. Turner Daniel, Levchenko Kirill, Snoeren Alex C., Savage Stefan, California fault lines : understanding the causes and impact of network failures, 10.1145/1851182.1851220
  7. F. Trate. Segment Routing is crossing the chasm with real live deployments. Cisco Blog, 2016.
  8. O. Tilmans and S. Vissicchio. IGP-as-a-Backup for Robust SDN Networks. In CNSM, 2014.
  9. J. Tantsura. The critical role of maximum sid depth (msd) hardware limitations in segment routing ecosystem and how to work around those. In NANOG71, October 2017. https://pc.nanog.org/static/published/meetings//NANOG71/daily/day_5.html#talk_1424.
  10. Suurballe J. W., Tarjan R. E., A quick method for finding shortest pairs of disjoint paths, 10.1002/net.3230140209
  11. R. Steenbergen. MPLS Autobandwidth. RIPE 64 presentation, 2012.
  12. N. Spring et al. Measuring ISP Topologies with Rocketfuel. IEEE/ACM ToN, 12(1):2--16 2004.
  13. V. Sharma and F. Hellstrand. Framework for Multi-Protocol Label Switching (MPLS)-based Recovery. RFC 3469, 2003.
  14. Schuller Timmy, Aschenbruck Nils, Chimani Markus, Horneffer Martin, Schnitter Stefan, Traffic engineering using segment routing and considering requirements of a carrier IP network, 10.23919/ifipnetworking.2017.8264828
  15. Raiciu Costin, Barre Sebastien, Pluntke Christopher, Greenhalgh Adam, Wischik Damon, Handley Mark, Improving datacenter performance and robustness with multipath TCP, 10.1145/2018436.2018467
  16. A. Pathak, M. Zhang, Y. C. Hu, R. Mahajan, and D. Maltz. Latency Inflation with MPLS-based Traffic Engineering. In IMC, 2011.
  17. NANOG mailing list. Bell outage. https://mailman.nanog.org/pipermail/nanog/2017-August/091828.html, 2017.
  18. P. Mattes. Segment Routing for Datacenter Interconnect at Scale. MPLS World Congress, 2017.
  19. Markopoulou A., Iannaccone G., Bhattacharyya S., Chen-Nee Chuah, Ganjali Y., Diot C., Characterization of Failures in an Operational IP Backbone Network, 10.1109/tnet.2007.902727
  20. J. Liu, A. Panda, A. Singla, B. Godfrey, M. Schapira, and S. Shenker. Ensuring Connectivity via Data Plane Mechanisms. In NSDI, 2013.
  21. Liu Hongqiang Harry, Kandula Srikanth, Mahajan Ratul, Zhang Ming, Gelernter David, Traffic engineering with forward fault correction, 10.1145/2619239.2626314
  22. Li Chung-Lun, McCormick S.Thomas, Simchi-Levi David, The complexity of finding two disjoint paths with min-max objective function, 10.1016/0166-218x(90)90024-7
  23. Knight Simon, Nguyen Hung X., Falkner Nickolas, Bowden Rhys, Roughan Matthew, The Internet Topology Zoo, 10.1109/jsac.2011.111002
  24. Karp Richard M., Reducibility among Combinatorial Problems, Complexity of Computer Computations (1972) ISBN:9781468420036 p.85-103, 10.1007/978-1-4684-2001-2_9
  25. C. Hopps. Analysis of an equal-cost multi-path algorithm. RFC 2992, 2000.
  26. Hartert Renaud, Vissicchio Stefano, Schaus Pierre, Bonaventure Olivier, Filsfils Clarence, Telkamp Thomas, Francois Pierre, A Declarative and Expressive Approach to Control Forwarding Paths in Carrier-Grade Networks, 10.1145/2785956.2787495
  27. Hao Fang, Kodialam Murali, Lakshman T. V., Optimizing restoration with segment routing, 10.1109/infocom.2016.7524551
  28. Gvozdiev Nikola, Vissicchio Stefano, Karp Brad, Handley Mark, Low-Latency Routing on Mesh-Like Backbones, 10.1145/3152434.3152453
  29. Guo Yuchun, Kuipers Fernando, Van Mieghem Piet, Link-disjoint paths for reliable QoS routing, 10.1002/dac.612
  30. Ghobadi Monia, Mahajan Ratul, Optical Layer Failures in a Large Backbone, 10.1145/2987443.2987483
  31. Francois Pierre, Filsfils Clarence, Evans John, Bonaventure Olivier, Achieving sub-second IGP convergence in large IP networks, 10.1145/1070873.1070877
  32. Foerster Klaus-Tycho, Parham Mahmoud, Chiesa Marco, Schmid Stefan, TI-MFA: Keep calm and reroute segments fast, 10.1109/infcomw.2018.8406885
  33. Filsfils Clarence, Nainar Nagendra Kumar, Pignataro Carlos, Cardona Juan Camilo, Francois Pierre, The Segment Routing Architecture, 10.1109/glocom.2015.7417124
  34. A. Farrel, O. Komolafe, and S. Yasukawa. An analysis of scaling issues in mpls-te core networks. IETF RFC5439, 2009.
  35. Elhourani Theodore, Gopalan Abishek, Ramasubramanian Srinivasan, IP fast rerouting for multi-link failures, 10.1109/infocom.2014.6848157
  36. Dolev Danny, Dwork Cynthia, Waarts Orli, Yung Moti, Perfectly secure message transmission, 10.1145/138027.138036
  37. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
  38. M. Chiesa, I. Nikolaevskiy, S. Mitrovic, A. Panda, A. Gurtov, A. Maidry, M. Schapira, and S. Shenker. The quest for resilient (static) forwarding tables. In INFOCOM, 2016.
  39. Björklund Andreas, Husfeldt Thore, Shortest Two Disjoint Paths in Polynomial Time, Automata, Languages, and Programming (2014) ISBN:9783662439470 p.211-222, 10.1007/978-3-662-43948-7_18
  40. Bhatia Randeep, Hao Fang, Kodialam Murali, Lakshman T.V., Optimized network traffic engineering using segment routing, 10.1109/infocom.2015.7218434
  41. R. Beckett, R. Mahajan, T. Millstein, J. Padhye, and D. Walker. Don't Mind the Gap: Bridging Network-wide Objectives and Device-level Configurations. In SIGCOMM, 2016.
  42. D. O. Awduche, L. Berger, D.-H. Gan, D. T. Li, D. V. Srinivasan, and G. Swallow. RSVP-TE: Extensions to RSVP for LSP Tunnels. RFC 3209, 2001.
  43. F. Aubry, D. Lebrun, S. Vissicchio, M. T. Khong, Y. Deville, and O. Bonaventure. SCMon: Leveraging Segment Routing to Improve Network Monitoring. In INFOCOM, 2016.
  44. Aubry Francois, Lebrun David, Deville Yves, Bonaventure Olivier, Traffic duplication through segmentable disjoint paths, 10.1109/ifipnetworking.2015.7145304
  45. A. Atlas and A. D. Zinin. Basic Specification for IP Fast Reroute: Loop-Free Alternates. RFC 5286, 2008.
  46. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.
Bibliographic reference Aubry, François ; Vissicchio, Stefano ; Bonaventure, Olivier ; Deville, Yves. Robustly disjoint paths with segment routing.the 14th International Conference on emerging Networking EXperiments and Technologies (Heraklion, Greece, du 4/12/2018 au 7/12/2018). In: Proceedings of the 14th International Conference on emerging Networking EXperiments and Technologies - CoNEXT '18, ACM Press2018
Permanent URL http://hdl.handle.net/2078.1/214183