Learning to route queries in unstructured P2P networks: Achieving throughput optimality subject to query resolution constraints

Finding a document or resource in an unstructured peer-to-peer network can be an exceedingly difficult problem. In this paper we propose a dynamic query routing approach that accounts for arbitrary overlay topologies, nodes with heterogeneous processing capacity and heterogenous class-based likelihoods of query resolution at nodes, reflecting the query loads and manner in which files/resources are distributed across the network. Finite processing capacity at nodes, e.g., reflecting their degree of altruism, can indeed limit the stabilizable load into the system. Our approach is shown to be throughput optimal subject to a grade of service constraint, i.e., it stabilizes the query load subject to a guarantee that queries' routes meet pre-specified class-based bounds on their associated a priori probability of query resolution. Numerical and simulation results show significant improvement in capacity region and performance benefits, in terms of mean delay, over random walk based searches. Additional aspects associated with reducing complexity, learning, and adaptation to class-based query resolution probabilities and traffic loads are studied.