Matching schemes for input buffered switches with low delay and low complexity

Virtual output queuing is widely used by fixed-length high-speed switches to overcome head-of-line blocking. This is done by means of matching algorithms. Maximum matching algorithms have good performance, but their implementation complexity is quite high. Maximal matching algorithms need speedup to guarantee good performance. Iterative algorithms (such as PIM and iSLIP) use multiple iterations to converge on a maximal match. A class of matching algorithms, exhaustive service matching with Hamiltonian walk (EMHW), is stable and uses exhaustive service matching to achieve efficiency by minimizing the matching overhead over time. In this paper, we present three members of EMHW, HE-MLWM, HE-WiSLIP and HE-iSLIP, and show that they leads to very good delay and fairness performance compared to existing practical matching schemes under both uniform and nonuniform traffic.