AESOP home


A resurgence in product-forms

Peter G. Harrison

Book Review
The Computer Journal
Volume 51
Issue 6
March, 2008
Oxford Journals
DOI 10.1093/comjnl/bxn003

Interest in the stochastic behaviour of queueing networks began in the 1960s with the work by Jackson, Gordon, Newell and others. These authors derived the so-called product-form solutions for the equilibrium probabilities of the joint state in such a continuous time Markov chain (CTMC). From the preceding lecture, of course, these networks are special cases of G-networks, where there are no negative customers, triggers, signals, etc. After a number of generalizations of Jackson networks in the 1970s and 1980s, it was thought by many that a product-form for a stochastic network would only exist if that network satisfied a condition called partial or local balance. Essentially, this specifies a specific way by which the global balance equations of probability fluxes into, and out of, a given state (the steady-state theorem for CTMCs) are constructed from balanced subsets of these equations, each subset relating to a component of the network. Gelenbe's G-network model, and the related RNN model, with its non-linear traffic equations in particular, provided counter-examples to this widely held view. In turn, this sparked a resurgence of interest in the quest for product-forms, which continues today.

A recent result in the area of stochastic process algebra is the reversed compound agent theorem (RCAT), which derives the reversed process of certain cooperations between two CTMCs at equilibrium. Moreover, the result is 'compositional' in that this reversed process is simply the corresponding cooperation of the reversed processes of the individual components. From this, the joint state probabilities follow as a product-form. In this RCAT-based approach to finding product-forms, G-networks are no different from Jackson networks or the later BCMP networks. This is because interactions between nodes are defined in terms of synchronizations between transition types (e.g. a departure with an arrival) rather than explicit traffic fows: there are now co-operations between two types of departure transitions at different queues (for negative customers), as well as between departure transitions and arrival transitions, as in conventional queueing networks. This approach has led to many new variants of G-networks, with resets, batches and instantaneous chains of negative triggers that can empty parts of a network. It has also derived some product-forms unrelated to any form of queueing networks, for example in the performance of distributed software systems with critical sections. It has provided a sound basis for recent work on unifying practical implementations of performance tools, for example in G-PMIF, a performance model interchange format schema.


Discussant Contribution for the Computer Journal Lecture by Erol Gelenbe, "The Random Neural Network: the Model, its Applications, and Extensions in Biology and Queuing Theory", 1st October 2007

Information from