Abstract

This thesis presents research and study of load balancing algorithms and the analysis of the performance of each algorithm in varying conditions. The research also covers a study of the characteristics of Internet traffic and its statistical properties. The network workload models that were implemented in the simulation program were derived from the many works already published within the Internet community.

These workload models were successfully implemented and statistical proof is given that they exhibit characteristics similar to the workloads found on the Internet. Finally, this thesis compares and contrasts the differences between stateless server selection methods and state-base selection methods with the different algorithms studied.

C H A P T E R I

INTRODUCTION

The research and results of the topic of Load Balancing and Internet traffic modeling

are presented in this thesis.

Load Balancing is a form of system performance evaluation, analysis and optimization,

which attempts to distribute a number of logical processes across a network of processing

elements. There have been many algorithms and techniques that have been

developed and studied for improving system performance. In early research in the field of

computer science, the main focus for improving performance was to develop algorithms

and techniques to optimize the use of systems with limited and expensive resources for

scientific computing and information systems. Later, there was an emphasis on how to

network groups of computers or workstations and then share the resources among workgroups.

More recently there has been a tremendous increase in the popularity of the Internet

as a system for sharing and gathering information. The use of the Internet has been

increasing at a tremendous rate and there always has been a concern among those in the

Internet community that enough resources will be available to provide the expected quality

of service that is received by its users.

The process of “balancing”, “sharing”, “scheduling” or “distributing” work using a

network of computers or a system of multiple processing elements is a widely studied subject. This paper will focus on recent works that have been written regarding today’s computing environments.

In this thesis, we will look at the art of load balancing and how it can be applied to

distributed networks and more specifically the Internet. Initially, the focus of the research

for this thesis was on development and analysis of algorithms that minimized the amount

of messaging or probing that is required for determining the current workload of a set of

processing elements, such as a group of replicated web servers. These algorithms were to

compare stochastic based methods of estimating server workloads, with more intrusive

methods of messaging and probing. During the process of developing the simulator to be

used for evaluating the algorithms in this study, tasks related to modeling network workloads,

and the workloads related to the Internet in particular, were identified to be crucial

to the research in this area and as a result of this effort, network modeling has become a

significant portion of this thesis.

The thesis is divided into the following chapters. Chapter 2 will discuss the concepts

and research related to the subject of Load Balancing. Chapter 3 will discuss the

issues related to modeling network traffic and in particular Internet traffic. Chapter 4

describes the Network Simulator used to evaluate the load balancing algorithms. Chapter

5 is the Experimental Design of the network simulations, and Chapter 6 will discuss the

results of the experimental simulations. Finally, Chapter 7 will discuss the conclusions

based upon the experiments performed in this study.

Finally, in addition to the goals already mentioned, it is the hope of the author that

this research can be used as a reference for the continued study in the areas of network

performance evaluation, modeling and simulation.