Optimizing random walk search algorithms in P2P networks

DOI10.1016/J.COMNET.2006.08.004MaRDI QIDQ870381zbMATH OpenOpenAlexFDO

Authors Nabhendra Bisnik, Alhussein A. Abouzeid

Publication date 12 March 2007

Published in Computer Networks (Search for Journal in Brave)

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

zbMATH Keywords

statisticssimulationsperformance evaluationmodelingsystem designpeer-to-peer networks

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Network design and communication in computer systems (68M10)

Abstract: Overheads incurred by routing protocols diminish the capacity available for relaying useful data in a mobile wireless ad hoc network. Discovering lower bounds on the amount of protocol overhead incurred for routing data packets is important for the development of efficient routing protocols, and for characterizing the actual (effective) capacity available for network users. This paper presents an information-theoretic framework for characterizing the minimum routing overheads of geographic routing in a network with mobile nodes. specifically, the minimum overhead problem is formulated as a rate-distortion problem. The formulation may be applied to networks with arbitrary traffic arrival and location service schemes. Lower bounds are derived for the minimum overheads incurred for maintaining the location of destination nodes and consistent neighborhood information in terms of node mobility and packet arrival process. This leads to a characterization of the deficit caused by the routing overheads on the overall transport capacity.

Recommendations

• Random walk search in unstructured P2P
• Numerical evaluation of the random walk search algorithm
• An efficient adaptive strategy for searching in peer-to-peer networks
• Novel approaches to efficient flooding search in peer-to-peer networks
• Improving resource location with locally precomputed partial random walks

Cited in

(18)

• The analysis of Kademlia for random IDs
• A bio-inspired location search algorithm for peer to peer networks
• scientific article; zbMATH DE number 2043436 (Why is no real title available?)
• A hierarchical load balancing strategy considering communication delay overhead for large distributed computing systems
• ISRL: intelligent search by reinforcement learning in unstructured peer-to-peer networks
• PeerRank: a strategy for resource discovery in unstructured P2P systems
• Performance of random walks in one-hop replication networks
• Maximizing remote work in flooding-based peer-to-peer systems
• A stochastic switching model for a class of hierarchical unstructured P2P systems
• Random walk search in unstructured P2P
• An efficient adaptive strategy for searching in peer-to-peer networks
• Principles of Distributed Systems
• Efficient search by optimized intermittent random walks
• A Cellular Automaton Model for an Immune-Derived Search Algorithm
• Improved degree search algorithms in unstructured P2P networks
• Distributed Computing - IWDC 2004
• Numerical evaluation of the random walk search algorithm
• JumpNet: improving connectivity and robustness in unstructured P2P networks by randomness

This page was built for publication: Optimizing random walk search algorithms in P2P networks

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