The queueing system in which the losses of incoming customers (tasks) are possible due to the introduction of a special renovation mechanism is under consideration. The renovation mechanism means that the task at the moment of the end of its service with some probability may empty the buffer and leave the system, or with an additional probability may just leave the system without emptying the buffer. The queueing system consists of the server with general service time distribution and the buffer of unlimited capacity. The incoming flow of tasks is a Poisson one. The embedded upon the end of service times Markov chain is constructed and under the assumption of the existence of a stationary regime for the embedded Markov chain the formula for the probability generation function is derived. In addition, the next probability characteristics (based on the embedded Markov chain) are obtained: the probability of the system being empty, the probability of a task in the buffer to be dropped (not to be dropped), the probability distribution of served (dropped) tasks. Also the average numbers of customers in the system, dropped customers and served customers (based on the embedded Markov chain) are derived as the service waiting time distribution for non-dropped tasks and the average service waiting time for non-dropped tasks.
1. Introduction
In this work we will consider the well-known M jGj1j1 system [
The renovation mechanism as some other mechanisms (failure of an unreliable
server [
In [
System description and stationary distribution of the embedded
Markov chain, probability generation function
If we introduce the probability i = R01 ( ix!)i e xdB(x) (i > 0) that during service time exactly i (i > 0) other customers may enter the system, then we obtain the matrix of transition probabilities for the embedded Markov:
The matrix of transition probabilities is a stochastic one.
If we denote by pi (i > 0) the probability, that there are i customers in the system upon service completion, and suppose that the stationary probability distribution of embedded Markov chain exists, then from (1) we obtain the following system for steadystate probabilities pi: p0 =
pi = ipp0 + i+1 1 with normal condition P pi = 1.
i=0
In order to obtain the formula for the probability p0 of system being empty just after the end of the service the probability generation function P (z) is introduced: P (z) = 1 X pizi; i=0 and can be written by multiplying (2) by z0 and (3) by zi (i > 1) in following form: (3) (4) (5) where
P (z) = (1 z)pp0 ( p ( z) zq
; (
1 z) = X izi = i=0
X1 zi Z1 ( x)i
e i=0 0
xdB(x): z) z i!
If p = 1 then (4) coincides with the Pollaczek-Khinchin formula for classic M jGj1j1
queue [
By using the P (z) analyticity property [
z = 0: (1 z0)pp0 ( z0)
z0q = 0; p0 =
qz0 (1 z0)p ( z0) : where from it follows that function).
Also, if we consider p = 1 (q = 1 p = 0) then we will get the well-known expression
1
b [
Probability-time characteristics In a similar way we may define the probability distribution p(loss) that exactly i i (i > 0) tasks from the buffer will be dropped later if at initial moment just after the end of the service there were at least i tasks in the buffer: Here b – is the average number of tasks arriving into the system during a service time of a single task (single service time).
Let us introduce the probability p(serv) that a task from the buffer will not be dropped at the moment just after the end of the service and will be eventually serviced (of course, if the system is not empty): p(serv) = 1 The P (p) — is the value of probability generation function (4) P (z) when z = p, 1 p0 — the probability that the system is not empty, p0 is obtained in (5).
The probability p(loss) that even one task being in the buffer at the moment just after the end of the service will be dropped later is: p(loss) = 1 p0 i=2
k=0 1 1 i 2 X pi X qpk = 1 (P (p) p(1 p0) : p0)
The probability distribution pi(serv) that exactly i (i > 0) tasks from the buffer will be served later if at initial moment just after the end of the service there were at least i tasks in the buffer: 8
(loss) = p0 + >>>p0 > > < 1 X pipi 1; i=1 > (loss) = q >>p > i > : The normalization requirement P1 pi(loss) = 1 is also valid.
i=0
For both distributions (pi(serv) and pi(loss), i > 0) the probabilities pi (i > 0) are the stationary probabilities of embedded Markov chain distribution.
The average number N (serv) of tasks (of remained in the buffer just after the end of the service) which will be served and the average number N (loss) of tasks (of remained in the buffer just after the end of the service) which will be lost may be obtained from (7) and (8) by definition:
N (serv) = N (loss) =
X1 ipi(serv) = 1 i=0 1 X ipi(loss) = N i=0
P (p) q
; 1
P (p)
q
;
where P (p) — the probability generation function (4) for z = p and N — the average
number of tasks (6). If p = 1 (q = 0) then N (serv) = N for M jGj1j1 queue [
The average characteristics N is the sum of (9) and (10).
Now let us consider the waiting time distribution for served task (customer). If we define as W (serv)(x) the probability, that the waiting time for the last task in the buffer (just after the end of the service) will be less than x, then we obtain:
W (serv)(x) =
1 (1 p0)p(serv) 1 X W (serv)(x)pi;
i i=1 here W (serv)(x) is the probability, that the waiting time for the i-th customer in the i 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 probability (1 p0)p(serv) is the probability of condition that just after the end of the service our system is not empty and all the tasks from the buffer will be served later.
The Laplace–Stieltjes transformation (LST) of (11) is: (9) (10) (11) !(serv)(s) =
1 (1 p0)p(serv) p1 + 1 X pipi 1 (s)i 1 i=2 ! 1
= = (1 p0)p(serv)
P (p (s))
p0 p (s) ; (12) here s is LST of service time distribution function B(x).
The mean waiting time of the customer which received service is obtained by differentiation of (12) at s = 0: w(serv) = !(serv)(s) 0 s=0 = b (1
P 0(p) p0)p(serv) 1 ; where
P 0(p) = b p0 p 2( q) ( q) qp 0 ( q) + q
( q) + p 0 ( q) (1 4.
Conclusions
The paper considers the queuing system with full renovation. Analytical expressions
for the main performance characteristics for the embedded Markov chain are obtained.
The study of M jGj1j1 queues with the general renovation as well as with renovation
and repeated service (due to [
Acknowledgments
The work is partially supported by RFBR grants No 15-07-03007, No 15-07-03406, and No 14-07-00090. The publication was financially supported by the Ministry of Education and Science of the Russian Federation (the Agreement number 02.A03.21.0008).