Author: David COUDERT

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.

Best student paper award

, ,

Fatima Zahra Moataz

Fatima Zahra Moataz received the best student paper award of the conference ALGOTEL 2015 for her paper entitled “On Spectrum Assignment in Elastic Optical Tree-Networks“.
 
 

  • Title: “On Spectrum Assignment in Elastic Optical Tree-Networks“
  • Author: Fatima Zahra Moataz
  • Event: ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, June 2015, Beaune, France.

  • Abstract: To face the explosion of the Internet traffic, a new generation of optical networks is being developed; the Elastic optical Networks (EONs). The aim with EONs is to use the optical spectrum efficiently and flexibly. The benefit of the flexibility is accompanied by more difficulty in the resource allocation problems. In this report, we study the problem of Spectrum Allocation in Elastic Optical Tree-Networks. In trees, even though the routing is fixed, the spectrum allocation is NP-hard. We survey the complexity and approximability results that have been established for the SA in trees and prove new results for stars and binary trees.

  • Keywords: Interval coloring; Optical networks; Routing and Spectrum Assignment; Approximation algorithms.

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.

PhD defense of Bi LI

PhD Bi Li

  • Title: “Tree Decompositions and Routing Problems”
  • When: November 12, 2014 — 10:00
  • Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
  • Committee:

  • Abstract: A tree decomposition of a graph is a way to represent it as a tree by preserving some connectivity properties of the initial graph. Tree decompositions have been widely studied for their algorithmic applications, in particular using dynamic programming approach. In this thesis, we study tree decompositions satisfying various constraints and design algorithms to compute them in some graph classes. We then use tree decompositions or specific graph properties to solve several problems related to routing. The thesis is divided into two parts.
    In the first part, we study tree decompositions satisfying some properties. In Chapter 2, we investigate minimum size tree decompositions, i.e., with minimum number of bags. Given a fixed k ≥ 4, we prove it is NP-hard to compute a minimum size decomposition with width at most k in the class of graphs with treewidth at least 4. We design polynomial time algorithms to compute minimum size tree decompositions in some classes of graphs with treewidth at most 3 (including trees). Part of these results will be presented in ICGT 2014.
    In Chapter 3, we study the chordality (longest induced cycle) of graphs and introduce the notion of good tree decomposition (where each bag must satisfy some particular structure). Precisely, we study the Cops and Robber games in graphs with no long induced cycles. Our main result is the design of a polynomial-time algorithm that either returns an induced cycle of length at least k + 1 of a graph G or compute a k-good tree decomposition of G. These results have been published in ICALP 2012 and Algorithmica.
    In the second part of the thesis, we focus on routing problems. In Chapter 4, we design a compact routing scheme that achieves good performance in the class of graphs admitting k-good tree decompositions.
    In Chapter 5, we consider the prize collecting Steiner tree problem (a generalization of the Steiner-tree problem with weighted nodes and edges). We design two risk models of the problem when the weights are given as intervals. In these models, we design polynomial-time algorithms for graphs with small treewidth. These results have been published in AAIM 2010 and the journal Acta Mathematicae Applicatae Sinica.
    Finally, in Chapter 6, we consider the gathering problem in grids and in presence of interferences. We design approximation algorithms (up to small additive constants depending on the interferences) for solving this problem. This work is in revision for TCS.

  • Keywords: Tree Decomposition, Compact Routing Scheme, Prize Collecting Steiner Tree, Gathering.

PhD defense of Ana Karolinna Maia de Oliveira

PhD Ana Karolinna Maia de Oliveira

  • Title: “Subdivisions of Digraphs”
  • When: November 5, 2014 — 10:00
  • Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
  • Committee:

  • Abstract: In this work, we consider the following problem: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We believe that there is a dichotomy between NP-complete and polynomial-time solvable instances of this problem. We present many examples of both cases. In particular, except for five instances, we are able to classify all the digraphs F of order 4. While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, we use different algorithmic tools for proving polynomial-time solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximum-flow calculations, handle decompositions of strongly connected digraphs, among others.
    Finally, we treat the very special case of F being the disjoint union of directed cycles. In particular, we show that the directed cycles of length at least 3 have the Erdos-Pósa Property: for every n, there exists an integer tn such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of tn vertices that meets every directed cycle of length at least 3. From this result, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F.

  • Keywords: Digraphs, subdivisions.