Scheduling communication requests traversing a switch : complexity and algorithms

(eng) In this paper, we study the problem of scheduling file transfers through a switch. This problem is at the heart of a model often used for large grid computations, where the switch represents the core of the network interconnecting the various clusters that compose the grid. We establish several complexity results, and we introduce and analyze various algorithms, from both a theoretical and a practical perspective. (fre) Dans ce rapport, nous étudions l’ordonnancement de l’envoi de fichiers à travers un switch. Ce problème est souvent utilisé pour modéliser le réseau utilisé par une grille de calcul, où le switch représente le coeur du réseau qui relie les différents clusters composant la grille. Nous établissons différents résultats de complexité, avant d’étudier plusieurs algorithmes, tant d’un point de vue théorique que d’un point de vue pratique.28 pages, figures en couleurs, tableaux, graphiques, 22 références bibliographique