基于Gossip的多源快速数据分发技术研究

论文摘要

快速数据分发是将数据源产生的数据在广域的范围快速分发至多个用户,是分布式环境中资源汇聚和共享的一项关键技术,并且随着网络技术的发展日益重要。而基于Gossip的快速数据分发技术,以其分发方法的简单性,灵活性,可扩展性,鲁棒性等特点而得到了广泛研究和应用。然而基于Gossip的快速数据分发面临着分发冗余量大,分发延迟时间长等问题,严重影响了数据分发效率。为支持高效的快速数据分发,对网络规模估计、带宽优化分配以及数据分发方法进行了深入研究。取得的主要研究进展如下:网络规模是数据分发系统中的基础信息,可以有效地辅助节点决策,降低分发冗余和分发延迟。在大规模动态的节点群体下,网络规模估计技术需要较强的自适应性和容错性。本文提出了基于随机行走的自适应网络规模估计方法RASE。RASE在节点加入或退出时发起随机行走过程以更新规模估计值,提高了更新过程的自适应性;随机行走过程利用已有的规模估计值迭代计算,降低了通讯开销和计算延迟;通过控制随机行走长度,实现计算精度和通讯冗余的高效折中;通过记录更新过程信息和备份节点规模估计值,处理失效节点,增强了方法的鲁棒性。理论分析和模拟测试表明,与已有的典型方法GBA相比,RASE在动态环境下具有更好的计算精度、自适应性、容错性、快速收敛性以及更小的通讯开销。高效的带宽分配方法能够提高数据分发的带宽吞吐率,保证节点公平性,降低分发延迟。针对已有带宽分配方法中带宽吞吐率、节点公平性、网络拥塞控制方面的不足,提出一种基于市场竞争机制的公平带宽分配方法FMBA。FMBA中节点以效用函数最大化为目标,采用带宽竞价方式分配带宽。请求节点根据资源提供者的带宽单价周期性选择最佳资源提供者,以增强自适应性,保证资源提供者的负载平衡;资源提供者根据带宽供需情况周期性更新带宽单价,以提高带宽吞吐率,避免网络拥塞;资源提供者根据资源请求者的竞价水平分配带宽,以避免节点恶意竞争;各个节点根据收益更新竞价策略,以保证节点公平性。理论分析和模拟测试表明,与已有的典型方法BT相比,FMBA具有更高的带宽吞吐率、自适应性以及较好的节点公平性。针对已有数据分发方法中分发冗余量大,分发延迟时间长的问题,提出一种基于Gossip先推后拉的快速数据分发方法GBFD。GBFD在分发前期采用基于推的Gossip数据分发方法,以降低分发冗余量,提高链路成功率;节点根据链路成功率采用基于随机行走的自适应网络规模估计方法RASE计算出推拉分界点,确定数据分发由主动推送方式转向主动请求方式的时机;在分发后期采用基于拉的Gossip数据分发方法,以降低分发延迟,保证数据分发方法的收敛性,并采用基于市场竞争机制的公平带宽分配方法FMBA优化带宽分配,提高带宽吞吐率。理论分析和模拟测试表明,与已有的基于推的数据分发方法CREW相比,GBFD具有较高的带宽吞吐率,较小的分发延迟和通讯冗余。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 快速数据分发
• 1.2.1 确定组播方法
• 1.2.2 概率组播方法
• 1.2.3 基于发布/订阅的方法
• 1.3 网络规模估计
• 1.4 带宽优化分配
• 1.4.1 基于非竞价博弈的带宽分配方法
• 1.4.2 基于竞价博弈的带宽分配方法
• 1.5 主要研究内容
• 1.6 论文组织结构
• 第二章 相关研究
• 2.1 基于 Gossip 快速数据分发技术
• 2.1.1 基于推的数据分发技术
• 2.1.2 基于拉的数据分发技术
• 2.1.3 基于推拉结合的数据分发技术
• 2.2 网络规模估计技术
• 2.2.1 基于随机行走的网络规模估计方法
• 2.2.2 基于反熵聚集的网络规模估计方法
• 2.2.3 基于标识密度的网络规模估计方法
• 2.2.4 基于跳步采样的网络规模估计方法
• 2.3 基于竞价博弈的带宽优化分配技术
• 2.3.1 收益最大化
• 2.3.2 社会福利最大化
• 2.3.3 公平性
• 2.4 本章小结
• 第三章 基于随机行走的自适应网络规模估计方法研究
• 3.1 基于随机行走的自适应网络规模估计方法描述
• 3.1.1 节点加入
• 3.1.2 节点退出
• 3.1.3 节点失效
• 3.2 基于随机行走的自适应网络规模估计方法性能分析
• 3.2.1 计算精度分析
• 3.2.1.1 参与随机行走节点的规模估计值期望
• 3.2.1.2 最后一次更新时的系统规模
• 3.2.1.3 误差分析
• 3.2.2 失效分析
• 3.2.3 通讯开销分析
• 3.3 模拟结果与分析
• 3.3.1 不同网络规模估计策略精度对比
• 3.3.1.1 节点动态加入
• 3.3.1.2 节点动态退出
• 3.3.2 鲁棒性和收敛性对比
• 3.3.3 不同网络规模估计策略通讯开销
• 3.4 本章小结
• 第四章 基于市场竞争机制的公平带宽分配方法研究
• 4.1 基于市场竞争机制的公平带宽分配方法描述
• 4.2 效用函数
• 4.3 竞价算法
• 4.3.1 最佳资源提供者选择策略
• 4.3.2 资源提供者带宽单价更新策略
• 4.3.3 分配带宽策略
• 4.3.4 购买能力更新策略
• 4.4 模拟结果与分析
• 4.4.1 带宽吞吐率
• 4.4.2 公平性
• 4.4.3 负载平衡性
• 4.4.4 自适应性
• 4.5 本章小结
• 第五章 基于 Gossip 的快速数据分发方法研究
• 5.1 基于 Gossip 的快速数据分发方法描述
• 5.1.1 基于推的数据分发
• 5.1.2 基于拉的数据分发
• 5.2 求解分界点
• 5.2.1 基于推的数据分发有效链路分析
• 5.2.2 基于拉的数据分发有效链路分析
• 5.2.3 确定分界点的时间
• 5.2.4 求解分界点算法描述
• 5.3 模拟结果与分析
• 5.3.1 下载完成时间
• 5.3.2 通讯冗余量
• 5.3.3 收敛性
• 5.4 本章小结
• 第六章 结束语
• 6.1 工作总结
• 6.2 研究展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果
• 攻读硕士学位期间参加的主要科研工作