硕士学位论文-一种分布式资源定位机制研究.doc

学校代码 10254 密级 论文编号 上海海事大学上海海事大学 SHANGHAI MARITIME UNIVERSITY 硕士学位论文硕士学位论文 MASTER DISSERTATION 论文题目 一种分布式资源 定位机制研究 学科专业 计算机应用技术 作者姓名 夏振华 指导教师 史小宏 副教授 完成日期 二 一零年五月 学校代码 10254 密 级 论文编号 论文独创性声明论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成 果 论文中除了特别加以标注和致谢的地方外 不包含其它人或其 它机构已经发表或撰写过的研究成果 其它同志对本研究的启发和 所做的贡献均已在论文中作了明确的声明并表示了谢意 作者签名 日期 论文使用授权声明论文使用授权声明 本人同意上海海事大学有关保留 使用学位论文的规定 即 学校有权保留送交论文复印件 允许论文被查阅和借阅 学校可以 上网公布论文的全部或部分内容 也可以采用影印 缩印或者其它 复印手段保留论文 保密的论文在解密后遵守此规定 作者签名 导师签名 日期 摘 要 摘摘 要要 分布式系统由一系列分散的网络节点组成 在各个节点间进行资源和信息 的交流 最重要的问题之一就是资源的定位 这也是最难实施的机制之一 本文分析了国内外分布式资源定位研究现状与分布式资源定位的相关内容 包括现有的资源定位发现机制以及小世界模型概念 阐述了幂律和小世界模型 对资源定位机制的影响 我们提出了 CARLM Clusting And Agent Based Resource Location Model 模型 它以日本大阪大学的分布式框架 PIAX 为基础 CARLM 是基于网络拓扑的资源 定位模型 在覆盖网络中利用聚类技术把节点分成多个兴趣簇 每个兴趣簇是 一个逻辑类似的小组 并给出了 Cluster 的形成 维护策略以及本地缓存信息 在 CARLM 模型的基础上扩展一个基于聚类和 Agent 的分布式资源定位算 法 FCB 网络内任一结点在发起资源查询请求时 搜索 Agent 首先查看结点所 在簇内其他结点是否能满足查询请求 使用泛洪查询方法 当簇内查询得不到 满足时 簇内结点通过转发结点向簇外结点发送资源请求消息 并使用蚁群算 法 泛洪算法和蚁群算法配合使用 目的是在 Agent 迁移中实现进一步的性能 提高 泛洪在簇内可以实现快速的资源发现而不会产生太多的信息量 聚类使 得关联节点间逻辑距离缩短 蚁群算法使得 Agent 向着资源丰富的节点移动 在簇外对迁移路径进行选择时 又利用了概率选择的方法 使搜索 Agent 向着 资源丰富的节点移动的同时又不至于使某条资源丰富的路径堵塞 为了验证本文提出的模型和算法 我们在 Peesim 仿真平台和 AgentSpace 上 进行了资源定位模拟实验 对泛洪算法和 FCB 以及没有利用蚁群算法的 FCB 进行了查询信息量 平均查找成功率以及平均跳数的性能的对比 实验表明算 法 FCB 更有效 关键词 资源定位 小世界 CARLM FCB 蚁群算法 移动 Agent ABSTRACT ABSTRACT The distributed system consists of a number of decentralized network nodes that are capable of sharing resources and informations One of the most important functions in distributes system is the location of resources and it is one of the hardest targets to achieve In this thesis we firstly outlines the current research status about the resource location of distributes system at home and abroad and then introduced the distributed resources location related content including the existing resource location discovery mechanism and the concept of small world model and describe the impact on the resource location mechanism which the power law and small world model have We propose CARLM model Clusting And Agent Based Resource Location Model which is bases on the distributed system framework PIAX that is proposed on the University of Osaka Japan CARLM is based on the network topology which uses clustering technology to put nodes into several clusters in the overlay network each cluster is a logically similar groups and then we describe the Cluster formation maintenance strategy and the local cache information we expand a clustering and Agent based distributed resource location algorithm FCB when any node within the network launch a request the search Agent examines other nodes in the same Cluster to see whether the nodes are able to satisfy the query request or not in which uses the flooding method When the inquiry is not satisfied in cluster the forward node sends the resource request message to the node outside the cluster in which uses the ant colony algorithm The conjunction of Flooding algorithm and ant colony algorithm is to achieve the further performance improvement in the Agent migration The Flooding can locate the resource quickly without creating too many messages in the cluster Clustering makes the logical distance between correlated nodes shorter Integrating ACO is expected to ABSTRACT strengthen the connections to resource rich nodes When selecting the link between nodes we use probabilistic selection to make the Search Agent migrate to the resource rich nodes without rendering the path of a certain resource rich link block In order to verify the proposed model and algorithm we make the simulated experiment of resource location in PeerSim and AgentSpace and compare our approach FCB with flooding algorithm and FCB without ACO in terms of Querying traffic Average Success rate and Average Hop count And the experiment shows that the FCB algorithm is more effective Keywords Resource Discovery Small World CARLM FCB ACO Mobile Agent 目 录 目 录 第一章第一章 绪论绪论 1 1 1 1 分布式资源定位研究现状 1 1 1 1 资源定位发展过程 1 1 1 2 国内研究情况 2 1 1 3 国外研究情况 3 1 2 本文研究工作 4 1 3 本文的组织结构 5 第二章第二章 分布式网络资源定位分布式网络资源定位 7 7 2 1 资源定位 7 2 1 1 组成部分 7 2 1 1 1 资源描述 7 2 1 1 2 资源信息组织 8 2 1 1 3 资源请求处理 10 2 1 1 4 资源选择 10 2 1 2 资源发现的要素和类型 11 2 1 2 1 网格中的资源发现 12 2 1 2 2 P2P 网络中的资源发现 12 2 1 2 3 移动自组网中的资源发现 14 2 1 2 4 其他分布式系统中的资源发现 14 2 2 现有资源定位技术 15 2 2 1 集中式发现机制 15 2 2 2 分布式结构化发现机制 16 2 2 3 半分布式发现机制 17 2 2 4 基于移动 Agent 的分布式资源定位方法 17 2 2 5 分布式非结构化发现机制 18 2 3 小世界模型 19 2 3 1 小世界和幂律特性 19 目 录 2 3 2 小世界拓扑生成方法 21 2 3 3 小世界模型对资源定位技术的影响 22 2 3 4 基于小世界模型的资源定位策略 23 2 4 本章小结 23 第三章第三章 分布式资源定位模型分布式资源定位模型 CARLM 2424 3 1 CARLM 设计思想 24 3 2 CARLM 系统模型 25 3 3 覆盖网络 27 3 3 1 节点关联度定义 28 3 3 2 Cluster 形成 29 3 3 3 Cluster 维护 32 3 4 本地缓存信息 33 3 4 1 节点本地 IA 信息 33 3 4 2 节点管理表 NMT 33 3 4 3 历史路径信息 34 3 5 本章小结 34 第四章第四章 CARLMCARLM 模型中资源定位机制模型中资源定位机制 FCBFCB 3535 4 1 蚁群聚类思想 35 4 1 1 Clusting 35 4 1 2 Ant Colony Optimization 36 4 2 资源定位机制 FCB 38 4 2 1 FCB 算法 39 4 2 2 簇内路由算法 40 4 2 3 簇外路由算法 41 4 3 CARLM 中资源搜索策略 44 4 4 算法分析 46 目 录 4 5 本章小结 47 第五章第五章 资源定位实验资源定位实验 4949 5 1 实验环境 49 5 2 实验执行 50 5 3 算法性能比较 54 5 3 1 查询信息量 54 5 3 2 平均查找成功率 55 5 3 2 平均跳数 56 5 4 本章小结 57 第六章第六章 总结与展望总结与展望 5858 6 1 本文工作总结 58 6 2 展望 59 致谢致谢 6060 参考文献参考文献 6161 攻读学位期间发表的学术论文攻读学位期间发表的学术论文 6464 第一章 绪论 1 第一章 绪论 1 11 1 分布式资源定位研究现状分布式资源定位研究现状 1 1 11 1 1 资源定位发展过程资源定位发展过程 随着互联网在世界各地进行快速传播 它经常被用来人类的各种交互活动 在各种应用软件间进行的用户交互要求软件能够与网络社区进行交流信息和资 源 传统客户机浏览器模式仅能体现真实世界的情况 如视频流媒体服务的出 现 在服务器上进行密集的访问会带来瓶颈问题 对等网络系统可以提供一个 解决这个问题的方法 分布式系统是由一系列分散的网络节点组成的 这些节 点能够分享资源 而不需要中央服务器的支持 已经存在很多应用 如 IP 电话 内容交付网络 CDN 和分布式计算都采用了分布式技术 并把它运用到基本的 通信系统中 分布式系统在各个节点间进行资源和信息的交流 分布式系统包 括一个覆盖网络 其中节点可以相互交流并分享彼此的资源 在这里 资源 指的是由网络节点提供的各种服务 分布式系统中最重要的问题之一就是资源的定位 而这也是最难实施的机 制之一 Napster 公司通过提供索引服务的中央服务器来解决这个问题 1 但是 这种服务器的问题是 如果出现错误就可能使整个网络瘫痪 因此 不含有任 何中央服务器的分布式系统是当前的分布式系统发展领域的研究重点 著名的分布式系统 Gnutella 2 采用消息 Flooding 来定位资源 这种系统的 优点是简单 但它对于大型网络系统是不切实际的 因为仅仅 Flooding 的资源 发现消息就很容易使整个网络达到饱和状态 为了解决这个问题 分布式哈希 表 DHT 被提出并使用 3 4 5 6 虽然 DHT 是最有前途的方法之一 并且它能 提供对分布式系统的快速资源查找效率 计算复杂度为 O log n 但是它具有下 列缺点 1 由于 DHT 的基本机制是映射关键字到节点 所以很难找到基于多个 关键字的对象或对象中的内容 2 是很难找到与给定的一个关键字或一组关键 字相关的多个节点 换句话说 基于 DHT 的资源查找方法过于僵化导致处理不 够灵活和查询不够智能 为了减轻 DHT 系统的僵化 一些分布式系统利用信息 Flooding 进行对象 第一章 绪论 2 的查找 以补充 DHT 的不足 7 由于消息 Flooding 会产生密集的通信量 它对 那种间歇性网络连接的移动通信环境是不适合的 由于 DHT 在拓扑结构的维护上存有严重的问题 目前对分布式系统的研究 侧重于控制和约束信息 Flooding 技术 整个 Gnutella 系统采用了一个叫做动态 查询 DQ 的受控 Flooding 技术 其中 DQ 技术预测了一个合适的生存期 TTL 值 以减少网络流量负载 8 Jian 等提出了一个加强的 DQ 技术 它采用一种置信区间的方法 使它能 够进一步减少网络流量负载 9 另一方面 移动 Agent 系统最近在各个领域都成为热门 10 在分布式系统 中移动 Agent 具有以下优点 1 移动 Agent 把节点之间的可能交互打包在一起 并把必要的处理方法传递到所需节点所在地 使得他们本地化 2 移动 Agent 是异步的 能够使这个产生移动 Agent 的节点完全可以执行不同的任务 甚至 暂时离开网络 3 移动 Agent 是独立自主的 当他们在网络中运行的同时就可 以了解网络 11 自治 Agent 在智能机器人控制系统 12 13 14 中发挥主要作用 移动 Agent 可 以引进所需的功能并能自主履行任务 并可以使通信量减少 因此 自然而然 的 在分布式系统中我们不仅利用静态 Agent 而且还要利用动态 Agent 以提 供灵活的搜索 移动 Agent 被期望可以减少查询信息的数量 1 1 21 1 2 国内研究情况国内研究情况 Maze 15 是北京大学网络实验室开发的一个中心控制与对等连接相融合的对 等计算文件共享系统 在结构上类似 Napster 对等计算搜索方法类似于 Gnutella 网络上的一台计算机 不论是在内网还是外网 可以通过安装运行 Maze 的客户端软件自由加入和退出 Maze 系统 每个节点可以将自己的一个或 多个目录下的文件共享给系统的其他成员 也可以分享其他成员的资源 Maze 支持基于关键字的资源检索 也可以通过好友关系直接获得 Granary 16 是清华大学自主开发的 P2P 存储服务系统 所谓 P2P 存储服务 系统是指存储服务的提供者在 Internet 中部署一定数量的存储服务器 为用户 提供数据存储服务 确保数据的可靠性 可用性 安全性和访问效率 存储服 第一章 绪论 3 务的使用者按照所存储数据的容量和质量付费 它以 对象 格式存储数据并 且支持属性级的数据查询 AnySee 17 是华中科大设计研发的视频直播系统 它采用了一对多的服务模 式 支持部分 NAT 和防火墙的穿越 提高了视频直播系统的可扩展性 同时 它利用了近播原则 分域调度的思想 使用 Landmark 路标算法直接建树的方 式构建应用层上的组播树 克服了 ESM 等一对多模式系统由联接图的构造和维 护带来的负载影响 WonGoo 18 是中科院计算所研制的一套 P2P 技术平台 该平台主要为信息 安全 网格计算提供支撑技术和实验环境 同时 WonGoo 的基础部件将在开发 完善之后以开放源代码的方式向社会公开 WonGoo 主要包括两个方面的特色 功能 具有强匿名性的 P2P 通讯 WonGoo Link 基于内容查找的 P2P 资源共 享 WonGoo Search 可以在这两个功能的基础上搭建各种特色化的 P2P 应用 目前相关的应用还没有具体实现 WonGoo Link 与 WonGoo Search 可以分别独 立构造并搭建各自的应用 同时 WonGoo Search 底层通讯也可以采用 WonGoo Link 协议来实现更安全的应用 基于 IPV6 的 P2P 内容存取应用系统 19 这是北京大学 清华大学 上海 交通大学 浙江大学 华中科技大学 华南理工大学 北京世纪鼎点软件有限 公司共同承担的国家 CNGI 项目的一部分 它主要研究基于智能节点弹性重叠 网络技术的内容存取应用中间件系统 在 CNGI 上建设可管理 可控制和可运 营的智能节点弹性重叠网络 开发内容存取类应用 1 1 31 1 3 国外研究情况国外研究情况 从国外公司研究来看 Microsoft 公司 Sun 公司和 Intel 公司投入较大 Microsoft 公司成立了 Pastry 项目组 主要负责分布式计算技术的研究工作 目 前开发了基于 Pastry 的多种应用 包括 SCRIBE PAST SQUIRREL 等 在新 一代的 Windows Vista 操作系统中 也增加了最新的研究成果来支持协同工作 标注 1 在 2000 年 8 月 Intel 公司宣布成立分布式 P2P 工作组 正式开展 P2P 的研究 工作组成立以后 积极与应用开发商合作 开发应用平台 2002 年 Intel 发布了 Net 基础架构之上的 Accelerator Kit P2P 加速工具包 和 P2P 安 第一章 绪论 4 全 API 软件包 从而使得微软 NET 开发人员能够迅速地建立 P2P 安全 Web 应 用程序 IBM 公司也开展了基于 P2P 技术的研究 提出了 Smart Networking 另外 IBM 公司大力支持的网格计算 Grid Computing 与 P2P 计算在许多方面研 究类似 Sun 公司以 Java 技术为背景 开展了 JXTA 项目 20 JXTA 是基于 Java 的 开源分布式 P2P 平台 任何个人和组织均可以加入该项目 因此 该项目不仅 吸引了大批研究人员和开发人员 而且已经发布了基于 JXTA 的即时聊天软件 包和搜索引擎 JXTA 定义了一组核心业务 认证 资源发现和管理 在安全 方面 JXTA 加入了加密软件包 允许使用该加密包进行数据加密 从而保证 消息的隐私 可认证性和完整性 在 JXTA 核心之上 还定义了包括内容管理 信息搜索以及服务管理在内的各种其它可选 JXTA 服务 在核心服务和可选服 务基础上 用户可以开发各种 JXTA 平台上的分布式应用 1 21 2 本文本文研究工作研究工作 第一 针对传统分布式资源定位存在的一些问题 我们在日本大阪大学的 PIAX 框架基础上改进了一种基于聚类和 Agent 的分布式资源定位模型 CARLM 该模型划分为物理网络层 覆盖传输层 多覆盖层 信息发现层 安 全机制层 Web Service 层以及 Agent 层 每层都负责各自不同的功能 很好的 适应了资源发现模型的设计原则 它是基于网络拓扑的资源定位模型 在覆盖 网络中利用聚类技术把节点分成多个兴趣簇 每个兴趣簇是一个逻辑类似的小 组 并给出了 Cluster 的形成 维护策略 以适应动态变化的网络环境 第二 我们在框架 CARLM 的基础上提出了资源定位算法 FCB 网络内任 一结点在发起资源查询请求时 首先查看结点所在簇内的其他结点是否能满足 查询请求 使用到泛洪方法查询 当簇内查询得不到满足时 结点通过转发结 点向簇外结点发送资源请求消息 使用蚁群算法 ACO 其中在簇外进行邻居节 点选择时 利用 LNRR Logical Nearest And Resource Richer 算法来选择那些逻 辑最近并且资源相对丰富的节点 第三 当一个 Agent 找到资源丰富的节点时 它加强通往这个节点的路径 信息 并减弱其他路径上的信息素 以便进一步提高效率 加强通往一个理想 第一章 绪论 5 节点的路线 是通过运用先前 Agent 的信息素完成的 这种信息素可以引导成 功的 Agent 使得他们很容易到达节点 当进行路径选择时 我们并不是选择 信息素最高的路径 因为那样很容易造成路径交通堵塞 我们的选择策略是用 概率的方法进行迁移 既保证了资源定位的高效性又不会造成交通堵塞 在这 个新系统中 我们的搜索 Agent 执行节点聚类的方法并间接被信息素指引 跟 以前的系统相比提高了搜索效率 第四 对算法进行模拟实验 它利用了仿真软件 PeerSim 以及移动 Agent 环境 AgentSpace 并与泛洪机制 不含 ACO 的 FCB 算法进行了性能对比 其 中主要从产生的信息量 查询成功率以及平均跳数这三方面进行对比 实验结 果表明本文算法 FCB 有比较明显的性能优势 1 31 3 本文的组织结构本文的组织结构 第一章 绪论 本章主要介绍分布式资源定位研究背景及意义 并介绍了国内外在分布式 资源定位领域的研究现状 然后给出了本文的研究以及组织结构 第二章 分布式网络资源定位 本章介绍了分布式网络资源定位的相关内容 包括资源定位的概念 现有 的资源定位机制以及小世界模型概念 第三章 分布式资源发现框架 CARLM 本章介绍了我们提出的分布式资源定位模型 CARLM 并介绍了框架各层 的功能特点 CARLM 是基于网络拓扑的资源定位模型 在覆盖网络中利用聚 类技术把节点分成多个兴趣簇 每个兴趣簇是一个逻辑类似的小组 并介绍了 Cluster 的形成 维护策略以及本地缓存信息 第四章 资源发现算法 FCB 本章提出了针对 CARLM 模型的智能高效资源定位算法 FCB 我们还描述 了聚类和蚁群优化 ACO 算法的技术 它们对资源发现效率的提高有很大帮助 网络内任一结点在发起资源查询请求时 首先查看结点所在簇内的其他结点是 否能满足查询请求 使用泛洪查询方法 当簇内查询得不到满足时 结点通过 转发结点向簇外结点发送资源请求消息 使用蚁群算法 ACO 第一章 绪论 6 第五章 资源定位实验 本章主要对算法进行模拟实验 它利用了仿真软件 PeerSim 以及移动 Agent 环境 AgentSpace 并与泛洪机制 不含 ACO 的 FCB 算法进行了性能对比 其 中主要从产生的信息量 查询成功率以及平均跳数这三方面进行对比 实验结 果显示本文算法 FCB 有比较明显的性能优势 第六章 总结与展望 对全文进行总结工作 并就本文进一步的研究工作进行了相应的讨论 第二章 分布式网络资源定位 7 第二章 分布式网络资源定位 2 12 1 资源定位资源定位 资源定位发现机制是关系到广域分布式环境中资源共享与协同工作效率的 关键 在 Web 服务 计算网格和 P2P 技术中 都需要对这个问题进行深入的研 究 资源是一种具有能为外界所感知的值的东西 包括设备 信息和服务 比 如 文件目录或一系列记录其它的主机结点地址的目录可以是资源 也可以是 来自同一个特定类别的文件 文字文档 音乐文件 电影片段等 一段可执行 代码也可以是资源 另外资源还可以包括硬件设备 如传真机 打印机 路由 器等 2 1 12 1 1 组成部分组成部分 2 1 1 12 1 1 1 资源描述资源描述 资源描述是指提供给用户来表述自己所需资源的方式 而用户对所需要的 资源的描述可以作为资源请求的一部分 用来进行资源的查找 它影响到资源 信息的组织和描述 同样也影响到资源提供者将要把资源的哪些信息发布出去 资源描述大体分为四大类 第一类资源定位发现系统中 为每个资源分配 一个全局唯一的名字 并且用它进行描述资源 也就是每个资源描述都唯一对 应一个确定的资源 比如说 PC 机的 IP 地址等 在第二类资源定位系统中 为每一类资源分配一个全局唯一的名字 当用它来描述资源时 用户所指定的 是一类资源中的任意一个 例如在 P2P 系统中 所有相同的文件都有同样的名 字 在第三类资源定位系统中 除了每类资源应该具有全局唯一的名字之外 还需要一些属性 类的名字加上属性共同描述用户对资源的需求 例如 Globus 的 RSL 21 在第四类系统中 在资源描述中增加了语义信息 所以它可以进行 模糊匹配查询 这四种类型系统的描述能力呈依次增强的趋势 可以说前一种 第二章 分布式网络资源定位 8 是后一种的特例 例如 在第二种系统中 把每一个资源都看成是一类 同时 赋予它一个类名 那么这个类名就是所有资源全局唯一的名字 具体选用哪种 资源描述方法 这取决于系统中资源的具体类型和用户的需求 例如文件共享 系统中 用文件名来描述用户需求就已经足够了 而在网格系统中 共享的资 源由于比较复杂 比如计算资源等等 用户就需要指定所需要资源的多种属性 比如主机的内存大小 或者是安装了某种特定的软件 2 1 1 22 1 1 2 资源信息组织资源信息组织 资源信息组织指资源信息是如何分布并存储在网络中的 它具体包括节点 间的 overlay 是如何进行构造的 资源信息是如何进行传播的 以及是存储在哪 些节点上的 其中资源信息的传播与存储是 offline 的 与具体请求的执行无关 它可以看成是一种预处理 可以增强定位搜索的性能 资源信息的组织可能受 到很多因素的影响 比如 带宽的限制 节点对消息的处理能力和节点的负载 能力 安全或者管理策略 网络的物理拓扑等等 所以 overlay 网络只是实际 物理可连通的网络的一个子网 例如 跟一个 Gnutella 节点在某一时间知道的 peer 数量 几百个 相比 它正在使用的连接是很少的 平均连接值少于 10 个 2001 年五月测量的平均值为 3 4 22 在相同的 overlay 网络上 可以有不同的 资源信息传播方式和存储方式 Overlay 网络拓扑大体可分为以下几类 如图 2 1 所示 集中结构 所有的资源信息都存储在同一个节点上 并且所有的资源信息 都注册到这一个节点 而且所有的查找也都在该节点上进行 之所以这样做 是因为定位查找的通信开销仅限于中心节点和请求者之间 并不会对其他的节 点造成负担 这样既减小了复杂度 又降低了开销 如果在请求负载较轻的情 况下 在网络延迟远远大于计算处理速度的现在 也许可以降低请求的响应速 度 但是 如果网络规模很大 注册 更新以及查找的所有请求都会汇聚到这 一个点上 会使它的网络负担非常重 也就难以达到预期的速度和性能 flat 结构 亦即 P2P 的方式 在这种结构下 所有的节点都是平等的 它 们所存储的信息量都是一致的 例如 它们都只是存储本地的信息 或者是负 责一部分资源空间的信息 第二章 分布式网络资源定位 9 层次性结构 亦即树形方式 整个网络分为两层或者更多层 同一层中的 节点之间彼此没有连接 下层节点都对应于一个或多个上层节点 上层节点都 对应一个或多个下层节点 P2P 与层次性结合的结构 网络中每层的节点都是对等的 并用一定的拓 扑结构相连 下层节点对应一个或者多个上层节点 同样上层节点对应一个或 者多个下层节点 如果只有一层的话 那么这种混合结构也就退化成了 flat 结 构 如果同一层之间的节点间彼此没有连接 那么这种混合结构就退化成为了 层次性结构 a 集中结构 b flat 结构 c 树形结构 d 混合结构 图 2 1 Overlay 网络的拓扑 上面四种结构的复杂性依次增加 需要维护的信息也是依次增多 维护结 构所需要的开销也依次增大 资源信息存储可以有以下几种方式 无信息的复制 每个节点只保存自己本地的资源信息 比如在 Gnutella 中 这种存储方式 多数采用 flat 的 overlay 拓扑 第二章 分布式网络资源定位 10 均匀信息复制 每个节点只负责资源空间中的一部分 每个节点都把自己 的资源信息注册到某些特定的节点上 例如 在有结构的 P2P 系统中 每个节 点都只负责一部分资源空间 并且所有的资源信息都均匀的分布在各个节点上 还存在一种非常极端的情况 就是每个节点都负责全部的资源空间 也就是资 源信息在所有节点间进行完全复制 比如因特网上的域内路由算法 链路状 态路由算法 就是一个例子 集中式信息复制 只有一部分特定节点负责存储资源信息 每个节点都将 自己的资源信息注册到一个或者多个专门负责存储资源信息的节点中 在极端 情况下 所有节点都把资源注册到一个节点 Napster 和 Matchmaker 23 都是这 样做的 在这三种信息的存储方式中 对存储节点的要求依次增加 第一种方 式没有信息的注册和更新的开销 第二种和第三种的开销因具体情况而不同 资源信息的组织对请求处理的过程影响是很大的 overlay 的拓扑决定着请求所 走的路径 资源信息存储极大的影响着请求的处理流程 2 1 1 32 1 1 3 资源请求处理资源请求处理 资源请求处理可以分为两部分 本地部分和远程部分 本地部分就是指在 本地信息中进行查找 并处理聚合请求 例如 有的请求同时请求 A 资源和 B 资源 那么我们可以把它分解成两个独立的请求 分别加以对待 或者是实施 本地策略 比如丢弃一些不符合本地的管理策略的请求 远程部分指的是请求传播的规则 在很多系统中 请求传播的规则与资源 信息的组织方式是密切相关的 比如 在 CAN Chord Tapestry 和 Pastry 中 请求传播规则就是由所使用的分布式哈希表以及资源空间组织决定的 但是在某些无结构的系统中 选择请求传播规则的自由度就变得大很多 比如 在文献 24 中 它们都采用了各种不同的策略 将请求发送给不同数量的 邻居 并且可以确定如何选择邻居 2 1 1 42 1 1 4 资源选择资源选择 资源选择是从那些满足用户需求的一组资源中按照一定的标准选择实际可 以为用户服务的资源 比如使用户费用最低 或者系统性能最高等等 在资源 第二章 分布式网络资源定位 11 发现的过程中 系统可以根据自己的设置做出一些选择 但那应该是一些简单 并且通用的标准 而那些针对用户需求的资源选择可以更复杂 更具体 更专 业 资源选择可以在资源发现过程中进行 也就是可以有选择的返回符合条件 的资源 也可以在靠近客户端的地方集中进行 也就是可以把所有满足条件的 资源都返回 然后从中选择一些更适合的 2 1 22 1 2 资源发现的要素和类型资源发现的要素和类型 根据文献 25 所述 设计一个通用的资源发现服务需要考虑以下几个方面 1 服务提供者 service provider 可以采用第三方服务 third party service 的 方式实现资源发现服务 即把提供资源发现服务的实体与资源提供者和使用者 分开 比如目前 web 上的搜索服务以及 DNS NaPster 等 例如 作为专门的 web 搜索服务提供者 Baidu 搜集 Web 上的大量页面 并编制一定的索引 通 过门户网站向用户提供网页搜索的服务 与之相对的另外一种形式是完全分布 genuinely distributed 的形式也就是 P2P 的形式 即资源发现服务分布在所有资 源提供者与使用者上 并没有集中或协调机构 例如文件交换系统 Gnutena 中 就不存在集中的全局资源索引结点 各个参与结点只了解本地的文件资源 文 件搜索则依赖于结点间广播式 或随机 的扩散搜索请求 需要指出的是 以第 三方服务形式所实现的资源发现系统同样可以是分布式的 例如 DNS 系统按照 树形结构组织分布在各个地方的域名服务器中 但是这些分布的服务器处于资 源发现服务提供者的统一管理中 而在完全分布的实现形式下 并没有统一的 管理和协调者 资源发现则依赖于各个参与结点之间的交互 2 网络构造方式 Construction 在一般的情况下 可以用一个图来表示分 布式资源定位发现系统中涉及的各个结点间的交互关系 对应于底层通信网络 之上的覆盖网络 overlay network 结点间的边代表两个结点间的交互关系 构 造覆盖网络的基本方法有两种 手工配置和自组织 或者是混合形式的 例如 DNS 系统基本依靠手工配置来维护各域名服务器之间的关系 而在 Gmitena 系 统中 各参与结点实现了自组织 各结点根据本地知识独立调整邻居结点 3 入网的预先知识 Foreknowledge 分布式资源定位发现系统中的每个结 点在加入前需要了解系统的一些相关信息 这些信息往往与网络的构造方式有 第二章 分布式网络资源定位 12 关系 例如在 Gnutella 系统中 加入的结点需要了解网络中任意一个活动结点 的地址 以完成提交加入请求 4 网络结构 Aichitecture 指分布式资源发现系统中各节点形成的覆盖网 络的拓扑结构 5 资源注册 ResourceRegistration 指资源信息在哪些节点进行注册 及 其更新过程 6 查询路由 QueryRouting 指查询请求的扩散与路由方式 2 1 2 12 1 2 1 网格中的资源发现网格中的资源发现 Globus Toolkit MDS 26 是一种网格环境中的资源发现解决方案 最开始 它使用的是集中式的方法 随着资源和用户数量的增长 它也衍变成了分布式 的结构 在 MDS 2 中 网格是由多个信息提供者组成的 这些信息提供者可以 根据注册协议 GRRP Grid Registration Protocol 把这些信息源注册到集成目录服 务器 aggregate directory server 信息提供者能够提供有关网格实体的详细的 动态的信息 集成目录服务器则提供专业的 与 VO 相关的 联合的资源或者 服务的视图 GRIP 协议是用来访问实体信息的协议 它支持 discovery 和 enquiry discovery 就是搜索的功能 例如 一个信息提供者维护着一组工作站 的信息 一个用户想要在这个信息提供者上进行一次搜索 以获取满足某个条 件的结果 而 enquiry 是直接的查找 lookup 信息 用户提供资源的名字 信息 提供者返回该资源的描述 2 1 2 22 1 2 2 P2PP2P 网络中的资源发现网络中的资源发现 最近倍受关注的 P2P 文件共享是一种基于名字 每种文件都对应一个全局唯 一的名字 的资源查找方式 最早的 P2P 系统是 Napster 它有一个中央索引服务器 central index server 资源提供者将自己的资源 文件 信息注册到这个服务器上 需要资源的用户也 到这个服务器上进行查找 找到满足要求的资源后 就直接从资源提供者那里 下载 此时 资源发现是集中式的 资源的使用是 P2P 的 后来出现了很多 P2P 系统 大致可以分为两类 无结构的 unstructured 和 第二章 分布式网络资源定位 13 有结构的 structured 无结构的 P2P 系统 比如 Gnutella 和 Freenet 有结构的 P2P 系统是基于分布式哈希表来构造搜索效率很高的 overlay 的 例如 CAN Chord Tapestry 和 Pastry Gnutella 的基本机制就是 Flooding 泛洪 对于不能回答的查找请求 每个节点都转发给它所有的邻居 直到超出时限 也就是 TTL time to live 过期 请求会沿着来时的轨迹 一个节点一个节点的返 回到初始的请求者 这种方法的好处是很简单 每个节点都只维护自己的邻居 列表 没有其他的信息需要交换和维护 缺点就是较好的搜索性能是以较大的 网络流量为代价的 为了解决 Flooding 算法网络开销比较大的问题 提出了 random walk 27 算 法 Random walk 算法就是当消息不能在本地被满足 需要转发出去的时候 从所有的邻居节点中随机的选取一个作为下一步 将请求消息传递过去 而不是 转发给所有的邻居 直到找到合适的资源 Random walk 能够降低消息开销 但是用户能够感知的成功搜索的延迟也会大幅度增大 Freenet 中的文件发现机 制使用的是基于动态路由表的请求传播方法 它既包括文件管理 又包括文件 查找机制 受欢迎的文件就被复制 放到离用户较近的地方 而最不受欢迎的 最终会消失 Freenet 中对资源 文件 本身进行了复制 但是很多资源是不可以 复制的 比如计算资源 或是出于安全 存储容量等因素不能进行复制的数据 那么这种方法就不适用了 有结构的 P2P 系统的共同之处在于使用了分布式哈 希表 DHT 每个资源 ID 都通过 DHT 被映射到一个节点 ID 关于该资源的信 息都将存放于该节点或者具有和该节点 ID 最相近 ID 的节点上 如果网络规模 很大 节点数量很多 一个节点不可能记录下所有节点 ID 和它的物理地址 IP 地址 所以 在大规模的 P2P 系统中都使用了各种 overlay 网络拓扑来使得每 个节点都存储少量的信息 但是又能通过某些路由机制找到任意一个节点 有结构的 P2P 系统 都是在一个有结构的 overlay 上传播信息 有类似的 成员协议和请求处理过程 区别则在于节点空间的定义不同 因而由于节点的 不断变化 维护这个定义空间的方法也不同 在 Chord 中 节点的空间是一个 环 CAN 中是一个 d 维的坐标空间 而在 Pastry 和 Tapestry 中是 Plaxtonmesh 28 向节点空间中的相邻节点不断发 我还活着 的消息 可以看 作是一种预处理 第二章 分布式网络资源定位 14 使用 DHT 的好处就在于进行资源处理时 只通过分布式哈希函数就能够确 定存放资源信息的节点的 ID 而不是像在无结构 P2P 系统中那样 需要通过遍 历来进行查找 在后面我们提出的部分连通的移动自组网中的资源发现框架中 因为群间的消息传递延迟比较长 遍历式的查找方式延迟会非常大 难以接受 我们就会使用 DHT 来实现确定性的资源查找 2 1 2 32 1 2 3 移动自组网中的资源发现移动自组网中的资源发现 由于移动自组网的网络拓扑是不断变化的 所以相对于因特网上验证有效 的集中式 静态的方法 分布式的 动态控制的机制更适合移动自组网 文献 29 中提出了一种基于 DA Discovery Agent 的 QoS aware 的移动自组网 中的资源发现框架 DA 会负责目录信息的组织和查询以及动态域的形成 初 始时 网络中的节点会 选举 出一些 DA 每个节点都会有自己的 home DA home DA 会根据资源的属性哈希出一个索引号 再把资源按照索引号注 册到一个或多个其他 DA 上 DA 主要有三个功能 1 目录信息的组织和查询 2 动态的形成域 3 域内和域间的 QoS 信息的监控 资源的查找有两种方式 一种是浏览方式 另一种是访问方式 对于浏览方式来说 就是将请求发送到 资源属性哈希出来的索引号对应的 DA 上 该 DA 返回所有满足条件的资源提 供者的信息给用户 而访问方式就是要从所有满足条件的资源提供者中选择 QoS 最好的资源进行下载 这种方法的主要特点在于它提供了基于 QoS 的资源 选择 从而使得它的性能要优于不考虑 QoS 的资源发现系统 2 1 2 42 1 2 4 其他分布式系统中的资源发现其他分布式系统中的资源发现 DNS Domain Name Service 30 是最大的基于名字的分布式查找系统 它将 Internet 主机域名翻译成相应的 IP 地址 它服务于整个因特网 已经成为了一 项重要的因特网资源服务 它采用层次性拓扑结构 节点加入到层次结构的某 个地址 overlay 的功能是维护好基于域的树形结构 请求的解析是由低向高层 顺序进行的 在 Ninjia 服务定位服务 31 中 服务是根据最相关的某些属性来命名的 系 统将这些名字做聚合 经过聚合可能会损失一些信息 并把这些概要信息在层 第二章 分布式网络资源定位 15 次结构中向上传 当处理查找请求时 按照 B 树搜索方式 在这种层次结构中 向上或向下转发 在系统部署时 overlay 的层次结构已经固定 Globe 定位机 制是建立在搜索树结构的基础上的 搜索关键字是全局唯一名字 命名服务将 一个 URL 转化成与位置无关的唯一标识符 所以 它的 overlay 成员关系维 护以及搜索方法 都是基于这样的搜索树的 Conder 的 Matchmaker 是基于属性的资源查找服务 资源描述与请求被发 送到一个中央验证机构 并在那里进行匹配 预处理就是把资源注册到中央服 务器中 每个节点只需知道中央服务器的地址 处理请求就是将请求发送到中 央服务器 只需告诉新加入的节点中央服务器的地址 除此之外不需要其他维 护成员关系的机制了 Lee 和 Benford 提出了基于请求传播 propagation 的资源发现机制 其中节 点把所有未解析出来的请求转发到一个无结构 overlay 上的其他节点中 这个 overlay 的构建要考虑到邻居节点的专长和喜好 一个节点要连接到有用服务的 节点或有好的推荐的节点 这种方法的预处理是要收集进行评价所需的信息 不管需要或不需要 trader 都会去探测整个网络 并把状态改变后通过 Flooding 方法传播出去 2 22 2 现有资源定位现有资源定位技术技术 根据拓扑结构