In-Order Packet Scheduling in Optical Switch With Wavelength Division Multiplexing and Electronic Buffer

Optical switches are widely considered the most promising candidate to provide ultra-high speed interconnections for future communication and computing systems. Due to the difficulty in implementing an all-optical buffer, optical switches with electronic buffers have been proposed recently. Among these switches, the optical cut-through (OpCut) switch has the capability to achieve low latency and minimize optical-electronic-optical (O/E/O) conversions. We studied the packet-scheduling problem in single-wavelength OpCut switches in our previous work. In this paper, we consider the wavelength division multiplexed (WDM) case. While WDM makes much higher bandwidth possible, it also increases the complexity of the switch architecture, as well as packet scheduling. Our goal is to schedule as many as possible packets to the switch output in each time slot and to maintain the packet order at the same time. While we prove that such an optimal scheduling problem is NP-hard and inapproximable in polynomial time within any constant factor by reducing the set packing problem to it, we present an approximation algorithm that maintains packet order and approximates the optimal scheduling within a factor of √(2Nk) with regard to the number of packets transmitted, where N is the switch size, and k is the number of wavelengths multiplexed on each fiber. This result is in line with the best known approximation algorithm for set packing problem. Based on the approximation algorithm, we also give practical schedulers that can be implemented in the fast optical switches. Simulation results show that the schedulers achieve close performance to the ideal WDM output-queued switch in terms of packet delay under various traffic models.