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

Excerpt

## 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. 1:

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

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 variable4.

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 load5 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

[...]

1 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.

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

3 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.

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

5 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.

Excerpt out of 140 pages

Details

Title
Load Balancing on Multimedia Client-Server Communication Networks: Computer Experiments
Course
A
Author
Year
2001
Pages
140
Catalog Number
V204152
ISBN (eBook)
9783656309680
File size
800 KB
Language
English
Notes
Describes an algorithm for server load balancing and its implementation. Show cases the algorithm output in tabular form. Includes C++ source code.
Keywords
Computer Science, Server Load Balancing, Theory of NP Completeness, Linear
Quote paper
Roger Doss (Author), 2001, Load Balancing on Multimedia Client-Server Communication Networks: Computer Experiments, Munich, GRIN Verlag, https://www.grin.com/document/204152