【优秀硕士论文参考】数据网格环境下的元数据分发技术研究

【优秀硕士论文参考】数据网格环境下的元数据分发技术研究 华中科技大学硕士学位论文 分 类 号 __________ 学号 ______________ TP311.52 2005612100175 公开 学校代码 __________ 密级 ______________ 10487 数据网格环境下的元数据分发技术 研究 学位申请人 : 学科专业 :计算机软件与理论 指导教师 : 答辩日期 :2007年6月2日 I 华中科技大学硕士学位论文 The Research on Metadata Dissemination Technology for Data Grid 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名: 日期: 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密?，在________年解密后适用本授权书。 本论文属于 不保密?。 (请在以上方框内打“?”) 学位论文作者签名: 指导教师签名: II 华中科技大学硕士学位论文 摘 要 伴随着Internet网络规模的飞速增长，在计算密集型和数据密集型应用领域，传统的分布式计算和并行处理技术已不能满足高性能分布式处理和分布式海量存储管理的需求，于是网格技术应运而生。数据网格(Data Grid)的概念来自于网格，它是网格技术在数据管理方面的应用和实现。 数据网格环境下的数据访问过程依赖于资源发现，而资源发现即为发现对数据资源进行描述的元数据，网格环境下网络资源频繁变化，相应的元数据变化也很频繁，而如何能更加快捷有效地获得所需要的元数据，就需要各个节点能够将各自的元数据快捷有效地分发到网络中的其他相关节点，这取决于元数据分发策略的实施。现有的元数据分发策略基本可以分为两类:被动分发和主动分发。主动元数据分发具有很高的准确性，但是却会占用很多网络资源;被动元数据分发具有低代价性，但是却很难保证元数据的准确性。 轮值会议元数据分发(Rotating Meeting Metadata Dissemination, RMMD)以轮值会议召开的方式来进行元数据的分发，并采用了HLA(High Level Architecture)数据分发管理中采用的数据过滤机制，它兼具了主动元数据分发的准确性和被动元数据分发的低代价性，能快捷有效的完成元数据在整个网格中的分发，让整个网格的元数据在较短的时间内、用较小的代价得到较好的配置。通过模拟仿真实验将RMMD策略与主动元数据分发策略、被动元数据分发策略进行比较，实验结果显示RMMD策略可以有效的分发整个网格中的元数据，提高分发的准确性，并保证分发的低代价性。 关键词: 数据网格，元数据分发，轮值会议 III 华中科技大学硕士学位论文 Abstract With the rapid growth of internet network scale, the traditional distributed computation and parallel processing technology hasn’t met the need of this high-powered distributed computation and distributed management for large memory in the domain of computation-dense and data-dense application. As a result, grid technology came into being. Data grid of is the grid technology’ application and realization in data management. The process of data accessing in the data grid depends on resource discovery which finds out the metadata that describes source. For the resource in grid frequently changes, the corresponding metadata changes a lot, too. To get the requisite metadata quickly and effectively requires that every node could disseminate its data to other corresponding nodes quickly and effectively, and this lies on the implement of metadata dissemination strategy which is classified as passive and active. Active metadata dissemination (ACTMD) has great veracity but it occupies too much network resource. Passive metadata dissemination (PASMD) has low cost but it hardly ensures the veracity of metadata. Rotating Meeting Metadata Dissemination (RMMD) disseminate metadata in the way of rotating meeting convocation, and adopts the data filtration mechanism in HLA data distribution management .The RMMD which has both the benefits of veracity of ACTMD and low cost of PASMD can disseminate metadata in the whole grid quickly and effectively, and make the metadata in the whole grid get better collocation with lower cost in a shorter time. Compared RMMD with PASMD and ACTMD through simulation experiment, the results show the RMMD strategy could disseminate the metadata in the whole grid effectively, increase the veracity and ensure the low cost of dissemination. Keywords:Data Grid，Metadata Dissemination，Rotating Meeting IV 华中科技大学硕士学位论文 目 录 摘 要 ...........................................................................................III Abstract ............................................................................................. IV 1 绪论 1.1 研究背景 ................................................................................... (1) 1.2 国内外研究概括 ........................................................................ (2) 1.3 本课 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 研究的目标和意义 ......................................................... (5) 1.4 本文组织结构 ............................................................................ (6) 2 数据网格中的元数据分发技术 2.1 数据网格核心问题 .................................................................... (7) 2.2 元数据的提出 ............................................................................ (7) 2.3 传统数据分发技术 .................................................................. (11) 2.4 数据网格中传统元数据分发技术 ............................................ (13) 2.5 小结 ......................................................................................... (15) 3 轮值会议元数据分发机制 3.1 背景介绍 ................................................................................. (16) 3.2 轮值会议元数据分发的原理 ................................................... (18) 3.3 轮值会议元数据分发的协议 ................................................... (19) 3.4 小结 ......................................................................................... (28) V 华中科技大学硕士学位论文 4 原型系统开发与仿真实验分析 4.1 RMMD原型系统开发 ............................................................. (29) 4.2 实验环境OPNET .................................................................... (30) 4.3 仿真模型 ................................................................................. (34) 4.4 仿真算法 ................................................................................. (37) 4.5 实验与性能分析 ...................................................................... (40) 4.6 小结 ......................................................................................... (43) 5 总结与展望 5.1 本文 工作总结 关于社区教育工作总结关于年中工作总结关于校园安全工作总结关于校园安全工作总结关于意识形态工作总结 .......................................................................... (44) 5.2 展望 ......................................................................................... (45) 致 谢 ........................................................................................ (46) 参考文献 ........................................................................................ (47) VI 华中科技大学硕士学位论文 1 绪论 1.1 研究背景 伴随着Internet网络规模的飞速增长，计算机网络技术和分布式技术得到了高速发展和广泛应用，许多科学计算领域，特别是计算密集型和数据密集型应用领域， [1]对广域网环境下海量数字信息分析处理和协同计算能力的要求也越来越高。这类应用需要将分布在不同地理区域的高性能计算能力、超大规模数据集合和各种资源整合在一起，为分布在不同地理区域的用户提供服务。传统的分布式计算和并行处理 [2,3]技术已不能满足这种高性能分布式处理和分布式海量存储管理的需求，于是网格技术应运而生。 网格技术可以把分布在各地的计算机连接起来，实现计算资源、存储资源、数据资源、信息资源、知识资源、专家资源的全面共享，感觉如同个人使用一台超级计算机一样。这种虚拟资源可以使相关人员迅速获得所需的数据访问和处理能力，帮助其进行计算密集型的研究和数据分析、解决复杂的业务问题。这样，网格就可以帮助用户突破今天技术基础设施的限制。对于传统网络环境，网格具有动态可变、异构、多域等特性。网格计算作为新一代的分布式计算框架，与传统分布式系统的主要区别在于在没有集中控制的情况下，通过对计算资源进行大规模的共享，满足 [4]应用程序对高性能计算的要求，并且这种对计算资源的大规模共享是动态的、柔性的、安全的和协作的。目前，在国内外网格也引起了极大的关注，如美国Argonne [5,6][7]国家实验室研发的Globus系统、欧洲数据网格DataGrid、美国能源部的科学计 [8]算网格DOE Science Grid、中科院计算所的织女星网格VEGA Grid等等。 数据网格(Data Grid)源于网格，它是网格技术在数据管理方面的应用和实现。它将地理上分布、异构的多种数据资源，通过高速互连网络连接并集成起来，屏蔽底层异构的物理资源，形成单一的逻辑视图，实现资源共享和协同工作，为用户提供虚拟的数据访问、数据存储、数据管理和处理环境。其中，良好地表示、存储、访问和使用大量资源信息是数据网格运行的基本前提。在数据网格计算中，资源是 1 华中科技大学硕士学位论文 分布的，资源及其提供者也是分布的。 为了对网络资源进行有效的管理和检索，使目前有序和无序状态并存的网络资源能够像传统资源(如馆藏资源)一样有序化，从而使它们得到更好的利用，人们一直都在作着多方面的努力。从早期的Archie和Gopher系统，到近期的搜索引擎和主题指南，都是这方面努力的成果。历年实践表明，增加关于资源的额外信息或元数据(metadata)是更好地组织资源的基础，它能够提高相关资源被检索和存取的可能性，提供对主题领域更清晰的全面认识，并提高用户区别相似资源的能力。正因为如此， [9]元数据逐渐受到普遍的重视。 元数据(metadata)，简言之就是“关于数据的数据”，是对数据进行组织和处理的基础。数据网格环境下的数据访问过程依赖于资源发现，而资源发现即为发现对数据资源进行描述的元数据。同时数据网格环境中网络资源频繁变化，一方面，结点可以动态的加入、离开系统，另一方面，各个节点中的资源也是不断变化的，相应的元数据变化也很频繁，而如何能更加快捷有效地获得所需要的元数据，就需要各个节点能够将各自的元数据快捷有效地分发到网络中的其他相关节点，这取决于元数据分发策略的实施，也是本文集中探讨的问题。 1.2 国内外研究概括 1.2.1 Globus中的元数据目录服务 Globus系统是目前比较具有影响力的一个网格项目，提供网格环境下的中间件服务，如MDS、GridFtp等。系统使用 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的协议实现了文件数据的移动、远程访问GASS及数据的高速传输GridFtp机制，在此基础上完成数据复制、元数据目录的管理MDS(Metadata and Directory Service)和复制的选择工作，为数据网格系统提供了 [10]一个较好的底层系统开发平台。 [11]其中，MDS在网格环境中提供资源信息服务。MDS主要负责对网格环境中信息的发现、注册、查询、修改等工作，提供对网格计算环境的一个真实、实时的动态反映。该服务是建立在轻权目录访问协议LDAP(Lightweight Directory Access 2 华中科技大学硕士学位论文 [12]Protocol)基础上的，处理网格计算环境中的各种资源(包括数据资源、计算资源等)、服务和其他主体(entity)的描述，是网格计算环境中的信息服务中心。它采用两层结[13]构: 1) 网格资源信息服务器(Grid Resource Information Server, GRIS):以一种目录的结构登记具体的资源信息。 2) 网格索引信息服务器(Grid Index Information Server, GIIS):记录有GRIS的地址，并能提供GRIS信息缓冲。 1.2.2 GridDaen中的元信息服务 GridDaen是国内最早实现的通用数据网格原型系统，是中国国家网格(China National Grid, 简称CNGrid)研究的一部分。CNGrid是国家“十五”863 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 “高性能计算机及其核心软件”重大专向支持建设的网格示范平台，通过资源共享、协同工作和服务机制，有效支持科学研究、资源环境、先进制造和信息服务等领域的应用，以技术创新推动国家信息化建设及相关产业的发展。GridDaen主要目标是统一管理和访问分布异构环境下的海量存储和数据资源，为用户提供一体化虚拟数据空间和统一逻辑视图，支持对分布数据集的统一无缝访问，实现虚拟数据集和跨管理域的联邦数据服务。系统具有可扩展性、安全性、动态可配置、高性能、高可用性 [14]等特点。 GridDaen主要由客户机、数据访问、元信息服务MDIS(Metadata Information Service)和底层异构资源四部分组成。其中，数据访问子系统包括请求优化管理调度与DRB(Data Request Broker)服务器，元信息服务子系统包括高层元信息服务与局部信息服务。DRB服务为用户提供数据访问、存储和管理的功能。MDIS是一个层次式分布服务结构，由局部元信息服务器和中央全局元信息服务器组成。各个局部元数据服务器负责所对应本地的资源和数据元信息服务，提供元信息服务的访问。中央服务器建立各个局部元信息的索引和数据缓冲，为DRB实现统一的访问接口和全局数据视图提供元信息支持。MDIS和DRB是相互独立设计和实现的，通过系统的部署和配置建立服务关系。图1.1为元信息服务逻辑结构图。 3 华中科技大学硕士学位论文 中央全局元信息服务器处于系统的中央位置，管理着分布各处的局部元信息服务。局部元信息服务则分散在系统中的不同位置，受到中央节点的管理和监控。局部元信息服务一般位于某台元信息服务节点机器上，通过配置为某个或者某几个DRB域提供元信息服务。这种两层式设计可以提高系统的可扩展性，方便系统管理，并减少了集中式设计带来的性能瓶颈和单点失效问题。 中心节点 局部 局部 局部 Site X Site B Site C Site A 图1.1 元信息服务逻辑结构图 1.2.3 传统网格中元数据分发技术 现有的元数据分发方式基本可以分为两类:被动分发和主动分发。对于被动分发而言，除非有请求到达，节点不会发布自己拥有资源的元数据;主动分发与之相反，当节点加入网络或者节点数据发生一定变化的时候，节点会立即发布自己的元数据。显然，被动分发的网络资源的消耗甚小，但同时对于网络资源频繁变化的环境，元数据中存在很多错误，其他节点数据的准确性无法得到满足。而主动分发可以在最大可能上保证元数据的准确性，从而可以增加节点数据的有效性，但由于分发数据过多，对网络资源的使用也是最多的。 对于主动分发而言，根据对元数据分发处理的不同，即分发给什么样的节点以 [15,16]及怎么样转发别的节点发来的元数据，可以将主动分发策略分为以下几种。 1. 泛洪式 在该算法中，元数据分发采用最简单的泛洪的方式。也就是说:当自身产生更新消息后，也向网格中的所有节点发送消息。 2. 邻居式 4 华中科技大学硕士学位论文 在该算法中，所采用的策略是:设定一个半径范围(该半径可以用节点跳转数来衡量)发送消息时，只向处于该半径范围之内的所有节点发送消息。 3. 水流式 在这种方法中，采用的其实是一种特殊节点法，根据某种方式来确定出某些特殊节点。现在比较流行的是网格势能来区分节点的处理能力。网格上的一个节点的网格势能可以被认为是可以被分派给某个节点上的应用程序的处理能力。该处理能力依赖于邻近出现的机器以及他们之间互连的网络。同时还有一个相对网格势能:节点相对于某个远程节点的势能。如果节点的自身网格势能小于相对于某远程节点的势能，就把由该远程节点发出的消息进行转发，否则不转发。而对于自身产生的更新消息，如果周围节点相对势能的平均值小于该节点的自身的势能，则该节点可以向周围的所有节点进行消息发送;否则不能进行消息发送。这种方式的主要特点是:消息从势能高的节点流向势能低的节点。这类似于水流的形式，故称为水流式。 4. 质点式 本算法依然采用了网格势能的概念。不同的是:即使相对势能比自身势能要低，节点也并不一定可以发送消息。在该算法中，引用了概率论的知识，即节点随机选取周围部分的节点进行消息发送。这种行为有点类似于质点的活动方式，故而称为质点式。 1.3 本课题研究的目标和意义 元数据被动分发对网络资源的消耗甚小，具有低代价性，但同时对于网络资源频繁变化的环境，元数据中存在很多错误，其他节点数据的准确性无法得到满足。而元数据主动分发可以在最大可能上保证元数据的准确性，从而可以增加节点数据的有效性，但由于分发数据过多，对网络资源的使用也是最多的。如何能设计出一种分发策略，将这两种分发技术的优点结合起来，这将是本文的工作核心。本文通过对传统数据分发技术，特别式网格中的元数据分发技术的研究，提出了一种新的元数据分发机制，并设计实现了这种分发策略，通过仿真实验的对比验证，实验结果表明这种分发策略确实综合了主动分发的准确性以及被动分发的低代价性。 5 华中科技大学硕士学位论文 1.4 本文组织结构 本文以数据网格为研究背景，介绍了传统的元数据分发技术，在此基础上提出了一种新的元数据分发框机制，并通过仿真实验与传统的分发技术进行了分析对比。本文各章的内容安排如下: 第一章为绪论，介绍了本课题的研究背景，然后介绍了国内外的研究现状。 第二章为数据网格中的元数据分发技术，介绍了数据网格中的核心问题，并对元数据的概念、网格中元数据的分类、元数据常有的标准化问题以及元数据分发方式做了详细的分析和介绍，最后详细介绍了传统的数据分发技术以及数据网格中的传统元数据分发技术。 第三章为轮值会议元数据分发机制，首先介绍了设计此分发机制的背景知识，随后提出了一种新的元数据分发机制，最后对对这种分发机制进行了设计和实现。 第四章为仿真实验与性能分析，首先介绍了RMMD的原型系统开发，之后分析了OPNET仿真工具，随后详细介绍了仿真模型及实验算法，最后给出仿真实验结果。 第五章为总结与展望，最后为致谢与参考文献。 6 华中科技大学硕士学位论文 2 数据网格中的元数据分发技术 2.1 数据网格核心问题 数据网格在网格基本功能的基础上扩充数据管理功能，提供与信息有关的各种服务，其最核心的关键技术是元数据管理和存储资源代理。 良好地表示、存储、访问和使用大量资源信息是数据网格运行的基本前提。在数据网格计算中，资源是分布的，资源及其提供者也是分布的，这些资源包括数据、 [17]计算机、设备、网络、外设、软件、服务、代码、人员等。元数据管理服务命名、描述、收集、组织和管理数据网格中的资源信息，这些信息就是用于描述资源、方法、数据集和用户的元数据。 为了实现命名的透明性，网格需要有效管理数量繁多的名字和属性，以及它们之间的关系;为了实现定位的透明性，网格需要有效管理数据集的定位信息;为了实现协议的透明性，网格需要有效管理数据资源的有关信息。实际上，这些信息就是用于描述资源、方法、数据集和用户的元数据，概括地说，元数据目录为用户身 [18]份认证、数据定位、访问控制、数据复制等提供支持。 2.2 元数据的提出 2.2.1 MDS元数据概念 元数据的概念起源于计算机科学，早在20世纪60年代，为了有效描述数据集，Jack Mayers就定义了Metadata一词的概念，其中文译名有多种，元数据是其当前在中国大陆比较通用的译名。元数据最常见的宽泛定义“关于数据的数据”已经得到了普遍认可，但由于这一定义过于简单抽象，对它的认可只是表明在元数据的本质方面人们达成的共识。事实上，人们对元数据的理解和认识还存在不少差异，迄今尚 [19]未形成一个真正统一的元数据定义。 较宽泛的元数据定义:元数据是描述一个具体的资源对象，并能对这个对象进行定位、管理，且有助于它的发现与获取的数据。这是一个比较笼统的概念，它包 7 华中科技大学硕士学位论文 括多个词汇:元数据标准、元数据项、元数据记录等，可以认为是这些概念的统称。 元数据的产生对管理庞大的信息数据起着不可忽视的作用。元数据的应用领域 [20]广泛，作用也各不相同，但总体来看，它们都具有一些共同的基本功能。 1. 描述功能 元数据的基本功能就是对信息资源进行描述，供用户读取以便了解自己所获信息是否是所需要的。因此可以节约用户的时间和精力，也可减少网络中信息交换的浪费。 2. 检索功能 元数据是提供检索的基础。元数据将信息对象中的重要信息抽出，加以组织，赋予语意，建立关系，使得检索结果更加准确。因此利用元数据进行简单、复杂或综合的信息查询，可以提高查询效率。 3. 定位功能 元数据包含有信息资源的位置信息，由此便可确定资源的位置所在，促进网络中信息对象的发现和检索。 4. 选择功能 根据元数据提供的描述信息，结合使用环境，用户便可对信息对象做取舍决定，选择适合用户使用的资源。 5. 评估功能 元数据提供信息对象的各类基本属性，使用户在无需浏览信息对象本身的情况下就能对信息对象具备基本的了解和认识，参照有关标准，即可对其进行价值评估，作为使用的参考。 2.2.2 元数据的分类 [21]元数据的应用领域不同，对元数据就会有各自不同的分类方法。在网格数据 [22]管理环境下，一般将描述数据对象的元数据分为五种类型，如图2.1所示。 最底层的物理元数据包括描述物理存储系统数据对象的元数据和副本定位元数据，其中物理存储系统包括文件系统和数据库管理系统。副本定位元数据提供将逻辑名与一个或多个副本物理定位信息相映射的服务。 8 华中科技大学硕士学位论文 用户元数据 User Metadata 虚拟组织元数据 Virtual Organization 特定域元数据 Metadata Domain-Specific Metadata 无关域元数据 Domain-Independent 物理元数据 Metadata Physical Metadata 图2.1 元数据的五种类型 无关域元数据描述一般元数据属性，这些元数据属性无论在应用域还是在虚拟组织中都会涉及和描述，如对逻辑名字，数据对象的创建者和维护者，授权和审查信息，共享池或视图中的数据对象集等信息的描述。 特定域元数据包括指定的某应用域、虚拟组织或某特定用户所用的数据对象集的元数据描述。特定域元数据的属性通常为某些应用团体所开发的元数据实体。例如，物理学家或地震学家都共享一些通用的学术术语和量度，这些特性可用于描述一些共享的数据集和表示可使用的元数据属性通用集。 虚拟组织元数据描述的是某个特定虚拟组织所使用的数据集内容。虚拟组织包括多个科学或企业机构，他们可能定义了一些特定的元数据属性集来描述传统的特征数据集。用户元数据用于对单个用户所使用的数据集进行描述。这些元数据可能是互相关联的数据集属性，如对某些数据对象或共享池里的数据进行描述。元数据及其提供的服务在数据网格中对数据集的发布、发现和存取都起着极其重要的角色。 2.2.3 元数据标准化问题 90年代元数据模式(Metadata Schema)大量涌现，不仅出现了很多针对不同资源的元数据模式，同时由于缺乏 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 和一致性约束，针对同一资源类型也出现了多种描述。另外元数据应用的广泛性，参与制定元数据模式的团体众多等原因，都是造成 [23]元数据模式大量出现的原因。元数据模式的众多，尤其是同一种资源有多种元数据模式的出现，不可避免地导致了数据共享问题的产生。唯一能够在不同数据管理 9 华中科技大学硕士学位论文 软件间交换元数据的途径是制定统一的元数据标准。元数据标准能够使数据生产者和用户一起着手处理有关元数据交换、共享和管理的问题。因此元数据的规范化和标准化问题也就逐渐提上了日程。 元数据标准的研制与实施已引起各国广泛重视，许多国家不但已经完成标准的制定，开发了多种操作工具软件，建成大量的元数据库，并已投入使用，而且多次召开国际学术讨论会，对元数据的理论、实施、应用及标准化的有关问题进行讨论。 元数据标准是描述某类资源的具体对象时所有规则的集合。不同类型的资源可能会有不同的元数据标准。一般而言，元数据标准包括三个方面的内容:内容结构、语义结构和语法结构。(1) 内容结构是对元数据标准中的构成元素及其定义标准进行描述。(2) 语义结构是定义元数据标准中元素的具体语义描述方法，尤其是定义描述时所采用的公用标准、最佳实践或自定义的语义描述要求(Instructions)。其中主要涉及到两方面的内容:语义定义规则和语义定义方法。(3) 语法结构负责定义元数据标准的结构以及如何描述这种结构，即元数据在计算机应用系统中的表示方法和相应的描述规则，这些称为元数据的描述语言和语法结构。目前，通常采用的是XML和 [24]RDF两种方式。 2.2.4 元数据分发方式分类 现有的元数据分发方式基本可以分为两类:被动分发和主动分发。对于被动分发而言，除非有请求到达，节点不会发布自己拥有资源的元数据;主动分发与之相反，当节点加入网络或者节点数据发生一定变化的时候，节点会立即发布自己的元数据。显然，被动分发的网络资源的消耗甚小，但同时对于网络资源频繁变化的环境，元数据中存在很多错误，其他节点数据的准确性无法得到满足。而主动分发可以在最大可能上保证元数据的准确性，从而可以增加节点数据的有效性，但由于分发数据过多，对网络资源的使用也是最多的。 10 华中科技大学硕士学位论文 2.3 传统数据分发技术 2.3.1 HLA中的数据分发技术 [25]高层体系结构HLA(High Level Architecture)是新一代分布式交互仿真标准，它的一个重要特征就是将仿真应用与底层的通信和基本功能相分离，由运行支撑系 [26,27]统RTI(Runtime Infrastructure)提供的服务来实现底层的通信和基本功能，联邦成员不必涉及底层的网络编程。在它的框架中，每个描述一定功能的子模块或仿真过程都被称为是HLA的一个联邦成员，每个联邦成员包含若干个对象。 目前RTI提供联邦管理、声明管理、对象管理、所有权管理、时间管理和数据分发管理六大类服务以及一些必要的支持服务，其中数据分发管理DDM(Data Distribution Management)是一类关键的服务，其主要目的是为了尽可能地减少联邦成员收到不需要的数据和网络数据流量，以有效地使用系统的通信带宽和处理机的计算能力来满足系统的可扩缩性，这种机制即为一种数据过滤机制。通过数据过滤机制，使仿真实体只与感兴趣集内的实体交互，它的目的主要有两个:一是尽可能减少不相关数据的产生，以减少网络带宽的占用;二是降低仿真结点接收冗余数据时引起的处理开销。 在HLA中，支持数据过滤的基本概念是区域(Region)。对象实例利用区域描述向外部发送数据以及从外部接收数据的需求信息。对象实例通过更新区域(update region)和订购区域(subscribe region)描述向外发送数据和接收外部数据的约束条件。 数据分发管理进行数据过滤的主要实现策略是各联邦成员在择径空间中分别表达各自感兴趣的更新区和订购区，通过更新区和订购区的比较，当存在共同的兴趣区时(即更新区和订购区出现重叠时)，DDM将更新联邦成员更新的数据信息传递到订购区与其更新区相重叠的订购联邦成员处。图2.2即为一个数据分发管理的基本实现流程。 DDM中采用的数据分发算法一般采用基于网格的过滤方法，此方法是一种传统的多播组分配方法。在该方法中，路由空间被分成一个由固定大小的网格单元构成的阵列，每一个网格单元对应一个多播组。当联邦成员的定购区域与网格单元交迭 11 华中科技大学硕士学位论文 时，就将联邦成员加入到该网格单元对应的多播组中。当联邦成员希望发送数据更新时，更新仅被发送到与该联邦成员更新区域交迭的网格单元所对应的多播组。对应于交迭单元的多播组负责将数据更新传送到多个定购联邦成员。 兴兴兴兴 兴兴兴兴兴兴兴兴 兴兴兴兴 兴兴兴兴 兴兴兴兴 图2.2 HLA中数据分发管理的基本实现流程 2.3.2 CDN中的数据分发技术 CDN(Content Delivery Network)，即内容分发网络技术。CDN的基本思路就是通过在Internet网络结构中增加一个完善、全面的中间层，利用缓存、复制、负载平衡和DNS重定向等技术，实时处理网络流量和各节点的负载状况，将用户的请求导向最近的服务节点上，用户就近取得所需的内容，从而解决网络拥塞、提高上网访问的总体性能。 CDN网络中客户的内容请求通过全局内容路由到达某个内容交换机，由交换机将请求的内容分发到距用户最近的网络边缘节点，即内容缓存服务器上，同时也将客户的请求重定向到边缘节点，改善用户的访问效果。CDN的主要技术有内容路由、 [28,29,30]内容分发等。 内容路由技术的作用是将用户请求导向整个CDN网络中的最佳节点。最佳节点的选择可以运用多种评估策略来实现，例如用户与服务器距离最近、服务器负载最轻等。这是CDN的核心，它决定了整个CDN的效率和性能。内容路由技术可以通过多种方法实现，包括DNS、应用层重定向、传输层重定向等。 内容分发技术指将内容从源到复制缓存到CDN边缘服务器的过程。从实现上来 12 华中科技大学硕士学位论文 看，有两种主流的分发技术:PUSH和PULL。PUSH是一种主动分发的技术。通常，PUSH由内容管理系统发起，将内容从源或中心媒体资源库分发到各边缘的Cache 节点。对于PUSH分发需要考虑的主要问题是分发策略，即在什么时候分发什么内容，可以根据用户访问的统计信息，以及预定义的内容分发规则来确定。PULL是一种被动的分发技术，PULL分发通常由用户请求驱动。当用户请求的内容在本地的边缘Cache上不存在时，Cache启动PULL方法从内容源或者其他CDN节点实时获取内容。在PULL方式下，内容的分发是按需的。 2.4 数据网格中传统元数据分发技术 2.2.4节的介绍可知，传统元数据分发技术可以分为两大类:主动分发和被动分发，由于被动分发较为简单，基本上不会涉及到分发算法研究，目前的研究基本上集中于主动分发上。对于主动分发而言，根据对元数据分发处理的不同，即分发给什么样的节点以及怎么样转发别的节点发来的元数据，传统主动分发策略也可以进 [15,16]行划分，下面将逐一进行介绍。 2.4.1 泛洪式(Flooding) 在该算法中，元数据分发采用最简单的泛洪方式。在这种算法中，假定每个节点都了解整个网格中所有节点的信息，这样当节点自身产生更新消息后，它会向网格中的所有节点发送消息。很显然，当网格规模较大时，由于网格中节点较多，这种分发方式的效率低下，且会产生极大的网络流量，这中风暴式的分发也必然会对网络稳定运行提出极大的挑战，因此这种分发只可能在极少数特殊的情况下采用。 2.4.2 邻居式(Neighborhood) 为了减少泛洪式元数据分发过程中产生的极大网络流量，邻居式分发算法得以提出，在该算法中，每个网格节点具有一个邻居半径属性R，即此节点了解半径为R范围内的节点，这样在节点产生了更新消息时，它就会在消息中设置TTL值为R，约定只有在TTL值大于0的情况下，消息才能进行转发，这样收到更新消息的邻居节点就会判断TTL是否大于0，如果大于0就会将其减1后向自己的邻居节点进行 13 华中科技大学硕士学位论文 转发，否则不进行转发。这样只有在距节点逻辑跳数不大于R范围中的节点才能收到消息，这种分发方式较之泛洪式分发方式可以明显的减少对网络带宽的占用。但是这种分发方式所产生的网络流量也是非常大的，分发效率也不高。 2.4.3 水流式(Fluid) 在这种方法中，为了进一步降低分发的网络流量以提高元数据分发的效率，引入了现在比较流行的是网格势能(Grid Potential，GP)来区分节点的处理能力。网格上的一个节点的网格势能可以被认为是可以被分派给某个节点上的应用程序的处理能力。该处理能力依赖于邻近出现的机器以及他们之间互连的网络。同时还有一个相对网格势能:节点相对于某个远程节点的势能。如果节点的自身网格势能小于相对于某远程节点的势能，就把由该远程节点发出的消息进行转发，否则不转发。而对于自身产生的更新消息，如果周围节点相对势能的平均值小于该节点的自身的势能，则该节点可以向周围的所有节点进行消息发送;否则不能进行消息发送。这种方式的主要特点是:消息从势能高的节点流向势能低的节点。这类似于水流的形式，故而称为水流式。 文献[15,16]给出了网格势能的计算方法:即选定一段特定的基准代码，这样以各网络节点执行这段基准代码的效率来确定各节点的网格势能，为了测试一个节点的网络势能，需选取一个标准节点作为比照，设C为这段基准代码的工作量，e为s标准节点执行基准代码所需的时间，l为测试节点的负载量(以节点平均工作量队n s列长度作为衡量指标)，为测试节点的工作速度，则测试节点执行基准代码的时间n e的计算公式为: n e,e*(1，l)/s (2.1) nsnn GP设为测试节点的网格势能，则根据定义，其计算公式为: n GP,C/e (2.2) nn 14 华中科技大学硕士学位论文 根据公式(2.1)及(2.2)，可得网格势能的推算公式为: (2.3) GP,C*s/(e*(1，l))nnsn 另外，节点相对网格势能的计算过程与上述类似，在此不再详述。 2.4.4 质点式(Particle) 为了进一步降低分发的网络流量以提高元数据分发的效率，本算法在引入网格势能的同时又对分发的目标进行概率处理。它与水流式的不同处在于:即使相对势能比自身势能要低，节点也并不一定可以发送消息。在该算法中，引用了概率论的知识。设某个节点(势能为)向远程节点(相对势能为)发送消息的可能性为:,,sr ,(,,,)/ksr，其中k是一个常数，这样节点对周围n,1个节点所能发送消息的节1,e 点数为:，节点会对n,1个邻居节点中随机的选取个节点进E(p(n,1))E(p(n,1))行消息发送。这种行为有点类似于质点的活动方式，故而称为质点式。 2.5 小结 本章首先分析数据网格中的一些核心问题，随后对元数据的概念、网格中元数据的分类、元数据常有的标准化问题以及元数据分发方式做了详细的分析和介绍，最后详细介绍了传统的数据分发技术以及数据网格中的传统元数据分发技术。对上述关键技术的充分研究，为第三章提出的一种新的元数据分发机制的设计和实现提供了相应的基础和依据。 15 华中科技大学硕士学位论文 3 轮值会议元数据分发机制 3.1 背景介绍 3.1.1 网络拓扑结构 数据网格可以认为是由一条高速链路将一系列的异构用户连接起来的虚拟网络，在实际网格应用中，整个网格系统会根据其自身需求和目的的不同划分为多个虚拟组织的形式。虚拟组织为所有参与者提供可用资源，获取同一规范，并在资源 [31,32]可以被使用的条件下使用资源等功能，每个虚拟组织管理的服务可理解为地理位置分布、逻辑位置相邻、属性相似的服务集合。 如图3.1所示，实际的数据网格系统可以分为上下两层，下层为集中控制层，上层为纯P2P层(非结构化)。这样下层中的网格用户就会被划分到不同的虚拟组织域中，并且每个虚拟组织域中都有一个元数据服务器，这样每个域内是属于集中控制的;同时所有的元数据服务器之间是纯对等的，即构成非结构化的P2P。 元数据纯P2P层 服务器 „„„ 集中控普通节 制层点 „„„ „„„ 图3.1 数据网格拓扑分层 这样实际上就将数据网格中的用户划分为两类:管理节点以及普通节点，其中 16 华中科技大学硕士学位论文 普通节点负责提供资源，同时也会请求资源;而管理节点即为一个元数据服务器，响应所辖域中普通节点的资源请求，同时还会与其他的管理节点进行交互。一个管理节点负责管理多个普通节点，它会收集所辖域中的所有普通节点的元数据信息以及它们所请求的元数据信息，并进行汇总，同时通过一定的控制策略来与其他的管理节点进行交互，以获取各自所需的元数据信息，最后将得到的元数据信息分发给所辖区的普通节点。由此可知，元数据分发的关键技术就落到了如何在管理节点间进行元数据分发的问题上，这也是本章研究的重点。 3.1.2 小世界网络 [33,34,35]小世界(Small-World)的概念来自于60年代末Milgram在哈佛完成的一个著名实验:他在信封上写上他在美国波士顿的一个朋友的地址，然后在在英国随机选择了若干人，要求他们把信通过中间人转交给他的朋友，注意每次都要把信转交给他认为最有可能找到收信人的熟人，下一个转发者再按照同样的方法将信转发。经过统计分析，Milgram发现在任何两个陌生人之间，只需要平均通过6个熟人就能联系在一起，这种特征被称为“6度分离”。Milgram的实验表明:社会中任意挑选的两个人之间，总存在一条由中间的熟人组成的短链把他们连接在一起，而他们也总能找到这条短链，这个结论用物理学的术语来说就是“小世界效应”。 Watts和Strogatz进一步指出小世界现象不仅存在于人类社会，它同样存在于现实世界的许多自然和人工的网络。符合Small-World这一特性的网络各个节点的连接度比较均匀，即基本上每个节点的联结数都近似相等，同时任意两个节点之间建立连接的长度都很小。研究表明目前流行的Gnutella网络也呈现Small-World特性。 3.1.3 Zipf定律 Zipf定律是由美国学者G.K.Zipf于上世纪40年代提出的词频分布定律:如果统计一篇较长文章中每个词出现的频率，按照高频词在前，低频词在后的递减顺序排列，并用自然数把这些词编上等级序号，频率最高的词为1，频率次高为2，以此类推。若用f表示频率，r表示序号，则有frC,,，C为常数。Zipf定律也被称为80-20法则，即80%的访问只会针对20%的数据。人们通过对现实Web系统中通信流量的 17 华中科技大学硕士学位论文 [36]分析，发现用户对Web对象的访问模式服从Zipf定律分布或者Zipf-like定律分布。 iZipf-like定律分布中:概率表示访问频度，则排列第个对象的访问概率为: POii 1P,i (3.1) n,1,i,k,1k 其中，为Zipf-like定律分布参数，n为所有数据的个数。通常。 ,,0.64,0.83,,,3.2 轮值会议元数据分发的原理 2.2.4节介绍了目前两种元数据分发方式的优缺点，为了综合这两种分发方式的优点，即主动元数据分发(Active Metadata Dissemination, ACTMD)的准确性和被动元数据分发(Passive Metadata Dissemination, PASMD)的低代价性，再结合国内外关于分发技术的相关研究成果，提出了一种新的元数据分发机制—轮值会议元数据分发(Rotating Meeting Metadata Dissemination, RMMD)。 3.2.1 轮值会议元数据分发的主要思想 RMMD主要思想如下:采用轮值会议主持的方法，每个管理节点会周期性地被系统触发并短暂的成为中央服务器，成为中央服务器的管理节点(“主持人”)会召开会议，并召集“代表”(相邻一定“距离”的管理节点)来参加会议，在会议进行中，每个“代表”会向“主持人”提交自己的元数据更新信息(包括自己更新的元数据以及部分拥有的元数据)、元数据定购信息，“主持人”会将这些信息收集起来，并进行汇总，从而得到一个全局元数据更新视图和一个全局元数据定购视图，这样“主持人”就会将结合全局元数据更新视图将自己的元数据进行更新，同时判断自己更新后的元数据信息是否能满足所有元数据的定购需求。如果完全满足这些需求，则“主持人”就会按照每个“代表”的定购信息将其所需的元数据发送过去，并宣告会议的结束;如果不能满足所有的元数据的定购需求，“主持人”会收集无法满足的元数据，对这些元数据进行归类统计，得到一个全局元数据“重定购”视图，最后按照自己的元数据将满足每个“代表”定购信息的元数据发送过去，同时将全局 18 华中科技大学硕士学位论文 元数据“重定购”视图中的一部分发送过去，再宣告会议结束，这样定购信息没有完全满足的“代表”只好参加下次会议去获取想要的元数据信息。一旦会议结束，参加会议的“主持人”和“代表”将不再存在关联，并且下一次会议将在一段时间后由系统指派另一个节点进行组织。 3.2.2 轮值会议元数据分发的特点 RMMD综合了主动分发的准确性和被动分发的低代价性，并采用了HLA数据分发管理中采用的数据过滤机制，它具有如下的几个特点。 第一，RMMD通过系统轮转触发机制可以在无结构化的纯P2P网络中引入局部集中控制机制，这样就能使元数据分发在局部范围内得到很好的实施，并且任何节点都有机会成为会议主持人并召集会议，只要能保证轮转机制的合理、公平、高效的展开，就能保证整个网络中的元数据得到较高效率的分发，至于怎样保证轮转机制的实施将会在下一节的RMMD的具体设计及实现中阐述。 第二，每一个被触发的节点就是一个局部范围内的服务器，一方面它可以让自己的元数据得到很好的更新，另一方面它又可以将自己的元数据分发给其他参加会议的节点，至于会议范围的确定以及分发怎样的元数据给会议参加节点，这些都会在下一节的RMMD的具体设计及实现中阐述。 第三，轮值会议的开展可以保证整个网络中的元数据在较低的成本代价下得到准确的配置，同时通过轮值会议可以让与会的节点对一定范围内的节点有更好的了解，而在传统的纯P2P网络中，每个节点仅仅了解与自己建立直接连接的节点(即为“邻居节点”)，这一改进将能给在纯P2P网络中提供更好的网络应用和网络配置创造很好的条件。 3.3 轮值会议元数据分发的协议 3.3.1 轮值会议协议设计 为了让RMMD机制得到实际的应用，并让元数据分发策略得到实施，必须合理的设计轮值会议协议。 19 华中科技大学硕士学位论文 1. 会议相关节点定义 与会议有关的节点分为:“会议候选节点”，“会议主持节点”，“会议预参加节点”，“会议参加节点”，“普通节点”。 “普通节点”是所有节点最原始的状态，即为所有节点初始化状态。 “会议候选节点”是指被系统触发的节点所处的状态，实际上它是一个中间状态，当节点在触发后没有与其他会议产生冲突，它就会在一段延迟时间(time_delay)后成为“会议主持节点”，反之它就会又转化为“普通节点”。 “会议主持节点”是指召开会议的节点所处的状态。 “会议预参加节点”是指接收到会议召开消息的节点所处的状态，它也是一个中间状态，如果在一段延迟时间(time_delay)内它收到“会议开始消息”，它就会成为“会议参加节点”，反之则它就会转化为“普通节点”。 “会议参加节点”是指参加会议的节点所处的状态。 为了保持系统能够正常的运转，在任何一个时刻任何一个节点有且只能处于这几种节点状态中的一种。 2. 会议相关消息定义 与会议有关的消息分为:“会议召开消息”，“会议开始消息”，“会议参加消息”，“会议结束消息”，“会议否决消息”。 “会议召开消息”是指“会议候选节点”被触发后向邻居节点发送的消息，此消息中包含了“会议候选节点”信息以及TTL值，收到这条消息的“普通节点”会成为“会议预参加节点”，并会取出TTL值，如果TTL不为1，就会将此消息的TTL值减去1后向自己的邻居节点进行转发，反之就不会转发。 “会议开始消息”是指“会议主持节点”向邻居节点发送的消息，此消息中包含了“会议主持节点”信息、会议延迟时间(time_meet)以及TTL值，收到这条消息的“会议预参加节点”就会成为“会议参加节点”，同时会向“会议主持节点”发送“会议参加消息”，并会取出此“会议开始消息”的TTL值，如果TTL不为1，就会将此消息的TTL值减去1后向自己的邻居节点进行转发，反之就不会转发。 “会议参加消息”即为“会议参加节点”向“会议主持节点”发送的消息，此 20 华中科技大学硕士学位论文 消息包含了此“会议参加节点”的元数据更新信息(包括自己更新的元数据以及部分拥有的元数据)、元数据定购信息。 “会议结束消息”是指会议定时到后“会议主持节点”向“会议参加节点”发送的消息，此消息包含了经过整理后满足“会议参加节点”定购信息的元数据及“重定购”的元数据。 “会议否决消息”是指发生冲突时相关节点向“会议候选节点”发送的消息，此消息中包含了否决时间time_deny，这样“会议候选节点”接收到此消息后，会取出time_deny值，将自己的会议按照此值进行延迟，这样系统就会在这段时间后再次对它进行触发。 3. 会议过程 对于会议主持人:每个节点都可以被系统随机触发为会议主持人，某个节点一旦被系统触发，就成为一个“会议候选节点”，它会向它的邻居节点发送“会议召开消息”，之后会延迟一段时间time_delay。如果在这段延迟时间内收到其他节点发来的消息，则说明存在冲突，它会使用冲突处理规则进行处理，处理完毕后它的会议有可能会被延迟一段时间，它会变为“普通节点”，另外它的会议也有可能得以继续进行，它会继续等待延迟时间time_delay的结束;如果延迟时间time_delay结束，则此节点就会成为“会议主持节点”，它就会向它的邻居节点发送“会议开始消息”，之后会延迟一段会议时间time_meet。如果在这段会议时间内收到“会议参加节点”发来的“会议参加消息”，它会将这些消息存储起来，而如果收到其他的消息，它会根据冲突处理规则进行处理;在会议时间time_meet结束前，它就会对所有“会议参加消息”中的元数据更新信息和定购信息进行汇总，从而得到一个全局元数据更新视图和一个全局元数据定购视图，这样它就会将结合全局元数据更新视图将自己的元数据进行更新，同时判断自己更新后的元数据信息是否能满足所有元数据的定购需求，如果完全满足这些需求，它就会按照每个“会议参加节点”的定购信息将其所需的元数据定购反馈发送过去，并宣告会议的结束;如果不能满足所有的元数据的定购需求，它会收集无法满足的元数据定购需求，对这些元数据进行归类统计，得到一个元数据“重定购”视图，最后按照自己的元数据将满足每个“会议参加节 21 华中科技大学硕士学位论文 点”定购信息的元数据定购反馈发送过去，同时将元数据“重定购”视图中的一部分发送过去，再宣告会议结束，此节点就会变为“普通节点”，系统会在某个时刻再次对它进行触发。 对于会议参与人:收到“会议召开消息”的普通节点会成为“会议预参加节点”，它会通过消息中的TTL值来判断是否转发此消息:如果TTL不为1，就会将此消息的TTL值减去1后向自己的邻居节点(除去“会议候选节点”)进行转发;反之就不会转发。之后它会延迟一段时间time_delay，如果在延迟时间结束前没有收到“会议开始消息”，则此节点就会成为“普通节点”;而如果收到其他的消息，则会使用冲突处理规则进行处理，然后继续等待;如果收到“会议开始消息”，则它就会成为“会议参加节点”，它会向“会议主持节点”发送自己的元数据更新信息(包括自己更新的元数据以及部分拥有的元数据)、元数据定购信息，同时会通过“会议开始消息”的TTL值来判断是否转发此消息:如果TTL不为1，就会将此消息的TTL值减去1后向自己的邻居节点(除去“会议主持节点”)进行转发;反之就不会转发。之后它会延迟一段时间time_meet，如果在会议时间结束前没有收到“会议结束消息”，则此节点就会成为“普通节点”;而如果收到其他的消息，则会使用冲突处理规则进行处理，然后继续等待;如果收到“会议结束消息”，则它会取出“会议主持节点”发来的元数据相关信息，首先根据元数据定购反馈信息对自己的元数据信息进行更新，同时结合收到的元数据“重定购”信息对自己的元数据定购信息进行更新，此节点就会变为“普通节点”。 4. 冲突处理规则 如果“会议主持节点”或者“会议参加节点”收到“会议召开消息”，则说明存在冲突，它就会从此消息中取出“会议候选节点”信息，并向“会议候选节点”发送一条“会议否决消息”，设正在进行会议的开始时间为meet_time_start，会议的延迟时间为time_meet，当前时间为time_now，则应设置此“会议否决消息”否决时间time_deny,time_meet,(time_now,meet_time_start)。 如果“会议候选节点”收到“会议召开消息”，则说明这两个预召开的会议存在 22 华中科技大学硕士学位论文 冲突，则它会比较两个会议的触发先后，如果对方的会议先召开，则它的会议就会延迟一段时间time_delay后再次被系统触发;而如果它的会议先召开，它就会从此消息中取出“会议候选节点”信息，并向“会议候选节点”发送一条“会议否决消息”，且设置此“会议否决消息”否决时间。 time_deny,time_delay 如果“会议预参加节点”收到“会议召开消息”，则它会取出“会议候选节点”信息，然后比较之前的“会议候选节点”与目前的“会议候选节点”是否相同，如果相同，则说明消息重复，无需进行别的处理;而如果不相同，则说明存在冲突，并且目前的预召开会议要晚于之前的那个预召开的会议，它向目前的“会议候选节点”发送一条“会议否决消息”，且设置此“会议否决消息”否决时间 。 time_deny,time_delay 如果“会议候选节点”收到“会议否决消息”，则说明存在冲突，它就会取出此消息中的否决时间time_deny，并设置自己的会议延迟一段时间time_deny后再次被系统触发。 5. RMMD协议的工作流程图 根据之前对于RMMD协议的相关介绍，可以将RMMD协议的工作流程图设计如图3.2所示。 3.3.2 轮值会议协议实现 1. 系统触发机制的实现 系统中的每个节点都有机会被系统触发成为“会议主持节点”，即“会议主持节点”这一角色会在各个节点间进行轮转，只有保证轮转机制的合理、公平、高效的展开，才能保证整个网络中的元数据得到较高效率的分发，而轮转机制高效的运作则建立在系统触发机制良好实现的基础上，下面将具体介绍系统触发机制的实现。 系统中的每个节点中都应包含一种随机被系统触发的机制，这样在系统运行初始化时就会给每个节点随机的分配一个会议触发时刻，这样随着系统当前运行时间的推移，当某一个节点的会议触发时刻到达时，它就会触发为“会议候选节点”，在冲突检测通过后它就会成为“会议主持节点”，那些参加会议的节点就会将自己的会 23 华中科技大学硕士学位论文 议触发时刻向后推移，具体推移数值取决于此次会议的延迟时间(具体数值为time_meet)，这样参加会议的节点就不会在参加会议时由于自己的会议触发时刻到达而产生不必要的冲突，会议结束后“会议主持节点”因为已经获得了一次被系统触发的机会，所以下一次被系统触发的时刻应该相对于其他还没有被触发的节点的时刻晚很多，这样这些节点就可以公平地获得被系统触发的机会，其中具体下一次触发时刻的设置应该主要取决于网络规模及每一次会议持续时间。另外，在会议触发遇到冲突时，“会议候选节点”将会议延迟一段时间进行，即取消当前的触发会议，将会议触发时刻推移一段时间(具体数值为time_deny)。 节点等待状态 否判断是否收到消息 是 是否为是否会议召开消息 向邻居节点转发是否为系统触发是会议召开消息否召开会议消息否向邻居节点发系统设置下次会议召开消息延迟时间是是否收到会会议触发时间否是否已到议开始消息判断是否收到消息否是延迟时间是是否参加会议，向邻居节是否已到判断是否为点转发会议开始消否是会议否决消息息，并向会议主持人发会议参加消息是否为其他节点是否会议召开消息 早于其他节点否是否会议时间是是否收到会召开会议否否已到议结束消息向邻居节点发会议开始消息是是 是否收到会议处理会议主持人分否是参加消息发来的元数据接收与会者发来的相关元数据 处理所以与会元数据，会议时间是向与会节点发会议结束否是否已到消息，并分发元数据 图3.2 RMMD的工作流程 2. 会议规模设置 24 华中科技大学硕士学位论文 会议的规模取决于“会议开始消息”的TTL值，TTL值越大，此消息传播的范围就会越大，参加会议的节点数就会越多，会议规模也就越大。同时由于会议规模越大，“会议主持节点”需要处理的信息会越多，这样就对“会议主持节点”的处理能力提出了很高的要求。借鉴2.4.3中关于数据网格中节点网格势能的定义及应用，可以将网格势能作为TTL值的主要衡量指标，这样TTL值可以看成节点的属性值，其设置方法如下:系统会在初始化时计算并收集所有节点的网格势能，设第i个节点的网格势能为GP，并设所有网格势能中最大的为GP，最小的为GP，可以设imaxmin置网格势能最小的节点的TTL值为1，由于TTL值越大，网络的延迟就会越大，这样就应该根据实际的网络状况设置网格势能最大的节点的TTL值，若设置其为TTL，此值应取为整数，则可知第i个节点的TTL值应该为:max ，这样系统初始化后每个节点举TTL,(TTL,1)*(GP,GP)/(GP,GP)，1，，imaximinmaxmin 行会议的会议规模就能确定。 3. 会议相关延迟时间设定 在会议召开的几个过程中，涉及到几个延迟时间的设定，分别为:time_delay，time_meet，time_deny，这几个延迟时间的设定将直接影响到轮值会议协议的实施，下面将对它们分别进行讨论。 在“会议候选节点”在向“会议主持节点”转变前，为了避免和周围正在举行的会议发生冲突，设定它延迟等待一段时间time_delay，由于消息在网络中的延迟，它的“会议召开消息”被正在参加(或者主持)会议的节点收到在网络中得一段时间延迟，而这些节点向它发送得“会议否决消息”也得一段时间延迟，如果time_delay设定过小，则有可能此次本应该被否决的会议得以非正常的召开，从而导致系统无法正常运行;而如果time_delay设定过大，则会导致会议协议运行效率的低下，因此应该根据实际情况中的网络状况进行设定这个值的大小。 在会议正式召开时，每个参加(或者主持)会议的节点均会延迟等待一段会议时间time_meet，这是因为“会议主持节点”向“会议参加节点”发送的“会议开始消息”在网络中转发得一段时间延迟，同时“会议参加节点”向“会议主持节点” 25 华中科技大学硕士学位论文 发送的“会议参加消息”在网络中也得一段时间延迟，而且“会议主持节点”对收集到的“会议参加消息”的处理也得耗费一些时间，特别是节点会议的TTL值越大，收到的消息越多，处理这些消息所需的时间也就越多，最后“会议主持节点”向“会议参加节点”发送的“会议结束消息”在网络中也得一段时间延迟。综述所述，可以得知time_meet的取值应该取决于网络状况和“会议主持节点”对众多消息的处理能力，因此time_meet值的具体大小应该结合网络状况、节点网络势能、节点TTL值等综合给定。 当会议举行发生冲突时，“会议候选节点”会收到“会议否决消息”，就会将会议延迟一段时间time_deny，这个值的具体设定可参见3.3.1节的“冲突处理规则”中的具体介绍。 3.3.3 元数据分发策略 参见2.4节中关于传统元数据分发技术的讨论可知，一方面，被动分发技术采用查询分发式，即当有查询请求到达时节点才分发自己拥有的元数据，这种方式虽然对网络资源的占用量小，具有低代价性，但是在网络资源频繁变化的环境中却无法保证节点元数据的准确性;另一方面，主动分发技术能在最大可能上保证元数据的准确性，但由于分发数据过多，对网络资源的使用量大，使得这种分发方式的效率较低。 对于被动分发没有什么策略控制可言，而对于主动分发，为了在保证一定分发准确性的前提下降低分发过程中对网络资源的占用，即提高它的分发效率，对它的分发策略研究较多，到目前为止，这些策略的研究很少有考虑被动分发机制的相关方法。通过研究HLA数据分发中采用的数据过滤机制，为如何在元数据分发策略的研究中将两种分发方式结合起来提供了很好的启示，即采用本章详细介绍的轮值会议元数据分发机制，下面将阐述RMMD采用的元数据分发策略。 在一次轮值会议中，众多的“会议参加节点”会向“会议主持节点”分发自己的元数据更新信息(包括自己更新的元数据以及部分拥有的元数据)，这即为主动分发方式，但是这种主动分发目标比较明确，即只分发给“会议主持节点”，所需的代 26 华中科技大学硕士学位论文 价低;同时“会议参加节点”还会向“会议主持节点”发送自己的元数据定购信息，即自己的元数据查询请求，然后等待“会议主持节点”向自己提供所需的元数据信息，这即为被动分发方式。“会议主持节点”在会议进行中相当于中心服务器的角色，它会收集到这个会议域内的所有元数据更新信息，同时还有一部分的全域元数据信息，这样它就可以对自己的元数据进行更新，从而获得一个“全局元数据视图”，然后再对照每个“会议参加节点”的元数据定购视图进行匹配，将这些查询请求的元数据反馈信息分发过去，这即类似于HLA数据分发中采用的数据过滤机制，同时完成了将主动分发方式与被动分发方式的结合，并完全继承了主动分发的准确性和被动分发的低代价性。 同时需要指出的是，在一次会议召开中所有“会议参加节点”的元数据定购请求是很难完全满足的。如果改变一下轮值会议分发策略，让“会议参加节点”将自己拥有的所有元数据(而非部分)分发给“会议主持节点”，这样肯定就能让“会议主持节点”收集到会议域内的全域元数据信息，这样就更有可能完全满足“会议参加节点”的元数据定购请求。但是这样所带来的结果是:“会议主持节点”会收到许多的冗余元数据信息，极大的增加“会议主持节点”的处理所需时间，而且会极大的增加网络的通信开销，这样就会导致分发的高代价。显然，这种改变是不可取的。 在本节的轮值会议协议设计中，当不能满足所有“会议参加节点”的元数据定购需求时，“会议主持节点”会收集无法满足的元数据定购需求，对这些元数据进行归类统计，得到一个元数据“重定购”视图，最后选取元数据“重定购”视图中的一部分发送给相应的“会议参加节点”，这样“会议参加节点”就会根据元数据“重定购”信息对自己的元数据定购信息进行更新。虽然这样做会导致会议相关消息数的增加，必然增加网络的通信开销，增加分发的代价，但是由于这些参加此次会议的节点可以去参加别的会议获取定购的元数据，即相当于将在这次会议没有获得满足的元数据定购请求向外传播出去，这样必然会提高元数据定购请求的命中率，可以进一步提高元数据分发的准确性，相对于分发代价的增大，对于分发准确性的提高效果还是很能值得的。 27 华中科技大学硕士学位论文 3.4 小结 本章首先介绍了设计的元数据分发机制的背景知识，为之后的具体设计打下了基础，随后介绍了轮值会议元数据分发机制的主要思想，并分析了其特点，最后详细设计并实现了该机制的会议协议以及元数据分发的具体策略。 28 华中科技大学硕士学位论文 4 原型系统开发与仿真实验分析 网格系统是一个非常庞大而且复杂的系统，在实际运行之前应确保系统具有设计时预期的性能表现，因此需要使用实验加以测试与验证，一般采用仿真实验的方式对网格系统进行评估。目前大多网格仿真软件是研究人员为验证自身研究成果而 [37][38][39]设计开发，如CAN Simulator，Gnutella Simulator，OptorSim等，但此类仿真软件设计目的单一，通用性较差，难以广泛使用。为了更好的对网格中元数据分发策略进行仿真，提高仿真的效率及仿真结果的有效性，拟采用OPNET 这一通用网络仿真工具来完成元数据分发方法的仿真工作。 本章首先介绍了RMMD的原型系统开发，之后分析了网络仿真工具OPNET的特点、构成以及工作原理，并通过OPNET提供的编程环境实现了RMMD算法以及传统的元数据分发算法，根据相关性能评价指标对实验结果进行了分析比较。 4.1 RMMD原型系统开发 根据3.3节对于RMMD的协议、分发策略的介绍与设计，可以将RMMD原型系统的结构设计如图4.1所示。 会议触发模块轮值会 议核心会议触发 模块会议召集模块元数据分 发模块 会议延迟模块会会议冲议召突进集产行生 冲突检测/处理模块 图4.1 RMMD原型系统的结构 RMMD原型系统的组成模块包括:轮值会议核心模块、冲突检测/处理模块，其 29 华中科技大学硕士学位论文 中，轮值会议核心模块包括:会议触发模块、会议召集模块、会议延迟模块、元数据分发模块，下面将对各个模块的功能进行相应介绍。 会议触发模块的功能是完成轮值会议的触发，网格系统中的每个节点中都应包含一种随机被系统触发的机制，被触发的节点将会成为“会议候选节点”进行会议的召集。此模块的具体实现参见3.3.2节的会议触发机制的实现。 会议召集模块的功能是完成“会议候选节点”向会议半径范围内的节点发送“会议召开消息”，并利用冲突检测模块检测此会议半径范围内是否有会议冲突，如果有则根据冲突处理模块对冲突进行处理，处理后再由会议延迟模块对相应的会议进行延迟处理;如果没有冲突则说明会议能正常进行，然后转入到元数据分发模块进行处理。此模块的具体实现参见3.3.1节的会议过程介绍。 会议延迟模块的功能是完成对会议冲突处理模块处理后需要进行延迟阻塞的会议进行相关设置，让此会议在相应时间后再次被系统触发。此模块的具体实现参见3.3.2节的会议相关延迟时间设定介绍。 元数据分发模块的功能是完成会议进行中的相关元数据在“会议主持节点”及“会议参加节点”间的分发，同时也要调用冲突检测/处理模块对会议半径范围内的会议冲突进行检测及处理。此模块的具体实现参见3.3.3节的元数据分发策略介绍。 冲突检测/处理模块的功能是完成对会议召集过程中、会议进行过程中的相关会议冲突进行检测及处理。此模块的具体实现参见3.3.1节的冲突处理规则介绍。 4.2 实验环境OPNET OPNET最早是由麻省理工学院信息决策实验室受美国军方委托开发，初始模型是由两个博士创建的，并于1987年建立了商业化的OPNET。OPNET迅速而稳步发展，作为高科技之网络规划、仿真及分析工具，OPNET在通信、国防及电脑网络领域已经被广泛认可和采用。成千上万的组织使用OPNET软件来优化网络性能、最大限度地提高通信网络和应用的可用性。目前共有大概2700个OPNET用户，包括企业、网络运营商，仪器配备厂商以及军事、教育、银行、保险等领域，OPNET近几年赢得的大 30 华中科技大学硕士学位论文 量奖项是对其在网络仿真中所采用的精确模拟方式及其呈现结果的充分肯定。 4.2.1 OPNET仿真机制 OPNET采用阶层性的模拟方式，从网络物件层次关系看，提供了三层建模机制，最底层为进程(Process)模型，以状态机来描述协议;其次为节点(Node)模型，由相应的协议模型构成，反映设备特性;最上层为网络(Network)模型。 OPNET采用离散事件驱动的模拟机制，其仿真核心实际上为离散事件驱动的事件调度器(Event Scheduler)，它对所有进程模块希望完成的事件和计划该事件发生的时间进行列表和维护。采用离散事件驱动的模拟机理，与时间驱动相比，计算效率 [40]得到了很大的提高。 4.2.2 OPNET编程特点 OPNET modeler进程—节点—网络三层结构的建模机制简单明了，在“进程层”模拟单个对象的行为，在“节点层”将其互连成设备，在“网络层”将这些设备互连组成 [40,41,42]网络，几个不同的网络场景组成“项目”，从而比较不同的设计。同时OPNET modeler图形化编程环境给使用者提供极大便利，图4.2即为OPNET modeler的三层核心编辑器的界面。 图4.2 OPNET modeler的核心编辑器界面 1. 网络编程器 31 华中科技大学硕士学位论文 网络编辑器以图形化的方式展示了通信网络的拓扑结构。网络包括节点和链路，这些对象可以通过对话框来进行配置。从编辑器的对象面板上拖拉，点击节点和链路或者使用导入拓扑结构和快速对象配置来建立网络。 2. 节点编程器 节点编辑器通过描述功能模块以及模块之间的数据流来展示网络设备和系统的体系结构，它是用来定义每一个节点的行为，一般来说，每一个节点通常由多个模块组成，其行为由其使用的不同的模块决定。每个模块完成一部分节点行为，同时每个模块可以生成，发送和接受来自其它模块的包。 3. 进程编程器 进程编辑器使用强大的有限状态机(FSM)来支持规范、协议、应用，算法以及排队策略。可以用状态和转移条件图形化的定义一个事件的逻辑。每个状态包括C/C++代码以及专门为协议编程设计提供的丰富的库函数。有限状态机是动态的，并且可以在仿真中对其它有限状态机引起的特定事件进行响应。 作为OPNET modeler 三层建模机制的最底层，进程模型是实施各种算法的载体因此也是进行离散事件算法仿真所要研究的重点。对于仿真来说，仿真的控制权不断地在进程模型和仿真核心之间转移，当事件到达时，仿真核心确定该事件应该交给哪一个进程进行处理，控制权随后转交给了该进程模型，进程模型进入活动状态，进程模型根据到达的事件种类，进行相应处理，处理后重新把控制权交回给仿真核心，进程模型进入阻塞状态，即进程模型就是不断在阻塞和活动状态之间进行转换。 对于进程模型主体之一的状态转换图来说，两个最主要的组成元素就是“状态”和“转换”，这就是离散事件分析的基础。 状态的含义就是进程在仿真进行当中所处的众多模式中的一个，状态之间既是互斥的，又是互补的，进程在收到中断之后，就会从一个状态转移到另一个状态。OPNET中共有3中状态:初始(initial)状态、强制(forced)状态和非强制(unforced)状态。初始状态是进程被访问的第一个状态，一般在此状态中进行变量的初始化工作;对于强制状态，指的是当仿真进入到此状态后，仿真核心不允许其停留在这个状态，强制其立即转移到下一个状态;对于非强制状态，进行非强制状态后的仿真，将停 32 华中科技大学硕士学位论文 留在那个状态，等待触发唤起。 每个状态都有相应的动作与其对应，这些动作就是执行代码。每个状态的执行代码分为上下两个部分，上面部分称为执行代码(enter executive)，下面部分成为离开执行代码(exit executive)，分别在仿真进入或离开这一状态时执行。 图4.3显示了OPNET进程模型中的非强制状态的执行流程。 对于非强制状态，当进 进入代码 开始激活 程执行完进入代码后， 阻塞 处于阻塞状态，并等待一旦激活，则进程 等待中断 被激活。 执行该状态的离开 离开代码 代码，然后立即转 根据对条件的判断，转移到下一个状态，执 线将指导进程进入下一个行其进入代码，然 状态或者返回本状态。 后再次被阻塞。 进入代码 阻塞 等待中断 离开代码 结束激活 图4.3 OPNET进程模型中的非强制状态的执行流程 强制状态就其本质来说并不能称为状态，因为系统并不会停留在强制状态上。强制状态只是由于编程的需要，为了有限状态机编程的方便而提出的一个状态。通过使用强制状态，能够方便而有效地把非强制状态分开，增加状态转换图的模块化，使其可读性大大地加强，图4.4显示了加入强制状态后的状态执行流程。 激活后从非强若在相邻非强制状态之间存在非强制状态 制状态的离开在多个强制状态，则这些状的进入代码执 代码开始执行 态将一次性顺序执行 行后结束激活 图4.4 加入强制状态后的状态执行流程 33 华中科技大学硕士学位论文 4.3 仿真模型 按照OPNET仿真建模机制，应该采用网络—节点—进程三层结构进行构造，由于要对RMMD、主动分发、被动分发进行相应的仿真并最后进行对比，所以只需要根据三种分发方式的不同定义好相应的进程级模型，并让相应的进程级模型部署到相同的网络、节点层上，即此仿真模型的网络层、节点层对于不同的分发算法都是一致的，这也即是OPNET仿真设计的优势所在。下面将对相应各层的模型的设计进行具体介绍。 4.3.1 仿真网络级模型 根据OPNET仿真设计的需要，首先应该将最上层的网络级模型实现出来，图4.5所示的即为本文仿真实验的网络级模型。 图4.5 仿真网络级模型 根据3.1.1节网络拓扑结构的介绍，对数据网格进行了分层设计，由于仅研究元数据服务器之间的分发算法设计，即只需考虑设计上层—纯P2P层(非结构化)。再根据3.1.2节对于小世界网络模型的介绍可知，目前流行的很多纯P2P网格是满足小 34 华中科技大学硕士学位论文 世界特性的，故将此网络级模型设计为符合Small- World特性，仿真实验中具体设计如下:网络由35个节点组成，如图4.5中所示，节点按照node_1到node_35进行编号，每个节点都于其最近的2个相邻节点相连，同时考虑到实际网络结构的随机性，让一部分节点随机的与另一个节点相连。这样构造后，节点的连接度为2或者3，即连接度比较均匀。 另外，为了简化处理，对于仿真系统中数据资源的设置如下:在仿真中设定数据资源为100个不同的文档，且每个文档都会有多份的拷贝，用数字0到99来标识这样文档的元数据。初时化时，对于各节点元数据资源分布设置如下:平均每个节点拥有10个文档的元数据，且请求5个文档的元数据，这样每一种文档大约有3.5个备份，其中请求的元数据满足3.1.3节中介绍的Zipf分布，即仿真系统中80,的元数据请求集中于20,的元数据资源上。 4.3.2 仿真节点级模型 6所示 根据上层(网络层)的需要对OPNET仿真的节点级模型进行设计，图4.的即为本文仿真实验的节点级模型。 图4.6 仿真节点级模型 由于网络层中设计了每个节点连接度为2或者3，故设计此节点级模型中包括3对收,发信机，如图4.6所示，收,发信机按照rec0-xmt0到rec2-xmt2进行编号。当节点的连接度为3时，收发,信机没有空闲的;而当节点的连接度为2时有一对收发,信机空闲。其中收信机的功能就是模拟从相应的节点端口中收取数据包，发 35 华中科技大学硕士学位论文 信机的功能就是模拟把节点产生的数据包从相应的节点端口发送出去，而对于数据包的处理/产生工作模拟则集中在图4.6中processor模块上面，这样对应于不同的分发算法，processor模块的设计就不同，即在OPNET进程级设计就不同。 4.3.3 仿真进程级模型 不同的分发算法，应该对应于不同的进程级模型，图4.7给出的即为RMMD的进程级模型，它采用有限状态机(FSM)来定义和实现了轮值会议元数据分发的协议，关于它的具体描述将在4.4节进行介绍。 图4.7 RMMD进程级模型 图4.8给出的即为主动/被动分发的进程级模型，之所以将这两种分发方式的FSM图设计相同，是因为这两种分发协议都比较简单，且处理过程类似，但实际仿真中此FSM图中的各个状态包含的代码是完全不同的。 图4.8 主动/被动分发进程级模型 36 华中科技大学硕士学位论文 4.4 仿真算法 4.4.1 仿真数据结构 由于OPNET仿真主要基于数据包的通信，通信协议也必须通过包的字段来进行 体现，因此仿真中所使用包的数据结构是整个仿真数据结构的核心，下面将分别对 RMMD及主动/被动分发算法中的包的数据结构进行介绍。 1(RMMD中包的数据结构 struct pk_format_RMMD { object id meet_pro_objid; //会议召开者的ID标识 int meet_size; //会议召开规模 int meet_ttl; //会议消息的TTL值 int meet_try; //会议召开消息标识 int meet_start; //会议开始消息标识 int meet_deny; //会议否决消息标识 int meet_hold; //会议参加消息标识 float meet_time; //一次会议持续的时间 int meet_distance; //会议消息所经过的节点数统计 int file_pro[10]; //节点提供的元数据标识数组 int file_req[5]; //节点请求的元数据标识数组 } 2(主动分发中包的数据结构 struct pk_format_ACTMD { object id act_pro_objid; //主动分发节点的ID标识 int act_size; //主动分发的规模 int act_ttl; //主动分发消息的TTL值 int act_distance; //主动分发消息所经过的节点数统计 int file_pro[10]; //节点提供的元数据标识数组 } 3(被动分发中包的数据结构 37 华中科技大学硕士学位论文 struct pk_format_PASMD { object id pas_pro_objid; //被动分发节点的ID标识 int pas_size; //被动分发的规模 int pas_ttl; //被动分发消息的TTL值 int pas_distance; //被动分发消息所经过的节点数统计 int file_req[5]; //节点请求的元数据标识数组 } 4.4.2 RMMD仿真算法描述 根据第三章的RMMD协议设计，参见图4.7中的FSM图，节点首先进入init状态，系统会对节点进行初时化，然后进入idle状态等待。如果系统对节点进行会议触发，则Self_intrpt条件满足，它会按照RMMD协议进行工作，会议可能得以进行或者会议冲突延迟，最后都会回到idle状态继续等待;如果节点收到会议相关消息，则Strm_intrpt条件满足，它也会按照RMMD协议进行工作，参加会议结束后会回到idle状态继续等待。下面将对上述过程的主要核心算法进行介绍。 1(系统对每个节点初始化:具体来说，应该对仿真统计变量、节点定义的状态变量、节点触发会议的时间、节点的会议消息TTL值选取、会议持续时间选取、节点的收,发信机状态、节点提供和请求的元数据资源标识数组等进行相应的设置。 算法4.1:节点收,发信机状态设置算法。 Procedure init_xmt() Begin Foreach n in nodes Begin Foreach xmt_index in n Begin If 对应于xmt_index有远程的接收机相连 then flag[xmt_index] = 1 Else flag[xmt_index] = 0 End End End 38 华中科技大学硕士学位论文 2(节点获得系统的会议触发，按照3.3.1节中RMMD协议设计进行处理: Self_intrpt条件满足，于是转入到meet_try状态，向邻居节点分发完“会议召开消息”后等待延迟时间time_delay的结束，同时还要进行冲突检测，如果有冲突就要进行处理。延迟时间结束后转入到meet_hold状态向邻居节点分发“会议开始消息”，并接着转入到meet_deal状态等待，等待延迟时间time_meet的结束，同时还要进行冲突检测，如果有冲突就要进行处理，延迟时间结束后分发“会议结束消息”，最后转入到idle状态等待下次会议的触发。下面将对核心算法内容进行介绍。 算法4.2:“会议候选节点”向邻居节点分发“会议召开消息”算法。 Procedure meet_try() Begin If 会议候选节点没有邻居节点then Return Else Foreach 邻居节点n Begin 设置会议召开消息相关标识 通过相应的发送机向邻居节点的相应收发机发送此消息 End End 算法4.3:“会议候选节点”冲突检测与处理算法。 Procedure collision_deal_meet_try() Begin If 检测到有会议否决消息 then 获取此消息中的延迟时间time_deny 将自己的会议延迟time_deny时间 Else if 检测到有会议开始消息 then 获取此会议的开始时间 If 对方会议的开始时间早于本会议的开始时间 then 将自己的会议延迟time_delay时间 Else 向对方发会议否决消息 设置会议否决时间time_deny = time_delay End 算法4.4:“会议主持节点”冲突检测及处理算法。 Procedure collision_deal_meet_deal() 39 华中科技大学硕士学位论文 Begin If 检测到有会议开始消息 then 获取自己的会议开始时间meet_time_start 获取会议的延迟时间为time_meet 获取当前时间为time now 向对方发会议否决消息 设置会议否决时间 time_deny,time_meet,(time_now,meet_time_start) End 3. 节点收到会议相关消息，按照3.3.1节中RMMD协议设计进行处理:首先节点收到“会议召开消息”转入到“会议预参加节点”状态，等待延迟时间time_delay结束，如果在时间结束前收到非“会议开始消息”就会进行冲突检测，如果在时间结束时还没有收到“会议开始消息”，就会转到idle状态，如果收到了“会议开始消息”就会转到meet_start状态并向自己的邻居节点转发此消息，然后进入meet_join状态等待会议时间time_meet的结束，结束前如果收到非“会议结束消息”就会进入冲突检测，如果收到“会议结束消息”就更新自己的元数据信息和元数据定购信息，最后转入到idle状态。由于这里的各种处理算法跟前面的介绍有很多类似，在这里就不再进行详细描述了。 4.5 实验与性能分析 实验采用OPNET对轮值会议元数据分发(RMMD)、主动元数据分发(ACTMD)和被动元数据分发(PASMD)分别进行仿真部署，依照4.3节仿真模型的设计实施对这三种分发策略的仿真对比测试。由于元数据分发是为了让网格中的节点更加快捷有效地获得所需要的元数据，即提高这些节点查询元数据的效率，而查询效率则主要体现在:查询的准确性、查询的响应时间及查询所需的代价，因此在仿真实验中主要收集如下几个仿真统计信息:平均查询命中率、平均每个查询所需的时间、平均每个查询所需的消息数。另外，由于实际网格中，各个节点的分发半径是不一样的，但是对于整个网格会有一个平均分发半径，在仿真实验中所说的分发半径都是指网格的平均分发半径，下面将分别介绍仿真实验所收集到的测试结果及分析。 40 华中科技大学硕士学位论文 图4.9表示分发半径与平均查询命中率之间的关系。从图中分析可知，对于这三种分发策略，当分发半径增大时，查询命中率必然会增加，这是因为当分发半径越大时，网格中各个节点获取别的节点分发过来的元数据的可能性就会增大，这样他们元数据的准确性就会相应提高，从而使得系统节点的平均查询命中率增加。另外，从图中可以看出，被动分发策略的查询命中率明显小于主动分发和轮值会议分发，其成功率偏低;同时，在分发半径为1时，主动分发的查询命中率高于轮值会议元数据分发，但随着分发半径的增加，轮值会议的查询命中率增长速度明显快于主动分发，在分发半径大于2后轮值会议分发的查询命中率超过主动分发，且当分发半径5时基本上可以获得100,的查询命中率。对于主动分发策略，一直到分发半径等于7时才能获得将近100,的查询命中率。从上述的数据分析可知:轮值会议元数据分发能够保证很高的分发精确性，并能在比较小的分发半径内保证元数据在整个网格中的较好配置，这也充分体现了RMMD策略的优势。 100 80 RMMD60ACTMD40PASMD 20 平均查询命中率(%)0 01234567 分发半径(TTL数) 图4.9 分发半径与查询命中率的关系曲线 图4.10表示分发半径与每查询所需消息数之间的关系。从图中分析可知，对于这三种分发策略，由于分发半径的增加，平均每查询所需的消息数是逐渐增加的。特别是对于主动分发方式而言，因为分发半径越大，即分发消息的TTL值越大，分发消息转发的半径越大，会导致网络中的分发消息呈现指数级的增长，虽然查询的命中率增加了，即整个网格中的查询成功数增加了，但是平均每查询所需的消息数会呈现至少线型级的增长，这也充分说明了主动分发的高代价性。对于被动分发而言，虽然分发半径的增大也会使总的分发消息呈现较大的增加，但是由于总的查询 41 华中科技大学硕士学位论文 成功数增加了，故平均每查询所需的消息数只会随着分发半径的增加呈现较小的增加，这即体现了被动分发的低代价性。对于RMMD策略而言，由于分发半径越大，即会议半径越大，会议过程中产生的会议消息数越大，但是由于会议半径越大，元数据在网格中配置得就会越好，查询成功数就会越大，这样平均每查询所需的消息数也只会有一定的增加，这也充分体现了RMMD策略具有类似于被动分发的低代价性。另外，当会议半径为5时，RMMD策略的查询命中率基本上接近100,，当会议半径大于5后，平均每查询的消息数会显著的增加，类似于主动分发策略，这是应该要避免的。这说明对RMMD策略来说，分发半径存在一个最好的有效值。 40 35 30RMMD25 20ACTMD15PASMD10 5每查询所需消息数0 01234567 分发半径(TTL数) 图4.10 分发半径与每查询所需消息数的关系曲线 图4.11表示分发半径与每查询所需时间之间的关系。从图中分析可知，随着分发半径的增加，虽然分发的时间会增加，但是查询成功数增加了，所以主动分发和被动分发的平均每查询所需时间是逐渐减小的，这即说明了分发半径越大，元数据越能在网格中得到较好的配置，这样平均每查询所需的时间就会越小，同时，被动分发的每查询所需时间明显大于主动分发，其查询时间偏长，这也充分体现出了主动分发的优势所在。对比主动分发与RMMD，在会议半径小于5时，虽然RMMD策略会耗用一些时间用于召开会议，但是由于会议的召开使得元数据在网格局部域中的配置取得很好的效果，从而能在很大程度上缩短相应的查询时间，因此在平均每查询所需的时间这一指标上的对比中，RMMD体现出了相对于主动分发的优势;但是由于在分发半径为5后，RMMD策略的查询命中率基本上接近100,，而如果再对分发半径进行增加，就会增加用于会议召开的时间，这样平均查询时间反而会 42 华中科技大学硕士学位论文 增加，这即说明RMMD策略的平均查询时间存在极小值，造成这的主要原因是会议的召开需要额外的时间开销。这也说明对RMMD策略来说，分发半径存在一个最好的有效值。 0.5 0.45 0.4 RMMD0.35 ACTMD0.3 PASMD0.25 0.2每查询所需时间(s)0.15 1234567 分发半径(TTL数) 图4.11 分发半径与每查询所需时间的关系曲线 综上所述，RMMD策略确实兼具了主动元数据分发的准确性和被动元数据分发的低代价性，它能快捷有效的完成元数据在整个网格中的分发，让整个网格的元数据在较短的时间内、用较小的代价得到较好的配置。同时RMMD能在较小的分发半径内完成元数据分发，并且分发半径并不是越大越好，它存在一个最好的有效值。 4.6 小结 本章首先介绍了RMMD的原型系统开发，之后分析了OPNET网络模拟器的工作原理，其次针对主动元数据分发、被动元数据分发及RMMD策略设计了具体的仿真模型，并介绍了仿真算法的具体描述，最后给出实验结果，分析了实验结果产生的原因，为前面RMMD策略设计与分析提供了实验论证。 43 华中科技大学硕士学位论文 5 总结与展望 5.1 本文工作总结 本文先对元数据及其在网格中的国内外应用和研究做了初步探索，随后对网格中元数据的分类、元数据常有的标准化问题以及元数据分发方式做了相应的分析和介绍，并详细介绍了传统的数据分发技术以及数据网格中的传统元数据分发技术。通过一系列的研究和比较，提出了一种适用于数据网格环境下的元数据分发策略。该策略综合了主动分发的准确性和被动分发的低代价性，并采用了HLA数据分发管理中采用的数据过滤机制，能快捷有效的完成元数据在整个网格中的分发，具有较高的效率。 本文在设计元数据分发策略的过程中，所做的主要工作是: 1(对元数据及其在网格中的国内外应用和研究进行了介绍，分析比较了传统的数据分发技术以及数据网格中的传统元数据分发技术，对数据网格中网络拓扑分层进行了讨论，并介绍了小世界网络特性与Zipf定律。 2(设计并实现了一种新的元数据分发机制—轮值会议元数据分发(Rotating Meeting Metadata Dissemination, RMMD)，此分发策略综合了主动分发的准确性和被动分发的低代价性，并采用了HLA数据分发管理中采用的数据过滤机制，此策略能快捷有效的完成元数据在整个网格中的分发，让整个网格的元数据在较短的时间内、用较小的代价得到较好的配置。 3(初步设计与实现了一个RMMD的系统原型，并采用OPNET网络模拟器针对主动元数据分发、被动元数据分发及RMMD策略设计了具体的仿真模型，并介绍了仿真算法的具体描述，最后给出实验结果，分析了实验结果产生的原因，通过仿真对比测试为RMMD策略设计与分析提供了实验论证。 44 华中科技大学硕士学位论文 5.2 展望 在本文的工作基础上，以下方面值得进一步的深入研究: 1(通过4.5节仿真实验结果分析可知，RMMD策略的分发半径并不是越大越好，它存在一个最好的有效值，通过初步分析，此值应该由网格规模、网络质量、节点分布等因素决定，由于它的具体大小对整个分发策略的性能影响是很大的，故今后工作重点可围绕这一方面进行深入探讨。 2(由于通过轮值会议的开展可以让与会的节点对一定范围内的节点有更好的了解，而在传统的纯P2P网络中，每个节点仅仅了解与自己建立直接连接的节点(即为“邻居节点”)，这一改进将能给在纯P2P网络中提供更好的网络应用和网络配置创造很好的条件，这也将是研究的一个很重要方向。 3(目前大多网格仿真软件是研究人员为验证自身研究成果而设计开发，但此类仿真软件设计目的单一，通用性较差，难以广泛使用。本文将OPNET 这一通用网络仿真工具引入网格系统的仿真工作，实际效果还是不错的，尝试使用这个仿真软件构建一个相对通用的网格仿真环境将是下阶段工作的方向之一。 45 华中科技大学硕士学位论文 致 谢 在我的毕业论文即将完成之际，在我即将完成研究生学业之时，我要衷心地感谢多年来悉心教导过我的老师们、热心帮助过我的同学和亲人朋友们。 首先要感谢我的导师卢炎生教授，本文是在他的悉心的教诲和无微不至的关怀下完成的。卢老师深厚的理论功底、渊博的学识、儒雅的学术风范和兢兢业业、精益求精的工作态度鞭策着我不断进取;卢老师宽广的胸襟、豁达的人生态度、和蔼可亲的待人方式给我太多的启迪，将会让我终身受益。由衷感谢卢老师对我孜孜不倦的教诲和无微不至的关怀，有幸师从卢老师将是我一生的骄傲! 感谢徐丽萍副教授在课题研究上给我悉心的帮助和指导。徐老师严谨的学术态度和忘我的工作精神无时无刻不在激励着我，徐老师对我们生活上的关心和照顾也让我倍感亲切。在此特别感谢徐老师对我的鼓励，帮助和信任。 感谢殷贤亮副教授、杨茂林老师、赵小松老师、谢晓东老师、潘鹏老师、吴海老师、江胜老师、瞿彬彬老师等各位老师在学习和生活中对我的指导和帮助，从你们身上我学到了丰富的知识和宝贵的经验。 感谢同课题组的黄明杰、贺记牢、张慧娜、郭慧峰、曹冬梅同学，你们扎实的学识和经验，勇于钻研的精神，认真负责的工作态度令我印象深刻。 感谢师兄许浒、刘波、黄靖、顾海波、宋锦、王轩、袁刚、张卫，师姐孙显姣、李珺，感谢你们给予我的关心和帮助，你们是我学习的榜样。感谢李支成、陈锦富、石磊、陈巍、周伟芳、黄晋、申敏杰、梁薇、张平等同学，感谢实验室所有的师兄师姐和师弟师妹们，感谢你们和我一起度过快乐的时光。 感谢我的父母和我的哥哥。一直以来，他们都无私地为我贡献着，风风雨雨陪伴我走了过来。回首这两年走过的路，回顾过去的点点滴滴，觉得万分地感动。我要向他们深深地鞠一躬! 最后感谢所有关心、爱护和帮助过我的亲人和朋友! 46 华中科技大学硕士学位论文 参考文献 [1] Foster I, Kesselman C. The Grid: Blueprint for a New Computing Infrastructure. San Francisco, CA, USA: Morgan Kaufmann Publishers,1999.47~90 [2] I. Foster. The Grid: A New Infrastructure for 21st Century Science. Physics Today, 2002, 55(2): 42~47 [3] Fox F, Gannon D. Computational grids. Computing in Science & Engineering, 2001, 3(4): 74~77 [4] I. Foster, C. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. San Francisco, USA: Morgan Kaufmann Publishers, 1999. 6~677 [5] I. Foster, C. Kesselman. Globus: A Metacomputing Infrastructure Toolkit. International Journal of Supercomputer Applications, 2003, 11(2): 115~128 [6] Ian Foster. The Globus Toolkit for Grid Computing. in: Proceeding of the 1st IEEE/ACM International Symposium on Cluster Computing and the Grid, 2001. 2~2 [7] B. Segal, L. Robertson, F. Gagliardi. Grid computing: the European Data Grid Project. Nuclear Science Symposium Conference Record, IEEE, 2000, 15(l): 20~31 [8] Z. Xu, W. Li. Research on Vega Grid Architecture. Journal of Computer Research and Development, 2002, 39(8): 37~43 [9] 刘嘉. 元数据导论. 第1版. 北京: 华艺出版社, 2002. 11~60 [10] Sharon Brunett, Karl Czajkowski, Steven Fitzgerald, et al. Application Experiences with the Globus Toolkit. in: Proceedings of the 7th International Symposium on High Performance Distributed Computing, 1998. 81~88 [11] Ellert M., Konstantinov A., Konya B., et al. The NorduGrid project: Using Globus Toolkit for Building GRID Infrastructure. in: Nuclear Instruments and Methods in Physics Research, 2003. 502(2): 407~410 [12] Jianghua Liang, Vijay K. Vaishnavi, Art Vandenberg. Clustering of LDAP Directory Schemas to Facilitate Information Resources Interoperability Across Organizations. 47 华中科技大学硕士学位论文 in: Proceedings of IEEE Transactions on Systems, Man and Cybernetics, 2006, 36(4): 631~642 [13] 金海, 邹德清, 韩宗芬. 基于Web的网格系统的实现. 小型微型计算机系统, 2003, 24(12): 2053~2056 [14] 付伟. 数据网格中元信息服务系统的设计与实现: [硕士学位论文]. 保存地点: 国防科学技术大学, 2003. [15] M. Maheswaran. Data dissemination approaches for performance discovery in grid computing systems. Parallel and Distributed Processing Symposium. in: Proceedings 15th International, 2001:910~923. [16] M. Maheswaran and K. Krauter. A parameter-based approach to resource discovery in Grid computing systems. in:1st IEEE/ACM Int'l Workshop on Grid Computing (Grid'00), Dec.2000. [17] 王意洁, 肖侬, 任浩等. 数据网格及其关键技术研究. 计算机研究与发展, 2002, 39(8): 943~947 [18] Ewa Deelman, Gurmeet Singh, Malcolm P. Atkinson, et al. Grid-Based Metadata Services, in: Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM’04), 2004. 1099~1108 [19] 尹文燕. 元数据发展现状及存在问题研究: [硕士学位论文]. 保存地点: 中国科 学技术信息研究所, 2003. [20] 武劼. 基于元数据的数字图书馆信息系统的研究: [ 硕士学位论文]. 保存地点: 北京师范大学, 2001. [21] Jean-Pierre Kent, Maarten Schuerhoff. Some Thoughts About a Metadata Management System. in: Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, 1997. 174~185 [22] Gurmeet Singh, Shishir Bharathi, Ann Chervenak, et al. A Metadata Catalog Service for Data Intensive Applications. in: Proceedings of the ACM/IEEE SC2003 Conference(SC’03), 2003. 33~49 [23] Peng Gu, Yifeng Zhu, Hong Jiang, et al. Nexus: A Novel Weighted-Graph-Based Perfetching Algorithm for Metadata Servers in Petabyte-Scale Storage Systems. in: 48 华中科技大学硕士学位论文 Proceedings of the Sixth IEEE International Symposium on Cluster Computing and the Grid (CCGRID’06), 2006. 8~15 [24] 杨德婷. 科学数据库元数据标准系统设计与应用: [硕士学位论文]. 保存地点: 中国科学院计算机网络信息中心, 2003. [25] DMSO. High Level Architecture Interface Specification, Version 1.3 [S]. Defense Modeling and Simulation Office, April 1998. [26] Van Hook D J, Calvin J O. Data Distribution Management in RTI1.3[C]. Proceedings of the 1998 Spring Simulation Interoperability Workshop (SIW), Spring 1998. [27] 侯朝桢. 基于HLA/RTI的分布式交互仿真体系结构及数据分发管理:[博士学位 论文]. 保存地点:北京理工大学,2003.33~51 [28] 陈妍. CDN网络中对象一致性算法研究. 电子学报，2005,8:1480~1483 [29] A Ninan. Maintaining Cache Consistency in Content Distribution Networks[D]. Master's thesis ,Department of Computer Science ,Univ. of Massachusetts , June 2001. [30] 吕智慧. 基于网格架构的分布式内容分发模型. 计算机工程，2005,18:38~40 [31] Srikumar Venugopal, Rajkumar Buyya, Kotagiri Ramamohanarao. A Taxonomy of Data Grids for Distributed Data Sharing, Management, and Processing. in: ACM Computing Surveys (CSUR), 2006. 38(3): 1~53 [32] Foster I , Kesselman C , Tuecke S. The Anatomy of the Grid: Enabling Scalable Virtual Organizations [J]. International Journal of Supercomputer Applications, 2001 ,15 (3) :1~10 [33] Kleinberg J. The small-world phenomenon and decentralized search. SIAM News,2004,37(3):1~2 [34] Watts D J, Strogatz S H. Collective dynamics of small-world networks.Nature,1998,393(4):440~442 [35] JON K leinberg. The Small-World phenomenon: An algorithmic perspective. ACM Symp on Theory of Computing, 2000,28(4).820~828 [36] Lee Breslau, Pei Cao, Li Fan, et al. Web Caching and Zipf-like Distributions: Evidence and Implications. In: Proceedings of IEEE INFOCOM, New York, NY, 49 华中科技大学硕士学位论文 USA. 1999. USA: IEEE Computer Society, 1999. 126~134 [37] S Ratnasamy, P Francis, M Handley, et al. A Scalable Content-Addressable Network [C]. In Proc. of the ACM SIGCOMM 2001 Technical Conference. San Diego, CA, USA. 2001. [38] M Portmann, A Seneviratne. Cost-Effective Broadcast for Fully Decentralized Peer-To-Peer Networks [J]. Computer Communications Journal, Special Issue on Ubiquitous Computing. 2002. [39] William H. Bell, David G. Cameron, Luigi Capozza, et al. OptorSim-A grid simulator for studying dynamic data replication strategies. International Journal of High Performance Computing Applications, 2003,17(4):403~416 [40] 陈敏. OPNET网络仿真. 北京:清华大学出版社，2004，1~164 [41] 王文博，张金文. OPNET Modeler与网络仿真. 北京:人民邮电出版社，2003， 1~211 [42] 孟 晨. OPNET通信仿真开发手册. 北京:国防工业出版社，2005，1~120 50