Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Minimal Cost Reconfiguration of Data Placement in Storage Area Network
verfasst von : Hadas Shachnai, Gal Tamir, Tami Tamir
Erschienen in: Approximation and Online Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Video-on-Demand (VoD) services require frequent updates in file configuration on the storage subsystem, so as to keep up with the frequent changes in movie popularity. This defines a natural
reconfiguration problem
in which the goal is to minimize the cost of moving from one file configuration to another. The cost is incurred by file replications performed throughout the transition. The problem shows up also in production planning, preemptive scheduling with set-up costs, and dynamic placement of Web applications. We show that the reconfiguration problem is NP-hard already on very restricted instances. We then develop algorithms which achieve the optimal cost by using servers whose load capacities are increased by
O
(1), in particular, by factor 1 +
δ
for any small 0 <
δ
< 1 when the number of servers is fixed, and by factor of 2 +
ε
for arbitrary number of servers, for some
ε
∈ [0,1). To the best of our knowledge, this fundamental optimization problem is studied here for the first time.