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.     

Large and Moderate Deviations for Estimators of Quadratic Variational Processes of Diffusions

For a diffusion process dX_t = σdB _t + b(t, X_t)dt with (σ _t ) unknown, we study the large and moderate deviations of the estimator of the quadratic variational process . This revised version was published online in June 2006 with corrections to the Cover Date.     

A queueing system with linear repeated attempts,bernoulli schedule and feedback

We analyse a single-server retrial queueing system with infinite buffer, Poisson arrivals, general distribution of service time and linear retrial policy. If an arriving customer finds the server occupied, he joins with probabilityp a retrial group (called orbit) and with complementary probabilityq a priority queue in order to be served. After the customer is served completely, he will decide either to return to the priority queue for another service with probability ϑ or to leave the system forever with probability =1−ϑ, where 0≤ϑ<1. We study the ergodicity of the embedded Markov chain, its stationary distribution function and the joint generating function of the number of customers in both groups in the steady-state regime. Moreover, we obtain the generating function of system size distribution, which generalizes the well-knownPollaczek-Khinchin formula. Also we obtain a stochastic decomposition law for our queueing system and as an application we study the asymptotic behaviour under high rate of retrials. The results agree with known special cases. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

Limit Laws for Norms of IID Samples with Weibull Tails

We are concerned with the limit distribution of l _t -norms (of order t) of samples of i.i.d. positive random variables, as N→∞, t→∞. The problem was first considered by Schlather [(2001), Ann. Probab. 29, 862–881], but the case where {X _i } belong to the domain of attraction of Gumbel’s double exponential law (in the sense of extreme value theory) has largely remained open (even for an exponential distribution). In this paper, it is assumed that the log-tail distribution function is regularly varying at infinity with index . We proceed from studying the limit distribution of the sums , which is of interest in its own right. A proper growth scale of N relative to t appears to be of the form (). We show that there are two critical points, α₁ = 1 and α₂ = 2, below which the law of large numbers and the central limit theorem, respectively, break down. For α < 2, under a slightly stronger condition of normalized regular variation of h, we prove that the limit laws for S _N (t) are stable, with characteristic exponent and skewness parameter . A complete picture of the limit laws for the norms R _N (t) = S _N (t)^1/t is then derived. In particular, our results corroborate a conjecture in Schlather [(2001), Ann. Probab. 29, 862–881] regarding the “endpoints” , α→ 0.      

Equations on real intervals

A (finite or infinite) set ∑ of equations, in operation symbols F_t (t ∈T) and variables x_i, is said to be compatible with iff there exist continuous operations F_t^A on such that the algebra satisfies the equations ∑ (with the variables x_i understood as universally quantified). It is proved that there is no algorithm to decide -compatibility for all finite ∑. If the definition is restricted to C¹ idempotent operations F_t^A , then there does exist an algorithm for compatibility. Received August 9, 2005; accepted in final form February 14, 2006.     

Wiener-Hopf analysis of an M/G/1 queue with negative customers and of a related class of random walks

Two variants of an M/G/1 queue with negative customers lead to the study of a random walkX _n+1=[X _n + _n ]⁺ where the integer-valued _n are not bounded from below or from above, and are distributed differently in the interior of the state-space and on the boundary. Their generating functions are assumed to be rational. We give a simple closed-form formula for , corresponding to a representation of the data which is suitable for the queueing model. Alternative representations and derivations are discussed. With this formula, we calculate the queue length generating function of an M/G/1 queue with negative customers, in which the negative customers can remove ordinary customers only at the end of a service. If the service is exponential, the arbitrarytime queue length distribution is a mixture of two geometrical distributions.Supported by the European grant BRA-QMIPS of CEC DG XIII.     

Exact Buffer Overflow Calculations for Queues via Martingales

Let _n be the first time a queueing process like the queue length or workload exceeds a level n. For the M/M/1 queue length process, the mean _n and the Laplace transform e^-sn is derived in closed form using a martingale introduced in Kella and Whitt (1992). For workload processes and more general systems like MAP/PH/1, we use a Markov additive extension given in Asmussen and Kella (2000) to derive sets of linear equations determining the same quantities. Numerical illustrations are presented in the framework of M/M/1 and MMPP/M/1 with an application to performance evaluation of telecommunication systems with long-range dependent properties in the packet arrival process. Different approximations that are obtained from asymptotic theory are compared with exact numerical results.     

On the rod placement theorem of Rybko and Shlosman

Given n−1 points on the real line and a set of n rods of strictly positive lengths , we get to choose an n-th point x_n anywhere on the real line and to assign the rods to the points according to an arbitrary permutation π. The rod is thought of as the workload brought in by a customer arriving at time x_k into a first in -first out queue which starts empty at − ∞. If any x_i equals x_j for i < j, service is provided to the rod assigned to x_i before the rod assigned to x_j. Let denote the set of departure times of the customers (rods). Let denote the number of choices for the location of x_n for which . Rybko and Shlosman proved that

A stochastic approximation algorithm with multiplicative step size modification

An algorithm of searching a zero of an unknown function ϕ: ℝ → ℝ is considered: x _t = x _t−1 − γ _t−1 y _t , t = 1, 2, ..., where y _t = ϕ(x _t−1) + ξ _t is the value of ϕ measured at x _t−1 and ξ _t is the measurement error. The step sizes γ _t > 0 are modified in the course of the algorithm according to the rule: γ _t = min{uγ _t−1, } if y _t−1 y _t > 0, and γ _t = dγ _t−1, otherwise, where 0 < d < 1 < u, > 0. That is, at each iteration γ _t is multiplied either by u or by d, provided that the resulting value does not exceed the predetermined value . The function ϕ may have one or several zeros; the random values ξ _t are independent and identically distributed, with zero mean and finite variance. Under some additional assumptions on ϕ, ξ _t , and , the conditions on u and d guaranteeing a.s. convergence of the sequence {x _t }, as well as a.s. divergence, are determined. In particular, if P(ξ ₁ > 0) = P (ξ ₁ < 0) = 1/2 and P(ξ ₁ = x) = 0 for any x ∈ ℝ, one has convergence for ud < 1 and divergence for ud > 1. Due to the multiplicative updating rule for γ _t , the sequence {x _t } converges rapidly: like a geometric progression (if convergence takes place), but the limit value may not coincide with, but instead, approximate one of the zeros of ϕ. By adjusting the parameters u and d, one can reach arbitrarily high precision of the approximation; higher accuracy is obtained at the expense of lower convergence rate.      

Some constructions on the Hermitian surface

In the geometric setting of commuting orthogonal and unitary polarities we construct an infinite family of complete (q + 1)²–spans of the Hermitian surface , q odd. A construction of an infinite family of minimal blocking sets of , q odd, admitting PSL ₂(q), is also provided.      

On the Oscillation of Second Order Neutral Differential Equations of Emden-Fowler Type

Some oscillation criteria are established by the averaging technique for the second order neutral delay differential equation of Emden-Fowler type where x(t) = y(t) + p(t)y(t − τ), τ, σ₁ and σ₂ are nonnegative constants, α > 0, β > 0, and a, p, q ₁, . The results of this paper extend and improve some known results. In particular, two interesting examples that point out the importance of our theorems are also included.     

Self-adjoint Analytic Operator Functions: Local Spectral Function and Inner Linearization

In this note we continue the study of spectral properties of a self-adjoint analytic operator function A(z) that was started in [5]. It is shown that if A(z) satisfies the Virozub–Matsaev condition on some interval Δ₀ and is boundedly invertible in the endpoints of Δ₀, then the ‘embedding’ of the original Hilbert space into the Hilbert space , where the linearization of A(z) acts, is in fact an isomorphism between a subspace of and . As a consequence, properties of the local spectral function of A(z) on Δ₀ and a so-called inner linearization of the operator function A(z) in the subspace are established.      

Optimal decompositions for theK-functional for a couple of Banach lattices

Letf=g _t+h _t be the optimal decomposition for calculating the exact value of theK-functionalK(t, f; ) of an elementf with respect to a couple =(X ₀ ,X ₁) of Banach lattices of measurable functions. It is shown that this decomposition has a rather simple form in many cases where one of the spacesX ₀ andX ₁ is eitherL ^∞ orL ¹. Many examples are given of couples of lattices for which |g _t| increases monotonically a.e. with respect tot. It is shown that this property implies a sharpened estimate from above for the Brudnyi-KrugljakK-divisibility constant γ( ) for the couple. But it is also shown that certain couples do not have this property. These also provide examples of couples of lattices for which γ( ). Research supported by the Technion V. P. R. Fund.     

Pointwise convergence for semigroups in vector-valued <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> spaces

Suppose that {T _t  : t  ≥  0} is a symmetric diffusion semigroup on L ²(X) and denote by its tensor product extension to the Bochner space , where belongs to a certain broad class of UMD spaces. We prove a vector-valued version of the Hopf–Dunford–Schwartz ergodic theorem and show that this extends to a maximal theorem for analytic continuations of on . As an application, we show that such continuations exhibit pointwise convergence.     

The Riemann–Hilbert Problem in Weighted Classes of Cauchy Type Integrals with Density from L P( · )(Γ)

We consider the Riemann–Hilbert problem in the following setting: find a function whose boundary values ϕ⁺(t) satisfy the condition a.e. on Γ. Here D is a simply connected domain bounded by a simple closed curve Γ, and K ^{p( · )}(D;ω) is the set of functions ϕ(z) representable in the form , where ω(z) is a weight function and (K _Γφ )(z) is a Cauchy type integral whose density φ is integrable with a variable exponent p(t). It is assumed that Γ is a piecewise-Lyapunov curve without zero angles, ω(z) is an arbitrary power function and p(t) satisfies the Log-H?lder condition. The solvability conditions are established and solutions are constructed. These solutions largely depend on the coefficients a, b, c, the weight ω, on the values of p(t) at the angular points of Γ and on the values of angles at these points. Submitted: May 13, 2007. Revised: August 8, 2007 and August 28, 2007. Accepted: November 8, 2007.     

Robust exponential attractors for a phase-field system with memory

H.G. Rotstein et al. proposed a nonconserved phase-field system characterized by the presence of memory terms both in the heat conduction and in the order parameter dynamics. These hereditary effects are represented by time convolution integrals whose relaxation kernels k and h are nonnegative, smooth and decreasing. Rescaling k and h properly, we obtain a system of coupled partial integrodifferential equations depending on two relaxation times ɛ and σ. When ɛ and σ tend to 0, the formal limiting system is the well-known nonconserved phase-field model proposed by G. Caginalp. Assuming the exponential decay of the relaxation kernels, the rescaled system, endowed with homogeneous Neumann boundary conditions, generates a dissipative strongly continuous semigroup S_{ɛ, σ}(t) on a suitable phase space, which accounts for the past histories of the temperature as well as of the order parameter. Our main result consists in proving the existence of a family of exponential attractors for S_{ɛ, σ}(t), with ɛ, σ ∈ [0, 1], whose symmetric Hausdorff distance from tends to 0 in an explicitly controlled way.     

Probabilistic Representations of Solutions of the Forward Equations

In this paper we prove a stochastic representation for solutions of the evolution equation

On <Emphasis Type="Italic">Γ</Emphasis>-convergence of quadratic functionals in the plane

In this paper, we prove that if a sequence of homeomorphisms , with bounded planar domains, of Sobolev space has uniformly equibounded distortions in EXP(Ω) and weakly converges to f in then the matrices A(x, f _j ) of the corresponding Laplace-Beltrami operators Γ-converge in the Orlicz–Sobolev space , where Q(t) = t ²log(e + t), to the matrix A(x, f) of the Laplace-Beltrami operator associated to f.      

Metrics in the sphere of a C*-module

Given a unital C*-algebra and a right C*-module over , we consider the problem of finding short smooth curves in the sphere = {x ∈ : 〈x, x〉 = 1}. Curves in are measured considering the Finsler metric which consists of the norm of at each tangent space of . The initial value problem is solved, for the case when is a von Neumann algebra and is selfdual: for any element x ₀ ∈ and any tangent vector ν at x ₀, there exists a curve γ(t) = e ^tZ (x ₀), Z ∈ , Z* = −Z and ∥Z∥ ≤ π, such that γ(0) = x ₀ and (0) = ν, which is minimizing along its path for t ∈ [0, 1]. The existence of such Z is linked to the extension problem of selfadjoint operators. Such minimal curves need not be unique. Also we consider the boundary value problem: given x ₀, x ₁ ∈ , find a curve of minimal length which joins them. We give several partial answers to this question. For instance, let us denote by f ₀ the selfadjoint projection I − x ₀ ⊗ x ₀, if the algebra f ₀ f ₀ is finite dimensional, then there exists a curve γ joining x ₀ and x ₁, which is minimizing along its path.