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.

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]

• Jain: The Convolution Algorithm (class handout)

• Menasce: Convolution Approach to Queueing Algorithms (presentation)