Fault-tolerance using shared path protection in wavelength division multiplexing optical transport networks

Wavelength division multiplexing (WDM) fiber optical networks in the future are intended to provide bandwidths in the range of 500-2000 Gbps with the number of wavelengths multiplexed onto a single fiber ranging from 100-200. The enormous bandwidth capacity of WDM networks have made fault-tolerance/survivability in these networks extremely important. The goal of fault-tolerant design of a network is to build a network that is resilient to failures such as link, node, fiber conduit, etc., that occur in a network. In this dissertation, we focus on three main issues, survivable virtual topology design, fault-tolerant routing in optical networks and static survivable network design. The objective of the survivable virtual topology design problem is to route a given virtual topology on the physical topology such that when single point failures occur in the physical network, the virtual topology is still connected. We propose a scalable solution to the survivable virtual topology problem. In our experiments we successfully computed survivable routing of 45-edge virtual topologies on physical topologies of sizes up to 24 nodes within 2 min. To provide fault-tolerance to a connection, one needs to compute a link/node diverse path pair between the source and destination nodes of the connection. Such a routing is called fault-tolerant routing. The path used for routing the traffic is called the working path and the other diverse path is called the backup path. To enable resource sharing among the backup paths of multiple fault-tolerant connections, we introduce and formalize the concept of dependent cost structure (DCS) of a backup path on its working path and current network status. We present an iterative heuristic to compute diverse path pairs and our simulations show that our heuristic greatly increases the resource sharing ability of backup paths and thus reduces blocked calls and resource consumption. The goal of the static survivable network design problem is to provision the given set of traffic demands in a network such as an optical WDM network or a high-speed capacitated network. We present approximation algorithms for three versions of survivable network design problems. To the best of our knowledge this is the first work that presents approximation algorithms to survivable network design problems