P2P组通讯的网络拓扑研究

论文摘要

互联网正承载着越来越多的多媒体传输任务,同一个多媒体数据大多在一个有着共同兴趣的群体里传输,在传输过程中这些数据往往需要占用大量的网络资源。IP组播是传统的组通讯实现方案,它能够避免在链路上传输重复报文,节省网络带宽,实现高效的组通讯传输。但是由于市场和运营方面等方面的原因,至今互联网仍然没有普及支持IP组播的路由器。基于P2P的组通讯实现方案以其灵活的组网方式和低成本的组网代价吸引了来自于业界和学术界不同领域的研究人员。P2P组通讯是一个复杂的过程,涉及到网络组建、维护和信息发布、获取等诸多因素。这些因素彼此相互关联,网络的构建方式支配着信息的传输路径,而信息的发布策略又可以影响网络的构建方案,只有一个合适的网络拓扑才能够让信息发布得更快更好,从而尽可能地为用户提供高质量的传输服务。本文重点研究针对多媒体传输的P2P组通讯的网络拓扑,论文的创新性工作主要体现在以下几个方面:1.针对P2P组通讯的特点,定义了根跳距和根距离两个拓扑特征指标参数来衡量测试拓扑图和底层网络的吻合程度。给出一个拓扑? （n, k）,发现任意一个主机只要随机选择Θ（log n）个不同的其它主机进行测试,就能保证在? （n, k）中从该源主机到所有其它主机都是可达的;并且只要随机选择?? 2.997×n0.5312??个不同的其它主机,就能保证从发送源到任意主机的路径长度最多是相应底层网络直径的2倍（即根跳距为2）。这表明不必进行完全测试就可以抽象出测试拓扑图在根跳距方面的特性。模拟试验显示,当满足上述条件时再增大k值已不会使P2P组通讯的传输路径的迂回程度有显著的改善。另外还发现随机选择更少的其它主机就可以保证根跳距为3或4。2.在基于树的P2P组通讯的传输路径方面,抽象了一个新的生成树问题——DCMD问题,该问题同时考虑了线路延迟、主机的发送/转发延迟和每个主机的工作负载有限三种情况,可以更加全面地刻画出构建在应用层的P2P组通讯;证明了这个问题属于NP-hard;提出了基于最大度和基于最长路径两类启发式算法作为解决该问题的途径。最后通过模拟试验评估了这两类启发式算法的可行性。3.在基于扩散机制的P2P组通讯领域中,提出了一种适合Gossip发布机制的网络动态分布式聚合方法。首先分析了评价Gossip发布机制性能的扩展速度、流畅性和健壮性三个指标以及网络拓扑对各个指标的影响,然后指出均衡网络的聚合特性和连通性的必要性。所提出的这种分布式聚合方法是基于簇估计的方法,可以在保证聚集度大的集群内部的高连通性的同时又保证集群之间连通,从而使得系统能够获得一个较为理想的

论文目录

• 第一章 引言
• 1.1 P2P 组通讯的研究背景
• 1.1.1 客户/服务器模式面临的问题
• 1.1.2 IP 组播
• 1.1.3 IP 组播的替代方案
• 1.2 研究内容
• 1.3 主要贡献
• 1.4 组织结构
• 第二章 P2P 网络拓扑的概述
• 2.1 结构型P2P 网络
• 2.2 非结构型P2P 网络
• 2.2.1 Erd?s-Rényi 随机图
• 2.2.2 k 规则随机图
• 2.2.3 随机有向图
• 2.3 其它问题的说明
• 2.3.1 幂律现象
• 2.3.2 多重图和偏好选取
• 2.4 本章结论
• 第三章 P2P 组通讯网络拓扑的关键技术
• 3.1 P2P 组通讯的应用类型
• 3.2 P2P 组通讯的应用场景特征
• 3.2.1 Flash crowd
• 3.2.2 组成员的动态特性
• 3.2.3 组成员的异质性
• 3.2.4 会议型和发布型应用场景
• 3.3 P2P 组通讯网络拓扑的关键技术
• 3.3.1 P2P 组通讯的拓扑发现
• 3.3.2 基于树的P2P 组通讯的转发树生成算法
• 3.3.3 基于Gossip 的P2P 组通讯的簇状网络研究
• 第四章 P2P 组通讯的拓扑发现
• 4.1 拓扑发现的相关研究
• 4.1.1 互联网络的定位技术
• 4.1.2 P2P 网络的拓扑发现
• 4.2 P2P 组通讯的拓扑发现目标
• 4.2.1 网络拓扑特性
• 4.2.2 P2P 组通讯的网络拓扑特性
• 4.2.3 吻合指标
• 4.3 P2P 组通讯的拓扑发现方案
• 4.4 方案模型
• 4.5 理论分析
• 4.5.1 基本术语
• 4.5.2 连通性
• 4.5.3 根跳距
• 4.5.4 根距离
• 4.6 动态环境中的拓扑发现机制
• 4.6.1 动态连通性
• 4.6.2 动态拓扑发现策略
• 4.7 试验结果
• 4.7.1 随机数的生成方案
• 4.7.2 根跳距
• 4.7.3 根距离
• 4.7.4 应用实例
• 4.7.5 动态环境
• 4.8 本章小结
• 第五章 P2P 组通讯转发树的生成算法
• 5.1 相关工作
• 5.1.1 IP 组播的转发树的研究
• 5.1.2 应用层组播的转发树的研究
• 5.2 待解决的问题
• 5.2.1 问题定义
• 5.2.2 DCMD 问题的复杂度分析
• 5.3 算法描述
• 5.3.1 术语
• 5.3.2 基于度的算法
• 5.3.3 基于最大延迟路径的算法
• 5.3.4 基于二次最小生成树算法
• 5.4 重构转发树的相关研究
• 5.4.1 重新计算转发树
• 5.4.2 冗余父亲节点
• 5.4.3 节点失败通知机制
• 5.5 试验结果
• max的比较'>5.5.1 与参考值dis^max的比较
• 5.5.2 与网络稠密度的关系
• 5.6 本章小结
• 第六章 基于Gossip 的P2P 组通讯网络拓扑
• 6.1 Gossip 发布机制的概述
• 6.2 衡量Gossip 发布性能的指标
• 6.2.1 扩散速度
• 6.2.2 流畅性
• 6.2.3 可靠性
• 6.3 Gossip 发布机制与簇状网络
• 6.4 聚合算法的相关研究
• 6.4.1 集中式聚合算法
• 6.4.2 分布式聚合方法
• 6.5 形成簇状网络的动态分布式聚合方法
• 6.5.1 设计目标
• 6.5.2 方法描述
• 6.5.3 分析
• 6.5.4 安全问题
• 6.6 估计集群大小的理论分析
• 6.6.1 相关研究
• 6.6.2 简单估计
• 6.7 试验结果
• 6.7.1 规模预测
• 6.7.2 簇状网络的连通性
• 6.7.3 簇状网络的根距离
• 6.7.4 簇状网络的可用信息
• 6.8 本章小结
• 第七章 结论与展望
• 7.1 论文结论
• 7.2 后继工作
• 致谢
• 参考文献
• 个人简历
• 参与的项目
• 发表的文章