The Analysis of Queuing System with General Service Distribution and Renovation

Full Text

• Introduction Due to the study of mathematical models close to reality, there is a growing need to find new solutions and methods of queueing systems construction and analysis. One of the classical and already well-studied systems close to reality is the system M/G/1/ with the Poisson incoming flow and general service distribution. The described non-Markov random process - a process where the future state can not depend only on the state, viewed in the given time. The system M/G/1/ can be investigated by a variety of different approaches and one of them is the construction of the embedded Markov chain [1]. Thanks to the Pollaczek-Khinchin formula [2] for a given stationary probability distribution some other characteristics can be also derived. These characteristics of the system M/G/1/ with the standard service discipline FCFS (First Come, First Served) can be transferred to some other common discipline [1, 2]. However, trying to describe a real system, it is necessary to take into account the possibility of losing data in the system, for example, due to failure of an unreliable server [3] or due to arrival of some “viral” applications [4], and the other tasks in the buffer will be dropped. This situation may be investigated with the help of queueing system M/G/1/ with renovation without repeated service [5-9]. Systems with renovation mechanism can be used for traffic control mechanism modeling [10]. We analyze the queueing system in which losses of the accepted customers are possible due to the so called renovation. • System Description Consider queueing system with the general service time distribution (), Poisson arrival rate and renovation. The renovation mechanism, due to [5, 7, 8], operates as follows. At the end of each service completion the customer leaving server with the (known) probability empties the buffer and leaves the system. With the probability = 1 it leaves the system without having any effect on the buffer contents. If p = 1 one obtains the well-known //1/ queue. As usual, if one considers the total number of customers , ;;; 0 in the system just after -th service completion, then , ;;; 0 is the embedded Markov chain of the queue-length process (), ;;; 0 . Denote the state set of the embedded Markov by = 0, 1, . . . . The matrix of transition probabilities for the embedded Markov chain has the form: • Stationary Distribution of the Embedded Markov Chain Denote by , ;;; 0, the probability, that there are i customers in the system upon service completion. Then, assuming that the stationary distribution exists, one has the following system for : Here denotes the probability that during service time exactly other customers have entered the system. It is straightforward to show, that the probability generation function (PGF) and can be written in the following form: where If = 1 then (3) coincides with the Pollaczek-Khinchin formula for classic //1/ queue. • Performance Characteristics Using the analytically property of () one can obtain the expression for the probability of system being empty upon service completion. Consider the equation It has the unique solution 0 < 0 < 1 for [0, 1]. As the denominator of (3) vanishes at point = 0 then the numerator of (3) must also vanish at this point. Thus wherefrom it follows that If p = 1 (q = 1 = 0) one gets the well-known expression 0 = 1 lb, where b is the mean service time. The average number N of customers in the system upon service completion is equal Here lb is the average number of customers arrived during a single service time. Let us denote by (serv) the probability that all the customers in the system just after the end of the service will not be dropped and will eventually receive service. Then The P () is the value of probability generation function (3) P (z) with z = . Let us denote as W (serv)(x) the probability, that the waiting time for the last customer in the buffer (just after the end of the service) will be less than x: here W (serv)(x) is the probability, that the waiting time for the i-th customer in the buffer (just after the end of the service) will be less than x with the requirement that there were exactly i customers just after the end of service. The Laplace-Stieltjes transformation of W (serv)(x) has the form: The mean waiting time of the customer which received service is equal to: • Conclusion The paper considers the queueing system with full renovation. Analytical expressions for the main performance characteristics are obtained. The study of M/G/1/ queues with the general renovation as well as with renovation and re-service (due to [11]) is an open issue.

About the authors

E V Bogdanova

RUDN University (Peoples’ Friendship University of Russia)

Email: official_kb@mail.ru
Department of Applied Probability and Informatics 6, Miklukho-Maklaya str., Moscow, Russia, 117198

T A Milovanova

RUDN University (Peoples’ Friendship University of Russia)

Email: tmilovanova77@mail.ru
Department of Applied Probability and Informatics 6, Miklukho-Maklaya str., Moscow, Russia, 117198

I S Zaryadov

Institute of Informatics Problems

Email: izaryadov@sci.pfu.edu.ru
Federal Research Center “Computer Science and Control” Russian Academy of Science Vavilova str., Moscow, Russia, 119333

References