Approximation Algorithms for Survivable Multicommodity Flow Problems with Applications to Network Design

Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time solvable while integer versions are NP-complete. However, exact algorithms to solve the fractional MF problems have high computational complexity. Therefore approximation algorithms to solve the fractional MF problems have been explored in the literature to reduce their computational complexity. Using these approximation algorithms and the randomized rounding technique, polynomial time approximation algorithms have been explored in the literature. In the design of high-speed networks, such as optical wavelength division multiplexing (WDM) networks, providing survivability carries great significance. Survivability is the ability of the network to recover from failures. It further increases the complexity of network design and presents network designers with more formidable challenges. In this work we formulate the survivable versions of the MF problems. We build approximation algorithms for the survivable multicommodity flow (SMF) problems based on the framework of the approximation algorithms for the MF problems presented in [1] and [2]. We discuss applications of the SMF problems to solve survivable routing in capacitated networks.

Least-cost Disjoint Paths with Dependent Cost Structure in Wavelength Continuous Optical WDM Networks

One of the important issues in establishing a fault tolerant connection in a wavelength division multiplexing optical network is computing a pair of disjoint working and protection paths and a free wavelength along the paths. While most of the earlier research focused only on computing disjoint paths, in this work we consider computing both disjoint paths and a free wavelength along the paths. The concept of dependent cost structure (DCS) of protection paths to enhance their resource sharing ability was proposed in our earlier work. In this work we extend the concept of DCS of protection paths to wavelength continuous networks. We formalize the problem of computing disjoint paths with DCS in wavelength continuous networks and prove that it is NP-complete. We present an iterative heuristic that uses a layered graph model to compute disjoint paths with DCS and identify a free wavelength.

Survivable Traffic Grooming with Path Protection at the Connection Level in WDM Mesh Networks

Survivable traffic grooming (STG) is a promising approach to provide reliable and resource-efficient multigranularity connection services in wavelength division multiplexing (WDM) optical networks. In this paper, we study the STG problem in WDM mesh optical networks employing path protection at the connection level. Both dedicated protection and shared protection schemes are considered. Given the network resources, the objective of the STG problem is to maximize network throughput. To enable survivability under various kinds of single failures such as fiber cut and duct cut, we consider the general shared risk link group (SRLG) diverse routing constraints. We first resort to the integer linear programming (ILP) approach to obtain optimal solutions. To address its high computational complexity, we then propose three efficient heuristics, namely separated survivable grooming algorithm (SSGA), integrated survivable grooming algorithm (ISGA) and tabu search survivable grooming algorithm (TSGA). While SSGA and ISGA correspond to an overlay network model and a peer network model respectively, TSGA further improves the grooming results from SSGA and ISGA by incorporating the effective tabu search method. Numerical results show that the heuristics achieve comparable solutions to the ILP approach, which uses significantly longer running times than the heuristics.

Dynamic traffic grooming algorithms for reconfigurable SONET over WDM networks

The emergence of Wavelength Division Multiplexing (WDM) technology provides the capability for increasing the bandwidth of Synchronous Optical Network (SONET) rings by grooming low-speed traffic streams onto different high-speed wavelength channels. Since the cost of SONET add-drop multiplexers (SADM) at each node dominates the total cost of these networks, how to assign the wavelength, groom in the traffic and bypass the traffic through the intermediate nodes has received a lot of attention from researchers recently.

Optimization of Amplifier Placements in Switch-Based Optical Networks

Wavelength division multiplexing (WDM) offers a solution to the problem of exploiting the large bandwidth on optical links; it is the current favorite multiplexing technology for optical communication networks. Due to the high cost of an optical amplifier, it is desirable to strategically place the amplifiers throughout the network in a way that guarantees that all the signals are adequately amplified while minimizing the total number amplifiers being used. Previous studies all consider a star-based network. This paper demonstrates an original approach for solving the problem in switch-based WDM optical network assuming the traffic matrix is always the permutation of the nodes. First we formulate the problem by choosing typical permutations which can maximize traffic load on individual links; then a GA (Genetic Algorithm) is used to search for feasible amplifier placements. Finally, by setting up all the lightpaths without violating the power constaints we confirm the feasibility of the solution.