Queuing-theoretic framework.
Consider a system of objects where count of objects at a time t is given by . The colony of objects grows and shrink through “birth” and “death” processes, respectively.
Birth and death model.
A birth or a death event may occur during a time interval . If is the birthrate and is the death rate then
■ probability that there will be a single birth
during is
■ probability that there will be no birth during
is
■ probability of multiple births during is zero.
■ probability of a single death during is .
■ probability of no death during is
■ probability of multiple death in is zero.
Let be the probability that the system is in state at time .
Then,
That is,
For , we get
… (1)
This is Birth-death equation of a Markov system. Why is it a Markov system?
Some specific cases.
1. Pure birth process. No death in the system. .
Then eqn (1) becomes
Check that the solution of this differential equation is
This is Poisson probability distribution. For example,
● number of packets received at a router in a 5 min period
● number of flaws on an IC panel
● number of typos per page typed
will most likely be Poisson distributed.
Notice average level or value of
and variance in ,
Example. The number of intrusion events as detected by a SNORT type system roughly amounts to 2.1 per day (i.e. the arrival rate per day). What is the probability that it will detect 4 intrusion events on a given day?
P(4 intrusions) =
Consider the equilibrium solution of eqn(1) i.e. . This implies:
M/M/1 queue
■ Poisson arrival (Indicated by M)
■ Exponential service time (time between two
departures from server)
■ Single server
■ Unlimited queue-size
■ Infinite population
What is G/G/m/k/N? What is D/M/m/k/?
Symbolic representation of a queuing system.
State diagram (transition diagram)
At state 0: the balance equation is
Flow-in = Flow-out
… (2a)
At state 1: the balance equation is
Flow-in = Flow-out
(
… (2b)
We see that in general it must be of the form
Define . Then .
Since we get if
Therefore,
or
… (3)
From here, we get,
…(4)
The average number of customers in the system, the resident-density is
=
But,
Discouraged arrivals:
More customers in the system lower arrival rate.
State Transition diagram:
Balance equations:
Continuing this way, we get
Since, we have
i.e. and
Probability that the system is busy = system utilization =
Expected number of customers in the system, L,
=
To use Little theorem once again,
average arrival rate in the system.
= utilization factor in terms of average
arrival rate
Thus,
Using this, and the Little theorem, average time spent in the system (Residence time)
Kendal’s notation for queues:
A/B/C/D/E
Where:
A: Distribution of interarrival times of customers
B: Distribution of service times
C: Number of servers
D: Max number of customers which can be in the system
E: Calling population size
A and B can take any of the following distribution.
: Exponential distribution (Markovian)
: Degenerate or Deterministic distribution
: Erlang distribution (k = shape parameter)
: General distribution (arbitrary distribution)
If G is used for A, it is often appears as GI (General and Independent).
e.g. M/M/m/k/N
Exponential interarrival time (Poison arrival), exponential service time, m servers, buffer size k, population size N
M/M/c queue. Multiserver queue. A queue with c servers.
Balance equations.
At state 0,
At state 1,
At state 2,
At state
At state
Rewriting, we get
… …
This gives, for and
for
From these two, we get (from the requirement )
By Little’s formula, and
Where
= …