Optimization models for backup VP planning of multicast connections in ATM networks

In a previous paper (see Proc. IEEE ICC p.267-71, 1997) we studied several backup path building schemes for multicast connections in self-healing ATM networks. In this paper, optimization models and algorithms for backup VP preplanning of multicast connections are developed. They are formulated as combinatorial optimization problems in which the objective functions are the minimization of bandwidth usage and the constraints are required to satisfy the survivability and physical limitations. Lagrangian based and greedy based heuristic algorithms have been developed to obtain the sub-optimal feasible solutions of our problems efficiently. In addition, the Lagrangian lower bounds are used to assess the quality of our heuristic solutions. After testing several cases, the evaluation results together with the advantage and disadvantage of each scheme are reported and discussed.