Transcript ppt - Electrical & Computer Engineering

CPE 619
Introduction to Queuing Theory
Aleksandar Milenković
The LaCASA Laboratory
Electrical and Computer Engineering Department
The University of Alabama in Huntsville
http://www.ece.uah.edu/~milenka
http://www.ece.uah.edu/~lacasa
Overview




Queueing Notation
Rules for All Queues
Little's Law
Types of Stochastic Processes
2
Queueing Models: What Will You Learn?








What are various types of queues?
What is meant by an M/M/m/B/K queue?
How to obtain response time, queue lengths,
and server utilizations?
How to represent a system using a network of several queues?
How to analyze simple queueing networks?
How to obtain bounds on the system performance
using queueing models?
How to obtain variance and other statistics
on system performance?
How to subdivide a large queueing network model and solve it?
3
Basic Components of a Queue
1. Arrival
process
5. Customer
Population
6. Service
discipline
2. Service time
distribution
4. Waiting
positions 3. Number of
servers
Example: students at a typical computer terminal room
with a number of terminals. If all terminals are busy,
the arriving students wait in a queue.
4
Kendall Notation A/S/m/B/K/SD






A: Arrival process
S: Service time distribution
m: Number of servers
B: Number of buffers (system capacity)
K: Population size, and
SD: Service discipline
5
Arrival Process




Arrival times:
Interarrival times:
tj form a sequence of Independent and Identically Distributed
(IID) random variables
The most common arrival process: Poisson arrivals


Inter-arrival times are exponential + IID  Poisson arrivals
Notation:




M = Memoryless = Poisson
E = Erlang
H = Hyper-exponential
G = General  Results valid for all distributions
6
Service Time Distribution





Time each student spends at the terminal
Service times are IID
Distribution: M, E, H, or G
Device = Service center = Queue
Buffer = Waiting positions
7
Service Disciplines












First-Come-First-Served (FCFS)
Last-Come-First-Served (LCFS)
Last-Come-First-Served with Preempt and Resume (LCFS-PR)
Round-Robin (RR) with a fixed quantum.
Small Quantum  Processor Sharing (PS)
Infinite Server: (IS) = fixed delay
Shortest Processing Time first (SPT)
Shortest Remaining Processing Time first (SRPT)
Shortest Expected Processing Time first (SEPT)
Shortest Expected Remaining Processing Time first (SERPT).
Biggest-In-First-Served (BIFS)
Loudest-Voice-First-Served (LVFS)
8
Common Distributions






M: Exponential
Ek: Erlang with parameter k
Hk: Hyper-exponential with parameter k
D: Deterministic  constant
G: General  All
Memoryless:


Expected time to the next arrival is always 1/l
regardless of the time since the last arrival
Remembering the past history does not help
9
Example: M/M/3/20/1500/FCFS








Time between successive arrivals is exponentially distributed
Service times are exponentially distributed
Three servers
20 Buffers = 3 service + 17 waiting
After 20, all arriving jobs are lost
Total of 1500 jobs that can be serviced
Service discipline is first-come-first-served
Defaults:





(Only the first 3 parameters are sufficient to indicate the type)
Infinite buffer capacity
Infinite population size
FCFS service discipline
G/G/1 = G/G/1/1/1/FCFS
10
Group Arrivals/Service




Bulk arrivals/service
M[x]: x represents the group size
G[x]: a bulk arrival or service process
with general inter-group times
Examples:


M[x]/M/1 : Single server queue with bulk Poisson
arrivals and exponential service times
M/G[x]/m: Poisson arrival process, bulk service with
general service time distribution, and m servers
11
Key Variables
1
2
l
m
m
ns
nq
n
Previous
Arrival
Time
Begin
End
Service Service
Arrival
t
w
s
r
12
Key Variables (cont’d)







t = Inter-arrival time = time between two successive arrivals
l = Mean arrival rate = 1/E[t]
May be a function of the state of the system,
e.g., number of jobs already in the system
s = Service time per job
m = Mean service rate per server = 1/E[s]
Total service rate for m servers is mm
n = Number of jobs in the system.
This is also called queue length
Note: Queue length includes jobs currently receiving service
as well as those waiting in the queue
13
Key Variables (cont’d)




nq = Number of jobs waiting
ns = Number of jobs receiving service
r = Response time or the time in the system
= time waiting + time receiving service
w = Waiting time
= Time between arrival and beginning of service
14
Rules for All Queues
Rules: The following apply to G/G/m queues
1. Stability Condition:
l < mm
Finite-population and the finite-buffer systems
are always stable
2. Number in System versus Number in Queue:
n = n q+ n s
Notice that n, nq, and ns are random variables. E[n]=E[nq]+E[ns]
If the service rate is independent of the number in the queue,
Cov(nq,ns) = 0
15
Rules for All Queues (cont’d)
3. Number versus Time:
If jobs are not lost due to insufficient buffers,
Mean number of jobs in the system
= Arrival rate  Mean response time
4. Similarly,
Mean number of jobs in the queue
= Arrival rate  Mean waiting time
This is known as Little's law.
5. Time in System versus Time in Queue
r=w+s
r, w, and s are random variables
E[r] = E[w] + E[s]
16
Rules for All Queues (cont’d)
6. If the service rate is independent
of the number of jobs in the queue,
Cov(w,s)=0
17
Little's Law




Mean number in the system
= Arrival rate  Mean response time
This relationship applies to all systems or parts of systems in
which the number of jobs entering the system is equal to those
completing service
Named after Little (1961)
Based on a black-box view of the system:
Arrivals

Black
Box
Departures
In systems in which some jobs are lost due to finite buffers,
the law can be applied to the part of the system
consisting of the waiting and serving positions
18
Proof of Little's Law
4 Arrival
Job 3
number
2
1
Departure
4
Number 3
in
2
System
1
12345678
Time





12345678
Time
If T is large, arrivals = departures = N
4
Arrival rate = Total arrivals/Total time= N/T Time
3
Hatched areas = total time spent inside
in
the system by all jobs = J
2
System
Mean time in the system= J/N
1
Mean Number in the system
= J/T = (N/T) (J/N)
= Arrival rate  Mean time in the system
1 2 3
Job number
19
Application of Little's Law
Arrivals

Applying to just the waiting facility of a service center


Departures
Mean number in the queue = Arrival rate  Mean waiting time
Similarly, for those currently receiving the service, we have:

Mean number in service = Arrival rate  Mean service time
20
Example 30.3

A monitor on a disk server showed that the average time to
satisfy an I/O request was 100 milliseconds. The I/O rate was
about 100 requests per second. What was the mean number
of requests at the disk server?

Using Little's law:
Mean number in the disk server
= Arrival rate  Response time
= 100 (requests/second) (0.1 seconds)
= 10 requests
21
Stochastic Processes



Process: Function of time
Stochastic Process: Random variables,
which are functions of time
Example 1:





n(t) = number of jobs at the CPU of a computer system
Take several identical systems and observe n(t)
The number n(t) is a random variable
Can find the probability distribution functions
for n(t) at each possible value of t
Example 2:

w(t) = waiting time in a queue
22
Types of Stochastic Processes




Discrete or Continuous State Processes
Markov Processes
Birth-death Processes
Poisson Processes
23
Discrete/Continuous State Processes





Discrete = Finite or Countable
Number of jobs in a system n(t) = 0, 1, 2, ....
n(t) is a discrete state process
The waiting time w(t) is a continuous state process
Stochastic Chain: discrete state stochastic process
24
Markov Processes






Future states are independent of the past and
depend only on the present
Named after A. A. Markov who defined and analyzed
them in 1907
Markov Chain: discrete state Markov process
Markov  It is not necessary to know how long the process
has been in the current state  State time has a memoryless
(exponential) distribution
M/M/m queues can be modeled using Markov processes
The time spent by a job in such a queue is a Markov process
and the number of jobs in the queue is a Markov chain
25
Birth-Death Processes
l0
0
1
m1



l1
l2
…
2
m2
lj-1
m3
j-1
lj
j
mj
lj+1
j+1
mj+1
m j+2
The discrete space Markov processes in which the transitions
are restricted to neighboring states
Process in state n can change only to state n+1 or n-1.
Example: the number of jobs in a queue with a single server
and individual arrivals (not bulk arrivals)
26
Poisson Processes


Interarrival time s = IID and exponential
 number of arrivals n over a given interval (t, t+x)
has a Poisson distribution
 arrival = Poisson process or Poisson stream
Properties:

1.Merging:

2.Splitting: If the probability of a job going to ith substream is
pi, each substream is also Poisson with a mean rate of pi l
27
Poisson Processes (cont’d)

3.If the arrivals to a single server with exponential service time are
Poisson with mean rate l, the departures are also Poisson with
the same rate l provided l < m
28
Poisson Process (cont’d)

4. If the arrivals to a service facility with m service centers are
Poisson with a mean rate l, the departures also constitute a
Poisson stream with the same rate l, provided l < i mi. Here,
the servers are assumed to have exponentially distributed service
times.
29
Relationship Among Stochastic
Processes
30
Summary




Kendall Notation: A/S/m/B/k/SD, M/M/1
Number in system, queue, waiting, service
Service rate, arrival rate, response time, waiting time,
service time
Little’s Law: Mean number in system = Arrival rate X
Mean time spent in the system
Processes: Markov  Memoryless,
Birth-death  Adjacent states
Poisson  IID and exponential inter-arrival
31
Analysis of A Single
Queue
Overview





Birth Death Processes
M/M/1 Queue
M/M/m Queue
M/M/m/B Queue with Finite Buffers
Results for other Queueing systems
33
Birth-Death Processes





Jobs arrive one at a time (and not as a batch)
State = Number of jobs n in the system
Arrival of a new job changes the state to n+1  birth
Departure of a job changes the system state
to n-1  death
State-transition diagram:
l0
0
l1
1
m1
l2
…
2
m2
lj-1
m3
j-1
lj
j
mj
lj+1
j+1
mj+1
m j+2
34
Birth-Death Processes (cont’d)

When the system is in state n, it has n jobs in it.



The new arrivals take place at a rate ln
The service rate is mn
We assume that both the inter-arrival times and
service times are exponentially distributed
35
Theorem: State Probability

The steady-state probability pn of a birth-death
process being in state n is given by:

Here, p0 is the probability of being in the zero state
36
Proof

Suppose the system is in state j at time t. There are j
jobs in the system. In the next time interval of a very
small duration Dt, the system can move to state j-1 or
j+1 with the following probabilities:
37
Proof (cont’d)



If there are no arrivals or departures, the system will
stay in state j and, thus:
Dt = small  zero probability of two events (two
arrivals, two departure, or a arrival and a departure)
occurring during this interval
pj(t) = probability of being in state j at time t
38
Proof (cont’d)

The jth equation above can be written as follows:

Under steady state, pj(t) approaches a fixed value pj,
that is:
39
Proof (cont’d)

Substituting these in the jth equation, we get:

The solution to this set of equations is:
40
Proof (cont’d)

The sum of all probabilities must be equal to one:
41
M/M/1 Queue






M/M/1 queue is the most commonly used type of queue
Used to model single processor systems or to model
individual devices in a computer system
Assumes that the interarrival times and the service times are
exponentially distributed and there is only one server
No buffer or population size limitations and the service
discipline is FCFS
Need to know only the mean arrival rate l and the mean
service rate m
State = number of jobs in the system
l
0
l
1
m
l
…
2
m
l
m
J-1
l
J
m
m
l
J+1
m
42
Results for M/M/1 Queue

Birth-death processes with

Probability of n jobs in the system:
43
Results for M/M/1 Queue (cont’d)


The quantity l/m is called traffic intensity and is
usually denoted by symbol r. Thus:
n is geometrically distributed.
Utilization of the server
= Probability of having one or more jobs in the
system:
44
Results for M/M/1 Queue (cont’d)

Mean number of jobs in the system:

Variance of the number of jobs in the system:
45
Results for M/M/1 Queue (cont’d)

Probability of n or more jobs in the system:

Mean response time (using the Little's law):
Mean number in the system =
Arrival rate × Mean response time
That is:
46
Results for M/M/1 Queue (cont’d)

Cumulative distribution function of the response time:

The response time is exponentially distributed.
 q-percentile of the response time
47
Results for M/M/1 Queue (cont’d)

Cumulative distribution function of the waiting time:

This is a truncated exponential distribution. Its qpercentile is given by:

The above formula applies only if q is greater than
100(1-r). All lower percentiles are zero.
48
Results for M/M/1 Queue (cont’d)




Mean number of jobs in the queue:
Idle  there are no jobs in the system
The time interval between two successive idle
intervals
All results for M/M/1 queues including some for the
busy period are summarized in Box 31.1 in the book.
49
Example 31.2





On a network gateway, measurements show that the packets
arrive at a mean rate of 125 packets per second (pps) and the
gateway takes about two milliseconds to forward them. Using
an M/M/1 model, analyze the gateway. What is the probability
of buffer overflow if the gateway had only 13 buffers? How
many buffers do we need to keep packet loss below one
packet per million?
Arrival rate l = 125 pps
Service rate m = 1/.002 = 500 pps
Gateway Utilization r = l/m = 0.25
Probability of n packets in the gateway
= (1-r)rn = 0.75(0.25)n)
50
Example 31.2 (cont’d)

Mean Number of packets in the gateway
= (r/(1-r) = 0.25/0.75 = 0.33)
Mean time spent in the gateway
= ((1/m)/(1-r)= (1/500)/(1-0.25) = 2.66 milliseconds
Probability of buffer overflow

To limit the probability of loss to less than 10-6:


We need about ten buffers.
51
Example 31.2 (cont’d)

The last two results about buffer overflow are
approximate. Strictly speaking, the gateway should
actually be modeled as a finite buffer M/M/1/B queue.
However, since the utilization is low and the number
of buffers is far above the mean queue length, the
results obtained are a close approximation.
52
Summary





Birth-death processes: Compute probability of having
n jobs in the system
M/M/1 Queue: Load-independent => Arrivals and
service do not depend upon the number in the
system ln= l, mn=m
Traffic Intensity: r = l/ m
Mean Number of Jobs in the system = r/(1-r)
Mean Response Time = (1/m)/(1-r)
53
M/M/m Queue
59