Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers

• BibTex
• RIS
• APA
• Harvard
• IEEE
• MLA
• Vancouver
• Chicago

@article{Zhernovyi_2018,
   doi = {10.17512/jamcm.2018.2.08},
   url = {https://doi.org/10.17512/jamcm.2018.2.08},
   year = 2018,
   publisher = {The Publishing Office of Czestochowa University of Technology},
   volume = {17},
   number = {2},
   pages = {93--103},
   author = {Yuriy Zhernovyi and  Bohdan Kopytko},
   title = {Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers},
   journal = {Journal of Applied Mathematics and Computational Mechanics}
}

TY  - JOUR
DO  - 10.17512/jamcm.2018.2.08
UR  - https://doi.org/10.17512/jamcm.2018.2.08
TI  - Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers
T2  - Journal of Applied Mathematics and Computational Mechanics
JA  - J Appl Math Comput Mech
AU  - Zhernovyi, Yuriy
AU  - Kopytko, Bohdan
PY  - 2018
PB  - The Publishing Office of Czestochowa University of Technology
SP  - 93
EP  - 103
IS  - 2
VL  - 17
SN  - 2299-9965
SN  - 2353-0588
ER  - 

Zhernovyi, Y., & Kopytko, B. (2018). Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers. Journal of Applied Mathematics and Computational Mechanics, 17(2), 93-103. doi:10.17512/jamcm.2018.2.08

Zhernovyi, Y. & Kopytko, B., 2018. Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers. Journal of Applied Mathematics and Computational Mechanics, 17(2), pp.93-103. Available at: https://doi.org/10.17512/jamcm.2018.2.08

[1]Y. Zhernovyi and B. Kopytko, "Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers," Journal of Applied Mathematics and Computational Mechanics, vol. 17, no. 2, pp. 93-103, 2018.

Zhernovyi, Yuriy, and Bohdan Kopytko. "Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers." Journal of Applied Mathematics and Computational Mechanics 17.2 (2018): 93-103. CrossRef. Web.

1. Zhernovyi Y, Kopytko B. Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers. Journal of Applied Mathematics and Computational Mechanics. The Publishing Office of Czestochowa University of Technology; 2018;17(2):93-103. Available from: https://doi.org/10.17512/jamcm.2018.2.08

Zhernovyi, Yuriy, and Bohdan Kopytko. "Recurrence relations for two-channel queueing systems with Erlangian service times and hysteretic strategy of random dropping of customers." Journal of Applied Mathematics and Computational Mechanics 17, no. 2 (2018): 93-103. doi:10.17512/jamcm.2018.2.08

RECURRENCE RELATIONS FOR TWO-CHANNEL QUEUEING SYSTEMS WITH ERLANGIAN SERVICE TIMES AND HYSTERETIC STRATEGY OF RANDOM DROPPING OF CUSTOMERS

Yuriy Zhernovyi ¹, Bohdan Kopytko ²

¹ Ivan Franko National University of Lviv, Lviv, Ukraine
² Institute of Mathematics, Czestochowa University of Technology
Częstochowa, Poland
yu.zhernovyi@lnu.edu.ua, bohdan.kopytko@im.pcz.pl

Received: 2 May 2018; Accepted: 18 June 2018

Abstract. This article proposes a method of study the M/E_s/2/m and M/E_s/2/∞ queueing systems with a hysteretic strategy of random dropping of customers. Recurrence relations are obtained to compute the stationary distribution of the number of customers and steady-state characteristics. The constructed algorithms were tested on examples with the use of simulation models constructed with the help of GPSS World.

MSC 2010: 60G10, 60J28, 60K25, 93B40

Keywords: two-channel queueing system, Erlangian service times, random dropping of customers, fictitious phase method, hysteretic strategy, recurrence relations, steady-state characteristics

1. Introduction

For investigating queueing systems with Erlang distributions and, in particular, the M/E_s/n/∞ system, the fictitious phase method developed by A.K. Erlang [1] is used. For the Erlang distribution of the sth order of service time, it is supposed that each customer sequentially passes through phases of service whose durations are distributed by exponential laws with parameters respectively.

Accounting for phases requires the fixation of the corresponding states and leads to the increase in the cumbersomeness of the description of a queuing system with phase-type distributions. The direct solution of a system of equations for steady-state probabilities of states can result in being impossible in view of a large size of the coefficient matrix of a system. The algorithmic approach is most expedient since it presumes the obtaining of a solution to systems of equations in the form of recursive formulas or in the form of matrix recurrence relations and algorithms [2-10]. The method proposed in [7-10] is based on the use of direct recurrence relations following immediately from system equations for steady-state probabilities. It does not contain iterations and it does not presume preliminary transformations of the system of equations being solved.

The objective of this article is the construction of recurrent algorithms with the help of the fictitious phase method to compute the steady-state distribution of the number of customers in the M/E_s/2/m and M/E_s/2/∞ queuing system, where with hysteretic strategy of the random dropping of customers. The random dropping of customers is used in queuing systems with a view for preventing overloads when each arriving customer can be discarded with a definite probability dependent on the queue length at the moment of arrival of a customer even if the buffer is not completely filled [11-13].

2. The M/E_s/2/m system with hysteretic strategy of random dropping of customers

Let us consider the M/E_s/2/m system, where and is the maximum number of customers who can simultaneously be in the queue. The input flow of customers is Poisson, i.e., the time intervals between the moments of arrival of customers adjacent in time are independent random variables exponentially distributed with the parameter The service time of each customer is distributed according to the generalized Erlang law, of the order so the service time is the sum of independent random variables exponentially distributed with parameters respectively.

We consider the random dropping of customers that is implemented according to the following rule: if, at the moment of arrival of a customer, the number of customers in the system is equal to (without making allowance for the arrived one), then the customer is accepted for service with probability and is refused (discarded) with probability

We consider a hysteretic strategy of the random dropping of customers with two thresholds and () and with two operating modes, namely, basic and dropping mode. Assume that when for the basic mode and when for the dropping mode. The dropping mode continues from the moment when the number of customers in the system achieves the value of up to the moment when the number of customers is re- duced to the value of If, at the moment of arrival of a customer, the condition is satisfied, then the mode is not changed. The rate of the simplest flow of customers accepted for service in the dropping mode is equal to In a partial case of the hysteretic strategy, assuming that for all in the dropping mode. If then where

The M/E_s/2/m system with the hysteretic strategy of the random dropping of customers we denote by M(h₁,h₂)/E_s/2/m. We introduce the following designations for system states in the basic mode: signifies that customers are absent in the system; signifies that k customers are present in the system and that two customers are at the ith phase of service and at the jth one respectively. The states correspond to one working channel and jth phase of service. We denote the steady-state probabilities of staying the system at the states and by and respectively. Let be the state similar to in the dropping mode and be the steady- state probability of staying the system at the state We assume that

To determine steady-state probabilities, we obtain the system of homogeneous algebraic equations with normalization condition

(1)

Introducing the notation

and using the system of algebraic equations, we find:

(2)

Recurrence relations (2) allow one to compute and as linear func- tions of the unknown parameters and in the following order:

To determine unknown parameters and we use the system that consists of equations that have not been involved in obtaining recurrence relations (2),

We use normalization condition (1) and determine the steady-state probabilities by the formulas

Here is steady-state probability of presence customers in the system.

We calculate the steady-state characteristics - the average number of customers in the system the average queue length average waiting time and service probability - by the formulas

3. The system without restrictions on the queue length

For the M(h₁,h₂)/E_s/2/∞ system, any constraint on the queue length is absent and, for the existence of stationary distribution of the number of customers in the system, the condition must be satisfied. Determining approximate values of steady-state probabilities is reduced to the use of recurrence relations (2) for large values of m. We choose the number so large that one of the conditions (or each of these conditions) specifying the accuracy of determining steady-state probabilities is fulfilled. These conditions can be specified, for example, in the form

(3)

Here and are positive numbers specifying the required accuracy of computa- tions; and are approximate values of steady-state characteristics and computed using steady-state probabilities is an approximate value of a steady-state probability which is obtained as a result of truncation of an infinite system of equations for steady-state probabilities.

4. Numerical examples

Let us consider examples of determining steady-state characteristics of the M(h₁,h₂)/E₅/2/∞ queuing system for different values of the thresholds and Let the probabilities for the dropping mode be set according to the rule: for For comparison, we calculate the stationary character- istics of the M/E₅/2/43 system, which does not apply the random dropping of customers.

The values of the steady-state probabilities and stationary characteristics of the M(h₁,h₂)/E₅/2/∞ system for cases 1-3, found using the recurrence relations obtained in this paper, as well as of the M/E₅/2/43 system, are presented in Tables 1 and 2. In order to verify the obtained values, Table 2 contains the computing results evaluated by the GPSS World simulation system [14] for the simulation time value

In computing approximate values of steady-state probabilities , the value of was selected so large that conditions (3) were satisfied when The obtained minimal values of for cases 1-3 are equal to 45, 45 and 47 respectively.

Analyzing the results, presented in Table 2, we see that the control of the input flow rate with the help of random dropping of customers makes it possible to considerably reduce the average queue length with an insignificant decrease in the system throughput. Thus, the decrease in the average queue length in the M(h₁,h₂)/E₅/2/∞ system (the case of ) in comparison with the M/E₅/2/43 system amounts to 81.6%, with a decrease in the relative throughput by 5.3%. If the value of the threshold increases, leaving the same value of then and increase.

Table 1

Stationary distribution of the number of customers in the systems

Table 2

Stationary characteristics of the systems

5. Conclusions

Using the method of fictitious phases, an algorithm for calculating the stationary distribution of the number of customers in the M/E_s/2/m systems with hysteretic strategy of the random dropping of customers, inclusive of the case is constructed. The obtained recurrence relations are used for the direct computation of the solutions of the algebraic system for the steady-state probabilities, which makes it possible to reduce the amount of computations in comparison with the direct or iterative classical methods. Using the obtained recurrence relations makes it possible to reduce the number of solved equations from to

References

[1] Brockmeyer, E., Halstrøm, H.L., & Jensen, A. (1948). The Life and Works of A.K. Erlang. Copenhagen: Danish Academy of Technical Sciences.

[2] Neuts, M.F. (1981). Matrix-geometric Solutions in Stochastic Models. Baltimore: The John’s Hopkins University Press.

[3] Bocharov, P.P., & Litvin, V.G. (1986). Methods of analysis and calculation of queuing systems with distributions of phase type, Avtomatika i Telemekhanika, 5, 5-23 (in Russian).

[4] Takahashi, Y., & Takami, Y. (1976). A numerical method for the steady-state probabilities of a GI/G/c queueing system in a general class. J. Oper. Res. Soc. Japan, 19, 2, 147-157.

[5] Ryzhikov, Yu.I. (1985). Recurrent calculation of multi-channel queueing systems with unlimited queue. Avtomatika i Telemekhanika, 6, 88-93 (in Russian).

[6] Ryzhikov, Yu.I. (1980). Algorithm for calculating a multichannel system with Erlang service. Avtomatika i Telemekhanika, 5, 30-37 (in Russian).

[7] Zhernovyi, K.Yu. (2017). Determining stationary characteristics of two-channel queueing systems with Erlangian distribution of service time. Cybernetics and Systems Analysis, 53, 1, 92-104.

[8] Zhernovyi, Yu.V., & Zhernovyi K.Yu. (2017). Determination of steady-state characteristics of three-channel queuing systems with Erlangian service times. Cybernetics and Systems Analysis, 53, 2, 280-292.

[9] Zhernovyi, Yu.V. (2017). Determining steady-state characteristics of some queuing systems with Erlangian distributions. Cybernetics and Systems Analysis, 53, 5, 776-784.

[10] Kopytko, B., & Zhernovyi, K. (2016). Steady-state characteristics of three-channel queueing systems with Erlangian service times. JAMCM, 15(3), 75-87.

[11] Chydziński, A. (2013). Nowe modele kolejkowe dla węzłów sieci pakietowych. Gliwice: Pracownia Komputerowa Jacka Skalmierskiego.

[12] Tikhonenko, O., & Kempa, W.M. (2013). Queue-size distribution in M/G/1-type system with bounded capacity and packet dropping. Communications in Computer and Information Science, 356, 177-186.

[13] Zhernovyi, Yu., Kopytko, B., & Zhernovyi K. (2014). On characteristics of the M^θ/G/1/m and M^θ/G/1 queues with queue-size based packet dropping. JAMCM, 13, 4, 163-175.

[14] Zhernovyi, Yu. (2015). Creating Models of Queueing Systems Using GPSS World. Saarbrücken: LAP Lambert Academic Publishing.