Efficient allocation and composition of distributed storage

    Authors

    J. Secretan; M. Lawson;L. Boloni

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    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.

    Journal Title

    Journal of Supercomputing

    Volume

    47

    Issue/Number

    3

    Publication Date

    1-1-2009

    Document Type

    Article

    First Page

    286

    Last Page

    310

    WOS Identifier

    WOS:000263391600003

    ISSN

    0920-8542

    Share

    COinS