分布式环境中的资源发现研究

论文摘要

构建分布式系统的目的之一是资源共享。从与因特网规模相似的网格,到基于无线技术的、不需要任何基础设施的移动自组网,它们的主要目的都是为了更多、更方便、更有效地共享资源。同时,分布式系统的普适化发展也使用户从科学家、工程技术人员扩展到商业金融用户,甚至普通的个人。在以资源共享为目的的分布式系统中,资源发现是一个不可或缺的部分。①资源发现是资源共享的基础。无论是从功能上,还是性能上,都是用户直接能感知并且十分看重的服务。②资源发现是很多应用的基石。好的资源发现服务能够产生许多新的应用,或是提高现有应用的性能、丰富其功能。③资源发现能为资源调度、资源使用收费等提供实现的手段和有力的支持。由于分布式环境的复杂性,资源发现面临许多困难。例如,在网格和移动自组网中,资源是异质的、自治的,同时也是动态变化的。其中,在网格中,资源的规模非常大,种类也非常多。而在部分连通的移动自组网中,节点之间可能没有同时存在的连接路径。这些现象使得资源发现问题非常具有挑战性。本文主要研究两个代表性的分布式系统――网格和部分连通的移动自组网――中的资源发现问题。资源发现问题由资源描述、资源信息组织、资源请求处理以及资源选择这四个子问题组成。本文从这四个方面着手,获得以下贡献。1)提出一种C/S与P2P相结合的网格资源发现框架VIRD。它充分利用物理网络的物理拓扑和逻辑拓扑,避免Overlay网络对延迟的错误估计。分层结构既能够提高查找效率,也具有很良好的可扩展性。2)提出一种基于群的部分连通的移动自组网中的资源发现框架。我们对资源信息进行合理地复制,对资源请求处理采用anycast查找,这些选择都有效地降低由于不连通性造成的较长的通信延迟。3)提出并解决移动自组网中资源发现服务器放置的问题。使用形式化方法分析资源发现服务器的放置问题,并为解决这个NP-hard问题提出两种近似算法。4)提出一种部分连通的移动自组网中的anycast路由算法。定义三种部分连通的移动自组网中anycast的语义模型,基于其中的CM模型,提出一种新颖的anycast路由度量（metric）――EMDDA。EMDDA利用不受控制的移动设备移动的随机特性,用概率的方法更准确地描述了实际的期望路由延迟,并给出相应的路由算法。通过实验证明了标准和算法的性能。

论文目录

• 摘要
• ABSTRACT
• 图目录
• 表目录
• 第一章 引言
• 1.1 网格简介
• 1.2 移动自组网以及部分连通的移动自组网简介
• 1.3 分布式环境中资源发现研究的意义
• 1.4 分布式环境中资源发现研究的挑战
• 1.5 设计目标
• 1.6 本文的主要贡献
• 1.7 论文的组织
• 第二章 相关工作
• 2.1 组成部分
• 2.1.1 资源描述
• 2.1.2 资源信息组织
• 2.1.3 资源请求处理
• 2.1.4 资源选择
• 2.2 相关工作
• 2.2.1 网格中的资源发现
• 2.2.2 P2P网络中的资源发现
• 2.2.3 移动自组网中的资源发现
• 2.2.4 其他分布式系统中的资源发现
• 2.3 小结
• 第三章 网格环境中的资源发现
• 3.1 Gnutella协议
• 3.2 Random Walk算法
• 3.3 VIRD资源发现框架
• 3.3.1 概述
• 3.3.2 资源描述
• 3.3.3 资源信息组织
• 3.3.4 资源请求处理
• 3.3.5 资源选择
• 3.4 性能分析
• 3.5 性能评价
• 3.5.1 VIRD结构可行性和有效性验证
• 3.5.2 VIRD总体资源发现性能评价
• 3.6 小结
• 第四章 部分连通的移动自组网中的资源发现
• 4.1 部分连通的移动自组网
• 4.2 资源发现框架
• 4.2.1 概述
• 4.2.2 资源描述
• 4.2.3 资源信息组织
• 4.2.4 资源请求处理
• 4.2.5 资源选择
• 4.3 群内RDA的放置
• 4.3.1 无线自组网中RDA的放置问题
• 4.3.2 相关工作
• 4.3.3 问题的形式化描述
• 4.3.4 近似算法
• 4.4 群间的anycast路由
• 4.4.1 部分连通的移动自组网中的anycast
• 4.4.2 相关工作
• 4.4.3 网络模型
• 4.4.4 anycast语义模型
• 4.4.5 EMDDA标准
• 4.4.6 基于EMDDA标准的anycast路由算法
• 4.5 性能评价
• 4.5.1 RDA放置的性能评价
• 4.5.2 群间anycast路由的性能评价
• 4.6 小结
• 第五章 结论及未来工作
• 5.1 本文工作总结
• 5.2 未来工作
• 5.2.1 网格中网络拓扑对资源发现算法的影响
• 5.2.2 网格系统中服务器失效后的恢复问题
• 5.2.3 部分连通的移动自组网中群间资源信息副本的放置问题
• 5.2.4 部分连通的移动自组网中的anycast路由
• 参考文献
• 致谢
• 作者简介