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