Optimal Schedules for Wavelength-Division Multiplexing Networks with Tuning Latency

We consider single-hop wavelength-division multiplexed (WDM) networks in which the transmitters take a nonzero amount of time, called tuning latency, to tune from one wavelength to another. For such networks, we show that, under certain conditions on the traffic matrix, there exist polynomial-time algorithms that produce the optimal schedule. Further, the tuning latency is masked in the length of the optimal schedule. Using Chernoff-Hoeffding bounds, we show that the condition on the traffic matrix is satisfied with high probability when the wavelength reuse factor is large, i.e., number of nodes is large compared to the number of wavelengths. Simulation results show the dramatic improvement in the performance of the network using our algorithm as compared with greedy heuristics. iii ACKNOWLEDGMENTS Throughout this thesis work I have benefited from the experience and patience of my advisor Dr. R. Srikant, whom I would like to thank first. I am also indebted to the AGM-ITA and to all ..