Bilkent University
Department of Computer Engineering


Reducing Query Overhead Through Route Learning in Unstructured Peer-to-Peer Networks


Selim Ciraci
Msc. Student
Computer Engineering
Bilkent University

In unstructured peer-to-peer networks such as Gnutella, peers propagate query messages towards the resource holders by flooding them through the P2P network. This is, however, a costly operation since it consumes node and link resources excessively and most of the time unnecessarily. There is no reason, for example, for a peer to receive a query message if the peer does not own any matching resource or if the peer is not on the path reaching to a peer holding a matching resource. Semantic routing is a technique that tries to forward the queries only to those nodes where replies are likely to come from. In this thesis we present Route Learning, a semantic routing scheme, which aims to reduce query traffic in unstructured peer-to-peer networks by utilizing a well-known estimation technique called Parzen Windows. In Route Learning, peers try to find the most likely neighbors through which replies can be get to submitted queries. In this way, a query is forwarded only to a subset of the neighbors of a peer, or is dropped if no neighbor, which is likely to return a reply, is found. The scheme has also mechanisms to cope with variations in user submitted queries, like changes in the keywords. This way the scheme can also evaluate the route for a query for which it is not retrained. The proposed scheme consists of three phases: training, evaluation and recursive learning. The last phase enables the scheme to adapt itself to changes in a dynamic peer-to-peer network. Our simulation results show that our scheme reduces the bandwidth overhead significantly without scarifying user satisfaction much compared to a pure flooding based querying approach.


DATE: August 19, 2005, Friday @ 14:00