无结构P2P网络演化过程的拓扑属性分析研究

论文摘要

P2P技术是一项极大地改变了人们在互联网上获取信息方式的发明,它消除了以往通过服务器获取信息时的瓶颈效应,提高了互联网上信息传播的效率,甚至改变了人们的生活方式。P2P网络中相互交换信息的节点间直接建立连接,参与节点通过自组织形成一个信息交换网络,具有传统C/S架构不可比拟的优势。由于不存在服务器瓶颈,P2P技术被广泛应用于诸如网格计算,分布式存储,Web缓存,网络电话,流媒体,网络会议,内容分发等实际系统中。在P2P网络中,不存在中心式的控制结构,所有节点都承担部分网络结构的组织与维护工作。由于节点间是相互独立的,P2P网络中的节点变动非常频繁,研究网络拓扑随时间而演化的过程对网络协议的设计和评估有着重要的参考价值。本文研究了无结构P2P网络拓扑结构随时间逐渐变化的动态过程,主要分为三个部分。第一,本文研究了无结构P2P网络的拓扑演化过程。在现有网络测量结果的基础上,我们建立了一类从概率上反映无结构P2P网络拓扑随时间逐渐变化的网络演化模型,该模型不仅考虑了网络节点的变化情况,也将P2P网络中频繁发生的连接变化考虑在内。此外,该模型的输入是反映网络用户统计行为特征的相关参数,在一定程度上反映了用户行为对网络拓扑产生的影响。本文在不考虑用户行为多样性的条件下,给出了关于演化模型度分布的差分方程,并利用生成函数方法求解了网络度分布,然后采用仿真和数值分析相结合的方法,验证了无结构P2P网络演化模型及其度分布分析的正确性。仿真和分析结果都表明存在两类影响网络度分布的因素,一类倾向于使其服从幂律分布,另一类倾向于使其偏离幂律分布,偏离幂律分布的程度与网络中节点的行为相关。第二,本文将无结构P2P网络的演化模型推广到对一类基于P2P的服务提供网络的建模中。这类网络向远程用户提供服务,但是其本身则是由数台分别完成部分功能的服务器组成。在不考虑节点变化的情况下,我们将无结构P2P网络的演化模型推广用于描述这类服务网络,并给出了与模型度分布相关的差分方程及其解。分析和仿真结果表明这类网络的资源度分布是Poisson分布,其均值与资源请求概率和资源分布概率相关,网络度分布则是几个Poisson分布之和。第三,我们研究了Gnutella网络中社区结构随时间变化的过程。基于在一段时间内连续测量的Gnutella网络拓扑数据,我们采用动态社区结构分析方法研究了Gnutella网络中社区结构的演化过程。分析结果表明,由于网络中节点加入退出非常频繁,Gnutella网络上的社区结构很不稳定,社区经常被分解,同时节点的频繁加入退出也影响到了节点所属社区的稳定性,导致节点经常更换自己所属社区。

论文目录

• 摘要
• ABSTRACT
• 表格
• 插图
• 第一章 绪论
• 1.1 P2P 网络
• 1.1.1 P2P 网络的应用领域
• 1.1.2 无结构P2P
• 1.2 网络结构模型以及社区结构
• 1.2.1 网络结构模型
• 1.2.2 社区结构
• 1.3 本文的研究目的
• 1.4 本文的组织结构
• 1.5 本文的主要贡献
• 第二章 相关研究工作简介
• 2.1 P2P 节点行为和拓扑属性测量
• 2.2 P2P 网络模型
• 2.3 考虑了节点或连接变化的演化模型
• 2.4 社区结构检测算法
• 2.4.1 社区的定义
• 2.4.2 社区结构检测算法
• 第三章 无结构P2P 网络的演化模型及其度分布
• 3.1 演化模型
• 3.1.1 模型描述
• 3.1.2 仿真验证
• 3.2 度分布分析
• 3.2.1 度分布方程
• 3.2.2 度分布方程求解
• 3.2.3 式（3.29）的证明
• 3.2.4 讨论与仿真
• 3.3 小结
• 第四章 基于P2P 的服务网络的演化模型
• 4.1 服务提供网络的非增长模型
• 4.2 非增长演化模型的度分布分析
• 4.2.1 网络度分布
• 4.2.2 资源度分布
• 4.2.3 度分布的求解
• 4.2.4 一个节点上拥有多种资源的情况
• 4.3 仿真结果
• 4.4 小结
• 第5章 Gnutella 网络动态社区结构分析
• 5.1 基本事件
• 5.2 数据集
• 5.3 Gnutella 的动态社区结构
• 5.3.1 社区结构
• 5.3.2 节点行为
• 5.3.3 社区稳定性
• 5.3.4 节点所属社区的稳定性
• 5.4 小结
• 第六章 总结与展望
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果