Network survivability—the ability to maintain operation when one or a few network components fail—is indispensable for present-day networks. In this paper, we characterize three main components in establishing network survivability for an existing network, namely, (1) determining network connectivity, (2) augmenting the network, and (3) finding disjoint paths. We present a concise overview of network survivability algorithms, where we focus on presenting a few polynomial-time algorithms that could be implemented by practitioners and give references to more involved algorithms. 1. Introduction Given the present-day importance of communications systems and infrastructures in general, networks should be designed and operated in such a way that failures can be mitigated. Network nodes and/or links might for instance fail due to malicious attacks, natural disasters, unintentional cable cuts, planned maintenance, equipment malfunctioning, and so forth. Resilient, fault tolerant, survivable, reliable, robust, and dependable, are different terms that have been used by the networking community to capture the ability of a communications system to maintain operation when confronted with network failures. Unfortunately, the terminology has overlapping meanings or contains ambiguities, as pointed out by Al-Kuwaiti et al. [1]. In this paper, we will use the term survivable networks to refer to networks that, when a component fails, may “survive” by finding alternative paths that circumvent the failed component. Three ingredients are needed to reach survivability.(1) Network connectivity, that is, the network should be well connected (connectivity properties are discussed in Section 1.1).(2) Network augmentation, that is, new links may need to be added to increase the connectivity of a network.(3) Path protection, that is, a procedure to find alternative paths in case of failures. These three ingredients will be explained in the following sections. 1.1. Network Connectivity A network is often represented as a graph , where is the set of nodes (which for instance represent routers) and is the set of links (which for instance represent optical fiber lines or radio channels). Links may be characterized by weights representing for instance their capacity, delay, length, cost, and/or failure probability. A graph is said to be connected if there exists a path between each pair of nodes in the graph, else the graph is said to be disconnected. In the context of survivability, the notion of connectivity may be further specified as -connectivity, where at least disjoint paths
References
[1]
M. Al-Kuwaiti, N. Kyriakopoulos, and S. Hussein, “A comparative analysis of network dependability, fault-tolerance, reliability, security, and survivability,” IEEE Communications Surveys and Tutorials, vol. 11, no. 2, pp. 106–124, 2009.
[2]
K. Menger, “Zur allgemeinen kurventheorie,” Fundamenta Mathematicae, vol. 10, pp. 96–115, 1927.
[3]
M. Fiedler, “Algebraic connectivity of graphs,” Czechoslovak Mathematical Journal, vol. 23, pp. 298–305, 1973.
[4]
P. Van Mieghem, Graph Spectra for Complex Networks, Cambridge University Press, 2011.
[5]
N. M. M. de Abreu, “Old and new results on algebraic connectivity of graphs,” Linear Algebra and Its Applications, vol. 423, no. 1, pp. 53–73, 2007.
[6]
K. Lee, E. Modiano, and H. W. Lee, “Cross-layer survivability in WDM-based networks,” IEEE/ACM Transactions on Networking, vol. 19, no. 4, pp. 1000–1013, 2011.
[7]
K. Lee, H. W. Lee, and E. Modiano, “Reliability in layered networks with random link failures,” IEEE/ACM Transactions on Networking, vol. 19, no. 6, pp. 1835–1848, 2011.
[8]
W. Zou, M. Janic, R. Kooij, and F. A. Kuipers, “On the availability of networks,” in Proceedings of the BroadBand Europe, Antwerp, Belgium, December 2007.
[9]
C. J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, New York, NY, USA, 1987.
[10]
P. Van Mieghem, H. Wang, X. Ge, S. Tang, and F. A. Kuipers, “Influence of assortativity and degree-preserving rewiring on the spectra of networks,” European Physical Journal B, vol. 76, no. 4, pp. 643–652, 2010.
[11]
D. Mosk-Aoyama, “Maximum algebraic connectivity augmentation is NP-hard,” Operations Research Letters, vol. 36, no. 6, pp. 677–679, 2008.
[12]
M. Yanakakis, “Computing the minimum fill-in is NP-complete,” SIAM Journal on Algebraic and Discrete Methods, vol. 2, no. 1, pp. 77–79, 1981.
[13]
P. Pan, G. Swallow, and A. Atlas, “Fast reroute extensions to RSVP-TE for LSP tunnels,” IETF Request for Comments RFC 4090, 2005.
[14]
M. Shand and S. Bryant, “IP fast reroute framework,” IETF Request for Comments RFC 5714, 2010.
[15]
R. Banner and A. Orda, “Designing low-capacity backup networks for fast restoration,” in Proceedings of the IEEE INFOCOM, San Diego, Calif, USA, March 2010.
[16]
G. Ellinas, A. G. Hailemariam, and T. E. Stern, “Protection cycles in mesh WDM networks,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 10, pp. 1924–1937, 2000.
[17]
R. Asthana, Y. N. Singh, and W. D. Grover, “p-cycles: an overview,” IEEE Communications Surveys and Tutorials, vol. 12, no. 1, pp. 97–111, 2010.
[18]
M. Médard, S. G. Finn, R. A. Barry, and R. G. Gallager, “Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs,” IEEE/ACM Transactions on Networking, vol. 7, no. 5, pp. 641–652, 1999.
[19]
K. P. Gummadi, M. J. Pradeep, and C. S. R. Murthy, “An efficient primary-segmented backup scheme for dependable real-time communication in multihop networks,” IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 81–94, 2003.
[20]
C. H. Papadimitriou and M. Yannakakis, “Optimization, approximation, and complexity classes,” Journal of Computer and System Sciences, vol. 43, no. 3, pp. 425–440, 1991.
[21]
B. Mohar, “Isoperimetric numbers of graphs,” Journal of Combinatorial Theory, Series B, vol. 47, no. 3, pp. 274–291, 1989.
[22]
D. W. Matula and F. Shahrokhi, “Sparsest cuts and bottlenecks in graphs,” Discrete Applied Mathematics, vol. 27, no. 1-2, pp. 113–123, 1990.
[23]
T. N. Dinh, Y. Xuan, M. T. Thai, E. K. Park, and T. Znati, “On approximation of new optimization methods for assessing network vulnerability,” in Proceedings of the IEEE INFOCOM, San Diego, Calif, USA, March 2010.
[24]
D. R. Fulkerson and G. B. Dantzig, “Computation of maximal flows in networks,” Naval Research Logistics, vol. 2, no. 4, pp. 277–283, 1955.
[25]
P. Elias, A. Feinstein, and C. E. Shannon, “A note on the maximum flow through a network,” IRE Transactions on Information Theory, vol. 2, pp. 117–119, 1956.
[26]
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Upper Saddle River, NJ, USA, 1st edition, 1993.
[27]
Y. Dinitz, “Dinitz' algorithm: the original version and Even's version,” in Essays in Memory of Shimon Even, O. Goldreich, A. L. Rosenberg, and A. L. Selman, Eds., vol. 3895 of Lecture Notes in Computer Science, pp. 218–240, Springer, Berlin, Germany, 2006.
[28]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, Cambridge, Mass, USA, 3rd edition, 2009.
[29]
S. Even and R. E. Tarjan, “Network flow and testing graph connectivity,” SIAM Journal on Computing, vol. 4, pp. 507–518, 1975.
[30]
G. B. Dantzig, “Application of the simplex method to a transportation problem,” in Activity Analysis of Production and Allocation, pp. 359–373, John Wiley & Sons, New York, NY, USA, 1951.
[31]
L. R. Ford and D. R. Fulkerson, “Maximal flow through a network,” Canadian Journal of Mathematics, vol. 8, pp. 399–404, 1956.
[32]
A. V. Karzanov, “Determining the maximal flow in a network by the method of preflows,” Soviet Mathematics-Doklady, no. 15, pp. 434–437, 1974.
[33]
R. E. Tarjan, “A simple version of Karzanov's blocking flow algorithm,” Operations Research Letters, vol. 2, no. 6, pp. 265–268, 1984.
[34]
Z. Galil and A. Naamad, “An O(EV log2V) algorithm for the maximal flow problem,” Journal of Computer and System Sciences, vol. 21, pp. 203–217, 1980.
[35]
Y. Shiloach and U. Vishkin, “An O(n2log n) parallel max-flow algorithm,” Journal of Algorithms, vol. 3, no. 2, pp. 128–146, 1982.
[36]
D. D. Sleator and R. E. Tarjan, “A data structure for dynamic trees,” Journal of Computer and System Sciences, vol. 26, no. 3, 1983.
[37]
A. V. Goldberg and R. E. Tarjan, “A new approach to the maximum-flow problem,” Journal of the ACM, vol. 35, no. 4, pp. 921–940, 1988.
[38]
R. K. Ahuja, J. B. Orlin, and R. E. Tarjan, “Improved time bounds for the maximum flow problem,” SIAM Journal on Computing, vol. 18, no. 5, pp. 939–954, 1989.
[39]
J. Cheriyan and T. Hagerup, “Randomized maximum-flow algorithm,” SIAM Journal on Computing, vol. 24, no. 2, pp. 203–226, 1995.
[40]
N. Alon, “Generating pseudo-random permutations and maximum flow algorithms,” Information Processing Letters, vol. 35, no. 4, pp. 201–204, 1990.
[41]
A. V. Goldberg and S. Rao, “Beyond the flow decomposition barrier,” Journal of the ACM, vol. 45, no. 5, pp. 783–797, 1998.
[42]
P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S. H. Teng, “Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs,” in Proceedings of The 43rd ACM Symposium on Theory of Computing, STOC' 11, pp. 273–281, San Jose, CA, USA, June 2011.
[43]
D. W. Matula, “Determining edge connectivity in ,” in Proceedings of the 28th Symposium on Foundations of Computer Science (FOCS '87), pp. 249–251, Los Angeles, Calif, USA, October 1987.
[44]
Y. Shiloach, “Edge-disjoint branching in directed multigraphs,” Information Processing Letters, vol. 8, no. 1, pp. 24–27, 1979.
[45]
Y. Mansour and B. Schieber, “Finding the edge connectivity of directed graphs,” Journal of Algorithms, vol. 10, no. 1, pp. 76–85, 1989.
[46]
G. B. Dantzig and D. R. Fulkerson, “On the max-flow min-cut theorem of networks,” in Linear Inequalities and Related Systems, Annals of Mathematics Studies, Study 38, pp. 215–221, Princeton University Press, Princeton, NJ, USA, 1956.
[47]
S. Even, Graph Algorithms, Computer Science Press, 1979.
[48]
M. R. Henzinger, S. Rao, and H. N. Gabow, “Computing vertex connectivity: new bounds from old techniques,” Journal of Algorithms, vol. 34, no. 2, pp. 222–250, 2000.
[49]
H. N. Gabow, “Using expander graphs to find vertex connectivity,” Journal of the ACM, vol. 53, no. 5, pp. 800–844, 2006.
[50]
Y. Yoshida and H. Ito, “Property testing on k-vertex-connectivity of graphs,” Algorithmica, vol. 62, no. 3-4, pp. 701–712, 2012.
[51]
P. Van Mieghem, D. Stevanovi？, F. A. Kuipers et al., “Decreasing the spectral radius of a graph by link removals,” Physical Review E, vol. 84, no. 1, 2011.
[52]
A. Natanzon, R. Shamir, and R. Sharan, “Complexity classification of some edge modification problems,” Discrete Applied Mathematics, vol. 113, no. 1, pp. 109–128, 2001.
[53]
G. Frederickson and J. JáJá, “Approximation algorithms for several graph augmentation problems,” SIAM Journal on Computing, vol. 10, no. 2, pp. 270–283, 1981.
[54]
K. P. Eswaran and R. E. Tarjan, “Augmentation problems,” SIAM Journal on Computing, vol. 5, no. 4, pp. 653–665, 1976.
[55]
J. Jensen and T. Jordán, “Edge-connectivity augmentation preserving simplicity,” in Proceedings of the 9th Annual ACM/SIAM Symposium On Discrete Algorithms (SODA '97), pp. 306–315, 1997.
[56]
S. Raghavan, “A note on Eswaran and Tarjan's algorithm for the strong connectivity augmentation problem,” in The Next Wave in Computing, Optimization, and Decision Technologies, vol. 29 of Operations Research/Computer Science Interfaces Series, pp. 19–26, Springer, 2005.
[57]
R. E. Tarjan, “A note on finding the bridges of a graph,” Information Processing Letters, vol. 2, no. 6, pp. 160–161, 1974.
[58]
E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, “On the structure of the system of minimum edge cuts of a graph,” in Issledovaniya po Diskretnoi Optimizatsii, A. A. Fridman, Ed., pp. 290–306, Nauka, Moscow, Russia, 1976.
[59]
A. V. Karzanov and E. A. Timofeev, “Efficient algorithm for finding all minimal edge cuts of a nonoriented graph,” Cybernetics and Systems Analysis, vol. 22, no. 2, pp. 156–162, 1986.
[60]
H. Nagamochi and T. Kameda, “Canonical cactus representation for minimum cuts,” Japan Journal of Industrial and Applied Mathematics, vol. 11, no. 3, pp. 343–361, 1994.
[61]
R. E. Gomory and T. C. Hu, “Multi-terminal network flows,” Journal of the Society for Industrial and Applied Mathematics, vol. 9, no. 4, pp. 551–570, 1961.
[62]
D. Gusfield and D. Naor, “Extracting maximal information about sets of minimum cuts,” Algorithmica, vol. 10, no. 1, pp. 64–89, 1993.
[63]
L. Fleischer, “Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time,” Journal of Algorithms, vol. 33, no. 1, pp. 51–72, 1999.
[64]
H. Nagamochi, “Graph algorithms for network connectivity problems,” Journal of the Operations Research Society of Japan, vol. 4, no. 4, pp. 199–223, 2004.
[65]
D. Naor, D. Gusfield, and C. Martel, “A fast algorithm for optimally increasing the edge connectivity,” SIAM Journal on Computing, vol. 26, no. 4, pp. 1139–1165, 1997.
[66]
E. Cheng, “Successive edge-connectivity augmentation problems,” Mathematical Programming B, vol. 84, no. 3, pp. 577–593, 1999.
[67]
R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, vol. 1, no. 2, pp. 146–160, 1972.
[68]
W. Mader, “A reduction method for edge-connectivity in graphs,” Annals of Discrete Mathematics, vol. 3, pp. 145–164, 1978.
[69]
A. Frank, “On a theorem of Mader,” Discrete Mathematics, vol. 101, no. 1–3, pp. 49–57, 1992.
[70]
V. D. Podderyugin, “An algorithm for determining edge-connectivity of a graph,” in Proceedings of the Seminar on Combinatorial Mathematics, Moscow, Russia, 1971, Doklady Akademii Nauk SSSR, Scientiffic Council on the Complex Problem “Cybernetics”, pp. 136–141, 1973.
[71]
H. Nagamochi and T. Ibaraki, “Computing edge-connectivity in multigraphs and capacitated graphs,” SIAM Journal on Discrete Mathematics, vol. 5, no. 1, pp. 54–66, 1992.
[72]
Z. Galil and G.F. Italiano, “Reducing edge connectivity to vertex connectivity,” ACM SIGACT News, vol. 22, no. 1, pp. 57–61, 1991.
[73]
H. N. Gabow, “A matroid approach to finding edge-connectivity and packing arborescences,” Journal of Computer and System Sciences, vol. 50, no. 2, pp. 259–273, 1995.
[74]
D. R. Karger, “Minimum cuts in near-linear time,” Journal of the ACM, vol. 47, no. 1, pp. 46–76, 2000.
[75]
G. Cai and Y. Sun, “The minimum augmentation of any graph to a K-edge-connected graph,” Networks, vol. 19, no. 1, pp. 151–172, 1989.
[76]
T. Watanabe and A. Nakamura, “Edge-connectivity augmentation problems,” Journal of Computer and System Sciences, vol. 35, no. 1, pp. 96–144, 1987.
[77]
A. Frank, “Augmenting graphs to meet edge-connectivity requirements,” SIAM Journal on Discrete Mathematics, vol. 5, no. 1, pp. 25–53, 1992.
[78]
H. N. Gabow, “Applications of a poset representation to edge connectivity and graph rigidity,” in Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS '91), pp. 812–821, October 1991.
[79]
A. A. Benczúr, “Augmenting undirected connectivity in RNC and in randomized ？(n3) time,” in Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC '94), pp. 658–667, New York, NY, USA, May 1994.
[80]
H. Nagamochi and T. Ibaraki, “Deterministic ？(nm) time edge-splitting in undirected graphs,” Journal of Combinatorial Optimization, vol. 1, no. 1, pp. 5–46, 1997.
[81]
A. A. Benczúr and D. R. Karger, “Augmenting undirected edge connectivity in ？(n2) time,” Journal of Algorithms, vol. 37, no. 1, pp. 2–36, 2000.
[82]
H. Nagamochi and T. Ibaraki, “Graph connectivity and its augmentation: applications of MA orderings,” Discrete Applied Mathematics, vol. 123, pp. 447–472, 2002.
[83]
Z. Nutov, “Approximating connectivity augmentation problems,” ACM Transactions on Algorithms, vol. 6, no. 1, article 5, 2009.
[84]
J. Plesník, “Minimum block containing a given graph,” Archiv der Mathematik, vol. 27, no. 1, pp. 668–672, 1976.
[85]
S. Khuller and R. Thurimella, “Approximation algorithms for graph augmentation,” Journal of Algorithms, vol. 14, no. 2, pp. 214–225, 1993.
[86]
S. Taoka, T. Watanabe, and T. Mashima, “Maximum weight matching-based algorithms for k-edge-connectivity augmentation of a graph,” in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS '05), pp. 2231–2234, May 2005.
[87]
A. Rosenthal and A. Goldner, “Smallest augmentation to biconnect a graph,” SIAM Journal on Computing, vol. 6, no. 1, pp. 55–66, 1977.
[88]
T. S. Hsu and V. Ramachandran, “Finding a smallest augmentation to biconnect a graph,” SIAM Journal on Computing, vol. 22, no. 5, pp. 889–912, 1993.
[89]
T. Watanabe and A. Nakamura, “A minimum 3-connectivity augmentation of a graph,” Journal of Computer and System Sciences, vol. 46, no. 1, pp. 91–128, 1993.
[90]
T. Jordán, “On the optimal vertex-connectivity augmentation,” Journal of Combinatorial Theory B, vol. 63, no. 1, pp. 8–20, 1995.
[91]
T. Hsu, “On four-connecting a triconnected graph,” in Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS '92), pp. 70–79, IEEE Computer Society, Washington, DC, USA, October 1992.
[92]
T. Jordán, “A note on the vertex-connectivity augmentation problem,” Journal of Combinatorial Theory B, vol. 71, no. 2, pp. 294–301, 1997.
[93]
B. Jackson and T. Jordán, “A near optimal algorithm for vertex-connectivity augmentation,” in Proceedings of the 11th International Conference on Algorithms and Computation (ISAAC '00), pp. 312–325, Springer, London, UK, December 2000.
[94]
B. Jackson and T. Jordán, “Independence free graphs and vertex connectivity augmentation,” Journal of Combinatorial Theory B, vol. 94, no. 1, pp. 31–77, 2005.
[95]
G. Kortsarz and Z. Nutov, “Approximating minimum-cost connectivity problems,” in Handbook of Approximation Algorithms and Metaheuristics, Chapter 58, Chapman & Hall/CRC, 2007.
[96]
G. Liberman and Z. Nutov, “On shredders and vertex connectivity augmentation,” Journal of Discrete Algorithms, vol. 5, no. 1, pp. 91–101, 2007.
[97]
J. Cheriyan and R. Thurimella, “Fast algorithms for k-shredders and k-node connectivity augmentation,” Journal of Algorithms, vol. 33, no. 1, pp. 15–50, 1999.
[98]
L. A. Végh, “Augmenting undirected node-connectivity by one,” SIAM Journal on Discrete Mathematics, vol. 25, no. 2, pp. 695–718, 2011.
[99]
A. Frank and T. Jordán, “Minimal edge-coverings of pairs of sets,” Journal of Combinatorial Theory, Series B, vol. 65, no. 1, pp. 73–110, 1995.
[100]
A. Frank and L. A. Végh, “An algorithm to increase the node-connectivity of a digraph by one,” Discrete Optimization, vol. 5, no. 4, pp. 677–684, 2008.
[101]
A. Frank, “Connectivity augmentation problems in network design,” in Mathematical Programming: State of the Art 1994, J. R. Bridge and K. G. Murty, Eds., University of Michigan, Ann Arbor, Mich, USA, 1994.
[102]
M. Gr？tschel, C. L. Monma, and M. Stoer, “Design of survivable networks,” in Handbooks in Operations Research and Management Science, vol. 7, pp. 617–672, 1995.
[103]
M. Penn and H. Shasha-Krupnik, “Improved approximation algorithms for weighted 2- and 3-vertex connectivity augmentation problems,” Journal of Algorithms, vol. 22, no. 1, pp. 187–196, 1997.
[104]
S. Khuller, “Approximation algorithms for finding highly connected subgraphs,” in Approximation Algorithms for NP-Hard Problems, D. S. Hochbaum, Ed., pp. 236–265, PWS Publishing, Boston, Mass, USA, 1997.
[105]
S. Khuller and B. Raghavachari, “Improved approximation algorithms for uniform connectivity problems,” Journal of Algorithms, vol. 21, no. 2, pp. 434–450, 1996.
[106]
R. Ravi and D. P. Williamson, “An approximation algorithm for minimum-cost vertex-connectivity problems,” Algorithmica, vol. 18, no. 1, pp. 21–43, 1997.
[107]
G. N. Frederickson and J. JáJá, “On the relationship between the biconnectivity augmentation and travelling salesman problems,” Theoretical Computer Science, vol. 19, no. 2, pp. 189–201, 1982.
[108]
C.-L. Li, S. T. Mccormick, and D. Simchi-Levi, “The complexity of finding two disjoint paths with min-max objective function,” Discrete Applied Mathematics, vol. 26, no. 1, pp. 105–115, 1990.
[109]
B. Yang, S. Q. Zheng, and S. Katukam, “Finding two disjoint paths in a network with min-min objective function,” in Proceedings of the 15th IASTED International Conference on Parallel and Distributed Computing and Systems, November 2003.
[110]
A. Itai, Y. Perl, and Y. Shiloach, “The complexity of finding maximum disjoint paths with length constraints,” Networks, vol. 12, no. 3, pp. 277–286, 1982.
[111]
A. Bley, “On the complexity of vertex-disjoint length-restricted path problems,” Computational Complexity, vol. 12, no. 3-4, pp. 131–149, 2003.
[112]
C.-L. Li, S. T. Mccormick, and D. Simchi-Levi, “Finding disjoint paths with different path costs: complexity and algorithms,” Networks, vol. 22, no. 7, pp. 653–667, 1992.
[113]
D. Xu, Y. Chen, Y. Xiong, C. Qiao, and X. He, “On finding disjoint paths in single and dual link cost networks,” in Proceedings of the IEEE INFOCOM, March 2004.
[114]
Q. She, X. Huang, and J. P. Jue, “How reliable can two-path protection be?” IEEE/ACM Transactions on Networking, vol. 18, no. 3, pp. 922–933, 2010.
[115]
B. H. Shen, B. Hao, and A. Sen, “On multipath routing using widest pair of disjoint paths,” in Proceedings of the High Perfomance Switching and Routing (HPSR '04), pp. 134–140, April 2004.
[116]
A. A. Beshir and F. A. Kuipers, “Variants of the min-sum link-disjoint paths problem,” in Proceedings of the 16th Annual IEEE Symposium on Communications and Vehicular Technology (IEEE SCVT '09), IEEE/SCVT, Louvain-la-Neuve, Belgium, November 2009.
[117]
R. Bhatia, M. Kodialam, and T. V. Lakshman, “Finding disjoint paths with related path costs,” Journal of Combinatorial Optimization, vol. 12, no. 1-2, pp. 83–96, 2006.
[118]
H. D. Sherali, K. Ozbay, and S. Subramanian, “The time-dependent shortest pair of disjoint paths problem: complexity, models, and algorithms,” Networks, vol. 31, no. 4, pp. 259–272, 1998.
[119]
J. W. Suurballe, “Disjoint paths in a network,” Networks, vol. 4, no. 2, pp. 125–145, 1974.
[120]
J. W. Suurballe and R. E. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol. 14, pp. 325–336, 1984.
[121]
N. Taft-Plotkin, B. Bellur, and R. Ogier, “Quality-of-service routing using maximally disjoint paths,” in Proceedings of the 7th International Workshop on Quality of Service (IWQoS), pp. 119–128, London, UK, May 1999.
[122]
R. G. Ogier, V. Rutenburg, and N. Shacham, “Distributed algorithms for computing shortest pairs of disjoint paths,” IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 443–455, 1993.
[123]
D. Sidhu, R. Nair, and S. Abdallah, “Finding disjoint paths in networks,” ACM SIGCOMM Computer Communication Review, vol. 21, no. 4, pp. 43–51, 1991.
[124]
J. Roskind and R. E. Tarjan, “Note on finding minimum-cost edge-disjoint spanning trees,” Mathematics of Operations Research, vol. 10, no. 4, pp. 701–708, 1985.
[125]
G. Xue, L. Chen, and K. Thulasiraman, “Quality-of-service and quality-of-protection issues in preplanned recovery schemes using redundant trees,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 8, pp. 1332–1345, 2003.
[126]
W. Zhang, G. Xue, J. Tang, and K. Thulasiraman, “Faster algorithms for construction of recovery trees enhancing QoP and QoS,” IEEE/ACM Transactions on Networking, vol. 16, no. 3, pp. 642–655, 2008.
[127]
P. Cholda, A. Mykkeltveit, B. E. Helvik, O. J. Wittner, and A. Jajszczyk, “A survey of resilience differentiation frameworks in communication networks,” IEEE Communications Surveys & Tutorials, vol. 9, no. 4, pp. 32–55, 2007.
[128]
S. Ramasubramanian, M. Harkara, and M. Krunz, “Linear time distributed construction of colored trees for disjoint multipath routing,” Computer Networks, vol. 51, no. 10, pp. 2854–2866, 2007.
[129]
Y. Guo, F. A. Kuipers, and P. Van Mieghem, “A link-disjoint paths algorithm for reliable QoS routing,” International Journal of Communication Systems, vol. 16, no. 9, pp. 779–798, 2003.
[130]
R. Banner and A. Orda, “The power of tuning: a novel approach for the efficient design of survivable networks,” IEEE/ACM Transactions on Networking, vol. 15, no. 4, pp. 737–749, 2007.
[131]
O. Gerstel and G. Sasaki, “Quality of protection (QoP): a quantitative unifying paradigm to protection service grades,” Optical Networks Magazine, vol. 3, no. 3, pp. 40–49, 2002.
[132]
A. V. Goldberg and R. E. Tarjan, “Finding minimum-cost circulations by canceling negative cycles,” Journal of the ACM, vol. 36, no. 4, pp. 873–886, 1989.
[133]
H. Luo, L. Li, and H. Yu, “Routing connections with differentiated reliability requirements in WDM mesh networks,” IEEE/ACM Transactions on Networking, vol. 17, no. 1, pp. 253–266, 2009.
[134]
F. A. Kuipers, A. Orda, D. Raz, and P. Van Mieghem, “A comparison of exact and -approximation algorithms for constrained routing,” in Proceedings of the 5th IFIP Networking Conference, Coimbra, Portugal, May 2006.
[135]
A. Chakrabarti and G. Manimaran, “Reliability constrained routing in QoS networks,” IEEE/ACM Transactions on Networking, vol. 13, no. 3, pp. 662–675, 2005.
[136]
D. Coudert, P. Datta, S. Perennes, H. Rivano, and M. E. Voge, “Shared risk resource group: complexity and approximability issues,” Parallel Processing Letters, vol. 17, no. 2, pp. 169–184, 2007.
[137]
J. Q. Hu, “Diverse routing in optical mesh networks,” IEEE Transactions on Communications, vol. 51, no. 3, pp. 489–494, 2003.
[138]
R. Bhandari, Survivable Networks: Algorithms for Diverse Routing, Kluwer Academic Publishers, New York, NY, USA, 1999.
[139]
P. Datta and A. K. Somani, “Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures,” Computer Networks, vol. 52, no. 12, pp. 2381–2394, 2008.
[140]
X. Luo and B. Wang, “Diverse routing in WDM optical networks with shared risk link group (SRLG) failures,” in Proceedings of the 5th IEE International Workshop on Design of Reliable Communication Networks (DRCN '05), Island of Ischia, Naples, Italy, October 2005.
[141]
H. W. Lee, E. Modiano, and K. Lee, “Diverse routing in networks with probabilistic failures,” IEEE/ACM Transactions on Networking, vol. 18, no. 6, pp. 1895–1907, 2010.
[142]
W. D. Grover, Mesh-Based Survivable Transport Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking, Prentice Hall PTR, London, UK, 2003.
[143]
D. Xu, Y. Xiong, C. Qiao, and G. Li, “Trap avoidance and protection schemes in networks with shared risk link groups,” Journal of Lightwave Technology, vol. 21, no. 11, pp. 2683–2693, 2003.
[144]
H. Zang, C. S. Ou, and B. Mukherjee, “Path-protection routing and wavelength assignment (RWA) in WDM mesh networks under duct-layer constraints,” IEEE/ACM Transactions on Networking, vol. 11, no. 2, pp. 248–258, 2003.
[145]
A. Sen, S. Murthy, and S. Banerjee, “Region-based connectivity—a new paradigm for design of fault-tolerant networks,” in Proceedings of the 15st International Conference on High Performance Switching and Routing (HPSR '09), Paris, France, June 2009.
[146]
P. K. Agarwal, A. Efrat, S. Ganjugunte, D. Hay, S. Sankararaman, and G. Zussman, “The resilience of WDM networks to probabilistic geographical failures,” in Proceedings of the IEEE INFOCOM, pp. 1521–1529, Shanghai, China, April 2011.
[147]
S. Neumayer, A. Efrat, and E. Modiano, “Geographic max-flow and mincut under a circular disk failure model,” in Proceedings of the 31st Annual IEEE International Conference on Computer Communications (INFOCOM '12), March 2012.
[148]
S. Trajanovski, F. A. Kuipers, P. Van Mieghem, A. Ili？, and J. Crowcroft, “Critical regions and region-disjoint paths in a network”.
[149]
A. A. Beshir, F. A. Kuipers, P. Van Mieghem, and A. Orda, “On-line survivable routing in WDM networks,” in Proceedings of the 21st International Teletraffic Congress (ITC '21), Paris, France, September 2009.
[150]
A. A. Beshir, F. A. Kuipers, A. Orda, and P. Van Mieghem, “Survivable impairment-aware traffic grooming in WDM rings,” in Proceedings of the 23rd International Teletraffic Congress, San Francisco, Calif, USA, September 2011.
[151]
A. A. Beshir, F. A. Kuipers, A. Orda, and P. Van Mieghem, “Survivable routing and regenerator placement in optical networks,” in Proceedings of the 4th International Workshop on Reliable Networks Design and Modeling (RNDM '12), Petersburg, Russia, October 2012.
[152]
A. A. Beshir, R. Nuijts, R. Malhotra, and F. A. Kuipers, “Survivable impairment-aware traffic grooming,” in Proceedings of the 16th European Conference on Networks and Optical Communications (NOC '11), Northumbria University, Newcastle upon Tyne, UK, July 2011.
