A fork-join queueing model: Diffusion approximation,integral representations and asymptotics

We consider two parallel M/M/1 queues which are fed by a single Poisson arrival stream. An arrival splits into two parts, with each part joining a different queue. This is the simplest example of a fork-join model. After the individual parts receive service, they may be joined back together, though we do not consider the join part here. We study this model in the heavy traffic limit, where the service rate in either queue is only slightly larger than the arrival rate. In this limit we obtain asymptotically the joint steady-state queue length distribution. In the symmetric case, where the two servers are identical, this distribution has a very simple form. In the non-symmetric case we derive several integral representations for the distribution. We then evaluate these integrals asymptotically, which leads to simple formulas which show the basic qualitative structure of the joint distribution function.     

An assignment problem for a parallel queueing system with two heterogeneous servers

In this paper, we consider an optimization problem for a parallel queueing system with two heterogeneous servers. Each server has its own queue and customers arrive at each queue according to independent Poisson processes. Each service time is independent and exponentially distributed. When a customer arrives at queue 1, the customers in queue 1 can be transferred to queue 2 by paying an assignment cost which is proportional to the number of moved customers. Holding cost is a function of the pair of queue lengths of the two servers. Our objective is to minimize the expected total discounted cost. We use the dynamic programming approach for this problem. Considering the pair of queue lengths as a state space, we show that the optimal policy has a switch over structure under some conditions on the holding cost.     

Kitting process in a stochastic assembly system

In small-lot, multi-product, multi-level assembly systems, kitting (or accumulating) components required for assembly plays a crucial role in determining system performance, especially when the system operates in a stochastic environment. This paper analyzes the kitting process of a stochastic assembly system, treating it as an assembly-like queue. If components arrive according to Poisson processes, we show that the output stream departing the kitting operation is a Markov renewal process. The distribution of time between kit completions is also derived. Under the special condition of identical component arrival streams having the same Poisson parameter, we show that the output stream of kits approximates a Poisson process with parameter equal to that of the input stream. This approximately decouples assembly from kitting, allowing the assembly operation to be analyzed separately.     

Approximation of throughput in tandem queues with multiple servers and blocking

In this paper, we develop an approximation method for throughput in tandem queues with multiple independent reliable servers at each stage and finite buffers between service stations. We consider the blocking after service (BAS) blocking protocol of each service stage. The service time distribution of each server is exponential. The approximation is based on the decomposition of the system into a set of coupled subsystems which are modeled by two-stage tandem queue with two buffers and are analyzed by using the level dependent quasi-birth-and-death (LDQBD) process.     

Modelling and analysis of M/G a,b /1/N queue – A simple alternative approach

In this paper, we consider a single-server finite-capacity queue with general bulk service rule where customers arrive according to a Poisson process and service times of the batches are arbitrarily distributed. The queue is analyzed using both the supplementary variable and imbedded Markov chain techniques. The relations between state probabilities at departure and arbitrary epochs have been presented in explicit forms.     

Stability and continuity of polling systems

The stability of a polling system with exhaustive service and a finite number of users, each with infinite buffers is considered. The arrival process is more general than a Poisson process and the system is not slotted. Stochastic continuity of the stationary distributions, rates of convergence and functional limit theorems for the queue length and waiting time processes have also been proved. The results extend to the gated service discipline.     

Stability and Analysis of TCP Connections with RED Control and Exogenous Traffic

In this paper we study the stability and performance of a system involving several TCP connections passing through a tandem of RED controlled queues each of which has an incoming exogenous stream. The exogenous stream, representing the superposition of all incoming UDP connections into a queue, has been modeled as an MMPP stream. We consider both the TCP Tahoe and the TCP Reno versions. We start with the analysis of a single TCP connection sharing a RED controlled queue with an exogenous stream. The effect of the exogenous stream (which is almost always present in large networks) is to cause the system to converge to a stationary distribution from any initial conditions. This stability result holds good for any work conserving discipline. We also obtain the performance indices of the system; specifically the goodputs and the mean sojourn times of the various connections. The complexity involved in computation of performance indices for the system is reduced by approximating the evolution of the average queue length process of the RED queue by a deterministic ODE. Then, by using a decomposition approach of two time scales, we reduce the study of the system to that of a simplified one for which the performance measures can be obtained under stationarity. Finally, we extend the above results to the case when multiple TCP connections share a RED controlled queue with an exogenous stream and to the case when a TCP connection passes through several RED controlled tandem queues each of which has an incoming exogenous stream. We also consider an example of multiple TCPs passing through a tandem of queues. A number of simulation results have been provided which support the analysis.     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

Distributional Form of Little's Law for FIFO Queues with Multiple Markovian Arrival Streams and Its Application to Queues with Vacations

This paper considers stationary queues with multiple arrival streams governed by an irreducible Markov chain. In a very general setting, we first show an invariance relationship between the time-average joint queue length distribution and the customer-average joint queue length distribution at departures. Based on this invariance relationship, we provide a distributional form of Little's law for FIFO queues with simple arrivals (i.e., the superposed arrival process has the orderliness property). Note that this law relates the time-average joint queue length distribution with the stationary sojourn time distributions of customers from respective arrival streams. As an application of the law, we consider two variants of FIFO queues with vacations, where the service time distribution of customers from each arrival stream is assumed to be general and service time distributions of customers may be different for different arrival streams. For each queue, the stationary waiting time distribution of customers from each arrival stream is first examined, and then applying the Little's law, we obtain an equation which the probability generating function of the joint queue length distribution satisfies. Further, based on this equation, we provide a way to construct a numerically feasible recursion to compute the joint queue length distribution.     

Exact analysis of asymmetric random polling systems with single buffers and correlated input process

We introduce a simple approach for modeling and analyzing asymmetric random polling systems with single buffers and correlated input process. We consider two variations of single buffers system: the conventional system and the buffer relaxation system. In the conventional system, at most one customer may be resided in any queue at any time. In the buffer relaxation system, a buffer becomes available to new customers as soon as the current customer is being served. Previous studies concentrate on conventional single buffer system with independent Poisson process input process. It has been shown that the asymmetric system requires the solution ofm 2 ^m –1) linear equations; and the symmetric system requires the solution of 2 ^m–1–1 linear equations, wherem is the number of stations in the system. For both the conventional system and the buffer relaxation system, we give the exact solution to the more general case and show that our analysis requires the solution of 2 ^m –1 linear equations. For the symmetric case, we obtain explicit expressions for several performance measures of the system. These performance measures include the mean and second moment of the cycle time, loss probability, throughput, and the expected delay observed by a customer.