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.

DRMSim: A Routing-Model Simulator for Large-Scale Networks

, ,

DRMSim architecture

by: Aurélien Lancin (COATI) and Dimitri Papadimitriou (Alcatel-Lucent Bell labs)
In ERCIM news 94, pp 31-32, July 2013

The expansion of Internet topology, which comprises thousands of Autonomous Systems (AS), has resulted in a number of important research challenges. The Border Gateway Protocol (BGP), which is used to make core routing decisions on the Internet, starts to show its limitations in terms of the number of routing table entries it can store locally, update in a timely fashion and dynamically exchange. Because it is impractical to deploy newly designed routing protocols on the Internet a large-scale, simulation is an unavoidable step to validate their properties. However, the increasing routing information processing (CPU) and storage (memory) introduces similar challenges for the simulation of state-full routing. For this purpose, we introduce DRMSim a Dynamic Routing Model simulator of routing models on large-scale networks. (read more)

http://drmsim.gforge.inria.fr