Efficient algorithms for wavelength rerouting in WDM multi-fiber unidirectional ring networks

In this article, we consider wavelength rerouting in wavelength-routed Wave length-Division Multiplexed (WDM) multi-fiber unidirectional ring networks with circuit switching. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a via ble and cost effective mechanism that can improve the blocking performance by rearranging certain existing lightpaths to accommodate a new request. Re cently, in Ref. [1], a rerouting scheme called 'Parallel Move-To-Vacant Wav elenth Retuning (MTV-WR)' with many attractive features such as shorter dis ruption period and simpler switching control has been proposed. A polynomia l time rerouting algorithm has also been proposed in Ref. [1] to minimize t he weighted number of rerouted lightpaths in WDM networks with the parallel MTV-WR rerouting scheme. However, this algorithm is not time optimal and w orks correctly when the fiber links, wavelength channels, and lightpaths ar e all bidirectional. We present here a time-optimal rerouting algorithm to minimize the number o f rerouted lightpaths in wavelength-routed WDM multi-fiber unidirectional r ing networks with parallel MTV-WR rerouting scheme. This algorithm requires only O(NFW) time units, where N is the number of nodes in the network, F i s the number of fiber links between two consecutive nodes, and W is the num ber of wavelength channels available on a fibre link. We also present on O( (NFW)-W-2) time rerouting algorithm to minimize the weighted number of rero uted lightpaths. The simulation results show that the rerouting algorithms improve the blocking performance considerably and only very few lightpaths are required to be rerouted per rerouting. The results also show that, for a given network load per wavelength per fiber, increasing the number of wav elengths or the number of fibers, leads to an improved performance by the n etworks with rerouting, without any rerouting and with full wavelength conv ersion capability at the routing nodes. (C) 1999 Elsevier Science B.V. Ail rights reserved.