Throughput bounding and simple approximation methods for exponential fork/join queueing networks with blocking

Exponential fork/join queueing networks (FJQNs) with finite buffers have been used as a major tool for evaluating the performances of manufacturing systems. In this study, we first suggest the throughput upper and lower bounds. Our upper-bounding method is elaborated on with general network configuration (acyclic configuration), while our lower bounds can be obtained only for networks with more specialized configuration. Next, developed is a simple approximation method for throughputs, which are based on decomposition/aggregation principles and structurally equivalent relations between different configurations.     

Approximate analysis of load dependent general queueing networks

A method for obtaining approximate solutions to load-dependent closed queueing networks containing general service-time distributions and first-come-first-served scheduling disciplines is presented. The technique demonstrated is an extension of the well-known method of R. Marie (1979). A formula for the conditional throughputs is derived. After each iteration a check is performed to guarantee that the results obtained are within a tolerance level ϵ. These iterations are repeated whenever invalid results are detected. On the average, the solutions obtained vary by less than 5% from their respective exact and simulation results     

Approximate throughput analysis of cyclic queueing networks withfinite buffers

An approximation method for obtaining the throughput of cyclic queueing networks with blocking as a function of the number of customers in it is presented. The approximation method was developed for two different blocking mechanisms. It was also extended to the case of the central server model with blocking. Validation tests show that the algorithm is fairly accurate     

Approximate analysis of M/G/c/c state-dependent queueing networks

Congestion is ever present in most practical situations. We describe a methodology for approximate analysis of open state-dependent M/G/c/c queueing networks in which the service rate is subject to congestion, that is, it is a function of the number of customers in the system. Important performance measurements are easily computed with high accuracy, such as the blocking probability, throughput, expected number of customers in the system (known also as work-in-process), and expected waiting time. The methodology forms a basic building block useful in many practical applications and contexts. Computational results demonstrate that the methodology provides accurate results in many topological configurations as well as in the analysis of network evacuation problems in high-rise buildings.     

Infinitesimal and finite perturbation analysis for queueing networks

The sample-path perturbation analysis technique is extended to include finite (and possibly large) perturbations typically introduced by changes in queue sizes or other parameters. It is shown that there is a natural hierarchy of perturbation analysis which takes care of increasingly large perturbations. Experiments with zero (infinitesimal) and first order (finite) perturbation analysis show that significant accuracy improvement can be obtained with small increase in computational effort.     

Approximate analysis of exponential queueing systems with blocking

Summary A network of service stations Q ₀ Q ₁,...,Q_M is studied. Requests arrive at the centers according to independent Poisson processes; they travel through (part of) the network demanding amounts of service, with independent and negative exponentially distributed lengths, from those centers which they enter, and finally depart from the network. The waiting rooms or buffers at each service station in this exponential service system are finite. When the capacity at Q _i is reached, service at all nodes which are currently processing a request destined next for Q _i is instantaneously interrupted. The interruption lasts until the service of the request in the saturated node Q _i is. completed. This blocking phenomenon makes an exact analysis intractable and a numerical solution computationally infeasible for most exponential systems. We introduce an approximation procedure for a class of exponential systems with blocking and show that it leads to accurate approximations for the marginal equilibrium queue length distributions. The applicability of the approximation method may not be limited to blocking systems.Mathematical Sciences Department Postdoctoral Fellow 1978–79.     

Approximate solution to multichain queueing networks with state dependent service rates

An approximation scheme for solving non-product form queueing networks with multiple chains and state dependent service rates is described. Estimates of the steady state probability distribution are obtained using less computational requirements than the standard solution techniques.The approximation scheme is based on a property called chain conditional balance, which leads to a decomposition of the global balance equations into smaller sets of equations. A technique for combining conditional distributions is examined and used to combine the solutions of conditional balance equations into the final estimates. Expressions for the storage and computational requirements of the approximation algorithm are given and an example is provided.An error analysis is described in which the approximation is tested on a large number of randomly generated queueing networks. The experimental results indicate that the approximation yields good estimates of the steady state distribution, as well as several important performance measures of these networks.     

A hybrid solution of fork/join synchronization in parallel queues

A new analysis technique, dynamic-bubblesort analysis, is introduced for general K-queue first-in-first-out HFJ (homogenous fork/join queuing) systems of K⩾2 . The dynamic-bubblesort model dynamically sorts the branches of the queues based on the number of the tasks waiting for synchronization in each branch. Jobs arrive with mean rate λ and a general arrival distribution. Upon arrival, a job forks into K tasks. Task k, k=1, 2, ..., K, is assigned to the kth queuing system, which is a first-in-first-out server with a general service distribution and an infinite capacity queue. A job leaves the HFJ system as soon as all its tasks complete their service. In other words, tasks corresponding to the same job are joined before departing the HFJ system. We obtain a general and simple hybrid solution which combines analysis and simulation for the mean response time that we denote by T_K. We obtain a very simple (as a function of T₁ and T₂ only) and general upper bound expression for T_K and we get an exact relationship between the cases for K=2 and 3. We evaluate our results by simulating 2, 3, ..., 99, and 100 queues for p=0.1, 0.2, ....0.8, and 0.9, each for four different HFJ cases, where ρ=λ/μ and μ is the average task service rate for a server. The maximum absolute offset for our hybrid solutions from all the simulations is less than 0.33 percent (1/300), which is a reasonable error ratio for simulation. The maximum offset for our upper bounds over all the simulations is 21 percent     

Equivalencies between open and closed queueing networks with finite buffers

Equivalencies between open and closed models of queueing networks with finite buffers are investigated. Interarrival times in open networks and service times are assumed to be exponentially distributed. Using these equivalencies, bounds on the throughput of open networks are established.     

Mean value analysis for blocking queueing networks

An approximation is introduced for the mean value analysis of queueing networks with transfer blocking. The blocking occurs when a job, after completing service at a station, wants to join a station which is full. The job resides in the server of the source station until a place becomes available in the destination station. The approximation is based on the modification of mean residence times, due to the blocking events that occur in the network. Several examples are executed that validate the approximate results.<>     

Performance evaluation of fork and join synchronization primitives

Summary The paper presents a performance model of fork and join synchronization primitives. The primitives are used in parallel programs executed on distributed systems. Three variants of the execution of parallel programs with fork and join primitives are considered and queueing models are proposed to evaluate their performance on a finite number of processors. Synchronization delays incurred by the programs are represented by a state-dependent server with service rate depending on a particular synchronization scheme. Closed form results are presented for the two processor case and a numerical method is proposed for many processors. Fork-join queueing networks having more complex structure i.e., processors arranged in series and in parallel, are also analyzed in the same manner. The networks can model the execution of jobs with a general task precedence graph corresponding to a nested structure of the fork-join primitives. Some performance indices of the parallel execution of programs are studied. The results show that the speedup which can be obtained theoretically in a parallel system may be decreased significantly by synchronization constraints.This research we carried out while the author was visiting ISEM, Université de Paris-Sud, France     

An analysis of an approximation algorithm for queueing networks

Queueing network models have proved to be useful aids in computer system performance prediction. Numerous approximation algorithms have been devised to allow queueing networks to be analyzed with a reduced computational expense. In particular, for separable queueing networks several popular iterative approximation algorithms are available.

One disadvantage of these algorithms has been the lack of results concerning their behavior, such as whether or not iteration convergence is guaranteed. This paper presents an analysis of an approximate MVA algorithm proposed by Schweitzer (1979). It is proved that the equations defining the algorithm have a unique solution when there is only a single customer class, and iteration initializations that yield monotonic convergence to this solution are exhibited. It is also proved that the solution is pessimistic relative to the exact queueing network solution.     

Perturbation analysis of closed queueing networks with generalservice time distributions

Perturbation analysis of closed queuing networks with nonexponential service time distributions is studied. Perturbation analysis formulas using realization probabilities are extended to these networks. A perturbation generation function, which generalizes the perturbation generation rule, is defined. equations for realization probability and formulas for sensitivity of the system throughput with respect to service time distribution parameters are presented. The formulas provide an analytical method of calculating throughput sensitivity and an explanation of the application of perturbation analysis algorithms for networks with general service time distributions. The author focuses on the extension of concepts and intuitive explanations of the formulas rather than on mathematical derivations     

Strong consistency of infinitesimal perturbation analysis for tandem queueing networks

Strong consistency of infinitesimal perturbation analysis for the sojourn times in a class of tandem queueing networks is proved. Service times at the queues are correlated, and they are affine functions of the variable parameters. Differentiability of the average sojourn times is not assumed, but proved. The analysis is not based on assumptions of regenerative cycles of the networks but on stability and ergodicity of the queueing processes involved. The proof of strong consistency is based on a set of abstract conditions, described in terms of properties of the sample performance functions. These conditions are first shown to be sufficient for strong consistency, and then their validity for the networks in question is proved.Research supported in part by the NSF under grants Nos. ECS85-15449 and CDR-8803012, under ONR contract nos. N00014-90-K-1093 and N00014-89-J-1023, and under Army contract no. DAAL-03-83-K-0171. This author is now with the Department of Manufacturing Engineering, Boston University, Boston, MA 02215.     

On perturbation analysis of queueing networks with finitelysupported service time distributions

Infinitesimal perturbation analysis (IPA) has emerged as an efficient tool for estimating the gradient of a function defined on the steady state of a queuing network. Differentiability of such functions is often assumed due to difficulties in proving it. It is pointed out that such functions may be nondifferentiable at an infinite set of points, dense in a given interval, for a large class of realistic system models. This phenomenon is largely due to correlation of traffic patterns on the links of a network, and to the presence of atoms in the distributions of their service times. The issue of nondifferentiability goes beyond IPA, to any method for estimating the gradients of functions in steady state     

An approach for non-intrusively adding malleable fork/join parallelism into ordinary JavaBean compliant applications

Motivated by the advent of powerful hardware such as SMP machines and execution environments such as Grids, research in parallel programming has gained much attention within the distributed computing community. There is a substantial body of efforts in the form of parallel libraries and frameworks that supply developers with programming tools to exploit parallelism in their applications. Still, many of these efforts prioritize performance over other important characteristics such as code invasiveness, ease of use and independence of the underlying executing hardware/environment. In this paper, we present EasyFJP, a new approach for semi-automatically injecting parallelism into sequential Java applications that offers a convenient balance to these four aspects. EasyFJP is based upon the popular fork/join parallel pattern, and combines implicit, application-level parallelism with explicit, non-invasive application tuning. Experiments performed with several classic CPU-intensive benchmarks and a real-world application confirm that EasyFJP effectively addresses these problems while delivers very competitive performance.     

Performance analysis of window flow controlled queueing networks with acknowledgment delay

Queueing networks with window flow control and bulk arrivals are discussed. The effect of acknowledgment delay is also considered. Using the method of maximum entropy, we provide an iterative algorithm to obtain numerical results for the network throughput, utilization and average number of packets at the nodes. It is shown that the analytic results agree favourably with simulation results.     

Optimizing uniform non-Markov queueing networks

We propose a new efficient analytic-imitational method of optimizing non-Markov queueing networks. We estimate its convergence speed and precision with experiments and give practicai recommendations for its use.     

Stability of acyclic multiclass queueing networks

In this paper we study multiclass queueing networks with fluid arrival streams and service processes. Assuming that the arrival rate does not exceed the network capacity, we deduce stability of the network using the tools of ergodic theory. We show that the distributions of the process converge to a unique steady state value and that convergence takes place at a geometric rate under appropriate moment conditions     

Implementation of Monte Carlo integration for the analysis of product-form queueing networks

MonteQueue is a new public-domain software package which rapidly solves large and small multiclass product-form queueing networks with multiple- and single-server stations over a wide range of traffic conditions. MonteQueue obtains estimates of performance measures by applying importance sampling to sum and integral representations of the network's normalization constants. This paper discusses the implementation issues and surveys of the theoretical properties of the four importance sampling techniques included in MonteQueue. It also presents new numerical data which compare the performance of the four techniques.