Algorithms for Computing Limit distributions of Oscillating Systems with Finite Capacity

Document Type : Research Article



We address the batch arrival  systems with finite capacity under partial batch acceptance strategy where service times or rates oscillate between two forms according to the evolution of the number of customers in the system. Applying the theory of Markov regenerative processes and resorting to Markov chain embedding, we present a new algorithm for computing limit distributions of the number customers in the system. The numerical results are given in the paper for a clearer expression of the proposed computational methodologies.


[1]     Altman, E. and A. Jean-Marie (1998). Loss probabilities for messages with redundant packets feeding a finite buffer. IEEE Journal of Selected Areas in Communications 16 (5), 779-787.
[2]     Bahary, E. and P. Kolesar (1972). Multilevel bulk service queues. Operations Research 20, 406-420.
[3]     Bekker, R., S. C. Borst, O. J. Boxma, and O. Kella (2004). Queues with workload-dependent arrival and service rates. Queuing Systems 46 (3-4), 537-556.
[4]     Bratiychuk, M. and A. Chydzinski (2003). On the ergodic distribution of oscillating queuing systems. Journal of Applied Mathematics and Stochastic Analysis 16 (4), 311-326.
[5]     Choi, B. D. and D.I. Choi (1996). Queuing system with queue length dependent service times and its application to cell discarding scheme in ATM networks. IEE Proceedings Communications 143 (1), 5-11.
[6]     Choi, B. D., Y. C. Kim, Y. W. Shin, and C. E. M. Pearce (2001). The M/G/1 queue with queue length dependent service times. Journal of Applied Mathematics and Stochastic Analysis 14 (4), 399-419.
[7]     Choi, D. I., C. Knessl, and C. Tier (1999). A queuing system with queue length dependent service times, with applications to cell discarding in ATM networks. Journal of Applied Mathematics and Stochastic Analysis 12 (1), 35-62
[8]     Chydzinski, A. (2002). The M/G-G/1 oscillating queuing system. Queuing Systems 42 (3), 255-268.
[9]     Chydzinski, A. (2003). The M-M/G/1-type oscillating systems. Cybernetics and Systems Analysis 39 (2), 316-324.
[10]  Chydzinski, A. (2004). The oscillating queue with finite buffer. Performance Evaluation 57 (3), 341-355.
[11]  Fakinos, D. and A. Economou (2001). A new approach for the study of the M/G/1 queue using renewal arguments. Stochastic Analysis and Applications 19, 151-156.
[12]  Federgruen, A. and H. C. Tijms (1980). Computation of the stationary distribution of the queue size in an M/G/1 queuing system with variable service rate. Journal of Applied Probability 17 (2), 515-522.
[13]  Golubchik, L. and J. C. S. Lui (2002). Bounding of performance measures for threshold-based queuing systems: Theory and application to dynamic resource management in video-ondemand servers. IEEE Transactions on Computers 51 (4), 353-372.
[14]  Harris, C. M. (1967). Queues with state-dependent stochastic service rates. Operations Research 15 (1), 117-130.
[15]  Harris, C. M. (1970). Some results for bulk-arrival queues with state-dependent service times. Management Science 16 (5), 313-326.
[16]  Ivnitskiy, V. A. (1975). A stationary regime of a queuing system with parameters dependent on the queue length and with nonordinary flow. Engineering Cybernetics 13 (85-90).
[17]  Kendall, D. G. (1951). Some problems in the theory of queues. Journal of the Royal Statistical Society B 13 (2), 151-185.
[18]  Kendall, D. G. (1953). Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. The Annals of Mathematical Statistics 24 (3), 338-354.
[19]  Kulkarni,V.G. (1995). Modeling and analysis of stochastic systems. London: ‎‎Chapmanand Hall.
[20]  Kwiatkowska, M., G. Norman, and A. Pacheco (2002). Mo del checking CSL until formulae with random time bounds. Lecture Notes in Computer Science 2399, 152-168.
[21]  Larsen, R. L. and A. K. Agrawala (1983). Control of a heterogeneous two-server exponential queuing system. IEEE Transactions on Software Engineering 9 (4), 522-526.
[22]  Li, S.-Q. (1989). Overload control in a finite message storage buffer. IEEE/ACM Transactions Communications 37 (12), 1330-1337.
[23]  Loris-Teghem, J. (1981). Hysteretic control of an M/G/1 queuing system with two service time distributions and removable server. In Point Processes and Queuing Problems, Volume 24 of Col loq. Math. Soc. Janos Bolyai, pp. 291-305. Amsterdam: North-Holland.
[24]  Lu, F. V. and R. F. Serfozo (1984). M/M/1 queuing decision processes with monotone hysteretic optimal policies. Operations Research 32 (5), 1116-1132.
[25]  Ramalhoto, M. F. (1991). Some inventory control concepts in the control of queues. In W. C. Vogt and M. H. Mickie (Eds.), Model ling and Simulations, Volume 22, pp. 639-647. University of Pittsburg Press.
[26]  Rhee, H.-K. and B. D. Sivazlian (1990). Distribution of the busy period in a controllable M/M/2 queue operating under the triadic (0; K; N; M) policy. Journal of Applied Probability 27 (2), 425-432.
[27]  Sriram, K., R. S. McKinney, and M. H. Sherif (1991). Voice packetization and compression in broadband ATM networks. IEEE Journal on Selected Areas in Communications 9 (3), 294-304.
[28]  Takagi, H. (1985). Analysis of a finite-capacity M/G/1 queue with a resume level. Performance Evaluation 5 (3), 197-203.
[29]  Vijaya Laxmi, P., , U.C. Gupta (2000). Analysis of finite-buffer multi-server queues with Group arrivals: . Queuing Systems 36(1-3): 125-140.
[30]  Welch, P. D. (1964). On a generalized M/G/1 queuing process in which the first customer of each busy period receives exceptional service. Operations Research 12 (5), 736-752.
[31]  Willmot, G. E. (1993). On recursive evaluation of mixed-Poisson probabilities and related quantities. Scandinavian Actuarial Journal 2, 114-133.