M M 1 Queue B314 - Lecture notes sdkj PDF

Preview

Summary

sjksjs...

Description

M/M/1 Queue 

What M/M/1 implies ?   We first need to have a look at Kendall’s  notation => A / B / s where: A => Arrival distribution ( M for poisson, D for deterministic and G for general) B => Service time distribution ( M for exponential, D for deterministic and G for general) S => Number of servers (Here we have 1) 

Why use the Poisson process for arrivals ?  M/M/1 queueing systems assume a Poisson arrival process. This assumption is a very good approximation for arrival process in real systems that meet the following rules: 1. The number of customers in the system is very large. 2. Impact of a single customer on the performance of the system is very small, i.e. a single customer consumes a very small percentage of the system resources. 3. All customers are independent, i.e. their decision to use the system is independent of other users.

 

Exploring queuing theory    According to the theory, any queue can be modeled by these 6 parameters: A  | B | c | D | E | F.  ●

A is the arrival process

●

B is server process

●

c is number of servers

●

D is queue capacity

●

E is population size

●

F is queueing discipline

  We’ll focus on the simplest queue of type M|M|1|∞|∞|FIFO  or usually abbreviated as M|M|1. 

M/M/1 Model   Imagine a queue with infinite capacity (∞) i.e. there’s no limit on how long can the waiting line be. Assume that the population size is also infinite (∞) i.e. the number of potential customers is limitless. Clients are served on a First-In-First-Out (FIFO) basis.  Let‘s assume that we’re operating a line with only one server (1) e.g. think of a basic food truck with 1 queue line. We can then model the customer arrival rate with a Poisson  process of rate  λ (M). We also assume that our service time is exponentially  distributed, hence can be modelled with a Poisson process of rate μ (M) as well.

The M/M/1 model is characterized by the following assumptions:  ● Jobs arrive according to a Poisson process with parameter tλ, or equivalently, the time between arrivals, t, has an exponential distribution with parameter λ, i.e., for 0≥t, the probability density function is

f(t) = λ e − λt  

● The service time, s, has an exponential distribution with parameter μ, i.e., for 0≥s, the probability density function is 

g(s) = μ e − λs  

● There is a single server; ● The buffer is of infinite size; and ● The number of potential jobs is infinite.

We represent this process as a Markov Chain. The state (node) represents how many items are at the queue, while transition rate shows the probability of receiving/serving a customer. For example S2 means that there are 2 items in the queue in that state. Since there’s only 1 server, items can only be processed sequentially, 1-by-1. Arrival rate of λ means that on average, in 1 time unit, λ items will arrive to the queue. Service rate of μ means that on average, in 1 time unit, μ items will be served and hence removed from the queue.

Time-dependent behaviour  The exponential distribution allows for a very simple description of the state of the system at time t, namely the number of customers in the system (i.e. the customers waiting in the queue and the one being served).  Neither do we have to remember when the last customer arrived nor we have to register when the last customer entered service. Since the exponential distribution is memoryless, this information does not yield a better prediction of the future.  Let pn(t) denote the probability that at time t there are n customers in the system,n= 0,1,...Based on the memoryless property, we get, for ∆t→0,

 p0(t+ ∆t) = (1−λ∆t)p0(t) +μ∆tp1(t) +o(∆t) For understanding the above equation in better way we can reframe it as:



p0 (t+ ∆t) - p0(t)  = μp1(t) - λp0( t) + o(∆t) ∆t ∆t 

 Here o(∆t), is a negligible term for ∆t→0, which comes into the picture due to Taylor series expansion of the poisson process. It therefore satisfies that:







lim o(∆t) = 0

∆t→0

∆t



Therefore the LHS denotes rate of change of probability of 0 people in a queue in ∆t→0 time window, which equals (RHS):  rate of people being served for queue having 1 person

 

μp1( t)

___ 

rate of arrival of people in queue of size 0,

λ  p0(t)

Similarly we observe:

pn(t+ ∆t) = λ∆tpn−1(t) + (1−(λ+μ)∆t)pn(t)  +μ∆tpn+1(t) +o(∆t) n= 1,2,... 

Hence, by letting ∆t→0, we obtain the following infinite set of differential equations for the probabilities pn(t).  p′0(t) =−λp0(t) +μp1(t) [ intuitive explanation given above] p′n(t) =λpn−1(t)−(λ+μ)pn(t) +μpn+1(t), n= 1,2,...   It is difficult to solve these differential equations. So already one of the simplest interesting queueing models leads to a difficult expression for the time-dependent behavior of its state probabilities. For more general systems we can only expect more complexity. Therefore, in the remainder we will focus on the limiting or equilibrium behavior of this system, which appears to be much easier to analyse.  

Limiting behaviour  If we take the probability of n number of people in the queue as pn(t) (time dependent), and assume t approaches infinity, and if we take consider the following limΔ t⟶0pn(t + Δt) = p’n(t) p’0(t) = −λp0(t) + µp1(t) p’n(t) = λpn−1(t) − (λ + µ)pn(t) + µpn+1(t) it’s clear that the former exhibits a time independent characteristic in equilibrium while the latter becomes zero. Hence using these values, found at ‘limiting’ state of the queue, equations for equilibrium state are worked out. 

 We have, 0 = −λp0 + µp1 0 = λpn−1 − (λ + µ)pn + µpn+1

: here n takes values 1, 2, 3, …

 This limiting behavior can be visualised through a flow diagram. The flow out at equilibrium for a state n will be equal to the flow in, hence establishing the balance. 

 Clearly, only for ρ average number of customers λ => customers’ arrival rate (assuming an identical departure rate)

W => average amount of time customers spend at the business When calculating L, the number of people at a business, simply invert the equation:

W = L

Important note : -  

Little’s Formula is valid for the steady state of any queueing process.

 Derivation Diving into the mathematics behind it …

The expected number of jobs in the system  (either queue or process) is ∞

∞

L = ∑ nPn = ∑ n  ρ n(1- ρ ) n=0

n=0

Simplifying, L can also be written as:

  After finding the expected number of jobs in the system, now finding expected number of jobs in the queue  for a single server :



Using the above results we can have the waiting time for the queue and system. We know, L = λW

… from Little’s law

 ⇒ In a steady state, the average time spent waiting in the queue will be :





Applying Little’s formula, i.e. , putting the value of Lq :

 Similarly for the average waiting time spent in the system  we have:

 Applying Little’s formula, putting the value of L :



  Mean values for queue size and waiting time  For all practical purposes we are interested in finding the mean number of customers in the system and mean time spent in the system Based on PASTA we know that the average number of customers in the system seen by an arriving customer equals E(L) and each of them (also the one in service) has a (residual) service time with mean 1/μ. The customer further has to wait for its own service time. The average number of customers in the system as we saw in the derivation part of Little’s formula is given by

 n n That is given by , using the results (pn =  ρ p0 ) and (pn = (1 − ρ)ρ )

And by using Little's law we find the average time spent in the system is equal to   In these equations ρ is λ/µ. 

  This simple relation is known as the a  rrivals relation.

Busy Period  

● Empty system

=> When there is no request processing in server

● Busy period(BP) ● Idle period(IP)

=> When server is helping customers => When the server is not helping ,i.e. System is empty

● Cycle

=> Time that elapses between two consecutive arrivals  finding an empty system. It is made by a BP and IP



Since exponential systems are memoryless , the idle period has expectation :

E(IP) = 1/λ : i.e. mean of exponential distribution



(Where λ is poisson parameter or the rate of arrival of customers) 

Mean Busy Period : E(BP) 

Fraction of time the server is busy = m ean busy period ÷ mean cycle length  ⇒ ρ = E(BP) / ( E(BP) + E(IP) ) ⇒ ρ = E(BP) / ( E(BP) + 1/λ ) ⇒ E(BP) = (ρ/λ) / (1- ρ) = (1/𝝁) / (1- ρ) 

ARRIVAL AND DEPARTURE DISTRIBUTIONS  a

L  : Number of of customers in the system just before the arrival of a customer Ld : Number of customers in the system just after a departure

 Dn(t) : Number of departures in (0, t) leaving behind n customers An(t) : Number of arrivals in (0, t) finding n customers in the system Dn(t) = An(t) ± 1 (Since customers arrive and leave one by one)

 P(L d = n) = lim t

Dn(t)/t = lim t

∞

∞

An(t)/t =

P(L a = n)

(the arrival and departure distribution are exactly the same)

Sources   https://www.win.tue.nl/~iadan/que/h4.pdf https://www.comp.nus.edu.sg/~cs3260/MM1.pdf http://pages.cs.wisc.edu/~dsmyers/cs547/lecture_11_pasta.pdf https://towardsdatascience.com/servitization-and-queueing-the ory-deriving-m-m-1-model-589175b23054   

Team members   Ridhima Kohli (B19CSE071) Saptashrungi Birajdar (B19CSE076) Sarthak Raj Jindal (B19CSE078) Shivam Kumar (B19CSE118)...