Branching/queueing networks: Their introduction and near-decomposability asymptotics |
| |
Authors: | Bayer N Kogan YA |
| |
Institution: | (1) Department of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, 84105, Israel;(2) AT&T Laboratories, Holmdel, NJ 07733, USA |
| |
Abstract: | A new class of models, which combines closed queueing networks with branching processes, is introduced. The motivation comes
from MIMD computers and other service systems in which the arrival of new work is always triggered by the completion of former
work, and the amount of arriving work is variable. In the variant of branching/queueing networks studied here, a customer
branches into a random and state-independent number of offspring upon completing its service. The process regenerates whenever
the population becomes extinct. Implications for less rudimentary variants are discussed. The ergodicity of the network and
several other aspects are related to the expected total number of progeny of an associated multitype Galton-Watson process.
We give a formula for that expected number of progeny. The objects of main interest are the stationary state distribution
and the throughputs. Closed-form solutions are available for the multi-server single-node model, and for homogeneous networks
of infinite-servers. Generally, branching/queueing networks do not seem to have a product-form state distribution. We propose
a conditional product-form approximation, and show that it is approached as a limit by branching/queueing networks with a
slowly varying population size. The proof demonstrates an application of the nearly complete decomposability paradigm to an
infinite state space.
This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | closed queueing networks branching processes nearly complete decomposability |
本文献已被 SpringerLink 等数据库收录! |
|