Transcript Document

2.6 The M/M/1/N Queueing System: The Finite
Buffer Case
State N
The blocking probability for various values of
offered load, λ/μ, when N=5
The blocking probability for various values of
offered load, λ/μ=0.9 and buffer size is varied
2.7 The M/M/∞ Queueing System:
Infinite Number of Servers
The state dependent arrival and
service rates are
The M/M/m Queueing Systems: m
Parallel Servers with a Queue
The state dependent arrival and
service rates
m Parallel Servers
Summing up over all the states one has
In the above ρ=λ/mμ
• In telephone engineering one quantity of
interest is the probability that all the server
in this system are busy
Substituting for p0 this becomes
2.9 The M/M/m/m Queue: A Loss System
As Figure 2.22 shows, the queueing system
simply consists of m parallel servers
Summing over all the m +1states leads to
Erlang’s B formula: Erlang formula of the
first kind, in Europe
2.10 Central Server CPU Model
The mean waiting to get through the
queueing system
2.11 Transient Solution of the M/M/1/∞
Queueing System
1.
Equilibrium case: A set of linear
equations
2. Transient case: A set of linear
differential equations
The moment-generating function
• The state probabilities form a sequence of
numbers that can be transformed, like any
numerical sequence, into a “frequency”
like domain. It turn out to relatively easy to
obtain the frequency domain solution.
The details of the solution
techniques are:
2.11.2 The Transient Solution
We first take the differential equations of the
previous section, multiply both sides by zn, and sum
from n=1 to∞:
• Recall that to get proper moment generating
functions the indexes must start at n=0 so
we have
But three of the items here are just the boundary
differential equation at n=0 and so drop out, leaving:
We can rewrite this further
Now identifying the moment-generating functions
(which sometimes requires adding and subtracting
terms) one has
The initial condition to this equation involves i
customers at time 0:
To solve this partial differential equation, one can
use Laplace transform which are defined as
For the left-hand side of the boxed equation one can
integrate by parts to find its transform:
Now take the Laplace transform of the boxed
differential equation and multiply out the constants so
that
We can now solve for P*(z,s):
At this point one must determine P0*(s) and invert the
transform. The interested reader can [GROS] (Page
99~103) for details. The well-known result for the time
evolution of the state probabilities is
Where ρ=λ/μ,
n(0)=i customers,
And Il() is the modified Bessel function of the first
kind of order l:
2.11.3 Speeding up the Computation
• An efficient procedure for the calculation of
Pn(t)
This is done by first letting
a=(2μt)1/2 and b=(2λt)1/2
Up to seven times faster
2.12 The M/G/1 Queueing System
• M/G/1: Arrivals  Poisson process,
Service General (arbitrary) probability
distribution
• Mean number in the M/G/1 queueing
system mean waiting time,
2.12.2 Mean number in the M/G/1
Queueing System
• Pollaczck-Khinchin mean value formula
• A key point is that that the state
probabilities as these departure instant are
in fact equal to the state probabilities at any
time instant.
• GROS, Kendall’s approach
The recursion
the determination of a succession of elements
• The number in the system immediately after the (i+1) st
departure instant is ni+1.
• This number includes both those customers in the
queue and the customer in service.
• This number is also equal to the number in the system
immediately after the ith departure instant minus 1
(because of the departure of a customer at the (i+1) st
departure instant. This number of arrival we will call
ai+1.
• For this equation to work there must be at least one
customer in the system all the departure instant. Thus
•
We still have to take care of the case ni=0. This is
actually simpler than the case ni>0. The number in the
queueing system at the (i+1) st departure instant is just
the number of arrivals during the service period of the
first customer to arrive to the empty queueing system.
This first customer is the one that departs at the (i+1) st
departures instant and is not counted in determining ai+1
• Bringing this together we have
We would like to express this as a single
equation. To do this, we will introduce
the unit step function:
Now we can rewrite the equation for ni+1 as
If we square both side of this recursion and
take expectations we have
6 items
In order to solve for the Pollaczek-Khinchin
formula we need to solve for each of these
terms, one by one, we will now do this
• Sundry (miscellaneous) Results
• E[(ni+1)2], E[ni2]
• These two terms should be equal in equilibrium so
that they will cancel in (2.189).
• E[(u(ni))2]:
• Because of the nature of the step function
u(ni)2=u(ni), we can replace E[(u(ni))2] with
E[(u(ni))]. But what is E[(u(ni))]?
P[busy]
• Consider an interval I. The server will be busy for
a time period equal to
I – I p0
• The number of customers served is
• (I – I p0)μ
• Where μ is the mean service rate of the queueing
system. In equilibrium the quantity above should
be equal to the number of arrivals
Note that no restrictive assumptions have been
made either the arrival process or the service
times. Thus this result is valid for a G/G/1
queueing system, that is, one with an arbitrary
process and service process time distribution.
2E[(ni, u(ni))]:
Clearly niu(ni)=ni, so we can say
2E[ u(ni)ai+1]:
The number of customers that arrive into the system
between the ith and (i+1)st departure instant, ai+1, is
independent of the number in the queueing system
immediately after the ith departure instant, ni. Thus
We already know that E[u(ni)]=ρ. To determine E[ai+1]
one can look at the original recursion for E[ni+1]
And take the expectation of both sides:
In equilibrium E[ni+1]=E[ni], so one is left with
One can now say that:
2 E[ni+1ai+1]:
Using the same argument as before, the two quantities are
statistically independent, so
Putting It All Together
Now we can substitute these sundry results into the equation:
Solve for E[ni], we have
We will assume for now, and prove in section 2.12.3, that
the expected number of customers in the queueing system
at the departure instants is the same as the expected
number of customers at any instant of time:
We can also say, because the input is Poisson, that the
expected number of arrivals between two successive
departure instants is a time-invariant quantity:
We thus have
We almost have a simple expression for the mean number
in the M/G/1 queueing system in equilibrium or E[n].
What is lacking is a simple expression for E[a2]
What is E[a2] ?
The quantity “a” is the number of arrivals during a typical
servicing period in equilibrium. Processing as in [GROS]
we can write
• We need to solve for VAR [a]. Let us the
service time. Then an interesting
relationship [GROS] for two random
variables X and Y that we can make use of
is [PARZ]
One can solve for the two components of this sum:
Here σs2 is the variance of the service time. So we have
The Pollaczek-Khinchin Mean Value Formula
Substituting (2.216) for E[a2] lead to
We can get another form by expressing E[n] as
E[n] = n as a function of the mean arrival rate, mean
service rate, and variance of the service time distribution.
Little’s Law
• n: the mean customers in a queueing system
• λ: the mean arrival rate to the queueing
system
• τ : the mean waiting time to get through the
queueing system
Page 82
2.12.3 Why We Use Departure
Instants
• The Pollaczek-Khinchin mean value formula:
the assumption of the state probabilities at
departure instants are the same as the state
probabilities at any instant.
• We will take a realization of the queueing process
over a long interval. The number in the queueing
system at time t will be n(t). The interval will
stretch from time 0 to time T.
2.12.3 Why We Use Departure
Instants
• The number of arrivals in the interval (0, T)
that occur when the number of customers in
the system is n will be called an(t). The
number of departures bringing the system
from state n+1 to state n in the interval (0, T)
will be called dn(t).
It should also be true from first principles that
Where d(T) and a(T) are the total number of departures and
arrivals, respectively, over (0,T). One can now define the
state probabilities for the departure instants as
This empirical definition of the state probabilities becomes
exact in the limit. Now
The denominator (the part of a fraction that is below the
line) can be recognized as the equation we just discussed,
(2.223). The numerator was created by adding and
subtracting an(T) to dn(T). As T∞, dn(T)-an(T) will never
be greater than one, as has been mentioned. As T∞, and
a(T) and an(T) will∞, and
2.12.3 Why We Use Departure
Instants
• What this proves directly is that state probabilities
seen at the departure instants are the same as the
state probabilities seen at the arrival instants. But
going back to our Poisson process coin-flipping
analogy, the arrival instants are random points in
time and independent of the queueing system state.
Thus it should seem as the state probability seen at
any time. This completes the proof that looking at
state probabilities at departure instants for the
M/G/1 queueing system is the same as looking at
state probabilities for this queueing system at any
instant.
2.12.4 Probability Distribution of the
Number in the Queueing System
• Define a matrix of transition probabilities
as
Service time density, b(s) , the probability of j arrivals
between the ith and (i+1)st departure instance.
The equilibrium equations
π: The state probabilities,
probabilities
P : A matrix of transition
π: The state probabilities
Given K, or K(z), we can obtain the transfer function π(z) or
the state probability π
Given K, or K(z), we can obtain the transfer function π(z) or
the state probability π