Abstract
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 feasible paths, without violating capacity constraints, for up to k 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 pessimistic model where flows interfere in a worst-case manner along equal-cost shortest paths, and an optimistic 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.
Chapter PDF
Similar content being viewed by others
References
Carolyn Jane 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–126, 2014.
Ron Banner and Ariel Orda. Multipath routing algorithms for congestion minimization. In IEEE/ACM Transactions on Networking (TON), volume 15, pages 92–122, 02 2005.
Cristina Bazgan, André Nichterlein, and Rolf Niedermeier. A refined complexity analysis of finding the most vital edges for undirected shortest paths. In Vangelis Th. Paschos and Peter Widmayer, editors, International Conference on Algorithms and Complexity, volume 9079 of LNCS, pages 47–60. Springer, 2015.
Ryan Beckett, Ratul Mahajan, Todd Millstein, Jitendra Padhye, and David Walker. Don’t mind the gap: Bridging network-wide objectives and device-level configurations. In Proceedings of the 2016 ACM SIGCOMM Conference, pages 328–341, 2016.
Y. Bi, C. W. Tan, and A. Tang. Network utility maximization with path cardinality constraints,. In Proceedings of the 35th Annual IEEE International Conference on Computer Communications (IEEE INFOCOM 2016), 2016.
Martin Nyx Brain, James H. 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’17), volume 1974 of CEUR, pages 1–15. CEUR-WS.org, 2017.
Zhiruo Cao, Zheng Wang, and Ellen Zegura. Performance of hashing-based schemes for internet load balancing. In Proceedings of IEEE INFOCOM 2000., volume 1, pages 332–341. IEEE, 2000.
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–54, July 2020.
Charles E. Leiserson. Fat-trees: Universal networks for hardware-efficient supercomputing. volume 34, pages 892–901, 1985.
M. Chiesa, G. Kindler, and M. Schapira. Traffic engineering with equal-cost-multipath: An algorithmic perspective,. In IEEE/ACM Transactions on Networking, vol. 25, no. 2, pp. 779-792, 2017.
Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64(1):2 – 22, 1985.
Eliezer Dekel, David Nassimi, and Sartaj Sahni. Parallel matrix and graph algorithms. SIAM Journal on Computing, 10(4):657–675, 1981.
Camil Demetrescu, Mikkel Thorup, Rezaul Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput., 37:1299–1318, 01 2008.
Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. 19(2):248–264, 1972.
Ahmed El-Hassany, Petar Tsankov, Laurent Vanbever, and Martin Vechev. Network-wide configuration synthesis. In International Conference on Computer Aided Verification, pages 261–281. Springer, 2017.
Bernard Fortz. Internet traffic engineering by optimizing OSPF weights. In in Proc. IEEE INFOCOM, pages 519–528, 2000.
Bernard Fortz, Jennifer Rexford, and Mikkel Thorup. Traffic engineering with traditional IP routing protocols. IEEE Comm. Magazine, 40(10):118–124, 2002.
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–767, 2002.
Bernard Fortz and Mikkel Thorup. Increasing internet capacity using local search. Computational Optimization and Applications, 29(1):13–48, 2004.
Nate Foster, Dexter Kozen, Konstantinos Mamouras, Mark Reitblatt, and Alexandra Silva. Probabilistic NetKAT. In Peter Thiemann, editor, Programming Languages and Systems (ESOP’16), volume 9632 of LNCS, pages 282–309. Springer, 2016.
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–44, 2005.
Albert Greenberg, James R Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A 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–62, 2009.
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.
Christian Hopps et al. Analysis of an equal-cost multi-path algorithm. Technical report, RFC 2992, November, 2000.
Jesper Stenbjerg Jensen, Troels Beck Krøgh, Jonas Sand Madsen, Stefan Schmid, Jiří Srba, and Marc Tom 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–227, 2018.
P.G. Jensen, D. Kristiansen, S. Schmid, M.K. Schou, B.C. Schrenk, and J. Srba. 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’20), pages 474–481. ACM, 2020.
Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of ACM, 24(1):1–13, 1977.
Simon Knight, Hung Nguyen, Nickolas Falkner, Rhys Bowden, and Matthew Roughan. The internet topology Zoo. Selected Areas in Communications, IEEE Journal on, 29:1765 – 1775, 11 2011.
Kim G. 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.
John Moy et al. OSPF version 2. 1998.
Sebastian Orlowski and Michal Pioro. Complexity of column generation in network design with path-based survivability mechanism. Networks, 59:132 – 147, 01 2012.
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’17), pages 699–718, 2017.
Christos M. Papadimitriou. Computational complexity. Addison-Wesley, Reading, Massachusetts, 1994.
J. S. Provan and D. R. Shier. A paradigm for listing (s, t)-cuts in graphs. Algorithmica, 15(4):351–372, apr 1996.
V. Ramachandran. The complexity of minimum cut and maximum flow problems in an acyclic network. 17(4):387–392, 1987.
Baruch Schieber, Amotz Bar-Noy, and Samir Khuller. The complexity of finding most vital arcs and nodes. Technical report, USA, 1995.
S. Schmid, N. Schnepf, and J. Srba. Reproducibility Package for TACAS’21 Paper Resilient Capacity-Aware Routing, January 2021. https://doi.org/10.5281/zenodo.4421365.
S. Schmid and J. Srba. Polynomial-time what-if analysis for prefix-manipulating MPLS networks. In Proc. IEEE INFOCOM, pages 1799–1807. IEEE, 2018.
Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., USA, 1986.
A. Valadarsky, G. Shahaf, M. Dinitz, and M. Schapira. Xpander: Towards optimal-performance datacenters. In CoNEXT, pages 205–219. ACM, 2016.
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’16, pages 811–830. Springer, 2016.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2021 The Author(s)
About this paper
Cite this paper
Schmid, S., Schnepf, N., Srba, J. (2021). Resilient Capacity-Aware Routing. In: Groote, J.F., Larsen, K.G. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2021. Lecture Notes in Computer Science(), vol 12651. Springer, Cham. https://doi.org/10.1007/978-3-030-72016-2_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-72016-2_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-72015-5
Online ISBN: 978-3-030-72016-2
eBook Packages: Computer ScienceComputer Science (R0)