Title :
Minimum wavelength assignment for multicast traffic in all-optical WDM tree networks
Author :
Rawat, Anuj ; Shayman, Mark ; La, Richard ; Marcus, Steve
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Maryland, College Park, MD
Abstract :
We study the problem of assigning wavelengths to a given set of multicast traffic requests with the objective of minimizing the number of wavelengths used per fiber. We assume that the underlying optical network is a tree and that all-optical networking paradigm is employed. First, we prove that the problem is NP hard even when the underlying network is a simple star or path. Since assigning wavelengths to a given set of unicast traffic requests on star and path networks is easy, this shows that the the multicast wavelength assignment problem is fundamentally harder than the unicast scenario. Next we present GREEDY and SUBTREE-BASED: two simple deterministic algorithms for assigning wavelengths to a given set of multicast traffic requests when the underlying network is a tree with maximum node degree 3 and 4 respectively. Of the two wavelength assignment schemes, GREEDY is a 5/2-approximation algorithm, and SUBTREE-BASED is an approximation algorithm with approximation ratio 10/3, 3 and 2 for the cases when the underlying network is a tree with degree 4, 3 and 2, respectively.
Keywords :
deterministic algorithms; greedy algorithms; multicast communication; optical fibre networks; telecommunication traffic; trees (mathematics); wavelength assignment; wavelength division multiplexing; NP hard problem; all-optical WDM tree network; deterministic algorithm; greedy algorithm; minimum wavelength assignment; multicast traffic; optical fiber network; star-path network; subtree-based approximation algorithm; wavelength division multiplexing; Costs; Optical fiber networks; Optical fibers; Switches; Telecommunication traffic; Ultraviolet sources; WDM networks; Wavelength assignment; Wavelength division multiplexing; Wavelength routing;
Conference_Titel :
Broadband Communications, Networks and Systems, 2008. BROADNETS 2008. 5th International Conference on
Conference_Location :
London
Print_ISBN :
978-1-4244-2391-0
Electronic_ISBN :
978-1-4244-2392-7
DOI :
10.1109/BROADNETS.2008.4769141