OPTIMAL LOAD BALANCING ON SONET BIDIRECTIONAL RINGS

In this paper we consider the Ring Loading Problem, which arises in th e design of SONET bidirectional rings. The issue of demand splitting d ivides the ring loading problem into the two kinds. One allows a deman d to be split and routed in two different directions and the other doe s not. The former I;ind becomes a relaxation of the latter. We present an efficient exact solution procedure for the case with demand splitt ing, and a two-approximation algorithm for the case without demand spl itting. Computational results are also shown to prove the efficiency o f the proposed procedures.