Title :
The ring loading problem
Author :
Shi-bing ; Bing-jun, Li ; Ming-Tian, Zhou
Author_Institution :
Univ. of Electron. Sci. & Technol. of China, Chengdu, China
fDate :
29 June-1 July 2002
Abstract :
The following problem arose in the planning of optical communications networks in which various ring structures are used to carry given traffic demands at least cost. When the pool of demand that is potentially carried on a ring is large relative to the ring´s line capacity, the problem is to find the subset of demands and their respective routing choices that maximizes the total demand carried by the ring. This is a NP-hard problem. In the complex network programming, this problem needed to be solved numerous times. Two heuristic algorithms are proposed and the relative performance of these algorithms is assessed in this paper.
Keywords :
computational complexity; optical fibre networks; telecommunication network planning; telecommunication network routing; telecommunication traffic; NP-hard problem; complex network programming; greedy algorithm; heuristic algorithms; line capacity; optical communications networks; planning; pool of demand; ring load problem; ring structures; routing choices; total demand; traffic demands; Capacity planning; Clocks; Complex networks; Costs; Heuristic algorithms; NP-hard problem; Optical fiber communication; Routing; Synchronous digital hierarchy; Wavelength division multiplexing;
Conference_Titel :
Communications, Circuits and Systems and West Sino Expositions, IEEE 2002 International Conference on
Print_ISBN :
0-7803-7547-5
DOI :
10.1109/ICCCAS.2002.1180715
