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.
Electronic data processing--Distributed processing, Internetworking (Telecommunication), Directed graphs--Data processing.
Level of Degree
Electrical and Computer Engineering
First Committee Member (Chair)
Second Committee Member
Gonzalez Ruiz, Alejandro. "Distributed load balancing over directed network topologies." (2009). http://digitalrepository.unm.edu/ece_etds/103