×

Stability and instability of a two-station queueing network. (English) Zbl 1070.90020

Summary: This article proves that the stability region of a two-station, five-class reentrant queueing network, operating under a nonpreemptive static buffer priority service policy, depends on the distributions of the interarrival and service times. In particular, our result shows that conditions on the mean interarrival and service times are not enough to determine the stability of a queueing network under a particular policy. We prove that when all distributions are exponential, the network is unstable in the sense that, with probability 1, the total number of jobs in the network goes to infinity with time. We show that the same network with all interarrival and service times being deterministic is stable. When all distributions are uniform with a given range, our simulation studies show that the stability of the network depends on the width of the uniform distribution. Finally, we show that the same network, with deterministic interarrival and service times, is unstable when it is operated under the preemptive version of the static buffer priority service policy. Thus, our examples also demonstrate that the stability region depends on the preemption mechanism used.

MSC:

90B15 Stochastic network models in operations research
90C31 Sensitivity, stability, parametric optimization
60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
37D45 Strange attractors, chaotic dynamics of systems with hyperbolic behavior
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Bertsimas, D., Gamarnik, D. and Tsitsiklis, J. N. (1996). Stability conditions for multiclass fluid queueing networks. IEEE Trans. Automat. Control 41 1618–1631. [Correction (1997) 42 128.] · Zbl 0870.90061
[2] Bramson, M. (1994). Instability of FIFO queueing networks. Ann. Appl. Probab. 4 414–431. JSTOR: · Zbl 0804.60079
[3] Bramson, M. (1996). Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Systems Theory Appl. 22 5–45. · Zbl 0851.90044
[4] Bramson, M. (1998). Stability of two families of queueing networks and a discussion of fluid limits. Queueing Systems Theory Appl. 28 7–31. · Zbl 0911.90163
[5] Bramson, M. (1999). A stable queueing network with unstable fluid model. Ann. Appl. Probab. 9 818–853. · Zbl 0964.60082
[6] Chen, H. (1995). Fluid approximations and stability of multiclass queueing networks I: Work-conserving disciplines. Ann. Appl. Probab. 5 637–665. JSTOR: · Zbl 0847.60073
[7] Chen, H. and Zhang, H. (1997). Stability of multiclass queueing networks under FIFO service discipline. Math. Oper. Res. 22 691–725. · Zbl 0892.60092
[8] Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5 49–77. JSTOR: · Zbl 0822.60083
[9] Dai, J. G. (1995). Stability of open multiclass queueing networks via fluid models. Stochastic Networks (F. Kelly and R. Williams, eds.) 71–90. Springer, New York. · Zbl 0823.60083
[10] Dai, J. G. (1996). A fluid-limit model criterion for instability of multiclass queueing networks. Ann. Appl. Probab. 6 751–757. · Zbl 0860.60075
[11] Dai, J. G. and Meyn, S. P. (1995). Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Automat. Control 40 1889–1904. · Zbl 0836.90074
[12] Dai, J. G. and Vande Vate, J. (1996). Global stability of two-station queueing networks. In Proceedings of Workshop on Stochastic Networks : Stability and Rare Events (K. S. P. Glasserman and D. Yao, eds.) 1–26. Springer, New York. · Zbl 0856.60093
[13] Dai, J. G. and Vande Vate, J. (2000). The stability of two-station multitype fluid networks. Oper. Res. 48 721–744. · Zbl 1106.90311
[14] Dumas, V. (1997). A multiclass network with non-linear, non-convex, non-monotonic stability conditions. Queueing Systems Theory Appl. 25 1–43. · Zbl 0894.60082
[15] El-Taha, M. and Stidham, S. (1999). Sample-Path Analysis of Queueing Systems . Kluwer, New York. · Zbl 0938.60095
[16] Foss, S. G. and Kovalevskii, A. (1999). A stability criterion via fluid limits and its application to a polling system. Queueing Systems Theory Appl. 32 131–168. · Zbl 0945.90013
[17] Harrison, J. M. and Nguyen, V. (1990). The QNET method for two-moment analysis of open queueing networks. Queueing Systems Theory Appl. 6 1–32. · Zbl 0702.60082
[18] Harrison, J. M. and Nguyen, V. (1995). Some badly behaved closed queueing networks. Stochastic Networks (F. Kelly and R. Williams, eds.) 117–124. Springer, New York. · Zbl 0838.90046
[19] Hasenbein, J. J. (1997). Necessary conditions for global stability of multiclass queueing networks. Oper. Res. Lett. 21 87–94. · Zbl 0888.90071
[20] Hasenbein, J. J. (2001). Stability of fluid networks with proportional routing. Queueing Systems Theory Appl. 38 319–349. · Zbl 1024.90023
[21] Karlin, S. and Taylor, H. M. (1975). A First Course in Stochastic Processes , 2nd ed. Academic Press, New York. · Zbl 0315.60016
[22] Kumar, P. R. (1993). Re-entrant lines. Queueing Systems Theory Appl. 13 87–110. · Zbl 0772.90049
[23] Kumar, S. and Kumar, P. R. (1996). Fluctuation smoothing policies are stable for stochastic reentrant lines. Discrete Event Dynamical Systems 6 361–370. · Zbl 0864.90061
[24] Lu, S. H. and Kumar, P. R. (1991). Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Automat. Control 36 1406–1416.
[25] Meyn, S. P. (1995). Transience of multiclass queueing networks via fluid limit models. Ann. Appl. Probab. 5 946–957. JSTOR: · Zbl 0865.60079
[26] Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability . Springer, New York. · Zbl 0925.60001
[27] Pulhaskii, A. and Rybko, A. (2000). Non-ergodicity of queueing networks when their fluid model is unstable. Problems Inform. Transmission 36 26–46.
[28] Rybko, A. N. and Stolyar, A. L. (1992). Ergodicity of stochastic processes describing the operation of open queueing networks. Problems Inform. Transmission 28 199–220. · Zbl 0768.60089
[29] Schwartz, A. and Weiss, A. (1995). Large Deviations for Performance Analysis . Chapman and Hall, New York. · Zbl 0871.60021
[30] Stolyar, A. (1995). On the stability of multiclass queueing networks: A relaxed sufficient condition via limiting fluid processes. Markov Process. Related Fields 1 491–512. · Zbl 0902.60079
[31] Stolyar, A. L. and Ramakrishnan, K. K. (1999). The stability of a flow merge point with non-interleaving cut-through scheduling disciplines. In Proceedings of INFOCOM’99 .
[32] Williams, R. J. (1998). Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse. Queueing Systems Theory Appl. 30 27–88. · Zbl 0911.90171
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.