Allocation distribuée de ressources pour les réseaux virtuels

The recent evolution of network infrastructures allows for more elasticity and dynamicity to network management. The 5th generation of networks (5G) allows the creation of Chains of Network Functions on top of virtual networks (”slices”) that can be multi-domain, or even multi-operators. Centralised solution usually used for network management might not be adequate for these newer use cases. This thesis makes the case for the opportunity of a distributed solution to the problem of the allocation of resources for these sorted chains of functions.A new distributed algorithm, split in two distinct part, is introduced. The first part computes a path that takes into account the constraints on the order of the resources and their placement on the network topology. The second part allocates the resources using vectors of counters for the scheduling or requests and a preemption mechanism to enforce it. Several heuristics are proposed for both parts. A numerical method is proposed to compare the performance of the algorithm to the expected value. The performances are then compared with those of four algorithms from the state of the art on an evaluation platform based on the SimGrid simulator. Results shows an improvement of up to 20% of the Average Usage Rate while not degrading the other metrics.Les dernières évolutions des infrastructures réseaux permettent d’apporter plus d’élasticité et de dynamicité à la gestion des réseaux. La 5ème génération de réseaux (5G) permet la création de chaînes ordonnées de fonctions sur des réseaux virtuels (”slices”) qui peuvent être multi-domaines, voire multi-opérateurs. Les solutions d’orchestration centralisée habituellement trouvées dans les réseaux peuvent ne pas répondre à certains des nouveaux cas d’usage. Cette thèse plaide pour l’opportunité d’une solution distribuée au problème d’allocation de ressources pour ces chaînes ordonnées de fonctions. Un nouvel algorithme distribué, découpé en deux parties distinctes, est proposé. La première partie calcule un chemin en prenant en compte les contraintes sur l’ordre des ressources et leur placement sur la topologie réseau. La seconde alloue les ressources en utilisant des horloges vectorielles pour l’ordonnancement des requêtes et en utilisantun mécanisme de préemption pour le faire respecter. Plusieurs heuristiques sont proposées pour chacune de ces parties. Une méthode numérique est proposée pour comparer les performances de algorithme à l’espérance mathématique. Les performances sont ensuite comparées avec celles de quatre algorithmes de l’état de l’art sur une plateforme d’évaluation basée sur le simulateur SimGrid. Les résultats montrent jusqu’à 20% d’amélioration du taux d’utilisation moyen des ressources, sans dégrader les autres métriques mesurées