Evaluating the Quality of a Network Topology through Random Walks

Erwan Le Merrer (1) , Anne-Marie Kermarrec (1) , Gilles Trédan (1) , Bruno Sericola (2)

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
2 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS

In this brief announcement we propose a distributed algorithm to assess the connectivity quality of a network, be it physical or logical. In large complex networks, some nodes may play a vital role due to their position (e.g. for routing or network reliability). Assessing global properties of a graph, as importance of nodes, usually involves lots of communications; doing so while keeping the overhead low is an open challenge.

Domaines: Réseaux et télécommunications [cs.NI]

Erwan Le Merrer, Anne-Marie Kermarrec, Gilles Trédan, Bruno Sericola. Evaluating the Quality of a Network Topology through Random Walks. DISC 2008: 22nd International Symposium on Distributed Computing, Sep 2008, Arcachon, France. pp.509--511, ⟨10.1007/978-3-540-87779-0⟩. ⟨inria-00329941⟩