A tandem queueing system with priorities

A system ofN unlimited queues andN time-discrete servers in series, is investigated. The input consists ofN stochastic processes where requests which have been generated according to thei-th process leave the system after they have received serivice by servers 1, 2, ...,i. The holding-time distributions can be calculated by means of an equivalence theorem which holds under certain conditions for the service times.     

Decomposition of general tandem queueing networks with MMPP input

For tandem queueing networks with generally distributed service times, decomposition often is the only feasible solution method besides simulation. The network is partitioned into individual nodes which are analyzed in isolation. In most existing decomposition algorithms for continuous-time networks, the output of a queue is usually approximated as a renewal process, which becomes the arrival process to the next queue. In this paper, the internal traffic processes are described as semi-Markov processes (SMPs) and Markov modulated Poisson processes (MMPPs). Thus, correlations in the traffic streams, which are known to have a considerable impact on performance, are taken into account to some extent. A two-state MMPP, which arises frequently in communications modeling, serves as input to the first queue of the tandem network. Furthermore, the single nodes may have infinite or finite buffers. Customers who arrive at a full buffer will get lost.

In principle, the analysis of an individual queue as an MMPP/G/1(/K) system delivers a wide range of performance measures. For different examples of tandem networks, stationary mean queue lengths at arbitrary time are compared to simulation data. The relative errors of the results, which are computed promptly by the decomposition component of the tool TimeNET, remain within a reasonable range.     

Gaussian tandem queues with an application to dimensioning of switch fabric interfaces

Tandem systems are seen in many places and at various hierarchical levels in high-speed communication networks, from router architectures to protocol stacks. If the traffic fed into the system is generated by independent or weakly dependent sources and the smallest relevant time scale is not too fine, the central limit theorem suggests that the input traffic is (close to) Gaussian.This paper considers tandem queues fed by Gaussian processes with stationary increments. Relying on the generalized version of Schilder’s sample-path large-deviations theorem, we derive the many-sources asymptotics of the overflow probabilities in the second queue; ‘Schilder’ reduces this problem to finding the most probable path along which the second queue reaches overflow. The general form of these paths is described by recently obtained results on infinite-intersections of events in Gaussian processes; for the special cases of fractional Brownian motion and integrated Ornstein–Uhlenbeck input, the most probable path can be explicitly determined, as well as the corresponding exponential decay rate.As the computation of the decay rate is numerically involved, we introduce an explicit approximation (‘rough full-link approximation’). Based on this approximation, we propose performance formulae for network provisioning purposes. Simulation is used to assess the accuracy of the formulae. As an example, we show how the methods can be applied to dimensioning the interface between a line card and a switch fabric.     

Multi-core application performance optimization using a constrained tandem queueing model

Recently, performance optimization on multi-core platforms has received more and more research interest especially for networking applications. While a number of case studies have been made with success, there is however a lack of analytical treatment on the modeling of parallel processing in applications. In this paper, we tackle the performance optimization problem using queueing analysis. Modeling macroscopic pipeline processes with a constrained tandem model, an optimization principle is derived. We then employ the derived principle to analyze two network applications: intrusion detection and image retrieval. Both theoretical performance analysis and simulation results confirm the effectiveness of our optimization principle.     

Optimal importance sampling for Markovian systems with applications to tandem queues

Importance sampling is a change-of-measure technique for speeding up the simulation of rare events in stochastic systems. In this paper we establish a number of properties characterizing optimal importance sampling measures for Markovian systems. We use these properties to develop a new method for computing the optimal measure and give specific results for a tandem queueing system. Optimal measures, though as diffcult to compute as the rare event probability itself, give useful insight into the characteristics of importance sampling measures. Our approach has no immediate computational advantage over other methods, but it suggests a number of heuristic approximations which may lead to computationally attractive methods.     

On tandem blocking queues with a common retrial queue

We consider systems of tandem blocking queues having a common retrial queue. The model represents dynamics of short TCP transfers in the Internet. Analytical results are available only for a specific example with two queues in tandem. We propose approximation procedures involving simple analytic expressions, based on mean value analysis (MVA) and on fixed point approach (FPA). The mean sojourn time of a job in the system and the mean number of visits to the orbit queue are estimated by the MVA which needs as an input the fractions of blocked jobs in the primary queues. The fractions of blocked jobs are estimated by FPA. Using a benchmark example of the system with two primary queues, we conclude that the approximation works well in the light traffic regime. We note that our approach becomes exact if the blocking probabilities are fixed. Finally, we consider two optimization problems regarding minimizing mean total sojourn time of a job in the system: (i) finding the best order of queues and (ii) allocating a given capacity among the primary queues.     

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.     

Computing effectiveness measures for tandem markovian queues with blocking

Upper and lower bounds are developed for the unexpected number of units in the second stage and the throughput of a two-stage $\text{M/M/c,/∞,M/M/c}{}_2\text{/c}{}_2\text{+ K}$) tandem queueing system with blocking at the second stage. The upper bound is derived from a two-stage Jackson system while the lower bound is obtained from a (loss) system in which customers blocked at the second stage are lost. Numerical results are given which show that the bounds become tight very quickly with increasing values of K and μ at the second stage.     

Fuzzy control of arrivals to tandem queues with two stations

We consider two queues in tandem, each of which has its own input of arriving customers, which, in turn, may either be accepted or rejected. Suppose that the system receives a fixed reward for each accepted customer and pays a holding cost per customer per unit time in the system. The objective is to dynamically determine the optimal admission policies based on the state of the system so as to maximize the average profit (reward minus cost) over an infinite horizon. This model finds applications in flow control in communication systems, industrial job shops, and traffic-flow systems. In this paper, a novel approach is presented using fuzzy control. This approach explicitly finds the optimal policy, which up until now has defied analytical solutions     

Optimal reservation policy for two queues in tandem

In this paper, we consider the optimal reservation problem for two multi-server loss queues in tandem, which is usually used to model network and communication systems. In previous work [European J. Oper. Res. 21 (1985) 399-409; Ph.D. diss., 1995; IEEE Trans. Automatic Control 42 (1997) 1017-1023], under appropriate conditions, the optimal reservation policy that maximizes the expected total discounted reward over an infinite horizon is shown to be a switching curve in two-dimensional state space. However, some counterintuitive examples for variation do exist in the numerical experiments. We therefore discuss and analyze the variation in these switching curves with the number of customers in the system. We propose two sufficient conditions under which the counterintuitive situation will not occur.     

Approximate analysis of a discrete-time tandem network of cut-through queues with blocking and bursty traffic

A discrete-time tandem network of cut-through queues is presented. The model allows finite capacity queues, blocking, and bursty traffic. A new bursty arrival process, IBK(k), for cut-through traffic is introduced. The tandem network is analyzed using single-node decomposition. Each queue is analyzed numerically in isolation assuming that its arrival and service processes are known. The parameters of the arrival and service processes of the queues are obtained using an iterative scheme. The results obtained are approximate and validation tests have shown that the model has good accuracy. Using this model, the packet loss, throughput, and queue length distributions were obtained for different traffic parameters and queue sizes.     

Infinitesimal perturbation analysis of a queueing system with bursty traffic

We study aG/G/1 queueing system with a bursty arrival process. Based on a general model for such a bursty process, we derive infinitesimal perturbation analysis (IPA) derivative estimators of the mean system time with respect to various parameters of interest. The cases of both complete and partial state information are considered. To ensure unbiasedness and strong consistency of the estimators, different sample path representations are developed such that sample functions are continuous with respect to the particular parameter of interest. Some of these representations are applicable to a wider class of gradient estimation problems where sample path discontinuities arise. Simulation results are included to compare the convergence rates and variance properties of the different IPA estimators developed.     

A maximum entropy optimization approach to tandem queues with generalized blocking

We study a general blocking scheme for an open tandem queueing network with finite intermediate buffers. The service time at each node as well as interarrival time at the first node is assumed to be exponentially distributed. The interarrival and service time at each intermediate node of the tandem queue, under the general blocking scheme, depend upon three parameters at each node, namely, the maximum number of raw jobs, the upper limit on the number of finished but blocked jobs and the buffer capacity. This three-parameter analysis was introduced by Cheng and Yao (1993), and was shown, using Monte Carlo simulations, to provide good results. Our analysis is also based on this three-parameter approach, but with a different view. We first decompose the tandem queue into a group of two-node subsystems in order to derive a set of equations for the effective interarrival and service time distributions at each node. Each of these two-node subsystems is treated as a finite capacity queueing system with population size constraints. Then we apply the principle of maximum entropy to evaluate different parameters such as the blocking probabilities, starvation probabilities, etc., of each subsystem. We propose a step-by-step algorithm along with its convergence properties. A comparison of numerical results with the simulation results is also discussed.     

The queueing equivalence to a manufacturing system with failures

The authors consider optimal production rate control in a failure prone manufacturing system. It is well known that the hedging point policy is the optimum controller for such a system. They show that under the hedging point policy the system can be treated as an M/M/1 queue. Therefore, existing results in queuing theory can be readily applied to obtaining the steady-state probability density function of the production surplus, based on which the optimal hedging point policy can be computed. To a large extent, the approach is based on sample path analysis. It not only provides an alternative way to solve the problem but also reveals some interesting insights     

Computational analysis of a Markovian queueing system with geometric mean-reverting arrival process

In the queueing literature, an arrival process with random arrival rate is usually modeled by a Markov-modulated Poisson process (MMPP). Such a process has discrete states in its intensity and is able to capture the abrupt changes among different regimes of the traffic source. However, it may not be suitable for modeling traffic sources with smoothly (or continuously) changing intensity. Moreover, it is less parsimonious in that many parameters are involved but some are lack of interpretation. To cope with these issues, this paper proposes to model traffic intensity by a geometric mean-reverting (GMR) diffusion process and provides an analysis for the Markovian queueing system fed by this source. In our treatment, the discrete counterpart of the GMR arrival process is used as an approximation such that the matrix geometric method is applicable. A conjecture on the error of this approximation is developed out of a recent theoretical result, and is subsequently validated in our numerical analysis. This enables us to calculate the performance measures with high efficiency and precision. With these numerical techniques, the effects from the GMR parameters on the queueing performance are studied and shown to have significant influences.     

Perturbation analysis of a multiclass queueing system withadmission control

A service facility with multiple customer classes is considered. Each class forms an independent Poisson arrival process with admission controlled by a threshold parameter and is characterized by a general service time distribution. Gradient estimators are derived for performance measures of the system (mean system time, throughput, blocking probabilities) using perturbation analysis techniques. The approach is based on exploiting alternative sample path representations of generalized semi-Markov process models of the system, such that the resulting sample functions are continuous with respect to parameters of interest. The unbiasedness of the estimators is proved. Simulation examples are included to illustrate their properties