Chapter 8
Queueing Theory
Reference Book:
Introduction to Probability Model – S. Ross
Topics:
Markov Chain
Queueing Models
Steady State Probability
Exponential Models (A single Server Queuing Sys)
Having Infinite Capacity
Having Finite Capacity
Prepared by Lec Wali Md Abdullah, CSE, MIST 1
Chapter 8
Queueing Theory
What is Queueing Theory?
Queueing theory is the mathematical study of waiting lines, or queues.
What is Markov Chain?
In probability theory, a Markov model is a stochastic model used
to model randomly changing systems where it is assumed that future
states depend only on the current state not on the events that occurred
before it (that is, it assumes the Markov property).
What is M/M/1 queue?
In queueing theory, a discipline within the mathematical theory of
probability, an M/M/1 queue represents the queue length in a system
having a single server, where arrivals are determined by a Poisson
process and job service times have an exponential distribution.
Prepared by Lec Wali Md Abdullah, CSE, MIST 2
Chapter 8
Queueing Theory
What is Poisson Process?
In probability, statistics and related fields, a Poisson point
process or Poisson process (also called a Poisson random
measure, Poisson random point field or Poisson point field) is a type
of random mathematical object that consists of points randomly located
on a mathematical space.
What is Exponential Distribution?
In probability theory and statistics, the exponential distribution (also
known as negative exponential distribution) is the probability
distribution that describes the time between events in a Poisson process,
i.e. a process in which events occur continuously and independently at a
constant average rate.
Prepared by Lec Wali Md Abdullah, CSE, MIST 3
Cost Equation
Prepared by Lec Wali Md Abdullah, CSE, MIST 4
Steady State Probability
Prepared by Lec Wali Md Abdullah, CSE, MIST 5
Steady State Probability
Prepared by Lec Wali Md Abdullah, CSE, MIST 6
Steady State Probability Example
Prepared by Lec Wali Md Abdullah, CSE, MIST 7
Steady State Probability Proof
Proof.
An arrival will see n in the system whenever the number in the system goes from
n to n + 1;
Similarly, a departure will leave behind n whenever the number in the system
goes from n + 1 to n.
Now in any interval of time T the number of transitions from n to n + 1 must equal
to within 1 the number from n + 1 to n.
(Between any two transitions from n to n + 1, there must be one from n + 1 to n,
and conversely.)
Hence, the rate of transitions from n to n + 1 equals the rate from n + 1 to n;
or, equivalently, the rate at which arrivals find n equals the rate at which
departures leave n.
Prepared by Lec Wali Md Abdullah, CSE, MIST 8
Steady State Probability Proof
Proof (Contd).
Prepared by Lec Wali Md Abdullah, CSE, MIST 9
Exponential Models
A Single Server Exponential Queueing System
Having Infinite Capacity
M/M/1 Queue:
Suppose that customers arrive at a single-server service station in accordance
with a Poisson process having rate λ.
The times between successive arrivals are independent exponential random
variables having mean 1/λ
Each customer, upon arrival, goes directly into service if the server is free and, if
not, the customer joins the queue.
When the server finishes serving a customer, the customer leaves the system,
and the next customer in line, if there is any, enters service.
The successive service times are assumed to be independent exponential
random variables having mean 1/μ.
The two Ms refer to the fact that both the inter-arrival and the service
distributions are exponential (and thus memory-less, or Markovian), and the 1
to the fact that there is a single server.
Prepared by Lec Wali Md Abdullah, CSE, MIST 10
Exponential Models
A Single Server Exponential Queueing System
Having Infinite Capacity
Analyze with Limiting Probability Pn
Rate Equality Principle: For each n is greater equal 0, the rate at which the
process enters state n equals the rate at which it leaves state n.
Now Consider Sate 0:
P0 P1
Prepared by Lec Wali Md Abdullah, CSE, MIST 11
Exponential Models
A Single Server Exponential Queueing System
Having Infinite Capacity
P0 P1 Pn-1 Pn P
n+1
Prepared by Lec Wali Md Abdullah, CSE, MIST 12
Exponential Models
A Single Server Exponential Queueing System
Having Infinite Capacity
Prepared by Lec Wali Md Abdullah, CSE, MIST 13
Exponential Models
A Single Server Exponential Queueing System
Having Infinite Capacity
Prepared by Lec Wali Md Abdullah, CSE, MIST 14
Exponential Models
A Single Server Exponential Queueing System
Having Infinite Capacity
Self Study: Example 8.2 (Important)
Prepared by Lec Wali Md Abdullah, CSE, MIST 15
Exponential Models
A Single Server Exponential Queueing System
Having Finite Capacity
M/M/1 Queue:
In the previous model, we assumed that there was no limit on the number of
customers that could be in the system at the same time.
However, in reality there is always a finite system capacity N, in the sense that
there can be no more than N customers in the system at any time.
By this, we mean that if an arriving customer finds that there are already N
customers present, then he does not enter the system.
The two Ms refer to the fact that both the inter-arrival and the service
distributions are exponential (and thus memory-less, or Markovian), and the 1
to the fact that there is a single server.
Prepared by Lec Wali Md Abdullah, CSE, MIST 16
Exponential Models
A Single Server Exponential Queueing System
Having Finite Capacity
P0 P1 P N-1 PN
Prepared by Lec Wali Md Abdullah, CSE, MIST 17
Exponential Models
A Single Server Exponential Queueing System
Having Finite Capacity
P0 Pn-1 Pn Pn+1 PN
Prepared by Lec Wali Md Abdullah, CSE, MIST 18
Exponential Models
A Single Server Exponential Queueing System
Having Finite Capacity
Solution:
We could now either solve the balance equations exactly as we did for the
infinite capacity model, or we could save a few lines by directly using the result that
the rate at which departures leave behind n−1 is equal to the rate at which arrivals
find n − 1. Invoking this result yields
Prepared by Lec Wali Md Abdullah, CSE, MIST 19
Exponential Models
A Single Server Exponential Queueing System
Having Finite Capacity
Prepared by Lec Wali Md Abdullah, CSE, MIST 20
THANK YOU
Prepared by Lec Wali Md Abdullah, CSE, MIST 21
