Paper Info
Title
Generalized Optimal Response Time Retrieval of Replicated Data from Storage Arrays
Abstract
Declustering techniques reduce query response times through parallel I/O by distributing data among parallel disks. Recently, replication-based approaches were proposed to further reduce the response time. Efficient retrieval of replicated data from multiple disks is a challenging problem. Existing retrieval techniques are designed for storage arrays with identical disks, having no initial load or network delay. In this article, we consider the generalized retrieval problem of replicated data where the disks in the system might be heterogeneous, the disks may have initial load, and the storage arrays might be located on different sites. We first formulate the generalized retrieval problem using a Linear Programming (LP) model and solve it with mixed integer programming techniques. Next, the generalized retrieval problem is formulated as a more efficient maximum flow problem. We prove that the retrieval schedule returned by the maximum flow technique yields the optimal response time and this result matches the LP solution. We also propose a low-complexity online algorithm for the generalized retrieval problem by not guaranteeing the optimality of the result. Performance of proposed and state of the art retrieval strategies are investigated using various replication schemes, query types, query loads, disk specifications, network delays, and initial loads.
Year
DOI
Venue
2013
10.1145/2491472.2491474
TOS
Keywords
Field
DocType
generalized retrieval problem,network delay,art retrieval strategy,replicated data,storage array,generalized optimal response time,initial load,storage arrays,retrieval schedule,challenging problem,efficient maximum flow problem,efficient retrieval,existing retrieval technique,linear programming,maximum flow,replication
Disk array,Online algorithm,Network delay,Initial load,Computer science,Parallel computing,Response time,Real-time computing,Integer programming,Maximum flow problem,Linear programming
Journal
Volume
Issue
ISSN
9
2
1553-3077
Citations 
PageRank 
References 
5
0.42
47
Authors
2
Name
Order
Citations
PageRank
Nihat Altiparmak1316.33
Ali Şaman Tosun219010.03