Dynamic Wavelength Allocation in WDM Ring Networks

We focus on wavelength allocation schemes for WDM ring networks based on add-drop multiplexer (ADM) nodes due to their central importance in MAN/Interoffice networks. We restrict ourselves to worst case performance analysis of the network, an approach which yields robust performance guarantees. For an N node network, we first consider a static wavelength allocation scenario, in which all required lightpaths (connections) are known in advance. We prove that if the maximum number of lightpath requests which use any link in the ring (termed the load) is bounded by Lmax, then up to 2Lmax-1 wavelengths may be needed. This result matches the known upper bound which shows that 2Lmax-1 wavelengths are sufficient. Next, we consider a dynamic scenario, in which requests to add or delete a lightpath arrive at different times, and the arrival process is not known. We prove that the shortest path routing heuristic produces a routing which has at most twice the load Lmax of the optimal solution. As far as the wavelength allocation problem is concerned, we show that at least 0.5Lmaxlog2 N wavelengths are required, and develop an algorithm which requires 2Lmaxlog2N wavelengths in the worst case. Our results show that dynamic scenarios result in substantial degradation in the ultilization of wavelengths comparing to static or even semi-dynamic scenarios.