Routing indices for peer-to-peer systems

TLDR

Finding information in a peer‑to‑peer system currently requires either a costly and vulnerable central index or flooding the network with queries. The paper introduces routing indices (RIs) that enable nodes to forward queries to neighbors more likely to have answers. RIs forward queries to a subset of neighbors selected by a local index, and the authors propose three schemes—compound, hop‑count, and exponential—to construct these indices. Simulations show that RIs improve performance by one to two orders of magnitude over flooding and up to 100 % over random forwarding, while tradeoffs among the schemes and key design variables affect system performance.

Abstract

Finding information in a peer-to-peer system currently requires either a costly and vulnerable central index, or flooding the network with queries. 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.