Buzen's algorithm

From Wikipedia, the free encyclopedia

You have new messages (last change).
Some information in this article or section is not attributed to sources and may not be reliable.
Please check for inaccuracies, and modify and cite sources as needed.

Contents

[edit] 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.[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).  [1]
Retrieved from "http://en.wikipedia.org../../../b/u/z/Buzen%27s_algorithm.html"