DocumentCode :
2501500
Title :
Maximizing Throughput for Traffic Grooming with Limited Grooming Resources
Author :
Wang, Yong ; Gu, Qian-Ping
Author_Institution :
Simon Fraser Univ., Burnaby
fYear :
2007
fDate :
26-30 Nov. 2007
Firstpage :
2337
Lastpage :
2341
Abstract :
In SONET/WDM networks, low-rate traffic demands are usually multiplexed to share a high-speed wavelength channel. The multiplexing/de-multiplexing is known as traffic grooming and performed by SONET add-drop multiplexers (SADM). The grooming factor, denoted by k, is the maximum number of low-rate traffic demands that can be multiplexed into one wavelength channel. SADMs are expensive and thus a critical optimization problem for traffic grooming is to maximize the number of accommodated traffic demands subject to a given number of SADMs. In this paper, we focus on the unidirectional path-switched ring (UPSR) networks with unitary duplex traffic demands. We assume that each network node is equipped with a limited number L of SADMs, and our objective is to maximize the throughput for a given set of traffic demands. We prove the NP-hardness of this Maximum Throughput traffic grooming problem, and propose a (k+1)-approximation algorithm. Extensive simulations are conducted to validate the performance of the algorithm. We also study the case that the given set of traffic demands is the all-to-all set. We propose an algorithm which accommodates at least (nL|radick|)/2 traffic demands, and prove that an optimal solution can accommodate at most nLradick/radic2 traffic demands for the all-to-all set on a UPSR network of n nodes. The solution of our algorithm is at most a constant factor (about radic2) away from the optimal solution.
Keywords :
SONET; approximation theory; computational complexity; demultiplexing; optical fibre networks; telecommunication channels; telecommunication traffic; wavelength division multiplexing; NP-hardness; SONET-WDM networks; UPSR network; add-drop multiplexers; demultiplexing; high-speed wavelength channel; k+1 approximation algorithm; maximum-throughput traffic grooming problem; multiplexing; unidirectional path-switched ring networks; unitary duplex traffic; Add-drop multiplexers; Bandwidth; Computer networks; Optical fibers; Partitioning algorithms; SONET; Telecommunication traffic; Throughput; Traffic control; WDM networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE
Conference_Location :
Washington, DC
Print_ISBN :
978-1-4244-1042-2
Electronic_ISBN :
978-1-4244-1043-9
Type :
conf
DOI :
10.1109/GLOCOM.2007.445
Filename :
4411355
Link To Document :
بازگشت