Small-World Networks: Is there a mismatch between theory and practice?

François Bonnet 1 Anne-Marie Kermarrec 1 Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : In small-world networks, each peer is connected to its closest neighbors in the network topology, as well as to additional long-range contact(s), also called shortcut(s). In 2000, Kleinberg showed that greedy routing in a $n$ peer small-world network, performs in $O(n^\frac{1}{3})$ steps when the distance to shortcuts is chosen uniformly at random, and in $O(\log^2n)$ when the distance to shortcuts is chosen according to a harmonic distribution in a $d$-dimensional mesh. Yet, we observe through experimental results that peer to peer gossip-based protocols achieving small-world topologies where shortcuts are randomly chosen, perform well in practice. The motivation of this paper is to explore this mismatch and attempt to reconcile theory and practice in the context of small-world overlay networks. More precisely, based on the observation that, despite the fact that the routing complexity of gossip-based small-world overlay networks is not polylogarithmic (as proved by Kleinberg), this type of networks ultimately provide reasonable results in practice. This leads us to think that the asymptotic big $O()$ complexity alone might not always be sufficient to assess the practicality of a system. The paper consequently proposes a refined routing complexity measure for small-world networks. Simulation results confirm that random selection of shortcuts can achieve ``practical'' systems. Then, given that Kleinberg proved that the distribution of shortcuts has a strong impact on the routing complexity, arises the question of leveraging this result to improve upon current gossip-based protocols. We show that it is possible to design gossip-based protocols providing a good approximation of Kleinberg-like small-world topologies. Along, are presented simulation results that demonstrate the relevance of the proposed approach.
Type de document :
[Research Report] PI 1849, 2007, pp.15
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger
Contributeur : Anne Jaigu <>
Soumis le : mardi 11 mai 2010 - 13:14:21
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : jeudi 16 septembre 2010 - 12:13:59


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


  • HAL Id : inria-00155579, version 1


François Bonnet, Anne-Marie Kermarrec, Michel Raynal. Small-World Networks: Is there a mismatch between theory and practice?. [Research Report] PI 1849, 2007, pp.15. 〈inria-00155579〉



Consultations de la notice


Téléchargements de fichiers