en>Mathmon at 23:05, 12 December 2013

2013-12-12T23:05:41Z

New page

In [[queueing theory]], a discipline within the mathematical [[probability theory|theory of probability]], '''Buzen's algorithm''' (or '''convolution algorithm''') is an algorithm for calculating the [[normalization constant]] G(''N'') in the [[Gordon–Newell theorem]]. This method was first proposed by [[Jeffrey P. Buzen]] in 1973.<ref name="buzen-1973">{{cite doi | 10.1145/362342.362345}}</ref> Computing G(''N'') is required to compute the stationary [[probability distribution]] of a closed queueing network.<ref name="gn">{{cite doi|10.1287/opre.15.2.254}}</ref>

Performing a naïve computation of the normalising constant requires enumeration of all states. For a system with ''N'' jobs and ''M'' states there are <math>\tbinom{N+M-1}{M-1}</math> states. Buzen's algorithm "computes G(1), G(2), ..., G(''N'') using a total of ''NM'' multiplications and ''NM'' additions." This is a significant improvement and allows for computations to be performed with much larger networks.<ref name="buzen-1973" />

==Problem setup==

Consider a closed queueing network with ''M'' service facilities and ''N'' circulating customers. Write ''n''''i''(''t'') for the number of customers present at the ''i''th facility at time ''t'', such that <math>\scriptstyle \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 parameter ''μ''''i'' and that after completing service at the ''i''th facility a customer will proceed to the ''j''th facility with probability ''p''''ij''.<ref name="gn" />

It follows from the [[Gordon–Newell theorem]] that the equilibrium distribution of this model is
::<math>\mathbb P(n_1,n_2,\cdots,n_M) = \frac{1}{\text{G}(N)}\prod_{i=1}^M \left( X_i \right)^{n_i}</math>
where the ''X''''i'' are found by solving
::<math>\mu_j X_j = \sum_{i=1}^M \mu_i X_i p_{ij}\quad\text{ for }j=1,\ldots,N.</math>
and ''G''(''N'') is a normalizing constant chosen that the above probabilities sum to 1.<ref name="buzen-1973" />

Buzen's algorithm is an efficient method to compute G(''N'').<ref name="buzen-1973" />

==Algorithm description==

Write g(''N'',''M'') for the normalising constant of a closed queueing network with ''N'' circulating customers and ''M'' service stations. The algorithm starts by noting solving the above relations for the ''X''''i'' and then setting starting conditions<ref name="buzen-1973" />
::<math>g(0, m) = 1 \text{ for }m=1,2,\cdots,M</math>
::<math>g(n, 1) = (X_1)^n \text{ for }n=0,1,\cdots,N.</math>
The recurrence relation<ref name="buzen-1973" />
::<math>g(n, m) = g(n,m-1)+X_m g(n-1,m).</math>
is used to compute a grid of values. The sought for value G(''N'') = g(''N'',''M'').<ref name="buzen-1973" />

==Marginal distributions, expected number of customers==

The coefficients g(''n'',''m''), computed using Buzen's algorithm, can also be used to compute [[marginal distribution]]s and [[expected value|expected]] number of customers at each node.
::<math>\mathbb P(n_i = k) = \frac{X_i^k}{G(N)}[G(N-k) - X_i G(N-k-1)]\quad\text{ for }k=0,1,\ldots,N-1,</math>
::<math>\mathbb P(n_i = N) = \frac{X_i^N}{G(N)}[G(0)].</math>
the expected number of customers at facility ''i'' by
::<math>\mathbb E(n_i) = \sum_{k=1}^N X_i^k \frac{G(N-k)}{G(N)}.</math>

==Implementation==
It will be assumed that the ''Xm'' have been computed by solving the relevant equations and are available as an input to our routine. Although ''g'' is in principle a two dimensional matrix, it can be computed in a column by column fashion starting from the leftmost column. The routine uses a single column vector ''C'' to represent the current column of ''g''.

<source lang="pascal">
C[0] := 1
for n := 1 step 1 until N do
C[n] := 0;

for m := 1 step 1 until M do
for n := 1 step 1 until N do
C[n] := C[n] + X[m]*C[n-1];
</source>

At completion, ''C'' contains the desired values ''G(0), G(1)'' to ''G(N)''. <ref name="buzen-1973" />

==References==

{{reflist}}

*[http://www.cs.wustl.edu/~jain/cse567-08/ftp/k_35ca.pdf Jain: The Convolution Algorithm (class handout)]
*[http://cs.gmu.edu/~menasce/cs672/slides/CS672-convolution.pdf Menasce: Convolution Approach to Queueing Algorithms (presentation)]

{{Queueing theory}}

[[Category:Stochastic processes]]
[[Category:Queueing theory]]
[[Category:Statistical algorithms]]

PLS (complexity) - Revision history

en>Mathmon at 23:05, 12 December 2013