Data replication optimisation in grid delivery network. (19th August 2009)

• Record Type: Journal Article
• Authors: Baert, Anne-Elisabeth; Boudet, Vincent; Jean-Marie, Alain
• Is Part Of: International journal of grid and utility computing. Volume 1:Number 4(2009)
• Page Start: 287
• Page End: 295
• Publication Date: 2009-08-19
• Subjects: performance analysis -- data replication -- grid delivery networks -- video on demand -- VOD -- probabilistic models -- approximation algorithms -- constraint optimisation -- simulation -- grid computing -- video services; Electronic data processing -- Distributed processing -- Periodicals; Electronic commerce -- Management -- Computer programs -- Periodicals; 004.605
• Languages: English
• ISSNs: 1741-847X

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.