Buzen's algorithm

Buzen's algorithm

Buzen's algorithm is an algorithm related to queueing theory used to calculate the normalization constant ${\displaystyle G(N)}$  for a closed Jackson network. This constant is used when analyzing these networks, alternatively Mean-value analysis can be used to avoid having to compute the normalization constant. This method was first proposed by Jeffrey P. Buzen in 1973.^[1]

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

Derivation

${\displaystyle G(N)=g(M,N)}$ 

${\displaystyle g(m,n)}$	${\displaystyle =\sum _{n_{1}+\cdot \cdot \cdot +n_{m}=n}\prod _{i=1}^{m}f_{i}(n_{i})}$
	${\displaystyle =\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})}$
	${\displaystyle =\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})}$
	${\displaystyle =\sum _{j=0}^{n}f_{m}(j)g(m-1,n-j)}$

${\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 ${\displaystyle G(N)}$  up to any value of N in order ${\displaystyle O(MN^{2})}$  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 g(m,n)}$	${\displaystyle =\sum _{j=0}^{n}f_{m}(j)g(m-1,n-j)}$
	${\displaystyle =f_{m}(0)g(m-1,n)+\sum _{j=1}^{n}f_{m}(j)g(m-1,n-j)}$
	${\displaystyle =f_{m}(0)g(m-1,n)+y_{m}\sum _{j=1}^{n-1}f_{m}(j)g(m-1,n-1-j)}$
	${\displaystyle =f_{m}(0)g(m-1,n)+y_{m}g(m,n-1)}$

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

Implementation

References

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