How network topology affects dynamic load balancing

Precious 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. The simulator, whose design includes task size, computation cost, communications cost, and task migration cost, consists of a task scheduler, a task queque, and a network of virtual processors. 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. The Fibonacci cube, derived from the well-known Fibonacci series, is one of the more recently proposed novel interconnection topologies. All five strategies performed best in the hypercube and the composite Fibonacci cube. The results also show that the performance of a dynamic load-balancing strategy is affected by both the average processor distance and the average node degree of the network.