Title: Data replication optimisation in grid delivery network

Authors: Anne-Elisabeth Baert, Vincent Boudet, Alain Jean-Marie

Addresses: LIRMM, CNRS, Universite de Montpellier 2, 161 rue ADA, 34392 Montpellier Cedex 5, France. ' LIRMM, CNRS, Universite de Montpellier 2, 161 rue ADA, 34392 Montpellier Cedex 5, France. ' LIRMM, CNRS, Universite de Montpellier 2, 161 rue ADA, 34392 Montpellier Cedex 5, France

Abstract: 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.

Keywords: performance analysis; data replication; grid delivery networks; video on demand; VOD; probabilistic models; approximation algorithms; constraint optimisation; simulation; grid computing; video services.

DOI: 10.1504/IJGUC.2009.027918

International Journal of Grid and Utility Computing, 2009 Vol.1 No.4, pp.287 - 295

Published online: 18 Aug 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article