Buzen's algorithm

From Wikipedia, the free encyclopedia

 This article needs additional citations for verification.
Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (July 2007)

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.[1]

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

[edit] Derivation

G(N) = g(M,N)

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 )

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

g(1,n) = f1(n)

This recursive relationship allows for the calculation of all G(N) up to any value of N in order O(MN2) 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:

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)
= fm(0)g(m − 1,n) + ymg(m,n − 1)

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.

[edit] Implementation

[edit] References

  1. ^ Buzen, Jeffrey (September 1973). "Computational algorithms for closed queueing networks with exponential servers". Communications of the ACM 16 (9). doi:10.1145/362342.362345.  [1]