Skip to Main content Skip to Navigation

Message Scheduling for Data Redistribution through High Performance Networks

Frédéric Wagner 1 Emmanuel Jeannot 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : With the emergence of large scale distributed computing, new problems bound to data transfers are appearing. We present here the problem of data redistribution between two clusters connected by a high performance network. This problem consists in finding the best way to transfer data from the first cluster to the second one in the shortest possible time. In order to avoid slowing down the network, and the transfer, it is necessary to schedule the messages. This NP-complete problem (named as KBPS) has already been studied. We recall the model chosen, and study the advantages and drawbacks of the existing resolution methods. We prove that the existing heuristics are not approximation algorithms, and can in some case give some very bad results. We then develop two new polynomial-time approximation algorithms. The proof of the approximation factor and the complexity in time are presented in detail. To validate the theoretical work achieved, we conclude with results obtained from simulations and experiments on real clusters.
Document type :
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:47:42 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:20:35 PM


  • HAL Id : inria-00071506, version 1



Frédéric Wagner, Emmanuel Jeannot. Message Scheduling for Data Redistribution through High Performance Networks. [Research Report] RR-5077, INRIA. 2004, pp.31. ⟨inria-00071506⟩



Record views


Files downloads