Fast scheduling for optical packet switches with minimum configurations

Scheduling optical packet switches with minimum configurations has been proven to be NP-complete. Moreover, an optimal scheduling algorithm produce as many as θ(log N) empty slots in each switching per time slot for an N × N optical switch. The best known algorithm approximates the optimal solution in O (N^3.5) time. In this paper, we propose an algorithm called DNC with minimal time complexity θ(N²) based on divide-and-conquer paradigm. The number of empty slots created by our algorithm is upper bounded by θ(N). However, simulation results indicate that it is approximately O(log N) on average. Therefore, our algorithm is more practical and beats the previous ones when optical switches have large reconfiguration overhead.