Title:  Fast Scheduling for Optical Packet Switches with Minimum Configurations
Speaker: Zhou Zhen
HKUST

Date: Friday, Feb 25, 2005
Time 11-12
Venue: Room 3464, HKUST


Abstract
scheduling optical packet switches with minimum number of 
reconfigurations has been proven to be NP-complete. Moreover, 
an optimal scheduling algorithm will produce as many as Theta(log /N/) empty slots 
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 denoted DNC with minimal time complexity Theta(/N/^2 ) 
based on a divide-and-conquer paradigm. The number of empty slots 
generated by our algorithm is upper bounded by Theta(Nlog /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.**