Distributed load balancing over directed network topologies

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.

Name thesis:degree_name

Electrical Engineering

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical and Computer Engineering

Year

2009

Author dc:creator

• Gonzalez Ruiz, Alejandro

Contributors dc:contributor

• Mostofi, Yasamin
• Hayat, Majeed
• Abdallah, Chaouki

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

Language dc:language

English

Repository record dc:identifier

https://digitalrepository.unm.edu/ece_etds/103

OAI identifier oai:identifier

oai:digitalrepository.unm.edu:ece_etds-1102