Search

In this paper, we investigate the efficiency of local search algorithms for some relatively unstructured networks. By local search, we mean that each vertex has a knowledge of its very close neighborhood, typically the identities, degrees and possibly the contents. Assuming there is no preprocessing step, we are interested in seeking a vertex of a given identity starting from any vertex. The time complexity of search is expressed as the number of vertices to explore before reaching the target or a neighbor of the target. For an arbitrary graph and a worst-case labelling of vertices, time complexity can be of the same order as the size of the graph itself. However, there is some hope that for large classes of graphs, the size of the exploration sequence would drastically decrease. Recent literature exhibits non trivial properties shared by the topologies of numerous real-world distributed networks: the combination of a low diameter, a specific degree distribution of the vertices and a sparse network are typically representative of a small-world topology. On the other hand, in a seminal paper, Kleinberg [Kle00] focuses on the ability of a user or a mobile agent to route along shorts paths within a class of random small-world graphs, the navigable small-worlds† using a greedy distributed algorithm (distances within a spanning subgraph are known or can be computed locally). Under some conditions, Kleinberg also proposes polynomial lower bounds valid for any distributed algorithm using the same knowledge of the network even if the diameter is polylogarithmic. However, Kleinberg’s model lacks an important property observed in real networks which are often scalefree. The degree distribution of the vertices tends to follow a power-law distribution, that is the number of vertices of degree δ is proportional to n ( 1 δ )k for an n-vertex graph and k a constant strictly greater than one. Moreover, it has been observed that for real-life networks, k tends to belong to the range [2,3]. For graphs built using Kleinberg’s model, the degree distribution is very different (close to a Poisson distribution). All local‡ distributed search algorithms presented in the literature work as follows: given the set of visited vertices, one should choose the next vertex to explore. The process stops as soon as the target is reached. In this paper, the underlying network is a random scale-free labeled graph whose node identities belong to the range [1,n]. Each vertex knows its own identity and its degree and we assume two models of local knowledge: some information about the neighbors can be known (strong model) or not (weak model). The first model is the more realistic one but our starting point is the second model. Note that Kleinberg’s model assumes more information than our strong model. Up to now, it is still an open problem to know if scale-free graphs are navigable in the polylogarithmic sense. In this paper, we answer negatively to this question for some random scale-free graphs built using a

Pulse est un protocole de streaming live, basé sur un réseau décentralisé non-structuré, qui a été testé avec succès sur simulateur, Grid'5000 et PlanetLab. Dans ce papier, nous étudions les arbres de diffusion de Pulse et montrons qu'ils ont des caractéristiques proches des arbres construits à l'aide de réseaux structurés. Nous étudions également le délai de réception d'un stream diffusé par PULSE, et montrons qu'il est comparable à celui de réseaux structurés.

National audience; Nous présentons un algorithme autostabilisant qui construit et entretient une table de hachage distribuée dans un environnement pair à pair. L'utilisation d'un modèle dans lequel les processus ne connaissent pas leurs voisins a priori le rend utilisable sur des systèmes à grande échelle. Ses performances en nombre de messages sont de l'ordre des références du domaine (notamment Chord), la réplication des données est également assurée. La base sur lequel il est construit permet d'en donner une preuve formelle de correction.

National audience; Dans le cadre de l'algorithmique réparti dans les réseaux, l'efficacité d'un algorithme dépend très fortement de la connaissance du réseau, disponible a priori. Très souvent, cette connaissance a priori est de nature qualitative (taille du réseau, son diamètre, etc.). Fraigniaud et al. (2006) ont introduit une mesure quantitative de la complexité d'une tâche répartie dans un réseau. Etant donné un problème réparti, cette mesure, la taille d'oracle, consiste en le plus petit nombre de bits d'information dont doit disposer l'algorithme pour résoudre le problème efficacement. Nous nous intéressons à la taille d'oracle permettant de résoudre efficacement l'encerclement dans les graphes. L'encerclement dans les réseaux vise à réaliser la capture d'un fugitif invisible, arbitrairement rapide et omniscient, par une équipe d'agents mobiles, dans un réseau. La stratégie d'encerclement est calculée en temps réel, par les agents eux mêmes, et doit vérifier les trois propriétés suivantes: (1) connexité : la zone nettoyée doit toujours être connexe, (2) monotonie : la zone nettoyée ne doit jamais être recontaminée, et (3) optimalité : le nombre d'agents utilisés doit être le plus petit possible. Les deux premières contraintes assurent des communications sécurisées entre les agents, ainsi qu'un temps de nettoyage polynomial en la taille du réseau. La troisième propriété assure une taille minimum des ressources utilisées. La seule connaissance, concernant le réseau, dont les agents disposent a priori, est modélisée par un oracle qui répartit sur les noeuds du réseau une chaÎne de bits d'information. Nous prouvons que la taille d'oracle pour résoudre l'encerclement est O(n log n) bits, avec n la taille du réseau, et que cette borne est optimale. Plus précisément, nous proposons un étiquetage des sommets, de taille O(n log n) bits, et un protocole réparti utilisant cet étiquetage. Ce protocole permet à une équipe d'agents, dont la mémoire est de taille O(log n) bits, de nettoyer le réseau de façon optimale monotone et connexe. Ce protocole améliore le protocole proposé par Blin et al. (2006) qui ne dispose d'aucune information a priori et, de ce fait, nécessite un temps de nettoyage exponentiel. De plus, nous prouvons qu'il n'existe pas de protocole réparti utilisant un oracle de taille o(n log n) bits qui permette de nettoyer tous les réseaux de façon optimale monotone et connexe.

National audience; Les réseaux de capteurs sans fils sont constitués d'un grand nombre de noeuds assujettis à de sévères contraintes en terme d'énergie, de capacité de traitement et de communication. Dans ce contexte, afin de réduire la complexité, un des défis majeurs rencontrés dans ce type de réseau est le calcul des routes et la mise en oeuvre de schémas de routage efficaces tout en minimisant la quantité d'information utilisée sur l'état du système. De nombreux travaux ont étudié ce compromis de facon qualitative ou grâce à des simulations. Nous proposons un modèle basé sur la théorie de la marche aléatoire pour estimer analytiquement ce compromis en considérant plus particulièrement l'influence du degré de connaissance de l'état du système que possède un noeud sur le temps moyen de collecte dans un réseau de capteurs sans fils.

National audience; Il est établit depuis 2001 que tout arbre à n sommets possède un schéma de routage de plus courts chemins utilisant des adresses, des en-têtes et des tables de routage de O(log n) bits. Il est ouvert de savoir si ce résultat optimal peut être étendu à des graphes plus généraux. En particulier Fraigniaud et al. ont posé la question de savoir si ce résultat restait vrai pour les graphes planaires-extérieurs, une classe de graphes planaires contenant les arbres. Dans cet article, nous répondons positivement à cette question. En fait, nous étendons le résultat à des graphes valués beaucoup plus généraux, appelés k-cellulaires. Tout graphe est k-cellulaire pour une certaine valeur de k, mais ces graphes comprennent, par exemple, le cas des graphes planaires où tous les sommets peuvent être couverts par O(k) faces disjointes, et dans ce cas le schéma de routage peut être construit en temps quadratique.

In 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., Ré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.