Competitive equilibrium approach for load balanicing a grid network

Abstract

Grids consist of hundreds of inexpensive heterogeneous computers distributed geographically to solve parallel processing problems that previously could have been solved by using super computers. Data grids provide an infrastructure for applications that generate and reference enormous amounts of data. One of the biggest issues in such a system is techniques for effectively distributing the processes of a parallel program on multiple processing elements. Load balancing is to allocate or distribute processes on multiple processors to achieve the performance goal(s) such as minimizing execution time, minimizing communication delays, and/or maximizing resource utilization. This thesis investigates various load balancing algorithms and proposes competitive equilibrium approach for load balancing a grid network. The thesis begins with the discussion of concepts relating to game theory and competitive equilibrium theory. Then the thesis presents a generic grid system model and maps the grid system model to Fisher s market model and Competitive Equilibrium is obtained. Later, the generic grid system model is extended to consider communication delay and static load balancing using Competitive Equilibrium approach is proposed. Further, the static load balancing scheme is extended for dynamically load balancing a grid system. In this context, a dynamic Fisher s market model is defined and the properties of Recursive Competitive Equilibrium are stated. Then the dynamic model of grid system is mapped to dynamic Fisher s market model and Recursive Competitive Equilibrium is obtained for dynamically load balancing a grid system. Further, a model for Data grid is presented and three approaches for load balancing a Data grid Global Optimal Scheme, Nash Equilibrium Scheme, and Competitive Equilibrium Scheme are discussed. In all the cases, a computer model is run to evaluate the performance of Competitive Equilibrium Scheme (CES) and compared against two other schemes- Global Optimal Scheme (GOS), and Nash Equilibrium Scheme