extended-abstract

An Optimal Scheduling Policy for the 2 X 2 Input-Queued Switch with Symmetric Arrival Rates

Authors:

M.S. Squillante,

X. WuAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 45, Issue 3

Pages 217 - 223

https://doi.org/10.1145/3199524.3199563

Published: 20 March 2018 Publication History

Abstract

We investigate a cannonical input-queued switch scheduling problem in which the objective is to minimize the infinite horizon discounted queue length under symmetric arrivals, for which we derive an optimal scheduling policy and establish its theoretical properties with respect to delay. We then compare via simulation these theoretical properties of our optimal policy with those of the well-known MaxWeight scheduling algorithm in order to gain insights on the delay optimality of the MaxWeight scheduling policy.

References

[1]

M. Andrews, K. Jung, A. Stolyar. Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads. In Proceedings STOC '07, pp. 145-154, 2007.

Digital Library

[2]

J. Baras, D.-J. Ma, A. Makowski. K competing queues with geometric service requirements and linear costs: The ?c-rule is always optimal. Systems & Control Letters, 6(3):173-180, 1985.

[3]

J.S. Baras, A.J. Dorsey, A.M. Makowski. Two competing queues with linear costs: The ?c-rule is often optimal. In The 22nd IEEE Conference on Decision and Control, pages 1173-1178, Dec 1983.

[4]

W.N. Kang, R.J. Williams. Diffusion approximation for an input-queued packet switch operating under a maximum weight algorithm. Stochastic Systems, 2012.

[5]

I. Keslassy, R. Zhang-Shen, N. McKeown. Maximum size matching is unstable for any packet switch. IEEE Comm. Let., 7(10):496-498, 2003.

[6]

Y.Lu, S.T. Maguluri, M.S. Squillante, T. Suk. On Optimal Weighted-Delay Scheduling in Input-Queued Switches. arXiv:1704.02302, 2017.

[7]

S. T. Maguluri, S. K. Burle, R. Srikant. Optimal heavy-traffic queue length scaling in an incompletely saturated switch. In Proceedings of ACM SIGMETRICS, pp. 13-24, 2016.

Digital Library

[8]

S. T. Maguluri, R. Srikant. Heavy traffic queue length behavior in a switch under the maxweight algorithm. Stoch. Syst., 6(1):211-250, 2016.

[9]

M.L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley, 2005.

[10]

S. Sarkar. Optimum Scheduling and Memory Management in Input Queued Switches with Finite Buffer Space. In Proceedings of INFOCOMM, 2003.

[11]

D. Shah, J. Tsitsiklis, Y. Zhong. Optimal scaling of average queue sizes in an input-queued switch: an open problem. QUESTA, 68(3-4):375-384, 2011.

Digital Library

[12]

D. Shah, J. N. Tsitsiklis, Y. Zhong. On queue-size scaling for input-queued switches, 2015. arxiv preprint http://arxiv.org/abs/1405.4764.

[13]

D. Shah, N. S. Walton, Y. Zhong. Optimal queue-size scaling in switched networks. Ann. Appl. Probab., 24(6):2207-2245, 12 2014.

[14]

D. Shah, D. Wischik. Switched networks with maximum weight policies: Fluid approximation and multiplicative state space collapse. Ann. Appl. Probab., 22(1):70-127, 2012.

[15]

M. Verloop, S. Borst, R. Nunez-Queija. Delay optimization in bandwidth-sharing networks. In Proceedings of CISS, pp. 1260-1265, 2006.

Cited By

Hurtado-Lange DVarma SMaguluri S(2022)Logarithmic heavy traffic error bounds in generalized switch and load balancing systemsJournal of Applied Probability10.1017/jpr.2021.8259:3(652-669)Online publication date: 21-Jun-2022
https://doi.org/10.1017/jpr.2021.82
Jhunjhunwala PMaguluri S(2021)Low-Complexity Switch Scheduling Algorithms: Delay Optimality in Heavy TrafficIEEE/ACM Transactions on Networking10.1109/TNET.2021.311660630:1(464-473)Online publication date: 8-Oct-2021
https://dl.acm.org/doi/10.1109/TNET.2021.3116606

Index Terms

An Optimal Scheduling Policy for the 2 X 2 Input-Queued Switch with Symmetric Arrival Rates
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis

Recommendations

Implementing Priority Scheduling in a Combined Input-Crosspoint-Output Queued Switch
AINA '06: Proceedings of the 20th International Conference on Advanced Information Networking and Applications - Volume 02

The combined input-crosspoint-queued (CICQ) crossbar switch is very appealing because it can obtain high throughput with simple scheduling mechanisms. However, in order to support multiple priority levels, separate queues per priority are required at ...
Queues with Workload-Dependent Arrival and Service Rates

We consider two types of queues with workload-dependent arrival rate and service speed. Our study is motivated by queueing scenarios where the arrival rate and/or speed of the server depends on the amount of work present, like production systems and the ...
Note on batch arrival LCFS and related symmetric queues

We consider insensitve aspects of batch arrival LCFS-P/R and related symmetric queues. New types of insensitive distributions are obtained for the queue length when the batch arrival processes are Poisson. For the LCFS-P/R GI^X/GI/1 queue, simple ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 45, Issue 3

December 2017

253 pages

ISSN:0163-5999

DOI:10.1145/3199524

Editor:
Nidhi Hegde
Bell Labs, Nokia, Nozay, France

Issue’s Table of Contents

Copyright © 2018 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: 20 March 2018

Published in SIGMETRICS Volume 45, Issue 3

Check for updates

Qualifiers

Extended-abstract

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
84
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hurtado-Lange DVarma SMaguluri S(2022)Logarithmic heavy traffic error bounds in generalized switch and load balancing systemsJournal of Applied Probability10.1017/jpr.2021.8259:3(652-669)Online publication date: 21-Jun-2022
https://doi.org/10.1017/jpr.2021.82
Jhunjhunwala PMaguluri S(2021)Low-Complexity Switch Scheduling Algorithms: Delay Optimality in Heavy TrafficIEEE/ACM Transactions on Networking10.1109/TNET.2021.311660630:1(464-473)Online publication date: 8-Oct-2021
https://dl.acm.org/doi/10.1109/TNET.2021.3116606

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 Publication

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