Wavelength rerouting for on-line multicast in WDM networks

We consider wavelength rerouting for on-line multicast in all-optical wavelength division multiplexing (WDM) networks where the multicast requests arrive and depart randomly. One limitation of such networks is the wavelength continuity constraint, imposed by the all-optical cross-connect switches, that requires the same wavelength be used on all the links in a multicast tree. With random arrivals and departures of multicast requests, it happens quite often that a new multicast request has to be blocked due to the fact that there are not enough available resources (e.g., wavelengths) to realize the request. Wavelength rerouting, a viable and cost-effective method, has been proposed to improve the blocking probability; it rearranges the wavelengths on certain existing multicast routes to free a wavelength continuous route for the new request. We study the wavelength rerouting problem for on-line multicast in both undirected and directed WDM networks with an objective to minimize the disruption incurred to the existing multicast services, or equivalently, to minimize the number of existing multicast routes to be wavelength-rerouted. We first show that the problem is not only NP-hard but also hard to approximate. We then devise approximation algorithms for it with provable approximation guarantees.