Queuing Theories and Model with Practice.ppt

Queuing Theory in Business Practices

1. Probability Review
Thinh Nguyen

2. Probability Theory Review
Sample space
Bayes’ Rule
Independence
Expectation
Distributions

3. Sample Space - Events
Sample Point

The outcome of a random experiment
Sample Space S

The set of all possible outcomes

Discrete and Continuous
Events

A set of outcomes, thus a subset of S

Certain, Impossible and Elementary

4. Set Operations
Union
Intersection
Complement
Properties
Commutation
Associativity
Distribution
De Morgan’s Rule
A B
A B
A B
C
A
C
A
A B B A  
  A B C A B C    
   A B C A B A C     
 
C
C C
A B A B  
S
A B

5. Axioms and Corollaries
Axioms


If
If A
1, A
2, … are pairwise
exclusive
Corollaries




A B 
 P A B P A P B  

11
k k
kk
P A P A
 

 

 
 

0P A
1P S
1
C
P A P A  
 
1P A
0P 
 
 
P A B
P A P B P A B
 
  

6. Conditional Probability
Conditional Probability of
event A given that event
B has occurred
If B
1, B
2,…,B
n a partition
of S, then
(Law of Total Probability)
A B
C
A
S
A B

 

|
P A B
P A B
P B


B
1
B
3
B
2
A

1 1
| ...
|
j j
P A P A B P B
P A B P B
  
   
   

7. Bayes’ Rule
If B
1, …, B
n a partition of S then

 
1
|
|
|
j
j
j j
n
k k
k
P A B
P B A
P A
P A B P B
P A B P B

 
 
 
 
   
   


likelihood prior
posterior
evidence



8. Event Independence
Events A and B are independent if
If two events have non-zero probability and are mutually
exclusive, then they cannot be independent
 P A B P A P B 

9. Random Variables

10. Random Variables
The Notion of a Random
Variable

The outcome is not always
a number

Assign a numerical value to
the outcome of the
experiment
Definition

A function X which assigns
a real number X(ζ) to each
outcome ζ in the sample
space of a random
experiment
S
x
S
x
ζ
X(ζ) = x

11. Cumulative Distribution Function
Defined as the probability
of the event {X≤x}
Properties
 
X
F x P X x 
0 1
X
F x 
lim 1
X
x
F x
 

lim 0
X
x
F x
  

if then
X X
a b F a F a 
 
X X
P a X b F b F a   
  1
X
P X x F x  
x
2
1
F
x
(x)
¼
½
¾
10 3
1
F
x(x)
x

12. Types of Random Variables
Continuous

Probability Density
Function
Discrete

Probability Mass
Function
 
X k k
P x P X x 
  
X X k k
k
F x P x u x x 


X
X
dF x
f x
dx

 
x
X X
F x f t dt
 


13. Probability Density Function
The pdf is computed from

Properties
For discrete r.v.
dx
f
X
(x)


X
X
dF x
f x
dx

  
b
X
a
P a X b f x dx  
 
x
X X
F x f t dt
 

1
X
f t dt

 

f
X(x)
 
X
P x X x dx f x dx   
x
  
X X k k
k
f x P x x x 

14. Expected Value and Variance
The expected value or mean of
X is
Properties
The variance of X is

The standard deviation of X is
Properties
 
X
E X tf t dt

 

 
k X k
k
E X x P x
E c c
E cX cE X
E X c E X c  
  
2
2
Var X E X E X
 
  
 
 Std X Var X 
0Var c
 
2
Var cX c Var X
 Var X c Var X 

15. Queuing Theory

16. Example
Send a file over the internetSend a file over the internet
packet link
buffer
Modem
card
(fixed rate)

17. Delay Models
time
place
A
B
C
p
r
o
p
a
g
a
t
i
o
n
t
r
a
n
s
m
i
s
s
i
o
n
C
o
m
p
u
t
a
t
i
o
n
(
Q
u
e
u
i
n
g
)

18. Queue Model

19. Practical Example

20. Multiserver queue

21. Multiple Single-server queues

22. Standard Deviation impact

23. Queueing Time

24. Queuing Theory
The theoretical study of waiting lines,
expressed in mathematical terms
input output
queue
server
Delay= queue time +service time

25. The Problem
Given
One or more servers that render the service
A (possibly infinite) pool of customers
Some description of the arrival and service
processes.
Describe the dynamics of the system
Evaluate its Performance
 If there is more than one queue for the server(s), there may also
be some policy regarding queue changes for the customers.

26. Common Assumptions
The queue is FCFS (FIFO).
We look at steady state : after the system has
started up and things have settled down.
State=a vector indicating the total # of customers in
each queue at a particular time instant
(all the information necessary to completely describe
the system)

27. Notation for queuing systems
A = the interarrival time distribution
B = the service time distribution
c = the number of servers
d = the queue size limit
A/B/c/d
M for Markovian (exponential) distribution
D for Deterministic distribution
G for General (arbitrary) distribution
:Where A and B can be

omitted if infiniteomitted if infinite

28. The M/M/1 System
Poisson
Process
output
queue
Exponential
server

29. Arrivals follow a Poisson process
a(t) = # of arrivals in time interval [0,t]

 = mean arrival rate
t = k ; k = 0,1,…. ; 0
Pr(exactly 1 arrival in [t,t+]) = 
Pr(no arrivals in [t,t+]) = 1-
Pr(more than 1 arrival in [t,t+]) = 0
Pr(a(t) = n) = e
- t
( t)
n
/n!
Readily amenable for analysisReadily amenable for analysis
Reasonable for a wide variety of situations Reasonable for a wide variety of situations

30. Model for Interarrivals and Service times
Customers arrive at times t
0 < t
1 < .... - Poisson distributed
The differences between consecutive arrivals are the
interarrival times : 
n = t
n - t
n-1



n in Poisson process with mean arrival rate , are
exponentially distributed,
Pr(
n  t) = 1 - e
- t

Service times
are exponentially distributed, with mean
service rate :
Pr(S
n  s) = 1 - e
-s

31. System Features
Service times are independent
service times are independent of the arrivals

Both inter-arrival and service times are memoryless
Pr(T
n > t
0+t | T
n> t
0) = Pr(T
n  t)
future events depend only on the present state
 This is a Markovian System

32. Exponential Distribution
given an arrival at time x
|
Same as probability starting at time = 0
P xtx
Px xt
Px
P xtPx
Px
e e
Px
e e
e
e e
e
xt x
xt x
x
x t
x
(() )
( ())
()
(())()
()
( )( )
()
( )
( )
()
()
 


 
 
 
 

 





 


 
 

 



 
 

 

1 1
1
11
1

33. Markov Models
Buffer
Occupancy
t t
• n+1
• n
• n-1
• n
departure
arrival

34. Probability of being in state n
PttPt t t tt
Pt t t
Ptt t
t
PttPt
dPt
dt
t
n n
n
n
n n
n
( )()[( )( ) ]
()[()( )]
()[()( )]
,
( )()
()
   
 
 

 


   
 
 

 
1 1
1
1
0
1
1
 
 
 
as Taylor series

35. Steady State Analysis
Substituting for
Steady state
P
0
Ptt
PP P
P
n
n n n
( )
( )

  

 



1 1
1

36. Markov Chains
0 1 ... n-1 n n+1
  
  
Rate leaving n =
Rate arriving n =
Steady State
State 0
P
P P
P P P
PP
n
n n
n n n
( )
( )






 

 
 
1 1
1 1
0 1

37. Substituting Utilization
P PP
P PP
P PP PP P
1 0 0
2 1 0
2 1 1 0 1 01
 
 
   








 
( )
()

38. Substituting P
1
PP P
PPP P
P P
n
n
2 0 0
2
0 0 0
2
0
0
1 
 

 


()

• Higher states have decreasing probability
• Higher utilization causes higher probability
of higher states

39. What about P
0
P PP
P
P
P
P
n
n
n
n
n
n
n
n






 





0 0
0 0
0
0
0
0
1
1
1
1
1
1
 



()
Queue determined by 




40. E(n), Average Queue Size



-1
=
)1()1()(
000








n
n
n
n
n
n nnnPnEq

41. Selecting Buffers
E(N)
1/3 .25
1 .5
3 .75
9 .9
For large utilization, buffers grow exponentially

42. Throughput
Throughput=utilization/service time = /T
s
For =.5 and T
s=1ms
Throughput is 500 packets/sec

43. Intuition on Little’s Law
If a typical customer spends T time units, on the overage, in
the system, then the number of customers left behind by
that typical customer is equal to
qTq

44. Applying Little’s Law
)1()1(
/
)1(
)( so
1
1
)1(
1
)1(
)(
)(
or or )()(
Delay Average M/M/1






















s
s
qw
T
TET
nE
TE
TqTwTEnE

45. Probability of Overflow
PnN p
n
nN
n
nN
N
( ) ()





1 1
1
1

46. Buffer with N Packets
1 with )1(
1
)1(
1
)1(
and
1
1
1
1
1
1+N
1
110
1
0
0
0
0


































N
N
N
N
N
n
nN
NN
n
n
N
n
n
p
pp
ppp

47. Example
Given

Arrival rate of 1000 packets/sec

Service rate of 1100 packets/sec

Find

Utilization

Probability of having 4 packets in the queue



 
1000
1100
091.
P
P P P P
4
4
1 2 3 5
1 062
082 075 068 056
 
   
().
.,.,.,.


48. Example
04,.05,.05,.06,.07,.07,.08,.09,.09,.10,.11.
04
1
1
yprobabilit loss cell buffers fixed 12With
28.)12(
buffers infiniteWith
99.9
1
)(
112
12
12
112











nP
.
)(
P
nP
nE






49. Application to Statistcal Multiplexing
Consider one transmission
line with rate R.
Time-division Multiplexing
Divide the capacity of the
transmitter into N channels,
each with rate R/N.
Statistical Multiplexing
Buffering the packets
coming from N streams into
a single buffer and
transmitting them one at a
time.
R/N
R/N
R/N
R


1
T
N
T
NN
T 



1
'

50. Network of M/M/1 Queues
1

1
2

3
3
4

2
211  
3212
 
313
 
ii
i
iL



 321 LLLL  321
 



J
i ii
i
T
1
1




51. M/G/1 Queue
Q S
0
S
2
2
S
SQ
Assume that every customer in the queue pays at rate R when his or
her remaining service time is equal to R.
Time Queuing:
Time Service :
Q
S
Total cost paid by a customer:
Expected cost paid by each customer:
2
][][
2
SEQE
C 










2
][][
][
2
SEQE
CQE


)1(2
][
][
2




SE
QE
At a given time t, the customers pay at a rate
equal to the sum of the remaining service times
of all the customer in the queue. The queue
begin first come-first served, this sum is equal to
the queueing time of a customer who would
enter the queue at time t.

1
][QET
The customers pat at rate since each
customer pays on the average and
customers go through the queue per unit time.
C
C 