Evaluating topology quality through random walks

Anne-Marie Kermarrec 1 Erwan Le Merrer 1 Bruno Sericola 2 Gilles Trédan 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
2 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Abstract : A distributed system or network can be modeled as a graph representing the "who knows who" relationship. The conductance of a graph expresses the quality of the connectivity. In a network composed of large dense clusters, connected through only a few links, the risk of partitioning is high; this is typically reflected by a low conductance of the graph. Computing the conductance of a graph is a complex and cumbersome task. Basically, it requires the full knowledge of the graph and is prohibitively expensive computation-wise. Beyond the information carried by the conductance of a graph, what really matters is to identify critical nodes from the topology point of view. In this paper we propose a fully decentralized algorithm to provide each node with a value reflecting its connectivity quality. Comparing these values between nodes, enables to have a local approximation of a global characteristic of the graph. Our algorithm relies on an anonymous probe visiting the network in a unbiased random fashion. Each node records the time elapsed between visits of the probe (called return time in the sequel). Computing the standard deviation of such return times enables to give an information to all system nodes, information that may be used by those nodes to assess their relative position, and therefore the fact that they are critical, in a graph exhibiting low conductance. Based on this information, graph improvement algorithms may be triggered. Moments of order 1 and 2 of the return times are evaluated analytically using a Markov chain model, showing that standard deviation of return time is related to the position of nodes in the graph. We evaluated our algorithm through simulations. Results show that our algorithm is able give informations that are correlated to the conductance of the graph. For example we were able to precisely detect bridges in a network composed of two dense clusters connected through a single link.
Type de document :
[Research Report] RR-6534, INRIA. 2008, pp.22
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 15 mai 2008 - 17:01:26
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 22:12:44


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00279074, version 2


Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan. Evaluating topology quality through random walks. [Research Report] RR-6534, INRIA. 2008, pp.22. 〈inria-00279074v2〉



Consultations de la notice


Téléchargements de fichiers