| Popis: |
This paper addresses the problem of scheduling packet transmissions in wavelength-division multiplexed networks with tunable transmitters and fixed-tuned receivers. Unlike previous work which assume that all packets are known in advance, this paper considers theon-linecase 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. In addition, off-line algorithms are presented for 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 of32, 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 better than32, provided the tuning delay?is less than (32?2)(S/6), whereSis the total number of packets to be transmitted. |
Full Text from ScienceDirect