A New Algorithm for the Ring Loading Problem with Demand Splitting

Y.-S. Myung and H.-G. Kim (Korea)


routing, ring loading problem, optimization, WDMnetwork design


In the ring loading problem with demand splitting, traffic demands are given for each pair of nodes in an undirected ring network and a flow is routed in either of two directions, clockwise and counterclockwise. The load of an edge is the sum of the flows routed through the edge and the objective of the problem is to minimize the maximum load on the ring. This problem arises in the design of SONET bidirectional rings. The fastest algorithm to date is the algorithm of Myung, Kim and Tcha[5] that runs in O(n|K|) time where n is the number of nodes and K is the index set of the origin-destination pairs of nodes having flow traffic demands. We improve the rerouting step of Myung, Kim and Tcha's algorithm and achieve a better running time.

Important Links:

Go Back