Periodic load balancing

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. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotically optimal cubature weight formulas

Krasnoyarsk. Translated from Sibirskii Matematicheskii Zhurnal, Vol. 30, No. 2, pp. 151–160, March–April, 1989.     

Two dimensional load balancing

We consider a bi-criteria parallel machine scheduling problem in which the first objective is the minimization of the makespan of the schedule and the second objective is the minimization of the maximum machine cost. Since the problem is strongly NP-hard, we propose a fast heuristic and derive its worst-case performance bound.     

Equilibria in load balancing games

A Nash equilibrium （NE） in a multi-agent game is a strategy profile that is resilient to unilateral deviations. A strong Nash equilibrium （SE） is one that is stable against coordinated deviations of any coalition. We show that, in the load balancing games, NEs approximate SEs in the sense that the benefit of each member of any coalition from coordinated deviations is well limited. Furthermore, we show that an easily recognizable special subset of NEs exhibit even better approximation of SEs.     

Asymptotically optimal parallel resource assignment with interference

Motivated by scheduling in cellular wireless networks and resource allocation in computer systems, we study a service facility with two classes of users having heterogeneous service requirement distributions. The aggregate service capacity is assumed to be largest when both classes are served in parallel, but giving preferential treatment to one of the classes may be advantageous when aiming at minimization of the number of users, or when classes have different economic values, for example.     

Asymptotically optimal estimators for moments of change

We consider the problem of finding asymptotically optimal estimators for many moments of change in the case of incomplete information on distributions. We prove that if the maximum-likelihood estimator is asymptotically optimal, then, under certain conditions, it preserves this property after the replacement of actual values by density estimators. We solve the problem for the case of one moment of change and generalize the results obtained to the case of several moments of change. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 3, pp. 406–416, March, 2006.     

Asymptotically optimal empirical bayes procedures for selecting good

Let ∏₁,…,∏_k denote k independent populations, where a random observation from population ∏ _i has a uniform distribution over the interval (0,θ _i ) and θ _i is a realization of a random variable having an unknown prior distribution G _i . Population ∏ _i is said to be a good population if θ _i ≥θ₀, where θ₀ is a given, positive number. This paper provides a sequence of empirical Bayes procedures for selecting the good populationsamong ∏₁,…,∏ _k . It is shown that these procedures are asymptotically optimal and that the order of associated convergence rates is O(n^-r/4) for some r, 0<r<2, where n is the number of accumulated past observations

at hand     

Constructing open-loop and closed-loop solutions of linear-quadratic optimal control problems

A linear-quadratic optimal control problem subject to geometric constraints on the controls is studied. Techniques for finding the optimal open-loop control and constructing a closed-loop control are described. The problem solution can include special intervals and sections with chattering modes. The proposed techniques make it possible to find special intervals and construct realizable approximations of unrealizable chattering modes to any degree of accuracy.     

Asymptotically optimal strategies in repeated games with incomplete information

It is known that for repeated zero-sum games with incomplete information the limit of the values of theN-stage game exists asN tends to infinity. In this paper strategies are constructed that guarantee in theN-stage game the limit of values up to an error term \(\frac{K}{{\sqrt N }}.\)      

Asymptotically optimal dividend policy for regime-switching compound Poisson models

This work develops asymptotically optimal dividend policies to maximize the expected present value of dividends until ruin.Compound Poisson processes with regime switching are used to model the surplus and the switching（a continuous-time controlled Markov chain） represents random environment and other economic conditions.Assuming the switching to be fast varying together with suitable conditions,it is shown that the system has a limit that is an average with respect to the invariant measure of a related Markov chain.Under simple conditions,the optimal policy of the limit dividend strategy is a threshold policy.Using the optimal policy of the limit system as a guide,feedback control for the original surplus is then developed.It is demonstrated that the constructed dividend policy is asymptotically optimal.     

Asymptotically optimal control of parallel tandem queues with loss

We consider admission and routing controls for a system of N parallel tandem queues with finite buffers as N becomes large, with the aim of minimizing costs due to loss. We obtain the fluid limit as N→∞, and solve a related optimization problem. Asymptotically, for N large, the optimal cost and associated control take one of two forms, depending on the ratio between the cost of blocking an arrival at entry and discarding after service at the first queue.     

Asymptotically optimal Bayesian sequential change detection and identification rules

We study the joint problem of sequential change detection and multiple hypothesis testing. Suppose that the common distribution of a sequence of i.i.d. random variables changes suddenly at some unobservable time to one of finitely many distinct alternatives, and one needs to both detect and identify the change at the earliest possible time. We propose computationally efficient sequential decision rules that are asymptotically either Bayes-optimal or optimal in a Bayesian fixed-error-probability formulation, as the unit detection delay cost or the misdiagnosis and false alarm probabilities go to zero, respectively. Numerical examples are provided to verify the asymptotic optimality and the speed of convergence.     

Existence of optimal open-loop strategies for a class of differential games

In this paper, the class of differential games with linear system equations and a quadratic performance index is investigated for saddlepoint solutions when one or both of the players use open-loop control. For each formulation of the game, a necessary and sufficient condition is obtained for the existence of an optimal strategy pair that generates a regular optimal path. For those cases where a solution exists, the unique saddle-point solution is presented. Also, relationships are established between the time intervals of existence of solutions for the various formulations of the game.This research was supported by the National Science Foundation, Grant No. GK-3341.     

Selfish load balancing for jobs with favorite machines

This paper studies the load balancing game for the favorite machine model, where each job has a certain set of favorite machines with the shortest processing time for the job. We obtain tight bounds on the Strong Price of Anarchy (strong PoA) for the general favorite machine model and a special case of the model. Our results generalize the well-known bounds on the strong PoA for the unrelated machine and identical machine models.     

Asymptotic independence of queues under randomized load balancing

Randomized load balancing greatly improves the sharing of resources while being simple to implement. In one such model, jobs arrive according to a rate-??N Poisson process, with ??<1, in a system of N rate-1 exponential server queues. In Vvedenskaya et al. (Probl. Inf. Transm. 32:15?C29, 1996), it was shown that when each arriving job is assigned to the shortest of D, D??2, randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as N????. This is a substantial improvement over the case D=1, where queue sizes decay exponentially. The reasoning in Vvedenskaya et al. (Probl. Inf. Transm. 32:15?C29, 1996) does not easily generalize to jobs with nonexponential service time distributions. A?modularized program for treating randomized load balancing problems with general service time distributions was introduced in Bramson et al. (Proc. ACM SIGMETRICS, pp.?275?C286, 2010). The program relies on an ansatz that asserts that, for a randomized load balancing scheme in equilibrium, any fixed number of queues become independent of one another as N????. This allows computation of queue size distributions and other performance measures of interest. In this article, we demonstrate the ansatz in several settings. We consider the least loaded balancing problem, where an arriving job is assigned to the queue with the smallest workload. We also consider the more difficult problem, where an arriving job is assigned to the queue with the fewest jobs, and demonstrate the ansatz when the service discipline is FIFO and the service time distribution has a decreasing hazard rate. Last, we show the ansatz always holds for a sufficiently small arrival rate, as long as the service distribution has 2 moments.     

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.     

A simple load balancing problem with decentralized information

The following load balancing problem is investigated in discrete time: A service system consists of two service stations and two controllers, one in front of each station. The service stations provide the same service with identical service time distributions and identical waiting costs. Customers requiring service arrive at a controller's site and are routed to one of the two stations by the controller. The processes describing the two arrival streams are identical. Each controller has perfect knowledge of the workload in its own station and receives information about the other station's workload with one unit of delay. The controllers' routing strategies that minimize the customers' total flowtime are determined for a certain range of the parameters that describe the arrival process and the service distribution. Specifically, we prove that optimal routing strategies are characterized by thresholds that are either precisely specified or take one of two possible values.