Gordon–Newell theorem

In queueing theory, a discipline within the mathematical theory of probability, the Gordon–Newell theorem is an extension of Jackson's theorem from open queueing networks to closed queueing networks of exponential servers where customers cannot leave the network.^[1] Jackson's theorem cannot be applied to closed networks because the queue length at a node in the closed network is limited by the population of the network. The Gordon–Newell theorem calculates the open network solution and then eliminates the infeasible states by renormalizing the probabilities. Calculation of the normalizing constant makes the treatment more awkward as the whole state space must be enumerated. Buzen's algorithm or mean value analysis can be used to calculate the normalizing constant more efficiently.^[2]

Definition of a Gordon–Newell network

A network of m interconnected queues is known as a Gordon–Newell network^[3] or closed Jackson network^[4] if it meets the following conditions:

the network is closed (no customers can enter or leave the network),
all service times are exponentially distributed and the service discipline at all queues is FCFS,
a customer completing service at queue i will move to queue j with probability $P_{ij}$ , with the $P_{ij}$ such that $\scriptstyle {\sum _{j=1}^{m}P_{ij}=1}$ ,
the utilization of all of the queues is less than one.

Theorem

In a closed Gordon–Newell network of m queues, with a total population of K individuals, write $\scriptstyle {(k_{1},k_{2},\ldots ,k_{m})}$ (where k_i is the length of queue i) for the state of the network and S(K, m) for the state space

S(K,m)=\left\{\mathbf {k} \in \mathbb {N} ^{m}{\text{ such that }}\sum _{i=1}^{m}k_{i}=K\right\}.

Then the equilibrium state probability distribution exists and is given by

\pi (k_{1},k_{2},\ldots ,k_{m})={\frac {1}{G(K)}}\prod _{i=1}^{m}\left({\frac {e_{i}}{\mu _{i}}}\right)^{k_{i}}

where service times at queue i are exponentially distributed with parameter μ_i. The normalizing constant G(K) is given by

G(K)=\sum _{\mathbf {k} \in S(K,m)}\prod _{i=1}^{m}\left({\frac {e_{i}}{\mu _{i}}}\right)^{k_{i}},

and e_i is the visit ratio, calculated by solving the simultaneous equations

e_{i}=\sum _{j=1}^{m}e_{j}p_{ji}{\text{ for }}1\leq i\leq m.

References

↑ Gordon, W. J.; Newell, G. F. (1967). "Closed Queuing Systems with Exponential Servers". Operations Research. 15 (2): 254. JSTOR 168557. doi:10.1287/opre.15.2.254.
↑ Buzen, J. P. (1973). "Computational algorithms for closed queueing networks with exponential servers" (PDF). Communications of the ACM. 16 (9): 527. doi:10.1145/362342.362345.
↑ Daduna, H. (1982). "Passage Times for Overtake-Free Paths in Gordon-Newell Networks". Advances in Applied Probability. 14 (3): 672–686. doi:10.2307/1426680.
↑ Gong, Q.; Lai, K. K.; Wang, S. (2008). "Supply chain networks: Closed Jackson network models and properties". International Journal of Production Economics. 113 (2): 567. doi:10.1016/j.ijpe.2007.10.013.

Queueing theory
Single queueing nodes	D/M/1 queue M/D/1 queue M/D/c queue M/M/1 queue Burke's theorem M/M/c queue M/M/∞ queue M/G/1 queue Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue
Arrival processes	Poisson process Markovian arrival process Rational arrival process
Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network
Service policies	FIFO LIFO Processor sharing Round-robin Shortest job first Shortest remaining time
Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method
Limit theorems	Fluid limit Mean field theory Heavy traffic approximation Reflected Brownian motion
Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue
Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering
Category

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Gordon–Newell theorem

Definition of a Gordon–Newell network

Theorem

See also

References