Appendix A. Lyapunov Analysis

This appendix provides an outline of the mathematical proof that shows why the least connections server load balancing (SLB) algorithm is inherently stable. This means that over a long period of time, the system will ensure that the load is evenly balanced. This analysis can be used to model and verify the stability of any network design, which may be of tremdous value if you are an advanced network architect.

Building on what was discussed in Chapter 3, we will extend the model of the single queue to that of the entire system and then show that the entire system is stable. The entire system consists of an aggregate ingress load of l, N server processes of varying service rates µ1, µ2, . . .µn, hence we get the following equation:

EQN 1: S = l + µ1 + µ2 +. . . µn

We will use this equation later. It states that the value S is the sum of the aggregate load and the sum of all the service rates. This means in one time slot:

• average sum of all incoming loads

• average sum of all server processing capacity

Since the incoming packets are modeled as Poisson arrivals, which is in continuous time, we will map the time domain to an index N, which increases whenever the state of the system changes. The state is defined as the queue occupancy. If a packet arrives, it will increase the size of one of the queues in the system. If a packet is serviced, then the size of one queue of the system will decrease.

Let Qs(t) = min(Q1(t), Q2(t). . . QN(t)). This Qs is the least occupied queue among all N queues.

Let Qb(t) = set {Q1(t), Q2(t). . . QN(t)} - {Qs(t)}, which is all the queues except for the least occupied.

Let Qa(t) = Qb(t) + Qs(t), which is all the queues.

We know that the next state of all queues in the set Qb(t) can change only due to a Web service, which is a reduction by one request. There can be no increase in this queue size because the SLB will not forward any new requests. Therefore, these queues cannot grow in the next time slot, so we get:

Qb(t+1) = Qb(t) - 1 with probability of µib/S

We can also figure out the next possible state of Qs(t), which can change due to a Web service, resulting in a reduction of queue size by 1 or an increase in queue size, due to the SLB forwarding a request to this queue. Hence we get the next state as follows:

Qs(t+1) = Qs(t) -1 with probability of µis/S

or Qs(t) +1 with a probability of lis/S

We can assign the Lyapunov Function to the sum of all the occupancies of all N queues. We will use t, representing a particular time slot:

Now if we look at one particular queue, Qi(t), keeping time discrete, the state of Qi(t) only changes due to events of arrivals and/or departures. We can see how this queue increases and decreases in size or queue occupancy.

For stability, we need to show:

EL = E[L(t+1) - L(t)) | L(t)] <= -e || Q || + k

This says that the expected value of the single step drift that is, the Lyapunov Function at time t+1 Lyapunov Function at time t, given the Lyapunov Function at time t must be a negative constant times the queue size plus some constant k. The value of EL becomes negative when the queue size times -e is larger than k. This is typical in almost all systems in that before the system reaches a steady state there is an initial unstable period, but after some time a steady state is reached. This is where we need to look at the system to determine the behavior of the system in steady state.

This is always negative as long as:

This means that since:

• All incoming traffic is being redirected by the SLB algorithm to the least occupied queue,

  

  
  

• All Web server capacity at time slot t is:

  

  
  

From this we conclude that as long as the incoming traffic is admissible or

The system is stable!

This proves that the SQF algorithm is guaranteed to drain all queues in such a way as to make sure the system is stable.

If we had a round-robin SLB algorithm instead, we would not get this mathematical result. In particular, there is no way we can enforce the following:

li < µi, resulting in Qi(t) overflowing, even though the overall average incoming traffic is less than the overall average server capacity that is, l < µ.

The SLB blindly forwards incoming traffic to servers, without considering the occupancy of Qi(t). The round-robin scheme can easily have some idle servers and still continue to forward traffic to an overloaded server, resulting in instability. In the SQF algorithm, we know that only the shortest queue is forwarded traffic and that the other queues can only drain. As long as Qis does not overflow, the entire system is stable. We know that l < µ hence we know that Qis(t) is stable.