PhD defense of Adrien Gausseran

Adrien Gausseran

  • Title: “Optimization algorithms for network slicing for 5G”
  • When: November 9, 2021 — 14:30
  • Where: Auditorium E130 of Polytech, Templier 2 building
  • Committee:
    • Mathieu Bouet (referee), head of network software lab, Thales SIX GTS France, Gennevilliers, France
    • Frédéric Giroire (supervisor), Senior Researcher, CNRS, Sophia Antipolis, France
    • Brigitte Jaumard, Professor, Concordia University, Montréal, Québec, Canada
    • Adlen Ksentini, Professor, EURECOM, Sophia Antipolis, France
    • Joanna Moulierac (supervisor), Assistant Professor, Université Côte d’Azur, Sophia Antipolis, France
    • Nicolas Nisse (supervisor), Senior researcher, Inria, Sophia Antipolis, France
    • Géraldine Texier (referee), Professor, IMT Atlantique, Cesson-Sévigné, France
    • Guillaume Urvoy-Keller, Professor, I3S, Sophia Antipolis, France
  • Abstract: Our decade is marked by an increase in the use of mobile networks for industrial and administration actors as well as for the general public thanks to their evolution. The introduction of the 5th generation of mobile networks, 5G, brings a diversity of use cases for mobile networks and a growing number of demands with very heterogeneous needs and with strong quality of service (QoS) constraints. The development of 5G relies on new techniques such as Software Defined Networking (SDN) and Network Function Virtualisation (NFV) technologies. SDN allows the separation of control and data planes by providing centralised network management. NFV decouples network functions from the hardware that performs them through virtualisation. The use of these two technologies automates the management of the network and makes it much more flexible and adaptable to changing traffic flows and requirements. The introduction of the network slicing paradigm leads to a division of the network into multiple independent virtual networks cohabiting on the same infrastructure. This paradigm allows to meet the very heterogeneous needs of future applications. In this thesis, we focus on optimising the resource utilisation of next generation networks in order to decrease operational costs and to accept more demands. We first study the allocation of service function chains, to quickly accept requests and to meet the diverse and high-volume demands of mobile networks. We then study the feasibility of Make-Before-Break reconfiguration of requests, which allows to reconfigure without degrading the QoS. We then scale up our reconfiguration and adapt it to network slicing to be used on future 5G networks. Finally, we optimise the reconfiguration periods by implementing a reinforcement learning algorithm, minimising the management costs.

  • Titre: “Algorithmes d’optimisation pour le Network Slicing pour la 5G”
  • Résumé: Notre décennie voit l’accroissement de l’utilisation des réseaux mobiles pour les acteurs industriels et administratifs ainsi que pour le grand public grâce à l’introduction de la 5ème génération de réseaux mobiles : la 5G. La 5G apporte une diversité de cas d’utilisation des réseaux mobiles et un nombre croissant de demandes avec des besoins très hétérogènes mais toujours avec de fortes contraintes de qualité de service (QoS).

    La 5G a été développée pour utiliser les technologies de réseaux définis par logiciel (SDN) et de virtualisation de fonctions réseaux (NFV). SDN sépare les plans de contrôle et de données et offre une gestion centralisée du réseau. NFV dissocie les fonctions réseaux du matériel qui les exécute grâce à la virtualisation. Ces technologies automatisent la gestion du réseau et le rendent plus flexible et adaptable à l’évolution du débit du trafic ainsi que de ses besoins. L’introduction du paradigme de découpage du réseau entraîne une division du réseau en des réseaux virtuels indépendants cohabitant sur la même infrastructure. Ce paradigme permettra de répondre aux besoins très hétérogènes des futures demandes.

    Dans cette thèse nous nous intéressons à l’optimisation de l’utilisation des ressources des réseaux de nouvelle génération afin de diminuer les coûts opérationnels et d’accepter plus de demandes. Nous étudions d’abord l’allocation de chaînes de fonctions de services, pour accepter rapidement les requêtes et répondre aux demandes diverses et abondantes des réseaux mobiles. Nous étudions ensuite la faisabilité de la reconfiguration Make-Before-Break des requêtes, qui permet de reconfigurer sans dégrader la QoS. Nous adaptons ensuite notre reconfiguration au network slicing pour l’utiliser sur les futures réseaux 5G. Enfin nous optimisons les périodes de reconfiguration grâce à un algorithme d’apprentissage par renforcement, réduisant ainsi les coûts de gestion.

PhD defense of Thibaud Trolliet

Thibaud Trolliet

  • Title: “Study of properties and modeling of complex social graphs”
  • When: June 25, 2021 — 14:00
  • Where: online on YouTube
  • Committee:
  • Abstract: The rapid emergence of social networks, their major impact on today’s society, and the recent access to large amounts of data about them has led to a strong interest in the study of complex networks in last decades. Many random graph models have been proposed to reproduce these networks and their properties – small diameter, power-law degree distribution, presence of communities, … However, due to the complexity of their theoretical study, the proposed models are often designed for undirected graphs and focus on the emergence of one or two properties at a time. This thesis aims at developing models of random graphs that are general enough to reproduce many complex properties observed in real-world networks. In particular, we present models for constructing graphs with arbitrary degree distributions, directed graphs with a high clustering coefficient, and hypergraphs with power-law degree distributions and a strong presence of communities. We study analytically and experimentally the properties of the presented models. We develop a tool using Markov chains to compute the degree distribution of preferential attachment models.
    In order to help in the construction of these models, we study in this thesis two large complex networks: a directed network with all followings on Twitter, with 505 million accounts and 23 billion followings; and a hypergraph of scientific co-publications extracted from the Scopus database, containing 2.2 million authors and 3.9 million publications. Atypical properties emerge from the study of these two graphs, coming in particular from their directed and hypergraph character, that no model of the literature could reproduce until now.

  • Titre: “Etude des propriétés et modélisation de graphes sociaux complexes”
  • Résumé: L’émergence rapide des réseaux sociaux lors des deux dernières décennies, leur impact majeur sur la société actuelle, ainsi que l’accès récent à de grandes quantités de données les concernant, a amené un fort attrait pour l’étude des réseaux complexes.
    De nombreux modèles de graphes aléatoires ont été proposés afin de reproduire ces réseaux et leurs propriétés – faible diamètre, distribution des degrés en loi de puissance, présence de communautés, …
    Cependant, du fait de la complexité de l’étude théorique de leurs propriétés, les modèles proposés sont souvent conçus pour des graphes non orientés et se concentrent sur l’émergence d’une ou deux propriétés à la fois.

    Cette thèse a pour but de développer des modèles de graphes aléatoires suffisamment généraux pour reproduire de nombreuses propriétés complexes observées dans les réseaux du monde réel. En particulier, nous présentons des modèles permettant de construire des graphes avec des distributions de degrés quelconques, des graphes dirigés avec un haut coefficient de clustering, et des hypergraphes avec distribution de degrés en loi de puissance et une forte présence de communautés. Nous étudions analytiquement et expérimentalement les propriétés des modèles présentés. Nous développons enfin un outil utilisant les chaînes de Markov pour calculer la distribution des degrés de modèles d’attachement préférentiel.

    Afin de s’aider dans la construction de ces modèles, nous étudions dans cette thèse deux réseaux complexes de grande taille : un graphe dirigé de l’ensemble des liens d’abonnements sur le réseau social Twitter, avec 505 millions de comptes et 23 milliards d’abonnements ; et un hypergraphe de co-publications scientifiques extraites de la base de données Scopus, contenant 2.2 millions d’auteurs distincts et 3.9 millions de publications.
    Des propriétés atypiques émergent de l’étude de ces deux graphes, provenant en particulier de leur caractère dirigé et d’hypergraphe, et qu’aucun modèle de la littérature ne permettait jusqu’alors de reproduire.

PhD defense of Giuseppe Di Lena

Giuseppe Di Lena

    • Title: “Distributed and Trustable SDN-NFV-enabled Network Emulation on Testbeds and Cloud infrastructures”
    • When: March 22, 2021 — 10:00
    • Where: online – (recorded and uploaded here)
    • Committee:
    • Abstract: In recent years, there have been multiple enhancements in virtualization tech-nologies, cloud computing, and network programmability. The emergence of concepts likeSoftware Defined Networking (SDN)andNetwork Function Vir-tualization (NFV) are changing the way the Internet Service Providers manage their services. In parallel, the last decade witnessed the rise of secure pub-lic cloud platforms like Amazon AWS and Microsoft Azure. These new con-cepts lead to cost reductions and fast innovation, driving the adoption of these paradigms by the industry. All these changes also bring new challenges. Net-works have become huge and complex while providing different kinds of services.Testing them is increasingly complicated and resource-intensive. To tackle this issue, we propose a new tool that combines emulation technologies and opti-mization techniques to distribute SDN/NFV experiments in private test-beds and public cloud platforms. Cloud providers, in general, deliver specific metrics to the users in terms of CPU and memory resources for the services they propose, but they tend to give a high-level overview for the network delay, without any specific value. This is a problem when deploying a delay-sensitive applica-tion in the cloud, since the users do not have any precise data about the delay. We propose a testing framework to monitor the network delay between multiple datacenters in the cloud infrastructures. Finally, in the context of SDN/NFVnetworks, we exploit the SDN centralized logic to implement an optimal routingstrategy in case of multiple link failures in the network. We also created a test-bed environment to validate our proposition in different network topologies.

    • Titre: “Emulation fiable et distribuée de réseaux virtualisés et programmables sur bancs de test et infrastructures Cloud”
    • Résumé: De nombreux progrès ont eu lieu ces dernières années dans les domaines de la virtualisation, l’informatique en nuage et la programmation des fonctions réseau. L’essor des concepts tels que Software Defined Networking (SDN) et Network Function Virtualization (NFV) a largement modifié la manière dont les fournisseurs de services Internet gèrent leurs offres. Parallèlement, au cours de la dernière décennie, les plateformes sécurisées de Cloud publiques telles que Amazon AWS ou Microsoft Azure sont devenues des acteurs incontournables de la scène. Ces nouveaux concepts permettent des réductions de coûts et une plus grande rapidité d’innovation, ce qui a conduit à l’adoption de ces paradigmes par l’industrie. Tous ces changements apportent également leur lot de nouveaux défis. Tout en étant devenus tentaculaires et complexes, ces réseaux offrent une plus grande diversité de services: les tester devient ainsi de plus en plus compliqué, tout en nécessitant
      beaucoup de ressources. Pour résoudre ce problème, nous proposons un nouvel outil qui combine les technologies d’émulation et les techniques d’optimisation afin de distribuer les simulations SDN/NFV dans des bancs de test privés et des plateformes de Cloud publiques. Par ailleurs, les fournisseurs de Cloud proposent en général aux utilisateurs des métriques spécifiques en termes de CPU et de ressources mémoire afin de caractériser leurs services, mais ont tendance à présenter une vue d’ensemble de haut niveau du délai maximum engendré par le réseau, sans aucune valeur spécifique. Ceci peut constituer un problème lorsqu’il s’agit de déployer des applications sensibles au délai dans le Cloud, car les utilisateurs n’ont pas de données précises sur ce sujet. Nous proposons un cadre de test pour surveiller le délai engendré par le réseau entre plusieurs centres de données des infrastructures Cloud. Enfin, dans le contexte des réseaux SDN/NFV, nous ex
      ploitons la logique centralisée SDN pour implémenter une stratégie optimale de routage en cas de défaillances multiples des liens dans le réseau. Un environnement de banc de test a également été créé afin de valider nos propositions pour différentes topologies de réseau.

HDR defense of Julien Bensmail

HDR Julien Bensmail

  • Title: A contribution to distinguishing labellings of graphs
  • When: December 15, 2020 — 09:00
  • Where: online with live streaming on Youtube
  • Committee:
  • Manuscript: http://jbensmai.fr/hdr/
  • Abstract: During the talk, I will present some of my contribution to distinguishing labellings of graphs, and the so-called 1-2-3 Conjecture that occupies an important place in this field. The general objective in this kind of problems is, given a (connected undirected) graph, to weight its edges in such a way that the adjacent vertices get distinguishable accordingly to some parameter computed from the edge-weighting. For instance, in the 1-2-3 Conjecture, raised by Karonski, Łuczak and Thomason in 2004, the aim is to weight the edges with 1,2,3 so that adjacent vertices get distinguished accordingly to their sums of incident weights.

    Although the 1-2-3 Conjecture was raised as nothing but a toy problem when it was introduced, several results in the recent years have established its deeper nature. The conjecture, by its very definition, has undoubtedly an algebraic nature. Some results have also established that it has some decompositional flavour. Although the conjecture is rather artificial, it is also related to other classical notions of graph theory, such as proper vertex-colourings of graphs.

    Through the results I will focus on during the talk, my main goal is to point out how deep this field is, and the many aspects of interest that are worth considering.

PhD defense of Fionn Mc Inerney

PhD Fionn Mc Inerney

    • Title: “Domination and Identification Games in Graphs”
    • When: July 8, 2019 — 14:00
    • Where: Inria Sophia Antipolis, Euler violet
    • Committee:
      • Steve Alpern, Warwick Business School, The University of Warwick, Coventry West Midlands, UK
      • Victor Chepoi, Laboratoire d’Informatique et Systèmes, Aix-Marseille Université, Marseille, France
      • Paul Dorbec (Rapporteur), Université de Caen Normandie, Caen, France
      • Sylvain Gravier (Rapporteur), Université Grenoble Alpes, Institut Fourier, Grenoble, France
      • Nicolas Nisse (Directeur), Université Côte d’Azur, Inria, CNRS, I3S, Sophia Antipolis, France
      • Aline Parreau, Laboratoire LIRIS, Université Claude Bernard Lyon 1, Lyon, France
    • Abstract: In this thesis, 2-player games on graphs and their algorithmic and structural aspects are studied. First, we investigate two dynamic dominating set games: the eternal domination game and its generalization, the spy game. In these two games, a team of guards pursue a fast attacker or spy in a graph with the objective of staying close to him eternally and one wants to calculate the eternal domination number (guard number in the spy game) which is the minimum number of guards needed to do this. Secondly, the metric dimension of digraphs and a sequential version of the metric dimension of graphs are then studied. These two problems are those of finding a minimum subset of vertices that uniquely identify all the vertices of the graph by their distances from the vertices in the subset. In particular, in the latter, one can probe a certain number of vertices per turn which return their distances to a hidden target and the goal is to minimize the number of turns in order to ensure locating the target. These games and problems are studied in particular graph classes and their computational complexities are also studied.

      Precisely, the NP-hardness of the spy game and the guard numbers of paths and cycles are first presented. Then, results for the spy game on trees and grids are presented. Notably, we show an equivalence between the fractional variant and the “integral” version of the spy game in trees which allowed us to use Linear Programming to come up with what we believe to be the first exact algorithm using the fractional variant of a game to solve the “integral” version. Asymptotic bounds on the eternal domination number of strong grids are then presented. This is followed by results on the NP-completeness of the Localization game under different conditions (and a variant of it) and the game in trees. Notably, we show that the problem is NP-complete in trees, but despite this, we come up with a polynomial-time (+1)-approximation algorithm in trees. We consider such an approximation to be rare as we are not aware of any other such approximation in games on graphs. Lastly, results on the metric dimension of oriented graphs are presented. In particular, the orientations which maximize the metric dimension are investigated for graphs of bounded degree, tori, and grids.

    • Titre: “Jeux de Domination et d’Identification dans les Graphes”
    • Résumé: Dans cette thèse, les jeux à 2 joueurs dans les graphes et leurs aspects algorithmiques et structurels sont étudiés. Nous explorons tout d’abord le jeu de domination éternelle ainsi que sa généralisation, le jeu de l’espion, deux jeux qui reposent sur les ensembles dominants dynamiques. Dans ces deux jeux, une équipe de gardes poursuit un attaquant ou espion rapide dans un graphe, avec l’objectif de rester près de lui éternellement. Le but est de calculer le nombre de domination éternelle (nombre de gardes pour le jeu de l’espion) qui est le nombre minimum de gardes nécessaires pour réaliser l’objectif. La dimension métrique des digraphes et une version séquentielle de la dimension métrique des graphes sont aussi étudiées. Ces deux problèmes ont pour objectif de trouver un sous-ensemble de sommets de taille minimum tel que tous les sommets du graphe sont identifiés uniquement par leurs distances aux sommets du sous-ensemble. En particulier, dans ce dernier problème, on peut “interroger” un certain nombre de sommets par tour. Les sommets interrogés retournent leurs distances à une cible cachée. Le but est de minimiser le nombre de tours nécessaires pour localiser la cible. Ces jeux et problèmes sont étudiés pour des classes de graphe particulières et leurs complexités temporelles sont aussi étudiées.

      Précisément, il est démontré que le jeu de l’espion est NP-difficile et les nombres de gardes des chemins et des cycles sont présentés. Ensuite, des résultats sur le jeu de l’espion dans les arbres et les grilles sont présentés. Notamment, nous démontrons une équivalence entre la variante fractionnaire et la variante “intégrale” du jeu de l’espion dans les arbres qui nous a permise d’utiliser la programmation linéaire pour concevoir ce que nous pensons être le premier algorithme exact qui utilise la variante fractionnaire d’un jeu pour résoudre sa variante “intégrale”. Des bornes asymptotiques sur le nombre de domination éternelle de la grille du roi sont aussi présentées. Ensuite, des résultats sur la NP-complétude du jeu de Localisation sous différentes conditions (et une variante de ce jeu) sont présentés. Notamment, nous démontrons que le problème est NP-complet dans les arbres. Malgré cela, nous concevons un (+1)-algorithme d’approximation qui résout le problème en temps polynomial. Autant que nous sachions, il n’existe pas d’autres telles approximations pour les jeux dans les graphes. Finalement, des résultats sur la dimension métrique des graphes orientés sont présentés. En particulier, les orientations qui maximisent la dimension métrique sont explorées pour les graphes de degré borné, les tores et les grilles.

PhD defense of Andrea Tomassilli

PhD Andrea Tomassilli

    • Title: “Towards Next Generation Networks with SDN and NFV”
    • When: June 24, 2019 — 14:30
    • Where: Inria Sophia Antipolis, Euler violet
    • Committee:
      • Mathieu Bouet (Referee), Thales, Paris, France
      • Stefano Secci (Referee), Cedric – CNAM, Pairs, France
      • Stéphane Pérennes (Supervisor), COATI, Université Côte d’Azur, CNRS, I3S, Inria, Sophia Antipolis, France
      • Frédéric Giroire (Supervisor), COATI, Université Côte d’Azur, CNRS, I3S, Inria, Sophia Antipolis, France
      • Michele Flammini, Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, Università degli Studi dell’Aquila, L’Aquila, Italy
      • Thierry Turletti, Inria, Sophia Antipolis, France
      • Brigitte Jaumard, Concordia University, Montréal, Québec, Canada
    • Abstract: Recent advances in networks, such as Software Defined Networking (SDN) and Network Function Virtualization (NFV), are changing the way network operators deploy and manage Internet services.
      On one hand, SDN introduces a logically centralized controller with a global view of the network state.
      On the other hand, NFV enables the complete decoupling of network functions from proprietary appliances and runs them as software applications on general–purpose servers. In such a way, network operators can dynamically deploy Virtual Network Functions (VNFs).
      SDN and NFV benefit network operators by providing new opportunities for reducing costs, enhancing network flexibility and scalability, and shortening the time-to-market of new applications and services.
      Moreover, the centralized routing model of SDN jointly with the possibility of instantiating VNFs on–demand, may open the way for an even more efficient operation and resource management of networks. For instance, an SDN/NFV-enabled network may simplify the Service Function Chain (SFC) deployment and provisioning by making the process easier and cheaper.
      In this study, we aim at investigating how to leverage both SDN and NFV in order to exploit their potential benefits.
      We took steps to address the new opportunities offered in terms of network design, network resilience, and energy savings, and the new problems that arise in this new context, such as the optimal network function placement in the network.
      We show that a symbiosis between SDN and NFV can improve network performance and significantly reduce the network’s Capital Expenditure (CapEx) and Operational Expenditure (OpEx).

    • Titre: “Vers les Réseaux de Nouvelle Génération avec SDN et NFV”
    • Résumé: Les progrès récents dans le domaine des réseaux, tels que les réseaux logiciel (SDN) et la virtualisation des fonctions réseaux (NFV), modifient la façon dont les opérateurs de réseaux déploient et gèrent les services Internet.
      D’une part, SDN introduit un contrôleur logiquement centralisé avec une vue globale de l’état du réseau. D’autre part, NFV permet le découplage complet des fonctions réseaux des appareils propriétaires et les exécute en tant qu’applications logicielles sur des serveurs génériques. De cette façon, les opérateurs de réseaux peuvent déployer dynamiquement des fonctions réseaux virtuelles (VNF).
      SDN et NFV, tous deux séparément, offrent aux opérateurs de nouvelles opportunités pour réduire les coûts, améliorer la flexibilité et le passage à l’échelle des réseaux et réduire les délais de mise sur le marché des nouveaux services et applications. De plus, le modèle de routage centralisé du SDN, associé à la possibilité d’instancier les VNF à la demande, peut ouvrir la voie à une gestion encore plus efficace des ressources réseaux. Par exemple, un réseau SDN/NFV peut simplifier le déploiement des chaînes de fonctions de services (SFC) en rendant le processus plus facile et moins coûteux.
      Dans cette thèse, notre objectif était d’examiner comment tirer parti des avantages potentiels de combiner SDN et NVF. En particulier, nous avons étudié les nouvelles possibilités offertes en matière de conception de réseau, de résilience et d’économies d’énergie, ainsi que les nouveaux problèmes qui surgissent dans ce nouveau contexte, comme l’emplacement optimal des fonctions réseaux.
      Nous montrons qu’une symbiose entre le SDN et le NFV peut améliorer la performance des réseaux et réduire considérablement les dépenses d’investissement (CapEx) et les dépenses opérationnelles (OpEx) du réseau.

HDR defense of Frédéric Giroire

HDR Frédéric Giroire

  • Title: “Optimisation des infrastructures réseaux. Un peu de vert dans les réseaux et autres problèmes de placement et de gestion de ressources
  • When: October 23, 2018 — 10:30
  • Where: Room Euler Violet, Inria Sophia Antipolis Méditerranée
  • Committee:
  • Abstract: In this thesis, I present a set of solutions to optimize network infrastructures. Pushed by the new sensitivity of the society, politics, and companies to energy costs and global warming, I investigated the question of how to build green networks. I first studied some practical scenarios to answer the question: how much energy could be saved for Internet Service Providers by putting into practice energy efficient protocols? It led me to study fundamental problems of graph theory.

    At the core of these energy efficient methods, there is a dynamic adaptation to the changes of demands, which is impossible to do in legacy networks which are mostly manually operated. The emergence of two new paradigms, software defined networking (SDN) and network function virtualization (NFV), leads to a finer control of networks and thus bears the promise to to put energy efficient solutions into practice. I thus studied how to use SDN to implement dynamic routing.

    My approach has been to use theoretical tools to solve problems raised by the introduction of new technologies or new applications. My tools come mainly from combinatorics and in particular from graph theory, algorithmics, optimization and probabilities. When I was able to propose new methods of resolution, I then tried to evaluate their practical impact by numerical evaluation, simulation or experimentation with realistic scenarios.

PhD defense of William Lochet

PhD William Lochet

    • Title: “Sub-structures in digraphs”
    • When: July 19, 2018 — 14:00
    • Where: Inria Sophia Antipolis, Euler violet
    • Committee:
    • Abstract: The main purpose of the thesis was to exhibit sufficient conditions on digraphs to find subdivisions of complex structures. While this type of question is pretty well understood in the case of (undirected) graphs, few things are known for the case of directed graphs (also called digraphs). The most notorious conjecture is probably the one due to Mader in 1985. He asked if there exists a function f such that every digraph with minimum outdegree at least f(k) contains a subdivision of the transitive tournament on k vertices. The conjecture is still wide open as even the existence of f(5) remains open. This thesis presents some weakening ofthis conjecture. Among other results, we prove that digraphs with large minimum outdegree contain large in-arborescences. We also prove that digraphs with large minimum outdegree contain large transitive tournaments as immersions, which was conjectured by DeVos et al. in 2011. Changing the parameter, we also prove that large chromatic number can force subdivision of cycles and other structures in strongly connected digraphs.
      This thesis also presents the proof of the Erdős-Sands-Sauer-Woodrow conjecture that states that the domination number of tournaments whose arc set can be partitioned into k transitive digraphs only depends on k. The conjecture, asked in 1982, was still open for k=3.
      Finally this thesis presents proofs for two results, one about orientation of hypergraphs and the other about AVD colouring using the recently developed probabilistic technique of entropy compression.

    • Titre: “Sous-structure dans les digraphes”
    • Résumé: Le but principal de cette thèse est de présenter des conditions suffisantes pour garantir l’existence de subdivisions dans les graphes dirigés. Bien que ce genre de questions soit assez bien maitrisé dans le cas des graphes non orientés, très peu de résultats sont connus sur le sujet des graphes dirigés. La conjecture la plus célèbre du domaine est sans doute celle attribuée à Mader en 1985 qui dit qu’il existe une fonction f tel que tout graphe dirigé de degré sortant minimal supérieur à f(k) contient le tournoi transitif sur k sommets comme subdivision. Cette question est toujours ouverte pour k=5. Cette thèse présente quelques résultats intermédiaires tendant vers cette conjecture. Il y est d’abords question de montrer l’existence de subdivisions de graphes dirigés autre que les tournois, en particulier les arborescences entrantes. Il y a aussi la preuve que les graphes dirigés de grand degré sortant contiennent des immersions de grand tournois transitifs, question qui avait été posée en 2011 par DeVos et al. En regardant un autre paramètre, on montre aussi qu’un grand nombre chromatique permet de forcer des subdivisions de certains cycles orientés, ainsi que d’autre structures, pour des graphes dirigés fortement connexes.
      Cette thèse présente également la preuve de la conjecture de Erdős-Sands-Sauer-Woodrow qui dit que les tournois dont les arcs peuvent être partitionnés en k graphes dirigés transitifs peuvent être dominé par un ensemble de sommet dont la taille dépend uniquement de k.
      Pour finir, cette thèse présente la preuve de deux résultats, un sur l’orientation des hypergraphes et l’autre sur la coloration AVD, utilisant la technique de compression d’entropie.

PhD defense of Nicolas Huin

PhD Nicolas Huin

    • Title: “Energy Efficient Software Defined Networks”
    • When: September 28, 2017 — 14:30
    • Where: Inria Sophia Antipolis, amphi Kahn
    • Committee:
    • Abstract: In the recent years, the growth of the architecture of telecommunication networks has been quickly increasing to keep up with a booming traffic. Moreover, the energy consumption of these infrastructures is becoming a growing issue, both for its economic and ecological impact. Multiple approaches were proposed to reduce the networks’ power consumption such as decreasing the number of active elements. Indeed, networks are designed to handle high traffic, e.g., during the day, but are over-provisioned during the night. In this thesis, we focus on disabling links and routers inside the network while keeping a valid routing. This approach is known as Energy Aware Routing (EAR).

      However current networks are not adapted to support the deployment of network-wide green policies due to their distributed management and the black-box nature of current network devices.The SDN and NFV paradigms bear the promise of bringing green policies to reality.The first one decouples the control and data plane and thus enable a centralized control of the network.The second one proposes to decouple the software and hardware of network functions and allows more flexibility in the creation and management of network services.

      In this thesis, we focus on the challenges brought by these two paradigms for the deployment of EAR policies. We dedicated the first two parts to the SDN paradigm. We first study the forwarding table size constraints due to an increased complexity of rules. We then study the progressive deployment of SDN devices alongside legacy ones. We focus our attention on the NFV paradigm in the last part, and more particularly, we study the Service Function Chaining problem.

      All the publications at the core of this thesis are available online here


PhD Nicolas Huin