In this paper, we examine the data replication problem in a particular distributed Video on Demand system. This VOD system is based on Grid Delivery Network which is an hybrid architecture based on P2P network and Grid Computing. In this system, datas are divided into fixed size blocks which must be replicated on hosts to decrease the total average download time. Thus, we propose a probabilistic model to optimize the average download time of requests for a document. The objective function induced by this model is a non-linear integer problem. It can be solved in real values by Lagrangian optimization. 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. We prove that the average download time is independent of the allocation of the documents' blocks. On the contrary, the allocation of the blocks have a very strong impact of the download time's variance.