%0 Journal Article
%T An Overview of Algorithms for Network Survivability
%A F. A. Kuipers
%J ISRN Communications and Networking
%D 2012
%R 10.5402/2012/932456
%X Network survivability¡ªthe ability to maintain operation when one or a few network components fail¡ªis indispensable for present-day networks. In this paper, we characterize three main components in establishing network survivability for an existing network, namely, (1) determining network connectivity, (2) augmenting the network, and (3) finding disjoint paths. We present a concise overview of network survivability algorithms, where we focus on presenting a few polynomial-time algorithms that could be implemented by practitioners and give references to more involved algorithms. 1. Introduction Given the present-day importance of communications systems and infrastructures in general, networks should be designed and operated in such a way that failures can be mitigated. Network nodes and/or links might for instance fail due to malicious attacks, natural disasters, unintentional cable cuts, planned maintenance, equipment malfunctioning, and so forth. Resilient, fault tolerant, survivable, reliable, robust, and dependable, are different terms that have been used by the networking community to capture the ability of a communications system to maintain operation when confronted with network failures. Unfortunately, the terminology has overlapping meanings or contains ambiguities, as pointed out by Al-Kuwaiti et al. [1]. In this paper, we will use the term survivable networks to refer to networks that, when a component fails, may ¡°survive¡± by finding alternative paths that circumvent the failed component. Three ingredients are needed to reach survivability.(1) Network connectivity, that is, the network should be well connected (connectivity properties are discussed in Section 1.1).(2) Network augmentation, that is, new links may need to be added to increase the connectivity of a network.(3) Path protection, that is, a procedure to find alternative paths in case of failures. These three ingredients will be explained in the following sections. 1.1. Network Connectivity A network is often represented as a graph , where is the set of nodes (which for instance represent routers) and is the set of links (which for instance represent optical fiber lines or radio channels). Links may be characterized by weights representing for instance their capacity, delay, length, cost, and/or failure probability. A graph is said to be connected if there exists a path between each pair of nodes in the graph, else the graph is said to be disconnected. In the context of survivability, the notion of connectivity may be further specified as -connectivity, where at least disjoint paths
%U http://www.hindawi.com/journals/isrn.communications.networking/2012/932456/