Abstract: Towards Optimal Load Balancing Topologies

Thomas Decker, Burkhard Monien, and Robert Preis

Many load balancing algorithms balance the load according to a topology. Its choice can significantly influence the performance of the algorithm. We consider the two phase balancing model. The first phase calculates a balancing flow with respect to this topology by a diffusion scheme. Its time requirement depends on the maximum node degree and on the number of eigenvalues of the network. The second phase migrates the load according to this flow.
A small flow volume and a small diameter of the graph keeps the time requirement of this phase low.

We compare and propose several network topologies based on these measurements. Several experiments on a Cray T3E and on a cluster of PCs confirm our cost functions for both balancing phases.