Zaid Allybokus a soutenu sa thèse le mardi 11 juin.
La soutenance a eu lieu dans l’Amphi Morgenstern (bâtiment Kahn du centre Inria de Sophia Antipolis) à 15:00.
Titre: Algorithmes distribués dédiés au calcul de l’allocation de ressources alpha-équitable en temps réel dans les réseaux SDN
Résumé:
Dans cette thèse, nous étudions la conception d’algorithmes dédiés au calul de
l’allocation de ressources α-équitable en temps réel dans les réseaux
Software-Defined Networks (SDN) distribués. En premier lieu, nous définissons
trois besoins majeurs établissant les enjeux des algorithmes en temps réel
implémentable dans les controlleurs distribués SDN. Ces enjeux sont la
disponibilité de solutions faisables à tout moment, une qualité transitoire
acceptable en termes d’écart à l’optimum, une convergence en un nombre
raisonnable de tours de communications entre les differents controlleurs, ainsi
qu’une facilité des algorithmes à être massivement parallèles, indépendamment
de l’architecture SDN du réseau. Nous utilisons les outils de l’Alternating
Directions Method of Multipliers afin de définir une classe d’algorithmes qui,
sans précédent, répondent simultanément à ces enjeux. À la lumière des
propriétés structurelles du modèle de l’allocation α-fair, nous calculons une
borne inférieure sur la solution optimale et l’utilisons afin d’ajuster le
paramètre de pénalité du Lagrangien augmenté du problème dans le but
d’optimiser la performance des algorithmes. Nous montrons que l’algorithme est
capable de fonctionner en temps réel lorsque les exigences du trafic varient de
façon plus ou moins brute. La variation des exigences du trafic est modelisée
par la variation en temps réel de certains coefficients du modèle
d’optimisation qui est résolu à la volée. Ces coefficients représentent en
pratique des politiques de priorité variées au sein du trafic (paiement, type
de trafic, nombre de connections à l’intérieur d’un chemin, etc). Ensuite, nous
décrivons comment étendre l’algorithme à des scenarios réels avec des
modifications minimes, afin de prendre en compte l’équilibrage en multi-chemin
des flots et l’ajustement de la bande passante en temps réel. Par ailleurs,
nous répondons au problème de partage de ressources α-équitable lorsque
l’environnement admet des incertitudes sur la quantité de ressources
disponibles sur chaque lien, connue uniquement au travers de fonctions de
densités générales. L’axe prioritaire est alors, au lieu de la faisabilité, la
notion de fiabilité. Nous concevons alors une heuristique qui affine une
approximation extérieure du problème en se basant sur l’analyse de sensibilité
du problème statique. En toute généralité, nous arrivons à fournir une solution
fiable et acceptable en termes d’efficacité en résolvant quelques problèmes statiques.
Mots-clés: Software-Defined Networks, Allocation de Ressources, AlphaEquité, Temps Réel, Algorithmes Distribuées, ADMM, Optimisation Convexe.
