- Title: "Study of complex networks properties for the optimization of routing models"
- When: December 9, 2014 -- 10:30
- Where: Conference room of I3S
- Committee:
- Jean-Claude Konig (Referee), LIRMM, Montpellier, France
- Bruno Quoitin (Referee), Univ. Mons, Belgium
- Laurent Viennot (Referee), Inria & LIAFA, Paris France
- David Coudert (supervisor), COATI, Inria/I3S-UNS, France
- Dimitri Papadimitriou, Alcatel-Lucent Bell, Antwerp, Belgium
- Guillaume Urvoy-Keller I3S, Univ. Nice Sophia Antipolis, France
-
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.
