How network topology affects dynamic loading balancing

Previous research has proposed several different load-balancing strategies and measured their performances on either a distributed system or a multiprocessor network of specific topology. The authors broadly classify all load-balancing strategies as being either static or dynamic. For certain applications, dynamic load balancing is preferable, because then the problem´s variable behavior more closely matches available computational resources. The authors address the performance of five dynamic load-balancing strategies: the Gradient Model strategy, the Sender-Initiated and Receiver-Initiated strategies, the Central Job Dispatcher strategy, and the Prediction-based strategy. The authors use a trace-driven simulation approach, collecting job traces from a production-distributed computer system and using them to simulate a loosely coupled multiprocessor network. This simulator enables performance comparisons across a range of network topologies, including a 2D-mesh, a 4D-hypercube, a linear array, and a composite Fibonacci cube