My Research Interests

Mes Intérêts de Recherche

Ma Thèse, Thématiques Principales

Algorithmes de routage, de la réduction des coûts de communication à la dynamique.

PhD Thesis and Main Subjects

Routing algorithms, from the reduction of communication cost to dynamics.

Ma thèse porte principalement sur la thématique du routage et plus précisement sur le routage compact. Les algorithmes de routage compact sont caractérisés par la petite taille des tables de routage utilisées pour prendre les décisions lors du transfert d'un packet. Classiquement les tables de routage sont de taille $O(n)$, les algorithmes de routage compacts comme [AGMNT] ou [TZ] utilisent quant à eux des tables de taille $O(\sqrt{n})$. Il existe de nombreux algorithmes centralisés de calcul de tables de routage compactes, cependant il n'existe à ce jour aucun algorithme distribué garantissant un étirement borné et utilisant une mémoire de travail sous-linéaire.

The work presented in my thesis is mainly about routing and more precisely it studies compact routing. The goal of a compact routing algorithm is to use small routing tables to achieve routing task. The naive routing algorithm, say shortest path algorithm is based on routing tables of linear size $O(n)$, with $n$ the size of the network. It is well known that any shortest path algorithm require at least $\Omega(n)$ routing entries by node on some graph famillies. However it exists some centralised compact routing algorithms that guaranty that any node has routing table of size $O(\sqrt{n})$. Algorithms such that [AGMNT] or [TZ]. The main unanswered question is the following : it is possible to use compact routing techniques in distributed models in order to reduce the amount of communication required to ensure that routing is available for any source node and any destination ? Nowadays, no algorithm ensure constant stretch routing with sub-quadratic communication cost (bit-complexity, the number of bits exchanged among distributed processes ).

La principale contribution présentée dans ma thèse répond à cette problématique. Le détail des caractéristiques de l'algorithme proposé est également donné dans une version résumée proposée à Algotel'13 [GGHI13a] ou encore dans une version un peu plus détaillée dans un article publié à DISC'13 [GGHI13b].

The main contribution of my thesis is to provide such an algorithm. We call that new algorithm DCR, for Distributed Compact Routing. DCR provides routes with stretch at most 5 with routing tables of size $O(\sqrt{n} \log n)$ and communication cost of $O(n^{3/2}\log n)$ for graphs of small diameter. A short resume of this algorithm is available in a paper published at DISC'13 [GGHI13b].


Le manuscrit de ma thèse est disponible sur la bibliothèque en ligne de l'université de Bordeaux [pdf] et en local [pdf]. Les slides utilisées lors de ma soutenance sont également disponible [pdf].

My PhD thesis manuscript is available at the online library of the university of Bordeaux [pdf], there is also a local version [pdf]. The slides used during my defense are available too [pdf].

Thématiques Secondaires

Les sujets connexes au calcul distribué ou au routage

Secondary Subjects

Subjecs related to routing on which I worked

Co-auteurs

Pages personnelles des co-auteurs

Co-authors

Personal web pages of my co-authors

Publications

Disconnected components detection and rooted shortest-path tree maintenance in networks

SSS'14 ( site de la conférence conference website ). Glacet Christian, Hanusse Nicolas, Ilcinkas David, Johnen Colette.

afficher l'abstractdisplay abstract [GHIJ14]

On the Communication Complexity of Distributed Name-Independent Routing Schemes

DISC'13 ( site de la conférence conference website ). Gavoille Cyril, Glacet Christian, Hanusse Nicolas, Ilcinkas David.

afficher l'abstractdisplay abstract [GGHI13b]

Algorithme Distribué de Routage Compact en Temps Optimal

ALGOTEL'13 ( site de la conférence conference website ). Gavoille Cyril, Glacet Christian, Hanusse Nicolas, Ilcinkas David.

afficher l'abstractdisplay abstract [GGHI13a]

Vers un Routage Compact Distribué

ALGOTEL'12 ( site de la conférence conference website ). Glacet Christian et Verdonk Lucas.

afficher l'abstractdisplay abstract [GV12]

Impact de la Dynamique sur le Nombre d'Erreurs dans un Réseau

OPODIS'11 ( site de la conférence conference website ). (Glacet Christian, Hanusse Nicolas, Ilcinkas David)

afficher l'abstractdisplay abstract [GHI11]

Expèriences d'Enseignement

Teachings positions

Voici un petit résumé des enseignement dispensés à l'IUT d'informatique et à l'UFR Mathématiques et Informatique de Bordeaux 1. Here is a small resume of my teachings at the university of Bordeaux and at the IUT of computer sience.

Algorithmique et Programmation

Algorithmics and Programation basis

2011 - IUT Bordeaux (64h)

Cours d'introduction à l'algorithmique et à la programmation, les étudiants sont formés sur la notion de type de donnée et de fonctions. Des techniques de programmation sont également rapidement abordées, notamment les fonction récursives. D'un point de vue technique, lors des TP le langage utilisé est le C++, cette formation comprend également une partie de cours plus orienté système (gestion de flux, compilation, gestion de la mémoire, débogage, etc.). This course is an introduction to programming : typing, functions, arrays and pointers, it is taught at the very beginning of the formation, thus it is a first and therefore important step in computer science field. The goal is obviously to introduce the notion of Algorithm, how to express a solution in a formal manner. It also introduce some programming techniques such as recursive functions.

Référent Referent Nicholas Journet

Utilisation des Systèmes UNIX

Using UNIX Systems

2012 - IUT Bordeaux (48h)

Ce cours se présente en deux parties, d'abord articulé autour de la gestion son espace de travail (manipulation d'une arborescence de fichier, archivage, etc.). La suite du cours est plus orienté traitement de fichier via l'utilisation de scripts en bash. L'objectif de cette seconde partie est de permettre aux étudiants d'analyser des logs de données volumineux de façon automatisée. This course contains two parts, first we go through the basis of unix system usage, so students can work efficiently on this (sometimes) new OS. This part is made to learn how to use the file system, how to go through it, archive things and also how to manage distant files via ssh or ftp (how to work from home in some sense). Secondly we study scripts (bash), mainly file reading and parsing in order to automate tasks done frequently.

Référent Referent Michel Billaud

Devoir surveillé proposé aux étudiants ici.

Test made by me (french) here.

Architecture Système

System Architecture

2013 - IUT Bordeaux (16h)

L'objectif de ce cours est d'enseigner les implémentations bas niveau (langage machine) des mécanismes plus haut niveaux (gestion de tableaux, expressions conditionnelles et boucles, etc. ) ainsi que la gestion de la mémoire (pile et tas, données dynamique vs. statiques, etc.). L'objectif à terme étant de préparer les étudiants à faire des analyse plus précises d'algorithmes (calculs de complexité, choix de structures de donnés, etc.) et également à mieux comprendre le fonctionnement d'un microprocesseur. This course is about computers system architecture, we study mainly ALU (which is the circuit that performs arithmetic), more generally CPU, memory management (heap, stack, pointers, indexed access). The course also contains some initiation to assembly programming and to some standard optimization such as branching optimization.

Référent Referent Eric Woirgard

Devoirs surveillés proposés aux étudiants version 1 puis en rattrapage version 2.

Tests made by me : version 1 ; and for those who wanted to re-take the exam version 2.

Architecture Système

System Architecture

2014 - Université de Bordeaux (2*48h)

Le contenu et les objectifs de ce cours sont très proches de ceux du cours d'architecture donné à l'IUT. La différence se fait notamment sur le type de microprocesseurs utilisés comme exemple. À l'IUT l'architecture PowerPc est utilisée ici c'est l'architecture Y86. Ce cours est entre également un peu plus dans les détails, plus précisement, nous abordons des sujets tels que la construction d'une architecture moderne depuis le niveau logique (portes) jusqu'au micro-processeur pipeliné. Le cours aborde également des notions d'optimisations telles que les additions avec anticipation de retenues. This curse as more or less the same content as the IUT course, it just goes into more details. This course is based on «Computer Systems: A Programmer's Perspective» by Randal E. Bryant and David R. O'Hallaron and «Computer Architecture : a Quantitative Approach» by J. Hennessy and D. Patterson. The most important difference with the previous course I taught is that we study how to build a pipelined processor, from logical gates to a simple, but complete, pipelined CPU. We even go to further technical details such as performing arithmetic operations efficiently (Carry-lookahead adders).

Référent Referent François Pellegrini

Supports de cours ici

Examens ici

Teaching materials can be found here

Tests can be found here

Christian Glacet