PACKET SCHEDULING IN BROADCAST WDM NETWORKS WITH ARBITRARY TRANSCEIVER TUNING LATENCIES

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.