Buzen's algorithm

In queueing theory, a discipline within the mathematical theory of probability, Buzen's algorithm is an algorithm related for calculating the normalization constant ${\displaystyle G(K)}$ in the Gordon–Newell theorem. This method was first proposed by Jeffrey P. Buzen in 1973.^[1] Mean-value analysis is an alternative algorithm that can also be used to derive performance measures without having to directly compute the normalization constant.

The motivation for this algorithm is the result of the combinatorial explosion of the number of states that the system can be in.

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 ${\displaystyle 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). doi:10.1145/362342.362345. {{cite journal}}: Unknown parameter |month= ignored (help) [1]