Worst-Case Analysis of Dynamic Wavelength Allocation in Optical Networks

This paper proposes algorithms for allocation of wavelengths to connections (lightpaths) in optical wavelength division multiplexed networks, predominantly for ring topologies. The worst-case situation is considered where no blocking is allowed, and there are no assumptions on the traffic arrival and holding times. The traffic is characterized by its load L, which is the maximum number of lightpaths that can be present on any link assuming no blocking. We start with networks without wavelength conversion, consider a static scenario and prove that the known algorithm which requires 2L - 1 wavelengths is optimal. For a dynamic scenario we show that the shortest path routing produces a routing which has at most twice the load of the optimal solution. We also show that at least 0.5Llog2 N + L wavelengths are required by any algorithm for rings of N nodes and present an algorithm that uses at most Llog2N + L wavelengths for rings and 2(L - 1)log2N for trees. For rings, the known First-Fit algorithm is shown to require at most 2.53Llog2N + 5L and at least 0.9Llog2 N wavelengths. When limited wavelength conversion is allowed, we first show how to use expanders to insure no blocking in arbitrary topologies. Then we present conversion patterns for rings with conversion degree d = 2 which require Llog2 L + 4L or 2Llog2log2 L + 4L wavelengths. In a different traffic model where lightpaths are never taken down, the number of wavelengths needed is shown to be only max{0,L - d}+L for a conversion degree of d.