The potentials method for the M/G/1/m queue with customer dropping and hysteretic strategy of the service time change
Yuriy Zhernovyi
,Bohdan Kopytko
Journal of Applied Mathematics and Computational Mechanics |
Download Full Text |
THE POTENTIALS METHOD FOR THE M/G/1/M QUEUE WITH CUSTOMER DROPPING AND HYSTERETIC STRATEGY OF THE SERVICE TIME CHANGE
Yuriy Zhernovyi^{ 1}, Bohdan Kopytko^{ 2}
^{1} Ivan
Franko National University of Lviv
Lviv, Ukraine
^{2} Institute of Mathematics, Czestochowa University of Technology
Częstochowa, Poland
yu.zhernovyi@lnu.edu.ua, bohdan.kopytko@im.pcz.pl
Abstract. We propose a method for determining the probabilistic characteristics of the queueing system with the random dropping of arrivals and distribution of the service time depending on the queue length. Two sets of service modes, with the service time distribution functions and respectively, are used according to the two-threshold hysteretic strategy. The Laplace transforms for the distribution of the number of customers in the system during the busy period and for the distribution function of the length of the busy period are found. The developed algorithm for calculating the stationary characteristics of the system is tested with the help of a simulation model constructed with the assistance of GPSS World tools.
Keywords: single-channel queueing system, random dropping of customers, hysteretic strategy for service time, potentials method, stationary characteristics
1. Introduction
Studies show [1-3] that the random dropping of arrivals is a powerful tool for parameter control of a queueing system. The dropping can not only regulate the queue length, loss probability of customers, waiting time, and queue length variance, but also regulate several of these parameters simultaneously.
In order to increase the system capacity, threshold strategies of the service intensity (service time) change are used in queueing systems. In the general case, the essence of this strategy is that the service time distribution depends on the number of customers in the system at the beginning of each customer service [4]. With the help of the potentials method, we have developed an efficient algorithm for computing the stationary distribution of the number of customers in the systems with threshold functioning strategies [4-8].
In this paper we consider the queueing system with random dropping of customers and distribution of the service time depending on the queue length. Two sets of service modes (the main mode and overload mode), with the service time distribution functions and respectively, are used according to the two-threshold hysteretic strategy. The overload mode with the functions starts functioning if at the beginning of service of a customer, the number of customers in the system satisfies the condition The return to the main mode with the functions carried out at the beginning of service of the customer, for which where
Each arriving customer can be accepted for service with a probability depending on the queue length. We assign this probability according to the rule: if at the time of the arrival of a customer customers are in the system, then the customer is accepted for service with probability and leaves the system (is discarded) with probability Fix a threshold value and suppose that for and for In paper [9] we also studied the queueing systems with random dropping of arrivals. In contrast to this article, in [9] the probability does not change during the time interval from the beginning to the completion of service of each customer.
2. Basic random walks
We consider the system, where is the maximum number of custom- ers in the queue. Let be a parameter of the exponential distribution of the time intervals between moments of arrival of customers. Suppose that, if at the beginning of service of a customer the number of customers in the system is equal to then the service time of this customer is a random variable with distribution function for the main mode and for the overload mode.
Denote by the conditional probability, provided that at the initial time the number of customers in the queueing system is equal to and by (P) the conditional expectation (the conditional probability) if the system starts to work at the time of arrival of the first customer. Let be the number of customers arriving in the system during the time interval Let
For and consider the sequences and defined by the relations:
(1) |
Similarly, for and we set the sequences and
(2) |
Let and denote the exponentially distributed random variables with parame- ter and respectively, and is a random variable distributed according to the law of Pascal, that is, It is known [10], that that is, as a result of a random decimation of the simplest flow we obtain a simplest flow.
Given the above, for we find
For we obtain
Taking into account the expressions for and equalities
by (1), (2) calculate the terms of the sequences and
For we find
(3) |
For and we obtain
(4) |
Expressions for and are similar with presented in (3) and (4) for or and for respectively, if we replace and by and
Note that
(5) |
Introduce the notation:
With the help of equalities (1)-(5) we can obtain expressions for the members of the sequences and
3. Distribution of the number of customers in the system during the busy period
Let be the number of customers in the system at time Denote by () the conditional probability, provided that at the initial time the number of customers of the system is equal to and the service begins with the service time distributed according to the law
Let denote the length of the first busy period for the considered queueing system, and for
It is evident that With the help of the formula of total probability we obtain the equalities:
(6) |
Here is the indicator of a random event ; it equals 1 or 0 depending on whether or not the event occurs.
Introduce the notation:
Taking into account the relations (1) and (2), from (6) we obtain the system of equations for the functions and :
(7) |
(8) |
with the boundary conditions
(9) |
For solving the systems of equations (7)-(9) we will use the functions and defined by the recurrence relations:
(10) |
Introduce the notation:
Reasoning as in the proof of Theorem 1 of [7], we obtain the following statement.
Theorem 1. For all and the equalities
are fulfilled, where
4. Busy period and stationary distribution
If the system starts functioning at the moment when the first customer arrives, then
(11) |
To obtain a representation for we sum up equalities (11) for running from 1 to . Given the definitions of and it is not difficult to ascertain that
Introduce the notation:
Thus, (11) confirms the following statement.
Theorem 2. The Laplace transform of the distribution function of the length of the busy period is defined as
(12) |
To find we need to pass to the limit in (12) as We use the sequences and as well as sequences and obtained by limit passages: For and (10) implies the recurrence relations:
(13) |
Note that
Using the relations (13) and taking into account the equalities
we can prove that
(14) |
Given (5) and (14), using (12) we obtain the following statement.
Theorem 3. The mean length of the busy period is determined in the form
(15) |
where
Introduce the notation: Reasoning as in the paper [4], from (11) we obtain formulas for the stationary distribution of the number of customers in the system.
Theorem 4. The stationary distribution of the number of customers in the system is given by
(16) |
where
Using (15) we find the ratio of the mean number of customers served per unit of time to the mean number of all arriving customers per unit time and obtain the formula for the stationary service probability
(17) |
where
We find the stationary queue characteristics - the average queue length and average waiting time - by the formulas
(18) |
5. Example for calculating of stationary characteristics
Assume that the uniform distribution on the intervals and corresponds to the distribution functions of the service time and respectively. Thus,
The row of Table 1 contains steady-state probabilities calculated by the formulas (16). For the sake of comparison, the same table contains the corresponding probabilities evaluated by the GPSS World simulation system [11, 12] for the time value The values of the stationary characteristics found by the formulas (15), (17) and (18), and calculated with the help of GPSS World, are shown in Table 2.
Table 1
Stationary distribution of the number of customers in the system
Number of customers k |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
p_{k} |
0.00373 |
0.01504 |
0.05757 |
0.13005 |
0.24539 |
0.33756 |
0.15697 |
0.05369 |
p_{k} (GPSS World) |
0.00371 |
0.01506 |
0.05768 |
0.13005 |
0.24527 |
0.33713 |
0.15693 |
0.05418 |
Table 2
Stationary characteristics of the system
Characteristic |
E(t) |
E(Q) |
E(W) |
P_{sv} |
Analytical value |
26.724 |
3.511 |
0.541 |
0.650 |
Value according to GPSS World |
26.894 |
3.512 |
0.541 |
0.649 |
Calculations show that if the random dropping of customers is not used, then for the considered data the value of the capacity of the system is increased by 13.1%, but and are also increased by 25.6% and 11.1% respectively.
6. Conclusions
With the help of the potentials method, we have obtained simple and suitable formulas for numerical realization for finding the stationary characteristics of the queueing system with the random dropping of customers and hysteretic change of the service time. We have examined a fairly general statement of the problem, because we assume that the service time depends on the number of customers in the system and the dropping probability is a function of the queue length at the time of arrival of a customer.
Our approach, unlike most of the methods used to study the semi-Markov models of queueing, allows to investigate not only stationary, but also the transient regime of the system, in particular, to find the Laplace transforms for the distribution of the number of customers in the system during the busy period and for the distribution function of the length of the busy period.
References
[1] Chydziński A., Nowe modele kolejkowe dla węzłów sieci pakietowych, Pracownia Kompute- rowa Jacka Skalmierskiego, Gliwice 2013.
[2] Tikhonenko O., Kempa W.M., Queue-size distribution in M/G/1-type system with bounded capacity and packet dropping, Communications in Computer and Information Science 2013, 356, 177-186.
[3] Kempa W.M., A direct approach to transient queue-size distribution in a finite-buffer queue with AQM, Applied Mathematics and Information Sciences 2013, 7, 3, 909-915.
[4] Zhernovyi K.Yu., Zhernovyi Yu.V., M^{q}/G/1/m and M^{q}/G/1 systems with the service time dependent on the queue length, Journal of Communicat. Technology and Electronics 2013, 58, 12, 1267-1275.
[5] Zhernovyi Yu., Zhernovyi K., Potentials Method for Threshold Strategies of Queueing, LAP Lambert Academic Publishing, Saarbrücken 2015 (in Russian).
[6] Zhernovyi K.Yu., Stationary characteristics of the M^{q}/G/1/m system with the threshold functioning strategy, Journal of Communicat. Technology and Electronics 2011, 56, 12, 1585-1596.
[7] Zhernovyi Yu., Kopytko B., The potentials method for a closed queueing system with hysteretic strategy of the service time change, Journal of Applied Mathematics and Computational Mechanics 2015, 14(2), 131-143.
[8] Zhernovyi Yu.V., Zhernovyi K.Yu., Method of potentials for a closed system with queue length dependent service times, J. of Communicat. Technology and Electronics 2015, 60, 12, 1341-1347.
[9] Zhernovyi Yu., Kopytko B., Zhernovyi K. On characteristics of the M^{q}/G/1/m and M^{q}/G/1 queues with queue-size based packet dropping, Journal of Applied Mathematics and Computational Mechanics 2014, 13(4), 163-175.
[10] Wentzel E.S., Ovcharov L.A., Theory of Stochastic Processes and its Engineering Applications, Vysshaya Shkola, Moscow 2000 (in Russian).
[11] Zhernovyi Yu., Creating Models of Queueing Systems Using GPSS World, LAP Lambert Academic Publishing, Saarbrücken 2015.
[12] Boyev V.D., Systems Modeling, Tools of GPSS World, BHV-Petersburg, St. Petersburg 2004 (in Russian).