Scheduling communication requests traversing a switch : complexity and algorithms

Matthieu Gallet (1) , Yves Robert (1) , Frédéric Vivien (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

In this paper, we study the problem of scheduling file transfers through aswitch. This problem is at the heart of a model often used for large grid computations,where the switch represents the core of the network interconnectingthe various clusters that compose the grid. We establish several complexityresults, and we introduce and analyze various algorithms, from both a theoreticaland a practical perspective.

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 cœur 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.

Mots clés: Complexity; Grid computing; Networks; Scheduling file transfers; Switch

Mots clés: Commutateur; Complexité; Grille de calcul; Ordonnancement de transfert de fichiers; Réseaux

Domaines: Informatique [cs]

Matthieu Gallet, Yves Robert, Frédéric Vivien. Scheduling communication requests traversing a switch : complexity and algorithms. [Research Report] LIP RR-2006-25, Laboratoire de l'informatique du parallélisme. 2006, 2+26p. ⟨hal-02102309⟩