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-wait load balancing with sparse messaging

A key challenge in designing load balancing strategies is to achieve low delay in large-scale systems while only using minimal communication overhead. Motivated by these issues, we introduce a novel scheme in which the dispatcher becomes aware of idle servers without any explicit communication from either side, using absence of messages at predefined time instants. The proposed scheme achieves provably vanishing queueing delays while using strictly less than one message per job on average.     

On-line scheduling to minimize average completion time revisited

We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.     

Throughput and delay optimality of power-of-d choices in inhomogeneous load balancing systems

It is well-known that the power-of-d choices routing algorithm maximizes throughput and is heavy-traffic optimal in load balancing systems with homogeneous servers. However, if the servers are heterogeneous, throughput optimality does not hold in general. We find necessary and sufficient conditions for throughput optimality of power-of-d choices when the servers are heterogeneous, and we prove that almost the same conditions are sufficient to show heavy-traffic optimality. Additionally, we generalize the sufficient condition for throughput optimality to a larger class of routing policies.     

A case study of an adaptive load balancing algorithm

In this paper we present an effective load balancing algorithm for a multi-processor architecture designed for the real time switching of telephone calls. By modifying an algorithm developed for an abstract queueing model, which is of independent interest by itself, we propose a hybrid load balancing algorithm and study its performance in a simulation test-bed. This case study demonstrates how simple abstractions and theoretically intractable but intuitively appealing ideas can be combined to effectively solve a real problem.     

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.     

Insensitive versus efficient dynamic load balancing in networks without blocking

So-called Whittle networks have recently been shown to give tight approximations for the performance of non-locally balanced networks with blocking, including practical routing policies such as joining the shortest queue. In the present paper, we turn the attention to networks without blocking. To this end, we consider a set of “insensitive” dynamic load balancing schemes preserving the structure of Whittle networks in the case of infinite buffers and examine their efficiency. Using Hausdorff’s theorem, we prove that the optimal insensitive schemes are static in this case, i.e., routing decisions do not depend on the current state of the queues. On the other hand, simulations show that the performance of static policies is generally much worse than that of “non balanced” sensitive dynamic policies. This demonstrates that strict insensitivity and efficiency may be incompatible objectives for networks with dynamic load balancing in case of infinite buffers. AMS Subject Classifications 60K25 · 68M20     

广义线性多乘积问题的完全多项式时间近似算法

本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.     

Optimal bundle pricing with monotonicity constraint

We consider the problem of pricing (digital) items in order to maximize the revenue obtainable from a set of bidders. We suggest a natural monotonicity constraint on bundle prices, show that the problem remains NP-hard, and we derive a PTAS. We also briefly discuss the highway pricing problem.     

Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem

The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a (⌈D_s/2⌉+1)/(⌊log₂(D_s+1)⌋+1)-approximation algorithm for MVRST where D_s is the minimum diameter of spanning trees of G.     

The complexity of optimizing over a simplex,hypercube or sphere: a short survey

We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems arise naturally from diverse applications. We review known approximation results as well as negative (inapproximability) results from the recent literature.      

Most probable explanations in Bayesian networks: Complexity and tractability

One of the key computational problems in Bayesian networks is computing the maximal posterior probability of a set of variables in the network, given an observation of the values of another set of variables. In its most simple form, this problem is known as the MPE-problem. In this paper, we give an overview of the computational complexity of many problem variants, including enumeration variants, parameterized problems, and approximation strategies to the MPE-problem with and without additional (neither observed nor explained) variables. Many of these complexity results appear elsewhere in the literature; other results have not been published yet. The paper aims to provide a fairly exhaustive overview of both the known and new results.     

On-line scheduling of unit time jobs with rejection: minimizing the total completion time

We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs.We give an on-line algorithm for this problem with competitive ratio . Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.     

Sell or Hold: A simple two-stage stochastic combinatorial optimization problem

The sell or hold problem (SHP) is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. We show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SHP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2,k/n}-approximation algorithm is presented for the scenario-based SHP.     

Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies

The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function such that |Λ(u)−Λ(v)|2, when u,v are neighbors in G, and |Λ(u)−Λ(v)|1 when the distance of u,v in G is two. The discrete number of frequencies used is called order and the range of frequencies used, span. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span (min span RCP) or the order (min order RCP).In this paper, we deal with an interesting, yet not examined until now, variation of the radiocoloring problem: that of satisfying frequency assignment requests which exhibit some periodic behavior. In this case, the interference graph (modelling interference between transmitters) is some (infinite) periodic graph. Infinite periodic graphs usually model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they can model very large networks produced by the repetition of a small graph.A periodic graph G is defined by an infinite two-way sequence of repetitions of the same finite graph G_i(V_i,E_i). The edge set of G is derived by connecting the vertices of each iteration G_i to some of the vertices of the next iteration G_i+1, the same for all G_i. We focus on planar periodic graphs, because in many cases real networks are planar and also because of their independent mathematical interest.We give two basic results:

• We prove that the min span RCP is PSPACE-complete for periodic planar graphs.

• We provide an O(n(Δ(G_i)+σ)) time algorithm (where|V_i|=n, Δ(G_i) is the maximum degree of the graph G_i and σ is the number of edges connecting each G_i to G_i+1), which obtains a radiocoloring of a periodic planar graph G that approximates the minimum span within a ratio which tends to as Δ(G_i)+σ tends to infinity.

We remark that, any approximation algorithm for the min span RCP of a finite planar graph G, that achieves a span of at most αΔ(G)+constant, for any α and where Δ(G) is the maximum degree of G, can be used as a subroutine in our algorithm to produce an approximation for min span RCP of asymptotic ratio α for periodic planar graphs.

Heuristics and lower bounds for the simple assembly line balancing problem type 1: Overview,computational tests and improvements

Assigning tasks to work stations is an essential problem which needs to be addressed in an assembly line design. The most basic model is called simple assembly line balancing problem type 1 (SALBP-1). We provide a survey on 12 heuristics and 9 lower bounds for this model and test them on a traditional and a lately-published benchmark dataset. The present paper focuses on algorithms published before 2011.