On the Simulations of the Limited Resources Queueing Systems

Abstract

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.

Keywords

• 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

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.

A1(x), B1(x) AL (x), BL (x) customer l  type k

N k

R1 xk,1 

 RM xk,M Fk (x) CDF of amount of resources required for a customer Let (1) and (1) be the average of interarrival and serving times respectively. Then the ofered load is = ∑︁ (1)

(1) .

=0

The stochastic process () = ( (), (), (), (), ()) describes the system behaviour 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) (2) 1,..., (x1, . . . , xk) = 0 (x1) · · · (x) ∏︁ , =1 ∑︀ =1 where ⎛

0 = ⎝1 + ∑︁

∑︁ =1 1+...+= ⎞− 1 11 * . . . * (R) 11 . . . .

. 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

Release server and resources

Find the closest event departure

Customer blocked No Yes End

Initialization End of simulation No

Arrival or departure arrival

Enough resources? Yes

Occupy a server and a volume of resources

systems [ 4, 8, 12 ]. Figure 2 shows block-diagram of the simulation algorithm. Let us describe it briefly. 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. 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 components 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: () = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ ︁( − 1 ︁)

, 0, 1,

6 0, 0 < 6 , > , (3) 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 ofered 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 eficient approximate recurrent algorithms for estimation of stationary characteristics of limited resource queuing systems. 0,6 B 0,5 0,4 0,3 0,2 0,1 0 20 0,8 0,7

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 Eficiency 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-toDevice 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 Communications 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 , Efective real-time simulations of eventbased 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 Queueing 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 .

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 .