WU Xiaohu

Thesis

Techniques d'ordonnancement et de tarification dans le Cloud Computing

Le cloud est devenu le principal paradigme pour le calcul, le stockage de données, etc. Le design de mécanismes d'ordonnancement et de tarification des ressources est donc d'une importance primordiale pour les fournisseurs de services cloud dans le but d'améliorer leur qualité de service et leurs revenus. 

 

Nous considérons un modèle fondamental où un ensemble de tâches "batch" doivent être ordonnancées sur plusieurs machines identiques et chaque tâche est définie par une valeur, un quantité totale de travail, une date limite et une borne de parallélisme. Le nombre de machines allouées à une tâche peut varier au cours de l'exécution sans modifier la quantité totale de travail. Pour ce modèle, nous obtenons deux résultats essentiels: une condition nécessaire et suffisante pour que l'ensemble de tâches puisse être ordonnancé sur les machines; et un algorithme en temps polynomial pour produire un ordonnancement faisable. Ces résultats fournissent un outil conceptuel et un algorithme qui permettent de proposer de nouvelles analyses et de nouveaux designs d'algorithmes pour de multiples objectifs. Nous obtenons également de nouveaux résultats pour les tâches monotones pour lesquelles la quantité totale de travail augmente avec la parallélisation.

 

Dans un deuxième temps, étant donnés les principaux modèles de tarification tels que celui d'Amazon EC2, nous proposons un framework étendu d'apprentissage en ligne pour que les tenants puissent décider du type d'instances à acheter entre instances à la demande, spot et long terme (e.g., réservées à l'avance ou détenu par ailleurs par l'organisation), de façon à minimiser leur coût.