The standard gossiping used in many overlay networks consists in a Self-Avoiding Random Walk (SAW): a message, once received by a node, is forwarded to a node chosen uniformly at random among the neighbors, excluding the node it comes from. We focus on a generalization of the above walks, defined by the Neighbor-Avoiding Walks (NAWs), i.e. walks that not only avoid themselves, but preferably also the neighbors of the path they traveled. We studied the performance of NAW policies over geometric random networks (a common model used for unstructured networks for instance for Wireless Sensor Networks) in terms of cover time and as a function of several structural network graph metrics: nodes' cardinality, nodes' clustering coefficient, node distance distribution, link centrality distribution. We find that neighbor avoiding policies perform better that the usual SAW policy and that this improvement is especially apparent in networks whose topology is characterized by high values of link centrality.

The cover time of neighbor-avoiding gossiping on geometric random networks / E. Damiani, G. Gianini - In: 2013 7th IEEE International conference on digital ecosystems and technologies (DEST) : Menlo Park, California, USA 24–26 july 2013 : proceedingsPiscataway : Institute of electrical and electronics engineers, 2013. - ISBN 9781479907861. - pp. 7-12 (( Intervento presentato al 7. convegno 2013 7th IEEE International Conference on Digital Ecosystems and Technologies (DEST) tenutosi a Menlo Park, United States nel 2013 [10.1109/DEST.2013.6611321].

The cover time of neighbor-avoiding gossiping on geometric random networks

E. Damiani;G. Gianini
2013

Abstract

The standard gossiping used in many overlay networks consists in a Self-Avoiding Random Walk (SAW): a message, once received by a node, is forwarded to a node chosen uniformly at random among the neighbors, excluding the node it comes from. We focus on a generalization of the above walks, defined by the Neighbor-Avoiding Walks (NAWs), i.e. walks that not only avoid themselves, but preferably also the neighbors of the path they traveled. We studied the performance of NAW policies over geometric random networks (a common model used for unstructured networks for instance for Wireless Sensor Networks) in terms of cover time and as a function of several structural network graph metrics: nodes' cardinality, nodes' clustering coefficient, node distance distribution, link centrality distribution. We find that neighbor avoiding policies perform better that the usual SAW policy and that this improvement is especially apparent in networks whose topology is characterized by high values of link centrality.
Settore INF/01 - Informatica
Certification infrastrUcture for MUlti-Layer cloUd Services
IEEE
Book Part (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/225528
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact