Analysis of an open tandem queueing network with population constraint and constant service times 1

We consider an open tandem queueing network with population constraint and constant service times. The total number of customers that may be present in the network can not exceed a given value K. Customers arriving at the queueing network when there are more than K customers are forced to wait in an external queue. The arrival process to the queueing network is assumed to be arbitrary. We show that this queueing network can be transformed into a simple network involving only two nodes. Using this simple network, we obtain an upper and lower bound on the mean waiting time. These bounds can be easily calculated. Validations against simulation data establish the tightness of these bounds.     

Heavy traffic limit for a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue is M/G/1 and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. We investigate the amount of work in the second queue at certain embedded arrival time points, namely when the upstream queue has just emptied. We focus on the case of infinite-variance service times and obtain a heavy traffic process limit for the embedded Markov chain.     

Tandem queues with deterministic service times

In this paper we consider a tandem queueing model for a sequence of multiplexers at the edge of an ATM network. All queues of the tandem queueing model have unit service times. Each successive queue receives the output of the previous queue plus some external arrivals. For the case of two queues in series, we study the end-to-end delay of a cell (customer) arriving at the first queue, and the covariance of its delays at both queues. The joint queue length process at all queues is studied in detail for the 2-queue and 3-queue cases, and we outline an approach to the case of an arbitrary number of queues in series.Part of the research of this author has been supported by the European Grant BRA-QMIPS of CEC DG XIII.The research of this author was done during the time that he was affiliated with CWI, in a joint project with PTT Research.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

Optimal batch service of a polling system under partial information

We consider the optimal scheduling of an infinite-capacity batch server in aN-node ring queueing network, where the controller observes only the length of the queue at which the server is located. For a cost criterion that includes linear holding costs, fixed dispatching costs, and linear service rewards, we prove optimality and monotonicity of threshold scheduling policies.     

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.     

Cycle analysis of a two-phase queueing model with threshold

We consider a single-server, two-phase queueing system with N-policy. Customers arrive at the system according to a Poisson process and receive batch service in the first phase followed by individual services in the second phase. If the system becomes empty at the moment of the completion of the second-phase services, it is turned off. After an idle period, when the queue length reaches N (threshold), the server is turned on and begins to serve customers. We obtain the system size distribution and show that the system size decomposes into three random variables. The system sojourn time is provided. Analysis for the gated batch service model is also provided. Finally we derive a condition under which the optimal operating policy is achieved.     

The infinite-buffer single server queue with a variant of multiple vacation policy and batch Markovian arrival process

We consider an infinite-buffer single server queue where arrivals occur according to a batch Markovian arrival process (BMAP). The server serves until system emptied and after that server takes a vacation. The server will take a maximum number H of vacations until either he finds at least one customer in the queue or the server has exhaustively taken all the vacations. We obtain queue length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue lengths and mean waiting times, etc. have been obtained. Several other vacation queueing models like, single and multiple vacation model, queues with exceptional first vacation time, etc. can be considered as special cases of our model.     

Waiting time approximation in multi-class queueing systems with multiple types of class-dependent interruptions

We consider a single-server queue subject to class-dependent interruptions motivated by vessel queueing at entrances of waterways. Two classes of customers and k types of possibly simultaneous and class-dependent service interruptions are considered. We have employed service completion time analysis and proposed approximations to obtain the expected waiting time of a customer (vessel) in the queue.     

推广的M~x/G(M/G)/1(M/G)可修排队系统(I)── 一些排队指标

考虑M     

Analysis of an SPP/G/1 system with multiple vacations and E-limited service discipline

Many researchers have studied variants of queueing systems with vacations. Most of them have dealt with M/G/1 systems and have explicitly analyzed some of their performance measures, such as queue length, waiting time, and so on. Recently, studies on queueing systems whose arrival processes are not Poissonian have appeared. We consider a single server queueing system with multiple vacations and E-limited service discipline, where messages arrive to the system according to a switched Poisson process. First, we consider the joint probability density functions of the queue length and the elapsed service time or the elapsed vacation time. We derive the equations for these pdf's, which include a finite number of unknown values. Using Rouché's theorem, we determine the values from boundary conditions. Finally, we derive the transform of the stationary queue length distribution explicitly.     

An explicit solution to a tandem queueing model

We consider two queues in tandem, each with an exponential server, and with deterministic arrivals to the first queue. We obtain an explicit solution for the steady state distribution of the process (N₁(t), N₂(t), Y(t)), where N_j(t) is the queue length in the jth queue and Y(t) measures the time elapsed since the last arrival. Then we obtain the marginal distributions of (N₁(t), N₂(t)) and of N₂(t). We also evaluate the solution in various limiting cases, such as heavy traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

Mean queue size in a queue with discrete autoregressive arrivals of order <Emphasis Type="Italic">p</Emphasis>

We consider a discrete time single server queueing system where the arrival process is governed by a discrete autoregressive process of order p (DAR(p)), and the service time of a customer is one slot. For this queueing system, we give an expression for the mean queue size, which yields upper and lower bounds for the mean queue size. Further we propose two approximation methods for the mean queue size. One is based on the matrix analytic method and the other is based on simulation. We show, by illustrations, that the proposed approximations are very accurate and computationally efficient.     

Analysis of the queue-length distribution for the discrete-time batch-service Geo/G/1/K queue

In this paper, we consider a discrete-time finite-capacity queue with Bernoulli arrivals and batch services. In this queue, the single server has a variable service capacity and serves the customers only when the number of customers in system is at least a certain threshold value. For this queue, we first obtain the queue-length distribution just after a service completion, using the embedded Markov chain technique. Then we establish a relationship between the queue-length distribution just after a service completion and that at a random epoch, using elementary ‘rate-in = rate-out’ arguments. Based on this relationship, we obtain the queue-length distribution at a random (as well as at an arrival) epoch, from which important performance measures of practical interest, such as the mean queue length, the mean waiting time, and the loss probability, are also obtained. Sample numerical examples are presented at the end.     

Analyzing a Two-Stage Queueing System with Many Point Process Arrivals at Upstream Queue

We consider a two-stage queueing system where the first (upstream) queue serves many flows, of which a fixed set of flows arrive to the second (downstream) queue. We show that as the capacity and the number of flows aggregated at the upstream queue increases, the overflow probability at the downstream queue converges to that of a simplified single queue obtained by removing the upstream queue from the original two-stage queueing system. Earlier work shows such convergence for fluid traffic, by exploiting the large deviation result that the workload goes to zero almost surely, as the number of flows and capacity is scaled. However, the analysis is quite different and more difficult for the point process traffic considered in this paper. The reason is that for point process traffic the large deviation rate function need not be strictly positive (i.e., I(0)=0), hence the workload at the upstream queue may not go to zero even though the number of flows and capacity go to infinity. The results in this paper thus make it possible to decompose the original two-stage queueing system into a simple single-stage queueing system.     

Some notes on the reduction of network dimensionality in nested open queueing networks

In this paper, we study an open and nested tandem queueing network, where the population constraint within each subnetwork is controlled by a semaphore queue. The total number of customers that may be present in the subnetwork can not exceed a given value. Each node has a constant service time and the arrival process to the queueing network follows an arbitrary distribution.A major characteristic of this queueing network is that the low layer flow is halted by the state of the high layer. We develop a simple and equivalent queueing network that has the same performance characteristics as the original queueing network. Using this model, the waiting time on the queueing network can be easily derived. It is interesting to see how the simplification process can be applied to multi-layered queueing network.     

Analysis of the GI/Geo/1 queue with N-policy

We consider a discrete-time single server N  -policy GI/Geo/1$\mathit{GI}/\mathit{Geo}/1$ queueing system. The server stops servicing whenever the system becomes empty, and resumes its service as soon as the number of waiting customers in the queue reaches N. Using an embedded Markov chain and a trial solution approach, the stationary queue length distribution at arrival epochs is obtained. Furthermore, we obtain the stationary queue length distribution at arbitrary epochs by using the preceding result and a semi-Markov process. The sojourn time distribution is also presented.     

Performance analysis of AAL multiplexer with CBR traffic and bursty traffic

This paper models and evaluates the AAL multiplexer to analyze AAL protocol in ATM networks. We consider an AAL multiplexer in which a single periodically deterministic CBR traffic stream and several variable size bursty background traffic streams are multiplexed and one ATM cell stream goes out. We model the AAL multiplexer as aB ^X +D/D/1/K queue and analyze this queueing system. We represent various performance measures such as loss probability and waiting time in the basis of cell and packet.     

Queueing and Fluid Analysis of Partial Message Discarding Policy

We consider a stream of packets that arrive at a queue with a finite buffer. A group of consecutive packets constitutes a frame. We assume that when an arriving packet finds the queue full, not only is the packet lost but also the future packets that belong to the same frame will be rejected. The first part of the paper deals with a detailed packet level queueing model; we obtain exact expressions for the stationary queue length distribution and the goodput ratio (i.e. the fraction of arriving frames that experience no losses). The second part deals with a fluid model and the fluid analysis leads to simple closed form expressions for the stationary workload process and the fluid goodput ratio.