Minimal cost reconfiguration of data placement in a storage area network
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 0(1), in particular, by factor 1 + delta for any small 0 < delta < 1 when the number of servers is fixed, and by factor of 2 + epsilon for arbitrary number of servers, for some epsilon is an element of [0, 1). To the best of our knowledge, this particular variant of the data migration problem is studied here for the first time. (C) 2012 Elsevier B.V. All rights reserved.
reconfiguration data placement video-on-demand approximation algorithms