Activités de Recherche

Mes dernières activités de recherche se focalisent sur les thématiques suivantes :

• Routage.
• Conception des réseaux.
• Conception hors ligne des réseaux physiques,
• Conception de réseaux virtuels (mappage des réseaux virtuels sur un réseau substrat),
• Placement et chainage de fonctions réseaux (VNF) ou problème d’approvisionnement des chaines de service (SFC provisioning).
• Couverture dans les réseaux (drones ou capteurs).
• Robustesse des réseaux
• Impact des stratégies de partage de ressources sur l’efficacité de la prtection contre les pannes,
• Protection locale des réseaux virtuels,
• Protection de bout-en-bout des chaines de services.
• Méta-heuristiques et optimisations combinatoires

Dans le cadre de ma recherche, je traite différents problèmes NP-complets liés aux thématiques précédentes. Parmi les résultats obtenus, je cite :

• Transformation du problème de placement et de chaînage des fonctions réseau en un problème de routage contraint dans un graphe multiparti : Ce résultat constitue une avancée significative, car il fournit, pour la première fois, une solution exacte au problème sans recourir à la programmation linéaire en nombres entiers (ILP). Le routage contraint, largement étudié et bien documenté dans la littérature, facilite le développement d’heuristiques efficaces pour résoudre ce problème. En outre, non seulement la complexité du problème est désormais connue, mais également son approximabilité, ce qui permet une meilleure compréhension des mécanismes sous-jacents au placement et au chaînage des fonctions réseau.

À cet égard, nous avons proposé une heuristique basée sur l’algorithme de Dijkstra, où jusqu’à k chemins sont conservés à chaque nœud de la topologie du réseau substrat. Les simulations réalisées ont montré que le gain obtenu en augmentant la valeur du paramètre k diminue rapidement avec l’augmentation de k. Cela suggère qu’une faible valeur de k offre une probabilité élevée d’obtenir une solution proche de l’optimum. Ces résultats mettent en lumière l’efficacité de notre approche pour résoudre ce problème complexe. Plus de détails sur cette contribution sont disponibles dans notre publication : lien

• Placement des fonctions réseau dans un réseau substrat avec bande passante abondante : Ce problème a été reformulé en un problème quadratique de sac à dos multiple. Les contraintes correspondent à celles du bin packing, tandis que l’objectif s’aligne sur celui du sac à dos multiple. Pour résoudre ce problème, nous avons utilisé des algorithmes génétiques, reconnus pour leur efficacité dans les différentes variantes du problème du sac à dos. Plus de détails sur cette contribution sont disponibles ici : lien

• Protection des réseaux virtuels contre les pannes simples : Nous avons démontré que, dans un réseau surdimensionné, le problème de protection locale d’un réseau virtuel peut être réduit à la construction d’un arbre de Steiner, un problème connu pour sa NP-difficulté. Une heuristique basée sur les arbres de Kou-Markowsky-Berman a été proposée pour les réseaux substrats aux ressources limitées. Plus d’informations sur ce travail sont disponibles ici : lien

• Protection des chaines de service (SFC) : J'ai démontré que le problème de protection de bout en bout d’une chaîne de services (SFC) est NP-complet, même sans contraintes de ressources, ce qui constitue un résultat crucial pour les fournisseurs et opérateurs qui ne peuvent plus se contenter de surdimensionner les réseaux pour résoudre ce problème. Pour y faire face, j’ai développé une heuristique originale, inspirée du principe de « leave room » issu des problèmes de couverture par ensembles, qui maximise la disjonction entre les parcours primaire et de secours tout en réduisant l’allocation des ressources, apportant ainsi une avancée significative à ce type de problème

• Complexité de différents problèmes : Nous avons montré que, dans un réseau surdimensionné, le problème de placement et chaînage des fonctions réseau peut être réduit à un problème de plus court chemin, solvable en temps polynomial. En revanche, nous avons également démontré que la version générique de ce problème est NP-complet, même pour des chaînes de service (SFC) de taille fixe ou des topologies de réseau substrat fixes. Ces résultats, ainsi que d’autres contributions, peuvent être consultés ici: lien

• Autres thématiques de recherche : Parmi les autres sujets abordés figurent le mappage de réseaux virtuels dans les réseaux interdomaines, la conception de réseaux physiques, et la protection des réseaux de drones. D’autres thématiques ayant attiré mon attention et que j’ai traitées sont décrites en détail sur cette page : lien

La liste de mes publications peut être trouvée ici : lien