Calculation Study

This thesis focuses on Peer-to-Peer (P2P) computing. P2P networkingapplications have seen explosive growth in recent years. One of the mostimportant applications of P2P computing is P2P ?le sharing system. Thesuccess of P2P ?le sharing system highly depends on the scalability andversatility of its search mechanism. Existing structured P2P networks (such as CAN [5], Chord [6], Pastry[7] and Tapestry [8]) supporting Distributed Hash Table (DHT) functionalityare scalable, but they can not support partial-match queries e?ectively. Onthe opposite, unstructured P2P networks (such as Gnutella) rely on ?ood-ing for search, thus supporting partial-match queries, but such ?ooding doesnot make the systems scalable. We propose a novel architecture called Se-mantic Peer-to-peer Networks (SPNs) where semantically related nodes areconnected to each other. Based on Content Addressable Networks (CAN),we construct coarse-grained SPNs (pGroup) and ?ne-grained SPNs (fGroup)respectively. According to the di?erent querying, we present correspond-ing search algorithms in pGroup and fGroup respectively. As is shown bysimulations, search e?ciency is improved greatly compared to Gnutella. To expedite the reception of a large ?le, many P2P systems such asKazaa, Grokster and Morpheus have employed the scheme of parallel down- 2This work is supported by a grant from the Ministry of Science and Technology (grant#2001CCA03000), National Natural Science Fund (grant #60273045) and Shanghai Sci-ence and Technology Development Fund (grant #025115032) IIIIVloading. To investigate the impact that this scheme might have on the net-work if multiple clients simultaneously use it, we formulate parallel down-loading as a non-cooperative game. To the best of our knowledge this isthe ?rst work that analyzes the parallel downloading problem in a nonco-operative game theoretical fashion. Within this framework, we present acharacterization of the tra?c con?guration at Nash equilibrium in a generalnetwork, and analyze its properties in a speci?c network. We also establishthe dynamic convergence to equilibrium for two speci?c networks. Finally,we investigate the e?ciency of Nash equilibrium from the point of view ofthe clients and the system respectively, i.e., downloading latencies perceivedby individual clients and total latencies over all connections. We ?nd thatalthough the tra?c con?guration at Nash equilibrium is optimal from thepoint of view of the clients, it may be bad from the point of view of thesystem. Most DHTs such as CAN, Chord, Pastry and Tapestry require O(logN)neighbors and have O(logN) pathlengths. In order to maintain the e?ciencyand correctness of routing, they require O(logN) repair operations of theirrouting tables when a node joins or leaves. Given the highly transient userpopulations in P2P systems, it is therefore of great importance to constructDHTs with O(1) neighbors and O(logN) pathlengths. Several recent papers[70, 73, 74] have proposed de Bruijn graphs for peer-to-peer networks. Butthey all use links in only one direction. By introducing bi-directionality oflinks, we further improve the routing algorithm and construct such DHTs byusing the continuous-discrete approach [75].