Paper Info
Title
Integrated Maximum Flow Algorithm for Optimal Response Time Retrieval of Replicated Data
Abstract
Efficient retrieval of replicated data from multiple disks is a challenging problem. Traditional retrieval techniques assume that replication is done at a single site using homogeneous disk arrays having no initial load or network delay. Recently, generalized retrieval algorithms are proposed to cover heterogeneous disk arrays, initial loads, and network delays. Generalized retrieval algorithms achieve the optimal response time retrieval schedule by performing multiple runs of a maximum flow algorithm. Since the maximum flow algorithm is used as a black box technique, flow values of the previous runs cannot be conserved to speed up the process. In this paper, we propose integrated maximum flow algorithms for the generalized optimal response time retrieval problem. Our first algorithm uses Ford-Fulkerson method and the second algorithm uses Push-relabel algorithm. Besides the sequential implementations, a multi-threaded version of the push-relabel algorithm is also implemented. Proposed algorithms are investigated using various replication schemes, query types, query loads, disk specifications, and system delays. Experimental results show that the sequential integrated push-relabel algorithm runs up to 2.5X faster than the black box version. Furthermore, parallel integrated push-relabel implementation achieves up to 1.7X speed up (~1.2X on average) over the sequential algorithm using two threads, which makes the integrated algorithm up to 4.25X (~3X on average) faster than its black box counterpart.
Year
DOI
Venue
2012
10.1109/ICPP.2012.34
ICPP
Keywords
Field
DocType
integrated maximum flow algorithm,generalized retrieval algorithm,proposed algorithm,sequential integrated push-relabel algorithm,network delay,replicated data,maximum flow algorithm,initial load,integrated algorithm,optimal response time retrieval,sequential algorithm,push-relabel algorithm,efficient retrieval,maximum flow,formal specification,parallel processing,replication,storage arrays,servers,multi threading
Black box (phreaking),Push–relabel maximum flow algorithm,Disk array,Dinic's algorithm,Out-of-kilter algorithm,Computer science,Parallel computing,Maximum flow problem,Black box,Sequential algorithm,Distributed computing
Conference
Citations 
PageRank 
References 
8
0.49
14
Authors
2
Name
Order
Citations
PageRank
Nihat Altiparmak1316.33
Ali Saman Tosun214418.94