Algorithms for Replica Placement and Update in Tree Network

Abstract

A critical issue in data replication is to wisely place data replicas which involves identifying the best possible nodes to duplicate data. Facing dynamics of data requests, this paper investigates the problem of replica placement and update in tree networks, where part of nodes have pre-existing replicas. We aim to develop efficient algorithms to accelerate the replica placement and update without causing obvious degradation in solution quality via reusing pre-existing replicas. Firstly, an efficient heuristic algorithm GRP is proposed to quickly place replicas when users change their requests dynamically, under the Closest policy where a client must be served by the closest server. Then, a Tabu search algorithm TSRP is customized to further refine the solution obtained by GRP. Furthermore, we propose a heuristic algorithm MPFSF for the replica placement and update problem, under the Multiple policy where requests of a client are served by multiple servers. Simulation results show that, GRP and TSRP can accelerate existing dynamic programming algorithm by 87.97% while quality degradation is bounded by 2.49%. MPFSF can achieve the best improvement for about 84.6% than existing heuristic algorithm.