A Predictive Lossless Queue for Extremely Large Dataset Transfer in Markov Communication Systems
Article Sidebar
Main Article Content
Abstract
In this paper, a parametric prediction model is proposed for a queuing system driven by the Markov process. The aim of the model is to minimize the packet loss caused by time dependency characterized by the queue tail being too long, resulting in a time-out during the transfer of a large dataset. The proposed technique requires the key parameters influencing the queue content to be determined prior to its occupation regardless of the server capacity definition, using Bayesian inference. The subsequent time elapsing between the arrival and departure of a packet in the system is given, as well as the system load. This queue content planning is considered as the Markov birth-death chain; a type of discretization that characterizes almost all queuing systems, leading to an exponential queue, and captured herein using beta distribution. The inference results obtained using this exponential queue indicate that the queue with predictive parameters employing beta distribution, even when dealing with a loss system queue, involves less transition time and a greater load than a queue with coarse parameters; hence, preventing a long tail in the queue which is the cause of packet loss.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
This journal provides immediate open access to its content on the principle that making research freely available to the public supports a greater global exchange of knowledge.
- Creative Commons Copyright License
The journal allows readers to download and share all published articles as long as they properly cite such articles; however, they cannot change them or use them commercially. This is classified as CC BY-NC-ND for the creative commons license.
- Retention of Copyright and Publishing Rights
The journal allows the authors of the published articles to hold copyrights and publishing rights without restrictions.
References
A. T. Bharucha-Reid, Elements of the Theory of Markov Processes and Their Applications. New York, USA: McGraw-Hill, 1960.
I. Adan and J. Resing. (2015). Queueing systems [Online]. Available: https://www.win.tue.nl/~iadan/queueing.pdf
I. Adan and J. Resing, Queueing Theory. Eindhoven, The Netherlands: Department of Mathematics and Computing Science, Eindhoven University of Technology, 2001.
J. F. C. Kingman, “On queues in heavy traffic,” Journal of the Royal Statistical Society. Series B (Methodological), vol. 24, no. 2, pp. 383–392, 1962.
H. Heffes and D. Lucantoni, “A markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance,” IEEE Journal on Selected Areas in Communications, vol. 4, no. 6, pp. 856–868, Sep. 1986.
W. Whitt, “Approximating a point process by a renewal process, I: Two basic methods,” Operations Research, vol. 30, no. 1, pp. 125–147, Feb. 1982.
M. Schwartz, Telecommunication Networks: Protocols, Modeling and Analysis. Reading, Massachusetts, USA: Addison-Wesley, 1987.
M. Luhanga, “A fluid approximation model of an integrated packet voice and data multiplexer,” in IEEE INFOCOM’88, Seventh Annual Joint Conference of the IEEE Computer and Communcations Societies. Networks: Evolution or Revolution?, 1988, pp. 687–692.
J. M. Harrison and A. Zeevi, “Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime,” Operations Research, vol. 52, no. 2, pp. 243–257, Apr. 2004.
J. F. C. Kingman, “Some inequalities for the queue GI/G/1,” Biometrika, vol. 49, no. 3/4, pp. 315–324, Dec. 1962.
K. T. Marshall and R. V. Evans, “Some inequalities in queuing,” Operations Research, vol. 16, no. 3, pp. 651–668, Jun. 1968.
A. I. Elwalid and D. Mitra, “Statistical multiplexing with loss priorities in rate-based congestion control of high-speed networks,” IEEE Transactions on Communications, vol. 42, no. 11, pp. 2989–3002, Nov. 1994.
W. Whitt, “Approximating a point process by a renewal process: The view through a queue, an indirect approach,” Management Science, vol. 27, no. 6, pp. 619–636, Jun. 1981.
D. Cox and H. Miller, The Theory of Stochastic Processes. Hoboken, New Jersey, USA: John Wiley & Sons, 1965.
R. B. Cooper, Introduction to Queueing Theory. New York, USA: Macmillan, 1972.
A. Kuczura, “The interrupted poisson process as an overflow process,” Bell System Technical Journal, vol. 52, no. 3, pp. 437–448, Mar. 1973.
B. Wallström, “Congestion studies in telephone systems with overflow facilities,” Ericsson Technics, vol. 22, no. 3, pp. 190–351, 1967.
R. I. Wilkinson, “Theories for toll traffic engineering in the U. S. A.” Bell System Technical Journal, vol. 35, no. 2, pp. 421–514, Mar. 1956.
C. Armero and M. J. Bayarri, “Bayesian prediction in M/M/1 queues,” Queueing Systems, vol. 15, pp. 401–417, Mar. 1994.
F. Ruggeri, M. Wiper, and D. R. Insua. Bayesian model selection for M/G/1 queues [Online]. Available: ftp://ftp.isds.duke.edu/pub/WorkingPapers/97-31.ps
P. Nain. (1998) Basic elements of queuing theory: Application to the modelling of computer systems [Online]. Available: http://zyurvas.narod.ru/knigi/Nain.pdf
F. B. Nilsen, “Queuing systems: Modeling, analysis and simulation,” Department of Informatics, University of Oslo, Norway, Research Report 259, Apr. 1998. [Online]. Available: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.353&rep=rep1&type=pdf
S. K. Bose. (2002) The G/M/1, G/G/1, G/G/m and M/G/m/m queues [Online]. Available: http://home.iitk.ac.in/~skb/qbook/Slide_Set_12.PDF
L. Kleinrock, Queueing Systems, Volume 1: Theory. Hoboken, New Jersey, USA: Wiley, 1975.
I. Adan, O. Boxma, and D. Perry, “The G/M/1 queue revisited,” Mathematical Methods of Operations Research, vol. 62, pp. 437–452, Nov. 2005.
D. G. Kendall, “Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain,” The Annals of Mathematical Statistics, vol. 24, no. 3, pp. 338–354, Sep. 1953.
L. Takács, Introduction to the Theory of Queues. New York, USA: Oxford University Press, 1962.
R. Cruz, “A calculus for network delay. I. network elements in isolation,” IEEE Transactions on Information Theory, vol. 37, no. 1, pp. 114–131, Jan. 1991.
D. R. Cox, “The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables,” Mathematical Proceedings of the Cambridge Philosophical Society, vol. 51, no. 3, pp. 433–441, Jul. 1955.
J. C. Lui. G/G/1 queueing systems [Online]. Available: http://www.cse.cuhk.edu.hk/~cslui/CSC5420/GG1.pdf
D. Sloughter. (2004) Liouville’s theorem [Online]. Available: http://math.furman.edu/~dcs/courses/math39/lectures/lecture-32.pdf
H. Kobayashi, “Bounds for the waiting time in queueing systems,” in Computer Architectures and Networks: Modelling and Evaluation : Proceedings of an International Workshop, E. Gelenbe and R. Mahl, Eds. Amsterdam, The Netherlands: North-Holland, 1974, pp. 263–274.
S. L. Brumelle, “Some inequalities for parallel-server queues,” Operations Research, vol. 19, no. 2, pp. 402–413, Apr. 1971.
M. M. Marjanović and Z. Kadelburg, “A proof of Chebyshev’s inequality,” The Teaching of Mathematics, vol. 10, no. 2, pp. 107–108, 2007.
W. Feller, An Introduction to Probability Theory and Its Applications. Hoboken, New Jersey, USA: John Wiley & Sons, 1957, vol. 1.
H. Michiel and K. Laevens, “Teletraffic engineering in a broad-band era,” Proceedings of the IEEE, vol. 85, no. 12, pp. 2007–2033, Dec. 1997.
Y. Nonaka and S. Nogami, “Evaluation of diffusion approximation for the G/G/1 queuing model,” in 8th Asia-Pacific Symposium on Information and Telecommunication Technologies, 2010.
G. F. Newell, Applications of Queueing Theory. London, U.K.: Chapman & Hall, 1971.
D. P. Gaver and G. S. Shedler, “Approximate models for processor utilization in multiprogrammed computer systems,” SIAM Journal on Computing, vol. 2, no. 3, pp. 183–192, 1973.
H. Kobayashi, “Application of the diffusion approximation to queueing networks I: Equilibrium queue distributions,” Journal of the ACM, vol. 21, no. 2, pp. 316–328, Apr. 1974.
M. Reiser and H. Kobayashi, “Accuracy of the diffusion approximation for some queuing systems,” IBM Journal of Research and Development, vol. 18, no. 2, pp. 110–124, Mar. 1974.
H. Kobayashi and Q. Ren, “A diffusion approximation analysis of an ATM statistical multiplexer with multiple types of traffic. - I. equilibrium state solutions,” in Proceedings of ICC’93 - IEEE International Conference on Communications, Geneva, Switzerland, 1993, pp. 1047–1053.
Q. Ren and H. Kobayashi, “Diffusion approximation modeling for Markov modulated bursty traffic and its applications to bandwidth allocation in ATM networks,” IEEE Journal on Selected Areas in Communications, vol. 16, no. 5, pp. 679–691, Jun. 1998.
S. Nlend, “Optimization of resources allocation for H.323 endpoints and terminals over VoIP networks,” M.S. Thesis, Department of Electrical and Electronic Engineering Science, University of Johannesburg, South Africa, 2013.
A. Mahanta. Beta distribution [Lecture notes].
C. Piech. (2018). Beta distribution [Online]. Available: https://web.stanford.edu/class/archive/cs/cs109/cs109.1192/lectureNotes/17-Beta.pdf
J. D. C. Little, “A proof for the queuing formula: L = λW,” Operations Research, vol. 9, no. 3, pp. 383–387, May 1961.