Probability

set-111.pdf

Home >Mathematics homework help >Probability homework help >Probability

Elements of Queuing Theory

Birth-Death Systems ■  A birth-death system (process) is a Markov chain in which states denote

the number of elements in the system and the transition probabilities satisfy the following:

pij = 0 if | i – j | > 1 , pi,i+1 > 0 and pi+1, i > 0 for all i ≥ 0 ■  Any arrival (birth) or departure (death) at any one time can only be of

magnitude one.

0 1

p01

p10 2

p12

p21 p23 p32

p00

p11 p22 …

M/M/1 Queuing System ■  Arrivals at any state are Poisson with parameter λ ■  Departures at any state are Poisson with parameter µ ■  Inter-arrival and inter-departure times are therefore exponentially

distributed. ■  If the system is nonempty, the time until the next departure is an

exponential random variable. ■  Let N(t) = k, i.e., the number of customers in the system at time t. ■  We are interested in TRANSITION RATES of the system, i.e., the

transition rates for N(t).

M/M/1 Queuing System ■  Let A(δ) be the number of arrivals in an interval of length δ. ■  Arrivals are Poisson, and so the probability of one arrival in δ is

■  Similarly, the probability of more than one arrival in δ is P[A(δ)>1]=1−(P[A(δ)=0]+P[A(δ)=1])=o(δ)

■  The probability of a customer completing her service in the next δ seconds is P[τ ≤δ]=1−e−µδ = µδ +o(δ)

■  Because arrivals and departures are independent, the probability of one arrival and one departure is P[A(δ)=1,τ ≤δ]= P[A(δ)=1]P[τ ≤δ]=o(δ)

■  Similarly, the probability of any change involving multiple departures and arrivals is o(δ)

P[A(δ)=1]= λδ 1! e−λδ =

λδ 1! 1+ −

λδ 1! + (λδ)2

2! −...+

(−1)n(λδ)n

n! +...

⎡

⎣ ⎢

⎤

⎦ ⎥

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟= λδ +o(δ)

o(δ) approaches 0 as δ approaches 0

M/M/1 Queuing System ■  As δ → 0 we have o(δ) → 0

Probability of an arrival: P[A(δ) =1] → λδ in any state Probability of a departure: P[D(δ) =1] →µδ in any state

■  Substituting these transition probabilities we obtain:

■  As with other Markov chains, we can express the state probabilities in terms of the transition probabilities

0 1 λδ

µδ 2 λδ

λδ

µδ µδ

1 – λδ 1 – (λδ+µδ)

…

1 – (λδ+µδ)

M/M/1 Queuing System ■  Equation at state 0: 0 µδ

1 – λδ

π0= (1 – λδ) π0 + µδ π1 or 0 = – λδ π0 + µδ π1 so λδ π0 = µδ π1 and hence λ π0 = µ π1

■  Equation at state 1: π1= λδ π0 + (1 – λδ – µδ) π1 +µδ π2 or

0= λδ π0 + ( λδ + µδ) π1 +µδ π2 or (λδ + µδ) π1 = λδ π0 + µδ π2 (λ + µ) π1 = λ π0 + µ π2 ■  Equation at state n:

πn= λδ πn – 1 + (1 – λδ – µδ) πn +µδ πn +1 or (λδ + µδ) πn = λδ πn – 1 + µδ πn +1 or (λ + µ) πn = λ πn – 1 + µ πn+1

The state equations are simply “balance equations,” each stated as a function of arrival and departure rates.

M/M/1 Queuing System ■  Consequence: N(t) increases by one at a rate λ and decreases by one at a rate µ ■  We can focus on TRANSITION RATES of the system, i.e., the transition

rates for N(t). ■  We can state a transition-rate diagram for the system showing how N(t)

changes with arrivals and departures. It is similar to the state-transition diagram.

■  The system is in equilibrium: “Rate of going into a state must equal rate of going out of it.”

0 1 λ µ

2 λ µ

M/M/1 Queuing System

■  Balance equation at state 0: λ π0= µ π1 ■  Balance equation at state 1: (µ + λ) π1 = λ π0 + µ π2 ■  Balance equation at state n: (µ + λ) πn = λ πn – 1 +µ πn +1 ■  We need to solve the above n + 1 equations to express πn in terms

of λ and µ. ■  The approach is by iteration and [strong] induction.

0 1 λ

µ 2

M/M/1 Queuing System Balance equation at state 0: λ π0= µ π1 Balance equation at state 1: (µ + λ) π1 = λ π0 + µ π2 Balance equation at state n: (µ + λ) πn = λ πn – 1 +µ πn +1

0 1 λ

µ 2

π1 = λ µ π0 π2 =

1 µ (µ +λ)π1 −λ π0[ ] =

1 µ (µ +λ)

λ µ π0 −λ π0

# $

& '

= 1 µ µ λ µ π0 +λ

λ µ π0 −

λµ µ π0

⎡

⎣ ⎢

⎤

⎦ ⎥=

λ µ

⎛

⎝ ⎜

⎞

⎠ ⎟

π0

We can make the guess: πn = λ µ

⎛

⎝ ⎜

⎞

⎠ ⎟

π0 (1) We need to show that Eq. (1) is true

M/M/1 Queuing System The basis case for n = 1 is true by construction. Assume the result is true for any i ≤ k and show for k + 1. From the balance equation at state k, we have:

Substituting our inductive hypothesis in Eq. (2):

Therefore, πk+1= (λ/µ)k +1 π0 and the result in Eq. (1) is true.

(µ +λ)πk = λπk−1 +µπk+1 and so k λ

µ k+1 k – 1

πk+1 = 1 µ

(µ +λ)πk −λπk−1[ ] (2)

πk+1 = 1 µ (µ +λ)

λk

µk π0 −λ

λk−1

µk−1 π0

# $

& '=

π0 µ

λk

µk−1 + λk+1

µk − λk

µk−1 "

# $

& '

We now have πn as a function of π0

M/M/1 Queuing System What is π0? We define ρ = λ/µ and call it the utilization of the system. For the system to be stable, λ < µ; otherwise, the queue size goes to infinity.

Accordingly, π0 = 1 – ρ It follows that This corresponds to the

geometric distribution with parameter ρ = λ/µ

We have shown that πn = ρ nπ

0 and we also know that π jj=0

∞

∑ =1 and 0 < ρ <1

Using these results, 1= πk k=0

∞

∑ = π0ρ k

k=0

∞

∑ = π0 ρ k

k=0

∞

∑ = π0 1

1−ρ ⎛

⎝ ⎜

⎞

⎠ ⎟

πn = ρ n 1−ρ( ) =

λ µ

# $

& '

1− λ µ

# $

& '

M/M/1 Queuing System Performance measures of interest: N = Number of customers in the system

NQ = Queue length [number of customers in queue] T = Delay in the system for a given customer W = Time a customer waits in the queue Consequence of M/M/1 assumptions: 1/λ =Average customer inter-arrival time 1/µ = Average customer service time

BREAK

M/M/1 Queuing System Performance measures of interest: N = Number of customers in the system

M/M/1 Queuing System Average number of customers in the system E(N):

The distribution ρi (1 – ρ) states the probability of success after i +1 trials (i.e., having i failures followed by a success), rather than the probability of success after i – 1 failures.

N = E(N) = i π i i=0

∞

∑ = 0 + i π i i=1

∞

∑ = i ρi (1− i=1

∞

∑ ρ) (1)

N = iρρi (1− i=1

∞

∑ ρ) = ρ iρi−1(1− i=1

∞

∑ ρ) =ρ 1

1−ρ ⎛

⎝ ⎜

⎞

⎠ ⎟ N =

ρ 1−ρ

However, ρi = ρ(ρi – 1) and so:

M/M/1 Queuing System Average number of customers in queue E(NQ): NQ = (i−1)π i

i=1

∞

∑ = i π i i=1

∞

∑ − π i i=1

∞

∑ (1)

For the second sum: π j j=0

∞

∑ =1 ; therefore, π j j=1

∞

∑ =1−π0 =1− (1−ρ) = ρ (3)

Therefore, NQ = ρ2

1−ρ

With j > 0 customers in the system, one is being serviced and j – 1 are in the queue

For the first sum: i π i i=0

∞

∑ = 0 + i π i i=1

∞

∑ =N (2)

Substituing (2) and (3) in (1): NQ = N −ρ = ρ

1−ρ −ρ =

ρ −ρ(1−ρ) 1−ρ

(4)

M/M/1 Queuing System Average delay in the system E(T): Consider a specific customer c in the system arriving at time t and leaving the system at time t + T. Because customers are services with a FIFO discipline, the number of customer left in the system at time t + T equals the number of customers that arrived in T seconds, which is λT.

time

customer c

t t + T

M/M/1 Queuing System Average delay in the system E(T): On average, the number of customers left behind by any customer c must equal the average number of customers in the system, i.e., E(N). We thus have, E(N) = λE(T)

T = N λ

Therefore,

Little’s result Substituting E(N) in this result we have :

T = ρ

λ(1−ρ) =

λ λµ(1−λ /µ)

;

T = 1

µ −λ

M/M/1 Queuing System Average waiting time E(W): The average time spent in the system is the waiting time plus the service time; therefore,

We then have: W =T − 1 µ =

1 µ(1−ρ)

− 1 µ =

ρ µ(1−ρ)

W = ρ

µ(1−ρ)

T =W +1/µ

Back to average number of customers in queue, from Little’s formula:

Therefore: NQ = λ ρ

µ(1−ρ) =

ρ2

1−ρ

NQ = λW

M/M/1 Queuing System Variance of number of customers in system:

E(N 2)= 2ρ2

(1−ρ)2 +

ρ (1−ρ)

Var(N) = E(N 2 ) −E2 (N) and we know E(N) = ρ / (1−ρ)

Var(N) = 2ρ2

(1−ρ)2 +

ρ (1−ρ)

− ρ

(1−ρ) ⎛

⎝ ⎜

⎞

⎠ ⎟

= ρ2

(1−ρ)2 +

ρ (1−ρ)

= ρ2 +ρ(1−ρ)

(1−ρ)2 =

ρ (1−ρ)2

We can show that:

Var(N)= ρ

(1−ρ)2

M/M/1 Queuing System with Finite Capacity (M/M/1/K)

■  Systems have a finite capacity for serving customers. ■  The M/M/1 queuing system capable of supporting up to K customers is

called an M/M/1/K queuing system. ■  Arrivals at any state are Poisson with parameter λ ■  Departures at any state are Poisson with parameter µ ■  Inter-arrival and inter-departure times are exponentially distributed.

0 1 λ

µ 2

µ K

µ K – 1 …

M/M/1/K Queuing System ■  Balance equation at state 0: λ π0= µ π1 ■  Balance equation at state n: (µ + λ) πn = λ πn – 1 +µ πn +1 ■  Balance equation at state K: λ πK – 1= µ πK ■  We need to solve the above K + 1 equations to express πn in terms of λ

and µ. We can show that, for ρ < 1, πn =

ρn 1−ρ( ) 1−ρK+1

n = 0, 1, 2, ..., K −1; ρ = λ µ

N = ρ

1−ρ −

(K +1)ρK+1

1−ρK+1

M/M/1/K Queuing System ■  In contrast to the M/M/1 system, a customer that arrives when there are

K customers in the system is turned away. ■  The arrival rate of customers λ consists of two components, depending

on whether the customers are turned away: λ = λ (1 – πK ) +λ πK = λa +λ b ■  Here λ (1 – πK ) states the actual arrival rate into the system. ■  From Little’s formula:

T = N

λ(1−πK )

General B-T Queuing System ■  Balance equation at state 0: λ0 π0= µ1 π1 ■  Balance equation at state 1: (µ1 + λ1) π1 = λ0 π0 + µ2 π2 ■  Balance equation at state n: (µn + λn) πn = λn – 1 πn – 1 + µn +1 πn +1 ■  We need to solve the above n + 1 equations to express πn in terms

of λ’s and µ’s.

0 1 λ0 µ1

2 λ1 µ2

λ2

µ3

k λk – 1 µk

λk

µk+1 … …

■  By iteration and [strong] induction:

π1 = λ0 µ1 π0

π2 = 1 µ2 (µ1 +λ1)π1 −λ0π0⎡⎣ ⎤⎦=

1 µ2 (µ1 +λ1)

λ0 µ1 π0 −λ0π0

⎡

⎣ ⎢

⎤

⎦ ⎥

π2 = 1 µ2

µ1 λ0 µ1 π0 +λ1

λ0 µ1 π0 −λ0π0

⎡

⎣ ⎢

⎤

⎦ ⎥=

λ0λ1 µ1µ2

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟π0

General B-T Queuing System

■  We can make the guess: πn = λ0λ1... λn−1 µ1µ2 ... µn

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟π0 (1)

General B-T Queuing System The basis case for n = 1 is true by construction. Assume the result in Eq. (1) is true for any i ≤ k and show that is also true for for k + 1. From the balance equation at state k, we have: (µk + λk) πk = λk – 1 πk – 1 + µk +1 πk +1 and hence

πk+1 = 1 µk+1

(µk +λk) λ0λ1... λk−1 µ1µ2 ... µk

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟π0 −λk−1

λ0λ1... λk−2 µ1µ2 ... µk−1

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟π0

⎡

⎣ ⎢ ⎢

⎤

⎦ ⎥ ⎥

πk+1 = 1 µk+1

(µk +λk )πk −λk−1πk−1⎡⎣ ⎤⎦ (2)

Substituting our inductive hypothesis in Eq. (2):

General B-T Queuing System Simplifying:

Therefore, the result in Eq. (1) is true.

πk+1 = π0 µk+1

λ0λ1... λk−1 µ1µ2 ... µk−1

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟+

λ0λ1... λk µ1µ2 ... µk

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟−

λ0λ1... λk−1 µ1µ2 ... µk−1

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟

⎡

⎣ ⎢ ⎢

⎤

⎦ ⎥ ⎥

πk+1 = π0 µk+1

λ0λ1... λk µ1µ2 ... µk

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟

⎡

⎣ ⎢ ⎢

⎤

⎦ ⎥ ⎥ =

λ0λ1... λk µ1µ2 ... µk+1

⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟π0

π 0 = π

0 and πk = π0

λi µi+1i=0

k−1

∏ for k =1, 2,...

General B-T Queuing System What is π0?

πk k=0

∞

∑ = π0 + πk k=1

∞

∑ = π0 + π0 λi µi+1i=0

k−1

∏ ⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟

k=1

∞

∑ =1 (3)

Accordingly,

π j j=0

∞

∑ =1 We know that:

Therefore,

1 = π0 1+ λi µi+1i=0

k−1

∏ ⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟

k=1

∞

∑ ⎛

⎝ ⎜ ⎜

⎞

⎠ ⎟ ⎟ and thus π0 =

1+ λi µi+1i=0

k−1

∏ ⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟

k=1

∞

∑

πk = λi µi+1i=0

k−1

∏ ⎡

⎣ ⎢

⎤

⎦ ⎥/ 1+

λi µi+1i=0

k−1

∏ ⎛

⎝ ⎜⎜

⎞

⎠ ⎟⎟

k=1

∞

∑ ⎡

⎣ ⎢ ⎢

⎤

⎦ ⎥ ⎥

M/M/1 Queuing System

πn = ρ n 1−ρ( )ρ = λ /µ

N = ρ

1−ρ

T = N λ =

ρ λ(1−ρ)

W = ρ

µ(1−ρ)

ρ = λ /µ πn = ρ n 1−ρ( )

Nm = ρ

1−ρ

Tm = N

λ / m =

mρ λ(1−ρ)

=mT

Wm = ρ

(µ /m)(1−ρ) =

mρ µ(1−ρ)

=mW

System with reduced rates is slower. Average delays are m times higher.

What happens when arrival and departure rates are reduced by the same factor m?

Packet Switching vs. Circuit Switching

πn = ρ n 1−ρ( )

ρps = ρ = λ /µ

Nps = ρ

1−ρ

Tps = N λ =

ρ λ(1−ρ)

Wps = ρ

µ(1−ρ)

Average delays are shorter with packet switching; resources are wasted in circuit switching

NQ = ρ

1−ρ ;

Tm = NQ λ / m

= mρ

λ(1−ρ) =mTps

Wm = ρ

(µ /m)(1−ρ) =

mρ µ(1−ρ)

=mWps

Ncs =mNQ = mρ

1−ρ

ρQ = ρ = λ /µ

END