Search

We establish functional central limit theorems (FCLTs) for a cumulative input process to a fluid queue from the superposition of independent on–off sources, where the on periods and off periods may have heavy-tailed probability distributions. Variants of these FCLTs hold for cumulative busy-time and idle-time processes associated with standard queueing models. The heavy-tailed on-period and off-period distributions can cause the limit process to have discontinuous sample paths (e.g., to be a non-Brownian stable process or more general Lévy process) even though the converging processes have continuous sample paths. Consequently, we exploit the Skorohod M1 topology on the function space D of right-continuous functions with left limits. The limits here combined with the previously established continuity of the reflection map in the M1 topology imply both heavy-traffic and non-heavy-traffic FCLTs for buffer-content processes in stochastic fluid networks.

We review functional central limit theorems (FCLTs) for the queue-content process in a single-server queue with finite waiting room and the first-come first-served service discipline. We emphasize alternatives to the familiar heavy-traffic FCLTs with reflected Brownian motion (RBM) limit process that arise with heavy-tailed probability distributions and strong dependence. Just as for the familiar convergence to RBM, the alternative FCLTs are obtained by applying the continuous mapping theorem with the reflection map to previously established FCLTs for partial sums. We consider a discrete-time model and first assume that the cumulative net-input process has stationary and independent increments, with jumps up allowed to have infinite variance or even infinite mean. For essentially a single model, the queue must be in heavy traffic and the limit is a reflected stable process, whose steady-state distribution can be calculated by numerically inverting its Laplace transform. For a sequence of models, the queue need not be in heavy traffic, and the limit can be a general reflected Levy process. When the Levy process representing the net input has no negative jumps, the steady-state distribution of the reflected Levy process again can be calculated by numerically inverting its Laplace transform. We also establish FCLTs for the queue-content process when the input process is a superposition of many independent component arrival processes, each of which may exhibit complex dependence. Then the limiting input process is a Gaussian process. When the limiting net-input process is also a Gaussian process and there is unlimited waiting room, the steady-state distribution of the limiting reflected Gaussian process can be conveniently approximated.

By exploiting an infinite-server-model lower bound, we show that the tails of the steady-state and transient waiting-time distributions in the M/GI/s queue with unlimited waiting room and the first-come first-served discipline are bounded below by tails of Poisson distributions. As a consequence, the tail of the steady-state waiting-time distribution is bounded below by a constant times the sth power of the tail of the service-time stationary-excess distribution. We apply that bound to show that the steady-state waiting-time distribution has a heavy tail (with appropriate definition) whenever the service-time distribution does. We also establish additional results that enable us to nearly capture the full asymptotics in both light and heavy traffic. The difference between the asymptotic behavior in these two regions shows that the actual asymptotic form must be quite complicated.

O.J. Boxma and J.W. Cohen recently obtained an explicit expression for the M/G/1 steady-state waiting-time distribution for a class of service-time distributions with power tails. We extend their explicit representation from a one-parameter family of service-time distributions to a two-parameter family. The complementary cumulative distribution function (ccdf's) of the service times all have the asymptotic form F^c(t)~@at^-^3^/^2 as t->~, so that the associated waiting-time ccdf's have asymptotic form W^c(t)~@bt^-^1^/^2 as t->~. Thus the second moment of the service time and the mean of the waiting time are infinite. Our result here also extends our own earlier explicit expression for the M/G/1 steady-state waiting-time distribution when the service-time distribution is an exponential mixture of inverse Gaussian distributions (EMIG). The EMIG distributions form a two-parameter family with ccdf having the asymptotic form F^c(t)~@at^-^3^/^2e^-^@h^t as t->~. We now show that a variant of our previous argument applies when the service-time ccdf is an undamped EMIG, i.e., with ccdf G^c(t)=e^@h^tF^c(t) for F^c(t) above, which has the power tail G^c(t)~@at^-^3^/^2 as t->~. The Boxma-Cohen long-tail service-time distribution is a special case of an undamped EMIG.

This paper proposes an optimization model of incorporating competence sets of group decision makers to maximize the total benefit of the whole group. Such an incorporation model is formulated as finding a deduction graph linked from the nodes of existing competencies to the nodes of desired competencies. Compared with other methods treating competence set problems (Yu and Zhang 1991, Li and Yu 1994, and Shi and Yu 1996), the proposed model can solve problems involving multiple decision makers; in addition it allows the network to be cyclic and to contain compound nodes.

We introduce open stochastic fluid networks that can be regarded as continuous analogues or fluid limits of open networks of infinite-server queues. Random exogenous input may come to any of the queues. At each queue, a c.d.f.-valued stochastic process governs the proportion of the input processed by a given time after arrival. The routeing may be deterministic (a specified sequence of successive queue visits) or proportional, i.e. a stochastic transition matrix may govern the proportion of the output routed from one queue to another. This stochastic fluid network with deterministic c.d.f.s governing processing at the queues arises as the limit of normalized networks of infinite-server queues with batch arrival processes where the batch sizes grow. In this limit, one can think of each particle having an evolution through the network, depending on its time and place of arrival, but otherwise independent of all other particles. A key property associated with this independence is the linearity: the workload associated with a superposition of inputs, each possibly having its own pattern of flow through the network, is simply the sum of the component workloads. As with infinite-server queueing models, the tractability makes the linear stochastic fluid network a natural candidate for approximations.

We explore the issues of when and how to partition arriving customers into service groups that will be served separately, in a first-come first-served manner, by multiserver service systems having a provision for waiting, and how to assign an appropriate number of servers to each group. We assume that customers can be classified upon arrival, so that different service groups can have different service-time distributions. We provide methodology for quantifying the tradeoff between economies of scale associated with larger systems and the benefit of having customers with shorter service times separated from other customers with longer service times, as is done in service systems with express lines. To properly quantify this tradeoff, it is important to characterize service-time distributions beyond their means. In particular, it is important to also determine the variance of the service-time distribution of each service group. Assuming Poisson arrival processes, we then can model the congestion experienced by each server group as an M/G/squeue with unlimited waiting room. We use previously developed approximations for M/G/sperformance measures to quickly evaluate alternative partitions.

In order to numerically invert Laplace transforms to calculate probability density functions (pdf's) and cumulative distribution functions (cdf's) in queueing and related models, we need to be able to calculate the Laplace transform values. In many cases the desired Laplace transform values (e.g., of a waiting-time cdf) can be computed when the Laplace transform values of component pdf's (e.g., of a service-time pdf) can be computed. However, there are few explicit expressions for Laplace transforms of component pdf's available when the pdf does not have a pure exponential tail. In order to remedy this problem, we propose the construction of infinite-series representations for Laplace transforms of pdf's and show how they can be used to calculate transform values. We use the Laplace transforms of exponential pdf's, Laguerre functions and Erlang pdf's as basis elements in the series representations. We develop several specific parametric families of pdf's in this infinite-series framework. We show how to determine the asymptotic form of the pdf from the series representation and how to truncate so as to preserve the asymptotic form for a time of interest.

This paper investigates the possibility of predicting each customer's waiting time in queue before starting service in a multiserver service system with the first-come first-served service discipline, such as a telephone call center. A predicted waiting-time distribution or an appropriate summary statistic such as the mean or the 90th percentile may be communicated to the customer upon arrival and possibly thereafter in order to improve customer satisfaction. The predicted waiting-time distribution may also be used by the service provider to better manage the service system, e.g., to help decide when to add additional service agents. The possibility of making reliable predictions is enhanced by exploiting information about system state, including the number of customers in the system ahead of the current customer. Additional information beyond the number of customers in the system may be obtained by classifying customers and the service agents to which they are assigned. For nonexponential service times, the elapsed service times of customers in service can often be used to advantage to compute conditional-remaining-service-time distributions. Approximations are proposed to convert the distributions of remaining service times into the distribution of the desired customer waiting time. The analysis reveals the advantage from exploiting additional information.

This paper investigates the effect upon performance in a service system, such as a telephone call center, of giving waiting customers state information. In particular, the paper studies two M/M/s/r queueing models with balking and reneging. For simplicity, it is assumed that each customer is willing to wait a fixed time before beginning service. However, customers differ, so the delay tolerances for successive customers are random. In particular, it is assumed that the delay tolerance of each customer is zero with probability β, and is exponentially distributed with mean α−1 conditional on the delay tolerance being positive. Let N be the number of customers found by an arrival. In Model 1, no state information is provided, so that if N ≥ s, the customer balks with probability β; if the customer enters the system, he reneges after an exponentially distributed time with mean α−1 if he has not begun service by that time. In Model 2, if N = s + k ≥ s, then the customer is told the system state k and the remaining service times of all customers in the system, so that he balks with probability β + (1 − β)(1 − qk), where qk = P(T > Sk), T is exponentially distributed with mean α−1, Sk is the sum of k + 1 independent exponential random variables each with mean (sμ)−1, and μ−1 is the mean service time. In Model 2, all reneging is replaced by balking. The number of customers in the system for Model 1 is shown to be larger than that for Model 2 in the likelihood-ratio stochastic ordering. Thus, customers are more likely to be blocked in Model 1 and are more likely to be served without waiting in Model 2. Algorithms are also developed for computing important performance measures in these, and more general, birth-and-death models.

Motivated by interest in probability density functions (pdf's) with nonexponential tails in queueing and related areas, we introduce and investigate two classes of beta mixtures of exponential pdf's. These classes include distributions introduced by Boxma and Cohen (1997) and Gaver and Jacobs (1998) to study queues with long-tail service-time distributions. When the standard beta pdf is used as the mixing pdf, we obtain pdf's with an exponentially damped power tail, i.e. as . This pdf decays exponentially, but analysis is complicated by the power term. When the beta pdf of the second kind is used as the mixing pdf, we obtain pdf's with a power tail, i.e. as . We obtain explicit representations for the cumulative distributions functions, Laplace transforms, moments and asymptotics by exploiting connections to the Tricomi function. Properties of the power-tail class can be deduced directly from properties of the other class, because the power-tail pdf's are undamped versions of the other pdf's. The power-ta...

We establish functional large deviation principles (FLDPs) for waiting and departure processes in single-server queues with unlimited waiting space and the first-in first-out service discipline. We apply the extended contraction principle to show that these processes obey FLDPs in the function space D with one of the nonuniform Skorohod topologies whenever the arrival and service processes obey FLDPs and the rate function is finite for appropriate discontinuous functions. We apply our previous FLDPs for inverse processes to obtain an FLDP for the waiting times in a queue with a superposition arrival process. We obtain FLDPs for queues within acyclic networks by showing that FLDPs are inherited by processes arising from the network operations of departure, superposition, and random splitting. For this purpose, we also obtain FLDPs for split point processes. For the special cases of deterministic arrival processes and deterministic service processes, we obtain convenient explicit expressions for the rate function of the departure process, but not more generally. In general, the rate function for the departure process evidently must be calculated numerically. We also obtain an FLDP for the departure process of completed work, which has important application to the concept of effective bandwidths for admission control and capacity planning in packet communication networks.

Multiprocessor load balancing aims to improve performance by moving jobs from highly loaded processors to more lightly loaded processors. Some schemes allow only migration of new jobs upon arrival, while other schemes allow migration of jobs in progress. A difficulty with all these schemes, however, is that they require continuously maintaining detailed state information. In this paper we consider the alternative of periodic load balancing, in which the loads are balanced only at each T time units for some appropriate T. With periodic load balancing, state information is only needed at the balancing times. Moreover, it is often possible to use slightly stale information collected during the interval between balancing times. In this paper we study the performance of periodic load balancing. We consider multiple queues in parallel with unlimited waiting space to which jobs come either in separate independent streams or by assignment (either random or cyclic) from a single stream. Resource sharing is achieved by periodically redistributing the jobs or the work in the system among the queues. The performance of these systems of queues coupled by periodic load balancing depends on the transient behavior of a single queue. We focus on useful approximations obtained by considering a large number of homogeneous queues and a heavy load. When the number of queues is sufficiently large, the number of jobs or quantity of work at each queue immediately after redistribution tends to evolve deterministically, by the law of large numbers. The steady-state (limiting) value of this deterministic sequence is obtained as the solution of a fixed point equation, where the initial value is equal to the expected transient value over the interval between successive redistributions conditional on the initial value. A refined approximation based on the central limit theorem is a normal distribution, where the mean and variance are obtained by solving a pair of fixed-point equations. With higher loads, which is natural to consider when load balancing is performed, a heavy-traffic limit theorem shows that one-dimensional reflected Brownian motion can be used to approximately describe system performance, even with general arrival and service processes. With these approximations, we show how performance depends on the assumed arrival pattern of jobs and the model parameters. We do numerical calculations and conduct simulation experiments to show the accuracy of the approximations.

Traffic measurements from communication networks have shown that network traffic is quite complex, exhibiting phenomena such as long-tail probability distributions, long-range dependence and self similarity. Thus, in order to design and control new communication networks, we are motivated to consider new source traffic models and new ways to analyze network performance when there are many independent sources each with traffic that can be described by such models. We present a candidate source traffic model: The required bandwidth (arrival rate) as a function of time for each source is represented as the sum of two stochastic processes: (1) a macroscopic (longer-time-scale) level process and (2) a microscopic (shorter-time-scale) within-level variation process. We let the level process be a finite-state semi-Markov process (SMP), allowing general (possibly long-tail) level holding-time distributions, and we let the within-level variation process be a zero-mean piecewise-stationary process. To cope with the added model complexity, we suggest making design and control decisions based on the likelihood that aggregate demand (the input rate from a set of sources) will exceed capacity (the maximum possible output rate). This approach to model analysis avoids the customary queueing detail (focus on buffer content and overflow). We propose using transient analysis for control, conditioning on the level and elapsed level holding time of each source. In doing so, we exploit asymptotics associated with multiplexing a large number of sources.

We show how to compute the time-dependent blocking probability given an arbitrary initial state, the distribution of the time that all servers first become busy given an arbitrary initial state, the time-dependent mean number of busy servers given an arbitrary initial state, and the stationary covariance function for the number of busy servers over time in the Erlang loss model by numerically inverting the Laplace transforms of these quantities with respect to time. Algorithms for computing the transforms are available in the literature, but they do not seem to be widely known. We derive a new revealing expression for the transform of the covariance function. We show that the inversion algorithm is effective for large systems by doing examples with up to 10,000 servers. We also show that computations for very large systems (e.g., 106 servers) can be done with computations for moderately sized systems (e.g., 102-103 servers) and scaling associated with the heavy-traffic limit involving convergence of a nor...

Traffic measurements from communication networks have shown that many quantities charecterizing network performance have long-tail probability distributions, i.e., with tails that decay more slowly than exponentially. File lengths, call holding times, scene lengths in MPEG video streams, and intervals between connection requests in Internet traffic all have been found to have long-tail distributions, being well described by distributions such as the Pareto and Weibull. It is known that long-tail distributions can have a dramatic effect upon performance, e.g., long-tail service-time distributions cause long-tail waiting-time distributions in queues, but it is often difficult to describe this effect in detail, because performance models with component long-tail distributions tend to be difficult to analyze. We address this problem by developing an algorithm for approximating a long-tail distribution by a hyperexponential distribution (a finite mixture of exponentials). We first prove that, in prinicple, it is possible to approximate distributions from a large class, including the Pareto and Weibull distributions, arbitrarily closely by hyperexponential distributions. Then we develop a specific fitting alogrithm. Our fitting algorithm is recursive over time scales, starting with the largest time scale. At each stage, an exponential component is fit in the largest remaining time scale and then the fitted exponential component is subtracted from the distribution. Even though a mixture of exponentials has an exponential tail, it can match a long-tail distribution in the regions of primary interest when there are enough exponential components. When a good fit is achieved, the approximating hyperexponential distribution inherits many of the difficulties of the original long-tail distribution; e.g., it is still difficult to obtain reliable estimates from simulation experiments. However, some difficulties are avoided; e.g., it is possible to solve some queueing models that could not be solved before. We give examples showing that the fitting procedure is effective, both for directly matching a long-tail distribution and for predicting the performance in a queueing model with a long-tail service-time distribution.

A many-server heavy-traffic FCLT is proved for the $G_t/M/s_t+\mathit {GI}$ queueing model, having time-varying arrival rate and staffing, a general arrival process satisfying a FCLT, exponential service times and customer abandonment according to a general probability distribution. The FCLT provides theoretical support for the approximating deterministic fluid model the authors analyzed in a previous paper and a refined Gaussian process approximation, using variance formulas given here. The model is assumed to alternate between underloaded and overloaded intervals, with critical loading only at the isolated switching points. The proof is based on a recursive analysis of the system over these successive intervals, drawing heavily on previous results for infinite-server models. The FCLT requires careful treatment of the initial conditions for each interval., Published in at http://dx.doi.org/10.1214/13-AAP927 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We identify conditions under which relatively large buffers will be required in broadband communication networks. For this purpose, we analyze an infinite-capacity stochastic fluid model with a general stationary environment process (without the usual independence or Markov assumptions). With that level of generality, we are unable to establish asymptotic results, but by a very simple argument we are able to obtain a revealing lower bound on the steady-state buffer-content tail probability. The bounding argument shows that the steady-state buffer content will have a long-tail distribution when the sojourn time in a set of states with positive net input rate itself has a long-tail distribution. If a set of independent sources, each with a general stationary environment process, produces a positive net flow when all are in high-activity states, and if each of these sources has a high-activity sojourn-time distribution with a long tail, then the steady-state buffer-content distribution will have a long tail, but possibly one that decays faster than the tail for any single component source. The full buffer-content distribution can be derived in the special case of a two-state fluid model with general high- and low-activity-time distributions, assuming that successive high- and low-activity times come from independent sequences of i.i.d. random variables. In that case the buffer-content distribution will have a long tail when the high-activity-time distribution has a long tail. We illustrate by giving numerical examples of the two-state model based on numerical transform inversion.

We develop deterministic fluid approximations to describe the recovery from rare congestion events in a large multi-server system in which customer holding times have a general distribution. There are two cases, depending on whether or not we exploit the age distribution (the distribution of elapsed holding times of customers in service). If we do not exploit the age distribution, then the rare congestion event is a large number of customers present. If we do exploit the age distribution, then the rare event is an unusual age distribution, possibly accompanied by a large number of customers present. As an approximation, we represent the large multi-server system as an M/G/\infty model. We prove that, under regularity conditions, the fluid approximations are asymptotically correct as the arrival rate increases. The fluid approximations show the impact upon the recovery time of the holding-time distribution beyond its mean. The recovery time may or not be affected by the holding-time distribution having a long tail, depending on the precise definition of recovery. The fluid approximations can be used to analyze various overload control schemes, such as reducing the arrival rate or interrupting services in progress. We also establish large deviations principles to show that the two kinds of rare events have the same exponentially small order. We give numerical examples showing the effect of the holding-time distribution and the age distribution, focusing especially on the consequences of long-tail distributions.

We consider an infinite-capacity s-server queue in a finite-state random environment, where the traffic intensity exceeds 1 in some environment states and the environment states change slowly relative to arrivals and service completions. Queues grow in unstable environment states, so that it is useful to look at the system in the time scale of mean environment-state sojourn times. As the mean environment-state sojourn times grow, the queue-length and workload processes grow. However, with appropriate normalizations, these processes converge to fluid processes and diffusion processes. The diffusion process in a random environment is a refinement of the fluid process in a random environment. We show how the scaling in these limits can help explain numerical results for queues in slowly changing random environments. For that purpose, we apply recently developed numerical-transform-inversion algorithms for the MAP/G/1 queue and the piecewise-stationary Mt/Gt/1 queue

We consider a generalization of the classical Erlang loss model with both retrials of blocked calls and a time?dependent arrival rate. We make exponential?distribution assumptions so that the number of calls in progress and the number of calls in retry mode form a nonstationary, two?dimensional, continuous?time Markov chain. We then approximate the behavior of this Markov chain by two coupled nonstationary, one?dimensional Markov chains, which we solve numerically. We also develop an efficient method for simulating the two?dimensional Markov chain based on performing many replications within a single run. Finally, we evaluate the approximation by comparing it to the simulation. Numerical experience indicates that the approximation does very well in predicting the time?dependent mean number of calls in progress and the times of peak blocking. The approximation of the time?dependent blocking probability also is sufficiently accurate to predict the number of lines needed to satisfy blocking probability requirements.

We consider the classical M/G/1 queue with two priority classes and the nonpreemptive and preemptive-resume disciplines. We show that the low-priority steady-state waiting-time can be expressed as a geometric random sum of i.i.d. random variables, just like the M/G/1 FIFO waiting-time distribution. We exploit this structures to determine the asymptotic behavior of the tail probabilities. Unlike the FIFO case, there is routinely a region of the parameters such that the tail probabilities have non-exponential asymptotics. This phenomenon even occurs when both service-time distributions are exponential. When non-exponential asymptotics holds, the asymptotic form tends to be determined by the non-exponential asymptotics for the high-priority busy-period distribution. We obtain asymptotic expansions for the low-priority waiting-time distribution by obtaining an asymptotic expansion for the busy-period transform from Kendall’s functional equation. We identify the boundary between the exponential and non-exponential asymptotic regions. For the special cases of an exponential high-priority service-time distribution and of common general service-time distributions, we obtain convenient explicit forms for the low-priority waiting-time transform. We also establish asymptotic results for cases with long-tail service-time distributions. As with FIFO, the exponential asymptotics tend to provide excellent approximations, while the non-exponential asymptotics do not, but the asymptotic relations indicate the general form. In all cases, exact results can be obtained by numerically inverting the waiting-time transform.

In this paper we consider the M_t /G/\infty queueing model with infinitely many servers and a nonhomogeneous Poisson arrival process. Our goal is to obtain useful insights and formulas for nonstationary finite-server systems that commonly arise in practice. Here we are primarily concerned with the peak congestion. For the infinite-server model, we focus on the maximum value of the mean number of busy servers and the time lag between when this maximum occurs and the time that the maximum arrival rate occurs. We describe the asymptotic behavior of these quantities as the arrival changes more slowly, obtaining refinements of previous simple approximations. In addition to providing improved approximations, these refinements indicate when the simple approximations should perform well. We obtain an approximate time-dependent distribution for the number of customers in service in associated finite-server models by using the modified-offered-load (MOL) approximation, which is the finite-server steady-state distribution with the infinite-server mean serving as the offered load. We compare the value and lag in peak congestion predicted by the MOL approximation with exact values for M_t/M/s delay models with sinusoidal arrival-rate functions obtained by numerically solving the Chapman–Kolmogorov forward equations. The MOL approximation is remarkably accurate when the delay probability is suitably small. To treat systems with slowly varying arrival rates, we suggest focusing on the form of the arrival-rate function near its peak, in particular, on its second and third derivatives at the peak. We suggest estimating these derivatives from data by fitting a quadratic or cubic polynomial in a suitable interval about the peak.

We derive optimal gambling and investment policies for cases in which the underlying stochastic process has parameter values that are unobserved random variables. For the objective of maximizing logarithmic utility when the underlying stochastic process is a simple random walk in a random environment, we show that a state-dependent control is optimal, which is a generalization of the celebrated Kelly strategy: the optimal strategy is to bet a fraction of current wealth equal to a linear function of the posterior mean increment. To approximate more general stochastic processes, we consider a continuous-time analog involving Brownian motion. To analyze the continuous-time problem, we study the diffusion limit of random walks in a random environment. We prove that they converge weakly to a Kiefer process, or tied-down Brownian sheet. We then find conditions under which the discrete-time process converges to a diffusion, and analyze the resulting process. We analyze in detail the case of the natural conjugate prior, where the success probability has a beta distribution, and show that the resulting limit diffusion can be viewed as a rescaled Brownian motion. These results allow explicit computation of the optimal control policies for the continuous-time gambling and investment problems without resorting to continuous-time stochastic-control procedures. Moreover they also allow an explicit quantitative evaluation of the financial value of randomness, the financial gain of perfect information and the financial cost of learning in the Bayesian problem.

Motivated by telecommunication applications, we investigate ways to estimate the parameters of a nonhomogeneous Poisson process with linear rate over a finite interval, based on the number of counts in measurement subintervals. Such a linear arrival-rate function can serve as a component of a piecewise-linear approximation to a general arrival-rate function. We consider ordinary least squares (OLS), iterative weighted least squares (IWLS) and maximum likelihood (ML), all constrained to yield a nonnegative rate function. We prove that ML coincides with IWLS. As a reference point, we also consider the theoretically optimal weighted least squares (TWLS), which is least squares with weights inversely proportional to the variances (which would not be known with data). Overall, ML performs almost as well as TWLS. We describe computer simulations conducted to evaluate these estimation procedures. None of the procedures differ greatly when the rate function is not near 0 at either end, but when the rate function is near 0 at one end, TWLS and ML are significantly more effective than OLS. The number of measurement subintervals (with fixed total interval) makes surprisingly little difference when the rate function is not near 0 at either end. The variances are higher with only two or three subintervals, but there usually is little benefit from going above ten. In contrast, more measurement intervals help TWLS and ML when the rate function is near 0 at one end. We derive explicit formulas for the OLS variances and the asymptotic TWLS variances (as the number of measurement intervals increases), assuming the nonnegativity constraints are not violated. These formulas reveal the statistical precision of the estimators and the influence of the parameters and the method. Knowing how the variance depends on the interval length can help determine how to approximate general arrival-rate functions by piecewise-linear ones. We also develop statistical tests to determine whether the linear Poisson model is appropriate.

In this paper we investigate operators that map one or more probability distributions on the positive real line into another via their Laplace–Stieltjes transforms. Our goal is to make it easier to construct new transforms by manipulating known transforms. We envision the results here assisting modelling in conjunction with numerical transform inversion software. We primarily focus on operators related to infinitely divisible distributions and Lévy processes, drawing upon Feller (1971). We give many concrete examples of infinitely divisible distributions. We consider a cumulant-moment-transfer operator that allows us to relate the cumulants of one distribution to the moments of another. We consider a power-mixture operator corresponding to an independently stopped Lévy process. The special case of exponential power mixtures is a continuous analog of geometric random sums. We introduce a further special case which is remarkably tractable, exponential mixtures of inverse Gaussian distributions (EMIGs). EMIGs arise naturally as approximations for busy periods in queues. We show that the steady-state waiting time in an M/G/1 queue is the difference of two EMIGs when the service-time distribution is an EMIG. We consider several transforms related to first-passage times, e.g. for the M/M/1 queue, reflected Brownian motion and Lévy processes. Some of the associated probability density functions involve Bessel functions and theta functions. We describe properties of the operators, including how they transform moments.

We consider a multiserver service system with general nonstationary arrival and service-time processes in which s(t), the number of servers as a function of time, needs to be selected to meet projected loads. We try to choose s(t) so that the probability of a delay (before beginning service) hits or falls just below a target probability at all times. We develop an approximate procedure based on a time-dependent normal distribution, where the mean and variance are determined by infinite-server approximations. We demonstrate that this approximation is effective by making comparisons with the exact numerical solution of the Markovian Mt/M/st model.

A basic multiprocessor version of the makespan scheduling problem requires that n tasks be scheduled on m identical processors so as to minimize the latest task finishing time. In the standard probability model considered here, the task durations are i.i.d. random variables with a general distribution F having finite mean. Our main objective is to estimate the distribution of the makespan as a function of m n and F under the on-line greedy policy, i.e., where the tasks are put in sequence and assigned in order to processors whenever they become idle. Because of the difficulty of exact analysis, we concentrate on the asymptotic behavior as n→∞ or as both m→∞ and n→∞with m≥n. The focal point is the Markov chain giving the remaining processing times of the m — 1 tasks still running at task completion epochs. The theory of stationary marked point processes is used to show that the stationary distribution of this Markov chain coincides with the order statistics of m — 1 independent random variables having the ...

We consider an automatic overload control for two large service systems modeled as multi-server queues, such as call centers. We assume that the two systems are designed to operate independently, but want to help each other respond to unexpected overloads. The proposed overload control automatically activates sharing (sending some customers from one system to the other) once a ratio of the queue lengths in the two systems crosses an activation threshold (with ratio and activation threshold parameters for each direction). To prevent harmful sharing, sharing is allowed in only one direction at any time. In this paper, we are primarily concerned with ensuring that the system recovers rapidly after the overload is over, either (i) because the two systems return to normal loading or (ii) because the direction of the overload suddenly shifts in the opposite direction. To achieve rapid recovery, we introduce lower thresholds for the queue ratios, below which one-way sharing is released. As a basis for studying the complex dynamics, we develop a new six-dimensional fluid approximation for a system with time-varying arrival rates, extending a previous fluid approximation involving a stochastic averaging principle. We conduct simulations to confirm that the new algorithm is effective for predicting the system performance and choosing effective control parameters. The simulation and the algorithm both show that the system can experience an inefficient nearly-periodic behavior, corresponding to an oscillating equilibrium (congestion collapse), if the sharing is strongly inefficient and the control parameters are set inappropriately.

In this paper we consider a family of product-form loss models, including loss networks (or circuit-switched communication networks) and a class of resource-sharing models. There can be multiple classes of requests for multiple resources. Requests arrive according to independent Poisson processes. The requests can be for multiple units in each resource (the multi-rate case, e.g. several circuits on a trunk). There can be upper-limit and guaranteed-minimum sharing policies as well as the standard complete-sharing policy. If all the requirements of a request cannot be met upon arrival, then the request is blocked and lost. We develop an algorithm for computing the (exact) steady-state blocking probability of each class and other steady state descriptions in these loss models. The algorithm is based on numerically inverting generating functions of the normalization constants. In a previous paper we introduced this approach to product-form models and developed a full algorithm for a class of closed queueing networks. The inversion algorithm promises to be even more useful for loss models than for closed queueing networks because fewer alternative algorithms are available for loss models. Indeed, for many loss models with sharing policies other than traditional complete sharing, our algorithm is the first effective algorithm. Unlike some recursive algorithms, our algorithm has a low storage requirement. To treat the loss models here, we derive the generating functions of the normalization constants and develop a new scaling algorithm especially tailored to the loss models. In general, the computational complexity grows exponentially in the number of resources, but the computation can often be reduced dramatically by exploiting conditional decomposition based on special structure and by appropriately truncating large finite sums. We illustrate our numerical inversion algorithm by applying it to several examples. To validate our algorithm on small models, we also develop a direct algorithm. The direct algorithm itself is of interest, because it tends to be more efficient when the number of resources is large, but the number of request classes is small. Furthermore, it also allows a form of conditional decomposition based on special structure.

Limit theorems are established and relatively simple closed-form approximations are developed for the busy-period distribution in single-server queues. For the M/G/l queue, the complementary busy-period c.d.f. is shown to be asymptotically equivalent as t → ∞ to a scaled version of the heavy-traffic limit (obtained as p → 1), where the scaling parameters are based on the asymptotics as t → ∞. We call this the asymptotic normal approximation, because it involves the standard normal c.d.f. and density. The asymptotic normal approximation is asymptotically correct as t → ∞ for each fixed p and as p → 1 for each fixed t and yields remarkably good approximations for times not too small, whereas the direct heavy-traffic (p → 1) and asymptotic (t → ∞) limits do not yield such good approximations. Indeed, even the approximation based on three terms of the standard asymptotic expansion does not perform well unless t is very large. As a basis for generating corresponding approximations for the busy-period distribution in more general models, we also establish a more general heavy-traffic limit theorem.

Motivated by extreme-value engineering in service systems, we develop and evaluate simple approximations for the distributions of maximum values of queueing processes over large time intervals. We provide approximations for several different processes, such as the waiting times of successive customers, the remaining workload at an arbitrary time, and the queue length at an arbitrary time, in a variety of models. All our approximations are based on extreme-value limit theorems. Our first approach is to approximate the queueing process by one-dimensional reflected Brownian motion (RBM). We then apply the extremevalue limit for RBM, which we derive here. Our second approach starts from exponential asymptotics for the tail of the steady-state distribution. We obtain an approximation by relating the given process to an associated sequence of i.i.d. random variables with the same asymptotic exponential tail. We use estimates of the asymptotic variance of the queueing process to determine an approximate number of variables in this associated i.i.d. sequence. Our third approach is to simplify GI/G/1 extreme-value limiting formulas in Iglehart [25] by approximating the distribution of an idle period by the stationary-excess distribution of an interarrival time. We use simulation to evaluate the quality of these approximations for the maximum workload. From the simulations we obtain a rough estimate of the time when the extreme-value limit theorems begin to yield good approximations.

The stationary Erlang loss model is a classic example of an insensitive queueing system: the steady-state distribution of the number of busy servers depends on the service-time distribution only through its mean. However, when the arrival process is a nonstationary Poisson process, the insensitivity property is lost. We develop a simple, effective numerical algorithm for the Mt/PH/s/0 model with two service phases and a nonhomogeneous Poisson arrival process, and apply it to show that the time-dependent blocking probability with nonstationary input can be strongly influenced by the service-time distribution beyond the mean. With sinusoidal arrival rates, the peak blocking probability typically increases as the service-time distribution gets less variable. The influence of the service-time distribution, including this seemingly anomalous behavior, can be understood and predicted from the modified-offered-load and stationary-peakedness approximations, which exploit exact results for related infinite-server models.

A lockup period for investment in a hedge-fund is a time period after making the investment during which an investor cannot freely redeem his investment. Since long lockup periods have recently been imposed, it is important to estimate the premium an investor should expect from extended lockups. For this, Derman et al. (Wilmott J. 1(5–6):263–293, 2009) proposed a parsimonious three-state discrete-time Markov Chain (DTMC) to model the state of a hedge fund, allowing the state to change randomly among the states “good,” “sick” and “dead” every year. In this paper, we propose an alternative three-state absorbing continuous-time Markov Chain (CTMC) model, which allows state changes continuously in time instead of yearly. Allowing more dynamic state changes is more realistic, but the CTMC model requires new techniques for parameter fitting. We employ nonlinear programming to solve the new calibration equations. We show that the more realistic CTMC model is a viable alternative to the previous DTMC model for estimating the premium for extended hedge fund lockups.

We construct a version of the recently developed Poisson-Arrival-Location Model (PALM) to study communicating mobiles on a highway, giving the distribution of calls in progress and handoffs as a function of time and space. In a PALM arrivals generated by a nonhomogeneous Poisson process move independently through a general state space according to a location stochastic process. If, as an approximation, we ignore capacity constraints, then we can use this model to describe the performance of wireless communication systems. Our basic model here is for traffic on a one-way, single-lane, semi-infinite highway, with movement specified by a deterministic location function. For the highway PALM considered here, key quantities are the call density, the handoff rate, the call-origination-rate density and the call-termination-rate density, which themselves are simply related by two fundamental conservation equations. We show that the basic highway PALM can be applied, together with independent superposition, to treat more complicated models. Our analysis provides connections between teletraffic theory and highway traffic theory.

We consider the standardGI/G/1 queue with unlimited waiting room and the first-in first-out service discipline. We investigate the steady-state waiting-time tail probabilitiesP(W>x) when the service-time distribution has a long-tail distribution, i.e., when the service-time distribution fails to have a finite moment generating function. We have developed algorithms for computing the waiting-time distribution by Laplace transform inversion when the Laplace transforms of the interarrival-time and service-time distributions are known. One algorithm, exploiting Pollaczek's classical contourintegral representation of the Laplace transform, does not require that either of these transforms be rational. To facilitate such calculations, we introduce a convenient two-parameter family of long-tail distributions on the positive half line with explicit Laplace transforms. This family is a Pareto mixture of exponential (PME) distributions. These PME distributions have monotone densities and Pareto-like tails, i.e., are of orderx −r forr>1. We use this family of long-tail distributions to investigate the quality of approximations based on asymptotics forP(W>x) asx→∞. We show that the asymptotic approximations with these long-tail service-time distributions can be remarkably inaccurate for typicalx values of interest. We also derive multi-term asymptotic expansions for the waiting-time tail probabilities in theM/G/1 queue. Even three terms of this expansion can be remarkably inaccurate for typicalx values of interest. Thus, we evidently must rely on numerical algorithms for determining the waiting-time tail probabilities in this case. When working with service-time data, we suggest using empirical Laplace transforms.

In this paper we describe the time-dependent moments of the workload process in the M/G/1 queue. The kth moment as a function of time can be characterized in terms of a differential equation involving lower moment functions and the time-dependent server-occupation probability. For general initial conditions, we show that the first two moment functions can be represented as the difference of two nondecreasing functions, one of which is the moment function starting at zero. The two nondecreasing components can be regarded as probability cumulative distribution function (cdf's) after appropriate normalization. The normalized moment functions starting empty are called moment cdf's; the other normalized components are called moment-difference cdf's. We establish relations among these cdf's using stationary-excess relations. We apply these relations to calculate moments and derivatives at the origin of these cdf's. We also obtain results for the covariance function of the stationary workload process. It is interesting that these various time-dependent characteristics can be described directly in terms of the steady-state workload distribution.

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.

Methods are developed for approximately characterizing the departure process of each customer class from a multi-class single-server queue with unlimited waiting space and the first-in-first-out service discipline. The model is σ(GT i /GI i )/1 with a non-Poisson renewal arrival process and a non-exponential service-time distribution for each class. The methods provide a basis for improving parametric-decomposition approximations for analyzing non-Markov open queueing networks with multiple classes. For example, parametric-decomposition approximations are used in the Queueing Network Analyzer (QNA). The specific approximations here extend ones developed by Bitran and Tirupati [5]. For example, the effect of class-dependent service times is considered here. With all procedures proposed here, the approximate variability parameter of the departure process of each class is a linear function of the variability parameters of the arrival processes of all the classes served at that queue, thus ensuring that the final arrival variability parameters in a general open network can be calculated by solving a system of linear equations.

We relate laws of large numbers and central limit theorems for nonstationary counting processes to corresponding limits for their inverse processes. We apply these results to develop approximations for queues that are unstable in a nonstationary manner. We obtain unstable nonstationary analogs of the queueing relation L = λ W and associated central-limit- theorem versions. For modeling and to obtain the first limits, we can construct nonstationary point processes as random time-transformations of familiar point processes, such as renewal processes and stationary point processes. We deduce the asymptotic behavior of the nonstationary point process from the asymptotic behavior of the familiar point process and the time transformation.

We show, under regularity conditions, that a counting process satisfies a large deviations principle in ℝ or the Gartner-Ellis condition (convergence of the normalized logarithmic moment generating functions) if and only if its inverse process does. We show, again under regularity conditions, that embedded regenerative structure is sufficient for the counting process or its inverse process to have exponential asymptotics, and thus satisfy the Gartner-Ellis condition. These results help characterize the small-tail asymptotic behavior of steady-state distributions in queueing models, e.g., the waiting time, workload and queue length.

Rate-control throttles with token banks or leaky buckets have been used for overload control in telecommunication systems and have been recommended for traffic policing in broadband integrated services digital networks (B-ISDN). Enhancing the token-bank throttle with a buffer to shape the admitted traffic has been suggested. Researchers have shown that the presence of the buffer can dramatically reduce the squared coefficient of variation of the interadmission time. However, the authors show that the impact of the buffer on longer-time-scale characteristics of the admitted traffic is much less dramatic. In particular, they show (primarily through simulations) that the job buffer has much less impact on higher values of the index of dispersion for intervals and on small tail probabilities for the steady-state number in system at a downstream queue (with only this one arrival stream). Indeed, the smoothing benefit of the job buffer decreases as longer-time-scale characteristics become more important. However, if the downstream queue is fed by many sources with throttles, as would be the case in most applications, then the relevant time scale at the downstream queue indeed becomes relatively short. The simulation results show that the benefit of traffic shaping can be much greater. The benefit gained in reduced buffer requirements at the downstream queue, though, is typically significantly less than the sum of all job buffers added to the throttles. A full cost/benefit analysis depends on the relative cost of buffer space in the two places and on details of the relevant application. >

We consider the standard single-server queue with unlimited waiting space and the first-in first-out service discipline, but without any explicit independence conditions on the interarrival and service times. We find conditions for the steady-state waiting-time distribution to have asymptotics of the form x –1 log P(W > x) → –θ ∗as x → ∞for θ ∗ > 0. We require only stationarity of the basic sequence of service times minus interarrival times and a Gärtner–Ellis condition for the cumulant generating function of the associated partial sums, i.e. n –1 log E exp (θSn ) → ψ (θ) as n → ∞, plus regularity conditions on the decay rate function ψ. The asymptotic decay rate θ is the root of the equation ψ (θ) = 0. This result in turn implies a corresponding asymptotic result for the steady-state workload in a queue with general non-decreasing input. This asymptotic result covers the case of multiple independent sources, so that it provides additional theoretical support for a concept of effective bandwidths for admission control in multiclass queues based on asymptotic decay rates.

We derive the two-dimensional transforms of the transient workload and queue-length distributions in the single-server queue with general service times and a batch Markovian arrival process (BMAP). This arrival process includes the familiar phase-type renewal process and the Markov modulated Poisson process as special cases, as well as superpositions of these processes, and allows correlated interarrival times and batch sizes. Numerical results are obtained via two-dimensional transform inversion algorithms based on the Fourier-series method. From the numerical examples we see that predictions of system performance based on transient and stationary performance measures can be quite different

An open-loop window flow-control scheme regulates the flow into a system by allowing at most a specified window size W of flow in any interval of length L. The sliding window considers all subintervals of length L, while the jumping window considers consecutive disjoint intervals of length L. To better understand how these window control schemes perform for stationary sources, we describe for a large class of stochastic input processes the asymptotic behavior of the maximum flow in such window intervals over a time interval [0,T] as T and Lget large, with T substantially bigger than L. We use strong approximations to show that when T≫L≫logT an invariance principle holds, so that the asymptotic behavior depends on the stochastic input process only via its rate and asymptotic variability parameters. In considerable generality, the sliding and jumping windows are asymptotically equivalent. We also develop an approximate relation between the two maximum window sizes. We apply the asymptotic results to develop approximations for the means and standard deviations of the two maximum window contents. We apply computer simulation to evaluate and refine these approximations.

We apply Tauberian theorems with known transforms to establish asymptotics for the basic steady-state distributions in the BMAP/G/l queue. The batch Markovian arrival process (BMAP)is equivalent to the versatile Markovian point process or Neuts (N) process; it generalizes the Markovian arrival process (MAP) by allowing batch arrivals. We consider the waiting time, the workload (virtual waiting time) and the queue lengths at an arbitrary time, just before an arrival and just after a departure. We begin by establishing asymptotics for steady-state distributions of M/G/1-type Markov chains. Then we treat steady-state distributions in the BMAP/G/l and MAP/MSP/l queues. The MSPis a MAPindependent of the arrival process generating service completions during

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 ...

We study an ordinary differential equation (ODE) arising as the many-server heavy-traffic fluid limit of a sequence of overloaded Markovian queueing models with two customer classes and two service pools. The system, known as the X model in the call-center literature, operates under the fixed-queue-ratio-with-thresholds (FQR-T) control, which we proposed in a recent paper as a way for one service system to help another in face of an unanticipated overload. Each pool serves only its own class until a threshold is exceeded; then one-way sharing is activated with all customer-server assignments then driving the two queues toward a fixed ratio. For large systems, that fixed ratio is achieved approximately. The ODE describes system performance during an overload. The control is driven by a queue-difference stochastic process, which operates in a faster time scale than the queueing processes themselves, thus achieving a time-dependent steady state instantaneously in the limit. As a result, for the ODE, the driving process is replaced by its long-run average behavior at each instant of time; i.e., the ODE involves a heavy-traffic averaging principle (AP)., 55 pages (43 pages plus 12 page appendix), 14 figures

In a recent paper we considered two networked service systems, each having its own customers and designated service pool with many agents, where all agents are able to serve the other customers, although they may do so inefficiently. Usually the agents should serve only their own customers, but we want an automatic control that activates serving some of the other customers when an unexpected overload occurs. Assuming that the identity of the class that will experience the overload or the timing and extent of the overload are unknown, we proposed a queue-ratio control with thresholds: When a weighted difference of the queue lengths crosses a prespecified threshold, with the weight and the threshold depending on the class to be helped, serving the other customers is activated so that a certain queue ratio is maintained. We then developed a simple deterministic steady-state fluid approximation, based on flow balance, under which this control was shown to be optimal, and we showed how to calculate the control parameters. In this sequel we focus on the fluid approximation itself and describe its transient behavior, which depends on a heavy-traffic averaging principle. The new fluid model developed here is an ordinary differential equation driven by the instantaneous steady-state probabilities of a fast-time-scale stochastic process. The averaging principle also provides the basis for an effective Gaussian approximation for the steady-state queue lengths. Effectiveness of the approximations is confirmed by simulation experiments.