The Ring Loading Problem

The following problem arose in the planning of optical communications networks which use bidirectional SONET rings. Traffic demands d sub (i,j) are given for each pair of nodes in an n-node ring; each demand must be routed one of the two possible ways around the ring. The object is to minimize the maximum load on the cycle, where the load if an edge is the sum of the demands routed through that edge. We provide a fast, simple algorithm which achieves a load that is guaranteed to exceed the optimum by at most 3/2 times the maximum demand, and performs even better in practice.