|
|
Yu Zhang
zhangy02@csse.uwa.edu.au
Entry year: 2003
Enrolment status: confirmed
Degree: MCompSci
Degree status: complete semester 1, 2005
Project: Load Balancing and Rebalancing on Web Based Environment
Supervisor(s): Gordon Royle
Project status: complete semester 2, 2004
|
|
In this project, we investigate two variants of a load distribution problem that is associated with distributing loads of varying size on a multi-server web-based environment.
Solving the classical Load Balancing Problem allows us to distribute static web components to multiple servers, so that the loads on the servers are as equally distributed as possible.
A typical objective is to minimize the makespan, the load on the heaviest loaded server.
In reality however, loads on servers are often dynamic.o
As the load of web components change over time, the Load Rebalancing problem was introduced by S. Keshav of Ensim Corporation.
To solve the Load Rebalancing Problem, we try to redistribute the loads of web components, in a fixed number of steps as moving components across servers can be expensive, so that the load on the servers are as equally distributed as possible.
Solving these two problems successfully would allow us to utilize resources better and achieve better performance.
However, these problems have been proven to be NP-hard, thus generating the exact solutions in tractable amount of time becomes infeasible when the problems become large.
We thus adopt four greedy approximation algorithms to solve these two problems in polynomial time, within constant guaranteed error ratio.
We demonstrate how these algorithms works and carry out experiments to test if the said error ratios are valid on our test data set.
We present the results obtained, and compare the performance of the algorithms.
We conclude that these approximation algorithms do indeed run in polynomial time, they generate approximated results within the said error ratio on our test data sets, and they are valid tools to assist us to balance and rebalance loads on a multi-server web-based environment.
|
 Proposal
Dissertation
|
Last update: Wed Jul 27 10:49:03 2005
|
|
