A time optimal wavelength rerouting algorithm for dynamic traffic in WDM networks

In this paper, me consider wavelength rerouting in wavelength routed wavele ngth division multiplexed (WDM) networks with circuit switching, wherein li ghtpaths between source-destination pairs are dynamically established and r eleased in response to a random pattern of arriving connection requests and connection holding times. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a viable and cost effective mechanism that can improve the blocking performan ce by rearranging certain existing lightpaths to accommodate a new request. Recently, in [1], a rerouting scheme called "parallel move-to-vacant wavel ength retuning (MTV-WR)" with many attractive features such as shorter disr uption period and simple switching control, and a polynomial time rerouting algorithm, for this scheme, to minimize the weighted number of rerouted li ghtpaths have been proposed, This paper presents a time optimal;rerouting a lgorithm for wavelength-routed WDM networks with parallel MTV-WR rerouting scheme. The algorithm requires only O((NW)-W-2) time units to minimize the weighted number of existing lightpaths to be rerouted, where N is the numbe r of nodes in the network and W is the number of wavelength channels availa ble on a fiber link. Our algorithm is an improvement over the earlier algor ithm proposed in [1] that requires O((NW)-W-3+(NW2)-W-2) time units, which is not time optimal. The simulation results show that our algorithm improve s the blocking performance considerably and only very fem lightpaths are re quired to be rerouted per rerouting. It is also established through simulat ion that our algorithm is faster than the earlier rerouting algorithm by me asuring the time required for processing connection requests for different networks.