nach oben

Queueing Systems

Erschienen in:

28.11.2017

Optimal heavy-traffic queue length scaling in an incompletely saturated switch

verfasst von: Siva Theja Maguluri, Sai Kiran Burle, R. Srikant

Erschienen in: Queueing Systems | Ausgabe 3-4/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider an input-queued switch operating under the MaxWeight scheduling algorithm. This system is interesting to study because it is a model for Internet routers and data center networks. Recently, it was shown that the MaxWeight algorithm has optimal heavy-traffic queue length scaling when all ports are uniformly saturated. Here we consider the case when an arbitrary number of ports are saturated (which we call the incompletely saturated case), and each port is allowed to saturate at a different rate. We use a recently developed drift technique to show that the heavy-traffic queue length under the MaxWeight scheduling algorithm has optimal scaling with respect to the switch size even in these cases.

Vorheriger Artikel Asymptotics of insensitive load balancing and blocking phases

Nächster Artikel Costly circuits, submodular schedules and approximate Carathéodory Theorems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

The relative interior of a set is defined as its interior relative to its affine hull [5, Section 2.1.3].

Alizadeh, M., Yang, S., Sharif, M., Katti, S., McKeown, N., Prabhakar, B., Shenker, S.: pFabric: Minimal near-optimal datacenter transport. In: Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, SIGCOMM ’13, pp. 435–446 (2013)

Andrews, M., Jung, K., Stolyar, A.: Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads. In: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC ’07, pp. 145–154 (2007)

Bertsimas, D., Gamarnik, D., Tsitsiklis, J.N.: Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Ann. Appl. Probab. 11(4), 1384–1428 (2001)CrossRef

Bonald, T., Proutiere, A.: Insensitivity in processor-sharing networks. Perform. Eval. 49(1), 193–209 (2002)CrossRef

Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York, NY (2004)CrossRef

Eryilmaz, A., Srikant, R.: Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Syst. 72(3–4), 311–359 (2012)CrossRef

Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3), 502–525 (1982)CrossRef

Kang, W.N., Williams, R.J.: Diffusion approximation for an input-queued switch operating under a maximum weight matching policy. Stoch. Syst. 2(2), 277–321 (2012). https://doi.org/10.1214/12-SSY061 CrossRef

Lu, Y., Maguluri, S.T., Squillante, M., Suk, T.: On optimal weighted-delay scheduling in input-queued switches (2017). Arxiv preprint arXiv:1704.02302

10.

Maguluri, S.T., Burle, S.K., Srikant, R.: Optimal heavy-traffic queue length scaling in an incompletely saturated switch. In: Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, pp. 13–24. ACM (2016)

11.

Maguluri, S.T., Srikant, R.: Heavy traffic queue length behavior in a switch under the MaxWeight algorithm. Stoch. Syst. 6(1), 211–250 (2016). https://doi.org/10.1214/15-SSY193 CrossRef

12.

McKeown, N., Anantharam, V., Walrand, J.: Achieving 100% throughput in an input queued switch. In: Proceedings of IEEE INFOCOM, pp. 296–302 (1996)

13.

Neely, M.J., Modiano, E., Cheng, Y.S.: Logarithmic delay for n \(\times \) n packet switches under the crossbar constraint. IEEE/ACM Trans. Netw. 15(3), 657–668 (2007)CrossRef

14.

Perry, J., Ousterhout, A., Balakrishnan, H., Shah, D., Fugal, H.: Fastpass: a centralized “zero-queue” datacenter network. In: Proceedings of the 2014 ACM Conference on SIGCOMM, SIGCOMM ’14, pp. 307–318. ACM, New York, NY (2014). https://doi.org/10.1145/2619239.2626309

15.

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

16.

Shah, D., Tsitsiklis, J.N., Zhong, Y.: On queue-size scaling for input-queued switches (2015). Arxiv preprint arXiv:1405.4764

17.

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

18.

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

19.

Singh, R., Stolyar, A.: Maxweight scheduling: asymptotic behavior of unscaled queue-differentials in heavy traffic. arXiv preprint arXiv:1502.03793 (2015)

20.

Srikant, R., Ying, L.: Communication Networks: An Optimization, Control and Stochastic Networks Perspective. Cambridge University Press, Cambridge (2014)

21.

Stolyar, A.L.: Maxweight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1), 1–53 (2004)CrossRef

22.

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

23.

Wang, W., Maguluri, S.T., Srikant, R., Ying, L.: Heavy-traffic delay insensitivity in connection-level models of data transfer with proportionally fair bandwidth sharing. In: IFIP WG 7.3 Performance 2017 (2017)

24.

Weller, T., Hajek, B.: Scheduling nonuniform traffic in a packet-switching system with small propagation delay. IEEE/ACM Trans. Netw. 5(6), 813–823 (1997)CrossRef

25.

Ziegler, G.: Lectures on Polytopes. Graduate Texts in Mathematics. Springer, New York (1995)CrossRef

Titel: Optimal heavy-traffic queue length scaling in an incompletely saturated switch
verfasst von: Siva Theja Maguluri
Sai Kiran Burle
R. Srikant
Publikationsdatum: 28.11.2017
Verlag: Springer US
Erschienen in: Queueing Systems / Ausgabe 3-4/2018
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI: https://doi.org/10.1007/s11134-017-9562-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3-4/2018

Costly circuits, submodular schedules and approximate Carathéodory Theorems

Probabilistic selfish routing in parallel batch and single-server queues

Introduction to special issue: ACM SIGMETRICS 2016

Optimal timer-based caching policies for general arrival processes

Asymptotics of insensitive load balancing and blocking phases

Large deviations in relay-augmented wireless networks