Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the area swept under the occupation process of an M/M/1 queue in a busy period

We compute in this paper the distribution of the area swept under the occupation process of an M/M/1 queue during a busy period. For this purpose, we use the expression of the Laplace transform of the random variable established in earlier studies as a fraction of Bessel functions. To get information on the poles and the residues of , we take benefit of the fact that this function can be represented by a continued fraction. We then show that this continued fraction is the even part of an S fraction and we identify its successive denominators by means of Lommel polynomials. This allows us to numerically evaluate the poles and the residues. Numerical evidence shows that the poles are very close to the numbers as . This motivated us to formulate some conjectures, which lead to the derivation of the asymptotic behaviour of the poles and the residues. This is finally used to derive the asymptotic behaviour of the probability survivor function . The outstanding property of the random variable is that the poles accumulate at 0 and its tail does not exhibit a nice exponential decay but a decay of the form for some positive constants c and , which indicates that the random variable has a Weibull-like tail. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic Analysis of the GI/M/ 1 /n Loss System as n Increases to Infinity

This paper provides the asymptotic analysis of the loss probability in the GI/M/1/n queueing system as n increases to infinity. The approach of this paper is alternative to that of the recent papers of Choi and Kim (2000) and Choi et al. (2000) and based on application of modern Tauberian theorems with remainder. This enables us to simplify the proofs of the results on asymptotic behavior of the loss probability of the abovementioned paper of Choi and Kim (2000) as well as to obtain some new results.     

A Cramér Type Large Deviation Result for Student's t-Statistic

Let X, X ₁, X ₂,... be independent and identically distributed random variables with a finite third moment, and let T _n be the Student's t-statistic. This paper shows that lim _n P(T _n>x)/P(t _n>x)=1 holds uniformly in 0xo(n ^1/6), where t _n has a t-distribution with n–1 degrees of freedom. An example is also given to show that a finite third moment is necessary for this result.     

On weighted densities

The continuity of densities given by the weight functions n ^α , α ∈ [−1, ∞[, with respect to the parameter α is investigated. This work is supported by MIUR Italy, Program Barrande n. 2003-009-2, MSM6198898701 and GA ČR no. 201/04/0381.     

Asymptotic Behavior of Loss Probability in GI/M/1/K Queue as K Tends to Infinity

We obtain an asymptotic behavior of the loss probability for the GI/M/1/K queue as K for cases of <1, >1 and =1.     

Design of a production system with a feedback buffer

In this paper, we deal with an M/G/1 Bernoulli feedback queue and apply it to the design of a production system. New arrivals enter a “main queue” before processing. Processed items leave the system with probability 1-p or are fed back with probability p into an intermediate finite “feedback queue”. As soon as the feedback queue is fully occupied, the items in the feedback queue are released, all at a time, into the main queue for another processing. Using transform methods, various performance measures are derived such as the joint distribution of the number of items in each queue and the dispatching rate. We then derive the optimal buffer size which minimizes the overall operating cost under a cost structure. This revised version was published online in June 2006 with corrections to the Cover Date.     

Models and Approximations for Call Center Design

A call center is a facility for delivering telephone service, both incoming and outgoing. This paper addresses optimal staffing of call centers, modeled as M/G/n queues whose offered traffic consists of multiple customer streams, each with an individual priority, arrival rate, service distribution and grade of service (GoS) stated in terms of equilibrium tail waiting time probabilities or mean waiting times. The paper proposes a methodology for deriving the approximate minimal number of servers that suffices to guarantee the prescribed GoS of all customer streams. The methodology is based on an analytic approximation, called the Scaling-Erlang (SE) approximation, which maps the M/G/n queue to an approximating, suitably scaled M/G/1 queue, for which waiting time statistics are available via the Pollaczek-Khintchine formula in terms of Laplace transforms. The SE approximation is then generalized to M/G/n queues with multiple types of customers and non-preemptive priorities, yielding the Priority Scaling-Erlang (PSE) approximation. A simple goal-seeking search, utilizing SE/PSE approximations, is presented for the optimal staffing level, subject to GoS constraints. The efficacy of the methodology is demonstrated by comparing the number of servers estimated via the PSE approximation to their counterparts obtained by simulation. A number of case studies confirm that the SE/PSE approximations yield optimal staffing results in excellent agreement with simulation, but at a fraction of simulation time and space.     

Lack of Invariant Property of the Erlang Loss Model in Case of <Emphasis Type="Italic">MAP</Emphasis> Input

The BMAP/PH/N/0 model with three different disciplines of admission (partial admission, complete rejection, complete admission) is investigated. Loss probability is calculated. Impact of the admission discipline, variation and correlation coefficients of inter-arrival times distribution, and variation of service times distribution on loss probability is analyzed numerically. As by-product, it is shown by means of numerical results that the invariant property of the famous Erlang M/G/N/0 system, which was proven by B. A. Sevastjanov, is absent in case of the MAP input. AMS subject classification: Primary 60K25, 60K20 This revised version was published online in June 2005 with corrected coverdate     

Asymptotics for M/G/1 low-priority waiting-time tail probabilities

We consider the classical M/G/1 queue with two priority classes and the nonpreemptive and preemptive-resume disciplines. We show that the low-priority steady-state waiting-time can be expressed as a geometric random sum of i.i.d. random variables, just like the M/G/1 FIFO waiting-time distribution. We exploit this structures to determine the asymptotic behavior of the tail probabilities. Unlike the FIFO case, there is routinely a region of the parameters such that the tail probabilities have non-exponential asymptotics. This phenomenon even occurs when both service-time distributions are exponential. When non-exponential asymptotics holds, the asymptotic form tends to be determined by the non-exponential asymptotics for the high-priority busy-period distribution. We obtain asymptotic expansions for the low-priority waiting-time distribution by obtaining an asymptotic expansion for the busy-period transform from Kendall's functional equation. We identify the boundary between the exponential and non-exponential asymptotic regions. For the special cases of an exponential high-priority service-time distribution and of common general service-time distributions, we obtain convenient explicit forms for the low-priority waiting-time transform. We also establish asymptotic results for cases with long-tail service-time distributions. As with FIFO, the exponential asymptotics tend to provide excellent approximations, while the non-exponential asymptotics do not, but the asymptotic relations indicate the general form. In all cases, exact results can be obtained by numerically inverting the waiting-time transform. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Asymptotic results for the superposition of a large number of data connections on an ATM link

The M/PH/∞ system is introduced in this paper to analyze the superposition of a large number of data connections on an ATM link. In this model, information is transmitted in bursts of data arriving at the link as a Poisson process of rate λ and burst durations are PH distributed with unit mean. Some transient characteristics of the M/PH/∞ system, namely the duration θ of an excursion by the occupation process {X_t} above the link transmission capacity C, the area V swept under process {X_t} above C and the number of customers arriving in such an excursion period, are introduced as performance measures. Explicit methods of computing their distributions are described. It is then shown that, as conjectured in earlier studies, random variables Cθ,CV and N converge in distribution as C tends to infinity while the utilization factor of the link defined by γ = λ/C is fixed in (0,1), towards some transient characteristics of an M/M/1 queue with input rate γ and unit service rate. Further simulation results show that after adjustment of the load of the M/M/1 queue, a similar convergence result holds for the superposition of a large number of On/Off sources with various On and Off period distributions. This shows that some transient quantities associated with an M/M/1 queue can be used in the characterization of open loop multiplexing of a large number of On/Off sources on an ATM link. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the complete monotonicity of the waiting time density in some GI/G/k systems

In this note the complete monotonicity of the waiting time density in GI/G/k queues is proved under the assumption that the service time density is completely monotone. This is an extension of Keilson's [3] result for M/G/1 queues. We also provide another proof of the result that complete monotonicity is preserved by geometric compounding.     

The infinite server queue and heuristic approximations to the multi-server queue with and without retrials

In this paper, properties of the time-dependent state probabilities of theM _t /G/∞ queue, when the queue is assumed to start empty are studied. Those results are compared with corresponding time-dependent results for theM/M/1 queue. Approximation to the time-dependent state probabilities of theM/G/m/m queue by means of the corresponding time-dependent state probabilities of theM/G/∞ queue are discussed. Through a decomposition formula it is shown that the main performance characteristics of the ergodicM/M/m/m+d queue are sums of the corresponding random variables for the ergodicM/M/m/m andM/M/1/1+(d−1) queues, respectively, weighted by the 3-rd Erlang formula (stationary probability of waiting or being lost for theM/M/m/m+d queue). Successful exact and approximation extensions of this kind of decomposition formula to theM/M/m/m+d queue with retrials are presented.     

The PH/PH/1 queue at epochs of queue size change

The PH/PH/1 queue is considered at embedded epochs which form the union of arrival and departure instants. This provides us with a new, compact representation as a quasi-birth-and-death process, where the order of the blocks is the sum of the number of phases in the arrival and service time distributions. It is quite easy to recover, from this new embedded process, the usual distributions at epochs of arrival, or epochs of departure, or at arbitrary instants. The quasi-birth-and-death structure allows for efficient algorithmic procedures. This revised version was published online in June 2006 with corrections to the Cover Date.     

Semi-Invertible Extensions and Asymptotic Homomorphisms

We consider the semi-group Ext(A, B) of extensions of a separable C ^*-algebra A by a stable C ^*-algebra B modulo unitary equivalence and modulo asymptotically split extensions. This semi-group contains the group Ext^–1/2(A, B) of invertible elements (i.e. of semi-invertible extensions). We show that the functor Ext^–1/2(A, B) is homotopy invariant and that it coincides with the functor of homotopy classes of asymptotic homomorphisms from C A to M(B) that map S A C( ) A into B.     

Equivalence of the C*-Algebras qℂ and C 0(ℝ2) in the Asymptotic Category

The results of Kasparov, Connes, Higson, and Loring imply the coincidence of the functors [[qℂ ⊗ K, B ⊗ K]] = [[C ₀(ℝ²) ⊗ K, B ⊗ K]] for any C*-algebra B; here[[A, B]] denotes the set of homotopy classes of asymptotic homomorphisms from A to B. Inthe paper, this assertion is strengthened; namely, it is shown that the algebras qℂ ⊗ K and C ₀(ℝ²) ⊗ K are equivalent in the category whose objects are C*-algebras and morphisms are classes of homotopic asymptotic homomorphisms. Some geometric properties of the obtained equivalence are studied. Namely, the algebras qℂ ⊗ K and C ₀(ℝ²) ⊗ K are represented as fields of C*-algebras; it is proved that the equivalence is not fiber-preserving, i.e., is does not take fibers to fibers. It is also proved that the algebras under consideration are not homotopy equivalent.__________Translated from Matematicheskie Zametki, vol. 77, no. 5, 2005, pp. 788–796.Original Russian Text Copyright ©2005 by T. V. Shul’man.     

L ∞ — Decay estimations of the spherical mean value on symmetric spaces

LetM _t[](x) be the spherical mean value operator applied to a function on a symmetric Riemannian space of the non-compact type.L —decay estimations forM _t [](x) as well as for its derivatives with respect to (t, x) are given, provided that belongs to a Banach space with suitable weighted supremum norm. This leads to estimates of the solutions to the wave equation in certain cases in which Huygens' principle is valid.     

Fluid approximations for a processor-sharing queue

In this paper a fluid approximation, also known as a functional strong law of large numbers (FSLLN) for a GI/G/1 queue under a processor-sharing service discipline is established and its properties are analysed. The fluid limit depends on the arrival rate, the service time distribution of the initial customers, and the service time distribution of the arriving customers. This is in contrast to the known result for the GI/G/1 queue under a FIFO service discipline, where the fluid limit is piecewise linear and depends on the service time distribution only through its mean. The piecewise linear form of the limit can be recovered by an equilibrium type choice of the initial service distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Efficient Estimation in a Semiparametric Autoregressive Model

This paper constructs efficient estimates of the parameter in the semiparametric auto-regression model ,with a smooth function and independent and identically distributed innovations _t with zero means and finite variances. This will be done under the assumptions that and that the errors have a density with finite Fisher information for location. The former condition guarantees that the process can be chosen to be stationary and ergodic.