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.