State-dependent Coupling of Quasireversible Nodes

The seminal paper of Jackson began a chain of research on queueing networks with product-form stationary distributions which continues strongly to this day. Hard on the heels of the early results on queueing networks followed a series of papers which discussed the relationship between product-form stationary distributions and the quasireversibility of network nodes. More recently, the definition of quasireversibility and the coupling mechanism between nodes have been extended so that they apply to some of the later product-form queueing networks incorporating negative customers, signals, and batch movements.In parallel with this research, it has been shown that some special queueing networks can have arrival and service parameters which depend upon the network state, rather than just the node state, and still retain a generalised product-form stationary distribution.In this paper we begin by offering an alternative proof of a product-form result of Chao and Miyazawa and then build on this proof by postulating a state-dependent coupling mechanism for a quasireversible network. Our main theorem is that the resultant network has a generalised product form stationary distribution. We conclude the paper with some examples.     

Deadlock free buffer allocation in closed queueing networks

Blocking queueing networks are of much interest in performance analysis due to their realistic modeling capability. One important feature of such networks is that they may have deadlocks which can occur if the node capacities are not sufficiently large. A necessary and sufficient condition for the node capacities is presented such that the network is deadlock free. An algorithm is given for buffer allocation in blocking queueing networks such that no deadlocks will occur assuming that the network has the special structure called cacti-graph. Additional algorithm which takes linear time in the number of nodes, is presented to find cycles in cacti networks.Akyildiz's work was supported in part by School of Information and Computer Science, ICS, of Georgia Tech and by the Air Force Office of the Scientific Research (AFOSR) under Grant AFOSR-88-0028.     

Queueing networks with dependent nodes and concurrent movements

Classical queueing network processes are useful for modeling the movement of discrete units in a network in which the nodes operate independently, the routing of units is independent of the congestion, only one unit moves at a time and its equilibrium distribution is a well-understood product form. Actual networks, however, typically have dependent nodes and concurrent movement of units. Imagine the dependencies associated with the network movements of telephone calls, manufacturing material, computer data packets, messages in a parallel-processing simulation, etc. A second generation of queueing network processes is beginning to evolve for modeling such “intelligent” networks with dependent nodes and concurrent movements. This paper describes the following fundamental processes that have been developed in this regard:

? A basic queueing network process for dependent nodes and single-unit movements. Examples include the classical Jackson, BCMP, Kelly and Kelly-Whittle networks and networks with interacting subpopulations.

? Reversible queueing network processes for dependent nodes and concurrent movements. An example is a multivariate, compound birth-death process.

? Miscellaneous partially balanced queueing networks. Examples include extensions of the basic network processes and weakly coupled and quasi-reversible networks.

     

Factorized time-dependent distributions for certain multiclass queueing networks and an application to?enzymatic processing networks

Motivated by applications in biological systems, we show for certain multiclass queueing networks that time-dependent distributions for the multiclass queue-lengths can have a factorized form which reduces the problem of computing such distributions to a similar problem for related single-class queueing networks. We give an example of the application of this result to an enzymatic processing network.     

Structure-reversibility and departure functions of queueing networks with batch movements and state dependent routing

We consider characterizations of departure functions in Markovian queueing networks with batch movements and state-dependent routing in discrete-time and in continuous-time. For this purpose, the notion of structure-reversibility is introduced, which means that the time-reversed dynamics of a queueing network corresponds with the same type of queueing network. The notion is useful to derive a traffic equation. We also introduce a multi-source model, which means that there are different types of outside sources, to capture a wider range of applications. Characterizations of the departure functions are obtained for any routing mechanism of customers satisfying a recurrent condition. These results give a unified view to queueing network models with linear traffic equations. Furthermore, they enable us to consider new examples as well as show limited usages of this kind of queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Measurement and optimization of robust stability of multiclass queueing networks: Applications in dynamic supply chains

Multiclass queueing networks are an essential tool for modeling and analyzing complex supply chains. Roughly speaking, stability of these networks implies that the total number of customers/jobs in the network remains bounded over time. In this context robustness characterizes the ability of a multiclass queueing network to remain stable, if the expected values of the interarrival and service times distributions are subject to uncertain shifts. A powerful starting point for the stability analysis of multiclass queueing networks is the associated fluid network. Based on the fluid network analysis we present a measure to quantify the robustness, which is indicated by a single number. This number will be called the stability radius. It represents the magnitude of the smallest shift of the expected value of the interarrival and/or service times distributions so that the associated fluid network looses the property of stability. The stability radius is a worst case measure and is a conceptual adaptation from the dynamical systems literature. Moreover, we provide a characterization of the shifts that destabilize the network. Based on these results, we formulate a mathematical program that minimizes the required network capacity, while ensuring a desired level of robustness towards shifts of the expected values of the interarrival times distributions. This approach provides a new view on long-term robust production capacity allocation in supply chains. The capabilities of our method are demonstrated using a real world supply chain.     

Mean-value analysis for a class of Petri nets and batch-movement queueing networks with product-form equilibrium distributions

A number of recent papers have shown that there are classes of queueing networks, with batches of customers served and routed through the network, which have generalized product form equilibrium distributions. This extends to some Petri nets. In this paper, we indicate how a class of these is amenable to a mean-value analysis similar to that used for single-movement networks. To bring out the simplicity of the underlying ideas, we do this by working a simple example rather than presenting the development in its generality.     

On the Full Idle Time in Multiphase Queueing Systems

The modern queueing theory is a powerful tool for a quantitative and qualitative analysis of communication systems, computer networks, transportation systems, and many other technical systems. The paper is designated to the analysis of queueing systems arising in the network theory and communications theory (such as the so-called multiphase queueing systems, tandem queues, or series of queueing systems). We present heavy traffic limit theorems for the full idle time in multiphase queueing systems. We prove functional limit theorems for values of the full idle time of a queueing system, which is its important probability characteristic. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 3, pp. 367–386, July–September, 2005.     

Perturbation analysis and optimization of queueing networks

A new time-domain-based approach is developed in this paper for the perturbation analysis of queueing networks. We show that, by observing a single sample path realization of the network trajectory, we can derive sensitivity information of the throughput of the system with respect to various parameters. This information can then be used for the optimization of queueing networks. Numerous experiments as well as analytical results demonstrating the validity of this new approach are given and discussed.     

A sufficient condition and a necessary condition for the diffusion approximations of multiclass queueing networks under priority service disciplines

We establish a sufficient condition for the existence of the (conventional) diffusion approximation for multiclass queueing networks under priority service disciplines. The sufficient condition relates to a sufficient condition for the weak stability of the fluid networks that correspond to the queueing networks under consideration. In addition, we establish a necessary condition for the network to have a continuous diffusion limit; the necessary condition is to require a reflection matrix (of dimension equal to the number of stations) to be completely-S. When applied to some examples, including generalized Jackson networks, single station multiclass queues, first-buffer-first-served re-entrant lines, a two-station Dai–Wang network and a three-station Dumas network, the sufficient condition coincides with the necessary condition.     

Branching/queueing networks: Their introduction and near-decomposability asymptotics

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.     

Near optimal control of queueing networks over a finite time horizon

We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we solve as a separated continuous linear program. The optimal fluid solution partitions the time horizon to intervals in which constant fluid flow rates are maintained. We then use a policy by which the queueing network tracks the fluid solution. To that end we model the deviations between the queuing and the fluid network in each of the intervals by a multi-class queueing network with some infinite virtual queues. We then keep these deviations stable by an adaptation of a maximum pressure policy. We show that this method is asymptotically optimal when the number of items that is processed and the processing speed increase. We illustrate these results through a simple example of a three stage re-entrant line. Research supported in part by Israel Science Foundation Grant 249/02 and 454/05 and by European Network of Excellence Euro-NGI.     

The departure process of discrete-time queueing systems with Markovian type inputs

This paper proposes a unified matrix-analytic approach to characterize the output processes of general discrete-time lossless/lossy queueing systems in which time is synchronized/slotted into fixed length intervals called slots. The arrival process can be continuous- or discrete-time Markovian processes. It can be either renewal or non-renewal. The service of a customer commences at the beginning of a slot, consumes a random number of slots, and completes at the end of a later slot. The service times are independent and follow a common and general distribution. Systems with and without server vacations are both treated in this paper. These queueing systems have potential applications in asynchronous transfer mode (ATM) networks, packet radio networks, etc. Since the output process of a node in a queueing network becomes an input process to some node at the next stage, the results of this paper can be used to facilitate end-to-end performance analysis which has attracted more and more attention in the literature. This revised version was published online in June 2006 with corrections to the Cover Date.     

Higher order approximations for tandem queueing networks

In this paper a higher order approximation for single server queues and tandem queueing networks is proposed and studied. Different from the most popular two-moment based approximations in the literature, the higher order approximation uses the higher moments of the interarrival and service distributions in evaluating the performance measures for queueing networks. It is built upon the MacLaurin series analysis, a method that is recently developed to analyze single-node queues, along with the idea of decomposition using higher orders of the moments matched to a distribution. The approximation is computationally flexible in that it can use as many moments of the interarrival and service distributions as desired and produce the corresponding moments for the waiting and interdeparture times. Therefore it can also be used to study several interesting issues that arise in the study of queueing network approximations, such as the effects of higher moments and correlations. Numerical results for single server queues and tandem queueing networks show that this approximation is better than the two-moment based approximations in most cases.     

Markov network processes with product form stationary distributions

This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing networks and networks with interacting components or populations. The focus is on determining when these processes have product form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form. We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals and departures. The study ends by describing how the results extend to networks with multi-class transitions. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the law of the iterated logarithm in open queueing networks

An open queueing network model in heavy traffic is developed. Such models are mathematical models of computer networks in heavy traffic. Laws of the iterated logarithm for the virtual waiting time of the customer in open queueing networks and homogeneous computer networks are proved.     

MULTIQ: A Queueing Model for FMSs with Several Pallet Types

Analytical modelling of the work flow through flexible manufacturing systems (FMSs), based on closed queueing network models, has been successfully applied to the early stages of design and analysis of FMSs. This paper describes the advantages of using multiple job-class closed queueing networks for modelling realistic situations occurring in FMSs. The general modelling of FMSs by closed queueing networks is first reviewed. The way Solberg's CAN-Q—a single job-class queueing-based package—deals with several part types is clarified. A new model called MULTIQ, allowing multiple pallet types, each of which is used by several part types, is proposed. Results are derived using the data from an existing FMS. The use of the MULTIQ model for optimization purposes is suggested by some examples.     

Non-product form equilibrium probabilities in a class of two-station closed reentrant queueing networks

While many single station queues possess explicit forms for their equilibrium probabilities, queueing networks are more problematic. Outside of the class of product form networks (e.g., Jackson, Kelly, and BCMP networks), one must resort to bounds, simulation, asymptotic studies or approximations. By focusing on a class of two-station closed reentrant queueing networks under the last buffer first served (LBFS) policy, we show that non-product form equilibrium probabilities can be obtained. When the number of customer classes in the network is five or fewer, explicit solutions can be obtained. Otherwise, we require the roots of a characteristic polynomial and a matrix inversion that depend only on the network topology. The approach relies on two key points. First, under LBFS, the state space can be reduced to four dimensions independent of the number of buffers in the system. Second, there is a sense of spatial causality in the global balance equations that can then be exploited. To our knowledge, these two-station closed reentrant queueing networks under LBFS represent the first class of queueing networks for which explicit non-product form equilibrium probabilities can be constructed (for five customer classes or less), the generic form of the equilibrium probabilities can be deduced and matrix analytic approaches can be applied. As discussed via example, there may be other networks for which related observations can be exploited.     

Stability of Fluid Networks with Proportional Routing

In this paper we investigate the stability of a class of two-station multiclass fluid networks with proportional routing. We obtain explicit necessary and sufficient conditions for the global stability of such networks. By virtue of a stability theorem of Dai [14], these results also give sufficient conditions for the stability of a class of related multiclass queueing networks. Our study extends the results of Dai and VandeVate [19], who provided a similar analysis for fluid models without proportional routing, which arise from queueing networks with deterministic routing. The models we investigate include fluid models which arise from a large class of two-station queueing networks with probabilistic routing. The stability conditions derived turn out to have an appealing intuitive interpretation in terms of virtual stations and push-starts which were introduced in earlier work on multiclass networks.