Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/4734

Topology construction and searching algorithms for heterogeneous peer-to-peer networks

Authors Kwong, Kin Wah
Issue Date 2005
Summary In this thesis, we consider two fundamental questions in the context of un-structured peer-to-peer (P2P) networks. The first question is how to build an unstructured P2P network by tak-ing peer heterogeneity into account. In general, designing a good topology construction algorithm is not a trivial task because there are several chal-lenges. First, the algorithm should be decentralized without heavily relying on a central agent because the P2P networks typically support millions of users online concurrently and the P2P topology may not be completely known to the users. Second, the algorithm should be simple and lightweight in order to keep the overhead to a minimum. Third, the algorithm should be robust under a dynamic environment meaning that the peers can join and leave the network anytime. Therefore, we propose a very simple algorithm for building capacity-aware unstructured P2P networks such that the connectivity of each peer is based on its capacity to achieve load-balancing. The basic idea of the algorithm is to use a random walk to assist peers in selecting their neighbors with a high capacity per connectivity. Furthermore, we provide a comprehen-sive analysis to investigate the behaviors of the proposed protocol under any heterogeneous P2P environment. The analytical results, which are validated by simulations, provide insightful guidelines for heterogeneous overlay network modeling, planning and protocol design. The second question that we consider is how to efficiently search objects in an unstructured P2P network. Congestion and peer heterogeneity make this question more difficult to solve because we have to consider two important QoS metrics in parallel - hit rate and hit delay. However, this consideration has received little attention from the research community. To achieve an efficient search under heterogeneous networks, we propose a congestion-aware search algorithm by integrating congestion control and object discovery functionality so that the search algorithm can achieve good performance under any situ-ations such as congested networks and flash crowds. The simulation results show that our protocol can greatly reduce a hit delay while maintaining a high hit rate and also the congestion problems such as query loss and peer overloading can be effectively alleviated.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2005
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 343 B HTML