| Peer-to-Peer concepts provide new possibilities. Many large-scale Internet services are already introduced with the help of P2P networks. However, The P2P approach to systems design has not made a big impact in practice because designing a new system with P2P concepts is still more of a research problem than a software development problem. The main goal of this dissertation is to provide components that can be combined to build new systems easily. The use of P2P techniques in system design is increased by solving a number of problems that currently present barriers. To address the problems in developing P2P systems, the dissertation focuses on four principal goals: (a) building efficient network size-estimation algorithms (b) modeling and evaluating an efficient general search system (c) testing the search system in a real P2P environment, and (d) designing a new search technique apt for P2P database services.;To address Goal (a), I propose four network size estimation algorithms. The accuracy of network size algorithm has a great impact on several applications on P2P networks including data retrieval. The methods utilize node density within various lengths in a network. The node density makes one estimate of the number of nodes in the whole system by Nˆ = LD, where Nˆ, L, and D represent the estimated network size, the length of address space, and the node density, respectively. Each estimation method requires different communication costs and achieves different performance. Thus, a user can select one of the methods with respect to his purpose and expected performance.;For the pursuit of goal (b), I present Deetoo, an algorithm to perform completely general queries on a P2P network. My interest lies in building efficient unstructured P2P networks. Stated differently, I can apply the proposed model for any type of query without the necessity of mapping the queries onto a fixed DHT structure. Deetoo leverages one-dimensional routable small-world networks, and multicasting trees built on those networks, to build an unstructured query system which can support general queries, such as high-dimensional proximity queries or regular expression matching.;Lastly, this dissertation introduces how to apply P2P unstructured search to P2P database systems. The most important feature of database systems is that the search engine has to always return a correct answer. Deetoo is not sufficient for database systems due to the randomized nature. Thus, I propose Exact Deetoo, which is similar to Deetoo, but Exact Deetoo achieves 100% query success probability. The total communication cost for both caching and querying is not controllable in Exact Deetoo; however, the trade-off between caching cost and the querying cost can be managed by assigning more columns than rows or vice versa. The correctly maintained network decides the cost to achieve 100% success probability. There exists a trade-off between the exact response and the higher maintenance cost for a network structure in Exact Deetoo.;Each of the proposed algorithms are carefully tested and evaluated by simulation, experiments, as well as theoretical proofs. The proposed algorithms are applicable to be built on top of many existing P2P overlays and make it easy for developers to adopt each component. |
