AN OPTIMIZATION PROBLEM RELATED TO BALANCING LOADS ON SONET RINGS

We provide a model and a set of solution techniques for an important problem arising in the design of survivable telecommunication networks utilizing fiber-optics-based technologies. The emergence of a synchronous standard for optical signaling called ''SONET'' allows for an economic implementation of ring designs that provides protection for high capacity services. An objective is to choose a loading of the demands onto a ring design that minimizes associated equipment and facility costs while providing capacity for alternative routing should some link or node fail. After the computational complexity of the problem has been determined, three approximation heuristics, including a mathematical programming dual-ascent solution technique, are described and compared. The heuristics are being successfully applied to actual network design problems arising in Bell operating companies and other telecommunication providers.