Discriminatory processor sharing queues with stationary ergodic service times and the performance of TCP in overload

In a recent paper, Bonald and Roberts (2001) [6] studied non-persistent TCP connections in transient overload conditions, under the assumption that all connections have the same round-trip times. In this paper our goal is to develop theoretical tools that will enable us to relax this assumption and obtain explicit expressions for the rate of growth of the number of connections at the system, the rate at which TCP connections leave the system, as well as the time needed for the completion of a connection. To that end, we model the system as a discriminatory processor sharing (DPS) system which we analyze under very mild assumptions on the probability distributions related to different classes of arrivals: we only assume that the arrival rates of connections exist, and that the amount of information transmitted during a connection of a given type forms a stationary ergodic sequence. We then proceed to obtain explicit expressions for the growth rate of the number of connections at the DPS system for several specific probability distributions. We check through simulations the applicability of our queueing results for modeling TCP connections sharing a bottleneck.     

Delays in a series of queues with correlated service times

In almost all applications of queueing network models it is assumed that for each customer the service times at different network nodes are independent. But service times in, for instance, computer and communication networks are typically essentially determined by properties like message or packet lengths that do not change substantially on the route through the network. Therefore, the service times of any customer in a queueing network are likely to be correlated, which can significantly influence quality of service (QoS) properties and performance measures such that results obtained with the independence assumption may be misleading. We consider delays in a series of queues with correlated service times at each network node where for each customer the service time at the first node is a random variable and the successive service times are correlated with the one at the first node. A recursive scheme for delays is provided. This scheme is used in order to efficiently conduct a simulation study where two types of correlation are studied, namely identical service times, and service times with an additional Gaussian noise. The simulation study focuses on comparisons of end-to-end delays for independent service times at different nodes and correlated service times, respectively. It turns out that for both correlation types, in light traffic the delays in case of correlated service times are larger than for independent service times by a factor that first increases with increasing traffic intensity up to a maximum value approached in medium traffic after which it decreases quickly and drops down to become significantly smaller than one in heavy traffic. This effect intensifies with increasing number of network nodes and depends, as well as the crossover point from which on correlated service times yield smaller delays, on the distribution of the service times at the first node.     

Optimal control of service in tandem queues

Customers arrive in a Poisson stream into a network consisting of twoM/M/1service stations in tandem. The service rateu in [0, a]at station 1 is to be selected as a function of the state (x_{1}, x_{2}) where xiis the number of customers at stationiso as to minimize the expected total discounted or average cost corresponding to the instantaneous costc_{1}x_{1} + c_{2}x_{2}. The optimal policy is of the formu=aoru=0according asx_{1} < S(x_{2}) or x_{1} geq S(X_{2})andSis a switching function. For the case of discounted cost, the optimal process can be nonergodic, but it is ergodic for the case of average cost.     

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.     

Stationary probability distribution for states of G-networks with constrained sojourn time

We consider an exponential queueing network that differs from a Gelenbe network (with the usual positive and so-called negative customers), first, in that the sojourn time of customers at the network nodes is bounded by a random value whose conditional distribution for a fixed number of customers in a node is exponential. Second, we significantly relax the conditions on possible values of parameters for incoming Poisson flows of positive and negative customers in Gelenbe’s theorem. Claims serviced at the nodes and customers leaving the nodes at the end of their sojourn time can stay positive, become negative, or leave the network according to different routing matrices. We prove a theorem that generalizes Gelenbe’s theorem.     

Optimal balking strategies in single-server queues with general service and vacation times

In many service systems arising in OR/MS applications, the servers may be temporarily unavailable, a fact that affects the sojourn time of a customer and his willingness to join. Several studies that explore the balking behavior of customers in Markovian models with vacations have recently appeared in the literature. In the present paper, we study the balking behavior of customers in the single-server queue with generally distributed service and vacation times. Arriving customers decide whether to enter the system or balk, based on a linear reward-cost structure that incorporates their desire for service, as well as their unwillingness to wait. We identify equilibrium strategies and socially optimal strategies under two distinct information assumptions. Specifically, in a first case, the customers make individual decisions without knowing the system state. In a second case, they are informed about the server’s current status. We examine the influence of the information level on the customers’ strategic response and we compare the resulting equilibrium and socially optimal strategies.     

On conditions for a product-form stationary probability distribution of states of a multimode service network

We consider open and closed queueing networks with Markovian routing and symmetric service policies. Single-server nodes may operate in several modes. In each node, the amount of work required for servicing an arrival or for switching the mode is distributed arbitrarily. The performance rate for each of these operations depends on the residual amount of work. For open networks, the arrival flow is Poissonian. We establish conditions for a productform stationary distribution of states of the piecewise continuous process that describes the network behavior.     

On Taylor series expansions for waiting times in tandem queues: an algorithm for calculating the coefficients and an investigation of the approximation error

Recently, a Taylor series expansion was developed for expected stationary waiting times in open (max,+)-linear stochastic systems with Poisson input process; these systems cover various instances of queueing networks.As an application, we present an algorithm for calculating the coefficients for infinite capacity tandem queueing networks with discrete service-time distributions. The algorithm works quite efficiently if the random vector of the service times of all servers is concentrated at a small number of atoms. We investigate the relative error of the Taylor approximation by simulation; in many cases, it follows very well a simple expression which holds exactly for independent, exponentially distributed servers.     

Discrete time tandem networks of queues: Effects of different regulation schemes for simultaneous events

We consider tandem networks of discrete time Bernoulli servers with state dependent service rates and a state dependent Bernoulli arrival stream at the first node of the tandem. We investigate the effects of different regulation schemes for simultaneous events (e.g. joint arrivals and departures at some node, or joint departures at different nodes) on the performance behaviour of the network. The most serious effects occur with respect to arrival theorems which describe the distribution of the other customers present in the network and seen by an arriving customer, or observed by a customer during a jump inside the network. We prove necessary and sufficient conditions on the regulation scheme for a customer to observe always the time stationary behaviour of the network during his jumps. It turns out that we have to distinguish between local and global control for the regulation of simultaneous jumps. For different arrival schemes we compute the joint sojourn time distribution for a customer traversing the tandem. As a consequence we identify from this a regulation scheme which is known in the literature, where Little’s formula cannot be applied directly.     

Optimal allocation of a server between two queues with due times

Two queues share a single server. Arrivals to each queue have individual target due times for service completion (their due times are known to the controller) and a penalty is incurred when they stay in the system after the expiration of these due times. The two classes have different service requirements and incur penalty at different rates. The problem of dynamic priority assignment so as to minimize the discounted and average tardiness per customer is considered. The problem is formulated in discrete time where it is shown that, under the assumptions of geometric arrivals and geometric services, there is a nonidling stationary optimal preemptive policy. Within each class, the policy chooses, if at all, the customer with the smallest due time. A partial order on the space of the set of residual times is introduced. It is shown that the optimal choice of the customer class is monotonic with respect to this partial order; this implies a switchover-type property in the appropriate space. A combination of stochastic dominance and dynamic programming ideas is used to establish the results     

On the conditions for the existence of a stationary mode in a tandem of queuing systems with cyclic control in a random environment

A tandem of queuing systems for conflicting traffic flows is considered. The input flows are generated in a Markov random synchronous environment. In each system, the demands are served in the class of cyclic algorithms with readjustments. The serviced demands are transferred from the first system to the second one with a random speed. A mathematical model of the tandem as a homogeneous multidimensional countable Markov chain is considered. The necessary and sufficient conditions for the existence of a stationary mode are established.     

Information theoretic analysis for a general queueing system at equilibrium with application to queues in tandem

Summary In this paper, information theoretic inference methology for system modeling is applied to estimate the probability distribution for the number of customers in a general, single server queueing system with infinite capacity utilized by an infinite customer population. Limited to knowledge of only the mean number of customers and system equilibrium, entropy maximization is used to obtain an approximation for the number of customers in the G¦ G¦1 queue. This maximum entropy approximation is exact for the case of G=M, i.e., the M¦M¦1 queue. Subject to both independent and dependent information, an estimate for the joint customer distribution for queueing systems in tandem is presented. Based on the simulation of two queues in tandem, numerical comparisons of the joint maximum entropy distribution is given. These results serve to establish the validity of the inference technique and as an introduction to information theoretic approximation to queueing networks.This work was supported under a Naval Research Laboratory Fellowship under Grant N00014-83G-0203 and under an ONR Grant N00014-84K-0614 Former address:Westinghouse Defense and Electronics Center, Baltimore, MD, USA     

Simulation for passage times in closed, multiclass networks of queues with unrestricted priorities

Regenerative simulation for passage times in networks of queues with priorities among job classes (and one or more job types) can be based on observation of a fully augmented job stack process which maintains the position of each of the jobs in a linear ‘job stack’, an enumeration of the jobs by service center and job class. In this paper we develop an estimation procedure for passage times through a subnetwork of queues. Observed passage times for all the jobs enter into the construction of point and interval estimates. The confidence intervals obtained using this estimation procedure are shorter than those obtained from simulation using a marked job.     

A framework for the exact evaluation of expected cycle times in automated storage systems with full-turnover item allocation and random service requests

We present a new framework for obtaining analytic expressions of the expected throughput rate in Automated Storage and Retrieval Systems (AS/RSs). The models developed consider generalized full-turnover item allocation policies and random storage and retrieval requests. Both single command and dual command operations are considered. A general expression for the expected cycle time in a single command class-based system is also developed. It is shown that some well known results are derived as special cases of our expression. These results provide for rapid performance evaluation of various operational policies in automated warehouses and in certain mass-storage information devices currently used by various computer systems. The potential for significant reductions in the expected cycle time is demonstrated in the case of full-turnover item allocation.     

Invariance of the stationary distribution of states of multimode service policy networks

We consider open and closed preemptive-resume queueing systems with absolute priority of incoming customers. Single-server nodes have several service modes (regimes); the time of switching between the modes is exponential. Switching can be made to adjacent modes only. The amount of work required for servicing an incoming customer (workload) is a random variable with an arbitrary distribution function. For an open network, the input flow is Poissonian. We prove that the stationary distribution of the network states is invariant with respect to a functional form of workload distributions if the first moments are fixed.     

On busy period and sojourn time distributions in the M/G/1-EPS queue with catastrophes

We derive the Laplace-Stiltjes transforms of busy period and sojourn time distributions in the M/G/1 queue with egalitarian processor sharing (EPS) and the possibility of (external) catastrophes. Each arrival of the catastrophes immediately removes all the positive jobs (and hence unfinished work) in this non work-conserving queueing system. One of the main results is obtained by means of the so-called method of decomposition into delay elements introduced by the first author.     

On the distribution free continuous-review inventory model with a service level constraint

We consider a continuous-review (Q, r) inventory model with a fill rate service constraint and relax the assumption that the distribution of lead time demand is known. We adopt a distribution free approach: We assume that only the first two moments of the lead time demand distribution are known, and then, optimize the policy parameters against the worst possible distribution. We are able to derive closed-form expressions for the optimal order quantity and reorder point.     

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.     

Regenerative simulation of response times in networks of queues with multiple job types

We have previously discussed the simulation of networks of queues for general characteristics of passage times of a single job type, using the regenerative method for simulation and the idea of tracking a distinguished job through the network. We consider here, from a somewhat different point ov view, passage time simulation in closed networks of queues having multiple job types. Our results provide a means of obtaining, from a single replication, point and interval estimates for passage times of the several job types. They also yield a statistically more efficient estimation procedure for passage times of a single job type.