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.