学位论文 > 优秀研究生学位论文题录展示

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

作　者: 宋建涛
导　师: 朱洪
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 对等网内容编址网语义对等网并行下载纳什均衡分布式哈希表
分类号: TP393
类　型: 博士论文
年　份: 2004年
下　载: 519次
引　用: 7次
阅　读: 论文下载

内容摘要

本文着重研究对等(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。

全文目录

摘要  3-5
Abstract (英文摘要)  5-10
第1章引言  10-20
  1.1 背景知识  10-11
  1.2 对等计算的概念  11-12
  1.3 对等计算的特点  12-13
  1.4 对等计算的优点  13-15
  1.5 对等计算的体系结构  15-17
    1.5.1 集中式  16
    1.5.2 分散式非结构化  16-17
    1.5.3 分散式结构化  17
  1.6 本文工作  17-19
  1.7 本文结构  19-20
第2章对网资源定位和路由算法综述对等等  20-27
  2.1 分散式结构化系统  20-25
    2.1.1 PRR  20-21
    2.1.2 Tapestry  21
    2.1.3 Pastry  21-22
    2.1.4 Chord  22-23
    2.1.5 CAN  23-25
  2.2 分散式非结构化系统  25-27
第3章语义对网对等等  27-54
  3.1 引言  27-28
  3.2 相关工作  28-29
  3.3 语义对等网的概念  29-30
  3.4 粗粒度语义对等网pGroup  30-41
    3.4.1 pGroup的构造  30-33
    3.4.2 pGroup的维护  33-34
    3.4.3 pGroup的搜索机制  34-41
  3.5 细粒度语义对等网fGroup  41-47
    3.5.1 fGroup的构造  41-45
    3.5.2 fGroup的维护  45
    3.5.3 fGroup的搜索机制  45-47
  3.6 热点问题的解决方案  47-48
    3.6.1 采用多个哈希函数  47-48
    3.6.2 利用异质性  48
    3.6.3 使用复制技术  48
  3.7 模拟结果  48-52
    3.7.1 pGroup的模拟结果  49-51
    3.7.2 fGroup的模拟结果  51-52
  3.8 本章小结  52-54
第4章多用户并行下载中的纳什均衡  54-80
  4.1 引言  54-56
  4.2 相关工作  56-57
  4.3 预备知识  57-62
    4.3.1 并行下载  57-59
    4.3.2 博弈论与纳什均衡  59-62
  4.4 模型及问题描述  62-64
  4.5 纳什均衡的特征和性质  64-67
    4.5.1 纳什均衡的特征  64-65
    4.5.2 纳什均衡的性质  65-67
  4.6 纳什均衡的收敛性  67-75
    4.6.1 具有线型延迟函数的一个特殊网络  68-73
    4.6.2 具有一般延迟函数的另一个特殊网络  73-75
  4.7 纳什均衡的效率  75-78
  4.8 本章小结  78-80
第5章常数度、对数直径的DHT网络  80-90
  5.1 引言  80-82
  5.2 相关工作  82
  5.3 de Bruijn图的结构及路由  82-85
    5.3.1 de Bruijn图的结构  82-83
    5.3.2 de Bruijn图的路由  83-84
    5.3.3 无向de Bruijn图  84-85
  5.4 基于无向de Bruijn图构造DHT路由网络  85-88
    5.4.1 连续-离散方法概述  85-86
    5.4.2 构造DHT路由网络  86-88
  5.5 本章小结  88-90
第6章结论与展望  90-93
  6.1 结论  90-92
  6.2 进一步的研究工作  92-93
致谢  93-94
参考文献  94-102
参加的科研项目及发表的论文  102-103

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

内容摘要

全文目录

相似论文