Research On Load Balancing Algorithms On Interconnection Networks Based On Cayley Graph

Load balancing is a very important factor impacting the performance of the parallel and distributed computing. In many practical applications, there will be varying degrees of load balancing problems. Many scholars have researched and implemented load balancing algorithms on a variety of interconnection network structures. For large-scale network topology, such as Clustering and Grid Computing, the nearest neighbor algorithm is a more realistic and meaningful local load balancing algorithm than the global algorithm, which is equally applicable to the interconnection network based on Cayley graph. Due to its good properties, such as simply-constructed and symmetry, the Cayley-based interconnection network got a wide range of interest and applications. Thus, effectively solving the load balancing problems on this type of network is also of great significance.Our objective is to implement the load balancing algorithms on these new interconnection networks based on Cayley graph, represented by BSN ( Biswapped Network ) and GCNET ( a Caley-based network with small world characteristics ). We assume that each node can only communicates with its directly adjacent nodes, and computing loads can only move through these connecting edges. Similarly, each node can only balance loads with those directly connected nodes, through several iterations to achieve the whole system's load balancing. The load balancing algorithms will be used in this dissertation is a hybrid ideal of the diffusion and dimension exchange schemes, which also belong to the nearest neighbor algorithm.Firstly, as for the load balancing problem on BSN, according to its modular characteristic, a load balancing algorithm called DEDD is proposed, which mix diffusion and dimension exchange schemes, and the load-balancing process will be divided into four stages: diffusion– exchange– diffusion– diffusion. It shows better stability than general schemes for load balancing. According to existing diffusion algorithm FOS, SOS and OPT, an extended scheme DEDD-X is developed. Secondly, regarding to the load balancing on GCNET, similarly to the idea of the DEDD algorithm, the load-balancing process will be divided into four stages: diffusion– diffusion– exchange– diffusion. The algorithm is able to complete the load balancing tasks on GCNET and has a simple iterative process, which is called DDED. Finally, experiments and simulations show that the two kinds of load balancing algorithms we proposed have good convergence-rate under the state with random or peak initial load. These jobs have some reference value for the research and application on load balancing algorithms on interconnection networks based on Cayley graph.