The Experts below are selected from a list of 18378 Experts worldwide ranked by ideXlab platform
Ward Whitt - One of the best experts on this subject based on the ideXlab platform.
-
Exponential Approximations for Tail Probabilities in Queues, I: Waiting Times
Operations Research, 1995Co-Authors: Joseph Abate, Gagan L. Choudhury, Ward WhittAbstract:This paper focuses on simple exponential approximations for tail probabilities of the steady-state waiting time in infinite-capacity multiserver queues based on small-tail Asymptotics. For the GI/GI/s model, we develop a heavy-traffic Asymptotic expansion in powers of one minus the traffic intensity for the waiting-time Asymptotic Decay rate. We propose a two-term approximation for the Asymptotic Decay rate based on the first three moments of the interarrival-time and service-time distributions. We also suggest approximating the Asymptotic constant by the product of the mean and the Asymptotic Decay rate. We evaluate the exponential approximations based on the exact Asymptotic parameters and their approximations by making comparisons with exact results obtained numerically for the BMAP/GI/1 queue, which has a batch Markovian arrival process, and the GI/GI/s queue. Numerical examples show that the exponential approximations are remarkably accurate, especially for higher percentiles, such as the 90th percentile and beyond.
-
Heavy-traffic Asymptotic expansions for the Asymptotic Decay rates in the BMAP/G/1 queue
Communications in Statistics. Stochastic Models, 1994Co-Authors: Gagan L. Choudhury, Ward WhittAbstract:In great generality, the basic steady-state distributions in theBMAP/G/l queue have Asymptotically exponential tails. Here we develop Asymptotic expansions for the Asymptotic Decay rates of these tail probabilities in powers of one minus the traffic intensity. The first term coincides with the Decay rate of the exponential distribution arising in the standard heavy-traffic limit. The coefficients of these heavy-traffic expansions depend on the moments of the service-time distribution and the derivatives of the Perron-Frobenius eigenvalue δ(z) of the BMAP matrix generating function D (z) at z = 1. We give recursive formulas for the derivatives δ(κ) (1). The Asymptotic expansions provide the basis for efficiently computing the Asymptotic Decay rates as functions of the traffic intensity, i.e., the caudal characteristic curves. The Asymptotic expansions also reveal what features of the model the Asymptotic Decay rates primarily depend upon. In particular, δ(z) coincides with the limiting time-average of the ...
-
heavy traffic Asymptotic expansions for the Asymptotic Decay rates in the bmap g 1 queue
Stochastic Models, 1994Co-Authors: Gagan L. Choudhury, Ward WhittAbstract:In great generality, the basic steady-state distributions in theBMAP/G/l queue have Asymptotically exponential tails. Here we develop Asymptotic expansions for the Asymptotic Decay rates of these tail probabilities in powers of one minus the traffic intensity. The first term coincides with the Decay rate of the exponential distribution arising in the standard heavy-traffic limit. The coefficients of these heavy-traffic expansions depend on the moments of the service-time distribution and the derivatives of the Perron-Frobenius eigenvalue δ(z) of the BMAP matrix generating function D (z) at z = 1. We give recursive formulas for the derivatives δ(κ) (1). The Asymptotic expansions provide the basis for efficiently computing the Asymptotic Decay rates as functions of the traffic intensity, i.e., the caudal characteristic curves. The Asymptotic expansions also reveal what features of the model the Asymptotic Decay rates primarily depend upon. In particular, δ(z) coincides with the limiting time-average of the ...
-
A heavy-traffic expansion for Asymptotic Decay rates of tail probabilities in multichannel queues
Operations Research Letters, 1994Co-Authors: Joseph Abate, Ward WhittAbstract:We establish a heavy-traffic Asymptotic expansion (in powers of one minus the traffic intensity) for the Asymptotic Decay rates of queue-length and workload tail probabilities in stable infinite-capacity multichannel queues. The specific model has multiple independent heterogeneous servers, each with i.i.d. service times, that are independent of the arrival process, which is the superposition of independent nonidentical renewal processes. Customers are assigned to the first available server in the order of arrival. The heavy-traffic expansion yields relatively simple approximations for the tails of steady-state distributions and higher percentiles, yielding insight into the impact of the first three moments of the defining distributions.
-
Tail probabilities with statistical multiplexing and effective bandwidths in multi-class queues
Telecommunication Systems, 1993Co-Authors: Ward WhittAbstract:Our primary purpose in this paper is to contribute to the design of admission control schemes for multi-class service systems. We are motivated by emerging highspeed networks exploiting asynchronous transfer mode (ATM) technology, but there may be other applications. We develop a simple criterion for feasibility of a set of sources in terms of "effective bandwidths". These effective bandwidths are based on Asymptotic Decay rates of steady-state distributions in queueing models. We show how to compute Asymptotic Decay rates of steady-state queue length and workload tail probabilities in general infinite-capacity multi-channel queues. The model hasm independent heterogeneous servers that are independent of an arrival process which is a superposition ofn independent general arrival processes. The contribution of each component arrival process to the overall Asymptotic Decay rates can be determined from the Asymptotic Decay rates produced by this arrival process alone in a G/D/1 queue (as a function of the arrival rate). Similarly, the contribution of each service process to the overall Asymptotic Decay rates can be determined from the Asymptotic Decay rates produced by this service process alone in a D/G/1 queue. These contributions are characterized in terms of single-channel Asymptotic Decay-rate functions, which can be estimated from data or determined analytically from models. The Asymptotic Decay-rate functions map potential Decay rates of the queue length into associated Decay rates of the workload. Combining these relationships for the arrival and service channels determines the Asymptotic Decay rates themselves. The Asymptotic Decay-rate functions are the time-average limits of logarithmic moment generating functions. We give analytical formulas for the Asymptotic Decay-rate functions of a large class of stochastic point processes, including batch Markovian arrival processes. The Markov modulated Poisson process is a special case. Finally, we try to put our work in perspective with the related literature.
Xiaojun Lin - One of the best experts on this subject based on the ideXlab platform.
-
Design of scheduling algorithms for end-to-end backlog minimization in wireless multi-hop networks under k -hop interference models
IEEE ACM Transactions on Networking, 2016Co-Authors: Shizhen Zhao, Xiaojun LinAbstract:In this paper, we study the problem of link scheduling for multi-hop wireless networks with per-flow delay constraints under the $K$ -hop interference model. Specifically, we are interested in algorithms that maximize the Asymptotic Decay-rate of the probability with which the maximum end-to-end backlog among all flows exceeds a threshold, as the threshold becomes large. We provide both positive and negative results in this direction. By minimizing the drift of the maximum end-to-end backlog in the converge-cast on a tree, we design an algorithm, Largest-Weight-First (LWF), that achieves the optimal Asymptotic Decay-rate for the overflow probability of the maximum end-to-end backlog as the threshold becomes large. However, such a drift minimization algorithm may not exist for general networks. We provide an example in which no algorithm can minimize the drift of the maximum end-to-end backlog. Finally, we simulate the LWF algorithm together with a well known algorithm (the back-pressure algorithm) and a large-deviations optimal algorithm in terms of the sum-queue (the P-TREE algorithm) in converge-cast networks. Our simulation shows that our algorithm performs significantly better not only in terms of Asymptotic Decay-rate, but also in terms of the actual overflow probability.
-
INFOCOM - On the design of scheduling algorithms for end-to-end backlog minimization in multi-hop wireless networks
2012 Proceedings IEEE INFOCOM, 2012Co-Authors: Shizhen Zhao, Xiaojun LinAbstract:In this paper, we study the problem of link scheduling for multi-hop wireless networks with per-flow delay constraints. Specifically, we are interested in algorithms that maximize the Asymptotic Decay-rate of the probability with which the maximum end-to-end backlog among all flows exceeds a threshold, as the threshold becomes large. We provide both positive and negative results in this direction. By minimizing the drift of the maximum end-to-end backlog in the converge-cast on a tree, we design an algorithm, Largest-Weight-First(LWF), that achieves the optimal Asymptotic Decay-rate for the overflow probability of the maximum end-to-end backlog as the threshold becomes large. However, such a drift minimization algorithm may not exist for general networks. We provide an example in which no algorithm can minimize the drift of the maximum end-to-end backlog. Finally, we simulate the LWF algorithm together with a well known algorithm (the back-pressure algorithm) and a large-deviations optimal algorithm in terms of the sum-queue (the P-TREE algorithm) in converge-cast networks. Our simulation shows that our algorithm significantly performs better not only in terms of Asymptotic Decay-rate, but also in terms of the actual overflow probability.
-
On the queue-overflow probabilities of a class of distributed scheduling algorithms
Computer Networks, 2011Co-Authors: Can Zhao, Xiaojun LinAbstract:In this paper, we are interested in using large-deviations theory to characterize the Asymptotic Decay-rate of the queue-overflow probability for distributed wireless scheduling algorithms, as the overflow threshold approaches infinity. We consider ad hoc wireless networks where each link interferes with a given set of other links, and we focus on a distributed scheduling algorithm called Q-SCHED, which is introduced by Gupta et al. First, we derive a lower bound on the Asymptotic Decay rate of the queue-overflow probability for Q-SCHED. We then present an upper bound on the Decay rate for all possible algorithms operating on the same network. Finally, using these bounds, we are able to conclude that, subject to a given constraint on the Asymptotic Decay rate of the queue-overflow probability, Q-SCHED can support a provable fraction of the offered loads achievable by any algorithms.
-
CDC - On the queue-overflow probabilities of distributed scheduling algorithms
Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, 2009Co-Authors: Can Zhao, Xiaojun LinAbstract:In this paper, we are interested in using large-deviations theory to characterize the Asymptotic Decay-rate of the queue-overflow probability for distributed wireless scheduling algorithms, as the overflow threshold approaches infinity. We consider ad-hoc wireless networks where each link interferes with a given set of other links, and we focus on a distributed scheduling algorithm called Q-SCHED, which is introduced by Gupta et al. First, we derive a lower bound on the Asymptotic Decay rate of the queue-overflow probability for Q-SCHED. We then present an upper bound on the Decay rate for all possible algorithms operating on the same network. Finally, using these bounds, we are able to conclude that, subject to a given constraint on the Asymptotic Decay rate of the queue-overflow probability, Q-SCHED can support a provable fraction of the offered loads achievable by any algorithms.
-
On the large-deviations optimality of scheduling policies minimizing the drift of a Lyapunov function
2009 47th Annual Allerton Conference on Communication Control and Computing (Allerton), 2009Co-Authors: Xiaojun Lin, V. J. VenkataramananAbstract:We show that for a large class of scheduling algorithms, when the algorithm minimizes the drift of a Lyapunov function, the algorithm is optimal in maximizing the Asymptotic Decay-rate of the probability that the Lyapunov function value exceeds a large threshold. The result in this paper extends our prior results to the important and practically-useful case when the Lyapunov function is not linear in scale, in which case the evolution of the fluid-sample-paths becomes more difficult to track. We use the notion of generalized fluid-sample-paths to address this difficulty, and provide easy-to-verify conditions for checking the large-deviations optimality of scheduling algorithms. As an immediate application of the result, we show that the log-rule is optimal in maximizing the Asymptotic Decay-rate of the probability that the sum queue exceeds a threshold B.
Attahiru Sule Alfa - One of the best experts on this subject based on the ideXlab platform.
-
Tail Probability of Low-Priority Queue Length in a Discrete-Time Priority BMAP/PH/1 Queue
Stochastic Models, 2005Co-Authors: Jungong Xue, Attahiru Sule AlfaAbstract:ABSTRACT We investigate the tail probability of the queue length of low-priority class for a discrete-time priority BMAP/PH/1 queue that consists of two priority classes, with BMAP (Batch Markovian Arrival Process) arrivals of high-priority class and MAP (Markovian Arrival Process) arrivals of low-priority class. A sufficient condition under which this tail probability has the Asymptotically geometric property is derived. A method is designed to compute the Asymptotic Decay rate if the Asymptotically geometric property holds. For the case when the BMAP for high-priority class is the superposition of a number of MAP's, though the parameter matrices representing the BMAP is huge in dimension, the sufficient condition is numerically easy to verify and the Asymptotic Decay rate can be computed efficiently.
-
Accurate bounds for the Asymptotic constant in a statistical multiplexer with homogeneous generalized binary Markov sources
Journal of Applied Probability, 2003Co-Authors: J. Xue, Attahiru Sule AlfaAbstract:This paper considers the Asymptotic tail distribution of the number of cells queued in a statistical multiplexer fed with homogeneous generalized binary Markov sources. As the Asymptotic Decay rate is easy to obtain, we focus our effort on bounding the Asymptotic constant, which is dependent on the initial phase combination of the sources and is hard to compute even for a moderate number of sources. We derive upper and lower bounds for the Asymptotic constant, taking the initial phase combination into account. Numerical experiments show the accuracy of these bounds. They also show that, while the Asymptotic Decay rates are the same, the variation of initial phase combination of the sources may significantly affect the Asymptotic constants.
-
perturbation theory for the Asymptotic Decay rates in the queues with markovian arrival process and or markovian service process correction
Queueing Systems, 2001Co-Authors: Attahiru Sule Alfa, Jungong XueAbstract:Three kinds of queues with Markovian arrival process and/or Markovian service process, are considered in this paper. In great generality, their basic steady-state distributions have Asymptotically exponential tails. We investigate the sensitivity of these Asymptotic Decay rates to the small entrywise perturbations in the parameter matrices of the Markovian arrival process.
-
Perturbation Theory for the Asymptotic Decay Rates in the Queues with Markovian Arrival Process and/or Markovian Service Process – Correction
Queueing Systems, 2001Co-Authors: Attahiru Sule Alfa, Jungong XueAbstract:Three kinds of queues with Markovian arrival process and/or Markovian service process, are considered in this paper. In great generality, their basic steady-state distributions have Asymptotically exponential tails. We investigate the sensitivity of these Asymptotic Decay rates to the small entrywise perturbations in the parameter matrices of the Markovian arrival process.
Alexander Pronin - One of the best experts on this subject based on the ideXlab platform.
-
nanosecond rise time laser produced stress pulses with no Asymptotic Decay
Review of Scientific Instruments, 1993Co-Authors: Vijay Gupta, Jun Yuan, Alexander ProninAbstract:Stress pulses with rise times of 1.14 ns and amplitudes in excess of 3 GPa are produced using an Nd:YAG laser. In contrast to pulse profile assuming an Asymptotic tail at about 5% to 10% of the peak stress, the pulses reported here show much sharper, post‐peak Decays resulting in a zero stress at about 17 ns. Use of such stress pulses in the determination of the tensile strength of planar interfaces between thin coatings of 0.1‐μm thickness and substrates is also discussed.
-
Nanosecond rise‐time laser‐produced stress pulses with no Asymptotic Decay
Review of Scientific Instruments, 1993Co-Authors: Vijay Gupta, Jun Yuan, Alexander ProninAbstract:Stress pulses with rise times of 1.14 ns and amplitudes in excess of 3 GPa are produced using an Nd:YAG laser. In contrast to pulse profile assuming an Asymptotic tail at about 5% to 10% of the peak stress, the pulses reported here show much sharper, post‐peak Decays resulting in a zero stress at about 17 ns. Use of such stress pulses in the determination of the tensile strength of planar interfaces between thin coatings of 0.1‐μm thickness and substrates is also discussed.
Robert Evans - One of the best experts on this subject based on the ideXlab platform.
-
Structural crossover in a model fluid exhibiting two length scales: Repercussions for quasicrystal formation.
Physical Review E, 2018Co-Authors: Morgan C. Walters, Andrew J. Archer, Priya Subramanian, Robert EvansAbstract:We investigate the liquid state structure of the two-dimensional model introduced by Barkan et al. [Phys. Rev. Lett. 113, 098304 (2014)10.1103/PhysRevLett.113.098304], which exhibits quasicrystalline and other unusual solid phases, focusing on the radial distribution function g(r) and its Asymptotic Decay r→∞. For this particular model system, we find that as the density is increased there is a structural crossover from damped oscillatory Asymptotic Decay with one wavelength to damped oscillatory Asymptotic Decay with another distinct wavelength. The ratio of these wavelengths is ≈1.932. Following the locus in the phase diagram of this structural crossover leads directly to the region where quasicrystals are found. We argue that identifying and following such a crossover line in the phase diagram towards higher densities where the solid phase(s) occur is a good strategy for finding quasicrystals in a wide variety of systems. We also show how the pole analysis of the Asymptotic Decay of equilibrium fluid correlations is intimately connected with the nonequilibrium growth or Decay of small-amplitude density fluctuations in a bulk fluid.
-
Asymptotic Decay of pair correlations in a Yukawa fluid
Physical Review E, 2005Co-Authors: Paul Hopkins, Andrew J. Archer, Robert EvansAbstract:We analyze the r-->infinity Asymptotic Decay of the total correlation function h (r) for a fluid composed of particles interacting via a (point) Yukawa pair potential. Such a potential provides a simple model for dusty plasmas. The Asymptotic Decay is determined by the poles of the liquid structure factor in the complex plane. We use the hypernetted-chain closure to the Ornstein-Zernike equation to determine the line in the phase diagram, well removed from the freezing transition line, where crossover occurs in the ultimate Decay of h (r) , from monotonic to damped oscillatory. We show that (i) crossover takes place via the same mechanism (coalescence of imaginary poles) as in the classical one-component plasma and in other models of Coulomb fluids and (ii) leading-order pole contributions provide an accurate description of h (r) at intermediate distances r as well as at long range.
-
Asymptotic Decay of correlations in liquids and their mixtures
The Journal of Chemical Physics, 1994Co-Authors: Robert Evans, R. J. F. Leote De Carvalho, J. R. Henderson, David C. HoyleAbstract:We consider the Asymptotic Decay of structural correlations in pure fluids, fluid mixtures, and fluids subject to various types of inhomogeneity. For short ranged potentials, both the form and the amplitude of the longest range Decay are determined by leading order poles in the complex Fourier transform of the bulk structure factor. Generically, for such potentials, Asymptotic Decay falls into two classes: (i) controlled by a single simple pole on the imaginary axis (monotonic exponential Decay) and (ii) controlled by a conjugate pair of simple poles (exponentially damped oscillatory Decay). General expressions are given for the Decay length, the amplitude, and [in class (ii)] the wavelength and phase involved. In the case of fluid mixtures, we find that there is only one Decay length and (if applicable) one oscillatory wavelength required to specify the Asymptotic Decay of all the component density profiles and all the partial radial distribution functions gij(r). Moreover, simple amplitude relations lin...
-
Asymptotic Decay of liquid structure: oscillatory liquid-vapour density profiles and the Fisher-Widom line
Molecular Physics, 1993Co-Authors: Robert Evans, J. R. Henderson, David C. Hoyle, Andrew O. Parry, Zoheir SabeurAbstract:Recent work has highlighted the existence of a unified theory for the Asymptotic Decay of the density profile ρ(r) of an inhomogeneous fluid and of the bulk radial distribution function g(r). For a given short-ranged interatomic potential ρ(r) Decays into bulk in the same fashion as g(r), i.e. with the same exponential Decay length (α0/-1) and, for sufficiently high bulk density (ρb) and/or temperature (T), oscillatory wavelength (2π/α1). The quantities α0 and α1 are determined by a linear stability analysis of the bulk fluid; they depend on only the bulk direct correlation function. In this paper we reintroduce the concept of the Fisher-Widom (FW) line. This line was originally introduced, in say the (ρb, T plane, as that which separates pure exponential from exponentially damped oscillatory Decay of g(r). We explore the relevance of the FW line for the form of the density profile at a liquid-vapour interface. Using a weighted density approximation (WDA) density functional theory we locate the FW line fo...
