Author: David COUDERT

• Bernardetta Addis, Ecole des mines de Nancy, France
• Edoardo Amaldi (Referee), Politecnico di Milano, Italy
• David Coudert (co-supervisor), COATI, Inria/I3S-UNS, France
• Arie M.C.A. Koster, RWTH Aachen, Germany
• Laurent Lefèvre (Referee), Inria, Lyon, France
• Joanna Moulierac (co-supervisor), COATI, Inria/I3S-UNS, France
• Guillaume Urvoy-Keller, I3S, Univ. Nice Sophia Antipolis, France

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.

• Victor Chepoi, LIF, Aix-Marseille Université
• David Coudert, Inria, Univ. Nice Sophia Antipolis, I3S, CNRS
• Fedor V. Fomin, University of Bergen, Norway
• Pierre Fraigniaud, CNRS, LIAFA, Univ. Paris Diderot
• Cyril Gavoille (Rapporteur), LaBRI, Université de Bordeaux
• Jean-Charles Régin, I3S, Univ. Nice Sophia Antipolis
• Dimitrios M. Thilikos (Rapporteur), CNRS, LIRMM, Univ. Montpellier et Dept. of Maths., Univ. Athens
• Peter Widmayer (Rapporteur), ETH Zurich, Switzerland

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.