A heuristic method for self-healing ring design in a single-homing cluster

In this paper, we consider a SONET (Synchronous Optical NETwork) USHR (Uni- directional Self-Healing Ring) design problem for a single-homing cluster, i.e., a cluster with a single designated hub. The problem is formulated as a nonlinear integer programming problem and a branch and bound heuristic me thod based on the Lagrangian relaxation and subgradient optimization techni que is proposed to handle the problem. In solving any ring design problem, we should deal with two different aspects of the ring design, namely, the r ing routing aspect and the ring loading aspect. Both of these two aspects a re well integrated and represented in our model. Such an integrated formula tion has not been proposed in the existing literature mainly due to its com putationally intractable complexity. In order to cope with such complexity, a preprocessing technique for reducing the complexity and several branch a nd bound strategies are proposed. The efficiency of the proposed method is tested through computational experiments. For the computational experiments , test problems are generated using the data obtained from the actual topol ogies in Seoul, Korea. The computational experiments show that the proposed method yields near-optimum designs within reasonable computation time.