research-article

Queue-Proportional Sampling: A Better Approach to Crossbar Scheduling for Input-Queued Switches

Authors:

Jun (Jim) XuAuthors Info & Claims

Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 1, Issue 1

Article No.: 3, Pages 1 - 33

https://doi.org/10.1145/3084440

Published: 13 June 2017 Publication History

Abstract

Most present day switching systems, in Internet routers and data-center switches, employ a single input-queued crossbar to interconnect input ports with output ports. Such switches need to compute a matching, between input and output ports, for each switching cycle (time slot). The main challenge in designing such matching algorithms is to deal with the unfortunate tradeoff between the quality of the computed matching and the computational complexity of the algorithm. In this paper, we propose a general approach that can significantly boost the performance of both SERENA and iSLIP, yet incurs only O(1) additional computational complexity at each input/output port. Our approach is a novel proposing strategy, called Queue-Proportional Sampling (QPS), that generates an excellent starter matching. We show, through rigorous simulations, that when starting with this starter matching, iSLIP and SERENA can output much better final matching decisions, as measured by the resulting throughput and delay performance, than they otherwise can.

References

[1]

HdrHistogram: A High Dynamic Range (HDR) Histogram. https://github.com/HdrHistogram/HdrHistogram.

[2]

T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker.1993 High-speed Switch Scheduling for Local-area Networks. ACM Trans. Comput. Syst. 11, 4 (Nov. 1993), pages 319--352. ISSN 0734--2071

Digital Library

[3]

S. Atalla, D. Cuda, P. Giaccone, and M. Pretti. 2013 Belief-Propagation-Assisted Scheduling in Input-Queued Switches. IEEE Trans. Comput. 62, 10 (Oct. 2013), pages 2101--2107. ISSN 0018-9340

Digital Library

[4]

M. Bayati, B. Prabhakar, D. Shah, and M. Sharma.2007 Iterative Scheduling Algorithms. Proceedings of the IEEE INFOCOM. Anchorage, AK, USA, pages 445--453.

Digital Library

[5]

M. Bayati, D. Shah, and M. Sharma.2008 Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality. IEEE Transactions on Information Theory 54, 3 (Mar. 2008), pages 1241--1251. ISSN 0018-9448

Digital Library

[6]

G. Birkhoff.1946 Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Rev. Ser. Abi 5 (1946), pages 147--151.

[7]

J. Edmonds and R. M. Karp. 1972 Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM 19, 2 (Apr. 1972), pages 248--264. ISSN 0004-5411

Digital Library

[8]

A. Eryilmaz, R. Srikant, and J. R. Perkins. 2001 Throughput-optimal scheduling for broadcast channels. Proceedings of ITCom (Modeling and Design of Wireless Networks). Denver, CO.

[9]

J. Ghaderi and R. Srikant. 2010 On the design of efficient CSMA algorithms for wireless networks. 49th IEEE Conference on Decision and Control (CDC). pages 954--959. ISSN 0191-2216

[10]

P. Giaccone, B. Prabhakar, and D. Shah.2003 Randomized scheduling algorithms for high-aggregate bandwidth switches. IEEE Journal on Selected Areas in Communications 21, 4 (May 2003), pages 546--559.

Digital Library

[11]

M. W. Goudreau, S. G. Kolliopoulos, and S. B. Rao.2000 Scheduling algorithms for input-queued switches: randomized techniques and experimental evaluation. Proceedings of the IEEE INFOCOM. pages 1634--1643 vol.3.

[12]

G. R. Gupta, S. Sanghavi, and N. B. Shroff.2009 Node Weighted Scheduling. Proceedings of the ACM SIGMETRICS. Seattle, WA, USA, pages 97--108.

Digital Library

[13]

M. Karol, M. Hluchyj, and S. Morgan. 1987 Input Versus Output Queueing on a Space-Division Packet Switch. IEEE Transactions on Communications 35, 12 (Dec. 1987), pages 1347--1356. ISSN 0090-6778

[14]

I. Keslassy and N. McKeown.2001 Analysis of scheduling algorithms that provide 100% throughput in input-queued switches. Proceedings of the Allerton Conference on Communication, Control and Computing.

[15]

B. Li and R. Srikant.2015 Queue-Proportional Rate Allocation with Per-Link Information in Multihop Networks. Proceedings of the ACM SIGMETRICS. Portland, OR, USA, pages 97--108. ISBN x978-1-4503-3486-0

Digital Library

[16]

N. McKeown. 1995 Scheduling Algorithms for Input-Queued Cell Switches. Ph.D. Dissertation. University of California at Berkeley.

Digital Library

[17]

N. McKeown.1999 The iSLIP Scheduling Algorithm for Input-queued Switches. IEEE/ACM Transactions on Networking 7, 2 (Apr. 1999), pages 188--201. ISSN 1063-6692

Digital Library

[18]

N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand. 1999 Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communications 47, 8 (Aug.1999), pages 1260--1267. ISSN 0090--6778

[19]

A. Mekkittikul and N. McKeown.1998 A practical scheduling algorithm to achieve 100% throughput in input-queued switches. Proceedings of the IEEE INFOCOM. pages 792--799 vol.2. ISSN 0743-166X

[20]

E. Modiano, D. Shah, and G. Zussman. 2006 Maximizing Throughput in Wireless Networks via Gossiping. Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems ( SIGMETRICS '06/Performance '06). ACM, New York, NY, USA, pages 27--38. ISBN x1-59593-319-0

Digital Library

[21]

J. v. Neumann. 1953 A certain zero-sum two-person game equivalent to the optimal assignment problem. Contributions to the Theory of Games 2 (1953), pages 5--12.

[22]

J. Ni, B. Tan, and R. Srikant. 2012 Q-CSMA: Queue-Length-Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks. IEEE/ACM Transactions on Networking 20, 3 (June 2012), pages 825--836. ISSN 1063-6692

Digital Library

[23]

I. Olkin and A. W. Marshall. 2016 Inequalities: theory of majorization and its applications. Academic press.

[24]

S. Rajagopalan, D. Shah, and J. Shin. 2009 Network Adiabatic Theorem: An Efficient Randomized Protocol for Contention Resolution. Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '09). ACM, New York, NY, USA, pages 133--144 ISBN x978-1-60558--511-6

Digital Library

[25]

K. Seong, R. Narasimhan, and J. M. Cioffi. 2006 Queue Proportional Scheduling in Gaussian Broadcast Channels. 2006 IEEE International Conference on Communications, Vol.4. pages 1647--1652. ISSN 1550-3607

[26]

K. Seong, R. Narasimhan, and J. M. Cioffi. 2006 Queue proportional scheduling via geometric programming in fading broadcast channels. IEEE Journal on Selected Areas in Communications24, 8 (Aug 2006), pages 1593--1602. ISSN 0733-8716

Digital Library

[27]

D. Shah, P. Giaccone, and B. Prabhakar. 2002 Efficient randomized algorithms for input-queued switch scheduling. IEEE Microbib 22, 1 (Jan.2002), pages 10--18. ISSN 0272-1732

Digital Library

[28]

D. Shah and M. Kopikare. 2002 Delay bounds for approximate maximum weight matching algorithms for input queued switches. Proceedings of the IEEE INFOCOM, Vol. 2. pages 1024--1031 vol.2. ISSN 0743-166X

[29]

D. Shah and J. Shin.2012 RANDOMIZED SCHEDULING ALGORITHM FOR QUEUEING NETWORKS. The Annals of Applied Probability 22, 1 (2012), pages 128--171. ISSN 10505164 http://www.jstor.org/stable/41408096

[30]

D. Shah, N. Walton, and Y. Zhong.2012 Optimal Queue-size Scaling in Switched Networks. Proceedings of the ACM SIGMETRICS. ACM, New York, NY, USA, pages 17--28. 978-1-4503-1097-0

Digital Library

[31]

D. Shah and D. Wischik. 2006 Optimal Scheduling Algorithms for Input-Queued Switches. Proceedings of the IEEE INFOCOM. Barcelona, Spain, pages 1--11. 0743-166X

[32]

D. Shah and D. Wischik. 2006 Optimal Scheduling Algorithms for Input-Queued Switches. Proceedings of the IEEE INFOCOM. pages 1--11.

[33]

L. Tassiulas. 1998 Linear complexity algorithms for maximum throughput in radio networks and input queued switches. Proceedings of the IEEE INFOCOM. San Francisco, CA, USA, pages 533--539.

[34]

L. Tassiulas and A. Ephremides. 1992 Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks.IEEE Trans. Automat. Control 37, 12 (Dec. 1992), pages 1936--1948.

[35]

R. Tweedie. 1983 The existence of moments for stationary Markov chains. Journal of Applied Probability (1983), pages 191--196.

[36]

E. Vigoda. 2001 A note on the Glauber dynamics for sampling independent sets. Electronic Journal of Combinatorics volume8, number1 (2001), 1--8.

[37]

N. Walton. 2014 Concave Switching in Single and Multihop Networks. Proceedings of ACM SIGMETRICS. Austin, TX, USA, pages 139--151. 978-1-4503-2789-3

Digital Library

[38]

S. Ye, T. Shen, and S. Panwar. 2010 An O(1) Scheduling Algorithm for Variable-Size Packet Switching Systems. Proceedings of the 48th Annual Allerton Conference. pages 1683--1690.

Cited By

Meng JGong LXu J(2021)Sliding-Window QPS (SW-QPS)ACM SIGMETRICS Performance Evaluation Review10.1145/3453953.345396948:3(71-76)Online publication date: 5-Mar-2021
https://dl.acm.org/doi/10.1145/3453953.3453969
Gong LXu JLiu LMaguluri S(2021)QPS-r: A cost-effective iterative switching algorithm for input-queued switchesPerformance Evaluation10.1016/j.peva.2021.102197(102197)Online publication date: Feb-2021
https://doi.org/10.1016/j.peva.2021.102197
Gong LXu JLiu LMaguluri S(2020)QPS-rProceedings of the 13th EAI International Conference on Performance Evaluation Methodologies and Tools10.1145/3388831.3388836(19-26)Online publication date: 18-May-2020
https://dl.acm.org/doi/10.1145/3388831.3388836
Show More Cited By

Index Terms

Queue-Proportional Sampling: A Better Approach to Crossbar Scheduling for Input-Queued Switches

Recommendations

Queue-Proportional Sampling: A Better Approach to Crossbar Scheduling for Input-Queued Switches
Performance evaluation review

Most present day switching systems, in Internet routers and data-center switches, employ a single input-queued crossbar to interconnect input ports with output ports. Such switches need to compute a matching, between input and output ports, for each ...
Queue-Proportional Sampling: A Better Approach to Crossbar Scheduling for Input-Queued Switches
SIGMETRICS '17 Abstracts: Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

Most present day switching systems, in Internet routers and data-center switches, employ a single input-queued crossbar to interconnect input ports with output ports. Such switches need to compute a matching, between input and output ports, for each ...
An efficient single-iteration single-bit request scheduling algorithm for input-queued switches

Aiming at minimizing communication overhead of iterative scheduling algorithms for input-queued packet switches, an efficient single-iteration single-bit request scheduling algorithm called Highest Rank First with Request Compression 1 (HRF/RC1) is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Measurement and Analysis of Computing Systems

Proceedings of the ACM on Measurement and Analysis of Computing Systems Volume 1, Issue 1

June 2017

712 pages

EISSN:2476-1249

DOI:10.1145/3107080

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2017

Published in POMACS Volume 1, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

US NSF grants
Australian Research Council grant

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
231
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Meng JGong LXu J(2021)Sliding-Window QPS (SW-QPS)ACM SIGMETRICS Performance Evaluation Review10.1145/3453953.345396948:3(71-76)Online publication date: 5-Mar-2021
https://dl.acm.org/doi/10.1145/3453953.3453969
Gong LXu JLiu LMaguluri S(2021)QPS-r: A cost-effective iterative switching algorithm for input-queued switchesPerformance Evaluation10.1016/j.peva.2021.102197(102197)Online publication date: Feb-2021
https://doi.org/10.1016/j.peva.2021.102197
Gong LXu JLiu LMaguluri S(2020)QPS-rProceedings of the 13th EAI International Conference on Performance Evaluation Methodologies and Tools10.1145/3388831.3388836(19-26)Online publication date: 18-May-2020
https://dl.acm.org/doi/10.1145/3388831.3388836
Narayanan Prasanth NVimala Devi KKartheeban KManjula V(2020)Crossbar switch scheduling algorithms for high performance computing: A comprehensive reviewMaterials Today: Proceedings10.1016/j.matpr.2020.10.121Online publication date: Nov-2020
https://doi.org/10.1016/j.matpr.2020.10.121

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents