DocumentCode :
341041
Title :
Modelling, algorithms, and analysis of survivable VP planning in ATM networks
Author :
Wu, Cheng-Shong ; Lee, Shi-Wei
Author_Institution :
Dept. of Electr. Eng., Nat. Chung-Cheng Univ., Chia-Ti, Taiwan
Volume :
3
fYear :
1998
fDate :
1998
Firstpage :
1741
Abstract :
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 is to minimize the resource usage while maximizing the network survivability. By proper transformation of the objective function and applying the cutting plane method, the original formulation is transformed into an integer linear program 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. By assessing the gap between the heuristic upper bounds and the Lagrangian lower bounds, we find that our algorithm can efficiently provide a near optimal solution for the survivable VP layout design in ATM networks
Keywords :
asynchronous transfer mode; combinatorial mathematics; integer programming; linear programming; minimisation; telecommunication network planning; telecommunication network reliability; telecommunication network routing; ATM network; Lagrangian lower bounds; Lagrangian relaxation techniques; VP layout design; backup VP routing problem; candidate path set; cutting plane method; heuristic algorithms; heuristic upper bounds; integer linear program formulation; integer programming; network survivability maximization; nonlinear combinatorial optimization problem; objective function; resource usage minimization; survivable VP planning; system resource utilization; working VP routing problem; Algorithm design and analysis; Asynchronous transfer mode; Ear; Heuristic algorithms; Intelligent networks; Lagrangian functions; Routing; Switches; Telecommunication traffic; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Global Telecommunications Conference, 1998. GLOBECOM 1998. The Bridge to Global Integration. IEEE
Conference_Location :
Sydney,NSW
Print_ISBN :
0-7803-4984-9
Type :
conf
DOI :
10.1109/GLOCOM.1998.776683
Filename :
776683
Link To Document :
بازگشت