Load Balancing on Multimedia Client-Server Communication Networks: Computer Experiments

Contents

1 Introduction
1.1 Problem Statement
1.2 Objectives

2 Results of Experiments
2.1 Experiments with Three Servers and Five Tasks
2.1.1 First Data Set
2.1.2 Second Data Set
2.1.3 Third Data Set
2.2 Experiments with Three Servers and Six Tasks
2.2.1 First Data Set
2.2.2 Second Data Set
2.2.3 Third Data Set
2.3 Experiments with Four Servers and Five Tasks
2.3.1 First Data Set
2.3.2 Second Data Set
2.3.3 Third Data Set
2.4 Experiments with Four Servers and Six Tasks
2.4.1 First Data Set
2.4.2 Second Data Set
2.4.3 Third Data Set
2.5 Averages
2.5.1 Average Iterations for Load Redistributions
2.5.2 Average CPU Time Required for Load Balancing
2.6 Selected Problems with Five Servers and Seven Tasks

3 Analysis of Results

4 Description of the Implementation

A Load Balancing Algorithm Source Code

B Computing Averages Source Code

LIST OF TABLES

illustration not visible in this excerpt

List of Tables

illustration not visible in this excerpt

LIST OF TABLES

illustration not visible in this excerpt

1 Introduction

illustration not visible in this excerpt

1 Introduction

1.1 Problem Statement

To design and implement an algorithm which, given the inputs of work cost, backlogs, and tasks for multiple servers, produces an output of work distribu- tons (loads) for all servers and tasks in the system such that the timespans are minimal and, if possible, balanced. That is, the algorithm finds the optimal distribution for M tasks and N servers.

The project focuses on an algorithm for three server load balancing, and then attempts to generalize the algorithm to four and five servers. The system being considered consists of multiple servers represented as rows of a matrix, and multiple tasks, represented as columns of a matrix. Backlogs indicate the amount of work already being handled by a given server. Time spans indicate the run time associated with running several tasks on a server. Tasks can be of any type of work; however, the algorithm is conceptually focused on multi- media tasks. The data initially has been provided as integers. The system is mathematically modeled as a system of linear inequalities, therefore it is a member of the “Linear Programming” class of problems[1].

1.2 Objectives

The objective is to study and subsequently implement an algorithm capable of balancing multiple multimedia tasks on multiple servers. In order for the load to be correctly distributed, the final timespans for all servers in the system must be minimal. Further, it is desireable that the time spans be equal for all servers, if possible. ¹:

This problem bears similarity to “The Classical Transportation Problem”, from this, one knows that the “basic solution” requires no more than m+n−1 variables.

illustration not visible in this excerpt

The algorithm must distribute the loads in such a way, that the minimal timespan is achieved with all servers being considered. The first major phase involves the algorithm to balance for two servers. Based on the lecture, the algorithm proceeds by sorting the servers in increasing order based on their respective backlogs. Following this, the costs associcated with running a task on the first two servers are sorted in increasing order based on a ratio of W2j . In both sorting cases, all information in the rows is perserved and all information in the columns is preserved. After the sorting is achieved, the algorithm proceeds to distribute the loads by assigning them starting with the first server’s left most column and the second server’s right most columns, and proceeding from left to right for the first server, and right to left for the second server. This allows the least-cost distribution. In order to balance the two servers, a variable is introduced in one of the columns and a value is obtained via an equation of the form[5]:

illustration not visible in this excerpt

This is the “Knapsack” approach, which leaves the system in the following state:

illustration not visible in this excerpt

The second major phase that the algorithm takes is to consider the third server, and attempt to redistribute the loads from the prior assignments to the third server. This step, can be generalized to N servers, with each server being considered iteratively. That is, after the algorithm balances the N’th server, it may consider the N+1’th server, and so on. Loads are first considered on the N’th server for which costs are minimal. This involves sorting, in increasing order, the costs associated with the N’th server running the J’th task. The least cost task to run on the N’th server will be selected for introduction of a new load. When the load is introduced, the algorithm must find a “cycle” for which to increase and decrease approperiately, so that the servers can be balanced. By introducing a new load variable, the algorithm adds a positive load in a column on the N’th server. In this column, there must be a load on the previously balanced servers for which to decrease. Decreasing implies the algorithm must find a load in the same row to increase. This variable must have an associated variable in the same column to decrease.² If there is no such pair of variables, then the algorithm introduces an additional load on the new server, and considers the new load and an associated existing load on the previos servers.³ The algorithm does not introduce new loads where there is more than one load already in the column for simplicity. Once the new load and variables have been introduced, the system can be modeled using a set of linear inequalities of the form[5]:

D3 + N ≤ T1 − W1k (N ) + W1K (X )

D3 + N ≤ T2 − W2K (X ).

That is, the N’th server should have a timespan less than or equal to the existing 1 to N-1 servers previously balanced. The algorithm does not proceed to consider the next server if its timespan is already greator than the balanced servers.

There are several ways to solve the system of equations to produce the

values of for the new loads. The approach that this author chose was to set the equations equal to each other, and then to “combine like-terms” thereby producing a constants vector and a matrix of coefficients for each variable. The system is subsequently solved for each variable⁴.

The system; however, is correctly modeled via an inequality, not an equal- ity. Therefore, simply computing values for the variables introduced does not alone solve the system. The algorithm needs to consider the constraints placed on the variables in the system so that the property of “non-negativity” is enforced. This implementation uses a constraints vector for which the val- ues of solutions cannot be exceeded. If a constraint is violated, the newly introduced load is assigned the entire load⁵ and the remaining servers are re-balanced so as to maintain equilibrium at all stages. Failing to rebalance the servers produces errant results[5].

2 Results of Experiments

Table 1: Problem 85

illustration not visible in this excerpt

illustration not visible in this excerpt

2.1 Experiments with Three Servers and Five Tasks

2.1.1 First Data Set

Table 2: Solving the Generated Problem

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 3: Increasing all jobs b(j):=b(j)+1

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 4: Increasing all w(j,3):=w(j,3)+1.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 5: Increasing all jobs b(j):=2b(j).

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 6: Increasing all w(j,2):=w(j,2)+2.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 7: Increasing all delays d(k):=2d(k).

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 8: Increasing all w(2,k):=w(2,k)+3.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

2.1.2 Second Data Set

Table 9: Solving the Generated Problem.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 10: Increasing all jobs b(j):=b(j)+1.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 11: Increasing all w(j,3):=w(j,3)+1.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 12: Increasing all jobs b(j):=2b(j).

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 13: Increasing all w(j,2):=w(j,2)+2.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 14: Increasing all delays d(k):=2d(k).

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 15: Increasing all w(2,k):=w(2,k)+3.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

2.1.3 Third Data Set

Table 16: Solving the Generated Problem.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 17: Increasing all jobs b(j):=b(j)+1.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 18: Increasing all w(j,3):=w(j,3)+1.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 19: Increasing all jobs b(j):=2b(j).

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 20: Increasing all w(j,2):=w(j,2)+2.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 21: Increasing all delays d(k):=2d(k).

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

Table 22: Increasing all w(2,k):=w(2,k)+3.

illustration not visible in this excerpt

illustration not visible in this excerpt

illustration not visible in this excerpt

[...]

---

¹ The information presented here was derived in part from the class Lecture. The author of this document is presenting it here for completeness. It is not intended that the reader view this as the author’s work, but rather as reference material, which originated from the class lecture. It is therefore approperiately cited as such.

² This is always possible initially due to the state of the system after the two initial servers have been balanced.

³ The load that should already exist must be in a row other than that where the algorithm performed a decrement. This allows the previously balanced servers to be decre- mented simoultaneously.

⁴ The technique used to solve the systems of linear equations was Gaussian Elimination, though this is not the only way.

⁵ This is a pecularity of my implementation. One reason why the algorithm could not solve the system with a positive load is because the newly introduced server is drastically less buisy than the others already balanced. For this, it is safe to introduce the entire load to this server.