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.

PhD defense of Truong Khoa Phan

PhD Truong Khoa Phan

  • Title: “Design and Management of Networks with Low Power Consumption”
  • When: September 25, 2014 — 10:00
  • Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
  • Committee:
  • Abstract: In this thesis, we study several models of energy-aware routing. For each model, we present a linear programming formulation to find the exact solution. Moreover, since energy-aware routing is NP-hard problem, we also propose efficient heuristic algorithms for large scale networks.
    In the first part of this thesis, we deal with GreenRE – a new energy-aware routing model with the support of redundancy elimination. We first present a deterministic model in which we show how to combine energy-aware routing and redundancy elimination to improve energy efficiency for backbone networks. Then, we extend the model in order to take into account uncertainties in traffic volumes and redundancy rates.
    The second part of this thesis is devoted to the deployment issues of energy- aware routing in practice. In detail, to avoid service deterioration for end-users, we limit the changes in network configurations in multi-period traffic matrices in Open Shortest Path First (OSPF) protocol. Next, we address the problem of limited rule space in OpenFlow switches when installing energy-aware routing configurations.
    Finally, we present in the appendix other works developed during this thesis: multicast network protocol and TCP congestion control algorithm.

  • Keywords: Energy-aware Routing, Redundancy Elimination, Open Shortest Path First, Software Defined Networks.

HDR defense of Nicolas Nisse

HDR Nicolas Nisse

  • Title: “Algorithmic complexity, Between Structure and Knowledge: How Pursuit-evasion Games help”
  • When: May 26, 2014 — 14:30
  • Where: Room Euler Violet, Inria Sophia Antipolis Méditerranée
  • Committee:
  • Abstract: This manuscript describes the work I did since I obtained my Ph.D. in 2007. In addition to the presentation of my contributions, I tried to give overviews of the scientific areas my work takes part of and some of the main issues that arise here.
    My work deals with new algorithmic challenges posed by the growth of nowadays networks and by the increased data and traffic arising in it. One way to cope with the size of these problems is to use the particular network structures. For this, I strive to develop new characterizations of graph structural properties in order to calculate and use them efficiently for an algorithmic perspective. Whenever possible, I propose distributed algorithms
    that are based only on a local/partial knowledge of networks.
    In particular, I study the Pursuit-Evasion games – dealing with the capture of a mobile entity by a team of other agents – that offer an interesting perspective on many properties of graphs and, in particular, decompositions of graphs. This approach from mobile agents point of view also allows the study of various applications in telecommunication networks and of some distributed computing models.
    Chapter 1 is dedicated to the study of several variants of turn-by-turn Pursuit-Evasion Games, mostly to the Cops and Robber games. Chapter 2 focuses on graph decompositions and their relationship with graph searching. Chapter 3 treats another aspect of Pursuit-Evasion games with a study of variants of Graph Searching games, both in centralized and distributed settings. Finally, Chapter 4 deals with routing problems in various environments and with distributed models of computation.