Queueing theory is the mathematical study of waiting lines, or queues. The theory enables mathematical analysis of several related processes, including arriving at the queue, waiting in the queue , and being served at the front of the queue...
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, Buzen's algorithm is an algorithm for calculating the normalization constant G(K) in the Gordon–Newell theorem
Gordon–Newell theorem
In queueing theory, a discipline within the mathematical theory of probability, the Gordon–Newell theorem is an extension of Jackson's theorem from open queueing networks to closed queueing networks of exponential servers. We cannot apply Jackson's theorem to closed networks because the queue...
Jeffrey Peter Buzen is an American computer scientist in system performance analysis best known for his contributions to queueing theory. His 1971 doctoral thesis Computational algorithms for closed queueing networks with exponential servers has guided the study of queueing network modeling.Born...
in 1973. Once G is computed the probability distributions for the network can be found. In contrast, mean value analysis
Mean value analysis
In queueing theory, a specialty within the mathematical theory of probability, mean value analysis is a technique for computing expected queue lengths in equilibrium for a closed separable system of queues...
is an alternative algorithm that can also be used to derive some performance measures (such as the mean queue lengths) without having to directly compute the normalization constant.
The motivation for this algorithm is efficiency: a straightforward Gordon-Newell calculation would require the enumeration of all states that the system can be in, resulting in a combinatorial explosion. Buzen's algorithm is of order N2, making the application of the G-N theorem practical, and opening up a large class of queueing systems to accurate modeling.
In the queuing literature Buzen's algorithm is sometimes also referred to as the convolution algorithm.
Problem setup
Consider a closed queueing network with M service facilities and N circulating customers. Let represent the number of customers present at the ith facility, with . We assume that the service time for a customer at the ith facility is given by an exponentially distributed random variable with mean and that after completing service at the ith facility a customer will proceed to the jth facility with probability pij.
In queueing theory, a discipline within the mathematical theory of probability, the Gordon–Newell theorem is an extension of Jackson's theorem from open queueing networks to closed queueing networks of exponential servers. We cannot apply Jackson's theorem to closed networks because the queue...
that the equilibrium distribution of customers in the network is given by:
where the are found from the equations:
and G(N) is a normalizing constant such that the above probabilities sum to 1.
The purpose of the Buzen algorithm is to numerically compute values of G.
Marginal distributions, expected number of customers
The general G-N distribution given above is mainly of theoretical interest. However, expressions for a number of useful performance measures can be derived from it. Buzen showed that the probability that there are exactly k customers at facility i is given by:
and the expected number of customers at facility i by
Note that these expressions also involve G. It is in the evaluation of these expressions that the algorithm is useful.
Derivation
The algorithm computes not just G but a two-dimensional function
.
Once the calculation ends the values we are interested in are found by .
The definition of g and a recursive method of calculating it are as follows
Also
and
This recursive relationship allows for the calculation of all G(N) up to any value of N in order
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
O(MN) time.
Implementation
It will be assumed that the Xm have been computed by solving the relevant equations and are available as an input to our routine. Although g is in principle a two dimensional matrix, it can be computed in a column by column fashion starting from the leftmost column. The routine uses a single column vector C to represent the current column of g.
C[0] := 1
for n := 1 step 1 until N do
C[n] := 0;
for m := 1 step 1 until M do
for n := 1 step 1 until N do
C[n] := C[n] + X[m]*C[n-1];
At completion, C contains the desired values G(0), G(1) to G(N).
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
represent the number of customers present at the ith facility, with 
. We assume that the service time for a customer at the ith facility is given by an exponentially distributed random variable with mean 
and that after completing service at the ith facility a customer will proceed to the jth facility with probability pij.
are found from the equations:
.
.
