A deterministic parallel scheduling algorithm for input queued crossbar switches

Input-queued (IQ) switch architectures have become predominant in high-speed switching for the past decade. Maximum weight matching (MWM) algorithms are known to achieve 100% throughput under any admissible traffic. Unfortunately, MWM is impractical for its high computational complexity O(N/sup 3/). In this paper, we study a new type of approximate algorithm to MWM using local search technique. Instead of using randomized technique which is mainly used by the existing approximations, our algorithm runs in a deterministic way which is easy to be implemented by hardware. It provides 100% throughput under any admissible traffic and simulation results show that the proposed algorithm with only 3 iterations outperforms the existing approximations to MWM.