Transcript Elementary Stochastic Analysis-5

Chapter 5
Elementary Stochastic Analysis
Prof. Ali Movaghar
Birth and Death Processes




qk,k+1 = λ(k) : Arrival (birth) rate in state k
qk,k-1= μ(k) : Departure (death) rate in state k
qi,j = 0 : for |i-j|>1
-qkk= [λ(k) + μ(k)]
λ(1)
λ(0)
0
1
μ(1)
λ(n-1)
…
n-1
μ(2)
…
λ(n)
n
μ(n)
n+1
μ(n+1)
2
Birth and Death Processes (Con.)

The rate arrival depends on the current
system rate



Therefore interarrival times must be exponentially
distributed.
Similarly, service-time distribution must also be
exponential.
The probability of more than one arrival or service
completion in Δt is negligiable.
3
Birth and Death Processes (Con.)

The system is classical M/M :

Prob(one arrival in Δt | system is in state k )=λ(k)Δt

Prob(one service in Δt | system is in state k)=μ(k)Δt

Prob(no arrival/services in Δt| system is in state
k)= 1- λ(k)Δt - μ(k)Δt
4
Birth and Death Processes (Con.)


P(n,t) : Probability of finding n customers in
the system at time t.
There are three ways for the system to be in
state n at time t :



System is in state n-1 at time t and one arrival
occurs at Δt
system is in state n+1 at time t and a service
completion occurs during Δt
System is in state n at time t and no arrival/service
completion occurs during Δt
5
Birth and Death Processes (Con.)


P(n, t+Δt) = P(n-1,t)λ(n-1)Δt+
P(n+1,t)μ(n+1)Δt+
P(n,t)[1-λ(n)Δt - μ(n)Δt ]
Taking limit Δt0, we get
dP(n, t)
  (n  1)P(n  1, t)  (n  1)P(n  1, t)  [(n)  (n)]P(n, t)
dt
dP(0, t)
 (1)P(1, t)  (0)P(0, t)
dt

The above differential difference equations describe
the transient behavior of M/M system
6
Birth and Death Processes (Con.)

To examine the steady-state solution, the
system should be ergodic :
k n  k[(n) / (n  1)  1]

The work should be handled faster than it arrives
7
Birth and Death Processes (Con.)

For steady state, we dP(n, t)  0 and P(n,t) is
dt
shown by P(n)


P(n-1)λ(n-1)+ P(n+1)μ(n+1)=P(n)[1-λ(n)- μ(n)]
Under steady state, the effective rate with which
the system enters state n should be equal to the
effective rate with which it exits state n
8
Birth and Death Processes (Con.)

We can derive equation in a more genera
form:


For any closed boundary, the effective flow inward
must equal the effective flow outward. (Global
balance equation)
If the boundary contains states 0 through n-1, we
get :
P(n-1)λ(n-1)= P(n)μ(n)
so
P(n) 
(0)(1)...(n  1)
P(0)
(1)(2)...(n)
9
Steady-State Analysis of M/M
Systems


We will derive detailed results for several
important M/M systems
Knedall’s notation : M/G/c/FCFS/K/N






M : Poisson arrival
G : general service-time distribution
c : identical servers
FCFS : scheduling discipline
Storage capacity : K
N : population
10
Simple M/M/1/SI// Queue

Here both λ(n) and μ(n) are independent of
state n



Let =λ/μ, for ergodicity <1
n P(0) ,
P(n)=


n

 P(0)  1 results P(0)=(1-)
n 0


From two above : P(n)= (1-) n
In a simple M/M/1 system, the queue length distribution is
geometric with parameter .
11
Simple M/M/1/SI// Queue (Con.)

Various performance parameters can now be
obtained :





Utilization (U) = 1- P(0) =
Avg. queue length (Q) = E(X) =  nP(n) = /(-1)
Avg. response time (R)=little low E(X)/λ=1/μ(1-)
Avg. number waiting (L) =  (n-1) P(n)= 2/(1-)
Avg. waiting time (W) =little low L/λ = 2/λ(1-)
12
M/M/c/SI// Queue

This is the multiple-server extension of M/M/1
system.



λ(n) = λ
n0
μ(n) = 
 c0
for n  c
for n  c
where μ0 is the basic service rate
=λ/cμ0 so we get
  n P(0) (c) n

P(0) for n  c

n
n!
 0 n!
P(n)   n
n

P(0)
(c

)


P(0) for n  c
 0 n c!cn c c!cn c
13
M/M/c/SI// Queue (Con.)


Using  P(n)  1 , we can compute P(0)
n 0
n
c
(c

)
(c

)
P(0)1  

n!
c!(1  )
n 0
c 1
14
Simple M/G//SI// Queue

The arrival rate is state independent



λ(n) = λ
μ(n)=n μ0
n
n P(0)
P(n)  n P(0) 
0 n!
n!
=λ/μ0. P(0) can be computed by the requirement that
all probabilities sum to 1.
n 
P(n)  e sin ce
n!

n


/
n!

e

n 0
15
Simple M/G//SI// Queue (Con.)

Thus the distribution is Poisson with mean .



The Avg. queue length Q=
Utilization U=
By little ‘s law Avg. Response time R=1/μ0
16
Simple M/M/c/SI/K/ Queue

This is the finite storage case where system
hold at most K customers:




 0
(n)  
0
for n  K
for n  K
μ(n)=min(n,c,K)μ0
P(n) can be easily abstained as before.
Note that this system has only min(c,K)+1 states.
17
Finite Population Systems
Let N denote the total number of customers
in the “universe”.
the arrival rate λ depends on n and the
underlying physical situation.


Each customer has its own independent arrival
rate λ0.
a)

b)
Thus the overall arrival is proportional to the number of
customers left in universe: λ(n)=N-n) λ0
The customers are released sequentially. Thus
arrival rate is constant
18
Finite Population Systems (Con.)

As an example, consider M/M/1/SI/K/N
station with arrival model (a).



μ(n)=μ0
(N  n) 0
(n)  
0

for n  min(N, K)
for n  min(N, K)
The state probabilities and performance
parameters could be obtained as before.
Note that system suffers from blocking if K<N
19
Finite Population Systems (Con.)

An isolated station with finite population can
be view as a closed network of two stations :
μ1(n)
1
μ1(n)
λ1(n)= μ2(N-n)
1
2
μ2(n)
20
Example

A telephone exchange is to be set up for a small
community of 50 customers, each of whom
independently attempts to call at the average rate of
one per hour and talks for 12 minutes on the
average. The call attempts (including reattempts by
customers who get a busy tone) can be adequately
described by Poisson process. System has a
capacity of K voice channel. Find the minimum value
of K such that the probability of service denial is 2%
or less.
21
Example (Con.)

Solution : The system can be modeled as a
M/G/K/SI/K/N, with N=50




(N  n) 0
(n)  
0

for n  min(N, K)
for n  min(N, K)
,λ0=1/12
μ(n)=μ0, μ0= 1/60
=λ0/μ0=0.2
So we get
 50 
P(n)     P(0)
n
n
22
Example (Con.)

The probability reject call P(K) is given by

 50  
n  50 
P(K)         
 K   n 0  n  
K
1
K

Setting P(K)0.02 and solving the equation we get
K=14.
23
Response-Time Distribution


We briefly discuss how to determine
response-time distribution for M/M systems
The general approach is to pick a tagged
customer and account for all the delays it
encounters.
24
Response-Time Distribution (Con.)

Suppose M/M/1 system



Let R denote the response time for a tagged
customer
Let X denote the number of customers that it finds
on its arrival
So the distribution function R is:

FR (t )  Pr( R  t | X  n) 
 Pr(R  t | X  n) Pr( X  n)
n 0
25
Response-Time Distribution (Con.)

Let R(n) denote response time of the tagged
customer given that if finds n customers
ahead of iteself.

R(n)= R1 + S2 +…+ Sn + Sn+1




R1 is the remaining service time of the customer
currently receiving service
Each Si has exponential distribution with mean 1/μ
Distribution of R1 is the same as Si (memoryless
property of exponential distribution)
R(n) is sum of n+1 independent, identically distributed
random variables
26
Response-Time Distribution (Con.)

Let f denote the density function of R:
f R (t ) 

  (  t )n  t 
f R (t ) (t ) Pr( X  n) 
e  (1   )  n 


 n!
n 0 
  (1   )e




 t

(  t ) n
  (1   )e  (1  )t
n!
n 0

The response-time distribution is also exponetial
The mean average response time is 1/μ(1-)
27
Batch Systems and Method of Stages

We examine M/M systems with batch arrivals
and services



Customers may arrive or get served as a group
with a number of K, where K can be a random
variable : Mk/M or M(x)/M.
Server may have K stages, each has an
exponential service time distribution with rate kμ.
So the overall service time distribution is Erlang
with the rate equal to μ : M/Mk
The behavior of Mk/M/1 is similar to M/Mk/1
28
Analysis of Batch Systems
λc2
λc2
λc1
n-2
n-1
μ

λc1
λc1
n
μ
λc1
n+2
n+1
μ
μ
The batch size is a random variable denoted
C.



Let Prob(C=k)=ck
Services occur singly, backward transitions occur
only to adjacent states and have rate μ
Forward transitions from state n can occur to any
n+k, k>0 state with rate ckλ
29
Analysis of Batch Systems (Con.)
λc2
λc2
λc1
n-2
λc1
n-1
n
μ
μ

λc1
λc1
n+2
n+1
μ
μ
The global balance equation are given by:


 P(n  k )c
k
  P(n  1)  (   ) P(n)
n 0
where for n=0, λP(0)= μP(1)
30
Analysis of Batch Systems (Con.)

To solve the equation we use Z-transform:



Let C(z)= znc denote the z-transform of the
sequence c1, c2, …
Let  (z) denote the z-transform of state
probabilities.
Multiply both sides of equation by zn and then sum
over n, we get :
1
( z )  P(0)   (1   ) ( z )  P(0) 

z
(1  z ) P(0)
( z ) 
1  z   z (1  C ( z ))
  C ( z ) ( z ) 
31
Analysis of Batch Systems (Con.)

We use Utilization law to compute P(0)




1-P(0)=U=λtotal/μ, where λtotal= C λ
P(0)=(1- C )
To ensure ergodicity, P(0)>0, <1/
We assume C has a geometric distribution


ck = (1-a)ak-1 for k= 1.. . 0<a<1
C(z)=z(1-a)/(1-az) and C = C(1)=1/(1-a)
32
Analysis of Batch Systems (Con.)

The expression for  (z) simplifies to
(1  a   )(1  az )
( z ) 
(1  a)(1  z (a   ))

The average queue length is
Q

C
(1  C )
C
It can be noted that Qbatch=Qexpo C
33
Staged Service with FCFS Scheduling

The k-stage Erlang system is shown below.


At most one customer is allowed to enter the
“service box”
State system is pair (n,j) where n gives the total
number of customers at station and j=1..k gives
the total number of customers at the station
1st stage 2nd stage
kμ
kμ
…
kth stage
kμ
34
Staged Service with FCFS Scheduling
(Con.) 1,1 λ 2,1 λ … n-1,1 λ n,1 λ n+1,1
kμ
1,k

λ
2,k
…
kμ
kμ
kμ
n-1,2 λ n,2 λ n+1,2
kμ
kμ
λ
…
n-1,k
λ
n,k
…
…
…
…
0
kμ
λ
1,2 λ 2,1
kμ
…
kμ
λ
kμ
n+1,k
The balance equations are as follows:



(λ+μ)P(n,1) = λP(n-1,1)+kμP(n+1,k) for j=1
(λ+μ)P(n,j) = λP(n-1,j)+kμP(n,j-1) for j>1
(λ)P(0) = kμP(1,k)
35
Staged Service with FCFS Scheduling
(Con.)

Let =λ/(kμ) , P(0) can be found by utilization
law


U=1-P(0)= λ/μ=k  P(0)=1-k
Let P(n) denote the probability of finding n
customers in the system :
k
P ( n) 
 P(n, j)
j 1
36
Staged Service with FCFS Scheduling
(Con.)

Use two dimensional z-transform of P(n,j):
k
 ( y, z ) 
*


y j z n P(n, j )
j 1 n 1

Let (z) denote the z-transform of P(n):
k
P ( n) 

z n P(n, j )  P(0)  * (1, z )
j 1

By determining *(1,z), we can determine
(z):
( z ) 
(1  k  )(1  z )
1  z[1   (1  z )]k
37
Staged Service with FCFS Scheduling
(Con.)

Differentiating (z) and evaluating z=1, we
get the average queue length:
k  (2   (k  1))
Q
2(1  k  )


Note that the queue length is smaller for a comparable
M/M queue and decrease monotonically with k.
Let k with the utilization U=λ/μ=k, the Avg. queue
length is :
U (1  U / 2)
QM / D /1 
1U
38