On the minimisation of cost for replica migration

Abstract

Although several replica placement algorithms have becn proposed and sιudied ίη the literaturc, little research has been done so far οη capturing and minimizing the cost for migrating from an existing replica placement Ιο a new one. Ιη this work we investigate the 50 caIled RepIίca Transfer ScheduIίng Problem (RTSP) which can be briefly described as follows: Given replica placemcnts X..Id aηd Xnew , determine a sequence of object transfers and deletion5 to obtain X ηew based οη XoId with minimum transfer (network) cost. We study RTSP for the case where servers have limited storage capacity. lι can be shown that the problem is NP-complete. Therefore, we propose several heuristics and compare their performance. The proposed heuristics fall ίη three categories: (ί) algorithms derivcd from existing continuous replica placement heuristics, which take as ίηρυι an exi5ting placement and produce a new placement along with a schedule Ιο implement ίι; (ίί) algorithms that take as ίηρυι two placements and compute a schedule ιο obtain the one from ιhe other; (ίiί) algorithms for cnhancing a givcn schedule. Results indicate that heuristics of type (ίί) perfonη favorably compared Ιο the algorithms of type (ί), and that heuristics of type (ίίί) can optimize schedules generated by algorithms of type (ί) and (ίί). ΤΟ ουΓ knowledge, this is thc first time that RTSP has been sιudied as a separate problem.