Load-balanced routing in counter rotated SONET rings

Load-balanced routing in SONET rings has attracted much attention recently. Most prior works modeled the SONET rings as undirected rings and the traff ic as undirected chords. While this model fits well to the traditional tele phony applications, it is inefficient for the explosive Internet traffic an d multimedia data communications, which exhibit an unidirectional and asymm etric nature. For these applications, it is proper to model the SONET rings as a pair of counter rotated rings and the traffic as directed chords. In this paper, we first explore general flow properties in counter rotated rin gs and then introduce flow rounding and unsplitting techniques. Afterward, an optimal integral routing algorithm is provided. Finally, we show the up- completeness of optimal unsplit routing and present several polynomial-time approximation algorithms. (C) 2000 John Wiley & Sons, Inc.