Performance of random walks in one-hop replication networks
Ver/ Abrir
Impacto
Scholar |
Otros documentos de la autoría: Rodero Merino, Luis; Fernández Anta, Antonio; López, Luis; Cholvi, Vicent
Metadatos
Mostrar el registro completo del ítemcomunitat-uji-handle:10234/9
comunitat-uji-handle2:10234/7038
comunitat-uji-handle3:10234/8634
comunitat-uji-handle4:
INVESTIGACIONMetadatos
Título
Performance of random walks in one-hop replication networksFecha de publicación
2010Editor
ElsevierISSN
1389-1286Cita bibliográfica
RODERO-MERINO, Luis, et al. Performance of random walks in one-hop replication networks. Computer Networks, 2010, vol. 54, no 5, p. 781-796Tipo de documento
info:eu-repo/semantics/articleVersión de la editorial
https://www.sciencedirect.com/science/article/pii/S1389128609003259Versión
info:eu-repo/semantics/submittedVersionPalabras clave / Materias
Resumen
Random walks are gaining much attention from the networks research community. They are the basis of many proposals aimed to solve a variety of network-related problems such as resource location, network construction, ... [+]
Random walks are gaining much attention from the networks research community. They are the basis of many proposals aimed to solve a variety of network-related problems such as resource location, network construction, nodes sampling, etc. This interest on random walks is justified by their inherent properties. They are very simple to implement as nodes only require local information to take routing decisions. Also, random walks demand little processing power and bandwidth. Besides, they are very resilient to changes on the network topology. Here, we quantify the effectiveness of independent random walks (i.e, random walks that have statistical properties identical to the random sampling) as a search mechanism in one-hop replication networks: networks where each node knows its neighbors' identity/resources, and so it can reply to queries on their behalf. Our model focuses on estimating the expected average search time of the random walk by applying network queuing theory. To do this, we must provide first the expected average search length. This is computed by means of estimations of the expected average coverage at each step of the random walk for all random walks in all random networks with a given degree distribution. This model takes into account the revisiting effect: the fact that, as the random walk progresses, the probability of arriving to nodes already visited increases, which impacts on how the network coverage evolves. That is, we do not model the coverage as a memoryless process. Furthermore, we conduct a series of simulations to evaluate, in practice, the above mentioned metrics. Our results show a very close correlation between the analytical and the experimental results. © 2009 Elsevier B.V. All rights reserved. [-]
Publicado en
Computer Networks, 2010, vol. 54, no 5Proyecto de investigación
This research was supported in part by the Spanish MEC grants TIN2008-03687 and PR2008-0015; by Bancaixa grant P1-1B2007-44; by the Spanish MITC grants WCLlab and TSI-020110-2009-103; by the Spanish MICINN grants PET2008_0128, PET2007_0231, TSI2006-07799 and TIN2008-06735-C02-01; and by Comunidad de Madrid grant S-0505/TIC/0285.Derechos de acceso
http://rightsstatements.org/vocab/CNE/1.0/
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/openAccess
Aparece en las colecciones
- LSI_Articles [366]