Data replication optimisation in grid delivery network
Anne Elisabeth Baert, Vincent Boudet, Alain Jean Marie · International Journal of Grid and Utility Computing · 2009
In this paper, we examine the data replication problem in a particular Grid Delivery Network (GDN) which is a system that provides video services, among which is Video On Demand (VOD). In this system, the data are divided into fixed size blocks which must be replicated on hosts to decrease the total download time. We propose a probabilistic model to optimise the average download time of requests based on the host's availability and the document size distribution. The objective function induced by this model is a non-linear integer problem. It can be solved in real values by Lagrangian optimisation. We prove that in a particular case, this problem can be reduced to a knapsack problem. We propose approximation algorithms and validate them using simulations with varying characteristics.