论文部分内容阅读
本文着重研究对等(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。