A Stable Approach for Routing Queries in Unstructured P2P Networks

Virag Shah, Gustavo De Veciana, George Kesidis

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Finding a document or resource in an unstructured peer-to-peer network can be an exceedingly difficult problem. In this paper we propose a query routing approach that accounts for arbitrary overlay topologies, nodes with heterogeneous processing capacity, e.g., reflecting their degree of altruism, and heterogenous class-based likelihoods of query resolution at nodes which may reflect query loads and the manner in which files/resources are distributed across the network. The approach is shown to be stabilize the query load subject to a grade of service constraint, i.e., a guarantee that queries' routes meet pre-specified class-based bounds on their associated a priori probability of query resolution. An explicit characterization of the capacity region for such systems is given and numerically compared to that associated with random walk based searches. Simulation results further show the performance benefits, in terms of mean delay, of the proposed approach. Additional aspects associated with reducing complexity, estimating parameters, and adaptation to class-based query resolution probabilities and traffic loads are studied.

Original languageEnglish (US)
Article number7372490
Pages (from-to)3136-3147
Number of pages12
JournalIEEE/ACM Transactions on Networking
Issue number5
StatePublished - Oct 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'A Stable Approach for Routing Queries in Unstructured P2P Networks'. Together they form a unique fingerprint.

Cite this