Optimal Cost Stacked Uni-Directional Path Switched SONET/SDH Ring Design

SONET/SDH rings appear to be well-positioned to serve as the transport network for the next generation of voice and data networks. The problem of designing optimal ring networks, however, poses considerable challenges. In this paper, we have formulated the optimal cost stacked uni-directional path switched (UPSR) ring design problem. Given a set of demands between nodes which are arranged in a fiber ring topology, the problem is one of designing multiple rings stacked on the topology to carry the nodal demands. This design is to be carried out in a manner to minimize the overall equipment cost which includes three major components: a nodal add/drop multiplexer cost, and express node cost and a fixed per ring cost. We have shown that this problem is NP-hard and have proposed adapted bin-packing and LP column generation based heuristics and a cost lower bound. In numerical studies, the hybrid bin-packing and column generation heuristics were both observed to produce designs which were within 10% of the cost lower bound on average. However, the adapted bin-packing heuristic yielded a slightly worse cost performance but was found to be considerably faster then the column generation heuristic. Overall, choice of appropriate heuristic depends on the desired run-time performance.