Sojourn time tails in the single server queue with heavy-tailed service times

We consider the GI/GI/1 queue with regularly varying service requirement distribution of index −α. It is well known that, in the M/G/1 FCFS queue, the sojourn time distribution is also regularly varying, of index 1−α, whereas in the case of LCFS or Processor Sharing, the sojourn time distribution is regularly varying of index −α. That raises the question whether there exist service disciplines that give rise to a regularly varying sojourn time distribution with any index −γ∈[−α,1−α]. In this paper that question is answered affirmatively.     

On the departure process of a leaky bucket system with long-range dependent input traffic

Due to the strong experimental evidence that the traffic to be offered to future broadband networks will display long-range dependence, it is important to study the possible implications that such traffic may have for the design and performance of these networks. In particular, an important question is whether the offered traffic preserves its long-range dependent nature after passing through a policing mechanism at the interface of the network. One of the proposed solutions for flow control in the context of the emerging ATM standard is the so-called leaky bucket scheme. In this paper we consider a leaky bucket system with long-range dependent input traffic. We adopt the following popular model for long-range dependent traffic: Time is discrete. At each unit time a random number of sessions is initiated, having the distribution of a Poisson random variable with mean λ. Each of these sessions has a random duration τ, where the integer random variable τ has finite mean, infinite variance, and a regularly varying tail, i.e., P(τ >К) ~ К^-Lα L(К), where 1 < α < 2 L(·) is a slowly varying function. Once a session is initiated, it generates one cell at each unit of time until its termination. We examine the departure process of the leaky bucket policing mechanism driven by such an arrival process, and show that it too is long-range dependent for any token buffer size and any - finite or infinite - cell buffer size. Moreover, upper and lower bounds for the covariance sequence of the output process are established. The above results demonstrate that long-range dependence cannot be removed by the kinds of flow control schemes that are currently being envisioned for broadband networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Sojourn time asymptotics in the M/G/1 processor sharing queue

We show for the M/G/1 processor sharing queue that the service time distribution is regularly varying of index -ν, ν non-integer, iff the sojourn time distribution is regularly varying of index -ν. This result is derived from a new expression for the Laplace–Stieltjes transform of the sojourn time distribution. That expression also leads to other new properties for the sojourn time distribution. We show how the moments of the sojourn time can be calculated recursively and prove that the kth moment of the sojourn time is finite iff the kth moment of the service time is finite. In addition, we give a short proof of a heavy traffic theorem for the sojourn time distribution, prove a heavy traffic theorem for the moments of the sojourn time, and study the properties of the heavy traffic limiting sojourn time distribution when the service time distribution is regularly varying. Explicit formulas and multiterm expansions are provided for the case that the service time has a Pareto distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic behaviour of the tandem queueing system with identical service times at both queues

Consider a tandem queue consisting of two single-server queues in series, with a Poisson arrival process at the first queue and arbitrarily distributed service times, which for any customer are identical in both queues. For this tandem queue, we relate the tail behaviour of the sojourn time distribution and the workload distribution at the second queue to that of the (residual) service time distribution. As a by-result, we prove that both the sojourn time distribution and the workload distribution at the second queue are regularly varying at infinity of index 1−ν, if the service time distribution is regularly varying at infinity of index −ν (ν>1). Furthermore, in the latter case we derive a heavy-traffic limit theorem for the sojourn time S ⁽²⁾ at the second queue when the traffic load ρ↑ 1. It states that, for a particular contraction factor Δ (ρ), the contracted sojourn time Δ (ρ) S ⁽²⁾ converges in distribution to the limit distribution H(·) as ρ↑ 1 where .     

Subsequences of normal sequences

In this paper, we characterize a set of indices τ={τ(0)<τ(1)<…} such that forany normal sequence (α(0), α(1),…) of a certain type, the subsequence (α(τ(0)), α(τ(1)),…) is a normal sequence of the same type. Assume that_n→∞. Then, we prove that τ has this property if and only if the 0–1 sequence (θ _τ (0), whereθ _τ (i)=1 or 0 according asi∈{τ(j);j=0, 1,…} or not, iscompletely deterministic in the sense of B. Weiss.     

Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates

We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the M_t/M_t/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process are known.     

An asymptotic property of gap series. II

An upper bound estimate in the law of the iterated logarithm for Σf(n _k ω) where n_k+1∫n_k≧ 1 + ck ^-α (α≧0) is investigated. In the case α<1/2, an upper bound had been given by Takahashi [15], and the sharpness of the bound was proved in our previous paper [8]. In this paper it is proved that the upper bound is still valid in case α≧1/2 if some additional condition on {n _k} is assumed. As an application, the law of the iterated logarithm is proved when {n _k} is the arrangement in increasing order of the set B(τ)={₁ ⁱ ₁...q_τ ⁱ _τ|i₁,...,i_τ∈N ₀}, where τ≧ 2, N ₀=NU{0}, and q ₁,...,q _τ are integers greater than 1 and relatively prime to each others. This revised version was published online in June 2006 with corrections to the Cover Date.     

Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service

A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either queue 1 becomes empty, or the number of messages decreases to k less than that found upon the server's last arrival at queue 1, whichever occurs first, where 1 ≤ k ≤ ∞. After service completion in queue 1, the server switches over to queue 2 in the second stage and serves all messages in queue 2 until it becomes empty. It is assumed that an arrival stream is Poissonian, message service times at each stage are generally distributed and switch-over times are zero. This paper analyzes joint queue-length distributions and message sojourn time distributions.     

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.     

Transient distributions of level dependent quasi-birth-death processes with linear transition rates

Many queueing systems such asM/M/s/K retrial queue with impatient customers, MAP/PH/1 retrial queue, retrial queue with two types of customers andMAP/M/∞ queue can be modeled by a level dependent quasi-birth-death (LDQBD) process with linear transition rates of the form λ_k = α+ βk at each levelk. The purpose of this paper is to propose an algorithm to find transient distributions for LDQBD processes with linear transition rates based on the adaptive uniformizaton technique introduced by van Moorsel and Sanders [11]. We apply the algorithm to some retrial queues and present numerical results.     

On universality of the Lerch zeta-function

It is known that the Lerch zeta-function L(λ, α, s) with transcendental parameter α is universal in the Voronin sense; i.e., every analytic function can be approximated by shifts L(λ, α, s + iτ) uniformly on compact subsets of some region. In this paper, the universality for some classes of composite functions F(L(λ, α, s)) is obtained. In particular, general theorems imply the universality of the functions sin(L(λ, α, s)) and sinh(L(λ, α, s)).     

Hopf Bifurcations and Oscillatory Instabilities of Spike Solutions for the One-Dimensional Gierer-Meinhardt Model

Summary. In the limit of small activator diffusivity ɛ , the stability of symmetric k -spike equilibrium solutions to the Gierer-Meinhardt reaction-diffusion system in a one-dimensional spatial domain is studied for various ranges of the reaction-time constant τ≥ 0 and the diffusivity D>0 of the inhibitor field dynamics. A nonlocal eigenvalue problem is derived that determines the stability on an O(1) time-scale of these k -spike equilibrium patterns. The spectrum of this eigenvalue problem is studied in detail using a combination of rigorous, asymptotic, and numerical methods. For k=1 , and for various exponent sets of the nonlinear terms, we show that for each D>0 , a one-spike solution is stable only when 0≤ τ<τ ₀ (D) . As τ increases past τ ₀ (D) , a pair of complex conjugate eigenvalues enters the unstable right half-plane, triggering an oscillatory instability in the amplitudes of the spikes. A large-scale oscillatory motion for the amplitudes of the spikes that occurs when τ is well beyond τ ₀ (D) is computed numerically and explained qualitatively. For k≥ 2 , we show that a k -spike solution is unstable for any τ≥ 0 when D>D _k , where D _k >0 is the well-known stability threshold of a multispike solution when τ=0 . For D>D _k and τ≥ 0 , there are eigenvalues of the linearization that lie on the (unstable) positive real axis of the complex eigenvalue plane. The resulting instability is of competition type whereby spikes are annihilated in finite time. For 0<D<D _k , we show that a k -spike solution is stable with respect to the O(1) eigenvalues only when 0≤ τ<τ ₀ (D;k) . When τ increases past τ ₀ (D;k)>0 , a synchronous oscillatory instability in the amplitudes of the spikes is initiated. For certain exponent sets and for k≥ 2 , we show that τ ₀ (D;k) is a decreasing function of D with τ ₀ (D;k) → τ _0k >0 as D→ D _k ^- .     

On a processor sharing queue that models balking

We consider the processor sharing M/M/1-PS queue which also models balking. A customer that arrives and sees n others in the system “balks” (i.e., decides not to enter) with probability 1−b _n . If b _n is inversely proportional to n + 1, we obtain explicit expressions for a tagged customer’s sojourn time distribution. We consider both the conditional distribution, conditioned on the number of other customers present when the tagged customer arrives, as well as the unconditional distribution. We then evaluate the results in various asymptotic limits. These include large time (tail behavior) and/or large n, lightly loaded systems where the arrival rate λ → 0, and heavily loaded systems where λ → ∞. We find that the asymptotic structure for the problem with balking is much different from the standard M/M/1-PS queue. We also discuss a perturbation method for deriving the asymptotics, which should apply to more general balking functions.     

Self-similar extremal processes

Given an extremal process X: [0,∞)→[0,∞)^d with lower curve C and associated point process N={(t_k, X_k):k≥0}, t_k distinct and X_k independent, given a sequence ζ _n =(τ _n , ξ _n ), n≥1, of time-space changes (max-automorphisms of [0,∞)^d+1), we study the limit behavior of the sequence of extremal processes Y_n(t)=ξ _n ^-1 ○ X ○ τ_n(t)=C_n(t) V max {ξ _n ^-1 ○ X_k: t_k ≤ τ_n(t){ ⇒ Y under a regularity condition on the norming sequence ζ_n and asymptotic negligibility of the max-increments of Y_n. The limit class consists of self-similar (with respect to a group η_α=(σ_α, L_α), α>0, of time-space changes) extremal processes. By self-similarity here we mean the property L_α ○ Y(t) ₌ ^d Y ○ α_α(t) for all α>0. The univariate marginals of Y are max-self-decomposable. If additionally the initial extremal process X is assumed to have homogeneous max-increments, then the limit process is max-stable with homogeneous max-increments. Supported by the Bulgarian Ministry of Education and Sciences (grant No. MM 234/1996). Proceedings of the Seminar on Stability Problems for Stochastic Models, Hajdúszoboszló, Hungary, 1997, Part I.     

Selection from poisson processes

Summary There are givenk Poisson processes with mean arrival times 1/λ₁,...1/λ _k . Let λ_[1]≦λ_[2]≦...≦λ_[k] denote the ordered set of values λ₁...,λ_[k]. We consider three procedures for selecting the process corresponding to λ_[k]. The processes are observed until there areN arrivals from any of the given processes, when the processes are observed continuously, or until there are at leastN arrivals, when the processes are observed at successive intervals of time whereN is a pre-determined positive integer. In the continuous case, the process for which theNth arrival time is shortest, is selected. In the discrete case, the selection involves certain randomization. Given (λ_[k]/λ_[k-1])≧0>1, it is shown that the probability of a correct selection (Pcs) is minimized whenθλ_[1]=θλ_[2]=...=θλ_[k-1]=θλ_[k]=θλ, say. The Pcs for this configuration is independent of λ for two of the given procedures, and monotone increasing in λ for the third. The value ofN is determined by a lower bound placed on the value of the Pcs. The problem of selecting from given Poisson processes for the discrete case is related to the problem of selecting from given Poisson populations. An application of the given procedures to a problem of selecting the “most probable event” from a multinomial population, is considered.     

On sojourn times in <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">GI</Emphasis> systems under state-dependent processor sharing

We consider a system with Poisson arrivals and i.i.d. service times. The requests are served according to the state-dependent processor-sharing discipline, where each request receives a service capacity which depends on the actual number of requests in the system. The linear systems of PDEs describing the residual and attained sojourn times coincide for this system, which provides time reversibility including sojourn times for this system, and their minimal non-negative solution gives the LST of the sojourn time V(τ) of a request with required service time τ. For the case that the service time distribution is exponential in a neighborhood of zero, we derive a linear system of ODEs, whose minimal non-negative solution gives the LST of V(τ), and which yields linear systems of ODEs for the moments of V(τ) in the considered neighborhood of zero. Numerical results are presented for the variance of V(τ). In the case of an M/GI/2-PS system, the LST of V(τ) is given in terms of the solution of a convolution equation in the considered neighborhood of zero. For service times bounded from below, surprisingly simple expressions for the LST and variance of V(τ) in this neighborhood of zero are derived, which yield in particular the LST and variance of V(τ) in M/D/2-PS.     

Completeness of the system {z^λn} in L^2[B,α0]

Let B be an unbounded domain located outside an angle domain with vertex at the origin, A ={λn}（n = 1,2,...） be a sequence of complex numbers satisfying sup ｜ arg（λn）｜ 〈 α 〈 π/2 and denote by M（∧） = {z^λ, λ ∈ ∧} the corresponding system of functions z^λ（λ∈∧）. Let α0（z） be a weight function defined on B. We obtain a completeness theorem for the system M（∧） in the Hilbert space L^2 [B, α0].     

An additive divisor problem with a growing number of factors

Let τk(n) be the number of representations ofn as the product ofk positive factors, τ(n)=τ(n). The asymptotics of Σ _n≤x τ _k (n)τ(n+1) for 80k ¹⁰ (lnlnx)³≤lnx is shown to be uniform with respect tok. Translated fromMatematicheskie Zametki, Vol. 61, No. 3, pp. 391–406, March, 1997. Translated by N. K. Kulman     

The continuity of superposition operators on some sequence spaces defined by moduli

Let λ and μ be solid sequence spaces. For a sequence of modulus functions Φ = (ϕ k) let λ(Φ) = {x = (x _k ): (ϕk(|x _k |)) ∈ λ}. Given another sequence of modulus functions Ψ = (ψ_k), we characterize the continuity of the superposition operators P _f from λ(Φ) into μ (Ψ) for some Banach sequence spaces λ and μ under the assumptions that the moduli ϕk (k ∈ ℕ) are unbounded and the topologies on the sequence spaces λ(Φ) and μ(Ψ) are given by certain F-norms. As applications we consider superposition operators on some multiplier sequence spaces of Maddox type. This research was supported by Estonian Science Foundation Grant 5376.     

Notes on combinatorial set theory

We shall prove some unconnected theorems: (1) (G.C.H.) \omega _{\alpha + 1} \to \left( {\omega _\alpha + \xi } \right)_2^2 when ℵ_α is regular, │ξ│⁺<ωα. (2) There is a Jonsson algebra in ℵ_α+n, and \aleph _{a + n} \not \to \left[ {\aleph _{a + n} } \right]_{\aleph _{a + n} }^{n + 1} if 2^{\aleph _{ - - } } = \aleph _{a + n} \cdot (3) If λ>ℵ₀ is a strong limit cardinal, then among the graphs with ≦λ vertices each of valence <λ there is a universal one. (4)(G.C.H.) If f is a set mapping on \omega _{a + 1} (ℵ_α regular) │f(x)∩f(y│<ℵ_α, then there is a free subset of order-type ζ for every ζ<ω_α+1.