Scheduling transmissions in WDM optical networks

This paper addresses the problem of scheduling packet transmissions in wavelength-division multiplexed (WDM) networks with tunable transmitters and fixed-tuned receivers. Unlike previous work which assume that all packets are known in advance, this paper considers the on-line case in which packets may arrive at any time. An on-line algorithm is presented that achieves a performance ratio of 3 with respect to an optimal off-line algorithm. lit addition, of-line algorithms are presented far the case when there are two wavelength channels. Even this special case of the problem is known to be NP-complete and the currently best known algorithm for this case achieves a performance ratio of 2. Using a more rigorous analysis, it is shown that this algorithm has, in fact, a performance ratio of 3/2 and an example is presented where this algorithm achieves this performance ratio even when the tuning delay is zero. Furthermore, for this case, a new polynomial-time approximation algorithm is presented with a performance ratio even better than provided the tuning delay delta is less than (3/2 - alpha) S/6, where S is the total number of packets to be transmitted and alpha approximate to 1.4142136.