Fast scheduling for optical packet switches with minimum configurations

Scheduling optical packet switches with minimum configurations has been proven to be NT-complete. Moreover, an optimal scheduling algorithm will 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(lqg N) on average. Therefore, our algorithm is more practical and beats the previous ones when optical switches have large reconfiguration overhead.