Università degli studi di Cagliari
Dipartimento di Ingegneria Elettrica ed Elettronica

Tesi di Laurea Specialistica / Master Thesis:
Titolo / Title: Load balancing on networks with gossip based distributed algorithms [pdf]
Relatori / Advisors: Prof. Alessandro Giua (DIEE-UNICA); Dott. Carla Seatzu (DIEE-UNICA)

Software: Matlab source code

Pubblicazioni / Publications:
M. Franceschelli, A. Giua, C. Seatzu, "Load balancing on networks with gossip-based distributed algorithms," 46th IEEE Conf. on Decision and Control (New Orleans, LA, USA), December 2007. [pdf]

Load balancing over networks with gossip based distributed algorithms

Abstract

In this thesis we studied the distributed and decentralized load balancing problem on arbitrary connected graphs, representing an homogeneous network of agents. The net is supposed to contain several tasks or resources represented by possibly different integer numbers, to be processed, consumed or simply allocated at the nodes. We proposed a randomized algorithm based on gossip, fully distributed, that achieves consensus on the load distribution within fixed bounds of the optimal one. It is also shown by simulations that in most cases the achieved consensus is optimal. It is presented a computationally convenient heuristic and showed that it ensures the same bounds. The simulation results, however, show that the heuristic performs worse. Finally the cases of non homogeneous networks, where each node has a capacity, and finite atomic transfer updates, where the amount of transferred load in one step is bounded, have been explored. We studied the computational complexity of these algorithms and proposed an approach based on the branch and bound algorithm to reduce the computational load.

Keywords: load balancing, gossip, randomized algorithms, decentralized algorithms.

Bilanciamento del carico su reti con algoritmi distribuiti basati sul gossip

Sommario

In questa tesi è stato studiato il problema del bilanciamento distribuito del carico su grafi arbitrariamente connessi, rappresentanti una rete omogenea di agenti. Si suppone che la rete contenga molti task rappresentati da numeri interi possibilmente diversi che devono essere eseguiti, consumati o semplicemente allocati ai nodi. E' stato proposto un algoritmo randomizzato basato sul gossip, totalmente distribuito, che raggiunge il consenso sulla distribuzione del carico entro un intorno della distribuzione ottimale. Le simulazioni mostrano che nella maggior parte dei casi il consenso raggiunto è ottimo. In aggiunta è stata presentata una euristica di bassa complessità computazionale ed è stato mostrato come essa abbia le stesse prestazioni di caso peggiore dell' algoritmo generale. I risultati delle simulazioni mostrano però che l'euristica è meno efficiente dal punto di vista dell' ottimalità della soluzione. Per ultimo sono state esplorate delle varianti nel caso di reti non omogenee, ovvero quando i nodi hanno delle capacità differenti, e il caso di massimo trasferimento atomico limitato, corrispondente alla massima quantità di carico trasferibile in un passo dell' algoritmo. E' stata studiata la complessità computazionale di questi algoritmi ed è stata proposta una tecnica per ridurla basata sull'algoritmo del branch and bound.

Parole chiave: Bilanciamento del carico, gossip, algoritmi randomizzati, algoritmi decentralizzati.

back