Scheduling All-to-All Connections in WDM Rings

	C. Qiao and X. Zhang   and   L. Zhou
        Dept. of ECE 	and  Dept. of Automation
        SUNY at Buffalo  and  S. China Univ. of Tech.
	Buffalo, NY 14260 and Guangzhou, P.R. China


ABSTRACT

Scheduling all-to-all 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
(or CADS) is proposed. In a special case when K=1 and T=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
(and vice versa) such that neither T nor K would become the performance
bottleneck.