G-networks

G-networks are a class of probabilistic models that represent "customers" travelling around a set of N "service stations" or queues. Such "queueing networks" are commonly used in the design and optimisation of computer systems, packet networks such as the Internet, other communication networks, factory production schedules and job-shops, service organisations, and transportations systems and road traffic. These models may be described either in continuous time, or in discrete time. The state of a G-network is a vector representing the number of customers in each of the queues. Customers line up for service in a queue and then may either move to another queue, or they may depart the network. Customers may also arrive into the network from some external source and join one of the queues, and then continue to behave like the other customers. The novelty of G-networks lies in the fact that when a customer leaves a queue to join another one, it may become a "negative customer" which destroys one or more customers at the next queue it visits. Negative customers themselves disappear after they have affected the state of the queue they visit. A customer leaving a queue may also enter another queue as a "trigger" whose role will be to displace a customer from the queue that it is entering, and then move it to another queue. Again, a trigger disappears after having carried out its action. Customers can also be "resets" which fill up by one or more places the queue that they enter, or reset the queue's length to its steady-state value (if that value exists). G-networks offer a means to predict the behaviour of queueing systems in which certain specific customers exert control functions: negative customers eliminate work or traffic, while triggers move work or traffic from one queue to another. These models are described in terms of a probability distribution for the system state at a given time, and this probability distribution has been shown to satisfy a system of "Chapman-Kolmogorov" or "master" equations. The term "master equations" relates to the same term as it is used in theoretical chemistry to describe chemical reactions. When external arrivals to a G-network follow a Poisson process, and service times in the queues are independent and exponentially distributed random variables, certain quite general cases of G-networks, which may also include a way to distinguish between different "customer classes" using different probabilities of moving from one queue to another, have been shown to have "product form". The steady-state solution of these equations for G-networks, which yield the joint probability distribution for the number of customers in each queue of the network, have thus been shown to be equal to the product of the marginal probability distributions of the number of customers in each individual queue in the network. This is yet another example of the so called "product form" result which considerably simplifies the expression for the steady-state probabilities and offers an intuitive form for the solution in terms of the arrival rates of positive and negative customers, and triggers, to each queue. G-networks are related from a mathematical perspective to the random neural network.

ources

* E. Gelenbe. Product-form queueing networks with negative and positive customers, J. Applied Probability 28: 656-663, 1991.

* E. Gelenbe, R. Schassberger. Stability of product form G-networks. Probability in the Engineering and Informational Sciences, 6: 271-276, 1992.

* E. Gelenbe. G-Networks with triggered customer movement. Journal of Applied Probability, 30 (3): 742-748, 1993.

* Jean-Michel Fourneau, Erol Gelenbe and Rina Suros. G-Networks with multiple classes of negative and positive customers. Theoretical Computer Science 155(1): 141-156, 1996.

* J.R. Artalejo. G-networks: A versatile approach for work removal in queueing networks. European Journal of Operational Research, 126 (2): 233-249, October 2000.

* Erol Gelenbe and Jean-Michel Fourneau. G-networks with resets. Performance Evaluation 49(1/4): 179-191, 2002.

* Peter G. Harrison. Compositional reversed Markov processes, with applications to G-networks. Performance Evaluation 57(3): 379-408, 2004.

* Jean-Michel Fourneau and Franck Quessette. Computing the steady-state distribution of G-networks with synchronized partial flushing. International Symposium on Computer and Information Sciences, Springer Lecture Notes LNCS: 887-896, 2006.