The G t /GI/s t +GI many-server fluid queue

This paper introduces a deterministic fluid model that approximates the many-server G _t /GI/s _t +GI queueing model, and determines the time-dependent performance functions. The fluid model has time-varying arrival rate and service capacity, abandonment from queue, and non-exponential service and patience distributions. Two key assumptions are that: (i)?the system alternates between overloaded and underloaded intervals, and (ii)?the functions specifying the fluid model are suitably smooth. An algorithm is developed to calculate all performance functions. It involves the iterative solution of a fixed-point equation for the time-varying rate that fluid enters service and the solution of an ordinary differential equation for the time-varying head-of-line waiting time, during each overloaded interval. Simulations are conducted to confirm that the algorithm and the approximation are effective.     

Processor sharing for two queues with vastly different rates

We consider a 2-class queueing system, operating under a generalized processor-sharing discipline, in an asymptotic regime where the arrival and service rates of the two classes are vastly different. We use regular and singular perturbation analyses in a small parameter measuring this difference in rates. It is assumed that the system is stable, and not close to instability. Three different regimes are analyzed, corresponding to an underloaded, an overloaded and a critically loaded fast queue, respectively. In the first two regimes the lowest order approximation to the joint stationary distribution of the queue lengths is derived. For a critically loaded fast queue only the mean queue lengths are investigated, and the asymptotic matching, to lowest order, with the results for an underloaded and an overloaded fast queue is established.      

Heavily loaded queue coupled to two underloaded queues

We consider a system of three parallel queues with Poisson arrivals and exponentially distributed service requirements. The service rate for the heavily loaded queue depends on which of the two underloaded queues are empty. We derive the lowest-order asymptotic approximation to the joint stationary distribution of the queue lengths, in terms of a small parameter measuring the closeness of the heavily loaded queue to instability. To this order the queue lengths are independent, and the underloaded queues and the heavily loaded queue have geometrically and, after suitable scaling, exponentially distributed lengths, respectively. The expression for the exponential decay rate for the heavily loaded queue involves the solution to an inhomogeneous linear functional equation. Explicit results are obtained for this decay rate when the two underloaded queues have vastly different arrival and service rates.     

Log-weight scheduling in switched networks

We consider switched queueing networks in which there are constraints on which queues may be served simultaneously. The scheduling policy for such a network specifies which queues to serve at any point in time. We introduce and study a variant of the popular maximum weight or backpressure policy which chooses the collection of queues to serve that has maximum weight. Unlike the maximum weight policies studied in the literature, the weight of a queue depends on logarithm of its queue-size in this paper. For any multihop switched network operating under such maximum log-weighted policy, we establish that the network Markov process is positive recurrent as long as it is underloaded. As the main result of this paper, a meaningful fluid model is established as the formal functional law of large numbers approximation. The fluid model is shown to be work-conserving. That is, work (or total queue-size) is nonincreasing as long as the network is underloaded or critically loaded. We identify invariant states or fixed points of the fluid model. When underloaded, null state is the unique invariant state. For a critically loaded fluid model, the space of invariant states is characterized as the solution space of an optimization problem whose objective is lexicographic ordering of total queue-size and the negative entropy of the queue state. An important contribution of this work is in overcoming the challenge presented by the log-weight function in establishing meaningful fluid model. Specifically, the known approaches in the literature primarily relied on the “scale invariance” property of the weight function that log-function does not possess.     

Change in Network Revenue Due to Changes in Capacities of Links

A multirate, loss network is investigated. The intensities of the traffic carried on each link, and the link capacities, are assumed to be commensurately large. An asymptotic approximation to the change in network revenue, due to small changes in the capacities of the links, is derived. A significant advantage of this approximation is that it is not necessary to specify which links are overloaded, critically loaded, or underloaded. Moreover, it is shown how to asymptotically calculate the change in revenue in terms of quantities which are already known for the unchanged network. This result has been used to calculate linearized capacity costs in the joint resource allocation and routing design of virtual private networks.     

Performance guarantee for edf under overload

Earliest deadline first (edf) is a widely used algorithm for online deadline scheduling. It has been known for long that edf is optimal for scheduling an underloaded, single-processor system; recent results on the extra-resource analysis of edf further revealed that edf when using moderately faster processors can achieve optimal performance in the underloaded, multi-processor setting. This paper initiates the extra-resource analysis of edf for overloaded systems, showing that edf supplemented with a simple form of admission control can provide a similar performance guarantee in both the single and multi-processor settings.     

Diffusion approximation for an overloaded X model via a stochastic averaging principle

In previous papers we developed a deterministic fluid approximation for an overloaded Markovian queueing system having two customer classes and two service pools, known in the call-center literature as the X model. The system uses the fixed-queue-ratio-with-thresholds (FQR-T) control, which we proposed as a way for one service system to help another in face of an unexpected overload. Under FQR-T, customers are served by their own service pool until a threshold is exceeded. Then, one-way sharing is activated with customers from one class allowed to be served in both pools. The control aims to keep the two queues at a pre-specified fixed ratio. We supported the fluid approximation by establishing a functional weak law of large numbers involving a stochastic averaging principle. In this paper we develop a refined diffusion approximation for the same model based on a many-server heavy-traffic functional central limit theorem.     

Two fluid approximations for multi-server queues with abandonments

Insight is provided into a previously developed M/M/s/r+M(n) approximation for the M/GI/s/r+GI queueing model by establishing fluid and diffusion limits for the approximating model. Fluid approximations for the two models are compared in the many-server efficiency-driven (overloaded) regime. The two fluid approximations do not coincide, but they are close.     

Markov-Modulated Brownian Motion with Temporary Change of Regime at Level Zero

We determine the stationary distribution of a one-sided Markov-Modulated Brownian Motion (MMBM) of which the behaviour is modified during the intervals between a visit to level zero and the next visit to a fixed positive level b. We use the semi-regenerative structure of the process, and we also use the fluid approximation for MMBMs introduced by Latouche and Nguyen in 2015. Finally, we show how the expressions can be simplified in some interesting special cases and we conclude by providing some numerical illustrations.     

Stationary analysis of the shortest queue problem

In this paper, we derive an approximation for throughput of TCP Compound connections under random losses. Throughput expressions for TCP Compound under a deterministic loss model exist in the literature. These are obtained assuming that the window sizes are continuous, i.e., a fluid behavior is assumed. We validate this model theoretically. We show that under the deterministic loss model, the TCP window evolution for TCP Compound is asymptotically periodic and is independent of the initial window size. We then consider the case when packets are lost randomly and independently of each other. We discuss Markov chain models to analyze performance of TCP in this scenario. We use insights from the deterministic loss model to get an appropriate scaling for the window size process and show that these scaled processes, indexed by p, the packet error rate, converge to a limit Markov chain process as p goes to 0. We show the existence and uniqueness of the stationary distribution for this limit process. Using the stationary distribution for the limit process, we obtain approximations for throughput, under random losses, for TCP Compound when packet error rates are small. We compare our results with ns2 simulations which show a good match and a better approximation than the fluid model at low p.     

Investigation of Boundary-Value Problem for Stationary System of Equations of Viscous Non-Isothermal Fluid

In the Stokes approximation at small Reynolds and Peclet numbers, we obtain a solution to the boundary-value problem of flow around of particles of spherical shape for stationary system of equations of a viscous non-isothermal fluid comprising a linearized by speed Navier–Stokes equation system and the equation of heat transfer given an exponential-power law of dependence of viscosity of fluid on temperature.     

Non-isothermal fluid flow through a thin pipe with cooling

The stationary flow of a Boussinesquian fluid with temperature-dependent viscosity through a thin straight pipe is considered. The fluid in the pipe is cooled by the exterior medium. The asymptotic approximation of the solution is built and rigorously justified by proving the error estimate in terms of domain thickness. The boundary layers for the temperature at the ends of the pipe are studied.     

Integral approximation of the characteristic function of a spherical cap by algebraic polynomials

A problem of optimal boundary control of thermal sources for a stationary model of natural thermal convection of a high-viscosity inhomogeneous incompressible fluid in the Boussinesq approximation is investigated. Conditions for the solvability of the problem, as well as necessary and sufficient optimality conditions, are specified. Optimality conditions and the corresponding adjoint problems defining the gradient of the quality functional are written for several special cases of the functional. Computational procedures for finding an optimal control based on gradient methods are described. The results of numerical experiments are given.     

Existence for the stationary MHD-equations coupled to heat transfer with nonlocal radiation effects

We consider the problem of influencing the motion of an electrically conducting fluid with an applied steady magnetic field. Since the flow is originating from buoyancy, heat transfer has to be included in the model. The stationary system of magnetohydrodynamics is considered, and an approximation of Boussinesq type is used to describe the buoyancy. The heat sources given by the dissipation of current and the viscous friction are not neglected in the fluid. The vessel containing the fluid is embedded in a larger domain, relevant for the global temperature- and magnetic field- distributions. Material inhomogeneities in this larger region lead to transmission relations for the electromagnetic fields and the heat flux on inner boundaries. In the presence of transparent materials, the radiative heat transfer is important and leads to a nonlocal and nonlinear jump relation for the heat flux. We prove the existence of weak solutions, under the assumption that the imposed velocity at the boundary of the fluid remains sufficiently small.     

Bounds on the tight-binding approximation for the Gross-Pitaevskii equation with a periodic potential

We justify the validity of the discrete nonlinear Schrödinger equation for the tight-binding approximation in the context of the Gross-Pitaevskii equation with a periodic potential. Both piecewise-constant and smooth potentials are considered in the semi-classical limit. While justification of stationary equations is developed in our previous work (Pelinovsky et al. (2008) [11]), this work deals with time-dependent space-decaying solutions on large but finite time intervals.     

Optimality conditions for regenerative inventory systems under batch demands

We consider a single-item, continuous-review, (s, S) inventory system, under complete backlogging and a constant procurement lead time. Demands occur in independent, identically distributed batches, separated by independent identically distributed intervals. The model also includes a class of periodic review systems as a special case. Of interest are the optimal control policies with respect to a stationary cost rate function, constructed to include ordering, holding and shortage costs. We study the structural properties of the cost rate function and report some new bounds and optimality conditions. An application of these to the computation and approximation of optimal policies is also discussed.     

Computing the Stationary Distribution of an SRBM in an Orthant with Applications to Queueing Networks

In [15], a BNAfm (Brownian network analyzer with finite element method) algorithm was developed for computing the stationary distribution of a semimartingale reflecting Brownian motion (SRBM) in a hypercube. In this companion paper, that BNAfm algorithm is extended to computing the stationary distribution of an SRBM in an orthant, which is achieved by constructing a converging sequence of SRBMs in hypercubes. The SRBM in the orthant serves as an approximation model of queueing networks with infinite buffers. We show that the constructed sequence of SRBMs in the hypercubes converges weakly to the SRBM in the orthant as the hypercubes approach the orthant. Under the conjecture that the set of the stationary distributions of the SRBMs in the hypercubes is relatively compact, we prove that the sequence of the stationary distributions of the SRBMs in the hypercubes converges weakly to the stationary distribution of the SRBM in the orthant. A three-machine job shop example is presented to illustrate the effectiveness of the SRBM approximation model and our BNAfm algorithm. The BNAfm algorithm is shown to produce good estimates for stationary probabilities of queueing networks.     

Numerical simulation of thermal problems coupled with magnetohydrodynamic effects in aluminium cell

A system of partial differential equations describing the thermal behavior of aluminium cell coupled with magnetohydrodynamic effects is numerically solved. The thermal model is considered as a two-phases Stefan problem which consists of a non-linear convection–diffusion heat equation with Joule effect as a source. The magnetohydrodynamic fields are governed by Navier–Stokes and by static Maxwell equations. A pseudo-evolutionary scheme (Chernoff) is used to obtain the stationary solution giving the temperature and the frozen layer profile for the simulation of the ledges in the cell. A numerical approximation using a finite element method is formulated to obtain the fluid velocity, electrical potential, magnetic induction and temperature. An iterative algorithm and 3-D numerical results are presented.     

On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers

This paper deals with a multi-class priority queueing system with customer transfers that occur only from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system is introduced, for which an explicit product-form solution is found for the stationary distribution of queue lengths. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds on the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.