<title>Scheduling all-to-all connections in WDM rings</title>

Abstract

Scheduling all-to-al connections in a network of limited physical connectivity provides a way to trade bandwidth for reduced routing control as well as deterministic connection latency. In this paper, we consider the problem of scheduling all-to-all connections in a WDM ring. For a given number of wavelengths, K, and a given number of transmitter/receiver pairs per node, T, we determine the theoretical lower bound (TLB) on the scheduling length. A basic scheduling strategy called complementary assembly with dual strides (CADS) is proposed. In a special case when K equals 1 and T equals 1, the TLB can be achieved based on CADS. Heuristic algorithms based on either homogeneous or heterogeneous CADS are then proposed for the case when K > 1, and near minimum scheduling length can be achieved for any T. Our analysis also indicate that there is an optimal value of T for a given K such that neither T nor K would become the performance bottleneck. Impact of wavelength-tuning delay, ring propagation delay, laser array fabrication especially wavelength drift of the WDM sources on the scheduling method is also discussed.