For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Modeling, Algorithms and Analysis of Survivable VP Planning in ATM Networks
Cheng-Shong WU Shi-Wei LEE
IEICE TRANSACTIONS on Communications
Publication Date: 1999/04/25
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Communication Networks and Services
ATM, VP planning, survivability, lagrangian relaxation, decomposition,
Full Text: PDF>>
In this paper, we consider the working VP and backup VP routing problems jointly and employ the integer programming based approach to maximize the system resource utilization and the network survivability. The VP planning problem is formulated as a nonlinear combinatorial optimization problem. The objective function minimizes the resource usage while maximizing the network survivability. By proper transformation of the objective function and applying cutting plane method, the original formulation is transformed into an integer linear programing formulation which is suitable for applying Lagrangian relaxation techniques. After Lagrangian relaxation, the problem is further decomposed into several tractable subproblems. Unlike others' work, the candidate path set does not need to be prepared in advance and the best paths are generated while solving subproblems in our approach. Heuristic algorithms based on the solving procedure of the Lagrangian relaxation are developed. Closely examining the gap between the heuristic upper bounds and the Lagrangian lower bounds reveals that the proposed algorithm can efficiently provide a nearly optimal solution for the survivable VP layout design in ATM networks.