On the minimisation of cost for replica migration
![Thumbnail](/xmlui/bitstream/handle/11615/39706/5074.pdf.jpg?sequence=3&isAllowed=y)
Öffnen
Autor
Τziritas, NikolaosCommittee member
Houstis, Catherine
Mpozanis, Panagiotis
Supervisor name
Lalίs, Spyros
Datum
2006Language
en
Access
free
Zusammenfassung
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.
Academic publisher
Πανεπιστήμιο Θεσσαλίας. Πολυτεχνική Σχολή. Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών.