Show simple item record

dc.contributor.advisorHanusse, Nicolas
dc.contributor.advisorIlcinkas, David
dc.contributor.authorGLACET, Christian
dc.contributor.otherCoudert, David
dc.contributor.otherGavoille, Cyril
dc.date2013-12-06
dc.date.accessioned2020-12-14T21:12:21Z
dc.date.available2020-12-14T21:12:21Z
dc.identifier.urihttp://ori-oai.u-bordeaux1.fr/pdf/2013/GLACET_CHRISTIAN_2013.pdf
dc.identifier.uri
dc.identifier.urihttps://tel.archives-ouvertes.fr/tel-00951393
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/21950
dc.identifier.nnt2013BOR14960
dc.description.abstractRépondre à des requêtes de routage requiert que les entités du réseau, nommées routeurs, aient une connaissance à jour sur la topologie de celui-ci, cette connaissance est appelée table de routage. Le réseau est modélisé par un graphe dans lequel les noeuds représentent les routeurs, et les arêtes les liens de communication entre ceux ci.Cette thèse s’intéresse au calcul des tables de routage dans un modèle distribué.Dans ce modèle, les calculs sont effectués par un ensemble de processus placés sur les noeuds. Chaque processus a pour objectif de calculer la table de routage du noeud sur lequel il se trouve. Pour effectuer ce calcul les processus doivent communiquer entre eux. Dans des réseaux de grande taille, et dans le cadre d’un calcul distribué, le maintien à jour des tables de routage peut être coûteux en terme de communication. L’un des thèmes principaux abordés et celui de la réduction des coûts de communication lors de ce calcul. L’une des solutions apportées consisteà réduire la taille des tables de routage, permettant ainsi de réduire les coûts de communication. Cette stratégie classique dans le modèle centralisé est connue sous le nom de routage compact. Cette thèse présente notamment un algorithme de routage compact distribué permettant de réduire significativement les coûts de communication dans les réseaux tels que le réseau internet, i.e. le réseau des systèmes autonomes ainsi que dans des réseaux sans-échelle. Ce document contient également une étude expérimentale de différents algorithmes de routage compact distribués.Enfin, les problèmes liés à la dynamique du réseau sont également abordés. Plusprécisément le reste de l’étude porte sur un algorithme auto-stabilisant de calcul d’arbre de plus court chemin, ainsi que sur l’impact de la suppression de noeuds ou d’arêtes sur les tables de routage stockées aux routeurs.
dc.description.abstractEnIn order to respond to routing queries, the entities of the network, nammedrouters, require to have a knowledge concerning the topology of the network, thisknowledge is called routing table. The network is modeled by a graph in whichnodes represent routers and edges represent communication links between nodes.This thesis focuses on routing tables computation in a distributed model. In thismodel, computations are done by a set of process placed on nodes. Every processhas for objective to compute the routing table of the node on which he is placed.To perform this computation, processes have to communicate with each other. Inlarge scale network, in the case of a distributed computation, maintaining routingtables up to date can be costly in terms of communication. This thesis focuses mainlyon the problem of communication cost reduction. One of the solution we proposeis to reduce routing tables size which allow to reduce communication cost. In thecentralised model this strategy is well known under the name of compact routing.This thesis presents in particular a distributed compact routing algorithm that allowsto reduce significantly the communication costs in networks like Internet, i.e. theautonomous systems network and others networks that present scale-free properties.This thesis also contains an experimental study of several distributed compact routingalgorithms. Finally, some problems linked to network dynamicity are addressed.More precisely, the problem of network deconnexion during a shortest path treecomputation with auto-stabilisation guaranties, together with a study of the impactof several edges or nodes deletion on the state of the routing tables.
dc.language.isofr
dc.subjectRoutage compact
dc.subjectCalcul distribué
dc.subjectGraphe
dc.subjectDynamique
dc.subjectCoût de communication
dc.subjectCommunication asynchrone
dc.subject.enCompact routing
dc.subject.enDistributed computing
dc.subject.enGraph
dc.subject.enDynamics
dc.subject.enCommunication cost
dc.subject.enAsynchronous communication
dc.titleAlgorithmes de routage : de la réduction des coûts de communication à la dynamique
dc.title.enRouting algorithms : from communication cost reduction to network dynamics
dc.typeThèses de doctorat
bordeaux.hal.laboratoriesThèses de l'Université de Bordeaux avant 2014*
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.type.institutionBordeaux 1
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2013BOR14960
dc.contributor.rapporteurTixeuil, Sébastien
dc.contributor.rapporteurViennot, Laurent
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Algorithmes%20de%20routage%20:%20de%20la%20r%C3%A9duction%20des%20co%C3%BBts%20de%20communication%20%C3%A0%20la%20dynamique&rft.atitle=Algorithmes%20de%20routage%20:%20de%20la%20r%C3%A9duction%20des%20co%C3%BBts%20de%20communication%20%C3%A0%20la%20dynamique&rft.au=GLACET,%20Christian&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record