PhD defense of Ali Al Zoobi

Ali Al Zoobi

  • Title: “Practical computation of simple paths with length and diversity constraints in complex and multimodal networks”
  • When: November 25, 2021 — 10:30
  • Where: Inria, Euler Violet and live on Youtube (https://youtu.be/M6ypcki8yF4)
  • Committee:
  • Abstract: The shortest path problem is one of the most studied problem in graph theory and operations research. A classic generalization of this problem is the problem of finding k shortest simple paths (kSSP for short). That is, the problem of finding a shortest, a second-shortest, etc. until a k-th shortest simple path from a source to a destination in a directed weighted graph. Yen (1971) proposed the state-of-the-art kSSP algorithm, with theoretical time complexity in \(O(kn(m+n\log{n}))\), where n is the number of vertices and m is the number of arcs of the input digraph. Since then, the problem has been widely studied from an algorithmic engineering perspective, that is designing exact algorithms offering better performances in practice.

    In this thesis, we study the kSSP problem from an algorithm engineering perspective. More precisely, we design new kSSP algorithms allowing to outperform the state-of-the-art algorithms in terms of running time, memory consumption, or offering a better space-time trade-off. We also show how to apply our algorithms in graphs with arbitrary arc weights without negative cycles.
    Then, we study the problem of finding paths respecting dissimilarity constraints. Precisely, we study the complexity of the problem according to four different similarity measures, and we show in which cases the problem is NP-Complete or polynomial time solvable.
    Finally, we show how to adapt the kSSP problem to a multimodal public transportation network model, i.e., combining metro, tram, buses, and walk. Precisely, we design some kSSP algorithms to solve a related problem, which is, the problem of finding k earliest arrival journeys from a source station to a destination station in a public multimodal transportation network.

  • Titre: “Calcul pratique de chemins simples avec des contraintes de longueur et de diversité dans des réseaux complexes et multimodaux”
  • Résumé: Le problème du plus court chemin est l’un des problèmes les plus étudiés en théorie des graphes et en recherche opérationnelle. Une généralisation classique de ce problème est le problème de trouver k plus courts chemins simples (kSSP). C’est-à-dire, le problème de trouver le plus court, le deuxième plus court, etc. jusqu’au k-ième plus court chemin simple d’une source à une destination dans un graphe orienté pondéré. Yen (1971) a proposé l’algorithme avec la meilleure complexité théorique connue pour résoudre le kSSP dans un graphe orienté pondéré à n sommets et m arcs, avec une complexité en \(O(kn(m+n\log{n}))\). Depuis, le problème a été largement étudié du point de vue de l’ingénierie algorithmique.

    Dans cette thèse, nous étudions également le problème kSSP sous cet angle, c’est-à-dire que nous proposons des algorithmes exacts offrant de meilleures performances en pratique que l’état de l’art, en termes de temps d’exécution, de consommation mémoire ou offrant de meilleurs compromis espace-temps. Nous montrons aussi comment étendre nos algorithmes au cas des graphes avec des poids arbitraires sans cycles négatifs.
    De plus, nous étudions le problème de trouver k plus courts chemins simples qui sont mutuellement dissimilaires. Plus précisément, nous étudions la complexité du problème en fonction de quatre mesures de similarité différentes, et nous montrons dans quels cas le problème est NP-Complet ou peut être résolu en temps polynomial.
    Enfin, nous montrons comment adapter le problème kSSP à un modèle de réseau de transport public multimodal. Nous adaptons certains de nos algorithmes pour le kSSP au problème de trouver, dans un réseau de transport public multimodal, les k itinéraires d’une station source et à une station destination arrivant au plus tôt.

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.

New team member: Chuan Xu

Chuan Xu

Welcome to our new team member: Chuan Xu.

Chuan Xu received her PhD in Computer Science, titled ‘Power-Aware Protocols for Wireless Sensor Networks’, from University of Paris Saclay in Dec. 2017. After three years of postdocs in project-team NEO, at Inria Sophia Antipolis Méditerranée and Nokia (2018-2021), she joined Université Côte d’Azur (UCA) as an associate professor (“maître de conférences”) in Sept. 2021 and became a member of the I3S laboratory and of project-team COATI. Her main research interests are distributed machine learning, federated learning, population protocols, self-stabilizing distributed algorithms, energy problems in mobile wireless sensor networks and chance constrained program (stochastic optimization).

C@fé-in par Nicolas Nisse: Jouons un peu sur un échiquier (sans jouer aux échecs)

C@fé-in Nicolas Nisse

  • Quand: 8 juillet 2021 à 13h, en replay sur https://www.youtube.com/watch?v=uOW3HpsTuGY.
  • Intrigue: Dans ce Café-in, vous allez apprendre deux jeux/énigmes amusant(e)s (j’espère) auxquels vous pourrez jouer avec vos familles et amis.
    1. Etant donné un échiquier, sauriez vous couvrir toutes ses cases à l’aide de dominos, exceptées celles de deux coins opposés ?
    2. Considérons un échiquier classique (8 cases par 8) dont chaque case peut être soit saine soit infectée. Supposez que, si au moins 2 des 4 voisins d’une case infectée sont saines, alors la case infectée devient saine. Quel est le nombre minimum de cases qui doivent être saines initialement pour éradiquer complètement l’infection de l’échiquier ? Vous pouvez tester ce jeu ici : https://scratch.mit.edu/projects/517390361/

    A travers ces jeux, nous discuterons de questions importantes dans le travail des chercheurs comme « y a t-il une solution ? », « combien y a-t-il de solutions ? », « est-ce que cette solution est optimale ? » … Précisément, je répondrai à ces questions dans le cas des deux jeux proposés en présentant de très belles preuves de la littérature (oui, des preuves peuvent être « belles »: élégantes et simples). Pour finir, je présenterai une généralisation du second problème et montrerai brièvement ses relations avec le jeu de la vie de John Conway qui, malgré des règles très simples, permet de simuler n’importe quel ordinateur.

  • Biographie: Nicolas Nisse est CR Inria dans l’équipe COATI. Ses sujets de recherche portent sur l’algorithmique des graphes avec des applications dans les réseaux de télécommunication, routiers, sociaux… En particulier, son travail s’appuie sur la théorie des jeux combinatoires dans les graphes. Nicolas Nisse est ingénieur Supélec, a effectué sa thèse à l’université Paris-Sud 11 puis un postdoc à l’université du Chili (Santiago, Chili) et un postdoc dans l’équipe Mascotte (devenue COATI). Il est également membre de Terra Numerica.
  • En savoir plus sur MASTIC et C@fé-in.

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.