Sliding-Window QPS (SW-QPS)
- 5 March 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 48 (3), 71-76
- https://doi.org/10.1145/3453953.3453969
Abstract
In this work, we first propose a parallel batch switching algorithm called Small-Batch Queue-Proportional Sampling (SB-QPS). Compared to other batch switching algorithms, SB-QPS significantly reduces the batch size without sacrificing the throughput performance and hence has much lower delay when traffic load is light to moderate. It also achieves the lowest possible time complexity of O(1) per matching computation per port, via parallelization. We then propose another algorithm called Sliding-Window QPS (SW-QPS). SW-QPS retains and enhances all benefits of SB-QPS, and reduces the batching delay to zero via a novel switching framework called sliding-window switching. In addition, SW-QPS computes matchings of much higher qualities, as measured by the resulting throughput and delay performances, than QPS-1, the state-of-the-art regular switching algorithm that builds upon the same underlying bipartite matching algorithm.Keywords
This publication has 15 references indexed in Scilit:
- A Scaling Algorithm for Maximum Weight Matching in Bipartite GraphsPublished by Society for Industrial & Applied Mathematics (SIAM) ,2012
- Batch means and spectral variance estimators in Markov chain Monte CarloThe Annals of Statistics, 2010
- Logarithmic Delay for $N \times N$ Packet Switches Under the Crossbar ConstraintIEEE/ACM Transactions on Networking, 2007
- Optimal Scheduling Algorithms for Input-Queued SwitchesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Parallel maximum weight bipartite matching algorithms for scheduling in input-queued switchesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Switch scheduling via randomized edge coloringPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Randomized scheduling algorithms for high-aggregate bandwidth switchesIEEE Journal on Selected Areas in Communications, 2003
- The iSLIP scheduling algorithm for input-queued switchesIEEE/ACM Transactions on Networking, 1999
- Achieving 100% throughput in an input-queued switchIEEE Transactions on Communications, 1999
- The Asymptotic Validity of Sequential Stopping Rules for Stochastic SimulationsThe Annals of Applied Probability, 1992