=Paper=
{{Paper
|id=Vol-2177/paper-11-c007
|storemode=property
|title=
On the Simulations of the Limited Resources Queueing Systems
|pdfUrl=https://ceur-ws.org/Vol-2177/paper-11-c007.pdf
|volume=Vol-2177
|authors=Eduard S. Sopin,Konstantin E. Samouylov,Sergey Ya. Shorgin
}}
==
On the Simulations of the Limited Resources Queueing Systems
==
https://ceur-ws.org/Vol-2177/paper-11-c007.pdf
75
UDC 519.218.31
On the Simulations of the Limited Resources Queueing Systems
Eduard S. Sopin*† , Konstantin E. Samouylov*† , Sergey Ya. Shorgin†
*
Department of Applied Probability and Informatics
Peoples’ Friendship University of Russia (RUDN University)
6 Miklukho-Maklaya st., Moscow, 117198, Russian Federation
†
Institute of Informatics Problems, Federal Research Center
“Computer Science and Control” of the Russian Academy of Sciences
44-2 Vavilova st., Moscow, 119333, Russian Federation
Email: sopin_es@rudn.university, samuylov_ke@rudn.university, sshorgin@ipiran.ru
Queuing systems with limited resources are widely applicable in the modelling and analysis
of modern infocommunication systems. The main feature of them is that customers occupy not
only a server, but also a volume of multiple resources, for the whole serving time. Processor
time, memory, disc space may serve as examples of resources in a computing system, and
frequency range and signal power are examples of resources in modern wireless networks.
However, even under simplest assumptions on the arrival flows and service times distributions,
computational algorithms still have very high complexity, since deduced formulas for the
main stationary characteristics include multiple convolutions of the resource requirements
distribution function. Therefore, there is absolute necessity in simulation tools for limited
resources queuing systems. In the paper, we describe the general queuing system with multiple
customer types and multiple limited resources, present the developed simulator and provide
some simulation results for various types of arrival and serving processes.
Key words and phrases: queuing system, limited resources, random requirements,
simulation.
Copyright © 2018 for the individual papers by the papers’ authors. Copying permitted for private and
academic purposes. This volume is published and copyrighted by its editors.
In: K. E. Samouylov, L. A. Sevastianov, D. S. Kulyabov (eds.): Selected Papers of the VIII Conference
“Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”,
Moscow, Russia, 20-Apr-2018, published at http://ceur-ws.org
76 ITTMM—2018
1. Introduction
In the queuing systems with limited resources, each arriving customer requires not
only a server, but also a random volume of resources. This concept represents the
evolution of Kelly networks [7], in which customers occupy fixed volume of resources.
The key advantage of the queuing systems with limited resources in the communication
systems analysis is possibility to capture characteristic properties of radio resources
allocation schemes in modern wireless networks [2,5,9] by definition of specific cumulative
distribution function (CDF) of resource requirements.
There are plenty of analytical results of resource queuing systems analysis. However,
they were obtained under assumption of Poisson [10, 13, 17–20] or state-dependent
Poisson arrivals [11]. Moreover, exact algorithms for evaluation of the main probabilistic
characteristics obatined from the analytical formulas remain too complex due to multiple
convolutions of the resource requirements CDF.
In case of discrete resources, the recurrent algorithm was developed for evaluation of
stationary measures [16]. In [16], the sampling approach was also proposed for the case
of continuous resources, but the algorithm still have high complexity.
Since arrivals of customers in modern networks do not have Poisson distribution in
most cases, a simulation tool is required to evaluate stationary measures of queuing
systems with limited resources. In the paper, we start with brief description of the
mathematical model, then provide the design of the developed simulation tool. We
provide the detailed numerical analysis for various distributions of arrival and serving
processes and finally give a brief summary in the conclusion.
2. Queuing system with limited resources
We consider a multiserver queueing system with 𝑁 servers and 𝑀 types of resources,
in which arriving customer occupies a server and a vector of resources. The total volume
of resources in the system is R = (𝑅1 , 𝑅2 , . . . , 𝑅𝑀 ) and 𝐿 is the number of customer
types. Interarrival and serving times of 𝑙-type customers are independent identically
distributed random variables with CDFs 𝐴𝑙 (𝑥) and 𝐵𝑙 (𝑥) respectively. Volumes of 𝑙-type
customers’ resource requirements are also independent identically distributed random
variables, independent of arrival and serving processes and have CDFs 𝐹𝑙 (x). Figure 1
shows the scheme of the queuing system.
R1 RM
N
A1 ( x), B1 ( x)
Fk (x) CDFrequired
of amount of resources
for a customer
xk ,1
AL ( x), BL ( x)
k xk , M
lk
customer
type
Figure 1. Queuing system with limited resources
Sopin Eduard S., Samouylov Konstantin E., Shorgin Sergey Ya. 77
(1) (1)
Let 𝑎𝑖 and 𝑏𝑖 be the average of interarrival and serving times respectively. Then
the offered load is
𝐿 (1)
𝑖
∑︁ 𝑏
𝜌=(1)
.
𝑎
𝑙=0 𝑖
The stochastic process 𝑋(𝑡) = (𝜉(𝑡), 𝛼(𝑡), 𝛽(𝑡), 𝜃(𝑡), 𝛾(𝑡)) describes the system be-
haviour in time. Here 𝜉(𝑡) is the number of customers in the system at moment 𝑡 > 0,
𝛼(𝑡) = (𝛼1 (𝑡), . . . , 𝛼𝐿 (𝑡)) is the vector of the remaining times before next arrival, 𝛽(𝑡) =
(𝛽1 (𝑡), . . . , 𝛽𝜉(𝑡) (𝑡)) is the vector of residual service times, 𝜃(𝑡) = (𝜃1 (𝑡), . . . , 𝜃𝜉(𝑡) (𝑡))
is the vector of customer types and 𝛾(𝑡) is the matrix of occupied resources, where
𝛾𝑖,𝑗 (𝑡) denotes the volume of 𝑖-type resource occupied by 𝑗-th customer, 1 6 𝑖 6 𝑀 ,
1 6 𝑗 6 𝜉(𝑡). Note that 𝛼(𝑡) and 𝛽(𝑡) are decreasing with unit speed, while other
components of 𝑋(𝑡) change only at the moments of arrival or departure.
Let 𝛿(𝑡) = (𝛿1 (𝑡), . . . , 𝛿𝑀 (𝑡)) be the vector of total volume of occupied resources, where
𝜉(𝑡)
∑︀
𝛿𝑚 (𝑡) = 𝛾𝑚,𝑘 (𝑡). Denote the moment of arrival of the 𝑖-th customer and its resource
𝑘=1
requirements as 𝑡𝑖 and r𝑖 , 𝑖 > 1, respectively. If there is no free server (𝜉(𝑡𝑖 − 0) = 𝑁 ) or
not enough unoccupied resources (𝛿(𝑡𝑖 − 0) + r𝑖 > R), then the customer is lost. On the
contrary, if 𝜉(𝑡𝑖 − 0) < 𝑁 and there are enough resources, then the customer is accepted
and it occupies r𝑖 resources. Thus, if the customer is accepted, the system state changes
from (𝑘, (𝛼1 , . . . , 𝛼𝑖−1 , 0, 𝛼𝑖+1 , . . . , 𝛼𝐿 ), (𝛽1 , . . . , 𝛽𝑘 ), (𝜃1 , . . . , 𝜃𝑘 ), (𝛾1 , . . . , 𝛾𝑘 )) to (𝑘 +
1, (𝛼1 , . . . , 𝛼𝑖−1 , 𝛼𝑖 , 𝛼𝑖+1 , . . . , 𝛼𝐿 ), (𝛽1 , . . . , 𝛽𝑘 , 𝛽𝑘+1 ), (𝜃1 , . . . , 𝜃𝑘 , 𝑖), (𝛾1 , . . . , 𝛾𝑘 , 𝛾𝑘+1 )).
The volume of resources occupied by a customer remain constant until departure. On
the departure of a customer, it releases the server and resources, i.e. the system moves
from the state (𝑘, (𝛼1 , . . . , 𝛼𝐿 ), (𝛽1 , . . . , 𝛽𝑖−1 , 0, 𝛽𝑖+1 , . . . , 𝛽𝑘 ), (𝜃1 , . . . , 𝜃𝑘 ), (𝛾1 , . . . , 𝛾𝑘 ))
to (𝑘 − 1, (𝛼1 , . . . , 𝛼𝐿 ), (𝛽1 , . . . , 𝛽𝑖−1 , 𝛽𝑖+1 , . . . , 𝛽𝑘 ), (𝜃1 , . . . , 𝜃𝑖−1 , 𝜃𝑖+1 , . . . , 𝜃𝑘 ), (𝛾1 , . . . ,
𝛾𝑖−1 , 𝛾𝑖+1 , . . . , 𝛾𝑘 )).
In [10], the described system in case of Poisson arrivals and exponential service times
was analyzed. In [14], it was proved that stationary behavior of the limited resource
queuing systems under Poisson arrivals are insensitive to the service time distribution,
analogously to [15], so formulas (1) and (2) hold true for any distribution of the service
times. Stationary probabilities 𝑝𝑘𝑙1 ,...,𝑙 (x1 , . . . , xk ) that there are 𝑘 customers of types
𝑘
𝑙1 , . . . , 𝑙𝑘 and 𝑖-th customer occupies no more than x𝑖 resources is given by
𝑘
∏︁ 𝜆𝑙 𝑛
𝑝𝑘𝑙1 ,...,𝑙𝑘 (x1 , . . . , xk ) = 𝑝0 𝐹 (x1 ) · · · 𝐹 (x𝑘 ) , (1)
𝑘
𝑛=1
∑︀
𝜇𝑙𝑖
𝑖=1
where
⎛ ⎞−1
𝑁
𝑘 𝜌𝑘1 𝜌𝑘𝑟 𝑟 ⎠
𝐹1𝑘1 * . . . * 𝐹𝐿𝐿 (R) 1 . . . .
∑︁ ∑︁
𝑝0 = ⎝1 + . (2)
𝑟=1 𝑘1 +...+𝑘𝐿 =𝑟
𝑘1 ! 𝑘𝑟 !
Here 𝐹 (𝑘) (x) is 𝑘-fold convolution of the CDF 𝐹 (x) and sign * denotes convolution
operation.
3. Simulation tool description
In this section, we describe the simulation tool. The event-based approach was
utilized in the simulator, which is widly used for the analysis of event-based dynamic
78 ITTMM—2018
systems [4, 8, 12]. Figure 2 shows block-diagram of the simulation algorithm. Let us
describe it briefly.
Initialization
End of
Yes End
simulation
No
Release server and
resources Find the closest event
Arrival or
departure
departure
arrival
Customer Enough
No
blocked resources?
Yes
Occupy a server and a
volume of resources
Figure 2. Block-diagram of the simulation tool
1. Initial parameter setup. Set 𝑐𝑢𝑟𝑟𝑒𝑛𝑡_𝑡𝑖𝑚𝑒, 𝑎𝑟𝑟𝑖𝑣𝑎𝑙𝑠, all components of 𝑀 -
dimensional vector 𝑡𝑜𝑡𝑎𝑙_𝑜𝑐𝑐𝑢𝑝𝑖𝑒𝑑_𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠 and all components of 𝑁 ×𝑀 matrix
𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠 to 0. There are two event types: arrival and departure of customers.
Define components of 𝐿-dimensional vector 𝑎𝑟𝑟𝑖𝑣𝑎𝑙_𝑡𝑖𝑚𝑒 according to CDF 𝐴𝑙 (𝑥),
1 6 𝑙 6 𝐿 and set all elements of 𝑁 -dimensional vector 𝑑𝑒𝑝𝑎𝑟𝑡𝑢𝑟𝑒_𝑡𝑖𝑚𝑒 to infinity.
Define 𝑡𝑜𝑡𝑎𝑙_𝑛𝑢𝑚𝑏𝑒𝑟_𝑐𝑢𝑠𝑡𝑜𝑚𝑒𝑟𝑠 in the simulation session.
2. Start simulation cycle. The simulations continue until 𝑎𝑟𝑟𝑖𝑣𝑎𝑙𝑠 become equal to
𝑡𝑜𝑡𝑎𝑙_𝑛𝑢𝑚𝑏𝑒𝑟_𝑐𝑢𝑠𝑡𝑜𝑚𝑒𝑟𝑠. If simulation session continues, find the closest event
(corresponding to the smallest value in vectors 𝑎𝑟𝑟𝑖𝑣𝑎𝑙_𝑡𝑖𝑚𝑒 and 𝑑𝑒𝑝𝑎𝑟𝑡𝑢𝑟𝑒_𝑡𝑖𝑚𝑒),
set 𝑐𝑢𝑟𝑟𝑒𝑛𝑡_𝑡𝑖𝑚𝑒=𝑒𝑣𝑒𝑛𝑡_𝑡𝑖𝑚𝑒.
(a) If the closest event is arrival, then go to 3.
(b) If the closest event is departure, then go to 5.
Sopin Eduard S., Samouylov Konstantin E., Shorgin Sergey Ya. 79
3. Set 𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒_𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑚𝑒𝑛𝑡𝑠 of the customer according to CDF 𝐹𝑙 (x), where 𝑙
corresponds to the customer type, increment 𝑎𝑟𝑟𝑖𝑣𝑎𝑙𝑠 by one, check whether the
customer is accepted or not.
(a) If R − 𝑡𝑜𝑡𝑎𝑙_𝑜𝑐𝑐𝑢𝑝𝑖𝑒𝑑_𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠 > 𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒_𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑚𝑒𝑛𝑡𝑠 and one of
the components of 𝑑𝑒𝑝𝑎𝑟𝑡𝑢𝑟𝑒_𝑡𝑖𝑚𝑒 is equal to infinity, then customer is
accepted, go to 4.
(b) If R − 𝑡𝑜𝑡𝑎𝑙_𝑜𝑐𝑐𝑢𝑝𝑖𝑒𝑑_𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠 < 𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒_𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑚𝑒𝑛𝑡𝑠 or all compo-
nents of 𝑑𝑒𝑝𝑎𝑟𝑡𝑢𝑟𝑒_𝑡𝑖𝑚𝑒 are less than infinity, then the customer is blocked.
Set new 𝑎𝑟𝑟𝑖𝑣𝑎𝑙_𝑡𝑖𝑚𝑒, update statistics and go to 2.
4. Define a server to serve the customer, set the corresponding element of the vector
𝑑𝑒𝑝𝑎𝑟𝑡𝑢𝑟𝑒_𝑡𝑖𝑚𝑒 according to the the CDF 𝐵𝑙 (x) and set corresponding row of
matrix 𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠 to 𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒_𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑚𝑒𝑛𝑡𝑠. Increase 𝑜𝑐𝑐𝑢𝑝𝑖𝑒𝑑_𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠 by
𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒_𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑚𝑒𝑛𝑡𝑠 and set new 𝑎𝑟𝑟𝑖𝑣𝑎𝑙_𝑡𝑖𝑚𝑒. Update statistics and go to 2.
5. Decrease 𝑡𝑜𝑡𝑎𝑙_𝑜𝑐𝑐𝑢𝑝𝑖𝑒𝑑_𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠 by corresponding row of matrix 𝑟𝑒𝑠𝑜𝑢𝑟𝑐𝑒𝑠
and set the row to zero. Then set the corresponding element of 𝑑𝑒𝑝𝑎𝑟𝑡𝑢𝑟𝑒_𝑡𝑖𝑚𝑒
to infinity, update statistics and go to 2.
4. Simulation results
In this section, we present and discuss the simulation results. For the simplicity, we
consider the system with only one type of customers (𝐿 = 1) and one type of resources
(𝑀 = 1). Assume that 𝑁 = 100 and 𝑅 = 1.
We used gamma distribution for the interarrival times with the following probability
density function:
𝑒−𝑥/𝜃
𝑎(𝑥) = 𝑥𝑘−1 𝑘 , 𝑥 > 0,
𝜃 Γ(𝑘)
where Γ(𝑘) is the gamma-function. Three set of parameters were used with the same
average interarrival time 𝑎(1) = 10𝑠: (𝑘 = 1, 𝜃 = 10), (𝑘 = 5, 𝜃 = 2), (𝑘 = 10, 𝜃 = 1).
The resource requirements CDF 𝐹 (𝑥) was derived in [16], based on works [3, 6] for
machine-to-machine communications in a LTE cell:
⎧
⎪
⎪ 0, 𝑥 6 0,
⎨ (︁ 𝐷 )︁𝐸
𝐹 (𝑥) = 𝐶 𝑒𝑥 −1 , 0 < 𝑥 6 𝜑, (3)
⎪
⎪
1, 𝑥 > 𝜑,
⎩
where 𝐶 = 0.144, 𝐷 = 0.01, 𝐸 = −0.4 and 𝜑 = 0.1318. The values of constants in
formula (3) were calculated according to 3GPP standards [1].
Figures 3 and 4 show the behaviour of blocking probability and average volume of
occupied resources in case of equiprobability distribution of service times. The serving
intensities were chosen so that the offered load 𝜌 varies from 20 to 100.
5. Conclusions
In the paper, we developed the tool for simulation of queuing systems with limited
resources and random resource requirements. The simulation algorithm was described
briefly and some numerical examples were shown. The tool may be used for not only
evaluations of performance measures of contemporary wireless networks, but also for our
future research in developing efficient approximate recurrent algorithms for estimation
of stationary characteristics of limited resource queuing systems.
80 ITTMM—2018
B
0,6
0,5
0,4
0,3 k=5; θ=2
k=1; θ=10
0,2
k=10; θ=1
0,1
0 ρ
20 30 40 50 60 70 80 90 100
Figure 3. Blocking probabilities in case of exponential service times
b
1
0,9
k=1; θ=10
0,8 k=5; θ=2
k=10; θ=1
0,7
ρ
0,6
20 30 40 50 60 70 80 90 100
Figure 4. Average volume of occupied resources in case of exponential service
times
Sopin Eduard S., Samouylov Konstantin E., Shorgin Sergey Ya. 81
Acknowledgments
The reported study was supported by the Russian Science Foundation, research
project No. 16-11-10227.
References
1. 3GPP TS 36.300: Evolved Universal Terrestrial Radio Access (E-UTRA) and
Evolved Universal Terrestrial Radio Access Network (E-UTRAN): overall description
(Release 15).
2. F. Boccardi, J. Andrews, H. Elshaer, M. Dohler, S. Parkvall, P. Popovski, S. Singh,
Why to Decouple the Uplink and Downlink in Cellular Networks and How To Do It.
IEEE Communications Magazine 54 (3) (2016) 110–117.
3. O. Galinina, S. Andreev, A. Turlikov, Y. Koucheryavy, Optimizing Energy Efficiency
of a Multi-Radio Mobile Device in Heterogeneous Beyond-4G Networks, Performance
Evaluation, 78 (2014) 18–41.
4. Q. Fang, P. Liu, J. Yen, J. Morgan, D. Shemanski, F. Ritter, Analyzing Intelligence
on WMD Attacks Using Threaded Event-Based Simulation, IFIP Advances in
Information and Communication Technology 367 (2011) 201–216.
5. G. Fodor, S. Parkvall, S. Sorrentino, P. Wallentin, Q. Lu, N. Brahmi, Device-to-
Device Communications for National Security and Public Safety, IEEE Access 2 (1)
(2014) 1510–1520.
6. A. I. A. Jabbar, Y. A. Fawaz, Long Term Evolution (LTE) Scheduling Algorithms in
Wireless Sensor Networks (WSN), International Journal of Computer Applications
121 (10) (2015) 12–16.
7. F. P. Kelly, Loss Networks. The Annals of Applied Probability 1 (3) (1991) 319–378.
8. V. Klinshov, V. Nekorkin, Event-based simulation of networks with pulse delayed
coupling, Chaos: An Interdisciplinary Journal of Nonlinear Science 27 (2017) 101105.
9. J. Lee, H. Wang, J. Andrews, D. Hong, Outage Probability of Cognitive Relay
Networks with Interference Constraints. IEEE Transactions on Wireless Communi-
cations 10 (2) (2011) 390–395.
10. V. A. Naumov, K. E. Samuilov, A. K. Samuilov, On the total amount of resources
occupied by serviced customers, Automation and Remote Control 77 (8) (2016)
1419–1427.
11. V. Naumov, K. Samouylov, Analysis of multi-resource loss system with state
dependent arrival and service rates, Probability in the Engineering and Informational
Sciences, 31 (4) (2017) 413–419.
12. C. A. Rabbath, M. Abdoune, J. Belanger, Effective real-time simulations of event-
based systems, Procedings of the 2000 Winter Simulation Conference, 2000, 232–238,
https://doi.org/10.1109/WSC.2000.899723.
13. E. L. Romm, V. V. Skitovitch, On certain generalization of problem of Erlang,
Automation and Remote Control 32 (5) (1971) 1000–1003.
14. K. E. Samouylov, Yu. V. Gaidamaka, E. S. Sopin, Simplified Analysis of Queue-
ing Systems with Random Requirements, Statistics and Simulation, Springer
Proceedings in Mathematics & Statistics 231 (2018) https://doi.org/10.1007/
978-3-319-76035-3_27.
15. B. A. Sevast’yanov, An ergodic theorem for markov processes and its application to
telephone systems with refusals. Probability Theory and Applications 2 (1) (2006)
104–112, https://doi.org/10.1137/1102005.
16. K. Samouylov, E. Sopin, O. Vikhrova, and S. Shorgin, Convolution algorithm for
normalization constant evaluation in queuing system with random requirements,
AIP Conference Proceedings 1863 (2017) 090004.
17. O. Tikhonenko, Generalized Erlang problem for service systems with finite total
capacity. Problems of Information Transmission 41 (3) (2005) 243–253.
82 ITTMM—2018
18. O. M. Tikhonenko, Destricted Capacity Queueing Systems: Determination of their
Characteristics, Automation and Remote Control 58 (6) (1997) 969–973.
19. O. Tikhonenko, Determination of Loss Characteristics in Queueing Systems with
Demands of Random Space Requirement, Dudin A., Nazarov A., Yakupov R. (eds)
Information Technologies and Mathematical Modelling – Queueing Theory and
Applications, Communications in Computer and Information Science, 564 (2015)
209–215.
20. O. M. Tikhonenko, K. G. Klimovich, Analysis of queuing systems for random-length
arrivals with limited cumulative volume. Problems of Information Transmission
37 (1) (2001) 77–79.