（计算机系统结构专业论文）开放分布系统中动态资源发现和组合研究.pdf

开放分布系统中动态资源发现和组合研究 摘要 在对等网络( p e e r - t o p e e r ) 、网格( g r i d s ) 及服务计算( s e r v i c ec o m p u t i n g ) 等系统中， 许多分布在不同组织和位置的参与节点需要共享其他节点的资源或协作共同 提供服务，这些系统称为开放分布系统( o p e nd i s t r i b u t e ds y s t e m s ) ，它们都是建立 在i n t e m e t 基础设施上，通过i n t e m e t 把参与的节点连接起来，它们具有许多相似的特 性：自治性，动态性，位置分散性，异构性和普适性等。 在这些系统中一个重要的问题就是如何快速准确发现这些服务，要使用和组合 这些服务，首先要能够动态地发现这些服务，如在简单的对等网络文件共享系统 中，我们如何根据元数据找到需要的文件，在网格系统中，我们如何根据任务需 求、资源和调度策略等来分配资源。另外一个重要的问题就是如何高效高质量地组 合这些服务。 本论文提出了基于覆盖网络、语义标记和流程驱动的资源发现和组合框架 o p e n g r i d ，重点解决开放分布系统中资源快速准确发现和资源高效高质量组合问 题，与以前的系统相比不同之处主要在于以覆盖网络和语义标记描述资源发现，以 资源覆盖网络为基础进行多策略的资源组合。 开放分布系统中资源是基础，我们对资源进行了抽象和语义描述，基 于o n t o l o g y 匹配改进资源发现，在资源覆盖网络之上进行资源发现和资源组 合，我们设计了偏覆盖网络和多生成树覆盖网络用于语义资源发现，并对异构网络 资源发现进行了优化，通过实验对比了语义资源发现在网状拓扑和幂律拓扑覆盖网 络中查询和更新半径、查全率和查准率等。在多策略的资源组合中，我们设计了资 源路径和资源图用于资源组合探测，通过启发式组合步骤组合资源覆盖网络上的分 布式资源，通过优化策略和主动失效恢复等来保证组合服务质量，通过实验对比资 源组合在两种不同类型覆盖网络上三种不同的组合算法组合成功率、性能、开销和 主动失效恢复效率等。 本论文的创新性研究成果主要有： 1 提出基于动态策略和语义标记的资源发现及选择算法和模型，通过语义标记进 一t 一 上海交通大学博士学位论文 行自动分类和元数据抽取，从而标识出资源及其之间的语义关联。通过索引和 查询资源及其语义关联等信息进行资源发现和选择操作，降低了资源匹配算法 复杂度，同时又扩展了资源匹配应用层次的广度和深度。我们对资源进行了抽 象和语义描述，利用o n t o l o g y 建模工具构建了资源相关的n o d e ，r e q u e s t ，p o l i c y , l i n k 和p r o c e s s 等多个o n t o l o g y ，在资源覆盖网络平台o p e n g r i d 之上进行资源发 现和资源组合。 2 提出了资源覆盖网络模型一偏覆盖网络和生成树覆盖网络，通过应用层虚拟连接 每个独立的节点，与传统覆盖网络不同的是，o p e n g r i d 中每个节点不仅可以提 供应用级数据路由，而且可以提供一系列增值应用级服务，这样每个资源节点 可以动态加入和退出资源覆盖网络。利用资源节点状态信息和虚拟覆盖连接， 就能快速有效地进行资源组合。 3 提出了开放分布系统资源发现和资源组合完整融合应用平台架构，以覆盖网络 为核心，进行语义资源发现和多策略的资源组合。在o p e n g r i d 平台中，我们 设计了偏覆盖网络和多生成树覆盖网络用于语义资源发现，并对异构网络资源 发现进行了优化。通过仿真实验表明基于资源覆盖网络的语义资源发现在网状 拓扑和幂律拓扑覆盖网络中比其它随机或静态算法具有更好的特性，主要体现 在查询和更新半径更小、更新跨度更小、查全率和查准率更高。 4 提出流程驱动的资源组合方案和策略，结合商业工作流和科学工作流研究成 果，以工作流、消息流和服务流为驱动，组合分布式的资源，以在这些组合资 源之上建立应用和服务。我们设计了资源路径和资源图用于资源组合探测，通 过启发式组合步骤组合资源覆盖网络上的分布式资源，通过优化策略和主动失 效恢复等来保证组合服务质量，通过仿真实验表明资源组合在两种不同类型覆 盖网络上我们提出的多策略的优化组合算法在组合成功率、性能、开销和主动 失效恢复效率等均有较大优势。 关键词：开放分布系统，网格计算，对等计算，资源发现，语义匹配，资源组合， 开放工作流，覆盖网络 s t u d yo nd y n a m i cr e s o u r c e sd i s c o v e r ya n dc o m p o s i t i o n i no p e nd i s t r i b u t e ds y s t e m s a b s t r a c t i ns u c hs y s t e m sa sp e e r - t o p e e r , g r i d sa n du b i q u i t o u sc o m p u t i n g ，m a n yp a r t i c i p a t e d n o d e sd i s t r i b u t e di nd i f f e r e n to r g a n i z a t i o n sa n dl o c a t i o n sn e e dt os h a r er e s o u r c e so fo t h e r n o d e so rp r o v i d es e r v i c e sc o o p e r a t i v e l y t h e s es y s t e m sa r ec a ll e do p e nd i s t r i b u t e ds y s t e m s t h e ya r eb u i l to nt h ei n t e r n e ti n f r a s t r u c t u r e ，i n t e r c o n n e c t e dw i t he a c ho t h e r t h e ys h a r e l o t so fs i m i l a rf e a t u r e s ：a u t o n o m y , d y n a m i c ，g e o g r a p h i c a l l yd i s t r i b u t e d ，h e t e r o g e n e i t ya n d p e r m i s s i v e o n ei m p o r t a n ti s s u eo ft h e s es y s t e m si sh o wt od i s c o v e rr e s o u r c e sf a s ta n dp r e c i s e l y t ou s ea n dc o m p o s et h e s er e s o u r c e s ，f i r s t ，w es h o u l dd i s c o v e rt h e s er e s o u r c e sd y n a m i c a l l y s u c ha si ns i m p l ep e e r - t o p e e rf i l es h a r es y s t e m ，h o ww ed i s c o v e ri m p o r t a n tf i l e sa c c o r d i n g t om e t a d a t a i ng r i ds y s t e m ，h o ww ea l l o c a t er e s o u r c e sa c c o r d i n gt oj o br e q u i r e m e n t s ， r e s o u r c e sa n ds c h e d u l i n gp o l i c i e s ，e t c a n o t h e ri m p o r t a n ti s s u ei sh o wt oc o m p o s et h e s e s e r v i c e se f f e c t i v e l yw i t hq o s t h i sd i s s e r t a t i o nd i s c u s s e do p e n g 7 i dr e s o u r c ed i s c o v e r ya n dc o m p o s i t i o np l a t f o r m b a s e do ns e m a n t i cm a r k u pa n ds c i e n t i f i cw o r k f l o w ，s o l v e dt h ep r o b l e mo ft h ed y n a m i cd i s c o v e r ya n dc o m p o s i t i o no fr e s o u r c ea n ds e r v i c ei no p e nd i s t r i b u t e ds y s t e m c o m p a r e dw i t h t h ep a s tr e s e a r c hp r o j e c t ，t h ed i f f e r e n c ei sm a i n l yo nr e s o u r c ed i s c o v e r yd e s c r i b e db ys e m a n t i cm a r k u p ，a n dm u l t i s t r a t e g yr e s o u r c ec o m p o s i t i o nb a s e do nr e s o u r c eo v e r l a yn e t w o r k r e s o u r c ei st h ec o r ef o u n d a t i o no fo p e nd i s t r i b u t e ds y s t e m w ea b s t r a c t e da n ds e m a n t i c a l l yd e s c r i b e dr e s o u r c e ，e s t a b l i s h e dr e s o u r c er e l a t e do n t o l o g yb yu s i n go n t o l o g ym o d e l i n g t o o l s ，d i s c o v e r e da n dc o m p o s e dr e s o u r c et h r o u g hr e s o u r c eo v e r l a yn e t w o r k w ed e s i g n e d p a r t i a l - - o v e r l a yn e t w o r ka n dm u l t i s p a n n i n gt r e eo v e r l a yn e t w o r kf o rs e m a n t i cr e s o u r c ed i s - c o v e r y , o p t i m i z e dh e t e r o g e n e o u sr e s o u r c ed i s c o v e r ym o d e l w ee v a l u a t e ds e m a n t i cr e s o u r c e d i s c o v e r yp e r f o r m a n c eo fq u e r ya n du p d a t eo fr a d i u s ，r e c a l la n dp r e c i s i o ni nm e s ha n d p o w e r - l a wo v e r l a yn e t w o r k w ea l s op r o p o s e dr e s o u r c ep a t ha n dr e s o u r c eg r a p hf o rm u l t i 一 i i i s t r a t e g yr e s o u r c ec o m p o s i t i o np r o b e w ee v a l u a t e dm a n ya s p e c t so fr e s o u r c ec o m p o s i t i o ni n t w ot y p e so fd i f f e r e n t o v e r l a yn e t w o r k sw i t ht h r e ed i f f e r e n ta l g o r i t h m s ，s u c ha sc o m p o s i t i o n p r o b a b i l i t y , p e r f o r m a n c e ，o v e r h e a d ，p r o a c t i v ef a i l u r er e c o v e r y t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： 1 t h i sd i s s e r t a t i o np r o p o s e dd y n a m i cr e s o u r c ed i s c o v e r ya l g o r i t h ma n dm o d e lb a s e do n s e m a n t i cm a r k u p w ei d e n t i f i e dt h es e m a n t i cr e l a t i o n s h i po fr e s o u r c eb y a u t o m a t i c a l l y c l a s s i f i c a t i o na n dm e t a d a t ae x t r a c t i o n w e d e s i g n e dd i s c o v e r ya n ds e l e c t i n gr e s o u r c e a l g o r i t h m si no p e nd i s t r i b u t e ds y s t e m sb yr e s o u r c ei n d e xa n ds e m a n t i cr e l a t i o n s h i p w ea b s t r a c t e dt h er e s o u r c eu s in gs e m a n t i cm a r k u pa n do n t o l o g ya n d m o d e l e ds e v e r a l r e s o u r c eo n t o l o g yu s i n go n t o l o g ye d i t o rt o o l ，s u c ha sn o d e ，r e q u e s t ，p o l i c y ，l i n ka n d p r o c e s so n t o l o g ye t c t h i sd i s s e r t a t i o nd e s i g n e dar e s o u r c eo v e r l a ym o d e l 。t h er e s o u r c eo v e r l a yn e t w o r k a s s i s t si na u t o m a t e di n t e r c o n n e c t i o no fp r e v i o u s l yi s o l a t e dd i s t r i b u t e da p p l i c a t i o nr e s o u r c ec o m p o n e n t su s i n ga p p l i c a t i o n l e v e ln e t w o r k i n g t h ed i f f e r e n c ef r o mt h ec o n v e n t i o n a ld a t ao v e r l a yn e t w o r ki s ，e a c hn o d ei nt h es e r v i c eo v e r l a yn e t w o r kp r o v i d e s n o to n l ya p p l i c a t i o n l e v e ld a t ar o u t i n g ，b u ta l s oas e to fv a l u e a d d e da p p l i c a t i o ns e r - v i c e s t h u s ，t h ec o r eo p e n g r i dp r o v i d e sg l u ef o rd i s p e r s e ds e r v i c ec o m p o n e n t sa n d a l l o w st h e mt ob ed y n a m i c a l l yi n s e r t e di n t oo rr e m o v e df r o mt h eo v e r l a y b y k e e p i n g t r a c ko ft h es e m a n t i cr e l a t i o n s h i pa n dr e s o u r c es t a t e so fd i f f e r e n tr e s o u r c ec o m p o n e n t s a n do v e r l a yl i n k s ，o p e n g r i dc a np r o v i d em u l t i s t r a t e g yd y n a m i cr e s o u r c ec o m p o s i t i o n w i t hq o s ，l o a db a l a n c i n g ，a n df a s tf a i l u r er e c o v e r ys u p p o r t t h u s ，o p e n g r i dc a nd e 1 i v e rh i g h - 。q u a l i t yo n - d e m a n da p p l i c a t i o ns e r v i c e si nac o s t - e f f e c t i v ew a y b yp r o p e r l y c o m p o s i n gn e wr e s o u r c e sa n ds e r v i c e sf r o ma v a i l a b l er e s o u r c ec o m p o n e n t s t h i sd i s s e r t a t i o nb u i l taf u s i o np l a t f o r ma r c h i t e c t u r ef o ro p e nd i s t r i b u t e ds y s t e m s r e s o u r c eo v e r l a yn e t w o r ka st h ec o r e ，o p e n g r i dc a ns e m a n t i c a l l yd i s c o v e r sa n dc o m p o s e sr e s o u r c e w ed e s i g n e dr e s o u r c ep a r t i a l o v e r l a yn e t w o r ka n dm u l t i s p a n n i n gt r e e o v e r l a yn e t w o r k ，o p t i m i z e dt h er e s o u r c ed i s c o v e r ys c h e m eo fh e t e r o g e n e o u sr e s o u r c e w ee v a l u a t e ds e m a n t i cr e s o u r c ed i s c o v e r yp e r f o r m a n c eo fq u e r ya n d u p d a t eo fr a d i u s ， r e c a l la n d p r e c i s i o ni nm e s ha n dp o w e r - l a wo v e r l a yn e t w o r ka n dg o tb e t t e rr e s u l t 一i v 一 2 王 英文摘要 4 t h i sd i s s e r t a t i o np r o p o s e dp r o c e s s d r i v e nr e s o u r c ec o m p o s i t i o nm o d e la n ds c h e m e t h i sl e v e r a g et h er e s e a r c hr e s u l t so fb u s i n e s sw o r k f l o wa n ds c i e n t i f i cw o r k f l o w w ep r o - p o s e dr e s o u r c ep a t ha n d r e s o u r c eg r a p hf o rm u l t i - s t r a t e g yr e s o u r c ec o m p o s i t i o np r o b e w ee v a l u a t e dm a n ya s p e c t so fr e s o u r c ec o m p o s i t i o ni nt w ot y p e so fd i f f e r e n to v e r l a y n e t w o r k sw i t ht h r e ed i f f e r e n ta l g o r i t h m s ，s u c ha sc o m p o s i t i o np r o b a b i l i t y ，p e r f o r m a n c e ， o v e r h e a d ，p r o a c t i v ef a i l u r er e c o v e r y t h ee x p e r i m e n t a lr e s u l ti sp r o m i s i n g k e yw o r d s ： o p e nd i s t r i b u t e ds y s t e m ，g r i dc o m p u t i n g ，p e e r t o p e e rc o m p u t i n g ，r e s o u r c ed i s c o v e r y , s e m a n t i cm a t c h i n g ，r e s o u r c ec o m p o s i t i o n ，o p e nw o r k f l o w , o v e r l a yn e t w o r k s v 一 插图索引 l 割2 踅j j j 尼；覆，溢剐络及其路f ： | 过程q 意矧【1 3 0 j 9 图2 2 一种抽象的对等汁$ 嗍络体系乡淤匀1 9 2 1 1 2 鞠2 3 列等计算网络砉l i 织结翰分类1 7 9j 1 3 图2 4 楚于分依式哈希衷机制的结构化p 2 p 系统应用程序接口豕意嘲1 9 2 j 1 4 l 刳2 5p 2 p 系统路由表尺寸j 一彳州络f f 衽权衡渐进曲线 1 5 图2 6 网格系统参 学计辫一l j 作流分类【7 1 2 3 煳2 7 资源捌服务组件及组台税型【1 6 】 2 5 图2 8s p i d e r n e t 睡汽分崖体系绻构l1 6 1 2 6 斟3 1 传统分舸式讣锋明：境和，于 ：放分前i 系统概念比铰【l2 5 】 3 3 图4 1 月：放分布系统资源发现层次化模蹙 4 2 罔4 2 ( ) 小川( 7 ，j ，7 疑。引嘲络i 1 节点的路，挺技路由过程j 惫 4 3 图4 3r a n d o mp o i n t ，c rj u m p 馋钮一街后一1 j ，颤连接 4 6 图4 4n a m e d r o p p e , 镩法前后i 了点连接 4 6 圈4 5 偏覆盖网络! i 成辩翔：分够点 4 7 l 矧4 6 多j 扛成树覆j 盏嬲络巧：意 剞 5 2 罔4 7 奁渐环路示例 5 4 圈4 8 玲渤、f 户均组间澎i 数! j 憨跳数翰数关系( a ) 不组人小l b ) 小 j 嗍髓率 5 7 翻4 9r e s o t , r c eo n t o l o g y i ：! f | ；分类型和褐傩 5 9 翔4 10 伪，；l l ( ：r l i ，7o n t o l o g y l 夏务层次体系浆掏 6 0 浏4 il 务询二 j 径( a ) , f l i f 淘跨度 1 ) ) 一j 嘲络犬小函数多乏系 6 l 图4 12 ：玲准率与匹配 i l 率函数天系 6 2 | 判4 1 3 盟! 移i ，：弘径( a ) 毋j 更船i 跨j 立( hj 与p 络大_ 、眯f 数火系 6 3 斟4 1 4 史新b l j ：a , 数了资源密度，酒毁灭系 6 3 矧4 i5 蛮全率歹嘲络觇模笼系( a ) i * j i j c a ( j t 、( b ) 硌俅拇；扑，v j7 - = 2 z 州) 7 v 6 4 罔4 1 6 螽嘲半径与l 叫络舰梗炎系( a j 刚状拓讨 m ) 幂律拓扑、j ；：f l ，0 7 6 5 图4 1 7z 琶全率孑嘲络圭魁 捷：长系( a ) l 韧? 恢拓甜l 、( 1 ) ) h , i = t i w , i 4 - b ，二r ( 7 = = ( ) f ) ：；。v 6 5 一x i 上海交通大学博士学位论文 图二i + 1 务i f u ：t 二径与焖络规模天系( 刚嘲状拓扑( i ) ) 南舒挈拓扑，、：j 一( ) 1 般v 6 5 罔5 1 工作淹驱确的资源宝 台、f 台1 2 0 i 6 8 图5 2 种潮格环境自动工作流，成体系结构【1 7 1 7 0 图5 ，3 资游路径：资源组件线彤组合。， 7 1 翔5 4 资源阁：凌源乡l t f ：l ：1 ：线彤身l 合7 2 冈5 5 ：平i | 1 类穗资源连接组件 7 5 翔5 6 资源发现丘；连接模式 7 5 图5 7l ：件漉达f 建模tj 策略7 6 嘲5 8j ：作漉健馍肠i 语7 6 髑5 9j ：怍流建戏扩艇琢语7 7 图5 10 逝司、i i ：安仝秆j 上f 文敏感 ? 内节点翳换语义类型限制7 8 淄5 1 资源盈i 、f ；- 阁映射8 0 陶5 1 2 分支路径台井为完箭资溉“矧8 3 斟5 13 ，p 川( ? ，矗资源组f fi - ：动失效恢复 罔5 1 4 ，”( ? 7 ，ir 倒i 彤实现软件体系结构 8 7 9 0 煳5 15d r u g ) i , c o v e t y ( ；r i d ：实验： ： ：流尔例1 7 8 1 。，9 0 图5 1 6 ( ) ，j c ， ( ? _ r ? f 愤滁环境会i i f 建立t t g - f l q 浏5 1 7 ，) ? ，( 7 - r ir 绞溺i 组合算法隧能比较 9 1 。9 2 阁5 18f f l 合成功i 匕率( a ) 刚状拓扑( “器律托4 t 9 4 翻5 ，1 9 势0 翁玎销f a 疹状打对- ( b 1 幂律拓扑，。，。 9 4 劁5 ，2 0 组合t 动火效恢复成：叻l g 7 ： ：- f a ；l 蛩 j ；i j t ：# 4 i 扑f b ) ：铎 咎拓扑。 9 5 x i i 表格索引 炭2 1 网格i 辫：和对等汁算撰本麓别 7 表2 2p 2 p 计算系统综合比较 1 5 表2 3 翮格： 作流系统分类农 2 4 表4 1 几种朴索同然资源发现算法m - j 、乏l i 特1 f e 比较 4 5 丧5 1 不同i ：作流系统比较 6 8 x i i i 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名： 日期： 年一月一日 指导教师签名： 日期：一年一月一日 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 第一章绪论 1 1 研究背景与课题意义 在对等网络( p e e r t o p e e r ) 、网格( g r i d s ) 及服务计算( s e r v i c ec o m p u t i n g ) 等此类系 统中，许多分布在不同组织和位置的参与节点需要共享其他节点的资源或协作共 同提供服务，这些系统称为开放分布系统( o p e nd i s t r i b u t e ds y s t e m s ) ，它们都是建立 在i n t e r n e t 基础设施上，通过i n t e r n e t 把参与的节点连接起来，它们具有许多相似的特 性： 1 ) 自治性，参与的节点没有统一的管理组织，每个节点独立地管理自己的服务 和连接，节点之间没有明显的隶属关系，各个节点在整个系统中享有几乎相等的权 利和义务。2 ) 动态性，各个节点可以按需加入或退出系统，节点的动态加入和退出 不影响整个系统服务的提供。3 ) 位置分散性，这些节点分布在整个i n t e r n e t 的中心或 边缘位置，通过速度和质量保证不同的网络连接起来。4 ) 异构性，每个节点可能 具有不同的操作系统，处理能力，网络连接带宽，在线几率和服务质量等。5 ) 普 适性，随着普适计算时代的到来，网络和计算机在我们的工作和生活中无处不在， 我们每个人可能会拥有不同的计算机和网络系统连接，如：办公台式机，笔记本， 手机印d a 等，普适计算可以给我们提供自适应能力的服务及资源受限系统的服务聚 厶 口。 在这些系统中一个重要的问题就是如何快速准确发现这些服务，要使用和组合 这些服务，首先要能够动态地发现这些服务，如在简单的对等网络文件共享系统 中，我们如何根据元数据找到需要的文件，在网格系统中，我们如何根据任务需 求、资源和调度策略等来分配资源。另外一个重要的问题就是如何高效高质量组合 这些服务，传统的i n t e r n e t j 报务，如在线购物、信息检索服务都是由单一组织通过高 性能服务器或服务器集群集中提供，这就限制了其扩展性、灵活性和不同用户需求 的可定制性，通过资源组合把每个独立的资源组件组装成一个资源图为用户提供服 务。 当前基于分布式哈希表( d h t ) i 埘等网络系统主要提供基于逆序索引的多关键字 查询、“n g r a m s ”方法的模糊关键字查询、支持如同关系型数据库s q l 查询及简单 上海交通大学博士学位论文 语义支持的i r 模型复杂查询等资源发现服务，这些资源发现服务都是建立在资源静 态元数据基础之上，它们存在的共同问题是缺乏动态的资源和知识发现机制。对于 其资源组合来说，基本上都是单一的应用模式，资源聚集粒度比较细。 网格系统中资源发现和组合是网格应用的上层建筑，网格计算领域目前的研究 大都集中在如何设计和开发功能齐全完备的网格中间件上，这些网格中间件具有类 似的功能和体系结构，主要包括：任务管理，资源管理，数据管理，用户和安全 管理，网格工作流和网格应用开发框架等。网格系统中资源发现机制主要有g l o b u s m d s ，u d d i ，c o n d o rm a t c hm a k i n gs e r v i c e ，g l u e 和m a t c h m a k e r 等，主要基于静态资源 元数据和o n t o l o g y 模型。基于工作流模型的资源和服务组合已经成为网格系统资源 组合的研究热点，基于o n t o l o g y 和o w l s 过程模型及动态规划来进行资源组合也取 得了初步的成果。 本论文提出了基于语义标记和流程驱动的资源发现和组合框架，重点解决了开 放分布系统中资源动态发现和资源组合问题，与以前的系统相比不同之处主要在于 以语义标记描述资源发现，以资源覆盖网络为基础进行多策略的资源组合。 1 2 面临的主要研究问题 本节对开放分布系统研究的本质问题及其涉及到的关键技术简要加以分析，并 在下一节指出该领域当前主要存在的问题及相关的研究方向。 开放分布系统研究的本质问题 从理论上讲，要实现对等计算和网格计算的计算模式，必须至少完成四项工 作：资源分配( r e s o u r c e sa l l o c a t i o n ) 、资源发现( r e s o u r c e sd i s c o v e r y ) 、资源获 取( r e s o u r c e sr e t r i e v a l ) 和资源组合( r e s o u r c ec o m p o s i t i o n ) 。在对等计算和网格 计算系统中，并非每个节点的资源( 比如数据) 都放置在各自的位置上，很可能是 所有节点共同管理资源。比如在前面介绍的各种采用分布式哈希表放置数据的p 2 p 系统，所需数据往往放置在他人的机器上，于是如何进行合理的资源放置就成了必 须要回答的第一个问题。 当某用户需要获得数据或计算等资源时，他首先需要找到该资源，当然这与资 源放置方法是直接相关的。对于以分布式哈希表方式放置的数据，可以直接定位。 但在多数文件共享系统中，用户的文件都是放在各自的机器上，那么特定用户如何 一一 第一章绪论 知道哪些机器存有他需要的数据就成为一个关键问题，常常需要较大规模的搜索才 可以完成。资源发现就是研究如何更有效率地找到所需资源所处的位置，尤其是一 些在网络中稀有( r a r e ) 的数据和具有复杂需要的资源请求匹配。 当找到资源的位置后就需要获取资源，对于有些资源来说，这并不是很直接的 事，比如计算资源、大文件和流媒体资源。这里的问题主要在于如何才能更为高效 地获取资源，或者说如何使一些热点资源能够为更多的需要该资源的用户服务。通 常这需要尽量发挥对等计算系统中所有参与者的能力。例如，在b i t t o r r e n t 系统中， 如果大量用户同时下载一份数据，用传统的客户栅服务器模式，一个服务器不可能 同时支持非常多的用户，而使用对等计算模式，所有正在下载的用户一方面从共享 文件的源点进行下载，另一方面更多地从其他用户那里下载，这样充分地利用了所 有结点的带宽资源，使得并行下载能力得到了极大的拓展。 多个资源组合在一起形成一种新的资源为客户提供服务，以更好地重用软硬 件资产。它的特定表现形式如前面章节描述的网格计算。在面向服务的体系架构 ( s e r v i c e o r i e n t e da r c h i t e c t u r e ，s o a ) 中，资源组合更多地表现在服务编排和服务组 合方面。 如上所述，分布开放系统的研究从根本上是要解决资源分配、资源发现、资源 获取和资源组合四个问题。这四个问题是相互依赖、相辅相成的。 1 3 本文的研究内容及研究方法 具体地，本文的研究内容集中于开放分布系统资源发现和组合中的如下四个问 题： 开放分布系统资源模型和语义标记 开放分布系统资源有哪些特性，系统交互规则有哪些，o n t o l o g y 匹配如何应用 到资源发现和组合中，元数据如何索引和查询等问题。 资源覆盖网络 覆盖网络构建在物理网络之上，资源覆盖网络是一种特殊的p 2 p 覆盖网络，如 何设计资源覆盖网络用于资源发现和资源组合，偏覆盖网络和生成树覆盖网络 在o p e n g r i d 系统中作用和特性等问题。 o p e n g r i d 资源发现 一气一 上海交通大学博士学位论文 资源发现模型和算法，语义匹配o n t o l o g y 构建，偏覆盖网络和生成树覆盖网络 如何用来改进资源发现算法效率，分析和评估资源发现算法和模型的性能( 如 查全率和查准率等) 、开销( 如查询和更新开销) 、容错性和扩展性等问题。 o p e n g r 。i d 资源组合 资源组合是资源利用的高层次服务，如何利用工作流系统的研究成果来设计基 于流程驱动的资源组合方案，资源组合如何利用探测启发式算法，有哪些策略 可以进一步优化资源组合和提高资源组合的服务质量，分析和评估资源组合方 案的性能、开销、有效性、动态性、可管理性和质量保证等。 分析现有的开放分布系统中的资源模型的优缺点，构建一个在开放分布系统中 通用的资源模型，并对模型进行严格的定义和推理证明，分析在各种不同的开放分 布系统中模型的表现能力和整体覆盖度。分析和综合目前资源发现和选择算法和模 型的特点，找出其不足之处，提出更好的设计方案、评价标准和验证策略。分析和 综合目前资源覆盖网络及资源组合协议和模型的研究成果，结合考虑不同种类开放 分布系统特点，提出自己的方案。参照比较成熟的传统分布式系统设计思想，结合 国内外最新研究成果，不断进行改进和演化。 1 4 本文主要研究成果及贡献 分布式系统中的资源发现和组合是目前研究的热点问题之一，通常采用的是基 于语法和语义的元数据匹配算法和服务组合的方式，这些匹配算法大都集中于静态 资源选择，服务组合也没有考虑到服务所赖以依存的资源及其组合问题。本课题 针对目前的开放分布系统的特点和存在的问题，基于p 2 p 芹i l g r i d 两种计算模式融合 的思想，利用p 2 p 平台的可大规模扩展性、高度动态性等解决开放分布系统，特别 是g r i d 平台中的资源发现问题，通过语义标记更进一步扩大资源发现的应用价值； 利用g r i d 平台的高可靠性、可信任性等解决开放分布系统中的资源组合问题。 本论文提出了基于覆盖网络、语义标记和流程驱动的资源发现和组合框架 o p e n g r i d ，重点解决开放分布系统中资源快速准确发现和资源高效高质量组合问 题，与以前的系统相比不同之处主要在于以覆盖网络和语义标记描述资源发现，以 资源覆盖网络为基础进行多策略的资源组合。 开放分布系统中资源是基础，我们对资源进行了抽象和语义描述，利 一4 一 第一章绪论 用o n t o l o g y 建模工具构建了资源相关的n o d e ，r e q u e s t ，p o l i c y , l i n k 和p r o c e s s 等多 个o n t o l o g y ，在资源覆盖网络之上进行资源发现和资源组合，我们设计了偏覆 盖网络和多生成树覆盖网络用于语义资源发现，并对异