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.     

Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints

We propose a new technique for upper and lower bounding of the throughput and blocking probabilities in queueing networks with buffer capacity constraints, i.e., some buffers in the network have finite capacity. By studying the evolution of multinomials of the state of the system in its assumed steady state, we obtain constraints on the possible behavior of the system. Using these constraints, we obtain linear programs whose values upper and lower bound the performance measures of interest, namely throughputs or blocking probabilities. The main advantages of this new technique are that the computational complexity does not increase with the size of the finite buffers and that the technique is applicable to systems in which some buffers have infinite capacity. The technique is demonstrated on examples taken from both manufacturing systems and communication networks. As a special case, for the M/M/s/s queue, we establish the asymptotic exactness of the bounds, i.e., that the bounds on the blocking probability asymptotically approach the exact value as the degree of the multinomials considered is increased to infinity. This revised version was published online in June 2006 with corrections to the Cover Date.     

Deadlock properties of queueing networks with finite capacities and multiple routing chains

Blocking in queueing network models with finite capacities can lead to deadlock situations. In this paper, deadlock properties are investigated in queueing networks with multiple routing chains. The necessary and sufficient conditions for deadlockfree queueing networks with blocking are provided. An optimization algorithm is presented for finding deadlock-free capacity assignments with the least total capacity. The optimization algorithm maps the queueing network into a directed graph and obtains the deadlock freedom conditions from a specified subset of cycles in the directed graph. In certain network topologies, the number of deadlock freedom conditions can be large, thus, making any optimization computationally expensive. For a special class of topologies, so-calledtandem networks, it is shown that a minimal capacity assignment can be directly obtained without running an optimization algorithm. Here, the solution to the minimal capacity assignment takes advantage of the regular topology of tandem networks.This work was supported by the National Science Foundation under Grant No. CCR-90-11981.     

On stationary tandem queueing networks with job feedback

The class of tandem queueing networks with job feedback is studied under stationarity conditions on the arrival and service times sequences. Each job, after completing service in the last queue, is fed back (rerouted) to the first one, a random number of times, before leaving the system. The average execution time per job is exactly computed, as the number of jobs becomes large, and is minimized under mild conditions. The degree of parallelism achieved in the processing is also computed. The issue of rate-stability of the system is then considered. The network is defined to be rate-stable iff the job departure rate is equal to the job arrival rate; that depends heavily on the dynamic feedback policy we employ to place rerouted jobs in specific places of the front queue buffer of the network. The condition under which the network is rate-stable is specified, and a dynamic feedback policy is constructed, which rate-stabilizes the system under the maximum possible job arrival rate; thus, it maximizes the dynamic throughput of the network. Other related results concerning the performance of tandem networks with feedback are obtained.Research supported in part by grants NSF-DDM-RIA-9010778, NSF-NCR-9116268, NSF-NCR-NYI-9258 507, by an AT&T Foundation grant and a GTE Fellowship.     

Product form stationary distributions for queueing networks with blocking and rerouting

In this paper we study Markovian queueing networks in which the service and the routing characteristics have a particular form which leads to a product form stationary distribution for the number of customers in the various queues of the network. We show that if certain transitions are prohibited due to blocking conditions, then the form of the stationary distribution is preserved under a certain rerouting protocol. Several examples are presented which illustrate the wide applicability of the model. This revised version was published online in June 2006 with corrections to the Cover Date.     

Allocation of buffer capacities in queueing networks with arbitrary topologies

Two algorithms are developed to allocateM buffers toN service stations connected arbitrarily in a feed-forward manner. All service times and the interarrival times are assumed to be exponentially distributed. Both methodologies are easy-to-use tools to explore alternative buffer storage configurations and parameter settings during the initial design stages of production systems, communications networks, and flexible manufacturing systems.This research was done while the author was on a sabbatical leave of absence at North Carolina State University, Raleigh, North Carolina.     

Symmetry property of the throughput in closed tandem queueing networks with finite buffers

In this paper we consider closed tandem queueing networks with finite buffers and blocking before service. With this type of blocking, a server is allowed to start processing a job only if there is an empty space in the next buffer. It was recently conjectured that the throughput of such networks is symmetrical with respect to the population of the network. That is, the throughput of the network with population N is the same as that with population C − N, where C is the total number of buffer spaces in the network. The main purpose of this paper is to prove this result in the case where the service time distributions are of phase type (PH-distribution). The proof is based on the comparison of the sample paths of the network with populations N and C − N. Finally, we also show that this symmetry property is related to a reversibility property of this class of networks.     

Approximate analysis of arbitrary configurations of open queueing networks with blocking

An algorithm for analyzing approximately open exponential queueing networks with blocking is presented. The algorithm decomposes a queueing network with blocking into individual queues with revised capacity, and revised arrival and service processes. These individual queues are then analyzed in isolation. Numerical experience with this algorithm is reported for three-node and four-node queueing networks. The approximate results obtained were compared against exact numerical data, and they seem to have an acceptable error level.Supported in part by a grant from CAIP Center, Rutgers University.Supported in part by the National Science Foundation under Grant DCR-85-02540.     

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.     

A class of hierarchical queueing networks and their analysis

Queueing networks are an adequate model type for the analysis of complex system behavior. Most of the more realistic models are rather complex and do not fall into the easy solvable class of product form networks. Those models have to be analyzed by numerical solution of the underlying Markov chain and/or approximation techniques including simulation. In this paper a class of hierarchically structured queueing networks is considered and it is shown that the hierarchical model structure is directly reflected in the state space and the generator matrix of the underlying Markov chain. Iterative solution techniques for stationary and transient analysis can be modified to make use of the model structure and allow an efficient numerical analysis of large, up to now not solvable queueing networks.     

Insensitivity of multiclass systems with general dynamic preemptive resume queueing disciplines

We are concerned with the insensitivity of the stationary distributions of the system states inM/G/s/m queues with multiclass customers and with LIFO preemptive resume service disciplines. We introduce general entrance and exit rules into and from waiting positions, respectively, for the behaviour of waiting customers whose service is interrupted. These rules may, roughly speaking, depend on the number of customers in the system. It is shown that the stationary distribution of the system state is insensitive not only with respect to the service time distributions but also with respect to the general entrance and exit rules. As well as the insensitivity of the service scheme, our results are obtained for a special form of state and customer type dependent arrival and service rates. Some further results are concluded related to insensitivity like the formula for the conditional mean sojourn time and the property of transformation of a Poisson input into a Poisson output by the systems.     

A survey of product form queueing networks with blocking and their equivalences

Queueing network models have been extensively used to represent and analyze resource sharing systems, such as production, communication and information systems. Queueing networks with blocking are used to represent systems with finite capacity resources and with resource constraints. Different blocking mechanisms have been defined and analyzed in the literature to represent distinct behaviors of real systems with limited resources. Exact product form solutions of queueing networks with blocking have been derived, under special constraints, for different blocking mechanisms. In this paper we present a survey of product form solutions of queueing networks with blocking and equivalence properties among different blocking network models. By using such equivalences we can extend product form solutions to queueing network models with different blocking mechanisms. The equivalence properties include relationships between open and closed product form queueing networks with different blocking mechanisms.This work has been partially supported by CNR Project Research Funds Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo and by MURST Project Research Funds Performability hw/sw di sistemi distribuiti e paralleli.     

Approximate mean value performance analysis of cyclic queueing networks with production blocking

A simple approximation method is developed for performance analysis of exponential cyclic queues with production blocking. With a modified Arrival Instant Theorem to cater for finite queue capacity, a set of equations involving the mean values of performance measures are established and an efficient algorithm is proposed. Numerical experiments show that the approximation method is very efficient in providing results with good accuracy.     

A heavy traffic limit theorem for a class of open queueing networks with finite buffers

We consider a queueing network of d single server stations. Each station has a finite capacity waiting buffer, and all customers served at a station are homogeneous in terms of service requirements and routing. The routing is assumed to be deterministic and hence feedforward. A server stops working when the downstream buffer is full. We show that a properly normalized d-dimensional queue length process converges in distribution to a fd-dimensional semimartingale reflecting Brownian motion (RBM) in a d-dimensional box under a heavy traffic condition. The conventional continuous mapping approach does not apply here because the solution to our Skorohod problem may not be unique. Our proof relies heavily on a uniform oscillation result for solutions to a family of Skorohod problems. The oscillation result is proved in a general form that may be of independent interest. It has the potential to be used as an important ingredient in establishing heavy traffic limit theorems for general finite buffer networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the law of the iterated logarithm in multiserver open queueing networks

The paper is devoted to the analysis of queueing systems in the context of the network and communication theory. We investigate a theorem on the law of the iterated logarithm for a queue of jobs in a multiserver open queueing network under heavy traffic conditions.     

Approximate analysis of load-dependent generally distributed queuing networks with low service time variability

In this paper, we present an approximate method for solution of load-dependent, closed queuing networks having general service time distributions with low variability. The proposed technique is an extension of Marie’s (1980) method. In the methodology, conditional throughputs are obtained by an iterative procedure. The iterations are repeated until an invalid result is detected or no improvements are found. We demonstrate the performance of the technique with 10 different examples. On average, the solutions have 5% or lower deviations when compared to simulation results.     

Kronecker representation and decompositional analysis of closed queueing networks with phase-type service distributions and arbitrary buffer sizes

Two approximative fixed-point iterative methods based on decomposition for closed queueing networks with Coxian service distributions and arbitrary buffer sizes are extended to include phase-type service distributions. The irreducible Markov chain associated with each subnetwork in the respective decompositions is represented hierarchically using Kronecker products. The two methods are implemented in a software tool capable of computing the steady-state probability vector of each subnetwork by a multilevel method at each fixed-point iteration and are compared with other methods for accuracy and efficiency. Numerical results indicate that there is a niche filled by the two approximative methods. The authors thank Jean-Michel Fourneau for pointing out Marie’s method and Brouwer’s fixed-point theorem. The first author gratefully acknowledges grant TüBA-GEBİP from the Turkish Academy of Sciences.     

Influence of noise and delay on reaction-diffusion recurrent neural networks

In this paper, the influence of the noise and delay upon the stability property of reaction-diffusion recurrent neural networks （RNNs） with the time-varying delay is discussed. The new and easily verifiable conditions to guarantee the mean value exponential stability of an equilibrium solution are derived. The rate of exponential convergence can be estimated by means of a simple computation based on these criteria.