Title

Efficient Allocation And Composition Of Distributed Storage

Keywords

Distributed storage; Grid computing; Grid economics; Quality of service

Abstract

In this paper, we investigate the composition of cheap network storage resources to meet specific availability and capacity requirements. We show that the problem of finding the optimal composition for availability and price requirements can be reduced to the knapsack problem, and propose three techniques for efficiently finding approximate solutions. The first algorithm uses a dynamic programming approach to find mirrored storage resources for high availability requirements, and runs in the pseudo-polynomial O(n 2 c) time where n is the number of sellers' resources to choose from and c is a capacity function of the requested and minimum availability. The second technique is a heuristic which finds resources to be agglomerated into a larger coherent resource, with complexity of O(nlog∈n). The third technique finds a compromise between capacity and availability (which in our phrasing is a complex integer programming problem) using a genetic algorithm. The algorithms can be implemented on a broker that intermediates between buyers and sellers of storage resources. Finally, we show that a broker in an open storage market, using the combination of the three algorithms can more frequently meet user requests and lower the cost of requests that are met compared to a broker that simply matches single resources to requests. © 2008 Springer Science+Business Media, LLC.

Publication Date

3-1-2009

Publication Title

Journal of Supercomputing

Volume

47

Issue

3

Number of Pages

286-310

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s11227-008-0193-1

Socpus ID

60649084961 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/60649084961

This document is currently not available here.

Share

COinS