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.
|Titolo:||The cover time of neighbor-avoiding gossiping on geometric random networks|
DAMIANI, ERNESTO (Primo)
GIANINI, GABRIELE (Secondo)
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Progetto:||Certification infrastrUcture for MUlti-Layer cloUd Services|
|Data di pubblicazione:||2013|
|Enti collegati al convegno:||IEEE|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1109/DEST.2013.6611321|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|