Buzen's algorithm

Buzen's algorithm is an algorithm related to queueing theory used to calculate the normalization constant $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.cite journal
first = Jeffrey
last = Buzen
authorlink = Jeffrey L. Buzen
year = 1973
month = September
title = Computational algorithms for closed queueing networks with exponential servers
journal = Communications of the ACM
volume = 16
issue = 9
doi = 10.1145/362342.362345 [http://www-unix.ecs.umass.edu/~krishna/ece673/buzen.pdf] ]

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)$

$g(m,\; 0)\; =\; 1$ to avoid affecting the product.

$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^2)$ time.

There is a more efficient algorithm for finding $G(N)$ for some network. If it is assumed that $f\_\{i>1\}(\; n\; )\; =\; c\_iy\_i^n$, then the recursive relationship can be simplified as follows:

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