Tail asymptotics for the queue size distribution in the MAP/G/1 retrial queue

We consider a MAP/G/1 retrial queue where the service time distribution has a finite exponential moment. We derive matrix differential equations for the vector probability generating functions of the stationary queue size distributions. Using these equations, Perron–Frobenius theory, and the Karamata Tauberian theorem, we obtain the tail asymptotics of the queue size distribution. The main result on light-tailed asymptotics is an extension of the result in Kim et al. (J. Appl. Probab. 44:1111–1118, 2007) on the M/G/1 retrial queue.     

Single server retrial queues with two way communication

The main aim of this paper is to study the steady state behavior of an M/G/1-type retrial queue in which there are two flows of arrivals namely ingoing calls made by regular customers and outgoing calls made by the server when it is idle. We carry out an extensive stationary analysis of the system, including stability condition, embedded Markov chain, steady state joint distribution of the server state and the number of customers in the orbit (i.e., the retrial group) and calculation of the first moments. We also obtain light-tailed asymptotic results for the number of customers in the orbit. We further formulate a more complicate but realistic model where the arrivals and the service time distributions are modeled in terms of the Markovian arrival process (MAP) and the phase (PH) type distribution.     

A MAP/G/1 Queue with Negative Customers

In this paper, we consider a MAP/G/1 queue with MAP arrivals of negative customers, where there are two types of service times and two classes of removal rules: the RCA and RCH, as introduced in section 2. We provide an approach for analyzing the system. This approach is based on the classical supplementary variable method, combined with the matrix-analytic method and the censoring technique. By using this approach, we are able to relate the boundary conditions of the system of differential equations to a Markov chain of GI/G/1 type or a Markov renewal process of GI/G/1 type. This leads to a solution of the boundary equations, which is crucial for solving the system of differential equations. We also provide expressions for the distributions of stationary queue length and virtual sojourn time, and the Laplace transform of the busy period. Moreover, we provide an analysis for the asymptotics of the stationary queue length of the MAP/G/1 queues with and without negative customers.     

Asymptotic expansions for waiting time probabilities in an M/G/1 queue with long-tailed service time

We consider anM/G/1 queue with FCFS queue discipline. We present asymptotic expansions for tail probabilities of the stationary waiting time when the service time distribution is longtailed and we discuss an extension of our methods to theM ^[x]/G/1 queue with batch arrivals.     

Single-Server Queue with Markov-Dependent Inter-Arrival and Service Times

In this paper we study a single-server queue where the inter-arrival times and the service times depend on a common discrete time Markov chain. This model generalizes the well-known MAP/G/1 queue by allowing dependencies between inter-arrival and service times. The waiting time process is directly analyzed by solving Lindley's equation by transform methods. The Laplace–Stieltjes transforms (LST) of the steady-state waiting time and queue length distribution are both derived, and used to obtain recursive equations for the calculation of the moments. Numerical examples are included to demonstrate the effect of the autocorrelation of and the cross-correlation between the inter-arrival and service times. An erratum to this article is available at .     

The G/M/1 queue revisited

The G/M/1 queue is one of the classical models of queueing theory. The goal of this paper is two-fold: (a) To introduce new derivations of some well-known results, and (b) to present some new results for the G/M/1 queue and its variants. In particular, we pay attention to the G/M/1 queue with a set-up time at the start of each busy period, and the G/M/1 queue with exceptional first service. Dedicated to Arie Hordijk on his 65th birthday, in friendship and admiration.     

MAP 1, MAP2 /M/c retrial queue with guard channels and its application to cellular networks

In this paper, we investigate the impact of retrial phenomenon on loss probabilities and compare loss probabilities of several channel allocation schemes giving higher priority to hand-off calls in the cellular mobile wireless network. In general, two channel allocation schemes giving higher priority to hand-off calls are known; one is the scheme with the guard channels for hand-off calls and the other is the scheme with the priority queue for hand-off calls. For mathematical unified model for both schemes, we consider theMAP ₁,MAP ₂ /M/c/b, ∞ retrial queue with infinite retrial group, geometric loss, guard channels and finite priority queue for hand-off class. We approximate the joint distribution of two queue lengths by Neuts' method and also obtain waiting time distribution for hand-off calls. From these results, we obtain the loss probabilities, the mean waiting time and the mean queue lengths. We give numerical examples to show the impact of the repeated attempt and to compare loss probabilities of channel allocation schemes.     

On the Nonexistence of Global Weak Solutions to the Navier–Stokes–Poisson Equations in ℝ N

In this paper we prove nonexistence of stationary weak solutions to the Euler–Poisson equations and the Navier–Stokes–Poisson equations in ? ^N , N ≥ 2, under suitable assumptions of integrability for the density, velocity and the potential of the force field. For the time dependent Euler–Poisson equations we prove nonexistence result assuming additionally temporal asymptotic behavior near infinity of the second moment of density. For a class of time dependent Navier–Stokes–Poisson equations in ? ^N this asymptotic behavior of the density can be proved if we assume the standard energy inequality, and therefore the nonexistence of global weak solution follows from more plausible assumption in this case.     

M x /G/1 Queue with Multiple Vacations

Abstract

In this article, we study a queueing system M ^x /G/1 with multiple vacations. The probability generating function (P.G.F.) of stationary queue length and its expectation expression are deduced by using an embedded Markov chain of the queueing process. The P.G.F. of stationary system busy period and the probability of system in service state and vacation state also are obtained by the same method. At last we deduce the LST and mean of stationary waiting time in the service order FCFS and LCFS, respectively.     

On the Queue Length Distribution for the GI/G/1/K/VM Queue

Abstract

We present a transform-free distribution of the steady-state queue length for the GI/G/1/K queueing system with multiple vacations under exhaustive FIFO service discipline. The method we use is a modified supplementary variable technique and the result we obtain is expressed in terms of conditional expectations of the remaining service time, the remaining interarrival time, and the remaining vacation, conditional on the queue length at the embedded points. The case K → ∞ is also considered.     

Large-time asymptotics for the Gt/Mt/st+GIt many-server fluid queue with abandonment

We previously introduced and analyzed the G _t /M _t /s _t +GI _t many-server fluid queue with time-varying parameters, intended as an approximation for the corresponding stochastic queueing model when there are many servers and the system experiences periods of overload. In this paper, we establish an asymptotic loss of memory (ALOM) property for that fluid model, i.e., we show that there is asymptotic independence from the initial conditions as time t evolves, under regularity conditions. We show that the difference in the performance functions dissipates over time exponentially fast, again under the regularity conditions. We apply ALOM to show that the stationary G/M/s+GI fluid queue converges to steady state and the periodic G _t /M _t /s _t +GI _t fluid queue converges to a periodic steady state as time evolves, for all finite initial conditions.     

An M/G/1 unreliable retrial queue with two phases of service and Bernoulli admission mechanism

This paper deals with the steady state behaviour of an M^X/G/1 retrial queue with an additional second phase of optional service and unreliable server where breakdowns occur randomly at any instant while serving the customers. Further concept of Bernoulli admission mechanism is also introduced in the model. This model generalizes both the classical M^X/G/1 retrial queue subject to random breakdown and Bernoulli admission mechanism as well as M^X/G/1 queue with second optional service and unreliable server. We carry out an extensive analysis of this model.     

Conditional and unconditional distributions forM/G/1 type queues with server vacations

M/G/1 queues with server vacations have been studied extensively over the last two decades. Recent surveys by Boxma [3], Doshi [5] and Teghem [14] provide extensive summary of literature on this subject. More recently, Shanthikumar [11] has generalized some of the results toM/G/1 type queues in which the arrival pattern during the vacations may be different from that during the time the server is actually working. In particular, the queue length at the departure epoch is shown to decompose into two independent random variables, one of which is the queue length at the departure epoch (arrival epoch, steady state) in the correspondingM/G/1 queue without vacations. Such generalizations are important in the analysis of situations involving reneging, balking and finite buffer cyclic server queues. In this paper we consider models similar to the one in Shanthikumar [11] but use the work in the system as the starting point of our investigation. We analyze the busy and idle periods separately and get conditional distributions of work in the system, queue length and, in some cases, waiting time. We then remove the conditioning to get the steady state distributions. Besides deriving the new steady state results and conditional waiting time and queue length distributions, we demonstrate that the results of Boxma and Groenendijk [2] follow as special cases. We also provide an alternative approach to deriving Shanthikumar's [11] results for queue length at departure epochs.     

Impact of Bursty Traffic on Queues

The impact of bursty traffic on queues is investigated in this paper. We consider a discrete-time single server queue with an infinite storage room, that releases customers at the constant rate of c customers/slot. The queue is fed by an M/G/∞ process. The M/G/∞ process can be seen as a process resulting from the superposition of infinitely many ‘sessions’: sessions become active according to a Poisson process; a station stays active for a random time, with probability distribution G, after which it becomes inactive. The number of customers entering the queue in the time-interval [t, t + 1) is then defined as the number of active sessions at time t (t = 0,1, ...) or, equivalently, as the number of busy servers at time t in an M/G/∞ queue, thereby explaining the terminology. The M/G/∞ process enjoys several attractive features: First, it can display various forms of dependencies, the extent of which being governed by the service time distribution G. The heavier the tail of G, the more bursty the M/G/∞ process. Second, this process arises naturally in teletraffic as the limiting case for the aggregation of on/off sources [27]. Third, it has been shown to be a good model for various types of network traffic, including telnet/ftp connections [37] and variable-bit-rate (VBR) video traffic [24]. Last but not least, it is amenable to queueing analysis due to its very strong structural properties. In this paper, we compute an asymptotic lower bound for the tail distribution of the queue length. This bound suggests that the queueing delays will dramatically increase as the burstiness of the M/G/∞ input process increases. More specifically, if the tail of G is heavy, implying a bursty input process, then the tail of the queue length will also be heavy. This result is in sharp contrast with the exponential decay rate of the tail distribution of the queue length in presence of ‘non-bursty’ traffic (e.g. Poisson-like traffic). This revised version was published online in August 2006 with corrections to the Cover Date.     

A Regularly Preemptive Model and its Approximations

A regularly preemptive model D,MAP/D ₁,D ₂/1 is studied. Priority customers have constant inter-arrival times and constant service times. On the other hand, ordinary customers' arrivals follow a Markovian Arrival Process (MAP) with constant service times. Although this model can be formulated by using the piecewise Markov process, there remain some difficult problems on numerical calculations. In order to solve these problems, a novel approximation model MAP/MR/1 with Markov renewal services is proposed. These two queueing processes become different due to the existence of idle periods. Thus, a MAP/MR/1 queue with a general boundary condition is introduced. It is a model with the exceptional first service in each busy period. In particular, two special models are studied: one is a warm-up queue and the other is a cool-down queue. It can be proved that the waiting time of ordinary customers for the regular preemption model is stochastically smaller than the waiting time of the former model. On the other hand, it is stochastically larger than the waiting time of the latter model.     

Approximations for the delay probability in the M/G/s queue

This paper develops approximations for the delay probability in an M/G/s queue. For M/G/s queues, it has been well known that the delay probability in the M/M/s queue, i.e., the Erlang delay formula, is usually a good approximation for other service-time distributions. By using an excellent approximation for the mean waiting time in the M/G/s queue, we provide more accurate approximations of the delay probability for small values of s. To test the quality of our approximations, we compare them with the exact value and the Erlang delay formula for some particular cases.     

Zero divisors and units with small supports in group algebras of torsion-free groups

Kaplansky’s zero divisor conjecture (unit conjecture, respectively) states that for a torsion-free group G and a field 𝔽, the group ring 𝔽[G] has no zero divisors (has no units with supports of size greater than 1). In this paper, we study possible zero divisors and units in 𝔽[G] whose supports have size 3. For any field 𝔽 and all torsion-free groups G, we prove that if αβ = 0 for some non-zero α,β∈𝔽[G] such that |supp(α)| = 3, then |supp(β)|≥10. If 𝔽 = 𝔽₂ is the field with 2 elements, the latter result can be improved so that |supp(β)|≥20. This improves a result in Schweitzer [J. Group Theory, 16 (2013), no. 5, 667–693]. Concerning the unit conjecture, we prove that if αβ = 1 for some α,β∈𝔽[G] such that |supp(α)| = 3, then |supp(β)|≥9. The latter improves a part of a result in Dykema et al. [Exp. Math., 24 (2015), 326–338] to arbitrary fields.     

Analysis of BMAP/G/1 Queue with Reservation of Service

Abstract

In this article, we study BMAP/G/1 queue with service time distribution depending on number of processed items. This type of queue models the systems with the possibility of preliminary service. For the considered system, an efficient algorithm for calculating the stationary queue length distribution is proposed, and Laplace–Stieltjes transform of the sojourn time is derived. Little's law is proved. An optimization problem is considered.     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.