Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

Fluid limits of many-server queues with abandonments,general service and continuous patience time distributions

This paper extends the works of Kang and Ramanan (2010) and Kaspi and Ramanan (2011), removing the hypothesis of absolute continuity of the service requirement and patience time distributions. We consider a many-server queueing system in which customers enter service in the order of arrival in a non-idling manner and where reneging is considerate. Similarly to Kang and Ramanan (2010), the dynamics of the system are represented in terms of a process that describes the total number of customers in the system as well as two measure-valued processes that record the age in service of each of the customers being served and the “potential” waiting times. When the number of servers goes to infinity, fluid limit is established for this triple of processes. The convergence is in the sense of probability and the limit is characterized by an integral equation.     

Multiscale diffusion approximations for stochastic networks in heavy traffic

Stochastic networks with time varying arrival and service rates and routing structure are studied. Time variations are governed by, in addition to the state of the system, two independent finite state Markov processes X and Y. The transition times of X are significantly smaller than typical inter-arrival and processing times whereas the reverse is true for the Markov process Y. By introducing a suitable scaling parameter one can model such a system using a hierarchy of time scales. Diffusion approximations for such multiscale systems are established under a suitable heavy traffic condition. In particular, it is shown that, under certain conditions, properly normalized buffer content processes converge weakly to a reflected diffusion. The drift and diffusion coefficients of this limit model are functions of the state process, the invariant distribution of X, and a finite state Markov process which is independent of the driving Brownian motion.     

The point process approach for fractionally differentiated random walks under heavy traffic

We prove some heavy-traffic limit theorems for some nonstationary linear processes which encompass the fractionally differentiated random walk as well as some FARIMA processes, when the innovations are in the domain of attraction of a non-Gaussian stable distribution. The results are based on an extension of the point process methodology to linear processes with nonsummable coefficients and make use of a new maximal type inequality.     

Steady state analysis of an M/G/1 queue with two phase service and Bernoulli vacation schedule under multiple vacation policy

This paper examines the steady state behaviour of a batch arrival queue with two phases of heterogeneous service along and Bernoulli schedule vacation under multiple vacation policy, where after two successive phases service or first vacation the server may go for further vacations until it finds a new batch of customer in the system. We carry out an extensive stationary analysis of the system, including existence of stationary regime, queue size distribution of idle period process, embedded Markov chain steady state distribution of stationary queue size, busy period distribution along with some system characteristics.     

Asymptotic behaviour of the tandem queueing system with identical service times at both queues

Consider a tandem queue consisting of two single-server queues in series, with a Poisson arrival process at the first queue and arbitrarily distributed service times, which for any customer are identical in both queues. For this tandem queue, we relate the tail behaviour of the sojourn time distribution and the workload distribution at the second queue to that of the (residual) service time distribution. As a by-result, we prove that both the sojourn time distribution and the workload distribution at the second queue are regularly varying at infinity of index 1−ν, if the service time distribution is regularly varying at infinity of index −ν (ν>1). Furthermore, in the latter case we derive a heavy-traffic limit theorem for the sojourn time S ⁽²⁾ at the second queue when the traffic load ρ↑ 1. It states that, for a particular contraction factor Δ (ρ), the contracted sojourn time Δ (ρ) S ⁽²⁾ converges in distribution to the limit distribution H(·) as ρ↑ 1 where .     

A scaling analysis of a star network with logarithmic weights

The paper investigates the properties of a class of resource allocation algorithms for communication networks: if a node of this network has $L$ requests to transmit and is idle, it tries to access the channel at a rate proportional to $log(1+L)$. A stochastic model of such an algorithm is investigated in the case of the star network, in which $J$ nodes can transmit simultaneously, but interfere with a central node 0 in such a way that node 0 cannot transmit while one of the other nodes does. One studies the impact of the log policy on these $J+1$ interacting communication nodes. A fluid scaling analysis of the network is derived with the scaling parameter $N$ being the norm of the initial state. It is shown that the asymptotic fluid behavior of the system is a consequence of the evolution of the state of the network on a specific time scale $(N^t,t\in (0,1))$. The main result is that, on this time scale and under appropriate conditions, the state of a node with index $j\ge 1$ is of the order of $N^{a_j\left(t\right)}$, with $0\le a_j\left(t\right)<1$, where $t?a_j\left(t\right)$ is a piecewise linear function. Convergence results on the fluid time scale and a stability property are derived as a consequence of this study.     

Optimal admission control in a queueing system with heterogeneous traffic

We consider optimal admission control of the GI/PH/1-type queueing system. The problem is then reduced to that of determining multi-threshold strategies. Some numerical examples are presented. The results have applications in the optimal input control of information flow in a computer communication network with heterogeneous traffic.     

On the long time behavior of the TCP window size process

The TCP window size process appears in the modeling of the famous transmission control protocol used for data transmission over the Internet. This continuous time Markov process takes its values in [0,∞)$[0,\infty )$, and is ergodic and irreversible. It belongs to the additive increase–multiplicative decrease class of processes. The sample paths are piecewise linear deterministic and the whole randomness of the dynamics comes from the jump mechanism. Several aspects of this process have already been investigated in the literature. In the present paper, we mainly get quantitative estimates for the convergence to equilibrium, in terms of the _W1$W_1$ Wasserstein coupling distance, for the process and also for its embedded chain.     

Conditional residual lifetimes of coherent systems

In this paper, we derive mixture representations for the reliability function of the conditional residual lifetime of a coherent system with n$n$ independent and identically distributed (i.i.d.) components under the condition that at least j$j$ and at most k−1$k-1$ (j<k$j<k$) components have failed by time t$t$. Based on these mixture representations, we then discuss stochastic comparisons of the conditional residual lifetimes of two coherent systems with independent and identical components.     

Exact asymptotics of supremum of a stationary Gaussian process over a random interval

Let {X(t):t∈[0,∞)} be a centered stationary Gaussian process. We study the exact asymptotics of P(sup_s∈[0,T]X(s)>u), as u→∞, where T is an independent of {X(t)} nonnegative random variable. It appears that the heaviness of T impacts the form of the asymptotics, leading to three scenarios: the case of integrable T, the case of T having regularly varying tail distribution with parameter λ∈(0,1) and the case of T having slowly varying tail distribution.     

Optimal control of assignment of jobs to processors under heavy traffic

The paper is concerned with the optimal control of the assignment of jobs from several arriving random streams to one of a bank of processors. Owing to the difficulty of the general problem, a heavy traffic approach is used. The required work depends on the processor to which it is assigned. The information that the assignment can be based on is quite flexible, and several information structures (data on which the control is based) are considered. The assignment can be made on arrival or when the job is to be processed. There can be bursty arrivals (the bursts depending on randomly varying environmental factors), rather general nonlinear cost functions and other complications. It is shown, under reasonably general conditions, that the optimal costs for the physical systems converge to the optimal cost for the heavy traffic limit problem, as the heavy traffic parameter goes to its limit. Numerical data is presented to illustrate some of the potential uses of the limit process for obtaining optimal contros, or controls satisfying optimal tradeoffs among competing criteria. The methods of proof are quite powerful tools for such optimal control problems     

Largest integral simplices with one interior integral point: Solution of Hensley's conjecture and related results

For each dimension d, d-dimensional integral simplices with exactly one interior integral point have bounded volume. This was first shown by Hensley. Explicit volume bounds were determined by Hensley, Lagarias and Ziegler, Pikhurko, and Averkov. In this paper we determine the exact upper volume bound for such simplices and characterize the volume-maximizing simplices. We also determine the sharp upper bound on the coefficient of asymmetry of an integral polytope with a single interior integral point. This result confirms a conjecture of Hensley from 1983. Moreover, for an integral simplex with precisely one interior integral point, we give bounds on the volumes of its faces, the barycentric coordinates of the interior integral point and its number of integral points. Furthermore, we prove a bound on the lattice diameter of integral polytopes with a fixed number of interior integral points. The presented results have applications in toric geometry and in integer optimization.     

Sample path moderate deviations for a family of long-range dependent traffic and associated queue length processes

We consider the long-range dependent cumulative traffic generated by the superposition of constant rate fluid sources having exponentially distributed intra start times and Pareto distributed durations with finite mean and infinite variance. We prove a sample path moderate deviation principle when the session intensity is increased and the processes are centered and scaled appropriately. The governing rate function is known from large deviation principles for the tail probabilities of fractional Brownian motion. We derive logarithmic tail asymptotics for associated queue length processes when the traffic loads an infinite buffer with constant service rate. The moderate deviation approximation of steady-state queue length tail probabilities is compared to those obtained by computer simulations.     

Heavy-traffic approximations for fractionally integrated random walks in the domain of attraction of a non-Gaussian stable distribution

We prove some heavy-traffic limit theorems for processes which encompass the fractionally integrated random walk as well as some FARIMA processes, when the innovations are in the domain of attraction of a non-Gaussian stable distribution.     

Virtual waiting times in priority-M/G/1 queues with vacations

In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the six models analysed, the Laplace-Stieltjes transform of the virtual waiting timeW _k(t) at timet of classk is derived by the method of collective marks. A sufficient condition for , whereU has the standard normal distribution, is also given.     

Using a Hybrid Evolutionary Algorithm to Minimize Variance in Response Time for Multimedia Object Requests

This research addresses the scheduling problem of multimedia object requests, which is an important problem in information systems, in particular, for World Wide Web applications. The performance measure considered is the variance of response time which is crucial as end users expect fair treatment to their service requests. This problem is known to be NP-hard. The literature survey indicates that two heuristics have been proposed to solve the problem. In this paper, we present a new heuristic, a hybrid evolutionary heuristic, which is shown to perform much better than the two existing ones, e.g., the overall average errors of the existing ones are 1.012 and 2.042 while the error of the proposed hybrid evolutionary heuristic is 0.154.