SONET/SDH Ring Assignment with Capacity Constraints
Olivier Goldschmidt, Alexandre Laugier and Eli V. Olinick.


The use of fiber-optic technology in telecommunication has called for new network design concepts. One of the most popular designs is the Synchronous Digital Hierarchy (SDH) which is also known as Synchronous Optical NETwork (SONET) (the former name is more widely used in Europe and the latter in the United States). In a SONET ring, nodes (typically customer sites) are connected by a ring of fiber, each one sending, receiving, and relaying messages through a device called an add-drop-multiplexer (ADM). In bidirectional rings the traffic between two nodes can be sent clockwise or counterclockwise. The volume of traffic is limited by the ring capacity, which is equal in both directions. On the grounds of reliability, a major European telecommunication company has made the decision to send all traffic in one direction. A direct consequence of this decision is that the capacity of the bidirectional ring must accommodate the sum of bandwidth requests between all pairs of nodes connected by the ring.

We consider the problem of connecting a set of customer sites using bidirectional SONET rings of equal capacity. Each site is assigned to exactly one ring and a special ring, called the federal ring, connects the rings together. An expensive piece of equipment, a digital cross connect, joins each ring to the federal ring. The objective is to minimize the number of rings subject to a ring capacity limit. Two factors determine this capacity. A ring must be able to accommodate the total bandwidth required between sites assigned to it. Each ring must also have capacity sufficient to carry the traffic between its sites and the sites they communicate with on other rings.

We present exact (integer-programming-based) solution techniques and fast, easily implemented heuristic algorithms for this NP-hard problem. Although the heuristics may not always find optimal solutions, we prove that they never produce designs with more than twice the minimum number of rings. We apply both these algorithms and the exact methods to demand data from the telecommunications provider and to randomly generated problem instances. Empirical evidence indicates that in practice the heurisitics perform much better than their theoretical bound and often find optimal solutions.