Performance of random walks in one-hop replication networks

DOI10.1016/J.COMNET.2009.10.006zbMATH Open1213.68095arXiv0908.0601OpenAlexW2097007251MaRDI QIDQ975046FDOQ975046

Authors: B. E. Eshmatov 

Publication date: 8 June 2010

Published in: Computer Networks (Search for Journal in Brave)

Abstract: 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 random walks 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. 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.

Full work available at URL: https://arxiv.org/abs/0908.0601

Recommendations

• A model of self-avoiding random walks for searching complex networks
• Random walk search in unstructured P2P
• Improving resource location with locally precomputed partial random walks
• Numerical evaluation of the random walk search algorithm
• Optimizing random walk search algorithms in P2P networks

zbMATH Keywords

average search lengthaverage search timelook-ahead networksrandom-walk

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Cited In (3)

• Numerical evaluation of the random walk search algorithm
• A model of self‐avoiding random walks for searching complex networks
• Improving resource location with locally precomputed partial random walks

This page was built for publication: Performance of random walks in one-hop replication networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975046)