Anisotropic Meshless Frames on ℝ n

We present a construction of anisotropic multiresolution and anisotropic wavelet frames based on multilevel ellipsoid covers (dilations) of ℝ ⁿ . The wavelets we construct are C ^∞ functions, can have any prescribed number of vanishing moments and fast decay with respect to the anisotropic quasi-distance induced by the cover. The dual wavelets are also C ^∞, with the same number of vanishing moments, but with only mild decay with respect to the quasi-distance. An alternative construction yields a meshless frame whose elements do not have vanishing moments, but do have fast anisotropic decay.     

A fluid system with coupled input and output,and its application to bottlenecks in ad hoc networks

This paper studies a fluid queue with coupled input and output. Flows arrive according to a Poisson process, and when n flows are present, each of them transmits traffic into the queue at a rate c/(n+1), where the remaining c/(n+1) is used to serve the queue. We assume exponentially distributed flow sizes, so that the queue under consideration can be regarded as a system with Markov fluid input. The rationale behind studying this queue lies in ad hoc networks: bottleneck links have roughly this type of sharing policy. We consider four performance metrics: (i) the stationary workload of the queue, (ii) the queueing delay, i.e., the delay of a ‘packet’ (a fluid particle) that arrives at the queue at an arbitrary point in time, (iii) the flow transfer delay, i.e., the time elapsed between arrival of a flow and the epoch that all its traffic has been put into the queue, and (iv) the sojourn time, i.e., the flow transfer time increased by the time it takes before the last fluid particle of the flow is served. For each of these random variables we compute the Laplace transform. The corresponding tail probabilities decay exponentially, as is shown by a large-deviations analysis. F. Roijers’ work has been carried out partly in the SENTER-NOVEM funded project Easy Wireless.     

A fluid model for a relay node in an ad hoc network: the case of heavy-tailed input

Relay nodes in an ad hoc network can be modelled as fluid queues, in which the available service capacity is shared by the input and output. In this paper such a relay node is considered; jobs arrive according to a Poisson process and bring along a random amount of work. The total transmission capacity is fairly shared, meaning that, when n jobs are present, each job transmits traffic into the queue at rate 1/(n + 1) while the queue is drained at the same rate of 1/(n + 1). Where previous studies mainly concentrated on the case of exponentially distributed job sizes, the present paper addresses regularly varying jobs. The focus lies on the tail asymptotics of the sojourn time S. Using sample-path arguments, it is proven that ${\mathbb{P}\left\{ S > x \right\}}${\mathbb{P}\left\{ S > x \right\}} behaves roughly as the residual job size, i.e., if the job sizes are regularly varying of index  − ν, the tail of S is regularly varying of index 1 − ν In addition, we address the tail asymptotics of other performance metrics, such as the workload in the queue, the flow transfer time and the queueing delay.     

New Expressions for Repeated Upper Tail Integrals of the Normal Distribution

Expressions are given for repeated upper tail integrals of the univariate normal density (and so also for the general Hermite function) for both positive and negative arguments. The expressions involve moments of the form E(x + i N) ⁿ and E1 / (x ² + N ²) ⁿ , where N is a unit normal random variable. Laplace transforms are provided for the Hermite functions and the moments. The practical use of these expressions is illustrated.     

L-Functions for Jacobi Forms of Arbitrary Degree

A finite number ofL-functions are associated to every Jacobi cusp form of degreen. TheseL-functions are infinite series constructed with the Fourier coefficients of the form and a variables in ℂⁿ. It is proved that eachL-function has an integral representation, admits a holomorphic continuation to the whole space ℂⁿ, and the row vector formed with them satisfies a particular matrix functional equation.     

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.     

The Smallest Eigenvalue of Hankel Matrices

Let ℋ _N =(s _n+m ),0≤n,m≤N, denote the Hankel matrix of moments of a positive measure with moments of any order. We study the large N behavior of the smallest eigenvalue λ _N of ℋ _N . It is proven that λ _N has exponential decay to zero for any measure with compact support. For general determinate moment problems the decay to 0 of λ _N can be arbitrarily slow or arbitrarily fast in a sense made precise below. In the indeterminate case, where λ _N is known to be bounded below by a strictly positive constant, we prove that the limit of the nth smallest eigenvalue of ℋ _N for N→∞ tends rapidly to infinity with n. The special case of the Stieltjes–Wigert polynomials is discussed.     

Boundedness of Multilinear Operators in Herz-type Hardy Space

Let κ∈ℕ. We prove that the multilinear operators of finite sums of products of singular integrals on ℝⁿ are bounded from HK ^α1,p1 _q1 (ℝⁿ) ×···×HK ^αk,pk _qk (ℝⁿ) into HK ^α,p _q (ℝⁿ) if they have vanishing moments up to a certain order dictated by the target spaces. These conditions on vanishing moments satisfied by the multilinear operators are also necessary when α_j≥ 0 and the singular integrals considered here include the Calderón-Zygmund singular integrals and the fractional integrals of any orders. Received September 6, 1999, Revised November 17, 1999, Accepted December 9, 1999     

Structural interpretation and derivation of necessary and sufficient conditions for delay moments in FIFO multiserver queues

Scheller-Wolf [12] established necessary and sufficient conditions for finite stationary delay moments in stable FIFO GI/GI/s queues that incorporate the interaction between service time distribution, traffic intensity (ρ) and the number of servers in the queue. These conditions can be used to show that when the service time has finite first but infinite αth moment, s slow servers can give lower delays than one fast server. In this paper, we derive an alternative derivation of these moment results: Both upper bounds, that serve as sufficient conditions, and lower bounds, that serve as necessary conditions are presented. In addition, we extend the class of service time distributions for which the necessary conditions are valid. Our new derivations provide a structural interpretation of the moment bounds, giving intuition into their origin: We show that FIFO GI/GI/s delay can be represented as the minimum of (s − k) i.i.d. GI/GI/1 delays, when ρ satisfies k < ρ < k+1. AMS Subject Classification 60K25     

How many s-subspaces must miss a point set in PG(d, q)

The following result is well-known for finite projective spaces. The smallest cardinality of a set of points of PG(n, q) with the property that every s-subspace has a point in the set is (q ^n+1-s - 1)/(q - 1). We solve in finite projective spaces PG(n, q) the following problem. Given integers s and b with 0 ≤ s ≤ n - 1 and 1 ≤ b ≤ (q ^n+1-s - 1)/(q - 1), what is the smallest number of s-subspaces that must miss a set of b points. If d is the smallest integer such that b ≤ (q ^d+1 - 1)/(q - 1), then we shall see that the smallest number is obtained only when the b points generate a subspace of dimension d. We then also determine the smallest number of s-subspaces that must miss a set of b points of PG(n, q) which do not lie together in a subspace of dimension d. The results are obtained by geometrical and combinatorial arguments that rely on a strong algebraic result for projective planes by T. Szőnyi and Z. Weiner.     

Heavy-traffic analysis for the GI/G/1 queue with heavy-tailed distributions

We consider a GI/G/1 queue in which the service time distribution and/or the interarrival time distribution has a heavy tail, i.e., a tail behaviour like t ^−ν with 1 < ν ⩽ 2 , so that the mean is finite but the variance is infinite. We prove a heavy-traffic limit theorem for the distribution of the stationary actual waiting time W. If the tail of the service time distribution is heavier than that of the interarrival time distribution, and the traffic load a → 1, then W, multiplied by an appropriate ‘coefficient of contraction’ that is a function of a, converges in distribution to the Kovalenko distribution. If the tail of the interarrival time distribution is heavier than that of the service time distribution, and the traffic load a → 1, then W, multiplied by another appropriate ‘coefficient of contraction’ that is a function of a, converges in distribution to the negative exponential distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some first passage time problems for the shortest queue model

We consider the symmetric shortest queue (SQ) problem. Here we have a Poisson arrival stream of rate λ feeding two parallel queues, each having an exponential server that works at rate μ. An arrival joins the shorter of the two queues; if both are of equal length the arrival joins either with probability 1/2. We consider the first passage time until one of the queues reaches the value m ₀, and also the time until both reach this level. We give explicit expressions for the first two first passage moments, conditioned on the initial queue lengths, and also the full first passage distribution. We also give some asymptotic results for m ₀→∞ and various values of ρ=λ/μ. H. Yao work was partially supported by PSC-CUNY Research Award 68751-0037. C. Knessl work was supported in part by NSF grants DMS 02-02815 and DMS 05-03745.     

Decay rate for a PH/M/2 queue with shortest queue discipline

In this paper, we consider a PH/M/2 queue in which each server has its own queue and arriving customers join the shortest queue. For this model, it has been conjectured that the decay rate of the tail probabilities for the shortest queue length in the steady state is equal to the square of the decay rate for the queue length in the corresponding PH/M/2 model with a single queue. We prove this fact in the sense that the tail probabilities are asymptotically geometric when the difference of the queue sizes and the arrival phase are fixed. Our proof is based on the matrix analytic approach pioneered by Neuts and recent results on the decay rates. AMS subject classifications: 60K25 · 60K20 · 60F10 · 90B22     

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.     

Stationary tail asymptotics of a tandem queue with feedback

Motivated by applications in manufacturing systems and computer networks, in this paper, we consider a tandem queue with feedback. In this model, the i.i.d. interarrival times and the i.i.d. service times are both exponential and independent. Upon completion of a service at the second station, the customer either leaves the system with probability p or goes back, together with all customers currently waiting in the second queue, to the first queue with probability 1−p. For any fixed number of customers in one queue (either queue 1 or queue 2), using newly developed methods we study properties of the exactly geometric tail asymptotics as the number of customers in the other queue increases to infinity. We hope that this work can serve as a demonstration of how to deal with a block generating function of GI/M/1 type, and an illustration of how the boundary behaviour can affect the tail decay rate.     

Large number of queues in tandem: Scaling properties under back-pressure algorithm

We consider a system with N unit-service-rate queues in tandem, with exogenous arrivals of rate λ at queue 1, under a back-pressure (MaxWeight) algorithm: service at queue n is blocked unless its queue length is greater than that of the next queue n+1. The question addressed is how steady-state queues scale as N→∞. We show that the answer depends on whether λ is below or above the critical value 1/4: in the former case the queues remain uniformly stochastically bounded, while otherwise they grow to infinity.     

Regularly varying tail of the waiting time distribution in M/G/1 retrial queue

We consider an M/G/1 retrial queue where the service time distribution has a regularly varying tail with index −β, β>1. The waiting time distribution is shown to have a regularly varying tail with index 1−β, and the pre-factor is determined explicitly. The result is obtained by comparing the waiting time in the M/G/1 retrial queue with the waiting time in the ordinary M/G/1 queue with random order service policy.     

On the concentration of eigenvalues of random symmetric matrices

It is shown that for every 1≤s≤n, the probability that thes-th largest eigenvalue of a random symmetricn-by-n matrix with independent random entries of absolute value at most 1 deviates from its median by more thant is at most 4e ⁻ t ²32 ^s2. The main ingredient in the proof is Talagrand’s Inequality for concentration of measure in product spaces. Research supported in part by a USA — Israel BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research supported in part by a USA — Israel BSF grant and by a Bergmann Memorial Grant.     

Nonstationary queues with Interrrupted Poisson arrivals and unreliable/repairable servers

A queueing model having a nonstationary Interrupted Poisson arrival process (IPP(t)),s time-dependent exponential unreliable/repairable servers and finite capacityc is introduced, and an approximation method for analysis of it is developed and tested. Approximations are developed for the time-dependent queue length moments and the system viewpoint waiting time distributions and moments. The approximation involves state-space partitioning and numerically integrating partial-moment differential equations (PMDEs). Surrogate distribution approximations (SDA's) are used to close the system of PMDEs. The approximations allow for analysis using only (s + 1)(s + 6) differential equations for the queue length moments rather than the 2(c + 1)(s +1) equations required by the classic method of numerically integrating the full set of Kolmogorov-forward equations. Effectively hours of cpu time are reduced to minutes for even modest capacity systems. Approximations for waiting time distributions and moments are developed.This research was partially funded by National Science Foundation grant ECS-8404409.     

Approximation of convolutions by accompanying laws under the existence of moments of low orders

It is shown that if a one-dimensional distribution F has finite moment of order 1+β for some β, 1/2≤β≤1, then the rate of approximation of the n-fold convolution Fⁿ by accompanying laws is O(n^−1/2). Futhermore, if Eξ² = ∞ and 1/2<β<1, then the rate of approximation is o(n^−1/2). The question about the true rate of approximation of Fⁿ by infinitely divisible and accompanying laws is discussed. Bibliography: 27 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 228, 1996, pp. 135–141.