Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-22T05:29:40.463Z Has data issue: false hasContentIssue false
  • English
  • Français

A Paradox for Admission Control of Multiclass Queueing Network with Differentiated Service

Part of: Special processes Markov processes

Published online by Cambridge University Press:  14 July 2016

Heng-Qing Ye
Heng-Qing Ye*
Affiliation:
Hong Kong Polytechnic University and National University of Singapore
*
∗ Postal address: Department of Logistics, Hong Kong Polytechnic University, Hong Kong, P. R. China. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we present counter-intuitive examples for the multiclass queueing network, where each station may serve more than one job class with differentiated service priority and each job may require service sequentially by more than one service station. In our examples, the network performance is improved even when more jobs are admitted for service.

Keywords

Multiclass queueing networkadmission controlstability analysisperformance analysisfluid approximation

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60J25: Continuous-time Markov processes on general state spaces
Type
Research Article
Information
Journal of Applied Probability , Volume 44 , Issue 2 , June 2007 , pp. 321 - 331
Copyright
Copyright © Applied Probability Trust 2007 

Footnotes

Supported in part by a grant from National University of Singapore.

References

Braess, D. (1968). Über ein Paradoxon aus der Verkehrsplanung. Unternehmenforschung 12, 258–268.Google Scholar
Bramson, M. (1994). Instability of FIFO queueing networks. Ann. Appl. Prob. 4, 414–431.Google Scholar
Bramson, M. (1998). Stability of two families of queueing networks and a discussion of fluid limits. Queueing Systems Theory Appl. 23, 7–31.CrossRefGoogle Scholar
Chen, H. (1995). Fluid approximations and stability of multiclass queueing networks: work-conserving discipline. Ann. Appl. Prob. 5, 637–655.CrossRefGoogle Scholar
Chen, H. and Yao, D. D. (2001). Fundamentals of Queueing Networks: Performance, Asymptotics and Optimization. Springer, New York.CrossRefGoogle Scholar
Chen, H. and Ye, H. Q. (2002). Piecewise linear Lyapunov function for the stability of priority multiclass queueing networks. IEEE Trans. Automatic Control 47, 564–575.CrossRefGoogle Scholar
Chen, H. and Zhang, H. (2000). Stability of multiclass queueing networks under priority service disciplines. Operat. Res. 48, 26–37.CrossRefGoogle Scholar
Cohen, J.E. and Kelly, F. P. (1990). A paradox of congestion in a queueing network. J. App. Prob. 27, 730–734.CrossRefGoogle Scholar
Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid models. Ann. Appl. Prob. 5, 49–77.CrossRefGoogle Scholar
Dai, J. G. (1996). A fluid-limit model criterion for instability of multiclass queueing networks. Ann. Appl. Prob. 6, 751–757.CrossRefGoogle Scholar
Dai, J. G. and Meyn, S. P. (1995). Stability and convergence of moments for multiclass queueing networks via fluid models. IEEE Trans. Automatic Control 40, 1899–1904.CrossRefGoogle Scholar
Dai, J. G. and Vande Vate, J. H. (1996). Global stability of two-station queueing networks. In Proc. Workshop Stoch. Networks Stability Rare Events, eds Glasserman, P., Sigman, K. and Yao, D., Springer, New York, pp. 1–26.Google Scholar
Dumas, V. (1997). A multiclass network with non-linear, non-convex, non-monotonic stability conditions. Queueing Systems Theory Appl. 25, 1–43.CrossRefGoogle Scholar
Humes, C. (1994). A regulator stabilization technique: Kumar–Seidman revisited. IEEE Trans. Automatic Control 39, 191–196.CrossRefGoogle Scholar
Kumar, P. R. and Seidman, T. I. (1990). Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems. IEEE Trans. Automatic Control 35, 289–298.CrossRefGoogle Scholar
Lu, S. H. and Kumar, P. R. (1991). Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Automatic Control 36, 1406–1416.CrossRefGoogle Scholar
Meyn, S. (1995). Transience of multiclass queueing networks via fluid limit models. Ann. Appl. Prob. 5, 946–957.CrossRefGoogle Scholar
Puhalskii, A. and Rybko, A. N. (2000). Non-ergodicity of queueing networks under non-stability of their fluid models. Prob. Inf. Transmission 36, 26–48.Google Scholar
Rybko, A. N. and Stolyar, A. L. (1992). Ergodicity of stochastic processes describing the operations of open queueing networks. Problemy Peredachi Informatsii 28, 2–26.Google Scholar
Stolyar, A. L. (1995). On the stability of multiclass queueing network: a relaxed sufficient condition via limiting fluid processes. Markov Process. Rel. Fields 1, 491–512.Google Scholar
Stolyar, A. L. (2004). Max-weight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Ann. Appl. Prob. 14, 1–53.CrossRefGoogle Scholar