More Web Proxy on the site http://driver.im/

research-article

Optimal queue-size scaling in switched networks

Authors:

Yuan ZhongAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 40, Issue 1

Pages 17 - 28

https://doi.org/10.1145/2318857.2254762

Published: 11 June 2012 Publication History

Abstract

We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. In the main result of this paper, we provide a new class of online scheduling policies that achieve optimal average queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a conjecture about optimal queue-size scaling for input-queued switches.

References

[1]

S. Asmussen. Applied probability and queues. Second edition, Springer Verlag, 2003.

[2]

G. Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman Rev. Ser. A, 5:147--151, 1946.

[3]

T. Bonald and A. Proutiére. Insensitivity in processor-sharing networks. Performance Evaluation, 49(1--4):193--209, 2002.

Digital Library

[4]

T. Bonald and A. Proutiére. Insensitive bandwidth sharing in data networks. Queueing systems, 44(1):69--100, 2003.

Digital Library

[5]

M. Bramson. State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems, 30:89--148, 1998.

Digital Library

[6]

J. G. Dai and W. Lin. Maximum pressure policies in stochastic processing networks. Operations Research, 53(2), 2005.

Digital Library

[7]

J. G. Dai and W. Lin. Asymptotic optimality of maximum pressure policies in stochastic processing networks. The Annals of Applied Probability, 18(6), 2008.

[8]

J. G. Dai and B. Prabhakar. The throughput of switches with and without speed-up. In Proceedings of IEEE Infocom, pages 556--564, 2000.

[9]

A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah. Optimal throughput-delay scaling in wireless networks -- part ii: Constant-size packets. Information Theory, IEEE Transactions on, 52(11):5111--5116, 2006.

Digital Library

[10]

S. Foss and T. Konstantopoulos. An overview of some stochastic stability methods. Journal of Operations Research, Society of Japan, 47(4), 2004.

[11]

J. M. Harrison. Balanced fluid models of multiclass queueing networks: A heavy traffic conjecture. Stochastic Networks, 71:1--20, 1995. IMA Volumes in Mathematics and Its Applications.

[12]

J. M. Harrison. Brownian models of open processing networks: canonical representation of workload. The Annals of Applied Probability, 10:75--103, 2000. Also see harrison:canonical.corr.

[13]

J. M. Harrison. Correction to harrison:canonical. The Annals of Applied Probability, 13:390--393, 2003.

[14]

S. Jagabathula and D. Shah. Optimal delay scheduling in networks with arbitrary constraints. In Proceedings of the 2008 ACM SIGMETRICS, pages 395--406. ACM, 2008.

Digital Library

[15]

W. Kang, F. Kelly, N. Lee, and R. Williams. State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy. The Annals of Applied Probability, 2009.

[16]

F. Kelly, L. Massoulié, and N. Walton. Resource pooling in congested networks: proportional fairness and product form. Queueing Systems, 63(1):165--194, 2009.

Digital Library

[17]

F. P. Kelly. Reversibility and Stochastic Networks. Wiley, Chicester, 1979.

[18]

J. F. C. Kingman. On queues in heavy traffic. Journal of the Royal Statistical Society, series B, 24(2):383--392, 1962.

[19]

S. Meyn. Stability and asymptotic optimality of generalized maxweight policies. SIAM J. Control and Optimization, 2008.

Digital Library

[20]

S. Meyn and R. Tweedie. Markov chains and stochastic stability. Springer New York, 1993.

[21]

M. Neely, E. Modiano, and Y. Cheng. Logarithmic delay for n x n packet switches under the crossbar constraint. IEEE/ACM Transactions on Networking (TON), 15(3):657--668, 2007.

Digital Library

[22]

A. Proutiére. Insensitivity and stochastic bounds in queueing networks--Applications to flow level traffic modelling in telecommunication networks. PhD thesis, Ecoloe Doctorale de l'Ecole Polytechnique, 2003.

[23]

D. Shah, J. N. Tsitsiklis, and Y. Zhong. Qualitative properties of α-weighted scheduling policies. In ACM SIGMETRICS Performance Evaluation Review, volume 38, pages 239--250. ACM, 2010.

Digital Library

[24]

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

Digital Library

[25]

D. Shah, J. N. Tsitsiklis, and Y. Zhong. Qualitative properties of alpha-fair policies in bandwidth sharing network. Unpublished, available on arxiv.org, 2011.

[26]

D. Shah, N. Walton, and Y. Zhong. Optimal queue-size scaling in switched networks. http://arxiv.org/pdf/1110.4697v1.pdf.

[27]

D. Shah and D. Wischik. Fluid models of congestion collapse in overloaded switched networks. Queueing Systems, 69(2):121--143, 2011.

Digital Library

[28]

D. Shah and D. Wischik. Switched networks with maximum weight policies: Fluid approximation and state space collapse. The Annals of Applied Probability, 2011.

[29]

A. Stolyar. Large deviations of queues sharing a randomly time-varying server. Queueing Systems, 59(1):1--35, 2008.

Digital Library

[30]

A. L. Stolyar. MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. The Annals of Applied Probability, 14(1):1--53, 2004.

[31]

L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37:1936--1948, 1992.

[32]

V. Venkataramanan and X. Lin. Structural properties of LDP for queue-length based wireless scheduling algorithms. In Proceedings of Allerton, 2007.

[33]

J. von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. In Contributions to the theory of games, 2, 1953.

[34]

N. Walton. Proportional fairness and its relationship with multi-class queueing networks. The Annals of Applied Probability, 19(6):2301--2333, 2009.

[35]

W. Whitt. Stochastic-Process Limits. Springer, 2001.

[36]

R. J. Williams. Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Systems, 30:27--88, 1998.

Digital Library

[37]

S. Zachary. A note on insensitivity in stochastic networks. Journal of applied probability, 44(1):238--248, 2007.

Cited By

Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/30844401:1(1-33)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3084440
Yun DLee DYun SShin JYi Y(2016)Delay Optimal CSMA With Linear Virtual Channels Under a General TopologyIEEE/ACM Transactions on Networking10.1109/TNET.2015.249260224:5(2847-2857)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2492602
Walton N(2015)Concave switching in single-hop and multihop networksQueueing Systems: Theory and Applications10.1007/s11134-015-9447-981:2-3(265-299)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s11134-015-9447-9
Show More Cited By

Index Terms

Optimal queue-size scaling in switched networks

Recommendations

Optimal queue-size scaling in switched networks
SIGMETRICS '12: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems

We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such networks have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a ...
Optimizing buffer size for the retrial queue: two state space collapse results in heavy traffic

We study a single server queueing model with admission control and retrials. In the heavy traffic limit, the main queue and retrial queue lengths jointly converge to a degenerate two-dimensional diffusion process. When this model is considered with ...
Queue-Length Distribution for the Discriminatory Processor-Sharing Queue

In this paper, we study a multiple class discriminatory processor-sharing queue. The queue is assumed to have Poisson input and exponentially distributed service times. In this discipline there are K classes of customers. When there are n _i ...

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 40, Issue 1

Performance evaluation review

June 2012

433 pages

ISSN:0163-5999

DOI:10.1145/2318857

Issue’s Table of Contents

SIGMETRICS '12: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems
June 2012
450 pages
ISBN:9781450310970
DOI:10.1145/2254756
General Chair:
Peter Harrison
Imperial College London, United Kingdom
,
Program Chairs:
Martin Arlitt
HP Labs, USA and University of Calgary, Canada
,
Giuliano Casale
Imperial College London, United Kingdom

Copyright © 2012 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: 11 June 2012

Published in SIGMETRICS Volume 40, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
397
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/30844401:1(1-33)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3084440
Yun DLee DYun SShin JYi Y(2016)Delay Optimal CSMA With Linear Virtual Channels Under a General TopologyIEEE/ACM Transactions on Networking10.1109/TNET.2015.249260224:5(2847-2857)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2492602
Walton N(2015)Concave switching in single-hop and multihop networksQueueing Systems: Theory and Applications10.1007/s11134-015-9447-981:2-3(265-299)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s11134-015-9447-9
Walton N(2014)Concave switching in single and multihop networksACM SIGMETRICS Performance Evaluation Review10.1145/2637364.259198742:1(139-151)Online publication date: 16-Jun-2014
https://dl.acm.org/doi/10.1145/2637364.2591987
Walton NSanghavi SShakkottai SLelarge MSchroeder B(2014)Concave switching in single and multihop networksThe 2014 ACM international conference on Measurement and modeling of computer systems10.1145/2591971.2591987(139-151)Online publication date: 16-Jun-2014
https://dl.acm.org/doi/10.1145/2591971.2591987
Markakis MModiano ETsitsiklis J(2014)Max-Weight Scheduling in Queueing Networks With Heavy-Tailed TrafficIEEE/ACM Transactions on Networking10.1109/TNET.2013.224686922:1(257-270)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1109/TNET.2013.2246869
Lee DYun DShin JYi YYun S(2014)Provable per-link delay-optimal CSMA for general wireless network topologyIEEE INFOCOM 2014 - IEEE Conference on Computer Communications10.1109/INFOCOM.2014.6848200(2535-2543)Online publication date: Apr-2014
https://doi.org/10.1109/INFOCOM.2014.6848200
Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingACM SIGMETRICS Performance Evaluation Review10.1145/3143314.307850945:1(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3143314.3078509
Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/30844401:1(1-33)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3084440
Gong LTune PLiu LYang SXu JHajek BOh SChaintreau AGolubchik LZhang Z(2017)Queue-Proportional SamplingProceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems10.1145/3078505.3078509(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3078505.3078509
Show More Cited By

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.

Figures

Tables

Media

View Issue’s Table of Contents