Métaheuristiques pour l’ordonnancement de workflows dans l’infrastructure IaaS

Métaheuristiques pour l’ordonnancement de workflows dans l’infrastructure IaaS

 Modélisation du problème d’ordonnancement de workflows dans l’infrastructure IaaS Dans cette section, nous décrivons notre modélisation du système d’une manière formelle. Dans ce contexte, l’objectif de l’ordonnancement consiste à répartir les tâches du workflow entre les services fournis par l’IaaS de façon à optimiser plusieurs métriques de QoS. Par conséquent, nous présentons d’abord le modèle de cloud computing, puis, nous décrivons notre modèle de workflow et les paramètres de QoS que nous traitons. 

Modèle du cloud computing

Une infrastructure IaaS est composée d’un pool de machines virtuelles U= {VM1, …, VMm} hétérogènes qui sont interconnectées. Ces machines sont mises à la disposition des utilisateurs sous forme de services à la demande via un modèle de paiement à l’usage. Chaque instance de machine virtuelle, VMj , peut être décrite par une vitesse de calcul (MIPSj) correspondant au nombre d’instructions que la ressource peut traiter par seconde, un coût monétaire d’utilisation par unité de temps, prixUj et une fiabilité (taux d’échec, λj). Le comportement de l’infrastructure IaaS peut être modélisé sous forme d’un graphe pondéré non-orienté.

Les nœuds du graphe représentent les machines virtuelles et les arêtes 59 correspondent aux liens d’interconnexions entre elles. Les poids des arrêtes représentent les vitesses de transferts ou les bandes passantes (en Mbps) des liens entre les VMs. 

Modélisation du workflow

Nous modélisons une application de workflow sous forme d’un graphe orienté acyclique (DAG : Directed Acyclic Graph), noté G (V, E). L’ensemble de nœuds V = {T1, …, Tn} représente les tâches du workflow, l’ensemble des arcs E désigne les contraintes de précédence entre les tâches.

Un arc est sous la forme dij= (Ti , Tj)  E, où Ti est appelée la tâche mère de Tj , Tj est la tâche fille de Ti , dij sont les données produites par Ti et consommées par Tj . Nous supposons que la tâche fille ne peut pas être exécutée jusqu’à ce que toutes ses tâches mères soient achevées. Dans un graphe de tâches donné, une tâche sans prédécesseur est appelée une tâche d’entrée, et une tâche sans successeur est appelée une tâche de sortie. La figure 3.1 illustre un exemple de workflow composé de 4 tâches et une IaaS composée de 3 VM. Figure 3.1. Un exemple de workflow et des ressources d’une IaaS. 

Caractérisation des métriques de QoS

Makespan

L’une des mesures les plus utilisées dans l’évaluation des algorithmes d’ordonnancement de workflows est le temps de complétion ou makespan. Le makespan est la différence entre la date de soumission du workflow et la date de réception des résultats. Autrement dit, c’est la date de fin d’exécution de la dernière tâche du workflow. Le makespan est donné dans l’équation (3.1). (3.1) où, est la Date de Fin d’exécution de la tâche .