Research Article
Matching Schemes for Input Buffered Switches with Low Delay and Low Complexity
@INPROCEEDINGS{10.1109/CHINACOM.2008.4684972, author={Yihan Li and Prathima Agrawal}, title={Matching Schemes for Input Buffered Switches with Low Delay and Low Complexity}, proceedings={ChinaCom2008-Frontiers on Communications and Networking Symposium}, publisher={IEEE}, proceedings_a={CHINACOM2008-FCN}, year={2008}, month={11}, keywords={}, doi={10.1109/CHINACOM.2008.4684972} }- Yihan Li
Prathima Agrawal
Year: 2008
Matching Schemes for Input Buffered Switches with Low Delay and Low Complexity
CHINACOM2008-FCN
IEEE
DOI: 10.1109/CHINACOM.2008.4684972
Abstract
Virtual Output Queuing is widely used by fixedlength 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.