On a singular feature of critical G/M/1 queues

In this paper, we consider a critically loaded G/M/1 queue and contrast its transient behaviour with the transient behaviour of stable (or unstable) G/M/1 queues. We show that the departure process from a critical G/M/1 queue converges weakly to a Poisson process. However, as opposed to the stable (or unstable) case, we show that the departure process of a critical GI/M/1 queue does not couple in finite time with a Poisson process (even though it converges weakly to one). Thus, as the traffic intensity (ratio of arrival to service rates), , ranges over (0, ∞), the point = 1 represents a singularity with regard to the convergence mode of the departure process.     

A polynomial factorization approach to the discrete time GI/G/1/(N) queue size distribution

The queue of a single server is considered with independent and identically distributed interarrivai and service times and an infinite (GI/G/1) or finite (GI/G/1/N) waiting room. The queue discipline is non-preemptive and independent of the service times.

A discrete time version of the system is analyzed, using a two-component state model at the arrival and departure instants of customers. The equilibrium equations are solved by a polynomial factorization method. The steady state distribution of the queue size is then represented as a linear combination of geometrical series, whose parameters are evaluated by closed formulae depending on the roots of a characteristic polynomial.

Considering modified boundary constraints, systems with finite waiting room or with an exceptional first service in each busy period are included.     

A note on the departure process in an (S− 1, S) inventory system

Steady-state distribution functions are derived for interdeparture time (of filled requests) in an (S?1,S) inventory system in which (demand) arrival process is Poisson, replenishment times are independently and identically distributed negative exponential variates, and service is on a first-come-first-served basis. The departure process proves to be identical to the arrival process. Some implications of this property in the study of queueing networks with (S ? 1,S) inventory stations are discussed.     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

Loss probabilities of hand-in traffic under various protocols: II. Model comparisons

Mobile telephone traffic business demands that a given base station be able to handle both newly originating traffic and hand-off traffic from neighboring base stations, with priority to be given to the latter, existing traffic. This paper examines three access control protocols that give such traffic priority by specifying a reserve capacity R amongst the N_tot channels, where R need not be an integer. Assuming a Poisson arrival process and independent exponential service times, it is shown via birth–death processes, sample path constructions and stochastic monotonicity results for Markov processes that pairwise comparison of the protocols considered is possible, and, in particular, that one of them is ‘best’ in terms of the smallest loss probability of one type of traffic for a given rate of loss for the other type. Results proved via sample path constructions hold under weaker conditions of stationary ergodic arrival processes and exponential service times.     

Analysis of a tandem queue with state-dependent general blocking: A GSMP perspective

In this paper, we study a tandem queue where there is a finite number of buffer positions at each stage. The blocking scheme is general in the sense that it can model a number of classical blocking schemes, including communication, manufacturing and kanban blockings as special cases. The system considered here differs from the conventional system in two aspects: (1) departure of jobs from the system is determined by an external arrival process of another queue lying parallel to the tandem queue; (2) the control parameters of the blocking scheme are state-dependent in that they may change values depending on the state of the system.

We model this system as a generalized semi-Markov process (GSMP), we study the structural properties of its scheme, and establish monotonicity and convexity properties of event times with respect to both the clock times and the integer blocking parameters. In particular, we demonstrate that the state-dependent scheme is “better”, in certain sense, than the corresponding static scheme. Our results also recover the structural properties previously established for the classical blockings.     

Approximation models of feed-forward G/G/1/N queueing networks with correlated arrivals

In this paper we develop approximation models for feed-forward networks of G/G/1/N queues. We use Linear Algebra Queueing Theory (LAQT) techniques to create reduced state space representations for the queue departure processes. Reduced state space departure processes are presented where the first three moments and the correlation decay are mapped to a two state process. A three state process is also presented matching the first five moments and the first three lag autocorrelations. Numerical examples of end-to-end performance for high-speed communications networks with correlated arrival traffic are presented. The results are compared with simulation models and other approximation methods.     

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.     

Overload control for short message transfer in GPRS/UMTS networks

In the General Packet Radio Service (GPRS)/Universal Mobile Telecommunications System (UMTS) short message service (SMS) network, the serving GPRS support node (SGSN) stores the message in a queue until it is successfully transferred to the mobile device or its maximum waiting time expires. The queued message is forwarded to the new SGSN and is immediately removed from the waiting queue of the old SGSN, if the corresponding mobile device leaves the old SGSN area before the valid queueing time expires. Once the SGSN's buffer is full, all incoming messages must be discarded and retransmitted later. Under this situation, the messages, especially the forwarded messages, suffer from a longer delay before being successfully delivered. To prevent messages from being excessively delayed, this paper proposes an SGSN overload control scheme called the N-overload scheme. According to this scheme, a newly arriving message is discarded if the buffer is full upon its arrival. A forwarded message, however, is queued in an overload space of size N. Taking the forwarding and the expiration effects of queued messages into account, this paper also develops an analytical model to study the performance for the SGSN using the N-overload scheme. On the basis of the analysis, the optimal value of N is numerically determined so that the loss probability for the forwarded messages is minimized.     

The interdeparture time distribution for each class in the ∑Mi/Gi/1 queue with set-up times and repeated server vacations

This paper studies the interdeparture time distribution of one class of customers who arrive at a single server queue where customers of several classes are served and where the server takes a vacation whenever the system becomes empty or is empty when the server returns from a vacation. Furthermore, the first customer in the busy period is allowed to have an exceptional service time (set-up time), depending on the class to which this customer belongs. Batches of customers of each class arrive according to independent Poisson processes and compete with each other on a FIFO basis. All customers who belong to the same class are served according to a common generally distributed service time. Service times, batch sizes and the arrival process are all assumed to be mutually independent. Successive vacation times of the server form independent and identically distributed sequences with a general distribution.For this queueing model we obtain the Laplace transform of the interdeparture time distribution for each class of customers whose batch size is geometrically distributed. No explicit assumptions of the batch size distributions of the other classes of customers are necessary to obtain the results.The paper ends by showing how the mathematical results can be used to evaluate a protocol that controls access to a shared medium of an ATM passive optical network. The numerical results presented in the last section of this paper show that the bundle spacing principle that is used by the permit distribution algorithm of this protocol introduces high delays and in many cases also more variable interdeparture times for the ATM cells of individual connections. An alternative algorithm is proposed that does not cope with these performance short comings and at the same time conserves the good properties of the protocol.     

An approximate transient analysis of the M(t)/M/1 queue

An approach, based on recent work by Stern [56], is described for obtaining the approximate transient behavior of both the M/M/1 and M(t)/M/1 queues, where the notation M(t) indicates an exponential arrival process with time-varying parameter λ(t). The basic technique employs an M/M/1K approximation to the M/M/1 queue to obtain a spectral representation of the time-dependent behavior for which the eigen values and eigenvectors are real.Following a general survey of transient analysis which has already been accomplished, Stern's M/M/1/K approximation technique is examined to determine how best to select a value for K which will yield both accurate and computationally efficient results. It is then shown how the approximation technique can be extended to analyze the M(t)/M/1 queue where we assume that the M(t) arrival process can be approximated by a discretely time-varying Poisson process.An approximate expression for the departure process of the M/M/1 queue is also proposed which implies that, for an M(t)/M/1 queue whose arrival process is discretely time-varying, the departure process can be approximated as discretely time-varying too (albeit with a different time-varying parameter).In all cases, the techniques and approximations are examined by comparison with exact analytic results, simulation or alternative discrete-time approaches.     

Stability, queue length, and delay of deterministic and stochasticqueueing networks

We present two types of stability problems: 1) conditions for queueing networks that render bounded queue lengths and bounded delay for customers, and 2) conditions for queueing networks in which the queue length distribution of a queue has an exponential tail with rate &thetas;. To answer these two types of stability problems, we introduce two new notions of traffic characterization: minimum envelope rate (MER) and MER with respect to &thetas;. We also develop a set of rules for network operations such as superposition, input-output relation of a single queue, and routing. Specifically, we show that: 1) the MER of a superposition process is less than or equal to the sum of the MER of each process, 2) a queue is stable in the sense of bounded queue length if the MER of the input traffic is smaller than the capacity, 3) the MER of a departure process from a stable queue is less than or equal to that of the input process, and 4) the MER of a routed process from a departure process is less than or equal to the MER of the departure process multiplied by the MER of the routing process. Similar results hold for MER with respect to &thetas; under a further assumption of independence. For single class networks with nonfeedforward routing, we provide a new method to show that similar stability results hold for such networks under the first come, first served policy. Moreover, when restricting to the family of two-state Markov modulated arrival processes, the notion of MER with respect to &thetas; is shown to be equivalent to the recently developed notion of effective bandwidth in communication networks     

Burstiness in broadband integrated networks

Since broadband integrated networks have to cope with a wide range of bit rates, the notion of burstiness which expresses the irregularity of a flow, has been recognized as a vital question for such networks. In burstiness characterization encountered in the literature, special attention is given to the squared coefficient of variation of interarrival time (Cv²) in a cell arrival process. In order to observe the impact of a bursty flow on a queue, we introduce in this paper a new class of arrival process, the n-stage Markov Modulated Bernoulli Process, MMBP_n, for short, and its peculiar case, the n-stage Hyper-Bernoulli process, denoted by HBP_n. We numerically solve the MMBP_n/D/1/K and we compute in particular the rejection probability and the mean waiting time. For that purpose, a relation between the stationary queue length distribution and arrival time distribution is established. This relation adapts the GASTA equality to the arrival process under consideration. We then discuss the relevance of Cv² for burstiness characterization through an example: the HBP₂/D/1/K queue. We show that Cv² becomes significant only when local overload occurs, i.e., when the arrival rate is momentarily greater than the server rate. The results are then applied to two basic ATM problems: traffic characterization and buffer dimensioning using bursty inputs.     

A note on varying the number of states in the arrival process of MR/GI/1 queue

A single server queue with an autocorrelated arrival process is considered. A specific way of changing the number of states in the arrival process is introduced which enables us to extract the pure effect of the number of different types of arrivals on the queueing performance measures. We see that increasing the number of arrival types makes the arrival stream more correlated and causes longer waiting times in the system. This impact is much stronger when the successive arrival types tends to be the same under heavy traffic.     

On the overflow processes from the PH1 + PH2/M/S/K queue with two independent PH-renewal inputs

This paper presents an analysis of overflow processes from a PH₁ + PH₂/M/S/K queue having two independent phase type renewal input streams. Both the superposed overflow process and individual overflow processes for the PH₁- and PH₂-streams are analyzed using first passage time distributions for the number of customers in the system. Each overflow process is characterized as a Markov renewal process. The nth moment of the number of customers in an infinite server group to which these overflows have been offered is derived using a theory for the MR/M/∞ queue with a Markov renewal input. The numerical examples for means and variance-to-mean ratios (peakednesses) of the individual overflow streams are given for an H₂ + H₂/M/S/S queue with interrupted Poisson inputs, which is a vital model for telephone network planning. In addition, overflow traffic characteristics are discussed by using these examples.     

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.     

Analysis of a finite buffer queue with different scheduling and push-out schemes

A queueing system M₁, M₂/G₁, G₂/1/N with different scheduling and push-out scheme is analyzed in this paper. This work is motivated by the study of the performance of an output link of ATM switches with traffic of two classes with different priorities. However, the queueing model developed in this paper is more general than that of the output link of ATM switches with two-class priority traffic. General service time distributions are allowed for classes 1 and 2 and a general service discipline function, ₁(i, j), is introduced where ₁(i, j) is the probability that a class 1 packet will be served, given that there are i class 1 and j class 2 packets waiting for service. An exact solution is obtained for the loss probabilities for classes 1 and 2, the queue length distribution and the mean waiting time for class 1. The queue length distribution and the mean waiting time for class 2 are calculated approximately. It is shown that the approximation is an upper bound and the error due to the approximation is very small when the loss probability of class 2 is small (e.g., less than 0.01).     

CIPP — a versatile analytical model for VBR traffic

Correlated interarrival time Poisson process (CIPP) has been proposed in Proceedings of the Fifth Biennial Conference on Signal Processing and Communications (SPCOM’99), IISc, Bangalore, July 1999, pp. 43–50; J. Indian Inst. Sci. 79 (3) (1999) 233–249] for modeling both the composite arrival process of packets in broadband networks and the individual video source modeling. The CIPP — a generalization of the Poisson process — is a stationary counting process and is parameterized by correlation parameter ‘ρ’, the degree of correlation in adjacent interarrivals and ‘λ’, the intensity of the process. In this paper, we develop the theory for CIPP/M/1 queue and undertake the performance modeling of statistical multiplexer with VBR video traffic in broadband networks using the CIPP/M/1 queue. We first derive the expressions for stationary distributions for queue length and waiting time in a CIPP/M/1 queue. Then, we derive the queuing performance measures of interest. For reasons of feasibility of theoretical performance modeling and realistic compulsions, we propose a deterministic smoothing with random (geometrically distributed) packet sizes. We simulate a queue with (thus smoothed) VBR video trace data as input to compare with the theoretical performance measures derived above. Experimental results show that the CIPP/M/1 queue models well the statistical multiplexer performance with the real-world MPEG-1 VBR video traffic input.     

The departure process of a quorum queueing system

We study in this paper the departure process of a bulk service queueing system. The server operates under a minimum batch size strategy. We characterize the departure process through the distribution of the interdeparture times of batches and of customers, the distribution of the number of customers in a batch, and the coefficient of correlation between the interdeparture time of a batch and the number of customers in the batch. A numerical illustration is presented.