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.     

A generalization of the Erlang formula of traffic engineering

Calls arrive at a switch, where they are assigned to any one of the available idle outgoing links. A call is blocked if all the links are busy. A call assigned to an idle link may be immediately lost with a probability which depends on the link. For exponential holding times and an arbitrary arrival process we show that the conditional distribution of the time to reach the blocked state from any state, given the sequence of arrivals, is independent of the policy used to route the calls. Thus the law of overflow traffic is independent of the assignment policy. An explicit formula for the stationary probability that an arriving call sees the node blocked is given for Poisson arrivals. We also give a simple asymptotic formula in this case.Work on this paper was done while the author was at Bellcore and at Berkeley.     

Stationary tail probabilities in exponential server tandems with renewal arrivals

The problem considered is that of estimating the tail stationary probability for two exponential server queues in series fed by renewal arrivals. We compute the tail of the marginal queue length distribution at the second queue. The marginal at the first queue is known by the classical result for the GI/M/1 queue. The approach involves deriving necessary and sufficient conditions on the paths of the arrival and virtual service processes in order to get a large queue size at the second queue. We then use large deviations estimates of the probabilities of these paths, and solve a constrained convex optimization problem to find the most likely path leading to a large queue size. We find that the stationary queue length distribution at the second queue has an exponentially decaying tail, and obtain the exact rate of decay.Research supported in part by NSF grant NCR 88-57731 and the AT & T Foundation.     

Mitigation of cellulose recalcitrance to enzymatic hydrolysis by ionic liquid pretreatment

Efficient hydrolysis of cellulose-to-glucose is critically important in producing fuels and chemicals from renewable feedstocks. Cellulose hydrolysis in aqueous media suffers from slow reaction rates because cellulose is a water-insoluble crystalline biopolymer. The high-crystallinity of cellulose fibrils renders the internal surface of cellulose inaccessible to the hydrolyzing enzymes (cellulases) as well as water. Pretreatment methods, which increase the surface area accessible to water and cellulases are vital to improving the hydrolysis kinetics and conversion of cellulose to glucose. In a novel technique, the microcrystalline cellulose was first subjected to an ionic liquid (IL) treatment and then recovered as essentially amorphous or as a mixture of amorphous and partially crystalline cellulose by rapidly quenching the solution with an antisolvent. Because of their extremely low-volatility, ILs are expected to have minimal environmental impact. Two different ILs, 1-n-butyl-3-methylimidazolium chloride (BMIMC1) and 1-allyl-3-methylimidazolium chloride (AMIMC1) were investigated. Hydrolysis kinetics of the IL-treated cellulose is significantly enhanced. With appropriate selection of IL treatment conditions and enzymes, the initial hydrolysis rates for IL-treated cellulose were up to 90 times greater than those of untreated cellulose. We infer that this drastic improvement in the "overall hydrolysis rates" with IL-treated cellulose is mainly because of a significant enhancement in the kinetics of the "primary hydrolysis step" (conversion of solid cellulose to soluble oligomers), which is the rate-limiting step for untreated cellulose. Thus, with IL-treated cellulose, primary hydrolysis rates increase and become comparable with the rates of inherently faster "secondary hydrolysis" (conversion of soluble oligomers to glucose).     

Stochastic approximation with long range dependent and heavy tailed noise

Stability and convergence properties of stochastic approximation algorithms are analyzed when the noise includes a long range dependent component (modeled by a fractional Brownian motion) and a heavy tailed component (modeled by a symmetric stable process), in addition to the usual ‘martingale noise’. This is motivated by the emergent applications in communications. The proofs are based on comparing suitably interpolated iterates with a limiting ordinary differential equation. Related issues such as asynchronous implementations, Markov noise, etc. are briefly discussed.     

Load Balancing in Hypergraphs

Consider a simple locally finite hypergraph on a countable vertex set, where each edge represents one unit of load which should be distributed among the vertices defining the edge. An allocation of load is called balanced if load cannot be moved from a vertex to another that is carrying less load. We analyze the properties of balanced allocations of load. We extend the concept of balancedness from finite hypergraphs to their local weak limits in the sense of Benjamini and Schramm (Electron J Probab 6(23):13, 2001) and Aldous and Steele (in: Probability on discrete structures. Springer, Berlin, pp 1–72, 2004). To do this, we define a notion of unimodularity for hypergraphs which could be considered an extension of unimodularity in graphs. We give a variational formula for the balanced load distribution and, in particular, we characterize it in the special case of unimodular hypergraph Galton–Watson processes. Moreover, we prove the convergence of the maximum load under some conditions. Our work is an extension to hypergraphs of Anantharam and Salez (Ann Appl Probab 26(1):305–327, 2016), which considered load balancing in graphs, and is aimed at more comprehensively resolving conjectures of Hajek (IEEE Trans Inf Theory 36(6):1398–1414, 1990).     

How large delays build up in a GI/G/1 queue

LetW _k denote the waiting time of customerk, k 0, in an initially empty GI/G/1 queue. Fixa> 0. We prove weak limit theorems describing the behaviour ofW _k /n, 0kn, given W_n >na. LetX have the distribution of the difference between the service and interarrival distributions. We consider queues for which Cramer type conditions hold forX, and queues for whichX has regularly varying positive tail.The results can also be interpreted as conditional limit theorems, conditional on large maxima in the partial sums of random walks with negative drift.Research supported by the NSF under Grant NCR 8710840 and under the PYI Award NCR 8857731.     

Exact emulation of a priority queue with a switch and delay lines

All-optical packet switched networking is hampered by the problem of realizing viable queues for optical packets. Packets can be buffered in delay lines, but delay lines do not functionally emulate queues from an input-output point of view. In this paper we consider the problem of exact emulation of a priority queue of size K using a switching system comprised of a switch of size (M + 1) × (M + 1), which has one distinguished input for external arrivals, one distinguished output for external departures, and fixed-length delay lines of lengths L₁, L₂, ..., L_M connecting the other inputs and outputs in pairs. We measure the complexity of such an emulation by M + 1. We prove that and present a construction which works with ; further, in our construction . We also sketch an idea for an all-optical packet switched communication network architecture based on approximate emulation of priority queues of finite size using switches and delay lines, with erasure control coding at the packet level. AMS 2000 subject classifications: Primary: 60K25; Secondary: 90B22 · 90B36 · 68R99 The work of A. D. Sarwate is supported by an NDSEG Graduate Research Fellowship which is sponsored by the U.S. Department of Defense. The work of V. Anantharam is supported by ONR grant No. N00014-1-0637, DARPA grant No. N66001-00-C-8062, and by NSF grant No. ECS 0123512.     

Scheduling strategies and long-range dependence

Consider a single server queue with unit service rate fed by an arrival process of the following form: sessions arrive at the times of a Poisson process of rate λ, with each session lasting for an independent integer time τ ⩾ 1, where P(τ = k) = p _k with p _k ~ αk ^−(1+α) L(k), where 1 < α < 2 and L(·) is a slowly varying function. Each session brings in work at unit rate while it is active. Thus the work brought in by each arrival is regularly varying, and, because 1 < α < 2, the arrival process of work is long-range dependent. Assume that the stability condition λE[τ] < 1 holds. By simple arguments we show that for any stationary nonpreemptive service policy at the queue, the stationary sojourn time of a typical session must stochastically dominate a regularly varying random variable having infinite mean; this is true even if the duration of a session is known at the time it arrives. On the other hand, we show that there exist causal stationary preemptive policies, which do not need knowledge of the session durations at the time of arrival, for which the stationary sojourn time of a typical session is stochastically dominated by a regularly varying random variable having finite mean. These results indicate that scheduling policies can have a significant influence on the extent to which long-range dependence in the arrivals influences the performance of communication networks. This revised version was published online in June 2006 with corrections to the Cover Date.