Research Article
Minimum Wavelength Assignment for Multicast Traffic in All-Optical WDM Tree Networks
@INPROCEEDINGS{10.1109/BROADNETS.2008.4769141, author={Anuj Rawat and Mark Shayman and Richard La and Steven Marcus}, title={Minimum Wavelength Assignment for Multicast Traffic in All-Optical WDM Tree Networks}, proceedings={5th International ICST Conference on Broadband Communications, Networks, and Systems}, publisher={IEEE}, proceedings_a={BROADNETS}, year={2010}, month={5}, keywords={Wavelength Assignment Wavelength Division Multiplexing Approximation Algorithms}, doi={10.1109/BROADNETS.2008.4769141} }- Anuj Rawat
Mark Shayman
Richard La
Steven Marcus
Year: 2010
Minimum Wavelength Assignment for Multicast Traffic in All-Optical WDM Tree Networks
BROADNETS
IEEE
DOI: 10.1109/BROADNETS.2008.4769141
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.