Title: Allocating replicas in large-scale data grids using a QoS-aware distributed technique with workload constraints

Authors: Mohammad Shorfuzzaman; Peter Graham; Rasit Eskicioglu

Addresses: Department of Computer Science, University of Manitoba, Winnipeg, MB R3T 2N2, Canada. ' Department of Computer Science, University of Manitoba, Winnipeg, MB R3T 2N2, Canada. ' Department of Computer Science, University of Manitoba, Winnipeg, MB R3T 2N2, Canada

Abstract: An important technique to speed access in data grids is replication, which provides nearby replicas. In a data grid environment, resource availability, network latency and user request patterns may change. In this paper, we introduce a new distributed replica placement algorithm for hierarchical data grids that determines the positions of a minimum number of replicas expected to satisfy certain quality requirements. Our placement algorithm computes replica locations by minimising overall replication cost (read and update) while maximising Quality of Service (QoS) satisfaction for a given traffic pattern. Our algorithm also assumes that the workload capacity of each replica server is bounded. The problem is formulated using dynamic programming. We assess our algorithm using OptorSim. A comparison of our algorithm to its QoS-unconstrained counterpart and to two other existing algorithms (Greedy Add and Greedy Remove) shows that our algorithm can shorten job execution time significantly while requiring only moderate network bandwidth.

Keywords: data grids; replication; quality of service; QoS awareness; distributed algorithms; dynamic programming; workload constraints; replica allocation; grid computing; job execution time; network bandwidth.

DOI: 10.1504/IJGUC.2012.047766

International Journal of Grid and Utility Computing, 2012 Vol.3 No.2/3, pp.157 - 174

Received: 17 Jun 2011
Accepted: 09 Nov 2011

Published online: 20 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article