Tag: PhD & HDR

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

PhD defense of Guillaume Ducoffe

PhD Guillaume Ducoffe

  • Title: “Metric properties of large graphs”
  • When: December 9, 2016 — 14:30
  • Where: Inria Sophia Antipolis, amphi Kahn
  • Committee:

  • Abstract: Large scale communication networks are everywhere, ranging from data centers with millions of servers to social networks with billions of users. This thesis is devoted to the fine-grained complexity analysis of combinatorial problems on these networks.

    In the first part, we focus on the embeddability of communication networks to tree topologies. This property has been shown to be crucial in the understanding of some aspects of network traffic (such as congestion). More precisely, we study the computational complexity of Gromov hyperbolicity and of tree decomposition parameters in graphs – including treelength and treebreadth. On the way, we give new bounds on these parameters in several graph classes of interest, some of them being used in the design of data center interconnection networks. The main result in this part is a relationship between treelength and treewidth: another well-studied graph parameter, that gives a unifying view of treelikeness in graphs and has algorithmic applications. This part borrows from graph theory and recent techniques in complexity theory.

    The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analyzing information flows in these networks, represented as dynamical processes on graphs. First, a coloring game on graphs is studied as a solution concept for the dynamic of communities. We give a fine-grained complexity analysis for computing Nash and strong Nash equilibria in this game, thereby answering open questions from the literature. On the way, we propose new directions in algorithmic game theory and parallel complexity, using coloring games as a case example. Finally, we introduce a new learning problem that is motivated by the need for users to uncover any misuse of their personal data online. We give positive and negative results on the tractability of this problem.

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

  • Keywords: Graph theory, Hyperbolicity, tree-decomposition, complexity, privacy.

  • Manuscript: Core of the thesis, appendix, all in one file
  • Slides of the presentation

PhD defense of Fatima Zahra Moataz

PhD Fatima Zahra Moataz

  • Title: “Towards Efficient and Fault-Tolerant Optical Networks: Complexity and Algorithms”
  • When: October 30, 2015 — 14:30
  • Where: Inria Sophia Antipolis, salle Euler Violet
  • Committee:

  • Abstract: We study in this thesis optimization problems with application in optical networks. The problems we consider are related to fault-tolerance and efficient resource allocation and the results we obtain are mainly related to the computational complexity of these problems.
    The first part of this thesis is devoted to finding paths and disjoint paths. Finding a path is crucial in all types of networks in order to set up connections and finding disjoint paths is a common approach used to provide some degree of protection against failures in networks. We study these problems under different settings. We first focus on finding paths and vertex or link-disjoint paths in networks with asymmetric nodes, which are nodes with restrictions on their internal connectivity. Afterwards, we consider networks with star Shared Risk Link Groups (SRLGs) which are groups of links that might fail simultaneously due to a localized event. In these networks, we investigate the problem of finding SRLG-disjoint paths.
    The second part of this thesis focuses on the problem of Routing and Spectrum Assignment (RSA) in Elastic Optical Networks (EONs). EONs are proposed as the new generation of optical networks and they aim at an efficient and flexible use of the optical resources. RSA is the key problem in EONs and it deals with allocating resources to requests under multiple constraints. We first study the static version of RSA in tree networks. Afterwards, we examine a dynamic version of RSA in which a non-disruptive spectrum defragmentation technique is used.
    Finally, we present in the appendix another problem that has been studied during this thesis. It is a graph-theoretic problem referred to as minimum size tree-decomposition and it deals with the decomposition of graphs in a tree-like manner with the objective of minimizing the size of the tree.

  • Keywords: Asymmetric nodes, forbidden transitions, shared risk link group, routing and spectrum assignment, tree-decomposition, complexity.

PhD defense of Mohamed Bergach

PhD Mohamed Bergach

  • Title: “Adaptation of the Fast Fourier Transform processing on hybride integrated CPU/GPU architecture”
  • When: October 2, 2015 — 10:30
  • Where: Inria Sophia Antipolis, salle Euler Violet
  • Committee:

  • Abstract: Multicore architectures Intel Core (IvyBridge, Haswell, etc.) contain both general purpose CPU cores (4) and dedicated GPU cores embedded on the same chip (16 and 40 respectively). As part of the activity of Kontron (the company partially funding this CIFRE scholarship), an important objective is to efficiently compute arrays and sequences of fast Fourier transforms (FFT) such as one finds in radar applications, on this architecture. While native (but proprietary) libraries exist for Intel CPU, nothing is currently available for the GPU part.
    The aim of the thesis was to define the efficient placement of FFT modules, and to study theoretically the optimal form for grouping computing stages of such FFT according to data locality on a single computing core. This choice should allow processing efficiency, by adjusting the memory size available to the required application data size.
    Then the multiplicity of cores is exploitable to compute several FFT in parallel, without interference (except for possible bus contention between the CPU and the GPU). We have achieved significant results, both in the implementation of an FFT (1024 points) on a SIMD CPU core, expressed in C, and in the implementation of a FFT of the same size on a GPU SIMT core, then expressed in OpenCL.
    In addition, our results allow to define rules to automatically synthesize such solutions, based solely on the size of the FFT (more specifically its number of stages), and the size of the local memory for a given computing core. The performances obtained are better than the native Intel library for CPU, and demonstrate a significant gain in consumption on GPU. All these points are detailed in the thesis document.
    These results should lead to exploitation of the code as library by the Kontron company.

  • Keywords: FFT, GPU, multicores.

PhD defense of Alvinice Kodjo

PhD Alvinice Kodjo

  • Title: “Design and Optimization of Wireless Backhaul Networks”
  • When: December 18, 2014 — 14:30
  • Where: Polytech-Nice Sophia Antipolis, salle E+131 (Amphi Gradiné Templiers 2)
  • Committee:

  • Abstract: The main work of this thesis focuses on the wireless backhaul networks. This type of network has the advantage of allowing rapid and easy deployment at relatively low costs while offering capacity of up to 1Gbps over links of a hundred of kilometers. We studied different optimization problems in such networks that represent real challenges for industrial sector.
    The first issue addressed in this thesis concerns the capacity allocation on the links at minimum cost. It was solved by a linear programming approach with column generation. Our method solves the problems on large size networks. In addition, we quickly obtain very good quality solutions.
    We then studied the problem of network infrastructure sharing between virtual operators. The objective is to maximize the revenue of the operator of the physical infrastructure while satisfying the demands (constraints of quality of service) of virtual operators customers of the network. In this context, we proposed a model to the problem using mixed integer linear programming. Our formulation is robust to changes in traffic demands of virtual operators.
    Another operational expenditure in this type of network is the energy consumption. Many operators are now seeking to reduce network energy consumption, both by using more efficient equipments and by using more appropriate routing solutions. We proposed a robust energy-aware routing solution for the network. The proposed model is based on backbone networks, but it can easily be adapted to wireless back- haul networks. Our solution was formulated using a mixed integer linear program. We also proposed heuristics to find efficient solutions for large networks.
    The last work of this thesis focuses on cognitive radio networks and more specifically on the problem of bandwidth sharing. We formalized it using a linear program with a different approach to robust optimization. This model differs from other cases of robust optimization discussed above by the position of the uncertain terms in the model. We based our solution on the 2-stage linear robust formulation proposed by Michel Minoux.
    This thesis was carried out in partnership with the SME 3ROAM (http://www.3roam.com) and in collaboration with various researchers from different universities in the world. It was co-funded by the PACA province and the SME 3ROAM.

  • Keywords: Backhaul networks, Wireless networks, Operations Research, Robust optimization.

PhD defense of Aurélien Lancin

  • Title: "Study of complex networks properties for the optimization of routing models"
  • When: December 9, 2014 -- 10:30
  • Where: Conference room of I3S
  • Committee:

  • Abstract:This thesis considers routing issues in networks, and particularly the graph of the autonomous systems (AS) of the Internet. Firstly, we aim at better understanding the properties of the Internet that are useful in the design of new routing paradigms. Secondly, we want to evaluate by simulation the performance of these paradigms. The first part of my work concerns the study of the Gromov hyperbolicity, a useful metric property for the design of new routing paradigms. I show how to use a decomposition of the graph by clique-separators as a pre-processing method for the computation of the hyperbolicity. Then, I propose a new algorithm to compute this property. Altogether, these methods allows us for computing the hyperbolicity of graphs up to 58 000 nodes. The second part of my work concerns the development of DRMSim, a new Dynamic Routing Model Simulator. It facilitates the evaluation of the performances of various routing schemes and their comparison to the standard routing scheme of the Internet, the border router protocol BGP. Using DRMSim, we performed simulations of several compact routing schemes on topologies up to O(10k) nodes. I describe its architecture and detail some examples. Then, I present a feasibility study for the design of a parallel/distributed version of DRMSim in order to simulate BGP on larger topologies.

  • Keywords:Internet, Algorithm, Graph, Hyperbolicity, Graph decomposition, Routing, BGP, Simulation, Parallel Distributed Simulation.