Buzen's algorithm: Difference between revisions

Revision as of 15:05, 16 April 2009

Revision as of 03:20, 18 April 2009

Line 13:

| doi = 10.1145/362342.362345

| pages = 527

}} [http://www-unix.ecs.umass.edu/~krishna/ece673/buzen.pdf]</ref> Once ''G'' is computed the probability distributions for the network can be found. In contrast, [[Meanmean value analysis]] is an alternative algorithm that can also be used to derive some performance measures (such as the mean queue lengths) without having to directly compute the normalization constant.

The motivation for this algorithm is efficiency: a straightforward Gordon-Newell calculation would require the enumeration of all states that the system can be in, resulting in a combinatorial explosion. Buzen's algorithm is of order ''N''<mathsup>N^2</mathsup>, making the application of the G-N theorem practical, and opening up a large class of queueing systems to accurate modeling.

In the queuing literature Buzen's algorithm is sometimes also referred to as the '''Convolution algorithm'''.

Line 21:

==Problem setup==

Consider a closed queueing network with ''M'' service facilities and ''N'' circulating customers. Let <math>n_i</math> represent the number of customers present at the ''i-''th facility, with <math>\sum_{i=1}^M n_i = N</math>. We assume that the service time for a customer at the ''i-''th facility is given by an exponentially distributed random variable with mean <math>1/\mu_i</math> and that after completing service at the ''i-''th facility a customer will proceed to the ''j-''th facility with probability ''p''<mathsub>p_{''ij}''</mathsub>.

It follows from the [[Gordon–Newell theorem]] that the equilibrium distribution of customers in the network is given by:

Line 29:

where the <math>X_i</math> are found from the equations:

:<math>\mu_j X_j = \sum_{i=1}^M \mu_i X_i p_{ij}\,</math>text{ for <math>}j=1,\cdotsldots,N.</math>

and <math>''G''(''N'')</math> is a normalizing constant such that the above probabilities sum to 1. <ref>Buzen: op.cit.</ref>

The purpose of the Buzen algorithm is to numerically compute values of ''G''.

==Marginal distributions, expected number of customers==

The general G-N distribution given above is mainly of theoretical interest. However, expressions for a number of useful performance measures can be derived from it. Buzen showed that the probability that there are exactly ''k'' customers at facility ''i'' is given by:

:<math>P(n_i = k) = \frac{X_i^k}{G(N)}[G(N-k) - X_i G(N-k-1)]</math>

and the expected number of customers at facility ''i'' by:

:<math>E[n_i] = \sum_{k=1}^N X_i^k \frac{G(N-k)}{G(N)}.</math>

Note that these expressions also involve G. It is in the evaluation of these expressions that the algorithm is useful.