Mathematical Modeling in Heavy Traffic Queuing Systems

Sulaiman Sani, Onkabetse A. Daman

Department of Mathematics, University of Botswana, Gaborone.

DOI: 10.4236/ajor.2014.46033                

Abstract

In this article, modeling in queuing systems with heavy traffic customer flows is reviewed. Key areas include their limiting distributions, asymptotic behaviors, modeling issues and applications. Heavy traffic flows are features of queuing in modern communications, transportation and computer systems today. Initially, we reviewed the onset of asymptotic modeling for heavy traffic single server queuing systems and then proceeded to multi server models supporting diffusion approximations developed recently. Our survey shows that queues with heavy traffic customer flows have limiting distributions and extreme value maximum. In addition, the diffusion approximation can conveniently model performance characters such as the queue length or the waiting time distributions in these systems.

Keywords

Queuing Process, Brownian Process, Martingale, Regularly Varying Functions

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Medhi, J. (2003) Stochastic Models in Queueing theory. 2nd Edition, Academic Press, California, USA.
[2]	Boxma, O.J., Deng, Q. and Zwart, A.P. (2003) Waiting Time Asymtotics for the M/G/2 Queue with Heterogenous Servers. Queueing Systems, 40, 5-31. http://dx.doi.org/10.1023/A:1017913826973
[3]	Kingman, J.F.C. (1961) The Single Server Queue in Heavy Traffic. Mathematical Proceedings of the Cambridge Philosophical Society, 57, 902-904. http://dx.doi.org/10.1017/S0305004100036094
[4]	Lee, Y. and Kim, J.S. (2008) Characterization of Large-Scale SMTP Traffic: The Coexistence of the Poisson Process and Self-Similarity. Proceedings of Mascot, 143-152.
[5]	Karagiannis, T., Molle, M., Faloutsos, M. and Broido, A. (2008) A Nonstationary View on Poisson Internet Traffic. Proceedings of IEEE INFOCOM, 84-89.
[6]	Kos, A. and Bester, J. (2003) Poisson Packet Traffic Generation Based on Empirical Data. Systems, Cybernatics and Informatics, 1, 80-83.
[7]	Whitt, W. (1974) Heavy Traffic Limit Theorems for Queues: A Survey. Springer-Verlaq, Berlin, Heidelberg, Newyork, 1-46.
[8]	Kollerstrom, J. (1974) Heavy Traffic Theory for Queues with Several Servers 1. Journal of Applied Probability, 11, 544-552. http://dx.doi.org/10.2307/3212698
[9]	Borovkov, A. (1980) Asymptotic Methods in Theory of Queues. Nauka, Moscow in Russian.
[10]	Abate, J. and Whitt, W. (1994) A Heavy-Traffic Expansion for Asymptotic Decay Rates of Tail Probabilities in Multi-Channel Queues. Operational Research Letters, 15, 223-230. http://dx.doi.org/10.1016/0167-6377(94)90081-7
[11]	Abate, J. and Whitt, W. (1965) Asymptotics for M/G/1 Low-Priority Waiting-Time Tail Probabilities. Queueing Systems, 25, 173-233. http://dx.doi.org/10.1023/A:1019104402024
[12]	Iglehart, D.L. (1965) Limit Diffusion Approximations for the Many Server Queues and the Repairmen Problem. Journal of Applied Probability, 2, 429-441. http://dx.doi.org/10.2307/3212203
[13]	Gaver Jr., D.P. (1968) Diffusion Approximations and Modes for Certain Congestion Problems. Journal of Applied Probability, 5, 607-623. http://dx.doi.org/10.2307/3211925
[14]	Newell, G.F. (1982) Applications of Queueing Theory. 2nd Edition, Chapman and Hall, London. http://dx.doi.org/10.1007/978-94-009-5970-5
[15]	Kimura, T. (2004) Diffusion Models for Computer/Communication Systems. Economic Journal of Hokkaido University, 33, 37-52.
[16]	Guodong, P., Tareja, R. and Whitt, W. (2007) Martingale Proofs for Many-Server Heavy-Traffic Limits for Markovian Queues. Probability Surveys, 4, 193-267. http://dx.doi.org/10.1214/06-PS091
[17]	Iglehart, D.L. and Whitt, W. (1970) Multiple Channel Queue in Heavy Traffic I and II. Journal of Applied Probability, 2, 150-177, 355-369.
[18]	Reiser, M. and Kobayashi, H. (1974) Accuracy of the Diffusion Approximation for Some Queueing Systems. IBM Journal of Research and Development, 18, 110-124. http://dx.doi.org/10.1147/rd.182.0110
[19]	Atar, R., Mandelbaum, A. and Shaikhet, G. (2006) Queueing Systems with Many Servers: Null Controllability in Heavy Traffic. The Annals of Applied Probability, 16, 1764-1804. http://dx.doi.org/10.1214/105051606000000358
[20]	Lee, C. and Weerasinghe, A. (2011) Convergence of a Queueing System in Heavy Traffic with General Patience-Time Distributions. Stochastic Processes and Their Applications, 121, 2507-2552. http://dx.doi.org/10.1016/j.spa.2011.07.003
[21]	Wagenmakers, E.J., Raoul, P.P.P., Grassman, C.M. and Peter, M. (2005) On the Relationship between the Mean and the Variance of a Diffusion Model of Response Time Distribution. Journal of Mathematical Psychology, 49, 195-204. http://dx.doi.org/10.1016/j.jmp.2005.02.003
[22]	Glynn, P.W. and Whitt, W. (1995) Heavy-Traffic Extreme-Value Limits for Queues. Operational Research Letters, 18, 107-111. http://dx.doi.org/10.1016/0167-6377(95)00048-8
[23]	Szczotka, W. and Woyczynski, W. (2004) Heavy-Tailed Dependent Queues in Heavy Traffic. Probability and Mathematical Statistics, 24, 67-96.
[24]	Limic, V. (1999) On the Behavior of LIFO Preemptive Resume Queues in Heavy Traffic. Electronic Communications in Probability, 4, 13-27.
[25]	Boxma, O.J. and Cohen, J.W. (1999) Heavy Traffic Analysis of the G1/G/1 Queue with Heavy Tailed Distributions. Queueing Systems, 33, 177-204. http://dx.doi.org/10.1023/A:1019124112386
[26]	Whitt, W. (2000) An Overview of Brownian and Non-Brownian FCLTs for the Single-Server Queue. Queueing Systems, 36, 39-70. http://dx.doi.org/10.1023/A:1019122901425
[27]	Kruk, L., Lehoczky, J., Ramanan, K. and Shreve, S. (2011) Heavy Traffic Analysis for EDF Queues with Reneging. Annals of Applied Probability, 21, 484-545. http://dx.doi.org/10.1214/10-AAP681
[28]	Coffman Jr., E.G., Puhalskii, A.A. and Reiman, M.I. (1998) Polling System in Heavy Traffic: A Bessel Process Limit. Mathematics of Operations Research, 23, 257-304. http://dx.doi.org/10.1287/moor.23.2.257
[29]	Bertsekas, D. and Gallagher, R. (1992) Data Networks. Prentice Hall, Eaglehood Cliffs.
[30]	Williams, R.J. (1998) Diffusion Approximations for Open Multi Class Queueing Networks: Sufficient Conditions Involving State Space Collapse. Queueing Systems, 30, 27-88. http://dx.doi.org/10.1023/A:1019108819713
[31]	Dai, D.G. and Dai, W. (1999) A Heavy Traffic Limit Theorem for a Class of Open Queueing Networks with Finite Buffers. Queueing Systems, 32, 5-40. http://dx.doi.org/10.1023/A:1019178802391
[32]	Pekoz, E. and Joglekar, N. (2002) Poisson Traffic Flow in a General Feedback Queue. Journal of Applied Probability, 39, 630-636. http://dx.doi.org/10.1239/jap/1034082133
[33]	Ward, A. and Peter, W.G. (2003) Properties of the Ornstein-Uhlenbeck Process. Queuing Systems, 44, 109-123. http://dx.doi.org/10.1023/A:1024403704190
[34]	Ward, A. and Peter, W.G. (2003) A Diffusion Approximation for a Markovian Queue with Reneging. Queueing Systems: Theory and Applications, 43, 103-128. http://dx.doi.org/10.1023/A:1021804515162
[35]	Leland, W.E., Taqqu, M.S., Willinger, W. and Wilson, D.V. (1994) On the Self-Similar Nature of Ethernet Traffic (Extended Version). IEEE/ACM Transactions on Networking, 2, 1-15. http://dx.doi.org/10.1109/90.282603
[36]	Park, K., Kim, G. and Crovella, M. (1997) On the Effect of Traffic Self-Similarity on Network Performance. Proceedings of the SPIE International Conference on Performance and Control of Network Systems, Dallas, 3th-5th November 1997, 296-310. http://dx.doi.org/10.1117/12.290419
[37]	Strzalka, B., Mazurek, M. and Strzalka, D. (2012) Queue Performance in the Presence of Long-Range Dependencies: An Empirical Study. International Journal of Information Science, 2, 47-53. http://dx.doi.org/10.5923/j.ijis.20120204.04
[38]	Willinger, W. and Paxson, V. (1998) Where Mathematics Meets the Internet. Notices of the American Mathematical Society, 45, 961-970.
[39]	Willinger, W., Taqqu, M.S., Leland, W.E. and Wilson, D.E. (1995) Self Similarity in High Speed Packet Traffic: Analysis and Modeling of Ethernets Traffic Measurements. Statistical Science, 10, 67-85. http://dx.doi.org/10.1214/ss/1177010131
[40]	Paxon, V. and Floyd, S. (1995) Wide Area Traffic: The Failure of Poisson Modeling. IEEE/ACM Transactions on Networking, 3, 226-244. http://dx.doi.org/10.1109/90.392383
[41]	Robert, T.B., Ghosh, A. and Pipiras, V. (2007) Heavy Traffic Limits in a Wireless Queueing Model with Long Range Dependence. Decision and Control, 4, 4447-4452.
[42]	Kleinrock, L. (1976) Queueing Systems and Computer Applications. 2nd Edition, Wiley, New York.
[43]	Beran, J., Sherman, R., Taqqu, M.S. and Willinger, J. (1995) Long Range Dependence in Variable-Bit Video. IEEE Transactions on Communications, 43, 1566-1579. http://dx.doi.org/10.1109/26.380206
[44]	Ritchie, D.M. and Thompson, K. (1974) The Unix Time-Sharing System. Communications of the ACM, 17, 365-375. http://dx.doi.org/10.1145/361011.361061
[45]	Zhang, J. and Zwart, B. (2008) Steady State Approximations of Limited Processor Sharing Queues in Heavy Traffic. Queueing System, 60, 227-246. http://dx.doi.org/10.1007/s11134-008-9095-4
[46]	Levy, H. and Sidi, M. (1999) Polling Systems: Applications, Modeling and Optimisation. IEEE Transactions on Communications, 38, 1750-1760. http://dx.doi.org/10.1109/26.61446
[47]	David, J.L., Kleoniki, V., Tarek, B. and Alexander, B. (2012) A Diffusion Approximations to a Single Airport Queue. Transportation Research Part C: Emerging Technologies, 33, 227-237.