Randomized scheduling algorithm for input-queued switches

摘要

The sampling problem for input-queued (IQ) randomized scheduling algorithms is analyzed. We observe that if the current scheduling decision is a maximum weighted matching (MWM), the MWM for the next slot mostly falls in those matchings whose weight isclosed to the current MWM. Using this heuristic, a novel randomized algorithm for IQ scheduling, named genetic algorithm-like scheduling algorithm (GALSA), is proposed. Evolutionary strategy is used for choosing sampling points in GALSA. GALSA works with only O(N) samples which means that GALSA has lower complexity than the famous randomized scheduling algorithm, APSARA. Simulation results show that the delay performance of GALSA is quite competitive with respect to that of APSARA.