# Please explain linear programming as seen for this load balancing problem

I have at hand a linear program related to load balancing. However I have no idea what this is and wikipedia gives me something too simplified/abstract to be useful.

I wonder if someone can explain the basic lingo used in the formulation of the linear program. The goal of the program is of course to introduce the maximum amount of load capable on the lightest loaded machine.

Let

• $p_i$ be load of processor $i$
• $L$ be our load to be distributed
• $x_i$ be the fraction of load $L$ distributed to processor $i$
• $\gamma$ be the minimum of final load after distribution of $L$

Then solve:

$$max_{x,\gamma} \gamma$$

subject to $\gamma \underline 1 \leq p + xL$, $\underline 1'x = 1, x \geq 0$, $\underline 1$ is the one vector

Some confusions:

• How do you physically characterize the load of a processor, is it equivalent to CPU utilization? i.e. what can I do to find out what the load of my processor is currently having

• How is the fraction of load $L$ to be distributed determined?

• If $\gamma$ is the minimum final load after L, then why do we maximize it? wouldn't that be equivalent to maximize the left over work to be done?

• So you have a linear program without knowing what linear programming is? Why not read up on that subject first? There's is plenty of literature around on that topic. – Raphael Aug 17 '15 at 9:52

## 1 Answer

How do you physically characterize the load of a processor, is it equivalent to CPU utilization?

The program is modelling load like this. Whether you feel it's a good way to model load, and whether you can think of any real version of load that works like this is a separate issue.

You are running a storage facility for water. The key "facts" about water are:

1. It's just water and all water is the same. If I ask you to store a litre of water for me and I come back for it a week later, I don't care if you give me back exactly the same molecules of water: I just want you to give me a litre of water. (Economists call a substance with this property "fungible".)

2. Water is infinitely subdivisible. If I give you a litre of water, you can split it into any number of smaller quantities, without restriction. (Atoms? Shmatoms!)

OK. In your water storage facility, you have $n$ tanks, each of which can hold an unbounded amount of water (you were sure you only needed one such tank, but the TankCorp salesman was very persuasive). At any particular time, the $i$th tank contains $p_i$ litres of water. A new customer has just arrived with $L$ litres and you need to decide if you can store that and, if so, what is the best way of doing that.

You'll put $x_i$ litres of water in each of your tanks. You can choose the value of each $x_i$ however you want but, if you accept the customer, you must store all of his water, which means you must have $\sum_i x_i = L$. Also, TankCorp tanks do occasionally burst so you want to fill the tanks as evenly as possible so that, if a tank does burst, you know it won't be a super-full one: you want the loads in the tanks to be balanced. This is achieved by making the emptiest tank as full as possible. Why? Because the total amount of water in all the tanks is fixed so, if one tank has less water in it, you can always make the quantities more equal by taking water from a very full tank and transfering it to the emptiest one.

Your job is to pick values for the $x_i$ to satisfy these constraints. Note that if, at the start of the day, each of your tanks is empty, then the solution is trivial: you just set $x_i = L/n$ for each $i$ and each tank contains the same amount of water.

OK, that's the model. You can use it to represent any kind of load that resembles the idealized water I described: it must be arbitrarily subdivisible (you can split it between your servers however you want) and fungible (your client don't care which server does any fraction of the work). Literally speaking, that's nothing at all, but we can get a good approximation if we replace "infinitely subdivisible" by "subdivisible a lot". For example, suppose you're running a web server cluster. You can't literally divide a burst of a thousand requests between the machines in your cluster in any fraction ("I'll do 4.7 requests on server 1, ...") you want but you can divide it into any number of thousandths, which is close enough.

i.e. what can I do to find out what the load of my processor is currently having?

I'm not sure what you mean. This isn't a system for measuring load, it's a system for assigning fractions of jobs to servers so that each server will have about the same load.

How is the fraction of load $L$ to be distributed determined?

By solving the program! (I.e., choosing values for the $x_i$ that satisfy the constraints.)

If $\gamma$ is the minimum final load after $L$, then why do we maximize it? Wouldn't that be equivalent to maximize the left over work to be done?

No, because the total work to be done is fixed. Maximizing the least-busy server means that there's less work for the busiest server to do, so you finish as soon as possible.