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 :
Reports
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071506
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:47:42 PM
Last modification on : Thursday, May 16, 2019 - 6:46:13 PM
Long-term archiving on : Sunday, April 4, 2010 - 10:20:35 PM

Identifiers

  • HAL Id : inria-00071506, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

249

Files downloads

301