Basic Queueing Theory M/M/* Queues
嚜濁asic Queueing Theory
M/M/* Queues
These slides are created by Dr. Yih Huang of George
Mason University. Students registered in Dr.
Huang's courses at GMU can make a single
machine-readable copy and print a single copy of
each slide for their own reference, so long as each
slide contains the copyright statement, and GMU
facilities are not used to produce paper copies.
Permission for any other use, either in machinereadable or printed form, must be obtained from
the author in writing.
CS 756
1
Introduction
Queueing theory provides a mathematical
basis for understanding and predicting the
behavior of communication networks.
Basic Model
Arrivals
Departures
Queue
CS 756
Server
2
1
Major parameters:
每 interarrival-time distribution
每 service-time distribution
每 number of servers
每 queueing discipline (how customers are taken
from the queue, for example, FCFS)
每 number of buffers, which customers use to wait
for service
A common notation: A/B/m, where m is the
number of servers and A and B are chosen from
每 M: Markov (exponential distribution)
每 D: Deterministic
每 G: General (arbitrary distribution)
CS 756
3
M/M/1 Queueing Systems
Interarrival times are exponentially
distributed, with average arrival rate 竹.
Service times are exponentially distributed,
with average service rate ?.
There is only one server.
The buffer is assumed to be infinite.
The queuing discipline is first-come-firstserve (FCFS).
CS 756
4
2
System State
Due to the memoryless property of the
exponential distribution, the entire state of
the system, as far as the concern of
probabilistic analysis, can be summarized by
the number of customers in the system, i.
每 the past/history (how we get here) does
not matter
When a customer arrives or departs, the
system moves to an adjacent state (either i+1
or i-1).
CS 756
5
State Transition Diagram
竹
0
竹
1
?
竹
2
?
竹
3
?
竹
竹
4
?
5
?
?
竹
In equilibrium,
i+1
i
Let Pi = P{system in state i}
We have 竹 Pi = ? Pi +1
CS 756
?
The rate of
movements in
both directions
should be equal
6
3
Equations from the state transition diagram:
竹 P0 = ? P1
竹 P1 = ? P2
竹 P 2 = ? P3
Solve
竹
?
竹
P2 = ?
P
1
P
k
=
0
= 老 P0
1
= 老 ( 老 P0 ) = 老 2 P 0
P
P
= 老k
P
0
What is 老 ?
CS 756
7
Since
﹢
k =0
Pk =
﹢
k =0
老P
k
0
=1
we have
1
1? 老
P
0
=1
P
0
= 1? 老 .
That is, Pk = 老 k (1 ? 老 ).
Note that 老 must be less than 1, or else the
system is unstable.
CS 756
8
4
Average Number of Customers
N=
﹢
k =0
kP k = (1 ? 老 )
﹢
k 老k = ?
k =0
CS 756
9
Average delay per customer (time in queue
plus service time):
N
1
T= =
竹 ? ?竹
Average waiting time in queue:
1
1
老
W=
? =
? ?竹 ? ? ?竹
Average number of customers in queue:
老2
N Q = 竹W =
1? 老
CS 756
10
5
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- instructions for schedule m 3 form 1120 s rev december
- basic queueing theory m m queues
- chapter 3 o m management energy
- prospectus m a 2020 21
- matter of m a m respondent
- m 146000 m 146100 m 146200 lintra plus rodless
- convert lengths
- features and specifications for m acr automatic charging
- 2020 instructions for schedule m 3 form 1120 f
Related searches
- microeconomic theory basic principles
- microeconomic theory basic principles pdf
- basic set theory pdf
- m m to fpm
- m m financial scam
- basic set theory and logic
- basic electronics theory pdf
- microeconomic theory basic principles and extensions notes
- m m auto sales
- basic theory of biology
- medical m m case review template
- basic probability theory pdf