Preplanned rerouting optimization and dynamic path rerouting for ATM VP restoration

The survivability for ATM based B‐ISDN has become an important challenge for telecommunication network planners and engineers. In this paper, we consider multiple grades of reliability concept and a multilayer survivable network architecture for survivable ATM networks. We address two complementary ATM VP restoration schemes in this paper. First, we propose preplanned rerouting models and algorithms based on combinatorial optimization to prepare efficient backup VP configuration. We test two formulations and algorithms for this problem. Efficient column generation technique to solve linear programming relaxation and strong valid inequalities incorporating the branch‐and‐bound scheme are suitable to solve the problem to optimality within small time limits. Second, we propose a new dynamic VP path restoration scheme to restore nonprotected VPs by the preplanned rerouting. Our protocol has shown the advantage in restoration effectiveness comparing a well‐known protocol in computational simulation. We, finally, address the relationships between the suggested models of this paper and the expected results of our ongoing project. This revised version was published online in August 2006 with corrections to the Cover Date.