2024-03-29T06:49:21Zhttps://repositori.uji.es/oai/requestoai:repositori.uji.es:10234/495272023-11-03T12:29:47Zcom_10234_7038com_10234_9col_10234_8634
Repositori UJI
author
Rodero Merino, Luis
author
Fernández Anta, Antonio
author
López, Luis
author
Cholvi, Vicent
2012-10-22T11:18:11Z
2012-10-22T11:18:11Z
2010
RODERO-MERINO, Luis, et al. Performance of random walks in one-hop replication networks. Computer Networks, 2010, vol. 54, no 5, p. 781-796
1389-1286
http://hdl.handle.net/10234/49527
http://dx.doi.org/10.1016/j.comnet.2009.10.006
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.
eng
Average search length
Average search time
Look-ahead networks
Random-walk
Performance of random walks in one-hop replication networks
info:eu-repo/semantics/article
URL
https://repositori.uji.es/xmlui/bitstream/10234/49527/1/Performance+of+random_2009.pdf
File
MD5
65e32eba456dbc92ceff15735759d6cc
616435
application/pdf
Performance of random_2009.pdf
URL
https://repositori.uji.es/xmlui/bitstream/10234/49527/2/Performance+of+random_2009.pdf.txt
File
MD5
a5318e38b97be8fd8270b0ea478e9428
70615
text/plain
Performance of random_2009.pdf.txt