Single–server queueing system with limited queue, random volume customers and unlimited sectorized memory buffer

• Autorzy: Ziółkowski Marcin , Tikhonenko Oleg

Identyfikatory

DOI

10.24425/bpasts.2022.143647

• Języki publikacji: EN

Abstrakty

EN

In the present paper, we analyze the model of a single–server queueing system with limited number of waiting positions, random volume customers and unlimited sectorized memory buffer. In such a system, the arriving customer is additionally characterized by a non– negative random volume vector whose indications usually represent the portions of unchanged information of a different type that are located in sectors of unlimited memory space dedicated for them during customer presence in the system. When the server ends the service of a customer, information immediately leaves the buffer, releasing resources of the proper sectors. We assume that in the investigated model, the service time of a customer is dependent on his volume vector characteristics. For such defined model, we obtain a general formula for steady–state joint distribution function of the total volume vector in terms of Laplace-Stieltjes transforms. We also present practical results for some special cases of the model together with formulae for steady–state initial moments of the analyzed random vector, in cases where the memory buffer is composed of at most two sectors. Some numerical computations illustrating obtained theoretical results are attached as well.

Słowa kluczowe

EN

single-server queueing system; queueing systems with random volume customers; sectorized memory buffer; total volume vector; Laplace-Stieltjes transform

PL

system kolejkowy z jednym serwerem; system kolejkowy z losowymi klientami; bufor pamięci sektorowany; wektor objętości całkowity; transformata Laplace'a-Stieltjesa

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2022
• Tom: Vol. 70, nr 6
• Strony: art. no. e143647
• Opis fizyczny: Bibliogr. 42 poz., rys., tab.

Twórcy

autor

Ziółkowski Marcin

• Institute of Information Technology, Warsaw University of Life Sciences – SGGW, Poland

• https://orcid.org/0000-0001-8907-8813

autor

Tikhonenko Oleg

• Institute of Computer Science, Cardinal Stefan Wyszynski University in Warsaw, Poland

• https://orcid.org/0000-0003-3087-1694

Bibliografia

• [1] P.P. Bocharov, C. D’Apice, A.V. Pechinkin, and S. Salerno, Queueing Theory, VSP, Utrecht-Boston, 2004.
• [2] O. Tikhonenko, Computer Systems Probability Analysis, Akademicka OficynaWydawnicza EXIT,Warsaw, 2006 (in Polish).
• [3] S.F. Yashkov and A.S. Yashkova, “Processor sharing: A survey of the mathematical theory,” Autom. Remote Control, vol. 68, no. 9, pp. 1662–1731, 2007.
• [4] N. Shun-Chen, “A single server queueing loss model with heterogeneous arrival and service,” Oper. Res., vol. 28, no. 3, pp. 584–593, 1980.
• [5] O. Boxma, “Workloads and waiting times in single–server systems with multiple customer classes,” Queueing Syst., vol. 5, pp. 185–214, 1989.
• [6] P. Guo and P. Zipkin, “Analysis and comparison of queues with different levels of delay information,” Manage. Sci., vol. 53, no. 6, pp. 962–970, 2007.
• [7] J. Kim and A. Ward, “Dynamic scheduling of a 𝐺𝐼/𝐺𝐼/1+𝐺𝐼 queue with multiple customer classes,” Queueing Syst., vol. 75, pp. 339–384, 2013.
• [8] S. Dudin, C. Kim, O. Dudina and J. Baek, “Queueing system with heterogeneous customers as a model of a call center with a call–back for lost customers,” Math. Probl. Eng., vol. 2013, p. 983723, 2013.
• [9] D. Fiems and S. De Vuyst, “From exhaustive vacation queues to preemptive priority queues with general interarrival times,” Int. J. Appl. Math. Comut. Sci., vol. 28, no. 4, pp. 695–704, 2018.
• [10] M. Schwartz, Computer–communication Network Design and Analysis. Prentice-Hall, Englewood Cliffs, New York, 1977.
• [11] M. Schwartz, Telecommunication Networks: Protocols, Modeling and Analysis. Addison-Wesley Publishing Company, New York, 1987.
• [12] A.M. Alexandrov and B.A. Kaz, “Non–homogeneous demands flows service,” Izvestiya AN SSSR. Tekhnicheskaya Kibernetika, vol. 2, pp. 47–53, 1973 (in Russian).
• [13] B. Sengupta, “The spatial requirements of an 𝑀/𝐺/1 queue, or: How to design for buffer space,” in Modelling and Performance Evaluation Methodology. Lect. Notes in Contr. and Inf. Sci., vol. 60, Baccelli F., Fayolle G., Eds., Springer, Heidelberg, 1984, pp. 547–562.
• [14] A. Cascone, R. Manzo, A. Pechinkin and S. Shorgin, “A 𝐺𝑒𝑜𝑚/𝐺/1/𝑛 queueing system with LIFO discipline, service interruptions and resumption, and restrictions on the total volume of demands,” in Proceedings of the World Congress on Engineering 2010, UK, 2010.
• [15] S. Juneja, T. Raheja, and N. Shimkin, “The concert queueing game with a random volume of arrivals,” in Proceedings of the 6th International ICST Conference on Performance Evaluation Methodologies and Tools, B. Gaujal et al., Eds., IEEE, New York, 2012, pp. 317–325.
• [16] K. Kerobyan, R. Covington, R. Kerobyan, and K. Enakoutsa, “An infinite–server queueing 𝑀𝑀𝐴𝑃𝑘/𝐺𝑘/∞ model in semi–Markov random environment subject to catastrophes,” in Communications in Computer and Information Science, vol. 912, A. Dudin et al., Eds., Springer, Cham, 2018, pp. 195–212.
• [17] E. Lisovskaya, S. Moiseeva, M. Pagano, and V. Potatueva, “Study of the 𝑀𝑀𝑃𝑃/𝐺𝐼/∞ queueing system with random customers’ capacities,” Inf. Appl., vol. 11, no. 4, pp. 109–117, 2017.
• [18] E. Lisovskaya, S. Moiseeva, and M. Pagano, “Multiclass 𝐺𝐼/𝐺𝐼/∞ queueing systems with random resource requirements,” in Communications in Computer and Information Science, vol. 912, A. Dudin et al., Eds., Springer, Cham, 2018, pp. 129–142.
• [19] M. Matalytsky and P. Zając, “Application of HM-network with positive and negative claims for finding of memory volumes in information systems,” J. Appl. Math. Comput. Mech., vol. 18, no. 1, pp. 41–51, 2019.
• [20] V. Naumov, K. Samouylov, N. Yarkina, E. Sopin, S. Andreev, and A. Samuylov, “LTE performance analysis using queuing systems with finite resources and random requirements,” 2015 7th International Congress on Ultra Modern Telecommunications and Control Systems andWorkshops (ICUMT), Czech Republic, 2015, pp. 100–103.
• [21] V. Naumov, K. Samuilov, and A. Samuilov, “On the total amount of resources occupied by serviced customers,” Autom. Remote Control, vol. 77, pp. 1419–1427, 2016.
• [22] V. Naumov and K. Samuilov, “Analysis of networks of the resource queuing systems,” Autom. Remote Control, vol. 79, pp. 822–829, 2018.
• [23] B. Nowak, M. Piechowiak, M. Stasiak, and P. Zwierzykowski, “An analytical model of a system with priorities servicing a mixture of different elastic traffic streams,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 68, no. 2, pp. 263–270, 2020.
• [24] A. Rumyantsev and E. Morozov, “Stability criterion of a multiserver model with simultaneous service,” Ann. Oper. Res., vol. 252, pp. 29–39, 2017.
• [25] K. Samouylov, E. Sopin, and O. Vikhrova, “Analyzing blocking probability in LTE wireless network via queuing system with finite amount of resources,” in Communications in Computer and Information Science vol. 564, A. Dudin et al., Eds., Springer, Cham, 2015, pp. 393–403.
• [26] K. Samouylov, E. Sopin, O. Vikhrova, and S. Shorgin, “Convolution algorithm for normalization constant evaluation in queuing system with random requirements,” AIP Conf. Proc. vol. 1863, p. 090004, 2017.
• [27] K. Samouylov, Y. Gaidamaka, and E. Sopin, “Simplified analysis of queueing systems with random requirements,” in Statistics and Simulation. IWS 2015. Springer Proceedings in Mathematics and Statistics, J. Pilz et al., Eds., Springer, Cham, 2018, pp. 381–390.
• [28] Y. Zhernovyi and B. Kopytko, “The potentials method for the 𝑀/𝐺/1/𝑚 queue with customer dropping and hysteretic strategy of the service time change,” J. Appl. Math. Comput. Mech., vol. 15, no. 1, pp. 197–210, 2016.
• [29] O. Tikhonenko and M. Ziółkowski, “Queueing models of systems with non–homogeneous customers and their applications in computer science,” in Proc. of the IEEE 15th International Scientific Conference on Informatics “Informatics 2019”, Czech Republic, 2019, pp. 423–428.
• [30] O. Tikhonenko and M. Ziółkowski, “Queueing systems with random volume customers and their performance characteristics,” J. Inf. Organ. Sci., vol. 45, no. 1, pp. 21–38, 2021.
• [31] M. Ziółkowski, “𝑀/𝐺/𝑛/0 Erlang queueing system with heterogeneous servers and non–homogeneous customers,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 66, no. 1, pp. 59–66, 2018.
• [32] O. Tikhonenko and M. Ziółkowski, “Single server queueing system with external and internal customers,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 66, no. 4, pp. 539–551, 2018.
• [33] O.M. Tikhonenko, “Generalized Erlang problem for service systems with finite total capacity,” Probl. Inf. Transm., vol. 41, no. 3, pp. 243–253, 2005.
• [34] O.M. Tikhonenko, “Queuing systems with processor sharing and limited resources,” Autom. Remote Control, vol. 71, no. 5, pp. 803–815, 2010.
• [35] O. Tikhonenko, M. Ziółkowski, and M. Kurkowski, “M/G/n/(0,V) Erlang queueing system with non-homogeneous customers, non-identical servers and limited memory space,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 67, no. 3, pp. 489–500, 2019.
• [36] H.-K. Kim, “System and method for processing multimedia packets for a network,” US Patent No. 7,236,481 B2, 2002, https://patents.google.com/patent/US723648 1B2/en
• [37] X. Chen, A. Stidwell, and M. Harris, “Radiotelecommunications apparatus and method for communications internet data packets containing different types of data,” US Patent No. 7,558,240 B2, 2009, https://patents.google.com/patent/US9351923B2/en
• [38] M. Ziółkowski and O. Tikhonenko, “Multiserver queueing system with non–homogeneous customers and sectorized memory space,” in Communications in Computer and Information Science, CN 2018, vol. 860, A. Kwiecien, P. Gaj, M. Sawicki, G. Suchacka, Eds. Springer, Cham, 2018, pp. 272–285,.
• [39] O. Tikhonenko and M. Ziółkowski, “Queueing systems with non-homogeneous customers and infinite sectorized memory space,” in Communications in Computer and Information Science, CN 2019, vol. 1039, A. Kwiecien, P. Gaj, M. Sawicki, Eds., Springer, Cham, 2019, pp. 316–329.
• [40] O. Tikhonenko, M. Ziółkowski, and W.M. Kempa, “Queueing systems with random volume customers and a sectorized unlimited memory buffer,” Int. J. Appl. Math. Comut. Sci., vol. 31, no. 3, pp. 471–486, 2021.
• [41] J. Sztrik, Basic Queueing Theory, University of Debrecen, Faculty of Informatics, 2012.
• [42] M.L. Abell and J.P. Braselton, The Mathematica Handbook, Elsevier, 1992.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).