Web server load balancing: A queueing analysis

Over the last few years, the Web-based services, more specifically different types of E-Commerce applications, have become quite popular, resulting in exponential growth in the Web traffic. In many situations, this has led to unacceptable response times and unavailability of services, thereby driving away customers. Many companies are trying to address this problem using multiple Web servers with a front-end load balancer. Load balancing has been found to provide an effective and scalable way of managing the ever-increasing Web traffic. However, there has been little attempt to analyze the performance characteristics of a system that uses a load balancer. This paper presents a queuing model for analyzing load balancing with two Web servers. We first analyze the centralized load balancing model, derive the average response time and the rejection rate, and compare three different routing policies at the load balancer. We then extend our analysis to the distributed load balancing and find the optimal routing policy that minimizes the average response time.     

Zero-sum Markov games and worst-case optimal control of queueing systems

Zero-sum stochastic games model situations where two persons, called players, control some dynamic system, and both have opposite objectives. One player wishes typically to minimize a cost which has to be paid to the other player. Such a game may also be used to model problems with a single controller who has only partial information on the system: the dynamic of the system may depend on some parameter that is unknown to the controller, and may vary in time in an unpredictable way. A worst-case criterion may be considered, where the unknown parameter is assumed to be chosen by nature (called player 1), and the objective of the controller (player 2) is then to design a policy that guarantees the best performance under worst-case behaviour of nature. The purpose of this paper is to present a survey of stochastic games in queues, where both tools and applications are considered. The first part is devoted to the tools. We present some existing tools for solving finite horizon and infinite horizon discounted Markov games with unbounded cost, and develop new ones that are typically applicable in queueing problems. We then present some new tools and theory of expected average cost stochastic games with unbounded cost. In the second part of the paper we present a survey on existing results on worst-case control of queues, and illustrate the structural properties of best policies of the controller, worst-case policies of nature, and of the value function. Using the theory developed in the first part of the paper, we extend some of the above results, which were known to hold for finite horizon costs or for the discounted cost, to the expected average cost.     

Asymptotically optimal open-loop load balancing

In many distributed computing systems, stochastically arriving jobs need to be assigned to servers with the objective of minimizing waiting times. Many existing dispatching algorithms are basically included in the SQ(d) framework: Upon arrival of a job, \(d\ge 2\) servers are contacted uniformly at random to retrieve their state and then the job is routed to a server in the best observed state. One practical issue in this type of algorithm is that server states may not be observable, depending on the underlying architecture. In this paper, we investigate the assignment problem in the open-loop setting where no feedback information can flow dynamically from the queues back to the controller, i.e., the queues are unobservable. This is an intractable problem, and unless particular cases are considered, the structure of an optimal policy is not known. Under mild assumptions and in a heavy-traffic many-server limiting regime, our main result proves the optimality of a subset of deterministic and periodic policies within a wide set of (open-loop) policies that can be randomized or deterministic and can be dependent on the arrival process at the controller. The limiting value of the scaled stationary mean waiting time achieved by any policy in our subset provides a simple approximation for the optimal system performance.     

Stability analysis of queueing systems

This paper contains a survey of some results on the stability of queueing systems obtained by the authors by means of the method of trial functions (developed from Lyapunov's direct method). In addition, the paper contains a series of new results on the stability of regenerative processes. All the qualitative statements are accompanied by the construction of quantitative estimates.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 87, pp. 41–61, 1979.     

Stability analysis and optimal control of stochastic singular systems

In this paper, problems of stability and optimal control for a class of stochastic singular systems are studied. Firstly, under some appropriate assumptions, some new results about mean-square admissibility are developed and the corresponding LMI sufficient condition is given. Secondly, finite-time horizon and infinite-time horizon linear quadratic (LQ) control problems for the stochastic singular system are investigated, in which the coefficients are allowed to be random in control input and quadratic criterion. Some results involving new stochastic generalized Riccati equation are discussed as well. Finally, the proposed LQ control model for stochastic singular systems provides an appropriate and effective framework to study the portfolio selection problem in light of the recent development on general stochastic LQ problems.     

Stability criteria for controlled queueing systems

We give an almost complete classification of ergodicity and transience conditions for a general multi-queue system with the following features: arrivals form Poisson streams and there are various routing schemes for allocating arrivals to queues; the servers can be configured in a variety of ways; completed jobs can feed back into the system; the exponential service times and feedback probabilities depend upon the configuration of the servers (this model includes some types of multi-class queueing system); switching between service regimes is instantaneous. Several different levels of control of the service regimes are considered. Our results for the N-queue system require randomisation of service configurations but we have studied the two queue system in situations where there is less control. We use the semi-martingale methods described in Fayolle, Malyshev and Menshikov [3] and our results generalise Kurkova [8] and complement Foley and McDonald [4] and [5]. AMS 2000 subject classification: Primary: 90B22; Secondary: 60J10 90B15     

Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies

This paper describes a family of discrete-review policies for scheduling open multiclass queueing networks. Each of the policies in the family is derived from what we call a dynamic reward function: such a function associates with each queue length vector q and each job class k a positive value r _k (q), which is treated as a reward rate for time devoted to processing class k jobs. Assuming that each station has a traffic intensity parameter less than one, all policies in the family considered are shown to be stable. In such a policy, system status is reviewed at discrete points in time, and at each such point the controller formulates a processing plan for the next review period, based on the queue length vector observed. Stability is proved by combining elementary large deviations theory with an analysis of an associated fluid control problem. These results are extended to systems with class dependent setup times as well as systems with alternate routing and admission control capabilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

Post-filtering of IC2-factors for load balancing in parallel preconditioning

A modification is proposed for the second order incomplete Cholesky decomposition (IC2). It makes possible to design a preconditioning procedure for the conjugate gradient method (CGM) with a controllable fill-in in the preconditioner. The modified algorithm is used to develop a load-balancing parallel preconditioning for CGM as applied to linear systems with symmetric positive definite matrices. Numerical results obtained using a multiprocessor computer system are presented.     

Dynamic scheduling for minimum delay in tandem and parallel constrained queueing models

The optimal scheduling problem in two queueing models arising in multihop radio networks with scheduled link activation is investigated. A tandem radio network is considered. Each node receives exogenous arriving packets which are stored in its unlimited capacity buffer. Links adjacent to the same node cannot transmit simultaneously because of radio interference constraints. The problem of link activation scheduling for minimum delay is studied for two different traffic types. In the first type all packets have a common destination that is one end-node of the tandem. In this case the system is modeled by a tandem queueing network with dependent servers. The server scheduling policy that minimizes the delay is obtained. In the second type of traffic, the destination of each packet is an immediate neighbor of the node at which the packet enters the network. In this case the system corresponds to a set of parallel queues with dependent servers. It is shown that the optimal policy activates the servers so that the maximum number of packets are served at each slot.     

Containment of socially optimal policies in multiple-facility Markovian queueing systems

We consider a Markovian queueing system with N heterogeneous service facilities, each of which has multiple servers available, linear holding costs, a fixed value of service and a first-come-first-serve queue discipline. Customers arriving in the system can be either rejected or sent to one of the N facilities. Two different types of control policies are considered, which we refer to as ‘selfishly optimal’ and ‘socially optimal’. We prove the equivalence of two different Markov Decision Process formulations, and then show that classical M/M/1 queue results from the early literature on behavioural queueing theory can be generalized to multiple dimensions in an elegant way. In particular, the state space of the continuous-time Markov process induced by a socially optimal policy is contained within that of the selfishly optimal policy. We also show that this result holds when customers are divided into an arbitrary number of heterogeneous classes, provided that the service rates remain non-discriminatory.     

The achievable region method in the optimal control of queueing systems; formulations,bounds and policies

We survey a new approach that the author and his co-workers have developed to formulate stochastic control problems (predominantly queueing systems) asmathematical programming problems. The central idea is to characterize the region of achievable performance in a stochastic control problem, i.e., find linear or nonlinear constraints on the performance vectors that all policies satisfy. We present linear and nonlinear relaxations of the performance space for the following problems: Indexable systems (multiclass single station queues and multiarmed bandit problems), restless bandit problems, polling systems, multiclass queueing and loss networks. These relaxations lead to bounds on the performance of an optimal policy. Using information from the relaxations we construct heuristic nearly optimal policies. The theme in the paper is the thesis that better formulations lead to deeper understanding and better solution methods. Overall the proposed approach for stochastic control problems parallels efforts of the mathematical programming community in the last twenty years to develop sharper formulations (polyhedral combinatorics and more recently nonlinear relaxations) and leads to new insights ranging from a complete characterization and new algorithms for indexable systems to tight lower bounds and nearly optimal algorithms for restless bandit problems, polling systems, multiclass queueing and loss networks.     

On the optimal control of a single-server queueing system: Reply

This comment replies to a criticism due to Klein and Gruver (Ref. 1) of our earlier paper (Ref. 2) on the application of control theory to a queueing system. The criticism concerns the state-space diagram and the table which we inadvertently gave for the terminal-reward problem, albeit incorrectly labeled, rather than for the free-endpoint problem considered in our paper. We show that the solution given by Klein and Gruver is itself incorrect and nonoptimal.     

Stability and irreducibility of queueing systems with finite capacity

In this paper, we obtain a readily verifiable condition of stability for GI/G/1 queueing systems with finite capacity. A necessary and sufficient condition of irreducibility of the queueing size process is involved. Under this assumption, we derive general conditions of recurrence (positive recurrence) for the general process describing the state of the system. The conditions of irreducibility and recurrence are based on restrictions over the supports of the interarrival and the service distributions, which are easy to check in practice. The positive recurrence is also connected to the first moments of both distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the optimal control of a single-server queueing system: Comment

In a recent paper by Scott and Jefferson, the optimal control of the service rate for a single-server queue with limited waiting space is treated by the maximum principle. We show that their control policies are necessarily suboptimal. Characterizations for optimal control are derived and used to obtain corresponding optimal trajectories in both nonsingular and singular regions.     

On the optimal control of a single-server queueing system: Further remarks

This comment is in response to a reply by Scott and Jefferson (Ref. 3) concerning the application of control theory to a queueing problem.     

Stability and sensitivity of solutions to optimal control problems for systems with control appearing linearly

We consider a family of optimal control problems for systems described by nonlinear ordinary differential equations with control appearing linearly. The cost functionals and the control constraints are convex. All data depend on a vector parameter.Using the concept of the second-order sufficient optimality conditions it is shown that the solutions of the problems, as well as the associated Lagrange multipliers, are locally Lipschitz continuous and directionally differentiable functions of the parameter.     

Flow control in capacity-constrained queueing systems with non-stationary arrivals

In this paper, we present a flow control policy to address the problem of service capacity constraints in queueing systems that face non-stationary customer arrival rates. The studied system concerns commercial trucks arriving at international border checkpoints for processing. Based on an extensive range of numerical examples, we quantify how the flow control policy of bringing arrival rates more in line with available capacity affects customer-oriented metrics and measures of efficiency in service capacity resources. We also quantify the expectations that the policy would place on arriving customers. How these quantitative outcomes are influenced by contextual parameters such as the pattern of customer arrivals and the tightness of capacity constraints is also clarified.     

On the optimal control problem of a single-server queueing system

For a single-server queueing system (with a finite waiting room) with phase type arrivals and exponential service times, an optimal control for the service rate is derived. This generalizes the result of Scott and Jefferson for theM/M/1/1 queueing model.     

Delay systems and optimal control

0. IntroductionIt is well known that evolution systems are an important class of distributed parametersystems and the optimal control of infinite dimensional systems is a remarkable subjectin control theory. Some authors including us investigated the existence of solutions orperiodic solutions (see [l--4] or [5,6] ). To the knowledge of the authors, optimal controls fordistributed parameter delay systems have not been extensively studied. Li and Yao obtaina maximum principle (see [7]). Here w…