Presentation material
This page provides presentation material used for the dissemination of project results during seminars or conferences
- Dimitri Papadimitriou and Bernard Sales, "A path towards strong architectural foundation for the internet design", 2nd ETSI Workshop on Future Network Technologies, Sophia Antipolis, France, September 26-27, 2011.
- Adrian Kosowski, Bi Li, Nicolas Nisse and Karol Suchan, "k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth", Slides
- 39th International Colloquium on Automata, Languages and Programming (ICALP, track C), Warwick, UK, July 2012. by Bi Li
- 14es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), La Grande Motte, France, June 2012. by Nicolas Nisse
- Seminar, Universidad Adolfo Ibanez, Santiago, Chile, August 2012. by Nicolas Nisse
abstract: Cops and robber games concern a team of cops that must capture a robber moving in a graph. We consider the class of k-chordal graphs, i.e., graphs with no induced cycle of length greater than k>2. We prove that k-1 cops are always sufficient to capture a robber in k-chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including k-chordal graphs. We present a quadratic algorithm that, given a graph G and k>2, either returns an induced cycle larger thank k in G, or computes a tree-decomposition of G, each bag of which contains a dominating path with at most k-1 vertices. This allows us to prove that any k-chordal graph with maximum degree D has treewidth at most (k-1)(D-1)+2, improving the O(D(D-1)^{k-3}) bound of Bodlaender and Thilikos (1997). Moreover, any graph admitting such a tree-decomposition has hyperbolicity at most 3k/2. As an application, for any n-node graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(log n) bits and achieving an additive stretch of O(k log D). As far as we know, this is the first routing scheme with O(log n)-routing tables and small additive stretch for k-chordal graphs.
- David Coudert, Aurélien Lancin, Dimitri Papadimitriou, Stéphane Pérennes and Issam Tahiri, "Feasibility Study on Distributed Simulations of BGP", 6th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation (PADS), Zhangjiajie, China, July 2012. by Aurélien Lancin.
abstract: The Autonomous System (AS) topology of the Internet (up to 61k ASs) is growing at a rate of about 10\% per year. The Border Gateway Protocol (BGP) starts to show its limits in terms of the number of routing table entries it can dynamically process and control. Due to the increasing routing information processing and storage, the same trend is observed for routing model simulators such as DRMSim specialized in large-scale simulations of routing models. Therefore, DRMSim needs enhancements to support the current size of the Internet topology and its evolution (up to 100k ASs). To this end, this paper proposes a feasibility study of the extension of DRMSim so as to support the Distributed Parallel Discrete Event paradigm. We first detail the possible distribution models and their associated communication overhead. Then, we analyze this overhead by executing BGP on a partitioned topology according to different scenarios. Finally, we conclude on the feasibility of such a simulator by computing the expected additional time required by a distributed simulation of BGP compared to its sequential simulation.