Investigating the replica transfer scheduling problem

Abstract

The Replica Placement Problem (RPP) aims at selecting the nodes for duplicating data objects in order to optimize their access. Even though a lot of work already exists on RPP, the issue of implementing the resulting allocation scheme is typically overlooked. In this paper we introduce the Replica Transfer Scheduling Problem (RTSP), briefly stated as: given a network of servers with limited storage capacity, a set of data objects and two replication schemes X old and X new, find a schedule of object transfers and deletions for implementing Xnew based on X old with minimum communication cost. Given that this problem is NP-complete, we introduce several different heuristics to solve it, and evaluate them via simulations.