Scheduling Bursts in Time-Domain Wavelength Interleaved Networks

We consider the problem of scheduling bursts of data in an optical network with an ultra-fast tunable laser and fixed receiver at each node. Due to the high data rates employed on the optical links, the burst transmissions typically last for very short times compared to the round trip propagation times between source-destination pairs. A good schedule should ensure that (i) there are no transmit/receive conflicts, (ii) propagation delays are observed, and (iii) throughput is maximized (schedule length is minimized). We formulate the scheduling problem as a generalization of the well-known crossbar switch scheduling. We prove that even in the presence of propagation delays, there exist a class of computationally viable scheduling algorithms which asymptotically achieve the maximum throughput that can be achieved without propagation delays. We also show that any schedule can be re-arranged to achieve a factor 2 approximation of the maximum throughput even without asymptotic limits. However, the delay/throughput performance of these schedules is limited in practice. We consequently propose a scheduling algorithm that exhibits near optimal (on average within ~ 7% of optimum) delay/throughput performance in realistic network examples.