Gn. Rouskas et V. Sivaraman, PACKET SCHEDULING IN BROADCAST WDM NETWORKS WITH ARBITRARY TRANSCEIVER TUNING LATENCIES, IEEE/ACM transactions on networking, 5(3), 1997, pp. 359-370
We consider the problem of scheduling packet transmissions in a broadc
ast, single-hop wavelength-division multiplexing (WDM) network, with t
unability provided only at one end, Our objective is to design schedul
es of minimum length to satisfy a set of traffic requirements given in
the form of a demand matrix. We address a fairly general version of t
he problem as we allow arbitrary traffic demands and arbitrary transmi
tter tuning latencies, The contribution of our work is twofold, First
we define a special class of schedules which permit an intuitive formu
lation of the scheduling problem, Based on this formulation we present
algorithms which construct schedules of length equal to the lower bou
nd provided that the traffic requirements satisfy certain optimality c
onditions, We also develop heuristics which, in the general case, give
schedules of length equal or very close to the lower bound, Secondly,
we identify two distinct regions of network operation, The first regi
on is such that the schedule length is determined by the tuning requir
ements of transmitters; when the network operates within the second re
gion however, the length of the schedule is determined by the traffic
demands, not the tuning latency, The point at which the network switch
es between the two regions is identified in terms of system parameters
such as the number of nodes and channels and the tuning latency, Acco
rdingly, we show that it is possible to appropriately dimension the ne
twork to minimize the effects of even large values of the tuning laten
cy.