Computing Publications

Publications Home » Product-forms in batch networks: ...

Product-forms in batch networks: approximation and asymptotics

Peter G. Harrison, Richard Hayden, William J. Knottenbelt

Conference or Workshop Paper
31st International Symposium on Computer Performance, Modeling, Measurements and Evaluation (IFIP PERFORMANCE)

It is shown that a Markovian queue, with bulk arrivals and departures having any probability mass functions for their batch sizes, has geometrically distributed queue length at equilibrium (when this exists) provided there is an additional special bulk arrival stream, with particular rate and batch size distribution, when the server is idle. It is shown that the time-averaged input rate of the special arrivals tends to zero as the queue becomes saturated, and a heavy-traffic limit for the queue without special arrivals is derived by martingale methods. This is shown to give the same asymptotic queue length probabilities as the geometric model. The product form is then extended to tandem networks of batch queues using the reversed compound agent theorem (RCAT). In order to obtain the product form in this case, it is required that, in addition to special arrival streams, so-called `partial batches' are discarded immediately from the network when there are not enough customers in the queue to fill an entire departing batch. Somewhat surprisingly it turns out that, in heavy traffic, the product-form network does not always agree with the regulated Brownian motion (RBM) diffusion limit for the standard network without special arrivals and where partial batches are not discarded, but forwarded to the next node. Indeed, we show that the two models agree in heavy traffic if and only if the skew-symmetry condition for the RBM to have a product form is satisfied. When the condition does hold, our theoretical and numerical results thus validate the use of the product-form batch networks as moderate-traffic approximations to the analogous standard queueing network model without special arrivals and where partial batches may be forwarded to the next node instead of being lost. In the case that the condition does not hold, we obtain a new product-form stationary distribution for the associated non-RBM diffusion limit.

PDF of full publication (536 kilobytes)
(need help viewing PDF files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.