基于拓扑感知和无偏抽样的快速数据分发研究

论文摘要

Internet环境下的数据分发是一种在广域网中将数据发送到多个节点的网络计算技术,在很多领域都有广泛的研究与应用。快速数据分发将中型数据以高吞吐率、低延迟的方式发送到异构的用户节点群体,在社会突发事件响应,信息化战场环境等领域具有重要的应用。基于覆盖网的快速数据分发可以利用覆盖网的自治性、可扩展性等特点实现有效的数据分发。覆盖网的异构性、动态性等特点给快速数据分发带来挑战。本文针对快速数据分发的特点,对高效的覆盖网拓扑感知、覆盖网抽样和异构、自私节点群体下的数据传输等基础性关键技术展开深入研究。取得的主要研究进展如下:拓扑感知技术能够有效支持低延迟伸展率的覆盖网构建过程,降低数据分发的网络延迟。网络坐标技术是一种轻量级的实现拓扑感知的有效方法。在异构、动态的用户节点群体下,高效的网络坐标技术需要有较强的自适应性和容错性。本文提出了网络坐标预测任意播方法Cocast。Cocast基于任意播查询方式分布式计算用户节点坐标,提高了坐标计算的扩展性和抗恶意节点破坏能力;利用分布式的层次化网络嵌入提高坐标计算的自适应能力和稳定性;提出以位置融合过滤器方式对坐标位置进行综合,提高坐标预测的容错性。理论分析和模拟测试表明,与已有的典型方法GNP,Vivaldi相比,Cocast具有更好的可扩展性、自适应性、容错性以及快速收敛能力。覆盖网抽样通过获取网络中典型的节点可以有效的维护拓扑结构,并优化数据传输路径。基于随机行走的方式可以有效实现覆盖网抽样。在动态的非结构化覆盖网中获取大量的无偏抽样要求随机行走具有可扩展性和无偏性。首先在理论上证明了已有的典型随机行走方式Naive,Metropolis-Hastings缺乏可扩展性,然后提出了基于多个节点自适应随机行走的抽样方法SMARW。SMARW利用代理随机行走一次获取一组可调数目的抽样节点;基于分布式的随机行走修正过程提高抽样过程的收敛速度。理论分析和模拟测试表明SMARW具有近似最优的负载均衡程度,随机行走修正过程收敛速度为O（logN）以及更好的无偏抽样能力。有效利用节点异构性的数据传输技术能够在实现每个节点公平的获取下载带宽的同时,优化系统范围的吞吐率。在异构且呈现自私性的用户节点群体下,为提高系统整体范围的吞吐率,基于覆盖网的快速数据分发需要针对不同上传能力的节点提供对应的服务质量。结合覆盖网拓扑感知技术和抽样技术,本文将能力区分的拓扑构建和速率控制结合,提出了基于能力区分的容错网络编码组播协议CORE。CORE利用能力区分的自适应层次化拓扑构建鼓励节点提供高的上传带宽并优化系统范围的吞吐率;通过直方图的方式对网络编码数据传输进行流量控制,减少冗余的编码数据传输;采用分布式的速率控制策略实现下载带宽分配的能力区分和pareto最优性;利用迭代的数据块内容检验进行虚假数据识别并主动隔离恶意节点。理论分析和模拟测试表明CORE协议能够充分利用异构节点的上传能力,提供区分的下载带宽分配,同时提高全局范围的吞吐率,具有高度的扩展性、较高的吞吐率、较低的端到端延迟以及高效的容错性等,能够有效提供异构网络环境下快速数据分发服务。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• §1.1 快速数据分发概述
• §1.2 基于覆盖网的快速数据分发
• §1.3 覆盖网拓扑感知技术
• §1.4 覆盖网抽样技术
• §1.5 基于网络编码的数据分发技术
• §1.6 主要研究内容
• §1.7 论文组织结构
• 第二章 相关研究
• §2.1 覆盖网拓扑感知技术
• 2.1.1 集中式
• 2.1.2 分布式
• §2.2 覆盖网无偏抽样技术
• 2.2.1 随机行走理论
• 2.2.2 覆盖网无偏抽样
• §2.3 基于网络编码的组播技术
• 2.3.1 网络编码理论
• 2.3.2 基于网络编码的应用层组播
• 2.3.3 网络编码组播中的资源优化
• 第三章 容错自适应的网络坐标任意播研究
• §3.1 网络坐标任意播基本思想
• 3.1.1 用户角色划分
• 3.1.2 任意播查找过程
• 3.1.3 层次化网络嵌入
• 3.1.4 位置融合过滤器
• §3.2 基于坐标融合的网络坐标任意播方法
• 3.2.1 任意播建立过程
• 3.2.2 网络坐标计算
• 3.2.3 位置融合过滤器
• 3.2.4 网络坐标查询实现
• §3.3 理论分析与模拟测试
• 3.3.1 理论分析
• 3.3.2 模拟器构造及参数配置
• 3.3.3 模拟结果分析
• §3.4 小结
• 第四章 覆盖网中可扩展的无偏抽样研究
• §4.1 相关概念
• §4.2 基于随机行走无偏抽样的可扩展性理论分析
• §4.3 基于自适应随机行走的可扩展无偏抽样方法
• 4.3.1 代理随机行走
• 4.3.2 自适应的分布式随机行走修正过程
• §4.4 理论分析与模拟
• 4.4.1 理论分析
• 4.4.2 模拟与分析
• §4.5 小结
• 第五章 基于能力区分的pareto最优网络编码组播研究
• §5.1 系统模型
• 5.1.1 节点能力计算
• 5.1.2 基于能力区分的数据分发
• §5.2 能力感知的近似Butterfly网络构造
• 5.2.1 自适应分层
• 5.2.2 节点加入机制及拓扑结构维护
• 5.2.3 基于滑动窗口路由机制判定层次容量范围
• 5.2.4 理论分析
• §5.3 基于直方图的连续网络编码传输机制
• §5.4 pareto最优的速率分配机制
• 5.4.1 问题建模
• 5.4.2 梯度下降方法
• 5.4.3 理论分析
• §5.5 基于安全隔离的容错网络编码机制
• §5.6 模拟测试
• §5.7 小结
• 第六章 结束语
• 致谢
• 参考文献
• 攻读硕士期间发表的主要学术论文
• 攻读硕士学位期间参加的主要科研工作