Distribution of Occupied Resources on A Discrete Resources Sharing in A Queueing System

Distribution of Occupied Resources on A Discrete Resources Sharing in A Queueing System

Toky Basilide Ravaliminoarimalalason

Ecole Doctorale en Sciences et Techniques de lIngénierie et de lInnovation,

University of Antananarivo, Antananarivo, Madagascar

Falimanana Randimbindrainibe

Ecole Doctorale en Sciences et Techniques de lIngénierie et de lInnovation,

University of Antananarivo Antananarivo, Madagascar

AbstractIn this paper, we study discrete resources sharing in a queueing system. We build analytical model of the distribution of occupied resources that can help for resources dimensioning. Both infinite and finite amount of discrete server resources are highlighted and validated with special cases of individual resource requirement following Poisson and Binomial distribution. It is found that there is a peak of usage near the average number of resources requested by customers, and other small peaks with low probability at multiples of this mean. The charging factor of the queue impacts mostly on the resources occupation distribution.

KeywordsDistribution; probability; queue; resource; sharing

1. INTRODUCTION

   An event flow called customers sequentially arrives in a system to claim a service [1]. The time between the arrival of these customers, called inter-arrival, and the length of service requested by customers are random variables. This queueing system is made up of a queueing area, of finite or infinite capacity, and servers handling the services requested by customers. With that comes a discipline dictating how or who in the queueing area customers are going to be served first.

   Basic theories of queueing systems have focused on numbers (finite or not) of servers. Each customer will be served by a server, until all servers are busy. Once busy, customers in the queueing system will wait until one server is free.

   However, in many real systems, some customers need more than one server, or more than one resource in a server. Some servers can take care of multiple customers at the same time, allocating some of their resources to customers, and some to other ones, depending on their needs. Researches have advanced on resource-based systems since Green's work on queues in which customers request multiple servers [2]. Others even wanted to generalize the notion of Erlang such as Romm

   1. or Tikhonenko [4]. Studies and analyzes of queueing systems capacity have been advanced [6][7][8], on queues with multiple servers or multiple resources [9][10] but we will be interested in analytical models of a queueing system that can share its discrete resources with users requesting service from it. More precisely, we will explore the probability distributions followed by the occupied resources in such queues in order to be able to perform a resource dimensioning.

2. FROM BIRTH AND DEATH PROCESS

   Given a queueing system a priori having customers. It can handle between 0 and customers. In this system, customers arrivals form a Poisson process of intensity , the service

   duration they request are random and are following an exponential distribution with average 1/.

   We denote by the state of this system, describes the

   number of customers present on it. Let (0, 1, . . . , 1) and

   (1, 2, . . . , ) be positive numbers.

   Proposition 1

   During an infinitely small time interval , knowing that there are customers in the queue :

   • The probability that a customer arrives in the queue is

     + (),

   • The probability that a customer leaves the queue is

     + (),

   • All other eventualities have a probability ().

   Proof:

   The probability that a customer will arrive during an infinitely small time interval , which we denote by , is equal to the probability that the inter-arrival of the customers is less than . The arrival of customers form a Poisson process of intensity , so the inter-arrival is random variable following an exponential distribution with parameter = (

   ) = 1 . For infinitely small, we can write the

   expansion limited to order 1 of this probability in the neighborhood of by = 1 (1 ) + () = +

   ().

   In a similar way, with a random variable of service duration following an exponential distribution with average 1/, we have the probability of customer departure =

   1 = + ().

   Proposition 2

   The stationary distribution = (0, , ) of this system is equal to :

   01 1 = 0 , = 1,2, , 1 2

   (1)

   Where

   1 0 01 01 1 = 1 + + + + 0 1 12 12

   (2)

   Proof:

   As a discrete-time Markov chain, with time step , we can show the following transition probability :

   – 00 = 1 0 + ()

   – ,1 = + () for = 1, ,

   – = 1 ( + ) + () for = 1, , 1

   – = 1 + ()

   – ,+1 = + () for = 0, , 1 = 1 where = – ! From these transition probabilities, the transition matrix is called charging factor.

   (5)

   corresponding to this Markov chain in discrete time is given by following equation:

   Proof:

   In this case, , = for all = 0, 1, 2, and =

   () 1 0 0 0 1 1 (1 + 1) 1 = 0 2 1 (2 + 2) 0 0 0 ( 0 0 0 ) +()

   (3)

   () 1 0 0 0 1 1 (1 + 1) 1 = 0 2 1 (2 + 2) 0 0 0 ( 0 0 0 ) +()

   (3)

   for all = 1,2,

   01 1

   = =

   = =

   12 .2

   01 1

   01 1

   1+0 +01 ++ + 1++ ++ +

   1

   12

   12

   .2

   .2

   =

   =

   .!

   1++ 2 ++ +

   ( )

   = =

   = =

   1

   !

   ()

   2.2!

   .!

   !

   This matrix can be written in the form () = + +

   () where is the infinitesimal stochastic generator of the continuous-time Markov chain obtained as approaches 0.

   Since the server has infinite capacity, then all customers in the system are served simultaneously. Customers arriving to the queueing area are immediately served after entering the system. If the system has customers served, they are using at the same time amount of resources. Let denote ( = ) the probability distribution of , the random variable describing the

   0 0 0 1 (1 + 1) 1 = 0 2 (2 + 2) 0 0 0 ( 0 0 0 )

   (4)

   0 0 0 1 (1 + 1) 1 = 0 2 (2 + 2) 0 0 0 ( 0 0 0 )

   (4)

   total amount of occupied resources, and () the probability

   The stationary distribution of the state of the system is obtained from the equaton of state relation of a continuous- time Markov chain . = 0. So,

   that the

   customers use

   ressources.

   ( = ) = + (( = ). ()) =1 = + ( 1 . ()) =1 !

   (6)

   ( = ) = + (( = ). ()) =1 = + ( 1 . ()) =1 !

   (6)

   – 00 = 11,

   – 00 (1 + 1)1 + 22 = 0, 11 = 22

   –

   – 22 (1 + 1)1 + = 0, 11 =

   , for = 2, , 1

   –

   – 11 =

   2) Individual resource usage following Poisson distribution

   We consider that resource usage by individual customer follows Poisson distribution with parameter : ().

   Proposition 4

   Resource usage by customers is a random variable also following the Poisson distribution with parameter :

   From these equations, we can get = 0 , =

   1 1 0 2 ().

   1

   = 0 1 ,

   = 2

   = 0 1 2 , , and then =

   Proof:

   2 1

   1 2 0 3

   3 2

   1 2 3 0

   The sum of independent Poisson random variable () and

   01 1

   for = 1,2, , . And knowing that ( , , )

   () is a random variable following Poisson distribution with

   12 0

   0

   parameter :

   .In other hand, the total amount of

   is a probability distribution, 0 + 1 + + = 1, so 0 is given by 1 = 1 + 0 + 01 + + 01 1.

   + ( + )

   occupied resources is additive (sum of resources amount of

   0

   1

   12

   12

   used by each customers).

   Proposition 5

   We note that = ( = ), the probability to find

   customers in the queueing system.

3. STATE DISTRIBUTION IN RESOURCE SHARING Now, we consider that the queueing system has discrete

   The number of occupied resources in the server has the following probability distribution:

   ( = ) = + () ! =1 ! of: m (6), and knowing that () = 1 ()

   (7)

   ( = ) = + () ! =1 ! of: m (6), and knowing that () = 1 ()

   (7)

   Pro

   resources in its servers. In total, resources are available on it,

   Fro

   !

   , we get

   {+}. It means that the quantity of system resources

   ( = ) = + 1 1 () =

   can be finite or infinite in our study, relative to the case.

   =1 !

   !

   Each customer needs an amount of resources, a discrete

   + ()

   random variable. If the amount of resources requested by the

   !

   =1 !

   customer is available, the server can allocate them while serving it. If they are not available, then the requesting customer remains in the queueing area until the requested resources are released for use.

   1. Infinite capacity queueing system with infinite server resources

      The system queueing is M/M/.

      1. General case Proposition 3

         The stationary distribution of this queueing system is:

   2. Infinite capacity queueing system with finite server resources

      1. General case

         We still have infinite capacity of queueing system, . But the server has finite resources, so the number of customers that can be served simultaneously is limited. Let be the maximum number of customers served by the server. We note that is variable according the amount of resources required by the customers. The stationary distribution of the queueing

         system having capacity in terms of number of customers is denoted by ,.

         Proposition 8

         1 ! 1++ 1 + =0! =1! , = 1 ! > { 1++ 1 + =0! =1!

         (8)

         1 ! 1++ 1 + =0! =1! , = 1 ! > { 1++ 1 + =0! =1!

         (8)

         The stationary distribution , is given by :

         Proof:

         If the capacity in terms of customer is = 1, then the usage of resources amount is limited to this only one customer. We have the probability : 1,. (1 = ) + 2,. (1 = ) +

         =2

         =2

         3,. (1 = ) + = 1,. (1 = ) + + ,. (1 =

         ).

         If the capacity in terms of customer is = 2, then the

         Proof:

         We get this stationary distribution from the following parameters : = (0 ), = (0 < < ) and =

         ( ), because the number of customers that can exit the system is limited by .

         usage of resources amount is limited to these 2 customers. We have the probability : 1,. (1 = ) + 2,. (2 = ) +

         3,. (2 = ) + = 2=1 ,. ( = ) +

         =3

         =3

         + ,. (2 = ).

         For any , the utilization of resources amount is limited to customers : 1,. (1 = ) + 2,. (2 = ) + +

         ,. ( = ) + +1,. ( = ) + +2,. ( = ) +

         So, for :

         .

         =

         =

         =1

         ,

         . (

         +

         = ) +

         = ) +

         =+1

         ,

         . (

         = ).

         ,

         = 2

         1++. ++. +.

         Thus, the probability of usage of amount of resources is

         obtained for all possible values of : ( = ) =

         2

         =

         2

         1

         !( )

         2

         =

         1

         ( )

         !

         =1

         (

         (

         =1

         ,

         . (

         +

         = ) +

         = ) +

         =+1

         ,

         . (

         = )) .

         1

         + 1

         +

         1

         + 1

         +

         1+ ++ ( ) +

         =1

         ( )

         =0 ( ) +

         =1

         ( )

         !

         !

         !

         !

         Blocking without loss applies in the following cases:

         – If the remaining amount of server resources is less than

         And for > :

         .

         = 2

         the next customer requirement, it cannot enter the server area and must wait there until the resources become available,

         ,

         1++. ++. +.

         )

         )

         2

         1

         2

         2

         1

         – If the total number of server resources (finite) is less

         )

         )

         = !(

         = !(

         than the customers requirement, the system will hang

         1

         + 1

         +

         1

         + 1

         +

         forever.

         1+ ++ ( ) + =1

         ( )

         =0 ( ) + =1

         ( )

         !

         !

         !

         !

         We denote ( ), the number of resources that the

         server can allocate. The capcity customers varies from 1 (if the customer require all resources at the same time) to (each customers consume a single resource). Let be the probability that this capacity in terms of customers is during an observation of the system.

         Proposition 6

         = 1 ( = ) . (1 > ) =

         (9)

         = 1 ( = ) . (1 > ) =

         (9)

         The probability distribution is given by :

         Proof:

         The capacity of the system is achieved in case of resources are used by hese customers , and the + 1-th following customer requests an amount of > resources. ( = ) = () denotes the probability that customers are using resources of the server.

         Proposition 7

         ( = 0) = (=).(1>) =1 1++ 1 + =0! =1!

         (10)

         ( = 0) = (=).(1>) =1 1++ 1 + =0! =1!

         (10)

         The probability that any resource is used is:

         Proof:

         This event is obtained when no customer is found in the queueing system, that is, with a probability 0,, for all possible values of .

         Proposition 9

         = 0 1 . , . ( = ). (1 )

         (12)

         = 0 1 . , . ( = ). (1 )

         (12)

         The blocking probability is given by:

         = =

         Proof:

         The system is blocked for any capacity in terms of customers whose server already occupies customers consuming amount of resources, and another customer requests an amount of resources greater than .

      2. Individual resource usage following Binomial distribution

         Lets take the example of binomial case to not fall in an eternal blockage of the system (we can limit the maximal number or required resources). A customer can request now a random quantity of resources amount at most according to his needs, and following a binomial distribution with mean .

         Proposition 10

         The number of required resources by one customer follows a binomial distribution with parameters = and = /

         : (, ).

         Proof:

         The maximal number of resources that a customer can request is , so the parameter of the binomial distribution is

         (=).(1>)

         ( = 0) = =1 0, . =

         =1

         1

         ++ 1

         .

         +

         = . His mean is = , so = /. It is a binomial

         Proposition 8

         =0!

         =1!

         distribution (, ) = ( = , = /).

         Proposition 11

         ( = ) = 1( =1 ,. ( = ) + = + +1 ,. ( = )) . for 0 < =

         (11)

         ( = ) = 1( =1 ,. ( = ) + = + +1 ,. ( = )) . for 0 < =

         (11)

         The probability distribution of the number of occupied resources is equal to:

         The amount of resources requested by customers follows also a binomial distribution with parameters and /.

         Proof:

         Due to the additivity of the amount of resources, and that the sum of independents binomial distributions (, ) is still a binomial distribution (, ).

         Using (9), (10), (11) and (12), we have:

         The probability of usage of resources by customers:

         ( = ) = () where = 1

         (13)

         The probability that the system has a capacity of customers :

         = 1 ( = ) . (1 > ) = = (() . ()) =1 =+1

         (14)

         The probability that amount of resources are occupied in the system :

         ( = ) = =1( =1 ,. ( = ) + + +1 ,. ( = )) . = = ( 1 ( 1 . () + =1 1++ 1 + =1 ! =0! =1! + 1 . () )) . =+1 !

         (15)

4. RESULTS AND DISCUSSIONS

   1. Validation of the analytical model

      To validate our theoretical results, simulations were carried out under Matlab-Simulink model of resource sharing.

      The first step was to share discrete resources from a queue to server of infinite resources. Customers arrive with an arrival rate = 1/1.2 s-1, request service with a random duration following exponential distribution of average 1 = 0.8 s, and require a random number of resources amount following a Poisson distribution with average = 5 resources.

      Fig. 1. shows comparison of the simulation result (histogram in blue) and the analytical expression of (7) (red curve). The histogram in blue indicates the normalized representation of observed number of resources occupied by customers. The observation is at each 0.1s for a duration of 5,000s. We note that the result of simulation follows the analytical expression of the probability distribution. Other simulations have been carried out for different values of , and and we found the same facts. This validates our expression in (7).

      Fig. 1. Occupied resources in an infinite resources sharing

      For the sharing of finite resources, Fig. 2. represents the result of simulation for customers arriving with an arrival rate

      = 1/1.2 s-1, requesting service with a random duration following exponential distribution of average 1 = 0.8 s. The resources requested by these customers are random following binomial distribution of maximum value = 6 resources, and of mean = 3 resources. The capacity of the server is = 10 resources.

      Fig 2. shows the comparison of the results of the simulation and the analytical expression in (15).

      Fig. 2. Occupied resources in a finite resources sharing

      We reach the same conclusion from the validation of our analytical model of finite resource sharing after multiple simulations with different values of , , and .

   2. Abacus of occupied resources

   From the analytical expressions that we have just validated, we can draw up the following charts based on the queueing system parameters values, whether finite resources or not.

   Fig. 3. Distribution of occupied resources for fixed in an infinite

   resources sharing

   Fig. 4. Distribution of occupied resources for fixed in an infinite

   resources sharing

   There is a peak near the average number of resources requested by customers, and then the curves spread to the left and to the right. It indicates that the number of busy resources is concentrated around the average requested by the customers. Other small peaks with low probability at multiples of this mean are also observed, explaining the fact that several customers are saved at the same time by the server.

   The probability of finding the server empty (in terms of the number of customers) decreases as increases. The increase of

   assumes that many customers are standing in the queueing area, either due to high service duration compared to inter- arrival, or to arrivals that are too frequent compared to service times. For infinite resources, can exceed 1, and the number of occupied resources also tends towards a high quantity amount as shown by the cyan curve ( = 2) in Fig. 4.

   Fig. 5. Distribution of occupied resources for fixed in a finite

   resources sharing

   Fig. 6. Distribution of occupied resources for fixed in a finite

   resources sharing

   The higher the capacity, the more the system tends towards the previous infinite resource scenarios as we can see in Fig. 5. The probability of finding the system free (0 customer, 0 utilization) decreases as the number of resources is reduced (Fig. 5) or as the charging factor increases (Fig. 6.). The notion of resource dimensioning begins to intervene from this step. We do not want to deploy resources that are not going to be used, or that will be under-used.

5. CONCLUSION

This paper focuses upon the study of occupied resources in queueing system whereby the customers arrival is Poisson process, they request service of duration exponential, and it requires a random amount of server resources. The server system has discrete resources and can share them to customers that request services to him. We proposed analytical model of the amount of the occupied resources by their probability distribution. We examined two cases of resources sharing: one with infinite amount of resources, and one with finite amount.

Special cases are also discussed regarding the individual resource usage following Poisson distribution and Binomial distribution. We validated our model using simulations on Matlab-Simulink.

The abacus presented in this paper can be used for resources dimensioning in case of Poisson or Binomial individual usage of discrete resource, but we can build more another abacus based on the formula that we validated.

In these proposed models, the server resources are discrete. In the future, we plan to build an analytical model of continuous resources sharing that we can also find in major cases of communication systems.

REFERENCES

1. E. Daru, Méthodes de résolution pour quelques problèmes de files dattente comportant des serveurs defficacités différentes, in Revue de la Recherche Opérationnelle, vol. 2, n°8, 3è trimestre 1958.

2. L. Green, A queueing system in which customers require a random number of servers, in Operations Research, vol. 28, n°6, pp. 1335- 1346, Nov-Dec 1980.

3. E. L. Romm, V.V. Skitovitch, On certain generalization of problem of Erlang, in Automation and Remote Control, vol. 32, n°5, pp. 1000- 1003, 1971.

4. O.M. Tikhonenko, Generalized Erlang problem for service systems with finite total capacity, in Problems of Information Transmission, vol. 41, n°3, pp. 243-253, 2005.

5. O.M. Tikhonenko, Destricted Capacity Queueing Systems: Determination of their Characteristics, in Automation and Remote Control, vol. 58, n°6, pp. 969-973, 1997.

6. O.M. Tikhonenko, K.G. Klimovich, Analysis of queuing systems for random-length arrivals with limited cumulative volume, in Problems of Information Transmission, vol. 37, n°1, pp. 77-79, 2001.

7. O.M. Tikhonenko, Determination of Loss Characteristics in Queueing Systems with Demands of Random Space Requirement, A. Dudin, A. Nazarov, R. Yakupov. (eds) Information Technologies and Mathematical Modelling Queueing Theory and Applications, in Communications in Computer and Information Science, vol. 564, pp. 209-215, 2015.

8. V. Naumov, K. Samouylov, Analysis of multi-resource loss system with state dependent arrival and service rates, in Probability in the Engineering and Informational Sciences, vol. 31, n°4, pp. 413-419, 2017.

9. G.Y. Fletcher, H.G. Perros, W.J. Stewart, A queueing system where customers require a random number of servers simultaneously, in Computer Science Department, Center for Communications and Signal Processing North Carolina State University, Raleigh, NC 27695-8206, U.S.A., 2011.

10. V.A. Naumov, K.E. Samuilov, A.K. Samuilov, On the total amount of resources occupied by serviced customers, in Automation and Remote Control, vol. 77, n°8, pp. 1419-1427, 2016.