Stanford InfoLab Publication Server

Routing Indices For Peer-to-Peer Systems

Crespo, Arturo and Garcia-Molina, Hector (2001) Routing Indices For Peer-to-Peer Systems. Technical Report. Stanford.




Finding information in a peer-to-peer system currently requires either a costly and vulnerable central index, or flooding the network with queries. In this paper we introduce the concept of Routing Indices (RIs), which allow nodes to forward queries to neighbors that are more likely to have answers. If a node cannot answer a query, it forwards the query to a subset of its neighbors, based on its local RI, rather than by selecting neighbors at random or by flooding the network by forwarding the query to all neighbors. We present three RI schemes: the compound, the hop-count, and the exponential routing indices. We evaluate their performance via simulations, and find that RIs can improve performance by one or two orders of magnitude vs. a flooding-based system, and by up to 100% vs. a random forwarding system. We also discuss the tradeoffs between the different RI schemes and highlight the effects of key design variables on system performance.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:Peer-to-peer systems, Routing Index, Query Processing, Query Forwarding, Approximate Indices, Content Discovery, Distributed Search Mechanisms
Subjects:Computer Science
Computer Science > Databases and the Web
Computer Science > Digital Libraries
Computer Science > Distributed Systems
Digital Libraries
Related URLs:Project Homepage, Project Homepage,
ID Code:514
Deposited By:Import Account
Deposited On:05 Nov 2001 16:00
Last Modified:27 Dec 2008 09:48

Download statistics

Repository Staff Only: item control page