Dobrushin's approach to queueing network theory (Q675248): Difference between revisions

R. L. Dobrushin (1929-1995) made considerable contribution -- to queueing network theory. The paper is mainly a survey of Dobrushin's works on queueing theory and related topics, and it also incorporates some basic notions and results of the modern queueing theory. In particular, some unexpected problems on stability of multiclass networks (detected recently by A. Rybko and A. Stolyar, M. Bramson, and others) are discussed in detail. The main attention is paid to the Poisson networks and so-called Poissonian conjecture (which has been proposed and partially established by Dobrushin): approximation of a general network by a Poisson one when the number of nodes in the network increases infinitely. Some particular network structures are studied in more detail (for example, a star-shaped network, the network with parallel execution and synchronization on arrival). Moreover, the authors discuss in detail the following Dobrushin's program of the studying of the networks: 1) to establish the most weak stability (ergodic) network conditions which are based on the balance equations and guarantee the existence (and uniqueness) of a stationary regime; 2) to extend maximally the class of the networks where the product-form of the limit queue-size distribution stays valid (exactly or approximately); 3) to establish the assumptions when the network output process preserves the properties of the arrival one (invariance problem).