Analysis of a queuing system of a single capacity with phase-type distributions and queue updating

Cover Page

Cite item

Full Text

Abstract

In this paper, we study a queuing system with a single-capacity storage device and queue updating. An update is understood as the following mechanism: an application that enters the system and finds another application in the drive destroys it, taking its place in the drive. It should be noted that systems with one or another update mechanism have long attracted the attention of researchers, since they have important applied significance. Recently, interest in systems of this kind has grown in connection with the tasks of assessing and managing the age of information. A system with a queue update mechanism similar to the one we are considering has already been studied earlier in the works of other authors. However, in these works we were talking about the simplest version of the system with Poisson flow and exponential maintenance. In this paper, we consider a phase-type flow and maintenance system. As a result of our research, we developed a recurrent matrix algorithm for calculating the stationary distribution of states of a Markov process describing the stochastic behavior of the system in question, and obtained expressions for the main indicators of its performance.

Full Text

1. Introduction The tasks related to the assessment and management of information age, which were initiated in [1- 13], revived interest in the study of systems with various kinds of updating mechanisms. One of these systems is a system with a queue update mechanism [14], the essence of which is that an application entering the system and finding another application in the drive “kills” it and takes its place in the drive. This ensures that the information transmitted by the application is updated as quickly as possible, which is extremely important for real technical systems implementing service complexes for which the time factor plays the most important role. A system with this queue update mechanism was considered in [7, 15, 16]. However, the authors of these papers considered a system with Poisson flow and exponential maintenance, which, according to Kendall’s notation, is usually encoded as
×

About the authors

Sergey I. Matyushenko

RUDN University

Email: matyushenko-si@rudn.ru
ORCID iD: 0000-0001-8247-8988

Candidate of Physical and Mathematical Sciences, Assistant professor of Department of Probability Theory and Cyber Security

6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation

Konstantin E. Samouylov

RUDN University

Author for correspondence.
Email: samuylov-ke@rudn.ru
ORCID iD: 0000-0002-6368-9680

Professor, Doctor of Technical Sciences, Head of the Department of Probability Theory and Cyber Security

6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation

Nikolai Yu. Gritsenko

RUDN University

Email: 1142221032@rudn.ru
PhD student of Department of Probability Theory and Cyber Security 6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation

References

  1. Kaul, S., Gruteser, M., Rai, V. & Kenney, J. Minimizing age of information in vehicular networks in 2011 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (2011), 350-358. doi: 10.1109/SAHCN.2011.5984917.
  2. Kaul, S., Yates, R. & Gruteser, M. Real-time status: How often should one update? in 2012 Proceedings IEEE INFOCOM (2012), 2731-2735. doi: 10.1109/INFCOM.2012.6195689.
  3. Bedewy, A. M., Sun, Y. & Shroff, N. B. Age-optimal information updates in multihop networks in 2017 IEEE International Symposium on Information Theory (ISIT) (2017), 576-580. doi: 10.1109/ISIT.2017.8006593.
  4. Bojan, T. M., Kumar, U. R. & Bojan, V. M. An internet of things based intelligent transportation system in 2014 IEEE International Conference on Vehicular Electronics and Safety (2014), 174-179. doi: 10.1109/ICVES.2014.7063743.
  5. Hu, C. & Dong, Y. Age of information of two-way data exchanging systems with power-splitting. Journal of Communications and Networks 21, 295-306. doi: 10.1109/JCN.2019.000037 (2019).
  6. Costa, М., Codreanu, М. & Ephremides, А. Age of information with packet management in IEEE International Symposium on Information Theory (ISIT) (2014), 1583-1587.
  7. Costa, M., Codreanu, M. & Ephremides, A. On the Age of Information in Status Update Systems With Packet Management. IEEE Transactions on Information Theory 62, 1897-1910. doi: 10.1109/TIT.2016.2533395 (2016).
  8. Chiariotti, F., Vikhrova, O., Soret, B. & Popovski, P. Peak Age of Information Distribution for Edge Computing With Wireless Links. IEEE Transactions on Communications 69, 3176-3191. doi: 10.1109/TCOMM.2021.3053038 (2021).
  9. Kadota, I., Uysal-Biyikoglu, E., Singh, R. & Modiano, E. Minimizing the Age of Information in broadcast wireless networks in 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (2016), 844-851. doi: 10.1109/ALLERTON.2016.7852321.
  10. Kosta, A., Pappas, N., Ephremides, A. & Angelakis, V. Non-linear Age of Information in a Discrete Time Queue: Stationary Distribution and Average Performance Analysis in ICC 2020 - 2020 IEEE International Conference on Communications (ICC) (2020), 1-6. doi: 10.1109/ICC40277.2020.9148775.
  11. Talak, R., Karaman, S. & Modiano, E. Improving Age of Information in Wireless Networks With Perfect Channel State Information. IEEE/ACM Transactions on Networking 28, 1765-1778. doi: 10.1109/TNET.2020.2996237 (2020).
  12. Tripathi, V., Talak, R. & Modiano, E. Age of information for discrete time queues 2019.
  13. Wijerathna Basnayaka, C. M., Jayakody, D. N. K., Ponnimbaduge Perera, T. D. & Vidal Ribeiro, M. Age of Information in an URLLC-enabled Decode-and-Forward Wireless Communication System in 2021 IEEE 93rd Vehicular Technology Conference (VTC2021-Spring) (2021), 1-6. doi: 10.1109/VTC2021Spring51267.2021.9449007.
  14. Bocharov, P. P. & Zaryadov, I. S. Stationary probability distribution in a queuing system with an update [Stacionarnoe raspredelenie veroyatnostey v sisteme massovogo obslugivaniya s obnovleniem]. Vestnik RUDN Seriya Matematika. Informatika. Phizika. in Russian, 14-23 (2007).
  15. Kaul, S. K., Yates, R. D. & Gruteser, M. Status updates through queues in 2012 46th Annual Conference on Information Sciences and Systems (CISS) (2012), 1-6. doi: 10.1109/CISS.2012.6310931.
  16. Inoue, Y., Masuyama, H., Takine, T. & Tanaka, T. A General Formula for the Stationary Distribution of the Age of Information and Its Application to Single-Server Queues. IEEE Transactions on Information Theory 65, 8305-8324. doi: 10.1109/TIT.2019.2938171 (2019).
  17. Bocharov, P. P. & Pechinkin, A. V. Queueing Theory [Teoriya massovogo obsluzhivaniya] in Russian. 529 pp. (Izd-vo RUDN, Moscow, 1995).
  18. Basharin, G. P., Bocharov, P. P. & Kogan, Y. A. Queue analysis in computer networks [Analiz ocheredey v vichislitelnih setyah] in Russian (Nauka, Moscow, 1989).
  19. Naumov, V. A. O predelnih veroyatnostyah polumarkovskogo processa [On the limiting probabilities of a semi-Markov process] in Russian. 35-39 (Universitet drugbi narodov, Moscow, 1975).
  20. Gelenbe, E. & Pujolle, G. Introduction to queueing networks (John Wiley, New York, 1987).

Copyright (c) 2024 Matyushenko S.I., Samouylov K.E., Gritsenko N.Y.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies