Dominating-Set-Based Searching in Peer-to-Peer Networks

Abstract — The peer-to-peer network for sharing information and data through direct exchange has emerged rapidly in recent years. The searching problem is a basic issue that addresses the question “Where is X”. Breadth-first search, the basic searching mechanism used in Gnutella networks [7], floods the networks to maximize the return results. Depth-first search used in Freenet [6] retrieves popular files faster than other files but on average the return results are not maximized. Other searching algorithms used in peer-to-peer networks, such as iterative deepening [13], local indices [13], routing indices [3] and NEVRLATE [2] provide different improved searching mechanisms. In this paper, we propose a dominating-set-based peer-to-peer searching algorithm to maximize the return of searching results while keeping a low cost for both searching and creating/maintaining the connecteddominating-set (CDS) of the peer-to-peer network. This approach is based on random walk. However, the searching space is restricted to dominating nodes. Simulation has been done and results are compared with the one using regular random walk. I