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 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 particular variant of the data migration problem is studied here for the first time.