Buzen's algorithm

In queueing theory, a discipline within the mathematical theory of probability, Buzen's algorithm (or convolution algorithm) is an algorithm for calculating the normalization constant G(N) in the Gordon–Newell theorem. This method was first proposed by Jeffrey P. Buzen in 1973. Computing G(N) is required to compute the stationary probability distribution of a closed queueing network.

Performing a naïve computation of the normalising constant requires enumeration of all states. For a system with N jobs and M states there are ${\tbinom {N+M-1}{M}}$ states. Buzen's algorithm "computes G(1), G(2), ..., G(N) using a total of NM multiplications and NM additions." This is a significant improvement and allows for computations to be performed with much larger networks.

Problem setup

Consider a closed queueing network with M service facilities and N circulating customers. Write n_i(t) for the number of customers present at the ith facility at time t, such that $\scriptstyle \sum _{i=1}^{M}n_{i}=N$. We assume that the service time for a customer at the ith facility is given by an exponentially distributed random variable with parameter μ_i and that after completing service at the ith facility a customer will proceed to the jth facility with probability p_ij.

It follows from the Gordon–Newell theorem that the equilibrium distribution of this model is

$\mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}\prod _{i=1}^{M}\left(X_{i}\right)^{n_{i}}$

where the X_i are found by solving

$\mu _{j}X_{j}=\sum _{i=1}^{M}\mu _{i}X_{i}p_{ij}\quad {\text{ for }}j=1,\ldots ,N.$

and G(N) is a normalizing constant chosen that the above probabilities sum to 1.

Buzen's algorithm is an efficient method to compute G(N).

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:

$P(n_{i}=k)={\frac {X_{i}^{k}}{G(N)}}[G(N-k)-X_{i}G(N-k-1)]$

and the expected number of customers at facility i by

$E[n_{i}]=\sum _{k=1}^{N}X_{i}^{k}{\frac {G(N-k)}{G(N)}}.$

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

$g(n,m){\text{ for }}n=0,1,\cdots ,N{\text{ and }}m=1,\cdots ,M$.

Once the calculation ends the values we are interested in are found by

$G(n)=g(n,M){\text{ for }}n=0,1,\cdots ,N$.

The definition of g and a recursive method of calculating it are as follows

${\begin{aligned}g(n,m)&=\sum _{n_{1}+\cdots +n_{m}=n}\prod _{i=1}^{m}(X_{i})^{n_{i}}\\&=\sum _{(n_{1}+\cdots +n_{m}=n)\wedge (n_{m}=0)}^{n}\prod _{i=1}^{m}(X_{i})^{n_{i}}+\sum _{(n_{1}+\cdots +n_{m}=n)\wedge (n_{m}>0)}^{n}\prod _{i=1}^{m}(X_{i})^{n_{i}}\\&=g(n,m-1)+X_{m}g(n-1,m)\end{aligned}}$

Also

$g(n,1)=(X_{1})^{n}{\text{ for }}n=0,1,\cdots ,N$

and

$g(0,m)=1{\text{ for }}m=1,2,\cdots ,M$

This recursive relationship allows for the calculation of all G(N) up to any value of N in order O(MN) time.

Implementation

It will be assumed that the X_m 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).

References

• Jain: The Convolution Algorithm (class handout)
• Menasce: Convolution Approach to Queueing Algorithms (presentation)