虚拟计算环境中的高效覆盖网构建技术研究

论文摘要

基于互联网的虚拟计算环境（iVCE）是一种新型网络计算平台。iVCE以互联网资源的自主化为基础,以按需聚合与自主协同为核心机制,在开放的网络基础设施之上实现多种资源的共享与协同工作。互联网资源的成长性、自治性和多样性等自然特性给iVCE的资源聚合带来巨大的挑战。结构化Peer-to-Peer覆盖网（简称结构化覆盖网）具有可扩展、延迟低、可靠性高等优点,是iVCE应对上述挑战、实现资源按需聚合的重要途径之一。拓扑构建是结构化覆盖网的基础性关键技术,实现了覆盖网的动态维护与消息路由等基本功能。本文面向iVCE资源聚合的需求,对高效的结构化覆盖网构建技术进行研究。iVCE中的不同应用对下层覆盖网拓扑具有不同的要求,例如路由延迟低、容错特性好或负载平衡等。针对特定要求,现有研究通常选择某种特定的正则图设计专用的覆盖网拓扑构建方法,其设计过程较为复杂,重复工作量大。针对上述问题,本文在国际上首次提出一种适用于任意正则图的通用覆盖网拓扑构建技术:分布式线图（DLG）变换。DLG变换设计了一系列创新性的机制和算法,包括拓扑图统一描述、DL迭代、逻辑点合并与分裂以及高效路由等。理论分析表明,DLG变换具有良好的性能:令d、N0、D0分别为初始正则图的基、秩和直径,N为节点个数,则在应用DLG变换构建的覆盖网中节点出度为常数d,入度在1和2d之间,平均入度为d,网络直径小于2（logd N ?lo gd N 0 ?D 0?1 ）,节点加入/退出维护开销为?（ log d N）,每次节点加入/退出时最多有3d个节点需要更新路由表。与超立方体、多维花环或deBruijn图等静态拓扑图比较,Kautz图具有最优直径、最大连通度等良好特性。然而,由于动态维护的复杂性,目前还没有结构化覆盖网能够基于任意Kautz图K （ d , D）进行构建。本文应用DLG变换技术,提出一种基于Kautz图K （d , D ）的结构化覆盖网:DLG-Kautz（DK）。针对Kautz图的特点,DK设计了高效的资源命名算法、资源-节点匹配策略、容错路由算法以及节点动态加入/退出时的资源重分配机制等。理论分析与模拟结果表明,给定平均节点出度（ d ?2 ）,在现有的结构化覆盖网中DK的网络直径最小。本文分别基于C和Java实现了DK的原型系统。DK的消息路由功能提供了精确匹配的资源查询能力。然而,随着互联网技术的发展,越来越多的上层应用要求下层覆盖网能够提供更加复杂的资源查询能力。高效的分布式索引是实现低延迟、低开销、负载平衡的复杂查询的关键。针对上述需求,本文在DK的基础上提出一种支持复杂查询的分布式索引构建技术:平衡Kautz树（BK树）。BK树通过Z曲线实现了资源空间到节点空间的映射,并基于PHT技术设计了高效的资源信息索引结构。在BK树的基础上,本文进而提出一种支持动态负载平衡并且延迟有界的区间查询算法ERQ。无论查询区间的大小或资源属性个数的多少,ERQ都能确保在一定的延迟（logd N （2logd logd N ?1 ））内返回查询结果,从而证明了BK树的有效性。本文简要讨论了基于BK树实现其他复杂查询（如Skyline查询、聚合查询等）的方法。现有的结构化覆盖网通常采用扁平结构进行组织:所有节点都被理想地认为是同构的,并且所有消息都使用同一种路由算法进行路由。然而,实际大规模系统中的节点通常是异构的,在计算能力、信誉和稳定性等各方面都存在广泛差异。传统结构化覆盖网的扁平结构难以适应互联网资源的多样性特点。针对上述问题,本文在国际上首次提出一种支持路由控制的覆盖网分组构建技术,允许上层应用根据节点属性的差异对节点进行分组,进而支持在消息路由过程中采用各种灵活的路由控制策略,例如选择一组计算能力强的节点提供计算服务、或者在路由过程中选择一组可信节点作为中间节点等。在分组覆盖网的基础上,本文进而提出一种覆盖网分级构建技术,在多个组之间存在层次关系的情况下,能够以较小的开销在覆盖网中支持分级结构,例如互联网中的管理域结构等。与传统覆盖网比较,分组/分级覆盖网能够使上层应用在性能、可靠性和安全等多方面获益。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 虚拟计算环境概述
• 1.1.1 基本概念
• 1.1.2 面向资源聚合的覆盖网技术
• 1.2 Peer-to-Peer覆盖网概述
• 1.2.1 基本概念
• 1.2.2 结构化覆盖网与非结构化覆盖网
• 1.3 本文工作
• 1.4 论文结构
• 第二章 相关研究
• 2.1 结构化覆盖网
• 2.1.1 基于环的DHT
• 2.1.2 基于多维花环或立方体的DHT
• 2.1.3 基于Plaxton图的DHT
• 2.1.4 基于蝶网的DHT
• 2.1.5 基于跳表的DHT
• 2.1.6 基于deBruijn图的DHT
• 2.1.7 基于Kautz图的DHT
• 2.1.8 比较与分析
• 2.2 非结构化覆盖网
• 2.2.1 盲路由
• 2.2.2 提示性路由
• 2.3 本章小结
• 第三章 DLG变换：适用于任意正则图的通用覆盖网构建技术
• 3.1 引言
• 3.2 相关工作
• 3.2.1 基本概念
• 3.2.2 线图迭代
• 3.3 基本DL迭代
• 3.3.1 拓扑图统一描述机制
• 3.3.2 DL迭代与DL图
• 3.3.3 DL图的基本性质
• 3.4 逻辑点合并与分裂
• 3.4.1 DL+图
• 3.4.2 路由算法
• 3.4.3 DL+图的基本性质
• 3.5 基于DLG变换构建DHT 拓扑
• 3.5.1 节点加入
• 3.5.2 节点退出
• 3.5.3 讨论
• 3.6 本章小结
• 第四章 基于DLG变换的高性能覆盖网
• 4.1 引言
• 4.2 相关工作
• 4.3 DK设计
• 4.3.1 节点/资源命名
• 4.3.2 资源发布与搜索
• 4.3.3 资源重分配
• 4.3.4 理论分析
• 4.3.5 与其他基于DLG变换的DHT 的比较
• 4.4 模拟评估
• 4.4.1 路由延迟
• 4.4.2 拓扑维护
• 4.4.3 容错路由
• 4.5 原型系统
• 4.5.1 主要功能模块
• 4.5.2 API接口函数
• 4.5.3 动态维护处理
• 4.5.4 消息结构和类型
• 4.6 本章小结
• 第五章 支持复杂查询的覆盖网索引构建技术
• 5.1 引言
• 5.2 相关工作
• 5.3 BK树索引
• 5.3.1 多维资源空间到Z曲线的映射
• 5.3.2 Z曲线到DK 节点空间的映射
• 5.4 实现复杂查询
• 5.4.1 基于BK树实现区间查询
• 5.4.2 讨论：其他复杂查询的实现
• 5.5 模拟评估
• 5.5.1 概述
• 5.5.2 查询延迟
• 5.5.3 查询开销
• 5.5.4 节点度数
• 5.5.5 动态负载平衡
• 5.6 本章小结
• 第六章 支持路由控制的覆盖网分组构建技术
• 6.1 引言
• 6.2 相关工作
• 6.2.1 管理域DHT
• 6.2.2 缩减Chord
• 6.3 分组覆盖网
• 6.3.1 概述
• 6.3.2 数据结构
• 6.3.3 灵活路由
• 6.3.4 动态维护
• 6.3.5 理论分析
• 6.3.6 基于DK的分组覆盖网
• 6.4 分级覆盖网
• 6.4.1 路由表优化
• 6.4.2 理论分析
• 6.5 模拟评估
• 6.5.1 概述
• 6.5.2 路由表大小
• 6.5.3 PC路由延迟
• 6.5.4 组查找延迟
• 6.5.5 路径局部性和收敛性
• 6.6 本章小结
• 第七章 总结与未来工作
• 7.1 论文工作的总结
• 7.2 课题研究展望
• 致谢
• 参考文献
• 作者在学期间发表的学术论文
• 作者在学期间申请的专利和软件著作权
• 作者在学期间参加的主要科研工作
• 作者在学期间获得的主要奖励