G-network

This article is about the mathematical model. For the wireless standard, see 802.11g.

In queueing theory, a discipline within the mathematical theory of probability, a G-network (generalized queueing network^[1] or Gelenbe network^[2]) is an open network of G-queues first introduced by Erol Gelenbe as a model for queueing systems with specific control functions, such as traffic re-routing or traffic destruction, as well as a model for neural networks.^[3] A G-queue is a network of queues with several types of novel and useful customers:

positive customers, which arrive from other queues or arrive externally as Poisson arrivals, and obey standard service and routing disciplines as in conventional network models,
negative customers, which arrive from another queue, or which arrive externally as Poisson arrivals, and remove (or 'kill') customers in a non-empty queue, representing the need to remove traffic when the network is congested, including the removal of "batches" of customers ^[4]^[5]^[6]
"triggers", which arrive from other queues or from outside the network, and which displace customers and move them to other queues

A product form solution superficially similar in form to Jackson's theorem, but which requires the solution of a system of non-linear equations for the traffic flows, exists for the stationary distribution of G-networks while the traffic equations of a G-network are in fact surprisingly non-linear, and the model does not obey partial balance. This broke previous assumptions that partial balance was a necessary condition for a product form solution. A powerful property of G-networks is that they are universal approximators for continuous and bounded functions, so that they can be used to approximate quite general input-output behaviours.^[7]

Definition

A network of m interconnected queues is a G-network if

each queue has one server, who serves at rate μ_i,
external arrivals of positive customers or of triggers or resets form Poisson processes of rate $\scriptstyle{\Lambda_i}$ for positive customers, while triggers and resets, including negative customers, form a Poisson process of rate $\scriptstyle{\lambda_i}$ ,
on completing service a customer moves from queue i to queue j as a positive customer with probability $\scriptstyle{p_{ij}^{+}}$ , as a trigger or reset with probability $\scriptstyle{p_{ij}^{-}}$ and departs the network with probability $\scriptstyle{d_i}$ ,
on arrival to a queue, a positive customer acts as usual and increases the queue length by 1,
on arrival to a queue, the negative customer reduces the length of the queue by some random number (if there is at least one positive customer present at the queue), while a trigger moves a customer probabilistically to another queue and a reset sets the state of the queue to its steady-state if the queue is empty when the reset arrives. All triggers, negative customers and resets disappear after they have taken their action, so that they are in fact "control" signals in the network,

note that normal customers leaving a queue can become triggers or resets and negative customers when they visit the next queue.

A queue in such a network is known as a G-queue.

Stationary distribution

Define the utilization at each node,

\rho_i = \frac{\lambda^+_i}{\mu_i + \lambda^-_i}

where the $\scriptstyle{\lambda^+_i, \lambda^-_i}$ for $\scriptstyle{i=1,\ldots,m}$ satisfy

$\lambda^+_i = \sum_j \rho_j \mu_j p^+_{ji} + \Lambda_i \,$

(1)

$\lambda^-_i = \sum_j \rho_j \mu_j p^-_{ji} + \lambda_i. \,$

(2)

Then writing (n₁, … ,n_m) for the state of the network (with queue length n_i at node i), if a unique non-negative solution $\scriptstyle{(\lambda^+_i,\lambda^-_i)}$ exists to the above equations (1) and (2) such that ρ_i for all i then the stationary probability distribution π exists and is given by

\pi(n_1,n_2,\ldots,n_m) = \prod_{i=1}^m (1 - \rho_i)\rho_i^{n_i}.

Proof

It is sufficient to show $\pi$ satisfies the global balance equations which, quite differently from Jackson networks are non-linear. We note that the model also allows for multiple classes.

G-networks have been used in a wide range of applications, including to represent Gene Regulatory Networks, the mix of control and payload in packet networks, neural networks, and the representation of colour images and medical images such as Magnetic Resonance Images.

Response time distribution

The response time is the length of time a customer spends in the system. The response time distribution for a single G-queue is known^[8] where customers are served using a FCFS discipline at rate μ, with positive arrivals at rate λ⁺ and negative arrivals at rate λ⁻ which kill customers from the end of the queue. The Laplace transform of response time distribution in this situation is^[8]^[9]

W^\ast(s) = \frac{\mu(1-\rho)}{\lambda^+}\frac{s+\lambda+\mu(1-\rho)-\sqrt{[s+\lambda+\mu(1-\rho)]^2-4\lambda^+\lambda^-}}{\lambda^--\lambda^+-\mu(1-\rho)-s+\sqrt{[s+\lambda+\mu(1-\rho)]^2-4\lambda^+\lambda^-}}

where λ = λ⁺ + λ⁻ and ρ = λ⁺/(λ⁻ + μ), requiring ρ < 1 for stability.

The response time for a tandem pair of G-queues (where customers who finish service at the first node immediately move to the second, then leave the network) is also known, and it is thought extensions to larger networks will be intractable.^[9]

References

↑ Gelenbe, Erol (Sep 1993). "G-Networks with Triggered Customer Movement". Journal of Applied Probability 30 (3): 742–748. doi:10.2307/3214781. JSTOR 3214781.
↑ Gelenbe, Erol; Fourneau, Jean-Michel (2002). "G-networks with resets". Performance Evaluation 49 (1/4): 179–191. doi:10.1016/S0166-5316(02)00127-X.
↑ Harrison, Peter (2009). "Turning Back Time – What Impact on Performance?". The Computer Journal 53 (6): 860. doi:10.1093/comjnl/bxp021.
↑ Gelenbe, Erol (1991). "Product-form queueing networks with negative and positive customers". Journal of Applied Probability 28 (3): 656–663. doi:10.2307/3214499. JSTOR 3214499.
↑ Gelenbe, Erol (1993). "G-Networks with signals and batch removal". Probability in the Engineering and Informational Sciences 7: 335–342. doi:10.1017/s0269964800002953.
↑ Artalejo, J.R. (Oct 2000). "G-networks: A versatile approach for work removal in queueing networks". European Journal of Operational Research 126 (2): 233–249. doi:10.1016/S0377-2217(99)00476-2.
↑ Gelenbe, Erol; Mao, Zhi-Hong; Da Li, Yan (1999). "Function approximation with spiked random networks". IEEE Transactions on Neural Networks 10 (1): 3–9. doi:10.1109/72.737488.
1 2 Harrison, P. G.; Pitel, E. (1993). "Sojourn Times in Single-Server Queues with Negative Customers". Journal of Applied Probability 30 (4): 943–963. doi:10.2307/3214524. JSTOR 3214524.
1 2 Harrison, Peter G. Response times in G-nets. 13th International Symposium on Computer and Information Sciences (ISCIS 1998). pp. 9–16. ISBN 9051994052.

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

Stochastic processes

Discrete time	Bernoulli process Branching process Chinese restaurant process Galton–Watson process Independent and identically distributed random variables Markov chain Moran process Random walk Loop-erased Self-avoiding

Continuous time	Bessel process Birth–death process Brownian motion Bridge Excursion Fractional Geometric Meander Cauchy process Contact process Continuous-time random walk Cox process Diffusion process Empirical process Feller process Fleming–Viot process Gamma process Hunt process Interacting particle systems Itô diffusion Itô process Jump diffusion Jump process Lévy process Local time Markov additive process McKean–Vlasov process Ornstein–Uhlenbeck process Poisson process Compound Non-homogeneous Point process Schramm–Loewner evolution Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process Wiener process Wiener sausage

Both	Branching process Gaussian process Hidden Markov model (HMM) Markov process Martingale Differences Local Sub- Super- Random dynamical system Regenerative process Renewal process White noise

Fields and other	Dirichlet process Gaussian random field Gibbs measure Hopfield model Ising model Potts model Boolean network Markov random field Percolation Pitman–Yor process Point process Cox Poisson Random field Random graph

Time series models	Autoregressive conditional heteroskedasticity (ARCH) model Autoregressive integrated moving average (ARIMA) model Autoregressive (AR) model Autoregressive–moving-average (ARMA) model Generalized autoregressive conditional heteroskedasticity (GARCH) model Moving-average (MA) model

Financial models	Black–Derman–Toy Black–Karasinski Black–Scholes Chen Constant elasticity of variance (CEV) Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie

Actuarial models	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson

Queueing models	Bulk Fluid Generalized queueing network M/G/1 M/M/1 M/M/c

Properties	Càdlàg paths Continuous Continuous paths Ergodic Exchangeable Feller-continuous Gauss–Markov Markov Mixing Piecewise deterministic Predictable Progressively measurable Self-similar Stationary Time-reversible

Limit theorems	Central limit theorem Donsker's theorem Doob's martingale convergence theorems Ergodic theorem Fisher–Tippett–Gnedenko theorem Large deviation principle Law of large numbers (weak/strong) Law of the iterated logarithm Maximal ergodic theorem Sanov's theorem

Inequalities	Burkholder–Davis–Gundy Doob's martingale Kunita–Watanabe

Tools	Cameron–Martin formula Convergence of random variables Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Kolmogorov continuity theorem Kolmogorov extension theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract

Disciplines	Actuarial mathematics Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Statistics Stochastic analysis Time series analysis Machine learning

List of topics Category

This article is issued from Wikipedia - version of the Thursday, September 03, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.