Online routing and wavelength assignment in WDM rings

摘要

We present new theoretical results on the performance limits of on-line routing and wavelength assignment (RWA) algorithms in a single-hub wavelength division multiplexing ring network architecture. An RWA algorithm is said to be on-line if at each point in time, the algorithm assigns a lightpath to a current connection request based only on past information and with no knowledge whatsoever about the future requests. We derive tight bounds on the throughput performance of an on-line min-hop algorithm in comparison with that of an optimal off-line algorithm. In addition, we show that when there are sufficiently many nodes in the ring, the min-hop algorithm achieves the best possible throughput performance among all on-line RWA algorithms. On the other hand, when the number of nodes is not greater than the number of wavelengths in the ring, an on-line algorithm that minimizes the maximum load of the network is shown to achieve better throughput performance than the min-hop algorithm.