Worst-Case Analysis of Dynamic Wavelength Allocation in
Optical Networks
Ori Gerstel
Optical Networking Group, Tellabs Operations, 15 Saw
Mill River Road, Hawthorne, NY 10532,
ori@tellabs.com
Galen Sasaki
Department of Electrical Engineering, University of Hawaii
2540 Dole Street, Honolulu, HI 96822
sasaki@spectra.eng.hawaii.edu
Shay Kutten
Department of Industrial Engineering, Technion, Haifa 32000, ISRAEL,
kutten@ie.technion.ac.il
and
Rajiv Ramaswami
Optical Networking Group, Tellabs Operations, 15 Saw Mill River Road,
Hawthorne, NY 10532,
rajiv@tellabs.com
Abstract
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 only 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 shortest path
routing produces a routing which has at most twice the load of the optimal solution. We also show that at
least 0.5L log2 N + L wavelengths are required by any algorithm for rings of N nodes and present an
algorithm that uses at most L*logN + L wavelengths for rings and 2(L - 1)*logN for trees. For rings, the
known First-Fit algorithm is shown to require at most 2.53L*logN + 5L and at least 0.9L*logN 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 L*logL + 4L or 2L*log2 logL + 4L wavelengths. In a different traffic model where lightpaths are
never taken down, the number of wavelengths needed is shown to be only maxf{0, L - d} + L for a conversion
degree of d.