对等计算中的若干问题研究

【作者】 宋建涛；

【导师】 朱洪；

【作者基本信息】 复旦大学 ， 计算机软件与理论， 2004， 博士

【摘要】 本文着重研究对等(Peer-to-Peer, 简称P2P)计算。对等网应用在近几年内已得到突飞猛进的发展。P2P文件共享系统是对等计算最重要的应用之一。P2P文件共享系统能否成功极大地取决于搜索机制的多样性和扩展性。 当前支持分布式哈希表(Distributed Hash Table, DHT)功能的结构化系统(如CAN [5]、Chord [6]、Pastry [7]和Tapestry [8])易扩展但不能有效地支持部分匹配的查询;而基于扩散的非结构化系统(如Gnutella)支持多样化查询但不易扩展。本文作者提出了一种新型的对等网体系结构—语义对等网(Semantic Peer-to-peer Networks, SPNs),其中语义相关的结点互相连接在一起。基于内容编址网(Content Addressable Networks,CAN),我们分别构造了粗粒度语义对等网pGroup 和细粒度语义对等网fGroup。根据不同的查询情况,我们分别对pGroup和fGroup提出相应的搜索算法。模拟结果表明,搜索效率比Gnutella网络大大提高了。 为加速大文件的接收,许多P2P系统如Kazaa、Grokster和Morpheus等采用了并行下载机制。为研究多个用户同时使用这一机制时其对整个网络的影响,本文作者利用非合作博弈论对并行下载问题进行建模。就我们所知,这是第一次用非合作博弈论方法分析并行下载问题的工作。在这个框架下,我们给出了纳什均衡在一般网络中的特征;针对特殊的网络分析了纳什均衡的性质;并对两个特殊的网络建立了纳什均衡的动态收敛性;最后,分别从用户和系统的角度,即分别从单个用户的下载时延和所有连接1本研究受到科学技术部基础研究重大项目前期研究专项第2001CCA0300号,国家自然科学基金第60273045号和上海市科技发展基金第025115032号资助。 I<WP=4>II上总的时延,研究了纳什均衡的效率。结果发现,尽管从用户的角度来看,纳什均衡是最优的;但从系统的角度来看,纳什均衡却很糟糕。大多数DHTs如CAN、Chord、Pastry和Tapestry 需要O(logN)的邻居数和O(logN)的路由长度。为维护路由的正确性和效率,当一个结点加入或离开系统时它们需要对路由表进行O(logN)的修复操作。考虑到P2P系统中用户的高度动态性,构造具有O(1)邻居数和O(logN)路由长度的DHTs是很重要的。最近的文献 [70, 73, 74]提出了基于de Bruijn 图的P2P网络,但他们都仅使用了单方向的链路。通过引入双向链路,我们进一步改进了其中的路由算法,并使用连续-离散方法 [75] 构造了DHTs。更多还原

【Abstract】 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) III<WP=6>IVloading. 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].更多还原