.png){kind=icon}
.png){kind=icon}
Return
The ring loading problem
.png){kind=icon}
PRE
AI
DOI：10.1137/S0036144599356470.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The following problem arose in the planning of optical communications networks which use bidirectional. SONET rings. Traffic demands d(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 of 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 that performs even better in practice. En route we prove the following curious lemma: for any x(1),...,x(n) is an element of [0, 1] there exist y(1),..., y(n) such that for each k, \y(k)\ = x(k) and [GRAPHICS] [This article is reprinted here (with updates) from SIAM J. Discrete Math., 11 (1998), pp. 1-14. New developments include a 1+epsilon approximation algorithm and a variation of ring loading in the setting of wavelength division multiplexing; remarks added for this printing, about these and other issues, are enclosed in brackets.]
Keywords:
SONET ring
load balancing
optical network design
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.