From Flow Control in Multi-path Networks to Multiple Bag-of-tasks Application Scheduling on Grids

A very large number of applications that are currently deployed on large scale distributed systems such as grids or volunteer computing systems are Bag-of-Tasks (BoT) applications. Up until now, simple mechanisms have been used to ensure a fair sharing of resources amongst these applications. Although these mechanisms have proved efficient for CPU-bound applications, they are known to be ineffective in the presence of network-bound applications. In this article, we propose a fully distributed algorithm for fairly scheduling BoT applications on a computing grid while respecting resource constraints. This algorithm is inspired by techniques used in flow control mechanisms in multi-path networks. Yet, we prove that the context of BoT scheduling is significantly more difficult in practice and that a set of non-trivial adaptations are required to ensure convergence. We prove their effectiveness through an extensive set of simulations that enables to deeply understand the potential benefits as well as the limitations of this technique in the context of grid computing.Une grande partie des applications actuellement déployées à grande échelle est de type Bag-of-Tasks (BoT), c'est-à-dire qu'elles sont constituées d'un grand nombre de tâches identiques et indépendantes. Jusqu'ici, seulement des mécanismes simples ont été mis en oeuvre pour s'assurer d'un partage équitable des ressources entre les applications. Si ces mécanismes ont prouvé leur efficacité dans le cas où les applications sont gourmandes en calcul, leur inefficacité en présence d'applications gourmandes en communications est également connue. Dans cet article, nous proposons un algorithme complètement distribué pour l'ordonnancement équitable d'applications de type BoT tout en exploitant efficacement l'ensemble des ressources (de communication et de calcul). Cet algorithme s'inspire de techniques qui ont été utilisées dans le domaine du contrôle de flux dans les réseaux multi-chemins. En dépit de leur ressemblance sur le plan théorique, nous montrons que le contexte de l'ordonnancement d'applications BoT dans une grille est significativement plus délicat en pratique que celui du contrôle de flux dans des réseaux multi-chemins. Un ensemble d'adaptations non triviales est nécessaire pour obtenir la convergence et nous montrons leur efficacité à travers un ensemble conséquent de simulations Nous pensons que l'analyse minutieuse de cet algorithme présentée dans ce document permet de comprendre finement les avantages et les limitations de cette technique dans le contexte des grilles de calcul