Abstract:

The problem of replica placement and update in tree networks plays an important role in network communications. When the data access requirements change over time, the replica placement and update strategy should make sure the quality of service and reduce the cost of network operating and replica update. We propose two greedy update strategies named MAX_REUSE strategy and REQUEST_COVER strategy to solve the update problem.Time complexity analysis and simulation show that the complexity of the proposed algorithms is just O(nlog n) in worst case, while the optimal solution obtained by dynamic programming is O(n5).The cost of network operating and replica update in two algorithms is no more than 11% compared to the optimal solution. The proposed strategies  not only reduce the time complexity but also keep a low total cost.

Key words: tree network;replica placement;update strategy