Buzen's algorithm

In queueing theory, a discipline within the mathematical theory of probability, Buzen's algorithm is an algorithm for calculating the normalization constant G(K) in the Gordon–Newell theorem. This method was first proposed by Jeffrey P. Buzen in 1973.^[1] Once G is computed the probability distributions for the network can be found. In contrast, Mean-value analysis 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 ${\displaystyle N^{2}}$, 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 ${\displaystyle n_{i}}$  represent the number of customers present at the i-th facility, with ${\displaystyle \sum _{i=1}^{M}n_{i}=N}$ . We assume that the service time for a customer at the i-th facility is given by an exponentially distributed random variable with mean ${\displaystyle 1/\mu _{i}}$  and that after completing service at the i-th facility a customer will proceed to the j-th facility with probability ${\displaystyle p_{ij}}$ .

It follows from the Gordon-Newell theorem that the equilibrium distribution of customers in the network is given by:

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

where the ${\displaystyle X_{i}}$  are found from the equations:

${\displaystyle \mu _{j}X_{j}=\sum _{i=1}^{M}\mu _{i}X_{i}p_{ij}\,}$  for ${\displaystyle j=1,\cdots ,N}$ 

and ${\displaystyle G(N)}$  is a normalizing constant such that the above probabilities sum to 1. ^[2]

The purpose of the Buzen algorithm is to numerically compute values of G.

Derivation

G(N) = g(M, N)

${\displaystyle {\begin{aligned}g(m,n)&=\sum _{n_{1}+\cdot \cdot \cdot +n_{m}=n}\prod _{i=1}^{m}f_{i}(n_{i})\\&=\sum _{j=0}^{n}\sum _{n_{1}+\cdot \cdot \cdot +n_{m-1}=n-j,n_{m}=j}\prod _{i=1}^{m}f_{i}(n_{i})\\&=\sum _{j=0}^{n}f_{m}(j)\sum _{n_{1}+\cdot \cdot \cdot +n_{m-1}=n-j}\prod _{i=1}^{m-1}f_{i}(n_{i})\\&=\sum _{j=0}^{n}f_{m}(j)g(m-1,n-j)\end{aligned}}}$ 

${\displaystyle g(m,0)=1\,}$ 

to avoid affecting the product.

${\displaystyle g(1,n)=f_{1}(n)\,}$ 

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

There is a more efficient algorithm for finding G(N') for some network. If it is assumed that ${\displaystyle f_{i>1}(n)=c_{i}y_{i}^{n}}$ , then the recursive relationship can be simplified as follows:

${\displaystyle {\begin{aligned}g(m,n)&=\sum _{j=0}^{n}f_{m}(j)g(m-1,n-j)\\&=f_{m}(0)g(m-1,n)+\sum _{j=1}^{n}f_{m}(j)g(m-1,n-j)\\&=f_{m}(0)g(m-1,n)+y_{m}\sum _{j=1}^{n-1}f_{m}(j)g(m-1,n-1-j)\\&=f_{m}(0)g(m-1,n)+y_{m}g(m,n-1)\end{aligned}}}$ 

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

Implementation

References

1. Buzen, Jeffrey (1973). "Computational algorithms for closed queueing networks with exponential servers". Communications of the ACM. 16 (9): 527. doi:10.1145/362342.362345. {{cite journal}}: Unknown parameter |month= ignored (help) [1]
2. Buzen: op.cit.

• Jain: The Convolution Algorithm (class handout)

• Menasce: Convolution Approach to Queueing Algorithms (presentation)