The ring loading problem

Author

Shi-bing ; Bing-jun, Li ; Ming-Tian, Zhou

Author_Institution

Univ. of Electron. Sci. & Technol. of China, Chengdu, China

Volume

1

fYear

2002

fDate

29 June-1 July 2002

Firstpage

714

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Circuits and Systems and West Sino Expositions, IEEE 2002 International Conference on

Print_ISBN

0-7803-7547-5

Type

conf

DOI

10.1109/ICCCAS.2002.1180715

Filename

1180715