Soutenance mémoire
Modélisation
Problème à temps-réel souple
Considérons un problème d’ordonnancement temps-réel où un ensemble de N jobs indépendants doivent être exécutés sur un unique processeur. Chaque job a une date d’arrivée, avant laquelle il ne peut pas être traité. Un job nécessite de traiter un certain nombre d’unités d’exécution pour être accompli. A chaque unité de temps, le processeur peut être au repos, ou au travail. La vitesse du processeur réfère au nombre d’unité d’exécution qu’il peut traiter par unité de temps (lorsqu’il est au travail). Au temps k, si s [k] dénote la vitesse du processeur et c j [k] dénote le nombre d’unités d’exécution restant pour qu’un job soit traité, min (c j [k] , s [k]) unités d’exécution sont traitées durant cette unité de temps.
Dans notre problème, transmettre des messages vers le Cloud est similaire à traiter des jobs avec un processeur. Dans cette analogie, le nombre de paquets pour transmettre un message correspond au nombre d’unités d’exécution pour traiter un job. L’analogie entre notre problème d’ordonnancement et le problème d’ordonnancement temps-réel est résumé dans la Table.
GÉNÉRATION DE SCÉNARIOS
Algorithme EDF qui ignore les jobs qui ne font pas parti du sous-ensemble trouvé. C’est une façon pratique d’utiliser le simulateur pour générer les résultats à partir de cet ordonnancement.
Les résultats obtenus par simulation peuvent aussi être avantageusement utilisé pour vérifier d’éventuelles erreurs d’implémentation. Par exemple, on peut vérifier que la valeur cumulée totale obtenue dans la simulation est égale à la valeur d’utilité de base de chaque job agrégé par somme sur le sousensemble de jobs ordonnaçables obtenu, ou vérifier que tous les jobs de ce sous-ensemble sont accomplis à temps.
En dépit de ces simplifications, le problème est toujours trop complexe à résoudre dans certains cas. Trouver un ordonnancement optimal dans une quantité de temps raisonnable n’est pas toujours possible. Le solveur a donc été utilisé avec les paramètres suivants pour rechercher une solution sousoptimale :
1. “−−pcost” : branche utilisant l’heuristique hybride pseudo-coût,
2. “−−mipgap 0.02” : défini une tolérance d’écart relative de 2%, c’est-à-dire que l’on s’arrête lorsque une solution sous-optimale a été trouvée et qui est distante de moins de 2% de la solution optimale.
En utilisant ces paramètres, une solution a été trouvée en quelques secondes la plupart du temps, et cela a prit jusqu’à 15 minutes pour les instances les plus difficiles.
Modèle de simulation
Nous avons implémenté le simulateur utilisé dans ce travail en langage Python. La simulation consiste à exécuter les étapes suivantes en boucle, jusqu’à ce qu’une date de fin arbitraire soit atteinte :
1. Activer tous les jobs qui arrivent au cycle courant k.
2. Eliminer les jobs inutiles, c’est-à-dire les jobs dont l’utilité au cycle courant n’est pas strictement positive.
3. Obtenir une décision d’ordonnancement de l’algorithme et l’exécuter : si un job est planifié et qu’il ne s’agit pas du job en cours de traitement, alors on arrête le traitement du job courant (s’il y en a un), et on démarre (ou reprend) l’exécution du job planifié.
4. On laisse passer le temps jusqu’au prochain cycle k + 1, puis on met à jour les caractéristiques de tous les jobs en conséquence (unités d’exécution restantes, jobs accomplis, etc.).
Travaux associés
Douglas Jensen a proposé d’associer à chaque job une valeur exprimée en fonction du temps [Jensen et al., 1985], résultant en des fonctions de temps/d’utilité qui définissent précisément les sémantiques des systèmes à temps-réel souple. Les fonctions d’utilité utilisées dans nos travaux sont similaire à d’autres propositions [Buttazzo, 2011b] et se concentrent sur la simplicité pour des raisons de performance.
Dans ce papier, nous avons comparé la performance d’algorithmes d’ordonnancement en-ligne, en utilisant un algorithme optimal clairvoyant comme référence. Cette méthodologie a été utilisée dans plusieurs travaux de recherche antérieurs. [Baruah et al., 1992] prouve qu’aucun algorithme d’ordonnancement en-ligne ne peut avoir un taux de compétitivité strictement supérieur à 1/4 lorsque le taux de charge n’est pas borné. Les auteurs prouvent que 1/2 est une borne supérieure serrée pour des jobs avec aucune laxité dans un système à 2-processeurs. [Koren and Shasha, 1995] décrit D over , un algorithme d’ordonnancement en-ligne pour des systèmes uni-processeur surchargés. D over fournit le meilleur taux de compétitivité qui peut être réalisé pour des algorithmes non-clairvoyants. Pour prouver des bornes supérieures et inférieurs sur les taux de compétitivité réalisables par un algorithme en-ligne, plusieurs techniques sont discutées dans [Karp, 1992].
De plus, [Karp, 1992] prouve qu’utiliser un taux de compétitivité comme métrique de performance est grossièrement équivalent à considérer un adversaire omniscient qui a une connaissance parfaite de l’algorithme et des ressources de calcul infinies.
Dans l’objectif d’identifier des algorithmes en-ligne qui ont une bonne performance en pratique, un affaiblissement de cet adversaire et/ou un renforcement de l’algorithme non clairvoyant évalué est suggéré. Il a été réalisé dans [Borodin et al., 1992, Fiat et al., 1991, Raghavan and Snir, 1989] que l’aléa pouvait (relativement) diminuer la puissance de l’adversaire puisque les décisions de l’algorithme enligne ne sont plus certaines. En accord avec cette idée, les algorithmes en-ligne aléatoires peuvent être considérés plus efficaces que les algorithmes déterministes, à l’encontre de différents types d’adversaires.
Dans [Kalyanasundaram and Pruhs, 2000], il est montré qu’augmenter modérément la vitesse du processeur utilisé par un algorithme non-clairvoyant donne effectivement à cet algorithme le pouvoir de clairvoyance. De façon plus intéressante, il est montré qu’il existe des algorithmes d’ordonnancement en-ligne avec des taux de compétitivité bornés pour toutes entrées, et qui ne sont pas vraiment corrélés avec la vitesse de processeur.
Dans [Lam et al., 2004], un renforcement de l’algorithme en-ligne est considéré. Un algorithme d’ordonnancement en-ligne est dit être speed-s optimal si l’algorithme peut correspondre à la performance d’un algorithme clairvoyant optimal avec le même nombre de processeurs mais en ayant une vitesse d’exécution s fois supérieure. A travers l’utilisation d’une approche analytique, il est démon- tré que EDF-ac atteint speed-2 (resp. speed-3) optimalité dans des systèmes uni-processeur (resp. multi-processeur) en condition de surcharge.
Dans [Baruah et al., 2012], le même facteur de vitesse est utilisé. L’algorithme d’ordonnancement Earliest Deadline First with Virtual Deadlines (EDF-VD) est démontré être optimal en respect de cette métrique. Comparé à notre étude, ces résultats sont basés sur une Mixed-Criticality implicitdeadline sporadic tasks, i.e. des jobs temps-réel fermes qui ont des contraintes spécifiques sur les dates d’inter-arrivée ainsi que des valeurs de deadline spécifiques.
Une étude comparative entre des algorithmes qui utilisent différentes affectations de priorité est présentée dans [Buttazzo et al., 1995]. L’analyse est basée sur les valeurs des jobs et les deadlines des jobs, mais également sur différents mécanismes de garanties, qui améliorent la performance d’un système temps-réel durant des conditions de surcharge. Les algorithmes sont comparés en utilisant la métrique HVR, pour deux ensembles de jobs différents où les caractéristiques des jobs diffèrent dans l’intérêt de voir à quel point un algorithme est sensible en respect des paramètres des jobs. Les auteurs observent que l’algorithme Highest Density First (HDF), basé sur la densité de valeur et correspondant à l’algorithme DVD1 dans notre papier, est le plus effectif dans des conditions de surcharge, affiche une dégradation très gracieuse pendant les surcharges, et n’est pas très sensible aux paramètres des jobs.
Dans [Aldarmi and Burns, 1999], une autre évaluation comparative entre les algorithmes d’ordonnancement en-ligne dans des conditions de surcharge est effectuée. Dans cette étude, les jobs sont à temps-réel souple et un ensemble unique de jobs avec des caractéristiques de jobs arbitraires a été utilisé pour l’évaluation de performance. Il est conclut que l’algorithme DVD2 est meilleur, et il est envisagé que DTD2 est un schéma efficace qui est plus adapté pour opérer sous toutes conditions de surcharge que SDVD et EDF.
Introduction
Dans cette partie, nous nous situons au niveau L2 par rapport à la décomposition du problème proposée partie I et illustrée Figure 3. Au niveau supérieur L3, des décisions sont prises périodiquement sur le long-terme. Le résultat de chaque décision est un budget alloué au coût de la remontée des données vers le Cloud sur une période de temps. Sur des périodes de temps plus courtes, il faut au niveau L2 déterminer la quantité optimale de chaque type de données à transmettre vers le Cloud, en veillant à ce que le coût engendré par le flux V2C n’excède pas le budget alloué au niveau L3.
Dans le Chapitre 1, nous précisons le problème que nous cherchons à résoudre. Il s’agit de réaliser la provision de données pour les services eHorizon, en conciliant les différents besoins qu’il ne sera pas possible de tous satisfaire entièrement en raison des contraintes économiques (viabilité du projet eHorizon) et techniques sur la fabrication des données (capacité de la flotte de véhicules à générer certains types de données et capacité du réseau cellulaire à les transmettre vers le Cloud). De plus, certains services peuvent être plus importants que d’autres, leurs besoins inconnus, difficiles à estimer, variables dans le temps, et nous souhaitons que la satisfaction des besoins individuels (= propres à chaque service) soit prioritaire face à la satisfaction des besoins globaux pour nous prémunir de situations de famines. Nous cherchons un moyen d’abstraire l’expression concrète des besoins, et de contrôler l’influence de chaque service sur le flux de données V2C. Le problème est illustré dans la Figure 1.
Définition du problème
Modélisation des acteurs et de leurs intéractions
Des services eHorizon consomment des données V2C centralisées dans le Cloud pour générer des services. Les services ainsi générés sont alors consommés par des clients.
Un mécanisme d’allocation centralisé dans le Cloud, appelé MAC, doit déterminer la quantité de chaque type de données V2C que la flotte de véhicules doit remonter vers le Cloud (= fabriquée) pour chaque période. Le MAC doit s’assurer que, sur le long-terme, le coût engendré par la fabrication des données n’excède pas le budget prévu.
Nous faisons ici abstraction du contrôle du flux V2C, que nous considérons parfait. Autrement dit, nous supposons que la quantité exacte de données V2C à remonter sur une période est effectivement remontée au cours de la période. En réalité, ce contrôle sera à réaliser au niveau L1, et doit faire l’objet de travaux supplémentaires.
Ainsi, le MAC doit réaliser plusieurs choses : déterminer 1) en quelle quantité doit être fabriqué chaque bien, 2) qui est autorisé à utiliser les biens fabriqués, et 3) qui paie combien.
Deux catégories d’acteurs sont impliqués dans ce processus. D’une part, des acteurs internes, qui sont :
1. le Mécanisme d’Allocation Centralisé (MAC), capable de fabriquer des biens, les données V2C, pour un certain coût.
2. des agents (= les services eHorizon), qui utilisent les données V2C du Cloud fournies par le mécanisme pour fabriquer d’autres biens, les services. Par exemple une estimation du trafic ou une estimation de la qualité de la route.
D’autre part, des acteurs externes, qui sont des clients. Par exemple un transporteur qui utiliserait les informations du trafic pour optimiser ses livraisons. Les acteurs internes constituent ce que l’on appelle un groupe. Chaque client contribue financièrement et volontairement au groupe, en échange de quoi le groupe fournit des services aux clients. Nous supposons que le degré de contribution de l’ensemble des clients dépend de la satisfaction, ou richesse, que les services eHorizon leurs apportent.
La relation entre les différents acteurs du système est illustrée Figure 13.
Le mécanisme et les agents ont un objectif commun : celui de maximiser le profit du groupe auquel ils appartiennent. La difficulté est que le profit du groupe est lié à la quantité de matières premières fabriquées par une chaîne de relations complexes, chaîne qui est illustrée Figure 14.
Maximiser le profit du groupe passe par deux objectifs conflictuels, maximiser le revenu du groupe et minimiser le coût de fabrication, qui dépendent tous deux des matières premières fabriquées. D’un côté, la relation avec le coût de fabrication paraît facile à modéliser. Par exemple, il est possible de considérer un coût marginal constant, comme dans [Clarke, 1971, Moulin, 1994], c’est-à-dire que lecoût est proportionnel à la quantité de bien fabriqué. Mais d’un autre côté, la relation avec le revenu du groupe est complexe à modéliser.
NON-SOUSTRACTIBILITÉ DES DONNÉES
Pour simplifier le problème, nous supposons que la part de contribution de chaque service eHorizon au revenu d’eHorizon est connue. Nous faisons également une hypothèse d’isolation, c’est-à-dire que la part de contribution de chaque service au revenu du groupe est indépendante des autres services.
Enfin, on suppose que la richesse totale est égale à la somme de la richesse individuellement générée par chaque service (principe de superposition). Ces simplifications nous amènent à la chaîne de relations représentée Figure 15.
Exclusion à la consommation
Dans la littérature, une justification à l’exclusion d’un bien de club est que l’exclusion peut limiter le problème bien connu de free-riders [Moulin, 1994] . Le problème de free-riders est un type de défaillance du marché qui se produit lorsque la plupart des agents deviennent des free-riders, reconnaissant et exploitant l’opportunité de sous-payer un bien dont ils bénéficient [Rittenberg, 2008].
En fait, une des racines du problème de free-riders se trouve dans la définition de l’objectif des agents. Très souvent, un agent cherche à maximiser la valeur générée par les biens consommés, additionnée à la quantité de numéraire cumulée par l’agent. Cependant, dans notre contexte, l’objectif de l’agent est uniquement de maximiser la valeur générée par les biens consommés, indépendamment du numéraire qu’il cumule. En conséquence, un agent n’a pas d’intérêt à maximiser le numéraire qu’il cumule. Bien au contraire, un agent a plutôt intérêt à échanger le numéraire avec le mécanisme pour contribuer à la fabrication des biens qui lui bénéficieraient. Cette différence d’objectif, minime mais pourtant fondamentale, implique que les effets obtenus par des agents en intéraction avec un mécanisme de provision dans de nombreux travaux de la littérature sont susceptibles d’être radicalement différents des effets obtenus dans notre cas.
1. Ce concept a été initialement nommé free rider problem, et malgré que les ouvrages spécialisés de ce problème utilisent la traduction « problème du passager clandestin » [Gérard-Varet, 1998, Milgrom and Roberts, 2016, Sève, 2013], cette traduction ne permet pas, seule, de faire clairement référence au concept de free-rider. Nous choisissons donc de ne pas traduire la dénomination originale de ce problème.
Conclusion
Dans ce chapitre, nous avons précisé le cadre du problème que nous cherchons à résoudre en posant un certain nombres d’hypothèses. Nous avons identifié deux caractéristiques majeures de notre problème qui, ensemble, rendent notre problème singulier au regard de la majorité des travaux existants dans la littérature.
Il s’agit d’une part de la propriété de non-soustractibilité des données, qui veut que la consommation de données ne réduit pas la quantité de données disponible pour les autres. Nous avons justifié l’importance critique de cette propriété, qui permet la multiplication de la richesse générée par des données fabriquées par la multiplication de leur consommation, pour un coût de consommation très faible devant le coût de fabrication.
D’autre part, l’objectif des services eHorizon diffère de l’objectif usuel qui consiste à maximiser la richesse générée par les biens consommés additionnée au numéraire cumulé. Ici, l’unique intérêt des services eHorizon est de maximiser la richesse qu’ils génèrent individuellement. Cette différence d’objectif implique que l’exclusion à la consommation des biens fabriqués, qui peut trouver du sens pour palier au problème de free-riders, est difficile à justifier dans notre cas.
De ce fait, il est difficile de prédire la performance des mécanismes de provision étudiés dans la littérature, ce qui nécessite donc de rechercher un mécanisme approprié à notre problème. Pour cela, nous proposons de construire une multitude de mécanismes, que nous évaluerons pour sélectionner le meilleur.
Dans le Chapitre 2, nous introduisons les enchères simultanées à ballots-scellés, un type d’enchères très populaire qui constituera la base des mécanismes que nous étudierons. Nous introduisons ensuite le formalisme nécessaire à la construction d’une famille de variantes de mécanismes basés sur des concepts similaires à des mécanismes existants.
Dans le Chapitre 3, nous proposons un moyen pour analyser les effets obtenus avec les différents mécanismes. En raison de la difficulté de l’analyse, nous nous orientons vers une approche expérimentale qui gagne en popularité, l’approche Agents-based Computational Economics (ACE). Dans notre cas, cette approche consiste à tirer profit des techniques d’apprentissage par renforcement pour apprendre aux services eHorizon à révéler stratégiquement et efficacement leurs besoins aux mécanismes. Les résultats obtenus avec des stratégies stables et efficaces sont ensuite discutés et analysés pour guider le choix d’un mécanisme parmi plusieurs étudiés.
|
Table des matières
Remerciements
Résumé
Abstract
Acronymes
Liste des figures
Liste des tableaux
Table des matières
I Introduction générale
1 Motivation, contexte, et problématique
1.1 Comment améliorer les systèmes de transport ?
1.2 Projet eHorizon
1.3 Nécessité d’optimiser le flux de données des véhicules vers le Cloud
1.4 Problématique
2 Objectifs de la recherche et décomposition du problème
2.1 Hypothèses initiales
2.2 Décomposition du problème
3 Contributions
3.1 Algorithme d’ordonnancement en-ligne embarqué dans les véhicules
3.2 Mécanisme d’Allocation Centralisé dans le Cloud
4 Structure du manuscrit
II Algorithme d’ordonnancement en-ligne embarqué dans les véhicules
1 Définition du problème
2 Modélisation
2.1 Problème à temps-réel souple
2.2 Méthode d’évaluation
2.3 Génération de scénarios
2.4 Modèle de simulation
3 Résultats et analyses
4 Travaux associés
III Mécanisme d’Allocation Centralisé dans le Cloud
1 Définition du problème
1.1 Modélisation des acteurs et de leurs intéractions
1.2 Non-soustractibilité des données
1.3 Exclusion à la consommation
2 Construction d’une famille de mécanismes à étudier
2.1 Formalisme préliminaire
2.2 Règles d’inclusion
2.3 Règles de redistribution
2.3.1 Paiement minimal d’un agent pour la règle d’inclusion NE
2.3.2 Paiement minimal d’un agent pour la règle d’inclusion 1HB
2.3.3 Paiement minimal d’un agent pour la règle d’inclusion MCT
2.3.4 Synthèse
2.4 Mécanismes populaires qui s’inscrivent dans notre modèle
2.4.1 First-Price Sealed-Bid Auctions with a Reservation Price (FPSBARP)
2.4.2 Provision-Point-Mechanism (PPM)
2.4.3 Equal Cost Sharing with Maximal Participation (ECSMP)
3 Moyen d’analyse
3.1 Choix de l’approche ACE
3.2 Principe de l’apprentissage multi-agents
3.3 Modèle de l’environnement multi-agents
3.4 Mise en œuvre de l’algorithme d’apprentissage
4 Résultats
4.1 Mécanismes de provision évalués
4.2 Paramètres et analyses
4.3 Processus de génération des résultats
4.4 Critères d’évaluation
4.5 Analyse de sensibilité au degré de compatibilité des besoins
4.6 Analyse de sensibilité au niveau d’équilibre des apports
5 Travaux associés
5.1 Travaux qui nous ont fortement inspirés
5.2 Travaux qui utilisent une méthodologie similaire à la nôtre
IV Conclusion générale et perspectives
1 Conclusion générale
2 Perspectives
Bibliographie
Annexe : validation de l’écart de performance entre DVD1 et DVD2
