Randomized parallel scheduling algorithm for input queued crossbar switches

A significant research effort has been devoted in recent years to the design of simple and efficient scheduling algorithms for input-queued packet switches. Among these algorithms, scheduling policies based on Maximum Weight Matching (MWM) were proved to achieve 100% throughput under any admissible traffic load. However, MWM is impractical for its high computational complexity O(N-3). In this paper, we propose a new approximate algorithm to MWM using local search technique. Notably we observe that: (a) Local search is well suitable for parallel computation. (b) Currently each line card of high performance router has at least one processor. Based on the two important observations, a randomized parallel scheduling algorithm is proposed It is proved to be rate stable and simulation results show that the proposed algorithm outperforms other randomized approximations to MWM.