Electrical and Computer Engineering ETDs

Publication Date

8-27-2009

Abstract

Due to the increasing demand for high performance computing and the increasing availability of high speed networks, it has become possible to interconnect various geographically distributed computational elements (nodes) so that they can work cooperatively and obtain a performance not attainable by individual nodes. In the literature, distributing the total computation load across available processors is referred to as load balancing. This thesis considers the problem of distributed load balancing over directed graphs that are not fully connected. The impact of network topology on the stability and balance of distributed computing is studied. Furthermore, Informed Load Balancing (I-LB) is proposed. This is an approach in which the nodes first reach an agreement over the balanced state, by using a consensus-seeking protocol, before proceeding to redistribute their tasks. The performance of I-LB is compared with the performance of the Original Load Balancing approach (O-LB) in terms of speed of convergence and bandwidth usage. A proof is given that shows that the O-LB approach can guarantee convergence to a balanced state if the underlying graph is strongly connected while I-LB may not converge. However, I-LB can increase the speed of convergence and/or reduce the bandwidth usage especially for low-connectivity graphs. Finally, a third protocol called Consensus-Based Load Balancing (C-LB) is studied and its convergence characteristics and tradeoffs are discussed.

Keywords

Electronic data processing--Distributed processing, Internetworking (Telecommunication), Directed graphs--Data processing.

Document Type

Thesis

Language

English

Degree Name

Electrical Engineering

Level of Degree

Masters

Department Name

Electrical and Computer Engineering

First Committee Member (Chair)

Hayat, Majeed

Second Committee Member

Abdallah, Chaouki

Download

Share

COinS