Optimal replica placement in hierarchical Data Grids with locality assurance

Abstract: In this paper, we address three issues concerning data replica placement in hierarchical Data Grids that can be presented as tree structures. The first is how to ensure load balance among replicas. To achieve this, we propose a placement algorithm that finds the optimal locations for replicas so that their workload is balanced. The second issue is how to minimize the number of replicas. To solve this problem, we propose an algorithm that determines the minimum number of replicas required when the maximum workload capacity of each replica server is known. Finally, we address the issue of service quality by proposing a new model in which each request must be given a quality-of-service guarantee. We describe new algorithms that ensure both workload balance and quality of service simultaneously. We conduct extensive simulation experiments to evaluate the effectiveness of our algorithms. The comparison with the previous Affinity Replica Location Policy demonstrates that our algorithms consistently outperform the heuristic algorithm both in terms of minimum number of replicas used and the actual data transmission time. [Copyright &y& Elsevier]