Online routing and wavelength assignment in single-hub WDM rings

We present new theoretical results on the performance limits of online routing and wavelength assignment (RWA) algorithms in a single-hub wavelength division multiplexing (WDM) ring network architecture. A routing and wavelength assignment (RWA) algorithm is said to be online if at each point in time, the algorithm assigns a route and a color to the current connection request based only on past information, without knowledge of future requests. We study the throughput performance of deterministic online RWA algorithms in terms of competitive ratio, i.e., the maximum ratio of the throughput of an optimal off-line algorithm to that of an online algorithm over any satisfiable sequence of requests. We show that the competitive ratio for the min-hop algorithm is exactly 2. When there are sufficient wavelengths, smaller competitive ratio W/(W+1-N) can be achieved by the greedy-complete algorithm for infinite-duration requests, and by the pair-complete algorithm for uniform-duration requests, where W is the number of wavelengths and N is the number of nodes. In the general case where requests can have arbitrary durations, we prove that a natural deterministic online algorithm can achieve a competitive ratio of 1+2g, where g>1 is the ratio of the longest duration of any request to the shortest duration of any request. These results exhibit the performance tradeoffs among the number of nodes, the number of wavelengths, and the range of request durations.