Exhaustive service matching algorithms for input queued switches

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 matching schemes, such as iSLIP and DRRM, use multiple iterations to converge on a maximal match. The objective of matching algorithms is to reduce the matching overhead for each time slot. In this paper, Exhaustive Service Matching is presented as a way to amortize the cost of a match over multiple time slots, thus significantly improving switch performance. In an Exhaustive Service Matching switch, cells belonging to the same packet are transferred to the output continuously, which leads to good packet delay performance and simplifies the implementation of packet reassembly. To avoid unfairness under some extremely unbalanced traffic pattern, Limited Service Matching and Exhaustive Service Matching with Hamiltonian Walk (EMHW) are presented. We show that Limited Service Matching achieves better fairness under unbalanced traffic patterns, and in some cases improves the delay performance, while retaining low implementation complexity and a scalable architecture. We prove that EMHW is stable under all admissible traffic. All these schemes can be applied to existing matching algorithms, such as iSLIP and DRRM, to achieve high switching efficiency with low implementation complexities.