Plansız peer-to-peer sistemler "rota öğrenme" tekniği ile sorgulama yükünün azaltılması

ABSTRACTREDUCING QUERY OVERHEAD THROUGH ROUTELEARNING IN UNSTRUCTURED PEER-TO-PEERNETWORKSSelim CıracışM.S. in Computer Engineering˙ üuSupervisors: Assist. Prof. Dr. Ibrahim Kürpeoğlu, Prof. Dr. Ozgü r Ulusoyo gAugust, 2005In unstructured peer-to-peer networks, such as Gnutella, peers propagate querymessages towards the resource holders by flooding them through the network.This is, however, a costly operation since it consumes node and link resourcesexcessively 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 matchingresource or if the peer is not on the path reaching to a peer holding a matchingresource.Semantic routing is a technique that tries to forward the queries only to thosenodes where replies are likely to come from. In this thesis, we present ?RouteLearning?, a semantic routing scheme, which aims to reduce query traffic in un-structured peer-to-peer networks by utilizing a well-known estimation techniquecalled ?Parzen Windows?. In Route Learning, peers try to find the most likelyneighbors through which replies can be obtained for submitted queries. In thisway, a query is forwarded only to a subset of the neighbors of a peer, or is droppedif no neighbor, which is likely to return a reply, is found. The scheme has alsomechanisms to cope with variations in user submitted queries, like changes inthe keywords. This way the scheme can also evaluate the route for a query forwhich it is not trained. The proposed scheme consists of three phases: training,evaluation, and recursive learning. The last phase enables the scheme to adaptitself to changes in a dynamic peer-to-peer network. Our simulation results showthat our scheme reduces the bandwidth overhead significantly without scarifyinguser satisfaction compared to a pure flooding based querying approach.Keywords: Peer-to-peer query routing, Parzen Windows estimation, querycaching, distributed hash tables.