Searching Techniques in Peer-to-Peer Networks.
Xiuqi Li, Jie Wu · 2005
This chapter provides a survey of major searching techniques in peer-to-peer (P2P) networks. We first introduce the concept of P2P networks and the methods for classifying different P2P networks. Next, we discuss various searching techniques in unstructured P2P systems, strictly structured P2P systems, and loosely structured P2P systems. The strengths and weaknesses of these techniques are highlighted. Searching in unstructured P2Ps covers both blind search schemes and informed search schemes. Blind searches include iterative deepening, k-walker random walk, modified random BFS, and two-level k-walker random walk. Informed searches include local indices, directed BFS, intelligent search, routing indices, attenuated bloom filter, adaptive probabilistic search, and dominating set based search. The discussion of searching in strictly structured P2Ps focuses on hierarchical Distributed Hash Table (DHT) P2Ps and nonDHT P2Ps. Searching in non-hierarchical DHT P2Ps is briefly overviewed. The presentation of the hierarchical DHT P2Ps pays more attention to Kelips and Coral, whereas that of searching in non-DHT P2Ps focuses on SkipNet and TerraDir. The description of searching in loosely structured P2Ps focuses on Freenet. We conclude this chapter by summarizing open problems in searching the P2P networks.