An Overview of Algorithms for Network Survivability
---
paper_title: A comparative analysis of network dependability, fault-tolerance, reliability, security, and survivability

paper_content:

A number of qualitative and quantitative terms are used to describe the performance of what has come to be known as information systems, networks or infrastructures. However, some of these terms either have overlapping meanings or contain ambiguities in their definitions presenting problems to those who attempt a rigorous evaluation of the performance of such systems. The phenomenon arises because the wide range of disciplines covered by the term information technology have developed their own distinct terminologies. This paper presents a systematic approach for determining common and complementary characteristics of five widely-used concepts, dependability, fault-tolerance, reliability, security, and survivability. The approach consists of comparing definitions, attributes, and evaluation measures for each of the five concepts and developing corresponding relations. Removing redundancies and clarifying ambiguities will help the mapping of broad user-specified requirements into objective performance parameters for analyzing and designing information infrastructures.
---
paper_title: Old and new results on algebraic connectivity of graphs

paper_content:

This paper is a survey of the second smallest eigenvalue of the Laplacian of a graph G, best-known as the algebraic connectivity of G, denoted a(G). Emphasis is given on classifications of bounds to algebraic connectivity as a function of other graph invariants, as well as the applications of Fiedler vectors (eigenvectors related to a(G)) on trees, on hard problems in graphs and also on the combinatorial optimization problems. Besides, limit points to a(G) and characterizations of extremal graphs to a(G) are described, especially those for which the algebraic connectivity is equal to the vertex connectivity.
---
paper_title: Reliability in Layered Networks with Random Link Failures

paper_content:

We consider network reliability in layered networks where the lower layer experiences random link failures. In layered networks, each failure at the lower layer may lead to multiple failures at the upper layer. We generalize the classical polynomial expression for network reliability to the multi-layer setting. Using random sampling techniques, we develop polynomial time approximation algorithms for the failure polynomial. Our approach gives an approximate expression for reliability as a function of the link failure probability, eliminating the need to resample for different values of the failure probability. Furthermore, it gives insight on how the routings of the logical topology on the physical topology impact network reliability. We show that maximizing the min cut of the (layered) network maximizes reliability in the low failure probability regime. Based on this observation, we develop algorithms for routing the logical topology to maximize reliability.
---
paper_title: Cross-Layer Survivability in WDM-Based Networks

paper_content:

In layered networks, a single failure at a lower layer may cause multiple failures in the upper layers. As a result, traditional schemes that protect against single failures may not be effective in multilayer networks. In this paper, we introduce the problem of maximizing the connectivity of layered networks. We show that connectivity metrics in layered networks have significantly different meaning than their single-layer counterparts. Results that are fundamental to survivable single-layer network design, such as the Max-Flow Min-Cut Theorem, are no longer applicable to the layered setting. We propose new metrics to measure connectivity in layered networks and analyze their properties. We use one of the metrics, Min Cross Layer Cut, as the objective for the survivable lightpath routing problem and develop several algorithms to produce lightpath routings with high survivability. This allows the resulting cross-layer architecture to be resilient to failures between layers.
---
paper_title: The Combinatorics of Network Reliability

paper_content:

Preliminaries Exact algorithms The computational complexity of reliability problems Exact algorithms for restricted classes The reliability polynominal Edge-disjoint subgraphs Additive and multiplicative improvements Combining the bounds The k-cycle bound Computational results References Index.
---
paper_title: On the availability of networks

paper_content:

In all networks that provide a service to the consumer, one of the main performance indicators is availability. The consumer, the user of the service, wants to be able to use the service for at least X% of the time. In order to be able to make such guarantees and commit to them in Service Level Agreements, network operators need to know their network availability. In this paper, we discuss how network availability can be algorithmically computed and we derive analytical expressions for several different network topologies. Finally we show how these results can be used to compute availability of real-life networks, such as SURFnet – a high-speed Dutch national network. Introduction Businesses today depend more on network communications than a few years ago. As business applications become more critical to a company’s success, so does the availability of the underlying network. Two main factors determine the availability of the underlying network: A first factor is the availability of the individual network elements. During the lifetime of a network element, it may endure periods in which it is out of service either because of a malfunctioning, maintenance or repair work. If we denote the mean time to failure by MTBF and the mean repair time by MTTR, the availability of a network element (or more formally, the probability that the element is working properly) is defined as MTTR MTBF MTBF A + = and the unavailability as U = 1 A. A second factor is the topology of the network. Obviously, higher redundancy in the network (e.g. more links connecting network switches) will lead to higher availability, but also to higher investment costs. For the traditional telephony service often a five nines (99.999%) availability is guaranteed. Network operators that offer other services need to be able to make similar claims. In order to make such claims, an unambiguous definition of network availability is needed. In this paper we propose a definition based upon connectivity of the network. The remainder of the paper is organized as follows. In the following section we discuss several network availability definitions. The algorithmic computation of network availability is discussed subsequently. Then we determine analytic expressions for a number of simple network topologies. Finally, we apply these results to obtain the availability for the real-world SURFnet network. Network availability definitions We consider a network represented as a graph G(V,E) consisting of a set of nodes V and a set of links E. |V| = N denotes the number of nodes while the number of links is |E| = L. Nodes represent routers or switches and links represent communication links (e.g., optical fibers). Both links and nodes have a certain availability. In our study we assume that the nodes are always available, i.e. only the links can fail. This assumption is based on the fact that node failures occur much less frequent than link failures, which occur e.g. when fibers are unintentionally broken by means of shovels. In addition we assume that failures occur independently. Path availability Let us first examine network availability in its strictest form. Assume that each user has precisely one path over which (s)he can communicate with another user. If this path fails the communication is precluded. Since a path consists of a serial concatenation of nodes and links, its availability is simply computed as the product of the availabilities of the nodes and links that constitute that path. Network availability can then be derived as the minimum path availability over all node pairs. Since all paths are known (or can be computed via a simple shortest paths algorithm), the network availability is easily computed. Let pij denote the availability probability of link (i,j), which connects nodes i and j. To gain the highest possible network availability (defined in its strictest form), the minimum path availability over all node pairs should be maximized. If we assign the weight -log (pij) to each link (i,j) ∈ E, then the same goal is achieved by using the shortest paths (given the new weights) between the sourcedestination (s-d) pairs. The shortest path with the highest weight has the lowest path availability and determines the optimal network availability that can be gained. Unloaded network availability The other extreme case is where communication can take place over all possible paths. This closely resembles routing in the Internet where, in case a failure takes place, routing protocols automatically reconfigure the routing tables to direct traffic over alternative working paths towards their destinations. Network unavailability is in this case determined by the probability that between a particular source-destination pair, no path is available (i.e., the network is disconnected). BroadBand Europe Antwerp, Belgium 3-6 December 2007 ISBN : 9789076546094 Paper Tu3A3 – Zou Page 2 of 6 The maximum probability over all s-d pairs determines the network unavailability and hence also the network availability. Loaded network availability The computation of network availability in the previous subsection is actually too optimistic in practice, since it assumes that when paths fail the alternate paths have enough resources available to handle the traffic of the failed path(s). Since resources are limited, this may not always be the case. If we consider the example in Figure 1, half of the subgraphs are disconnected let us call this unloaded network unavailability. However, the three subgraphs (l1,l2), (l2,l3) and (l1,l3) may also not be able to take over the traffic of the failed link we refer to such case as loaded network unavailability. We will not consider loaded network availability in this paper. Computation of network availability When looking at a network, one could say that links are either available (a) or unavailable (u). By pruning the unavailable links from the graph, we are left with a subgraph which may either be connected or disconnected. In the latter case, for at least one s-d pair, the network is unavailable. By computing the connectivity of all possible subgraphs, one can precisely determine the network (un)availability. We will illustrate this for the three-node network in Figure 1.
---
paper_title: Maximum algebraic connectivity augmentation is NP-hard

paper_content:

The algebraic connectivity of a graph, which is the second-smallest eigenvalue of the Laplacian of the graph, is a measure of connectivity. We show that the problem of adding a specified number of edges to an input graph to maximize the algebraic connectivity of the augmented graph is NP-hard.
---
paper_title: p-Cycles: An overview

paper_content:

One of the most promising techniques of network protection i.e. p-Cycles (pre-planned, preconfigured-cycles) is reviewed in this paper. In this paper we provide a survey of the main work on p-cycles to date. The characteristics of p-cycles and various types of protection provided by them are discussed. Finally, some possible extensions or enhancements of the p-cycle concept are discussed.
---
paper_title: IP Fast Reroute Framework

paper_content:

This document provides a framework for the development of IP fast- ::: reroute mechanisms which provide protection against link or router ::: failure by invoking locally determined repair paths. Unlike MPLS fast- ::: reroute, the mechanisms are applicable to a network employing ::: conventional IP routing and forwarding.
---
paper_title: An efficient primary-segmented backup scheme for dependable real-time communication in multihop networks

paper_content:

Several distributed real-time applications (e.g., medical imaging, air traffic control, and video conferencing) demand hard guarantees on the message delivery latency and the recovery delay from component failures. As these demands cannot be met in traditional datagram services, special schemes have been proposed to provide timely recovery for real-time communications in multihop networks. These schemes reserve additional network resources (spare resources) a priori along a backup channel that is disjoint with the primary. Upon a failure in the primary channel, its backup is activated, making the real-time connection dependable. In this paper, we propose a new method of providing backups called segmented backups, in which backup paths are provided for partial segments of the primary path rather than for its entire length, as is done in the existing schemes. We show that our method offers: 1) improved network resource utilization; 2) higher average call acceptance rate; 3) better quality-of-service guarantees on propagation delays and failure-recovery times; and 4) increased flexibility to control the level of fault tolerance of each connection separately. We provide an algorithm for routing the segmented backups and prove its optimality with respect to spare resource reservation. We detail necessary extensions to resource reservation protocol (RSVP) to support our scheme and argue that they increase the implementation complexity of RSVP minimally. Our simulation studies on various network topologies demonstrate that spare resource aggregation methods such as backup multiplexing are more effective when applied to our scheme than to earlier schemes.
---
paper_title: Fast Reroute Extensions to RSVP-TE for LSP Tunnels

paper_content:

This document defines RSVP-TE extensions to establish backup labelswitched path (LSP) tunnels for local repair of LSP tunnels. These mechanisms enable the re-direction of traffic onto backup LSP tunnels in 10s of milliseconds, in the event of a failure. Two methods are defined here. The one-to-one backup method creates detour LSPs for each protected LSP at each potential point of local repair. The facility backup method creates a bypass tunnel to protect a potential failure point; by taking advantage of MPLS label stacking, this bypass tunnel can protect a set of LSPs that have similar backup constraints. Both methods can be used to protect links and nodes during network failure. The described behavior and extensions to RSVP allow nodes to implement either method or both and to interoperate in a mixed network.
---
paper_title: Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs

paper_content:

We present a new algorithm which creates redundant trees on arbitrary node-redundant or link-redundant networks. These trees are such that any node is connected to the common root of the trees by at least one of the trees in case of node or link failure. Our scheme provides rapid preplanned recovery of communications with great flexibility in the topology design. Unlike previous algorithms, our algorithm can establish two redundant trees in the case of a node failing in the network. In the case of failure of a communications link, our algorithm provides a superset of the previously known trees.
---
paper_title: Protection cycles in mesh WDM networks

paper_content:

A fault recovery system that is fast and reliable is essential to today's networks, as it can be used to minimize the impact of the fault on the operation of the network and the services it provides. This paper proposes a methodology for performing automatic protection switching (APS) in optical networks with arbitrary mesh topologies in order to protect the network from fiber link failures. All fiber links interconnecting the optical switches are assumed to be bidirectional. In the scenario considered, the layout of the protection fibers and the setup of the protection switches is implemented in nonreal time, during the setup of the network. When a fiber link fails, the connections that use that link are automatically restored and their signals are routed to their original destination using the protection fibers and protection switches. The protection process proposed is fast, distributed, and autonomous. It restores the network in real time, without relying on a central manager or a centralized database. It is also independent of the topology and the connection state of the network at the time of the failure.
---
paper_title: Designing Low-Capacity Backup Networks for Fast Restoration

paper_content:

There are two basic approaches to allocate protection resources for fast restoration. The first allocates resources upon the arrival of each connection request; yet, it incurs significant set-up time and is often capacity-inefficient. The second approach allocates protection resources during the network configuration phase; therefore, it needs to accommodate any possible arrival pattern of connection requests, hence potentially calling for a substantial over-provisioning of resources. However, in this study we establish the feasibility of this approach. Specifically, we consider a scheme that, during the network configuration phase, constructs an (additional) low-capacity backup network. Upon a failure, traffic is rerouted through a bypass in the backup network. We establish that, with proper design, backup networks induce feasible capacity overhead. We further impose several design requirements (e.g., hop-count limits) on backup networks and their induced bypasses, and prove that, commonly, they also incur minor overhead. Motivated by these findings, we design efficient algorithms for the construction of backup networks.
---
paper_title: On the availability of networks

paper_content:

In all networks that provide a service to the consumer, one of the main performance indicators is availability. The consumer, the user of the service, wants to be able to use the service for at least X% of the time. In order to be able to make such guarantees and commit to them in Service Level Agreements, network operators need to know their network availability. In this paper, we discuss how network availability can be algorithmically computed and we derive analytical expressions for several different network topologies. Finally we show how these results can be used to compute availability of real-life networks, such as SURFnet – a high-speed Dutch national network. Introduction Businesses today depend more on network communications than a few years ago. As business applications become more critical to a company’s success, so does the availability of the underlying network. Two main factors determine the availability of the underlying network: A first factor is the availability of the individual network elements. During the lifetime of a network element, it may endure periods in which it is out of service either because of a malfunctioning, maintenance or repair work. If we denote the mean time to failure by MTBF and the mean repair time by MTTR, the availability of a network element (or more formally, the probability that the element is working properly) is defined as MTTR MTBF MTBF A + = and the unavailability as U = 1 A. A second factor is the topology of the network. Obviously, higher redundancy in the network (e.g. more links connecting network switches) will lead to higher availability, but also to higher investment costs. For the traditional telephony service often a five nines (99.999%) availability is guaranteed. Network operators that offer other services need to be able to make similar claims. In order to make such claims, an unambiguous definition of network availability is needed. In this paper we propose a definition based upon connectivity of the network. The remainder of the paper is organized as follows. In the following section we discuss several network availability definitions. The algorithmic computation of network availability is discussed subsequently. Then we determine analytic expressions for a number of simple network topologies. Finally, we apply these results to obtain the availability for the real-world SURFnet network. Network availability definitions We consider a network represented as a graph G(V,E) consisting of a set of nodes V and a set of links E. |V| = N denotes the number of nodes while the number of links is |E| = L. Nodes represent routers or switches and links represent communication links (e.g., optical fibers). Both links and nodes have a certain availability. In our study we assume that the nodes are always available, i.e. only the links can fail. This assumption is based on the fact that node failures occur much less frequent than link failures, which occur e.g. when fibers are unintentionally broken by means of shovels. In addition we assume that failures occur independently. Path availability Let us first examine network availability in its strictest form. Assume that each user has precisely one path over which (s)he can communicate with another user. If this path fails the communication is precluded. Since a path consists of a serial concatenation of nodes and links, its availability is simply computed as the product of the availabilities of the nodes and links that constitute that path. Network availability can then be derived as the minimum path availability over all node pairs. Since all paths are known (or can be computed via a simple shortest paths algorithm), the network availability is easily computed. Let pij denote the availability probability of link (i,j), which connects nodes i and j. To gain the highest possible network availability (defined in its strictest form), the minimum path availability over all node pairs should be maximized. If we assign the weight -log (pij) to each link (i,j) ∈ E, then the same goal is achieved by using the shortest paths (given the new weights) between the sourcedestination (s-d) pairs. The shortest path with the highest weight has the lowest path availability and determines the optimal network availability that can be gained. Unloaded network availability The other extreme case is where communication can take place over all possible paths. This closely resembles routing in the Internet where, in case a failure takes place, routing protocols automatically reconfigure the routing tables to direct traffic over alternative working paths towards their destinations. Network unavailability is in this case determined by the probability that between a particular source-destination pair, no path is available (i.e., the network is disconnected). BroadBand Europe Antwerp, Belgium 3-6 December 2007 ISBN : 9789076546094 Paper Tu3A3 – Zou Page 2 of 6 The maximum probability over all s-d pairs determines the network unavailability and hence also the network availability. Loaded network availability The computation of network availability in the previous subsection is actually too optimistic in practice, since it assumes that when paths fail the alternate paths have enough resources available to handle the traffic of the failed path(s). Since resources are limited, this may not always be the case. If we consider the example in Figure 1, half of the subgraphs are disconnected let us call this unloaded network unavailability. However, the three subgraphs (l1,l2), (l2,l3) and (l1,l3) may also not be able to take over the traffic of the failed link we refer to such case as loaded network unavailability. We will not consider loaded network availability in this paper. Computation of network availability When looking at a network, one could say that links are either available (a) or unavailable (u). By pruning the unavailable links from the graph, we are left with a subgraph which may either be connected or disconnected. In the latter case, for at least one s-d pair, the network is unavailable. By computing the connectivity of all possible subgraphs, one can precisely determine the network (un)availability. We will illustrate this for the three-node network in Figure 1.
---
paper_title: Isoperimetric numbers of graphs

paper_content:

Abstract For X ⊆ V ( G ), let ∂X denote the set of edges of the graph G having one end in X and the other end in V ( G ) βX . The quantity i(G)≔ min { |∂X| |X| } , where the minimum is taken over all non-empty subsets X of V ( G ) with |X| ≤ |V(G)| 2 , is called the isoperimetric number of G . The basic properties of i ( G ) are discussed. Some upper and lower bounds on i ( G ) are derived, one in terms of | V ( G )| and | E ( G )| and two depending on the second smallest eigenvalue of the difference Laplacian matrix of G . The upper bound is a strong discrete version of the wellknown Cheeger inequality bounding the first eigenvalue of a Riemannian manifold. The growth and the diameter of a graph G are related to i ( G ). The isoperimetric number of Cartesian products of graphs is studied. Finally, regular graphs of fixed degree with large isoperimetric number are considered.
---
paper_title: On Approximation of New Optimization Methods for Assessing Network Vulnerability

paper_content:

Assessing network vulnerability before potential disruptive events such as natural disasters or malicious attacks is vital for network planning and risk management. It enables us to seek and safeguard against most destructive scenarios in which the overall network connectivity falls dramatically. Existing vulnerability assessments mainly focus on investigating the inhomogeneous properties of graph elements, node degree for example, however, these measures and the corresponding heuristic solutions can provide neither an accurate evaluation over general network topologies, nor performance guarantees to large scale networks. To this end, in this paper, we investigate a measure called pairwise connectivity and formulate this vulnerability assessment problem as a new graph-theoretical optimization problem called β-disruptor, which aims to discover the set of critical node/edges, whose removal results in the maximum decline of the global pairwise connectivity. Our results consist of the NP-Completeness and inapproximability proof of this problem, an O(log n loglog n) pseudo-approximation algorithm for detecting the set of critical nodes and an O(log^1.5 n) pseudo-approximation algorithm for detecting the set of critical edges. In addition, we devise an efficient heuristic algorithm and validate the performance of the our model and algorithms through extensive simulations.
---
paper_title: Optimization, approximation, and complexity classes

paper_content:

We define a natural variant of NP, MAX NP , and also a subclass called MAX SNP . These are classes of optimization problems, and in fact contain several natural, well-studied ones. We show that problems in these classes can be approximated with some bounded error. Furthermore, we show that a number of common optimization problems are complete under a kind of careful transformation (called L - reduction ) that preserves approximability. It follows that such a complete problem has a polynomial-time approximation scheme iff the whole class does. These results may help explain the lack of progress on the approximability of a host of optimization problems.
---
paper_title: Sparsest cuts and bottlenecks in graphs

paper_content:

Abstract The problem of determining a sparsest cut in a graph is characterized and its computation shown to be NP-hard. A class of sparsest cuts, termed bottlenecks, is characterized by a dual relation to a particular polynomial time computable multicommodity flow problem. Efficient computational techniques for determining bottlenecks in a broad class of instances are presented.
---
paper_title: A note on the maximum flow through a network

paper_content:

This note discusses the problem of maximizing the rate of flow from one terminal to another, through a network which consists of a number of branches, each of which has a limited capacity. The main result is a theorem: The maximum possible flow from left to right through a network is equal to the minimum value among all simple cut-sets. This theorem is applied to solve a more general problem, in which a number of input nodes and a number of output nodes are used.
---
paper_title: COMPUTATION OF MAXIMAL FLOWS IN NETWORKS

paper_content:

Abstract : A simple computational method, based on the simplex algorithm of linear programming, is proposed for the following problem: 'Consider a network (e.g., rail, road, communication network) connecting two given points by way of a number of intermediate points, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given point to the other.'
---
paper_title: COMPUTATION OF MAXIMAL FLOWS IN NETWORKS

paper_content:

Abstract : A simple computational method, based on the simplex algorithm of linear programming, is proposed for the following problem: 'Consider a network (e.g., rail, road, communication network) connecting two given points by way of a number of intermediate points, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given point to the other.'
---
paper_title: Introduction to Algorithms

paper_content:

From the Publisher: ::: The updated new edition of the classic Introduction to Algorithms is intended primarily for use in undergraduate or graduate courses in algorithms or data structures. Like the first edition,this text can also be used for self-study by technical professionals since it discusses engineering issues in algorithm design as well as the mathematical aspects. ::: In its new edition,Introduction to Algorithms continues to provide a comprehensive introduction to the modern study of algorithms. The revision has been updated to reflect changes in the years since the book's original publication. New chapters on the role of algorithms in computing and on probabilistic analysis and randomized algorithms have been included. Sections throughout the book have been rewritten for increased clarity,and material has been added wherever a fuller explanation has seemed useful or new information warrants expanded coverage. ::: As in the classic first edition,this new edition of Introduction to Algorithms presents a rich variety of algorithms and covers them in considerable depth while making their design and analysis accessible to all levels of readers. Further,the algorithms are presented in pseudocode to make the book easily accessible to students from all programming language backgrounds. ::: Each chapter presents an algorithm,a design technique,an application area,or a related topic. The chapters are not dependent on one another,so the instructor can organize his or her use of the book in the way that best suits the course's needs. Additionally,the new edition offers a 25% increase over the first edition in the number of problems,giving the book 155 problems and over 900 exercises thatreinforcethe concepts the students are learning.
---
paper_title: Network Flow and Testing Graph Connectivity

paper_content:

An algorithm of Dinic for finding the maximum flow in a network is described. It is then shown that if the vertex capacities are all equal to one, the algorithm requires at most $O(|V|^{1/2} \cdot |E|)$ time, and if the edge capacities are all equal to one, the algorithm requires at most $O(|V|^{2/3} \cdot |E|)$ time. Also, these bounds are tight for Dinic’s algorithm.These results are used to test the vertex connectivity of a graph in $O(|V|^{1/2} \cdot |E|^2 )$ time and the edge connectivity in $O(|V|^{5/3} \cdot |E|)$ time.
---
paper_title: A comparative analysis of network dependability, fault-tolerance, reliability, security, and survivability

paper_content:

A number of qualitative and quantitative terms are used to describe the performance of what has come to be known as information systems, networks or infrastructures. However, some of these terms either have overlapping meanings or contain ambiguities in their definitions presenting problems to those who attempt a rigorous evaluation of the performance of such systems. The phenomenon arises because the wide range of disciplines covered by the term information technology have developed their own distinct terminologies. This paper presents a systematic approach for determining common and complementary characteristics of five widely-used concepts, dependability, fault-tolerance, reliability, security, and survivability. The approach consists of comparing definitions, attributes, and evaluation measures for each of the five concepts and developing corresponding relations. Removing redundancies and clarifying ambiguities will help the mapping of broad user-specified requirements into objective performance parameters for analyzing and designing information infrastructures.
---
paper_title: Finding the edge connectivity of directed graphs

paper_content:

Abstract We present two algorithms for finding the edge connectivity of a given directed graph G . The first algorithm runs in O ( nm ) time, where n is the number of vertices and m is the number of edges in G . The second algorithm runs in O ( λ 2 n 2 ) time, where λ is the edge connectivity of G . Combining both algorithms yields an O (MIN{ m , λ 2 n } n ) time algorithm for finding the edge connectivity of directed graphs. We also present an O (MIN{ m , k 2 n } n ) time algorithm for deciding whether the edge connectivity of a given directed graph G is at least k . Both algorithms are superior to the best known algorithms for finding the edge connectivity of directed graphs.
---
paper_title: Minimum cuts in near-linear time

paper_content:

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a random- ized (Monte Carlo) algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log 3 n) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n 2 log n) time. This variant has an optimal 51# parallelization. Both
---
paper_title: Using expander graphs to find vertex connectivity

paper_content:

The (vertex) connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding κ. For a digraph with <i>n</i> vertices, <i>m</i> edges and connectivity κ the time bound is <i>O</i>((<i>n</i> + min{κ<sup>&frac52;</sup>, κ<i>n</i><sup>¾</sup>})<i>m</i>). This improves the previous best bound of <i>O</i>((<i>n</i> + min{κ<sup>3</sup>, κ<i>n</i>&rcub)<i>m</i>). For an undirected graph both of these bounds hold with <i>m</i> replaced by κκ<i>n</i>. Expander graphs are useful for solving the following subproblem that arises in connectivity computation: A known set <i>R</i> of vertices contains two large but unknown subsets that are separated by some unknown set <i>S</i> of κ vertices; we must find two vertices of <i>R</i> that are separated by <i>S</i>.
---
paper_title: Computing Vertex Connectivity: New Bounds from Old Techniques

paper_content:

The vertex connectivity ? of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{?3+n,?n}m); for an undirected graph the term m can be replaced by ?n. A randomized algorithm finds ? with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(?1nmlog(n2/m)) where ?1?m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424?446) that computes edge connectivity.
---
paper_title: Finding the edge connectivity of directed graphs

paper_content:

Abstract We present two algorithms for finding the edge connectivity of a given directed graph G . The first algorithm runs in O ( nm ) time, where n is the number of vertices and m is the number of edges in G . The second algorithm runs in O ( λ 2 n 2 ) time, where λ is the edge connectivity of G . Combining both algorithms yields an O (MIN{ m , λ 2 n } n ) time algorithm for finding the edge connectivity of directed graphs. We also present an O (MIN{ m , k 2 n } n ) time algorithm for deciding whether the edge connectivity of a given directed graph G is at least k . Both algorithms are superior to the best known algorithms for finding the edge connectivity of directed graphs.
---
paper_title: Graph Algorithms

paper_content:

Shimon Even's Graph Algorithms, published in 1979, was a seminal introductory book on algorithms read by everyone engaged in the field. This thoroughly revised second edition, with a foreword by Richard M. Karp and notes by Andrew V. Goldberg, continues the exceptional presentation from the first edition and explains algorithms in a formal but simple language with a direct and intuitive presentation. The book begins by covering basic material, including graphs and shortest paths, trees, depth-first-search, and breadth-first search. The main part of the book is devoted to network flows and applications of network flows, and it ends with chapters on planar graphs and testing graph planarity.
---
paper_title: Decreasing the spectral radius of a graph by link removals

paper_content:

The decrease of the spectral radius, an important characterizer of network dynamics, by removing links is investigated. The minimization of the spectral radius by removing m links is shown to be an NP-complete problem, which suggests considering heuristic strategies. Several greedy strategies are compared, and several bounds on the decrease of the spectral radius are derived. The strategy that removes that link l=i~j with largest product (x1)i(x1)j of the components of the eigenvector x1 belonging to the largest adjacency eigenvalue is shown to be superior to other strategies in most cases. Furthermore, a scaling law where the decrease in spectral radius is inversely proportional to the number of nodes N in the graph is deduced. Another sublinear scaling law of the decrease in spectral radius versus the number m of removed links is conjectured.
---
paper_title: Edge-connectivity augmentation preserving simplicity

paper_content:

Given a simple graph G=(V, E), the goal is to find a smallest set F of new edges such that G=(V, E/spl cup/F) is /spl kappa/ edge connected and simple. Very recently this problem was shown to be NP hard by T. Jordan (1997). We prove that if OPT/sub P//sup /spl kappa// is high enough-depending on /spl kappa/ only-then OPT/sub S//sup /spl kappa//=OPT/sub P//sup /spl kappa// holds, where OPT/sub S//sup /spl kappa// (OPT/sub P//sup /spl kappa//) is the size of an optimal solution of the augmentation problem with (without) the simplicity preserving requirement, respectively. Furthermore, OPT/sub S//sup /spl kappa//-OPT/sub P//sup /spl kappa///spl les/g(/spl kappa/) holds for a certain (quadratic) function of /spl kappa/. Based on these results an algorithm is given which computes an optimal solution in time O(n/sup 4/) for any fixed /spl kappa/. Most of these results are extended to the case of non-uniform demands, as well.
---
paper_title: Building Chain and Cactus Representations of All Minimum Cuts from Hao-Orlin in the Same Asymptotic Run Time

paper_content:

A cactus is a simple data structure that represents all minimum cuts of a weighted, undirected graph in linear space. We describe the first algorithm that can build a cactus from the asymptotically fastest deterministic algorithm that finds all minimum cuts in a weighted graph?the Hao?Orlin minimum cut algorithm. This improves the deterministic time to construct the cactus in graphs with n vertices and m edges from O(n3) to O(nmlogn2/m).
---
paper_title: Extracting maximal information about sets of minimum cuts

paper_content:

There are two well-known, elegant, compact, and efficiently computed representations of selected minimum edge cuts in a weighted, undirected graphG=(V, E) withn nodes andm edges: at one extreme, the Gomory-Hu cut tree [12] represents $$\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)$$ minimum cuts, one for each pair of nodes inG; at the other extreme, the Picard-Queyranne DAG [24] represents all the minimum cuts between a single pair of nodes inG. The GH cut tree is constructed with onlynź1 max-flow computations, and the PQ DAG is constructed with one max-flow computation, plusO(m) additional time. In this paper we show how to marry these two representations, getting the best features of both. We first show that we can construct all $$\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)$$ DAGs, one for each fixed pair of nodes, using onlynź1 max-flow computations as in [12], plusO(m) time per DAG as in [24]. This speeds up the obvious approach by a factor ofn. We then apply this approach to an unweighted graphG, to find all the edge-connectivity cuts inG, i.e., cuts with capacity equal to the connectivity ofG. Matula [22] gave a method to find one connectivity cut inO(nm) time; we show thatO(nm) time suffices to represent all connectivity cuts compactly, and to list all of them explicitly. This improves the previous best time bound ofO(n2m) [3] for listing the connectivity cuts. The connectivity cuts are central in network reliability calculations. We then show how to find all pairs of nodes that are separated by at least one connectivity cut inO(nm) time.
---
paper_title: GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS

paper_content:

This paper surveys the recent progress on the graph algorithms for solving network connectivity problems such as the extreme set problem, the cactus representation problem, the edge-connectivity aug- mentation problem and the source location problem. In particular, we show that efficient algorithms for these problems can be designed based on maximum adjacency orderings.
---
paper_title: Canonical cactus representation for minimum cuts

paper_content:

It is known that all minimum cuts in a networkN can be embedded in a cactus whose size is bounded by a linear function of the number of vertices inN, such that any minimum cut ofN can be easily obtained as a minimum cut of the cactus. However, such a representation for a given network is not unique. We introduce two canonical forms of cactus representation for the minimum cuts and show their uniqueness. These cacti contain at most twice as many vertices asN.
---
paper_title: Successive edge-connectivity augmentation problems

paper_content:

,G1,G2,... of supergraphs of G such that Gi is a subgraph of Gj for any i<j and Gi is an optimal (l+i)-edge-connected augmentation of G for any i≥0.
---
paper_title: A fast algorithm for optimally increasing the edge-connectivity

paper_content:

An undirected, unweighted graph G=(V, E with n nodes, m edges, and connectivity lambda ) is considered. Given an input parameter delta , the edge augmentation problem is to find the smallest set of edges to add to G so that its edge-connectivity is increased by delta . A solution to this problem that runs in time O( delta /sup 2/nm+nF(n)), where F(n) is the time to perform one maximum flow on G, is given. The solution gives the optimal augmentation for every delta ', 1 >
---
paper_title: The minimum augmentation of any graph to a K-edge-connected graph

paper_content:

For a graph G0 = (V, E0) and an integer K, how many edges are needed for augmenting G0 to a K-edge-connected graph? Results in the literature have answered this in several special cases such as when G0 is a tree, or when K = 2. In this paper, we settle the problem in the general case where G0 can be any multigraph and K can be any positive integer. We obtained both good characterization and good algorithm for the problem. Applications of our algorithm are suggested in designing a reliable network aiming at the most effective use of exising network.
---
paper_title: Augmenting graphs to meet edge-connectivity requirements

paper_content:

The problem of determining the minimum number gamma of edges to be added to a graph G so that in the resulting graph the edge-connectivity between every pair (u,v) of nodes is at least a prescribed value r(u,v) is treated. A min-max formula for gamma is derived, and a polynomial-time algorithm for computing gamma is described. The directed counterpart of the problem is also solved for the case in which r(u,v)=k>or=1. The approach used makes it possible to solve a degree-constrained version of the problem. The minimum-cost augmentation problem can also be solved in polynomial time provided that the edge costs arise from node costs. >
---
paper_title: Maximum weight matching-based algorithms for k-edge-connectivity augmentation of a graph

paper_content:

The subject of the paper is to show that, by utilizing maximum-weight matching algorithms, we obtain heuristic algorithms of high capability for the k-edge-connectivity augmentation problem of graphs. The following points are shown by experimentally comparing the capabilities of eighteen algorithms for 4,175 graphs G' = (V, E') with 10/spl les/|V|/spl les/1400: (1) an existing algorithm, FSM, (previously proposed by us), based on an algorithm for finding a maximum-weight matching, produces the best solutions, while it becomes unrealistic when |V|>1000; (2) by utilizing a 2-approximation algorithm for the maximum-weight matching problem, a promising algorithm, HBD/sub a+/, is proposed, and it is shown that the second best solution (average 1.017 times that of FSM) is obtained in much shorter CPU time (average 0.1 times that of FSM).
---
paper_title: Augmenting graphs to meet edge-connectivity requirements

paper_content:

The problem of determining the minimum number gamma of edges to be added to a graph G so that in the resulting graph the edge-connectivity between every pair (u,v) of nodes is at least a prescribed value r(u,v) is treated. A min-max formula for gamma is derived, and a polynomial-time algorithm for computing gamma is described. The directed counterpart of the problem is also solved for the case in which r(u,v)=k>or=1. The approach used makes it possible to solve a degree-constrained version of the problem. The minimum-cost augmentation problem can also be solved in polynomial time provided that the edge costs arise from node costs. >
---
paper_title: Approximation Algorithms for Graph Augmentation

paper_content:

We study the problem of increasing the connectivity1 of a graph at an optimal cost. Since the general problem is NP-hard, we focus on efficient approximation schemes that come within a constant factor from the optimal. Previous algorithms either do not take edge costs into consideration, or run slower than our algorithm. Our algorithm takes as input an undirected graph G0 = (V, E0) on n vertices, that is not necessarily connected, and a set Feasible of m weighted edges on V, and outputs a subset Aug of edges which when added to G0 make it 2-connected. The weight of Aug, when G0 is initially connected, is no more than twice the weight of the least weight subset of edges of Feasible that increases the connectivity to 2. The running time of our algorithm is O(m + n logn). We also study the problem of increasing the edge connectivity of any graph G, to k, within a factor of 2 (for any k > 0). The running time of this algorithm is O(nk log n(m + n log n)). We observe that when k is odd we can use different techniques to obtain an approximation factor of 2 for increasing edge connectivity from k to (k+1) in O(kn2) time.
---
paper_title: On shredders and vertex connectivity augmentation

paper_content:

We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordan computes an augmenting edge set with at most @?(k-1)/[email protected]? edges over the optimum. [email protected]?V(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G-C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)>=k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p>=3) is less than 2n/(2p-3), and that this bound is asymptotically tight.
---
paper_title: A Near Optimal Algorithm for Vertex Connectivity Augmentation

paper_content:

Given an undirected graph G and a positive integer k, the k-vertex-connectivity augmentation problem is to find a smallest set F of new edges for which G + F is k-vertex-connected. Polynomial algorithms for this problem are known only for k ≤ 4 and a major open question in graph connectivity is whether this problem is solvable in polynomial time in general. For arbitrary k, a previous result of Jordan [14] gives a polynomial algorithm which adds an augmenting set F of size at most k - 3 more than the optimum, provided G is (k - 1)-vertex-connected. In this paper we develop a polynomial algorithm which makes an l- connected graph G k-vertex-connected by adding an augmenting set of size at most ((k - l)(k - 1) + 4)=2 more than (a new lower bound for) the optimum. This extends the main results of [14,15]. We partly follow and generalize the approach of [14] and we adapt the splitting off method (which worked well on edge-connectivity augmentation problems) to vertex-connectivity. A key point in our proofs, which may also find applications elsewhere, is a new tripartite submodular inequality for the sizes of neighbour-sets in a graph.
---
paper_title: Minimal Edge-Coverings of Pairs of Sets

paper_content:

We derive a new min-max formula for the minimum number of new edges to be added to a given directed graph to make it k-node-connected. This gives rise to a polynomial time algorithm (via the ellipsoid method) to compute the augmenting edge set of minimum cardinality. (Such an algorithm or formula was previously known only for k = 1). Our main result is actually a new min-max theorem concerning "bisupermodular" functions on pairs of sets. This implies the node-connectivity augmentation theorem mentioned above as well as a generalization of an earlier result of the first author on the minimum number of new directed edges whose addition makes a digraph k-edge-connected. As further special cases of the main theorem, we derive an extension of (Lubiw?s extension of) Gyo?ri?s theorem on intervals, Mader?s theorem on splitting off edges in directed graphs, and Edmonds? theorem on matroid partitions.
---
paper_title: Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation

paper_content:

A k-separator (k-shredder) of a k-node connected undirected graph is a set of k nodes whose removal results in two or more (three or more) connected components. Let n denote the number of nodes. Solving an open question, we show that the problem of counting the number of k-separators is #P-complete. However, we present an O(k2n2+k3n1.5)-time (deterministic) algorithm for finding all the k-shredders. This solves an open question: efficiently find a k-separator whose removal maximizes the number of connected components. For k?4, our running time is within a factor of k of the fastest algorithm known for testing k-node connectivity. One application of shredders is to increase the node connectivity from k to (k+1) by efficiently adding an (approximately) minimum number of new edges. Jordan (J. Combin. Theory Ser. B63 1995) gave an O(n5)-time augmentation algorithm such that the number of new edges is within an additive term of (k?2) from a lower bound. We improve the running time to O(min(k,n)k2n2), while achieving the same performance guarantee. For k?4, the running time compares favorably with the running time for testing k-node connectivity.
---
paper_title: An approximation algorithm for minimum-cost vertex-connectivity problems

paper_content:

We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design problem, a valuerij for each pair of verticesi andj is given, and a minimum-cost set of edges such that there arerij vertex-disjoint paths between verticesi andj must be found. In the case for whichrijź{0, 1, 2} for alli, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in whichrij=k for alli, j, we can find a solution of cost no more than 2H(k) times optimal, where $$\mathcal{H}(n) = 1 + \tfrac{1}{2} + \cdot \cdot \cdot + \tfrac{1}{n}$$ . No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which has recently led to approximation algorithms for many edge-connectivity problems.
---
paper_title: Independence free graphs and vertex connectivity augmentation

paper_content:

Given an undirected graph G and a positive integer k, the k-vertex-connectivity augmentation problem is to find a smallest set F of new edges for which G + F is k-vertex-connected. Polynomial algorithms for this problem have been found only for k ≤ 4 and a major open question in graph connectivity is whether this problem is solvable in polynomial time in general.In this paper, we develop an algorithm which delivers an optimal solution in polynomial time for every fixed k. In the case when the size of an optimal solution is large compared to k, our algorithm is polynomial for all k. We also derive a min-max formula for the size of a smallest augmenting set in this case. A key step in our proofs is a complete solution of the augmentation problem for a new family of graphs which we call k-independence free graphs. We also prove new splitting off theorems for vertex connectivity.
---
paper_title: Augmenting Undirected Node-Connectivity by One

paper_content:

We present a min-max formula for the problem of augmenting the node-connectivity of a graph by one and give a polynomial time algorithm for finding an optimal solution. We also solve the minimum-cost version for node-induced cost functions.
---
paper_title: Finding a smallest augmentation to biconnect a graph

paper_content:

The problem of finding a minimum number of edges whose addition biconnects an undirected graph is considered. This problem has been studied by several other researchers, two of whom presented a linear-time algorithm for this problem in an earlier volume of this journal. However, that algorithm contains an error that is exposed in this paper. A corrected linear-time algorithm for this problem, as well as a new efficient parallel algorithm, are presented. The parallel algorithm runs in $O(\log ^2 n)$ time with a linear number of processors on an EREW PRAM, where n is the number of vertices in the input graph.
---
paper_title: Depth first search and linear graph algorithms

paper_content:

The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples. An improved version of an algorithm for finding the strongly connected components of a directed graph and at algorithm for finding the biconnected components of an undirect graph are presented. The space and time requirements of both algorithms are bounded by $k_1 V + k_2 E + k_3 $ for some constants $k_1 ,k_2 $, and $k_3 $, where V is the number of vertices and E is the number of edges of the graph being examined.
---
paper_title: Design of Survivable Networks

paper_content:

Motivation.- Network survivability models using node types.- Survivable network design under connectivity constraints - a survey.- Decomposition.- Basic inequalities.- Lifting theorems.- Partition inequalities.- Node partition inequalities.- Lifted r-cover inequalities.- Comb inequalities.- How to find valid inequalities.- Implementation of the cutting plane algorithm.- Computational results.
---
paper_title: On four-connecting a triconnected graph

paper_content:

The author considers the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks. He presents an O(n alpha (m,n)+m) time sequential algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and alpha (m, n) is the inverse Ackermann function. He presents a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. The new lower bound applies for arbitrary k, and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k-1)-connect graph. For k=4, he shows that this lower bound is tight by giving an efficient algorithm for finding a set edges with the required size whose addition four-connects a triconnected graph. >
---
paper_title: Cross-Layer Survivability in WDM-Based Networks

paper_content:

In layered networks, a single failure at a lower layer may cause multiple failures in the upper layers. As a result, traditional schemes that protect against single failures may not be effective in multilayer networks. In this paper, we introduce the problem of maximizing the connectivity of layered networks. We show that connectivity metrics in layered networks have significantly different meaning than their single-layer counterparts. Results that are fundamental to survivable single-layer network design, such as the Max-Flow Min-Cut Theorem, are no longer applicable to the layered setting. We propose new metrics to measure connectivity in layered networks and analyze their properties. We use one of the metrics, Min Cross Layer Cut, as the objective for the survivable lightpath routing problem and develop several algorithms to produce lightpath routings with high survivability. This allows the resulting cross-layer architecture to be resilient to failures between layers.
---
paper_title: A minimum 3-connectivity augmentation of a graph

paper_content:

Abstract The paper considers the minimum 3-connectivity augmentation problems: determining a minimum-weight set of edges to be added so as to 3-connect a given undirectted simple graph. The first result is that the problem is NP-complete even if a given graph and weights are restricted to a 2-connected graph and either 1 or 2, respectively. The second result is for the problem with all weights are equal: it is shown that the cardinality of a solution to the problem can be computed from a given graph and that there is an O ( n v ( n v + n e ) 2 ) algorithm for finding a solution, where n v and n e are the numbers of vertices and edges of a given graph, respectively.
---
paper_title: NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems

paper_content:

The problem of finding a minimum augmenting edge-set to make a graphk-vertex connected is considered. This problem is denoted as the minimumk-augmentation problem. For weighted graphs, the minimumk-augmentation problem is NP-complete. Our main result is an approximation algorithm with a performance ratio of 3 for solving the minimum 3-augmentation problem. This improves the best previously known performance guarantee of 11/3. We also have the following marginal result: an approximation algorithm for the minimum 2-augmentation problem that achieves a factor of 2, and thus improves the previously known factor of 2+(1/n), withnas the number of vertices in the graph.
---
paper_title: Improved Approximation Algorithms for Uniform Connectivity Problems

paper_content:

The problem of finding minimum-weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial time approximation algorithms for various weighted and unweighted connectivity problems are given. The following results are presented:1. For the unweightedk-edge-connectivity problem an approximation algorithm that achieves a performance ratio of 1.85 is described. This is the first polynomial-time algorithm that achieves a constant less than 2, for allk.2. For the weightedk-vertex-connectivity problem, a constant factor approximation algorithm is given assuming that the edge-weights satisfy the triangle inequality. This is the first constant factor approximation algorithm for this problem.3. For the case of biconnectivity, with no assumptions about the weights of the edges, an algorithm that achieves a factor asymptotically approaching 2 is described. This matches the previous best bound for the corresponding edge connectivity problem.
---
paper_title: An algorithm to increase the node-connectivity of a digraph by one

paper_content:

We develop a combinatorial polynomial-time algorithm to make a (k-1)-connected digraph k-connected by adding a minimum number of new edges.
---
paper_title: Approximation Algorithms for Graph Augmentation

paper_content:

We study the problem of increasing the connectivity1 of a graph at an optimal cost. Since the general problem is NP-hard, we focus on efficient approximation schemes that come within a constant factor from the optimal. Previous algorithms either do not take edge costs into consideration, or run slower than our algorithm. Our algorithm takes as input an undirected graph G0 = (V, E0) on n vertices, that is not necessarily connected, and a set Feasible of m weighted edges on V, and outputs a subset Aug of edges which when added to G0 make it 2-connected. The weight of Aug, when G0 is initially connected, is no more than twice the weight of the least weight subset of edges of Feasible that increases the connectivity to 2. The running time of our algorithm is O(m + n logn). We also study the problem of increasing the edge connectivity of any graph G, to k, within a factor of 2 (for any k > 0). The running time of this algorithm is O(nk log n(m + n log n)). We observe that when k is odd we can use different techniques to obtain an approximation factor of 2 for increasing edge connectivity from k to (k+1) in O(kn2) time.
---
paper_title: Finding disjoint paths with related path costs

paper_content:

We consider routing in survivable networks that provide protection against node or link failures. In these networks resilience against failures is provided by routing connections on pairs of disjoint paths called primary and backup paths. The primary path of a connection carries its traffic under normal circumstances and in the eventuality of a network failure effecting the primary path the connection traffic (all or some portion of it) is rerouted over its backup path. In an online setting as connection requests arrive a pair of disjoint primary and backup paths of least total cost (under some link cost metric) are selected to route the connections. In many situations the cost metric used for the primary path differs from the cost metric used for the backup path. Also in many realistic settings these two cost metrics are related to each other.
---
paper_title: The complexity of finding maximum disjoint paths with length constraints

paper_content:

The following problem is considered: Given an integer K, a graph G with two distinct vertices s and t, find the maximum number of disjoint paths of length K from s to t. The problem has several variants: the paths may be vertex-disjoint or edge-disjoint, the lengths of the paths may be equal to K or bounded by K, the graph may be undirected or directed. It is shown that except for small values of K all the problems are NP-complete. Assuming P ≠ NP, for each problem, the largest value of K for which the problem is not NP-complete is found. Whenever a polynomial algorithm exists, an efficient algorithm is described.
---
paper_title: The complexity of finding two disjoint paths with min-max objective function

paper_content:

Abstract Given a network G = (V,E) and two vertices s and t, we consider the problem of finding two disjoint paths from s to t such that the length of the longer path is minimized. The problem has several variants: The paths may be vertex-disjoint or arc-disjoint and the network may be directed or undirected. We show that all four versions as well as some related problems are strongly NP-complete. We also give a pseudo-polynomial-time algorithm for the acyclic directed case.
---
paper_title: The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms

paper_content:

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issue of network vulnerability by prescribing alternate routes for traffic flows. Applications include the dispatching of duplicate packets of data to improve the reliability in communication networks and the diverting of traffic during congestion to reduce the chances of bottlenecks in transportation networks, in the presence of time-dependent variations in travel delays in the network. We prove that this problem, and many variations of it, are NP-hard and we develop a 0-1 linear programming model that can be used to solve this problem. This model can accommodate various degrees of disjointedness of the pair of paths, from complete to partial with respect to specific arcs. We also present some computational results obtained by solving the above models using CPLEX-MIP.
---
paper_title: Finding disjoint paths with different path-costs: Complexity and algorithms

paper_content:

Consider a network G = (V,E) with distinguished vertices s and t, and with k different costs on every edge. We consider the problem of finding k disjoint paths from s to t such that the total cost of the paths is minimized, where the j th edge-cost is associated with the j th path. The problem has several variants: The paths may be vertex-disjoint or arcdisjoint and the network may be directed or undirected. We show that all four versions of the problem are strongly NP-complete even for k = 2. We describe polynomial time heuristics for the problem and a polynomial time algorithm for the acyclic directed case.
---
paper_title: On the complexity of vertex-disjoint length-restricted path problems

paper_content:

Let G = (V,E) be a simple graph and s and t be two distinct vertices of G. A path in G is called l-bounded for some l ∈ N if it does not contain more than l edges. We prove that computing the maximum number of vertex-disjoint l-bounded s, t-paths is APX-complete for any l ≥ 5. This implies that the problem of finding k vertex-disjoint l-bounded s, t-paths with minimal total weight for a given number k ∈ N, 1 ≤ k ≤ |V| - 1, and nonnegative weights on the edges of G is NPO-complete for any length bound l ≥ 5. furthermore, we show that these results are tight in the sense that for l ≤ 4 both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. Similar results are obtained for the analogous problems with path lengths equal to l instead of at most l and with edge-disjointness instead of vertex-disjointness.
---
paper_title: On finding disjoint paths in single and dual link cost networks

paper_content:

Finding a disjoint path pair is an important component in survivable networks. Since the traffic is carried on the active (working) path most of the time, it is useful to find a disjoint path pair such that the length of the shorter path (to be used as the active path) is minimized. In this paper, we first address such a minmin problem. We prove that this problem is NP-complete in either single link cost (e.g. dedicated backup bandwidth) or dual link cost (e.g. shared backup bandwidth) networks. In addition, it is NP-hard to obtain a k-approximation to the optimal solution for any k>1. Our proof is extended to another open question regarding the computational complexity of a restricted version of the min-sum problem in an undirected network with ordered dual cost links (called MSOD problem). To solve the minmin problem efficiently, we introduce a novel concept called conflicting link set which provides insights into the so-called trap problem, and develop a divide-and-conquer strategy. The result is an effective heuristic for the minmin problem called COLE, which can outperform other approaches in terms of both the optimality and running time. We also apply COLE to the MSOD problem to efficiently provide shared path protection and conduct comprehensive performance evaluation as well as comparison of various schemes for shared path protection. We show that COLE not only processes connection requests much faster than existing ILP based approaches but also achieves a good balance among the AP length, bandwidth efficiency and recovery time.
---
paper_title: On multipath routing using widest pair of disjoint paths

paper_content:

Multipath and disjoint path routing schemes have received a considerable amount of attention in the networking research community in recent years due to many of advantages offered by such schemes. Delay, delay-jitter, bandwidth, are often used as parameters to specify quality-of-service. One of the most important parameters is the bandwidth of the route used for data transmission. A path from a source node s to a destination node t is known as the widest path if the bandwidth of this path is the largest among all paths between s to t. Algorithms for computing a widest path between a source-destination node pair is well-known. In this paper, we consider two problems where the notions of multipath, disjoint path and widest path are combined. In one version, we address the problem of finding a pair of disjoint paths between a source-destination node pair, such that the combined bandwidth of this path-pair is the maximum over all such pairs. In the other version, we want to find a pair of disjoint paths, such that the bandwidth of the first path is at least X/sub 1/ and the bandwidth of the second path is at least X/sub 2/, for some pre-specified values X/sub 1/ and X/sub 2/. We prove that both versions of the problem are NP-complete. We provide exact and approximate solutions for both versions of the problem. We show that our approximate solutions provide near-optimal solutions for almost all the instances of the problem.
---
paper_title: How Reliable Can Two-Path Protection Be?

paper_content:

This paper investigates the subject of reliability via two link-disjoint paths in mesh networks. We address the issues of how reliable two-path protection can be and how to achieve the maximum reliability. This work differs from traditional studies, such as MIN-SUM, MIN-MAX, and MIN-MIN, in that the objective in this paper is to maximize the reliability of the two-path connection given the link reliability, or equivalently, to minimize the end-to-end failure probability. We refer to this problem as MAX-REL. Solving MAX-REL provides 100% protection against a single failure while maximizing the reliability regardless of how many link failures occur in the network. We prove that this problem is NP-complete and derive a corresponding upper bound, which is the theoretical maximum reliability for a source-destination pair, and a lower bound, which is the worst case of the proposed algorithm. The time efficiency of the algorithms is analyzed, and the performance of the algorithms is evaluated through simulation. We demonstrate that our heuristic algorithms not only achieve a low computing complexity, but also achieve nearly equivalent performance to the upper bound.
---
paper_title: Linear time distributed construction of colored trees for disjoint multipath routing

paper_content:

Disjoint multipath routing (DMPR) is an effective strategy to achieve robustness in networks where data is forwarded along multiple link- or node-disjoint paths. DMPR poses significant challenges in terms of obtaining loop-free multiple (disjoint) paths and effectively forwarding data over the multiple paths, the latter being particularly significant in datagram networks. One approach to reduce the number of routing table entries for disjoint multipath forwarding is to construct two trees, namely red and blue, rooted at a destination node such that the paths from a source to the destination on the two trees are link/node-disjoint. This paper develops the first distributed algorithm for constructing the colored trees whose running time is linear in the number of links in the network. The paper also demonstrates the effectiveness of employing generalized low-point concept rather than traditional low-point concept in the DFS-tree to reduce the average path lengths on the colored trees.
---
paper_title: A survey of resilience differentiation frameworks in communication networks

paper_content:

Unintentional failures affect links and nodes in communication networks. Recovery mechanisms are the key tool for achieving the dependability required by the services using the network. However, high dependability in communication networks comes at a high cost in terms of the capacity needed by these mechanisms.The traffic from all services and users is carried by the same backbone network. Since the users and services have different requirements, and users have different willingness to pay for a high quality of service, it is desirable to have methods that enable provision of different levels of dependability in the same network, i.e. dependability differentiation. The thesis addresses dependability differentiation in connection-oriented backbone communication networks. Two methods to provide connections meeting differentiated guarantees on the asymptotic availability are proposed.The first of these uses a novel flexible arrangement for dedicated protection denoted a protection pattern. The protection pattern is used in a proposed distributed connection management system. The system is compared with alternative proposals based on centralized management and shows good performance. The second proposal uses shared protection, which may potentially use less resources in terms of bandwidth, but has higher complexity than dedicated protection. The proposed system is based on rules to control the sharing to enable provision of guarantees. Simulation results show that the proposed method performs significantly better than an alternative strategy based on dedicated protection.A different approach to availability-guaranteed services is to offer guarantees on the interval availability which is a measure commonly used Service Level Agreements (SLAs). The thesis contains a proposal of using adaptive management to increase compliance with interval availability guarantees. Different adaptive management policies are proposed and compared to alternative static provisioning policies in a case study. The thesis also addresses the problem of measuring dependability by simulation. To reduce the simulation effort needed to obtain precise estimates of dependability attributes, a rare-event simulation technique has been applied to the well-known Network Simulator 2 (NS2). The results show that the technique is applicable to this types of simulation scenario, but the gain is modest. The thesis also contains a broad literature survey of dependability differentiation research. This is the first survey of the topic. Hence, it is in itself a significant contribution. A classification scheme for how to approach differentiation is proposed and a critical evaluation of the state of art is given.This thesis contributes to fill in some of the ``gaps'' identified, but there are still significant challenges ahead before differentiation may be deployed in operational networks.
---
paper_title: Faster Algorithms for Construction of Recovery Trees Enhancing QoP and QoS

paper_content:

Medard et al. proposed an elegant recovery scheme (known as the MFBG scheme) using red/blue recovery trees for multicast path protection against single link or node failures. Xue et al. extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric for multifailure recovery capabilities of single failure recovery schemes. They also presented polynomial time algorithms to construct recovery trees with good QoP and quality of service (QoS). In this paper, we present faster algorithms for constructing recovery trees with good QoP and QoS performance. For QoP enhancement, our O(n + m) time algorithm has comparable performance with the previously best O(n2(n + m)) time algorithm, where n and m denote the number of nodes and the number of links in the network, respectively. For cost reduction, our O(n + m) time algorithms have comparable performance with the previously best O(n2(n + m)) time algorithms. For bottleneck bandwidth maximization, our O(m log n) time algorithms improve the previously best O(nm) time algorithms. Simulation results show that our algorithms significantly outperform previously known algorithms in terms of running time, with comparable QoP or QoS performance.
---
paper_title: Distributed algorithms for computing shortest pairs of disjoint paths

paper_content:

Distributed algorithms for finding two disjoint paths of minimum total length from each node to a destination are presented. The algorithms have both node-disjoint and link-disjoint versions and provide each node with information sufficient to forward data on the disjoint paths. It is shown that this problem can be reduced to the problem of finding a minimal shortest path from each node to the destination in a modified network, and a distributed algorithm on the original network that simulates a shortest-paths algorithm running on the modified network is presented. The algorithm has a smaller space complexity than any previous distributed algorithm for the same problem, and a method for forwarding packets is presented that does not require any additional space complexity. A synchronous implementation of the algorithm is also presented and studied. >
---
paper_title: Maximum algebraic connectivity augmentation is NP-hard

paper_content:

The algebraic connectivity of a graph, which is the second-smallest eigenvalue of the Laplacian of the graph, is a measure of connectivity. We show that the problem of adding a specified number of edges to an input graph to maximize the algebraic connectivity of the augmented graph is NP-hard.
---
paper_title: Disjoint paths in a network

paper_content:

Routes between two given nodes of a network are called diversified if they are node-disjoint, except at the terminals. Diversified routes are required for reliability in communication, and an additional criterion is that their total cost, assumed to be the sum of individual arc lengths or costs, is minimum. An algorithm and related theory is described for a general number K of node-disjoint paths with minimum total length. The algorithm applies shortest path labeling algorithms familiar in the literature. K node-disjoint paths are found in K iterations of a single shortest path algorithm.
---
paper_title: The Combinatorics of Network Reliability

paper_content:

Preliminaries Exact algorithms The computational complexity of reliability problems Exact algorithms for restricted classes The reliability polynominal Edge-disjoint subgraphs Additive and multiplicative improvements Combining the bounds The k-cycle bound Computational results References Index.
---
paper_title: Quality-of-service routing using maximally disjoint paths

paper_content:

We apply and evaluate a new efficient algorithm for finding maximally link disjoint pairs of paths in a network. We apply this algorithm for QoS routing in connection-oriented networks that support calls with multiple QoS requirements. Our algorithm (called MADSWIP) is applied for precomputing paths in advance of call arrivals. Through simulations, we compare our QoS routing method to another method that is typical of what a switch vendor might implement today. We then examine the performance of three different policies for selecting a path among multiple potential paths. We also study the effects of decreasing the density of a network topology. We study two styles of topologies: commercial-style and random topologies. We demonstrate that precomputing paths that have minimal overlap is more important than precomputing paths that explicitly address all QoS metrics in a network. We also show that load balancing policies outperform call packing policies in networks that support diverse applications.
---
paper_title: Quality-of-service and quality-of-protection issues in preplanned recovery schemes using redundant trees

paper_content:

We study quality-of-service (QoS) and quality-of-protection (QoP) issues in redundant tree based preplanned recovery schemes for a single-link failure in two-edge connected graphs and for a single-node failure in two-connected graphs. We present schemes (to be called G-MFBG schemes) that generalize the schemes (to be called MFBG schemes) developed by Me/spl acute/dard et al. (1997) to construct a pair of redundant trees, called red and blue trees, which guarantees fast recovery from any single-link/node failure, as long as the failed node is not the root node. Using the G-MFBG schemes, we study QoS issues relating to red/blue trees. We present effective heuristics for computing a pair of redundant trees with low average delay or small total cost. We develop an optimal algorithm for computing a pair of red/blue trees with maximum bandwidth. Furthermore, a pair of red/blue trees guarantees fast recovery from simultaneous multiple failures if it satisfies certain properties. This leads us to define the concept of QoP of a pair of red/blue trees. We present an effective heuristic to construct a pair of red/blue trees with high QoP. The paper concludes with a discussion of computational results that demonstrate the effectiveness of the different algorithms presented.
---
paper_title: A quick method for finding shortest pairs of disjoint paths

paper_content:

Let G be a directed graph containing n vertices, one of which is a distinguished source s, and m edges, each with a non-negative cost. We consider the problem of finding, for each possible sink vertex v, a pair of edge-disjoint paths from s to v of minimum total edge cost. Suurballe has given an O(n2 logn)-time algorithm for this problem. We give an implementation of Suurballe's algorithm that runs in O(m log(1+ m/n)n) time and O(m) space. Our algorithm builds an implicit representation of the n pairs of paths; given this representation, the time necessary to explicitly construct the pair of paths for any given sink is O(1) per edge on the paths.
---
paper_title: Reliability constrained routing in QoS networks

paper_content:

The issue of handling network failures is becoming increasingly important. In this paper, we address the problem of constrained routing by treating reliability as one of the QoS requirements. The problem is to create a feasible path from a given node to the destination such that the bandwidth and reliability requirements of the path are satisfied and the cost of the path is minimized (Reliability Constrained Least Cost Routing Problem). To solve the problem, we propose an approach which employs a novel concept, called partial protection, wherein backup paths are created for a selected set of domains in the network so as to meet the reliability constraints. The Partial Protection Approach (PPA) has two steps: Primary Path Creation and Backup Path Creation if necessary. To implement PPA, we propose three scalable two-pass resource reservation schemes, viz., Conservative, Optimistic, and Hybrid schemes. These schemes differ depending on whether the backup paths are created during the forward pass, reverse pass, or both. We evaluate the performance of the proposed schemes for dynamic multicast groups with different bandwidth and reliability requirements using average call acceptance rate and average tree cost as performance metrics. Our studies show that group dynamics and reliability requirements have significant impact on the performance of the schemes.
---
paper_title: Finding minimum-cost circulations by canceling negative cycles

paper_content:

A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and <italic>canceling</italic> it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in &Ogr;(<italic>nm</italic>(log <italic>n</italic>)min{log(<italic>nC</italic>), <italic>m</italic> log <italic>n</italic>}) time on a network of <italic>n</italic> vertices, <italic>m</italic> arcs, and arc costs of maximum absolute value <italic>C</italic>. This bound is comparable to those of the fastest previously known algorithms.
---
paper_title: A comparison of exact and ε-approximation algorithms for constrained routing

paper_content:

The Constrained Routing Problem is a multi-criteria optimization problem that captures the most important aspects of Quality of Service routing, and appears in many other practical problems. The problem is NP-hard, which causes exact solutions to require an intractable running time in the worst case. e -approximation algorithms provide a guaranteed approximate solution for all inputs while incurring a tractable (i.e., polynomial) computation time. This paper presents a performance evaluation of these two types of algorithms. The main performance criteria are accuracy and speed.
---
paper_title: Quality-of-service routing using maximally disjoint paths

paper_content:

We apply and evaluate a new efficient algorithm for finding maximally link disjoint pairs of paths in a network. We apply this algorithm for QoS routing in connection-oriented networks that support calls with multiple QoS requirements. Our algorithm (called MADSWIP) is applied for precomputing paths in advance of call arrivals. Through simulations, we compare our QoS routing method to another method that is typical of what a switch vendor might implement today. We then examine the performance of three different policies for selecting a path among multiple potential paths. We also study the effects of decreasing the density of a network topology. We study two styles of topologies: commercial-style and random topologies. We demonstrate that precomputing paths that have minimal overlap is more important than precomputing paths that explicitly address all QoS metrics in a network. We also show that load balancing policies outperform call packing policies in networks that support diverse applications.
---
paper_title: Quality of protection (QoP): a quantitative unifying paradigm to protection service grades

paper_content:

In this paper we discuss a quantitative framework for best- effort protection of the optical layer. This framework provides a way to bridge the gap between two known protection grades of fully protected connections vis-a-vis unprotected protection. The framework allows to specify the probability with which the connection will be protected, providing the customer with a full range of protection guarantees at possibly different prices. Since connections may be partially protected, the required protection bandwidth can be reduced. The amount of protection bandwidth is shown to depend on an 'equivalent survivable bandwidth.' The framework also extends to preemptable (low priority) connections and to different ring architectures.
---
paper_title: Routing connections with differentiated reliability requirements in WDM mesh networks

paper_content:

Reliability has been well recognized as an important design objective in the design of modern high-speed networks. While traditional approaches offer either 100% protection in the presence of single link failure or no protection at all, connections in real networks may have multiple reliability requirements. The concept of differentiated reliability (DiR) has been introduced in the literature to provide multiple reliability requirements in protection schemes that provision spare resources. In this paper, we consider the problem of routing connections with differentiated reliability in wavelength-division multiplexing (WDM) mesh networks when backup sharing is not allowed. Our objective is to route connections with minimum network cost (e.g., network resources) while meeting their required reliability. We assume connections arrive dynamically one-at-a-time and a decision as to accept or reject a connection has to be made without a priori knowledge of future arrivals. Since sharing cannot be used for achieving efficiency, the goal is to achieve efficiency by improved path selection. In this paper, we first present an integer linear programming (ILP) formulation for the problem. By solving the ILP formulation, we can obtain an optimal solution with respect to the current network state for each dynamic arrival. To solve the ILP formulation, however, is time consuming for large networks. We thus propose two approximation algorithms for the problem. The first one, called Shortest-Path-Pair-based Auxiliary graph (SPPA), can obtain an epsiv-approximation solution whose cost is at most 1 + epsiv times the optimum in O((n2(n + 1) + 2mn)(log log(2n) + 1/epsiv)) time, where n and m are the number of nodes and links in a network, respectively. To reduce the computational complexity of the first algorithm, the second algorithm, called Auxiliary graph-based Two-Step Approach (ATSA), is proposed and can obtain a near optimal solution with cost at most 2 + epsiv times that of the optimal solution in O(mn(log log n + 1/epsiv)) time. Results from extensive simulations conducted on two typical carrier mesh networks show the efficiency of the two algorithms.
---
paper_title: The power of tuning: a novel approach for the efficient design of survivable networks

paper_content:

Current survivability schemes typically offer two degrees of protection, namely full protection (from a single failure) or no protection at all. Full protection translates into rigid design constraints, i.e. the employment of disjoint paths. We introduce the concept of tunable survivability that bridges the gap between full and no protection. First, we establish several fundamental properties of connections with tunable survivability. With that at hand, we devise efficient polynomial (optimal) connection establishment schemes for both 1:1 and 1+1 protection architectures. Then, we show that the concept of tunable survivability gives rise to a novel hybrid protection architecture, which offers improved performance over the standard 1:1 and 1+1 architectures. Next, we investigate some related QoS extensions. Finally, we demonstrate the advantage of tunable survivability over full survivability. In particular, we show that, by just slightly alleviating the requirement of full survivability, we obtain major improvements in terms of the "feasibility" as well as the "quality" of the solution.
---
paper_title: How Reliable Can Two-Path Protection Be?

paper_content:

This paper investigates the subject of reliability via two link-disjoint paths in mesh networks. We address the issues of how reliable two-path protection can be and how to achieve the maximum reliability. This work differs from traditional studies, such as MIN-SUM, MIN-MAX, and MIN-MIN, in that the objective in this paper is to maximize the reliability of the two-path connection given the link reliability, or equivalently, to minimize the end-to-end failure probability. We refer to this problem as MAX-REL. Solving MAX-REL provides 100% protection against a single failure while maximizing the reliability regardless of how many link failures occur in the network. We prove that this problem is NP-complete and derive a corresponding upper bound, which is the theoretical maximum reliability for a source-destination pair, and a lower bound, which is the worst case of the proposed algorithm. The time efficiency of the algorithms is analyzed, and the performance of the algorithms is evaluated through simulation. We demonstrate that our heuristic algorithms not only achieve a low computing complexity, but also achieve nearly equivalent performance to the upper bound.
---
paper_title: Graph transformation approaches for diverse routing in shared risk resource group (SRRG) failures

paper_content:

Failure resilience is a desired feature of the Internet. Most traditional restoration architectures assume single failure assumption, which is not adequate in present day WDM optical networks. Multiple link failure models, in the form of shared risk link groups (SRLG's) and shared risk node groups (SRNG's) are becoming critical in survivable optical network design. We classify both of these form of failures under a common scenario of shared risk resource groups (SRRG) failures. We develop graph transformation techniques for tolerating multiple failures arising out of shared resource group (SRRG) failures. Diverse routing in such multi-failure scenario essentially necessitates finding out two paths between a source and a destination that are SRRG disjoint. The generalized diverse routing problem has been proved to be NP-Complete. The proposed transformation techniques however provides a polynomial time solution for certain restrictive failure sets. We study how restorability can be achieved for dependent or shared risk link failures and multiple node failures and prove the validity of our approach for different network scenarios. Our proposed technique is capable of improving the diverse route computation by around 20-30% as compared to approaches proposed in the literature.
---
paper_title: Region-based connectivity - a new paradigm for design of fault-tolerant networks

paper_content:

The studies in fault-tolerance in networks mostly focus on the connectivity of the graph as the metric of faulttolerance. If the underlying graph is k-connected, it can tolerate up to k — 1 failures. In measuring the fault tolerance in terms of connectivity, no assumption regarding the locations of the faulty nodes are made - the failed nodes may be close to each other or far from each other. In other words, the connectivity metric has no way of capturing the notion of locality of faults. However in many networks, faults may be highly localized. This is particularly true in military networks, where an enemy bomb may inflict massive but localized damage to the network. To capture the notion of locality of faults in a network, a new metric region-based connectivity (RBC) was introduced in [1]. It was shown that RBC can achieve the same level of fault-tolerance as the metric connectivity, with much lower networking resources. The study in [1] was restricted to single region fault model (SRFM), where faults are confined to one region only. In this paper, we extend the notion of RBC to multiple region fault model (MRFM), where faults are no longer confined to a single region. As faults in MRFM are still confined to regions, albeit multiple of them, it is different from unconstrained fault model where no constraint on locality of faults is imposed. The MRFM leads to several new concepts, such as region-disjoint paths and region cuts. We show that the classical result, the maximum number of node-disjoint paths between a pair of nodes is equal to the minimum number of nodes whose removal disconnects the pair, is no longer valid when region-disjoint paths and region cuts are considered. We prove that the problems of finding (i) the maximum number of region-disjoint paths between a pair of nodes, and (ii) minimum number of regions whose removal disconnect a pair of nodes, are both NP-complete. We provide heuristic solution to these two problems and evaluate their efficacy by comparing the results with optimal solutions.
---
paper_title: Shared risk resource group complexity and approximability issues

paper_content:

This article investigates complexity and approximability properties of combinatorial optimization problems yielded by the notion of Shared Risk Resource Group (SRRG). SRRG has been introduced in order to capture network survivability issues where a failure may break a whole set of resources, and has been formalized as colored graphs, where a set of resources is represented by a set of edges with same color. We consider here the analogous of classical problems such as determining paths or cuts with the minimum numbers of colors or color disjoint paths. These optimization problems are much more difficult than their counterparts in classical graph theory. In particular standard relationship such as the Max Flow - Min Cut equality do not hold any longer. In this article we identify cases where these problems are polynomial, for example when the edges of a given color form a connected subgraph, and otherwise give hardness and non approximability results for these problems.
---
paper_title: The resilience of WDM networks to probabilistic geographical failures

paper_content:

Telecommunications networks, and in particular optical WDM networks, are vulnerable to large-scale failures of their physical infrastructure, resulting from physical attacks (such as an Electromagnetic Pulse attack) or natural disasters (such as solar flares, earthquakes, and floods). Such events happen at specific geographical locations and disrupt specific parts of the network but their effects are not deterministic. Therefore, we provide a unified framework to model the network vulnerability when the event has a probabilistic nature, defined by an arbitrary probability density function. Our framework captures scenarios with a number of simultaneous attacks, in which network components consist of several dependent subcomponents, and in which either a 1+1 or a 1∶1 protection plan is in place. We use computational geometric tools to provide efficient algorithms to identify vulnerable points within the network under various metrics. Then, we obtain numerical results for specific backbone networks, thereby demonstrating the applicability of our algorithms to real-world scenarios. Our novel approach allows for identifying locations which require additional protection efforts (e.g., equipment shielding). Overall, the paper demonstrates that using computational geometric techniques can significantly contribute to our understanding of network resilience.
---
paper_title: Trap avoidance and protection schemes in networks with shared risk link groups

paper_content:

Shared risk link group (SRLG) has been widely recognized as an important concept in survivable optical networks. However, there are still several SRLG-related problems of both theoretical interest and practical importance that have not been explored fully. Specifically, there are two major issues that are still open: avoiding failures in path determination caused by "traps" and maximizing bandwidth sharing. These issues are more challenging when considering shared path protection in networks with SRLGs. In this paper, we address the above two open issues, starting with a heuristic approach to avoiding traps. In networks with SRLGs, a simple heuristic may run into traps up to 30% of the time. Integer linear programming (ILP)-based approaches, on the other hand, are not feasible for large SRLG networks. One of the widely used heuristics for trap avoidance is based on K shortest paths (KSP). As an alternative to KSP, we propose an innovative trap avoidance (TA) heuristic that requires much less running time than KSP (and ILP) and yet can effectively avoid almost all the avoidable traps as an ILP-based approach. We also propose an efficient shared SRLG protection scheme based on TA that can achieve a bandwidth efficiency that is nearly as high as other schemes based on ILP or KSP.
---
paper_title: Path-Protection Routing and Wavelength Assignment (RWA) in WDM Mesh Networks Under Duct-Layer Constraints

paper_content:

This study investigates the problem of fault management in a wavelength-division multiplexing (WDM)-based optical mesh network in which failures occur due to fiber cuts. In reality, bundles of fibers often get cut at the same time due to construction or destructive natural events, such as earthquakes. Fibers laid down in the same duct have a significant probability to fail at the same time. When path protection is employed, we require the primary path and the backup path to be duct-disjoint, so that the network is survivable under single-duct failures. Moreover, if two primary paths go through any common duct, their backup paths cannot share wavelengths on common links. This study addresses the routing and wavelength-assignment problem in a network with path protection under duct-layer constraints. Off-line algorithms for static traffic is developed to combat single-duct failures. The objective is to minimize total number of wavelengths used on all the links in the network. Both integer linear programs and a heuristic algorithm are presented and their performance is compared through numerical examples.
---
paper_title: Diverse Routing in Networks With Probabilistic Failures

paper_content:

We develop diverse routing schemes for dealing with multiple, possibly correlated, failures. While disjoint path protection can effectively deal with isolated single link failures, recovering from multiple failures is not guaranteed. In particular, events such as natural disasters or intentional attacks can lead to multiple correlated failures, for which recovery mechanisms are not well understood. We take a probabilistic view of network failures where multiple failure events can occur simultaneously, and develop algorithms for finding diverse routes with minimum joint failure probability. Moreover, we develop a novel Probabilistic Shared Risk Link Group (PSRLG) framework for modeling correlated failures. In this context, we formulate the problem of finding two paths with minimum joint failure probability as an integer nonlinear program (INLP) and develop approximations and linear relaxations that can find nearly optimal solutions in most cases.
---
paper_title: Critical regions and region-disjoint paths in a network

paper_content:

Due to the importance of communication networks to society, it is pertinent that these networks can withstand failures. Improving the robustness of a network usually requires installing redundant resources, which is very costly. Network providers are consequently less inclined to take robustness measures against failures that are unlikely to manifest, like several failures coinciding simultaneously in different geographic regions of their network. Protecting against single regional failures is more realistic. Network robustness, in terms of connectivity properties, also requires survivability algorithms to quickly reroute traffic affected by a network failure. In this paper, we consider a network embedded in a plane and study the problem of finding a circular region with radius r in that plane that would cause the biggest network degradation if all nodes within that particular region were to be destroyed. We propose a polynomial time algorithm for finding such critical regions. In addition, we develop a region-aware network augmentation technique to decrease the impact of a critical region failure. We subsequently consider the region-disjoint paths problem, which asks for two paths with minimum total weight between a source (s) and a destination (d) that cannot both be cut by a single circular regional failure of radius r (unless that failure includes s and d). We prove that the region-disjoint paths problem is NP-hard and propose and evaluate a heuristic algorithm for it.
---
paper_title: Diverse routing in WDM optical networks with shared risk link group (SRLG) failures

paper_content:

We study the diverse routing problem in WDM optical networks with SRLG failures. We consider a more general case of SRLG failures than those considered in Datta and Somani (2004) and Doucette and Grover (2002). All the optical links in an SRLG share a common endpoint. In addition, a link can belong to arbitrary number of SRLG groups and an SRLG may include more than two links. We develop a polynomial time optimal algorithm to find a pair of least cost SRLG-disjoint paths between a source and a destination. We prove the correctness of the algorithm which is also shown to be more time efficient than the graph transformation based algorithm of Datta and Somani (2004).
---
paper_title: Survivable Networks: Algorithms for Diverse Routing

paper_content:

From the Publisher: ::: Survivable Networks: Algorithms for Diverse Routingprovides algorithms for diverse routing to enhance the survivabilityof a network. It considers the common mesh-type network and describesin detail the construction of physically disjoint paths algorithms fordiverse routing. The algorithms are developed in a systematic manner,starting with shortest path algorithms appropriate for disjoint pathsconstruction. Key features of the algorithms are optimality andsimplicity. Although the algorithms have been developed forsurvivability of communication networks, they are in a generic form,and thus applicable in other scientific and technical disciplines toproblems that can be modeled as a network. ::: ::: A notable highlight of this book is the consideration of real-lifetelecommunication networks in detail. Such networks are described notonly by nodes and links, but also by the actual physical elements,called span nodes and spans. The sharing of spans (the actual physicallinks) by the network (logical) links complicates the network,requiring new algorithms. This book is the first one to providealgorithms for such networks. ::: ::: Survivable Networks: Algorithms for Diverse Routing is acomprehensive work on physically disjoint paths algorithms. It is aninvaluable resource and reference for practicing network designers andplanners, researchers, professionals, instructors, students, andothers working in computer networking, telecommunications, and relatedfields.
---
paper_title: On-line survivable routing in WDM networks

paper_content:

In WDM networks, survivable routing and wavelength assignment (SRWA) involves assigning link-disjoint primary and backup lightpaths. In the on-line SRWA problem, a sequence of requests arrive and each request is either accepted or rejected based only on the input sequence seen so far. For special networks, we establish on-line algorithms with constant and logarithmic competitive ratios. It is not possible to obtain good competitive ratios in general topologies. Hence, we propose heuristic schemes and evaluate their performance by way of simulations. The building blocks in these schemes are 2-approximation algorithms (MSA and ESA) that we establish for the minimum disruption link-disjoint paths (MDLDP) problem. These approximations require far less memory and computation time than the best-known exact solution of the MDLDP problem. We use these three algorithms as heuristics for the on-line SRWA problem for infinite and finite duration requests and we show that, in terms of on-line performance, our algorithms do as well as (even at times better than) the exact algorithm of the MDLDP problem. We also provide an exact ILP formulation to solve the infinite duration off-line SRWA problem.
---
paper_title: Survivable impairment-aware traffic grooming in WDM rings

paper_content:

Wavelength Division Multiplexing (WDM) optical networks offer a large amount of bandwidth using multiple, but independent wavelength channels (or lightpaths), each operating at several Gb/s. Since the traffic between users is usually only a fraction of the capacity offered by a wavelength, several independent traffic streams can be groomed together. In addition, in order to reverse the effect of noise and signal degradations (physical impairments), optical signals need to be regenerated after a certain impairment threshold is reached. We consider survivable impairment-aware traffic grooming in WDM rings, which are among the most widely deployed optical network topologies. We first show that the survivable impairment-aware traffic grooming problem, where the objective is to minimize the total cost of grooming and regeneration, is NP-hard. We then provide approximation algorithms (for uniform traffic), and efficient heuristic algorithms whose performance is shown to be close to the lower-bounds (for non-uniform traffic) both when (1) the impairment threshold can be ignored, and (2) the impairment threshold should be considered.
---
paper_title: Survivable impairment-aware traffic grooming

paper_content:

Traffic grooming allows efficient utilization of network capacity by aggregating several independent traffic streams into a wavelength. In addition, survivability and impairment-awareness (i.e., taking into account the effect of physical impairments) are two important issues that have gained a lot of research interest in the area of optical networks. In this paper, we consider the survivable impairment-aware traffic grooming problem in Wavelength Division Multiplexing (WDM) optical networks, where the objective is to minimize the cost of traffic grooming and regeneration. Our approach to solve this problem is shown, using data obtained from a realistic network, to significantly outperform a sequential approach, which is usually used by practitioners.
---
paper_title: Survivable routing and regenerator placement in optical networks

paper_content:

The large capacity of WDM optical networks facilitates the transportation of impressive volumes of traffic, which make survivability schemes that can reroute traffic upon a failure in the network highly important. Besides survivability, the signal quality in optical networks, which degrades along its path due to physical impairments, needs consideration. In this paper, we consider the design problem of where to place regenerators in the network such that both the primary and backup lightpaths for a (predicted) traffic matrix obey the impairment constraints. We study the survivable routing and regenerator placement problem under dedicated and shared protection schemes, analyze the complexity of both problem variants, and subsequently propose efficient algorithms to solve or approximate them.
---

Title: An Overview of Algorithms for Network Survivability

Section 1: Introduction
Description 1: Introduce the significance of network survivability and outline the key ingredients for achieving survivability in networks.

Section 2: Network Connectivity
Description 2: Describe the concept of network connectivity, including definitions of k-connectivity, link connectivity, node connectivity, and algebraic connectivity, and discuss their relevance to network survivability.

Section 3: Network Augmentation
Description 3: Discuss methods for augmenting network connectivity, including the addition of links or nodes, and explore the complexity of various augmentation problems.

Section 4: Path Protection
Description 4: Cover different schemes for path protection and restoration, including proactive and reactive mechanisms, and discuss the algorithms used to precompute disjoint paths for efficient rerouting.

Section 5: Determining Network Connectivity
Description 5: Explain methods to determine network connectivity, including algorithms to find minimum cuts and their computational complexities.

Section 6: Link Connectivity Augmentation
Description 6: Review algorithms and techniques to augment link connectivity, including NP-hard problems and approximation algorithms.

Section 7: Node Connectivity Augmentation
Description 7: Examine algorithms for augmenting node connectivity and discuss known results and complexities involved in increasing node connectivity.

Section 8: Disjoint Paths
Description 8: Detail algorithms for finding disjoint paths in a network to ensure alternate routes in case of failures, covering several problem types and their complexities.

Section 9: Probabilistic Survivability
Description 9: Discuss probabilistic models for network survivability, including algorithms to establish connections with a certain reliability and the min-sum p-survivable connection problem.

Section 10: Multiple Failures
Description 10: Address the challenges and algorithms related to surviving multiple failures, including SRLG-disjoint paths and geographic max-flow and min-cut problems.

Section 11: Conclusion
Description 11: Summarize the key points covered in the paper and the importance of algorithms in ensuring network survivability across various scenarios.