To design and implement an algorithm which, given the inputs of work cost, backlogs, and tasks for multiple servers, produces an output of work distributions (loads) for all servers and tasks in the system such that the time spans 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 multimedia 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.
Table of 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
Objectives & Themes
The primary goal of this project is to design and implement an algorithm that optimizes the distribution of multimedia tasks across multiple servers. The research focuses on finding an optimal load distribution where timespans for all servers are kept minimal and balanced, effectively modeling the system as a linear programming problem.
- Multimedia client-server communication networks
- Load balancing optimization via linear programming
- Task and server workload redistribution
- Generalization of balancing algorithms from three to five servers
- Algorithmic implementation and performance analysis
Auszug aus dem Buch
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.
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 W1j / 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.
Summary of Chapters
1 Introduction: Defines the problem statement and objectives, framing load balancing as a linear programming task.
2 Results of Experiments: Provides extensive experimental data and tables comparing load distributions across different server and task configurations.
3 Analysis of Results: Discusses the algorithmic observations, specifically how different input variations impact total finishing times and system balance.
4 Description of the Implementation: Explains the technical data structures and functions developed to execute the load balancing algorithm.
A Load Balancing Algorithm Source Code: Presents the core C++ implementation of the algorithm used for the computer experiments.
B Computing Averages Source Code: Details the utility program used to calculate the performance metrics for iterations and CPU time.
Keywords
Load Balancing, Multimedia Networks, Client-Server, Linear Programming, Task Redistribution, Timespan Optimization, Gaussian Elimination, Backlog, Workload, Algorithm, C++, Computer Experiments, System Optimization, Mathematical Modeling, Server Efficiency
Frequently Asked Questions
What is the core focus of this research?
The research focuses on designing and implementing an algorithm for multimedia client-server communication networks to achieve an optimal and balanced distribution of tasks across multiple servers.
What are the primary objectives of the study?
The main objectives are to ensure minimal timespans across all servers and to achieve, where possible, an equalized workload distribution.
Which mathematical approach is used?
The project models the balancing process as a linear programming problem, utilizing systems of linear inequalities and Gaussian Elimination for solving the variables.
How is the algorithm validated?
The algorithm is validated through numerous computer experiments that test different configurations of servers and tasks and measure the resulting iteration counts and CPU performance.
What does the main body of the document cover?
The main body covers the problem statement, the procedural approach to balancing (starting with two servers), experimental results, and a detailed description of the C++ software implementation.
Which key terminology defines this work?
Key terms include load balancing, multimedia networks, linear programming, work cost, backlogs, and redistribution cycles.
Why are cycles introduced during the balancing process?
Cycles are used to redistribute loads dynamically when a new load is introduced, ensuring the system reaches a balanced state while maintaining constraints.
What is the significance of the "non-negativity" property?
Non-negativity is a crucial constraint that ensures the algorithm does not produce invalid negative workloads during the redistribution of tasks.
How does the code handle data generation?
The implementation includes a pseudo-random number generator to create various input datasets representing backlogs and work costs to test the robustness of the algorithm.
What performance metrics are recorded?
The study tracks the number of load redistributions (iterations) and the CPU time required to solve each specific balancing problem.
- 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
