Adaptive double routing indices: Combining effectiveness and efficiency in P2P systems

Abstract

Unstructured peer-to-peer systems rely on strategies and data structures (Routing Indices) for the routing of requests in the network. For those requests corresponding to information retrieval queries, the emphasis can be either put on the effectiveness of the routing by privileging the relevance of the documents retrieved, or on the efficiency of the routing by privileging the response time. We propose in this paper a novel routing strategy based on adaptive Routing Indices. The Routing Indices are adaptive to the environment, i.e. network traffic, location, as well as relevance of the documents indexed, thanks to a reinforcement learning approach to their maintenance. The strategy can be used to tune the compromise between efficient and effective routing. It combines the estimation of the response time of routes with the estimation of the relevance of routes to keywords. We study performance and the tuning of the compromise offered by this novel strategy under various characteristics of the network and traffic. © Springer-Verlag Berlin Heidelberg 2004.