（计算机科学与技术专业论文）基于内容的快速数据分发技术研究.pdf

国防科技大学研究生院硕士学位论文 摘要 数据分发是分布式环境中资源汇聚和共享的一项关键技术，并且随着网络技 术的发展日益重要。基于内容的快速数据分发根据用户预先设定的兴趣和待分发 数据的特征信息，在尽可能短的时间内把一组中、小型数据从一个或者多个源节 点传送到对数据感兴趣的多个目标节点上。覆盖网机制能够有效的支持基于内容 的快速数据分发：目标节点对数据的需求在覆盖网上表达，源节点产生的数据通 过覆盖网与相应的数据需求匹配，进而被引导到感兴趣的目标节点集合。 拓扑结构的构建和维护、路由算法和匹配算法的设计是基于内容快速数据分 发的核心问题。现有的结构化拓扑虽然路由效率较高，但缺乏灵活性和可扩展性， 在动态嘲络环境下拓扑维护开销较高：非结构化拓扑灵活简单，然而路由开销较 高，不能满足快速分发的时效性要求。针对上述问题，本文从覆盖网拓扑构建、 维护方法，以及相应的路由算法和匹配算法等方面进行了深入研究。 针对动态网络环境中基于内容的快速数据分发的拓扑构建问题，提出了一种 基于内容的双层拓扑结构c b d l o 。c b d l o 是一个由上下两层拓扑构成的复合拓 扑结构，下层是一个非结构化的拓扑结构，上层是多个对应不同属性的分布式平衡 二又树d a v l 。在c b d l o 中，每个属性的值空间被分割成若干个相连但是互不相 交的子空间，每个子空间对应一个虚拟节点，然后根据其对应的值空间边界把虚 拟节点组织成一棵平衡二叉树。每个虚拟节点被映射到不同的网络节点上，使平 衡二叉树成为一个分布式的结构。在p e e r s i m 模拟器上以事件驱动的方式验证了 c b d l o 拓扑结构的性能。测试结果表明c b d l o 能够较好的适应网络的动态性， 具有较好的可扩展性。 为了降低下层非结构化拓扑上数据路由的消息开销，提出了一个基于内容的 带踪迹路由算法c r a w l 。c r a w l 以随机行走的方式在下层非结构化拓扑上转发 数据，同时为对应数据寻找相应的上层属性拓扑的入口。数据在转发过程中记录 了最近经过的路径踪迹信息，因此避免了随机转发过程中可能产生的环路。为了 避免踪迹可能导致的路径阻塞，设计了一种路径的恢复机制。模拟实验结果表明， c r a w l 算法通过降低消息开销有效地提高了数据分发的效率。 为了提高上层分布式平衡二叉树上精确数据匹配的效率，提出了一个基于属 性计数的分布式匹配算法c d m 。不同的属性对应不同的分布式平衡二叉树，因此， 同一个数据以并行的方式在不同的属性平衡二叉树上进行匹配，然后将匹配了的 数据直接发送到目标节点上。目标节点为每个数据维护一个计数器来记录收到该 数据的次数，当该数目达到订阅所含的属性数以后，确认接受该数据。p e e r s i m 上 的模拟实验结果表明，c d m 算法极大的降低了匹配的开销，适合对效率要求较高 第i 页 国防科技大学研究生院硕士学位论文 的快速数据分发应用。 主题词：快速数据分发，基于内容的数据分发，覆盖网，结构化拓扑， 非结构化拓扑，分发拓扑 第i i 页 国防科技大学研究牛院硕士学位论文 a bs t r a c t d a t ad i s s e m i n a t i o ni sak e yt e c h n o l o g yf o rr e s o u r c ea g g r e g a t i o na n ds h a r i n gi nt h e d i s t r i b u t e de n v i r o n m e n t c o n t e n t - b a s e df l a s hd a t ad i s s e m i n a t i o na i m st ot m n s m i t m e d i u m - a n ds m a l l - s i z e dd a t af r o mo n eo rm o r es o u r c er e d e st os e v e r a lt a r g e tr e d e si na s h o r tt i m e ，a c c o r d i n gt ot h ei n t e r e s t sa n dr e q u i r e m e n t so ft h et a r g e tn o d e s o v e r l a y m e c h a n i s mp r o v i d e sa ne f f i c i e n ti n f r a s t r u c t u r ef o rc o n t e n t b a s e dd i s s e m i n a t i o n ：t h e i n t e r e s t so ft h et a r g e tn o d e sa r ee x p r e s s e dt h r o u g ht h eo v e r l a yn e t w o r k s ；t h e nd a t a p r o d u c e db ys o u r c en o d e si s r m t c h e da n df i l t e r e db yt h eo v e r l a ya n df o r w a r d e dt ot h e c o r r e s p o n d i n gt a r g e tn o d e s t o p o l o g yc o n s t r u c t i o na n dm a i n t e m n e e ，r o u t i n ga l g o r i t h ma sw e l la sr m t c h i n g a l g o r i t h md e s i g na r ef u n d a m e n t a lp r o b l e m so fc o m e n t - b a s e df l a s hd a t ad i s s e m i n a t i o n e x i s t e ds t r u c t u r e do v e r l a yt o p 0 1 0 9 i e s ，t h o u g hh a v i n ge f f i c i e n tr o u t i n gr u l e s ，e x h i b i t w e a ks c a h b i l i t ya n df l e x i b i l i t y ；o nt h eo t h e r1 1 a n d ，u n s t r u c t u r e do v e r l a yt o p o l o g i e s ， o w n i n gs i m p l ea n df l e x i b l et o p o l o g yc o m t r u c t i o np r o c e s s ，h o w e v e r , c a n _ n o tm e e tt h e t i m e l i n e s sr e q u i r e m e m so ff l a s hd a t ad i s s e m i n a t i o n a c c o r d i n gt ot h ea b o v el i m i t so f e x i s t i n gm e t h o d s ，t h r e ec o h e r e n ts u b - p r o b l e m so ft h e c o n t e n t - b a s e df l a s hd a t a d i s s e m i n a t i o na r ed e e p l ys t u d i e d ：s c a l a b l et o p o b g yc o n s t r u c t i o na n dm a i n t e n a n c e m e t h o d s ，l o o p - f l e em e s s a g er o u t i n ga l g o r i t h m s ，a sw e l la st h ed a t aa t t r i b u t em a t c h i n g m e t h o d s f i r s t l y ，c o n s i d e r i n gt h ee f f i c i e n tt o p o l o g yc o m t r u c t i o np r o b l e mo fc o n t e n t - b a s e d f l a s hd a t ad i s s e m i n a t i o ni nad y n a m i ce n v i r o n m e n t ，ac o n t e n t - b a s e dd o u b l el a y e r e d o v e r l a y ( c b d l o ) i sp r o p o s e d c b d l oi sac o m p o u n dt o p o l o g yc o m p o s e do fal o w e r u n s t r u c t u r e dt o p o l o g ya n dm a n yu p p e ra t t r i b u t e t o p o l o g i e s ，e a c ho fw h i c hi s a d i s t r i b u t e db a l a n c e db i n a r yt r e e ( d a v e ) t h a ti sm a d eu po fv i r t u a ln o d e s i nt h e c b d l ot o p o l o g y ，e a c hv a l u es p a c eo ft h es u b s c r i p t i o na t t r i b u t ei sd i v i d e di n t om a n y j o i n e db u tn o ti n t e r s e c t e ds u b s p a c e s ，a n de a c hs u b s p a c ei sd e s i g n a t e dt oav i r t u a ln o d e ， w h i c hi sm a p p e di n t oar e a ln o d eo ft h en e t w o r k t h ev i r t u a ln o d e sf i n a l l yc o n s i s to f a d i s t r i b u t e da v lt r e e d e t a i l e ds i m u l a t i o n sa r ec a r r i e do u to nt h ep e e r s i ms i m u l a t o r b a s e do nt h ee v e n td r i v e nm o d e ts i m u l a t i o nr e s u l t ss h o wt h a tc b d l oc a nw e l la d a p t t ot h ed y n a m i c so f t h en e t w o r k ，a n dc a ns c a l eg r a c e f u l l ya si n c r e a s i n go ft h es i z eo f t h e n e t w o r k s e c o n d l y ，t or e d u c et h em u t i n gm e s s a g ec o s to nt h el o w e ru n s t r u c t u r e dt o p o l o g y ，a n e wc o n t e n t b a s e d r o u t i n ga l g o r i t h mw i t hh b e l e dt r a c e ( c r a w l ) i sp r o p o s e d c r a w li sd e s i g n e dt ot r a n s m i td a t ai nar a n d o mw a ( r m n n e r , s oa st ol o c a t et h e m a t c h e du p p e ra t t r i b u t e t o p o l o g y d u r i n gt h er a n d o mw a l kp r o c e s s ，t h er e c e n t l y t r a v e l e dn o d ei sa d d e dt ot h er o u t i n gm e s s a g ea sat r a c es oa st oa v o i dt h e r o u t i n gl o o p s m e a n w h i l e ，ap a t hr e s t o r i n gm e c h a n i s mi sa l s op r o p o s e dt oa v o i dt h er o u t i n gd e a d l o c k p o s e db yt r a c e s i m u l a t i o n si n d i c a t et h a tc r a w la l g o r i t h ms i g n i f i c a n t l yr e d u c e st h e 第i i i 页 国防科技大学研究牛院硕士学位论文 c o s to f t h el i l e s s a g ea n dt h u si m p r o v e st h ep e r f o r m a n c eo f d i s s e m i n a t i o r l t h i r d l y , i no r d e rt oi n c r e a s et h ee f f i c i e n c yo fa c c u r a t em a t c h i n gp r o c e s si nt h e d i s t r i b u t e da v l ，ac o u n t e r b a s e dd i s t r i b u t e dr m t c h i n ga l g o r i t h mc d mi sp r o p o s e d e a c ha t t r i b u t ei nt h ed a t ac o r r e s p o 耐st oad i s t i n c td i s t r i b u t e da v lt r e e ：t h es a m ed a t a i sl m t c h e di nd i f f e r e n td i s t r i b u t e da v lt r e e si np a r a l l e lf i n a l l y 。t h ed a t a w i l lb e f o r w a r d e dt oa l lt h em a t e h e dt a r g e tn o d e s e a c ht a r g e tm a i n t a i n sac o u n t e rf o re a c hd a t a t oc o n f i r mt h a tt h ed a t am a r c h e sa l lr e q u i r e m e n t so fi t ss u b s c r i p t i o n sa t t r i b u t e s s i m u l a t i o n ss h o wt h a tc d ma l g o r i t h mg r e a t l yr e d u c e st h em a t c h i n gc o s t , a n di sa n e x c e l l e n tc a n d i d a t ef o rf l a s hd a t ad i s s e m i n a t i 0 1 3 k e yw o r d s ：f l a s hd a t ad i s s e m in a t i o n ，c o n t e n t - b a s e dd a t ad i s s e m i n a t i o n ， o v e r l a y ，s t r u c t u r e dt o p o l o g y ，u n s t r u c t u r e dt o p o l o g y ，d i s s e m i n a t i o nt o p o l o g y 第i v 页 国防科技大学研究生院硕士学位论文 第1 v 页 国防科技大学研究生院硕士学位论文 图目录 图1 1基于覆盖网的数据分发示意图1 图2 1 n a p s t e r 的拓扑结构7 图2 2g n u t e l l a 的拓扑结构8 图2 3k a z a a 的拓扑结构9 图2 4c h o r d 的拓扑结构1 1 图2 5c a n 的拓扑结构1 1 图2 6c y c l o i d 的拓扑结构1 2 图2 7v i c e r o y 的拓扑结构1 2 图2 8发布订阅系统1 4 图3 1c b d l o 的双层网络拓扑结构。2 2 图3 2非结构化拓扑中新节点的加入过程。2 4 图3 3随机选择节点的过程2 4 图3 4 节点正常离开的处理过程。2 5 图3 5节点收到正常开的消息后的的处理过程2 6 图3 6节点失效的处理过程2 6 图3 7 节点收到失效消息后的处理过程。2 7 图3 8虚拟节点对应的数据结构2 8 图3 9订阅产生后的处理过程。3 0 图3 1 0 属性拓扑的产生过程3 1 图3 1 1 新的订阅属性加入时引起属性空间重新划分的四种情况。3 1 图3 1 2 新属性空间的加入过程3 2 图3 1 3 虚拟节点的映射过程。3 3 图3 1 4 属性空间的删除过程。3 4 图3 1 5a p t 的更新算法3 5 图3 1 6 分割拓扑的合并算法3 6 图3 1 7 模拟c b d l o 的体系结构3 7 图3 1 8 属性拓扑的检测效果3 9 图3 1 9a p t 大小与命中率的关系测试4 0 图4 1节点的数据结构示意图。4 3 图4 2 待分发数据的结构示意图4 4 图4 3属性拓扑间的路由算法4 4 图4 4 路径阻塞情况示意图4 5 第v 页 国防科技大学研究生院硕士学何论文 图4 5 属性拓扑内的路由算法4 6 图4 6数据在平衡二叉树上的分发算法4 7 图4 7节点的订阅信息结构4 8 图4 8数据在最终节点上的过滤过程4 8 图4 9有效分发的开销随订阅总数的变化5 0 图4 1 0 有效分发的消息开销随最人跳步数的变化。5 1 图4 1 1c b d l o 与t e r a 分发的消息开销比较5 1 图4 1 2o r = o 7 ，i j , ：o 8 时的z i p f 分布5 3 图4 1 3 匹配开销与订阅数目之间的关系5 4 图4 1 4 匹配开销与属性总数之间的关系。5 4 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文作者签名：二2 峰日期：冲年，月脚 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：二筮童耻 作者指导教师签名：兰耋：垩 日期：砷年 ，月，z 日 日期：凇7 年，月彦日 国防科技大学研究生院硕士学位论文 第一章绪论 随着网络技术的迅速发展，越来越多的资源连接到了i n t e r n e t ，从而使得 i n t e r n e t 成为最受瞩目的计算平台。为了满足信息交流、资源共享的需求，各种以 数据为中心的应用不断产生。数据分发实现将静态存放或动态产生的数据从数据 源节点传送到网络中对数据感兴趣的目标节点，是数据汇聚和共享的关键技术。 为了实现数据在动态网络环境下准确快速的分发，数据分发技术需要协调数 据源节点与数据需求节点之间的关系与动作。覆盖网是在物理网络之上构建的连 接网络上所有节点的逻辑拓扑结构，基于覆盖网的数据分发应用利用覆盖网上高 效的数据分发路由策略引导数据，把数据从数据源节点发送到目标节点上，如图 1 1 所示。不同的应用需求决定了拓扑构建维护的方法及其相关的分发路由策略。 图1 1 基于覆盖网的数据分发示意图 1 1 快速数据分发 随着网络技术的发展，各种基于对等网络的数据分发技术的应用迅速流行， 如b i t t o r r e n t 1 ，2 1 e m u l e 3 1 等，它们为数据的共享和汇聚提供了良好的平台。数据分 发是指将一组数据从一个或者多个数据源节点发送到多个目标节点的过程，其关 键在于数据需要由源节点出发经由动态异构的网络环境传送到地理上分散的目标 节点集合。在基于覆盖网的数据分发过程中涉及到四类实体：数据、源节点、覆 盖网、目标节点。数据由源节点提供，这些数据可能是持久保存的也可能是动态 产生的；源节点可以是一个或多个，多个源节点在地理上可以是分布的；覆盖网 负责接收并路由转发数据至所有的目标节点，覆盖网依据特定的规则构建，负责 完成数据的路由转发；目标节点的目的是获取源节点的全部或部分数据。数据分 第1 页 国防科技大学研究生院硕士学位论文 发的服务质量要求包括：及时性、准确性、可扩展性、健壮性、自适应性、可靠 性、安全性等。 在复杂动态的战场环境中，数据分发系统可以通过将情报信息及时准确地发 送到战场指挥人员以支持即时决策。美军提出的网络中心战1 4 坦口通过网络将传感器、 指挥员、战斗员有效地组织起来，从而将传感器采集的实时情报信息迅速传送至 指挥员及战斗员以形成共享的战场环境感知，最终提高整个作战系统的决策速度 和行动速度。为实践网络中心战理念，美军提出了联合战役信息空间计划j b i ( j o i n t b a t t l ei n f o s p h e r e ) 1 5 】来提供全球互操作的“信息空间 以汇聚、整合、并智能地分 发定制的战场信息。j b i 为个体用户提供满足其功能需求的信息，它把来自不同源 节点的数据进行汇聚、整合，同时按照合适的形式和粒度等级分发数据。战场环 境数据分发应用强调分发的及时性、准确性，即数据应该在尽可能短的时间内从 源节点准确地传送到需要该数据的目标节点上。 与战场环境下的数据分发应用相类似，紧急情况处理系统也对数据分发的即 时性与准确性提出了要求。紧急情况处理系统主要用来监测各种突发情况并帮助 相应管理部门作出及时的反应，这些突发情况包括诸如地震、海啸、火灾、恐怖 袭击等等。典型的系统有美国国立地震系统提供的地震信息共享服务s h a k e c a s t 6 1 。 s h a k e c a s t 首先通过传感器网络实时地收集地震数据，然后将这些数据进行处理生 成g i s 格式的震动效果地图以评价城市中哪些结构最易受影响，这些地图信息被 发送到各类订阅者( 如各级突发事件管理组织) 以支持对地震的影响进行即时评估、 相互协调以及资源分配等决策过程。s h a k e c a s t 中订阅者需要预先注册以接收信息； 订阅者所用的机器可能利用不同的网络( 如无线网络，以太网，a d s l ，微波等) 进 行互连。在动态异构的网络环境下，快速、准确的数据分发成为帮助及时决策处 理问题的关键因素。 上述两类数据分发系统被称为是快速数据分发系统( f l a s hd a t a d i s s e m i n a t i o n ) t 6 1 ，相对于传统的数据分发系统，它更强调数据分发的及时性和准确 性，以及对网络的动态适应性。其基本特点包括： 不可预料性： 数据分发事件是预先不可预料的，同时底层的网络基础设施也为不可预料的， 某些链路可能不可用； 动态性： 随着时间的推进，节点随时可能加入或者退出，这也称为网络波动( c h u r n ) ； 可扩展性： 网络的规模可能从几十到数千甚至更高，相应的接收节点的兴趣以及源节点 的数据等的规模也有可能很大； 第2 页 国防科技大学研冗生院硕士学位论文 数据异构性： 分发的数据类型多种多样，比如有图像、小的声音和视频片断、g i s 文件等， 大小范围从几百k b 到数十m b ； 网络异构性： 节点的地理位置分散，且处理能力和连接带宽存在差异。 传统的数据分发主要关注将已有的数据分发给所有的目标节点。其分发过程 往往由目标节点通过查询请求动作来启动，源节点只是被动地响应接收节点的请 求。这种被动而又紧耦合的分发模式很难适应前述的战场环境和紧急事件处理环 境。 快速数据分发主要研究在动态异构的网络环境中把动态产生的各种较小或者 中等大小的数据快速准确地传送到对数据感兴趣的节点上。而且要求能够满足上 述的几个基本特点。不可预料性，要求数据源节点结合主动“推送”和被动响应 两种模式，将动态产生的数据及时准确的发送到目标节点；动态性要求分发系统 有较高的鲁棒性和健壮性；可扩展性则要求分发系统的拓扑组织与数据路由应相 对简单且易于扩展；中小型的数据意味着传输过程中需要同时考虑延迟与带宽的 影响；网络异构性则要求分发系统能够根据不同节点的能力分配相应的任务。 快速数据分发传送的都是中小型的数据( 几百k b 到数十m b ) ，而且对分发的准 确性和实效性有更高的要求。因此仅仅依靠源节点被动响应的模式无法满足快速 数据分发系统中源节点动态产生的数据的分发需求，需要在数据产生以后由源节 点主动将其“推送到目标节点。这就需要数据在路由的过程中发现目标节点对 数据的需求，基于内容的分发为快速数据分发提供了很好的技术途径。发现目标 节点对数据的兴趣，选择“推送的目标节点并确定“推送的路由成为快速数 据分发需要解决的关键问题。 为数据源节点快速、准确地选择目标节点，需要构建一个高效的覆盖网拓扑 结构；高效的推送数据到目标节点，需要设计一个有效的路由策略，为分发选择 尽可能短的分发路径。 1 2 覆盖网拓扑结构 覆盖网是构建在一个或者多个网络之上的逻辑网络拓扑，它通过虚拟链路或 者逻辑链路把网络节点连接起来，为应用提供与底层网络透明的网络访问接口。 对覆盖网的研究一直是p 2 p 领域的一个热点问题。按照节点之间的耦合度， 现有的覆盖网拓扑结构可以分成结构化和非结构化两种。结构化拓扑通常以一种 严格的规则确定节点之间的邻居关系和数据的放置位置，因此路由的效率较高， 开销较小，但是维护开销较大，对网络的动态性支持不够；非结构化拓扑以一种 第3 页 国防科技大学研究生院硕士学位论文 松散的、随意的方式组织节点，因此构建简单，易于扩展，而且具有很好的鲁棒 性，但是路由的效率较低，开销较大。因此，融合结构化和非结构化的优点是值 得探索的方向。如层次式的基于超节点的网络拓扑1 7 一。 具体的拓扑结构往往和应用背景紧密相关，面向数据分发的拓扑不但要求拓 扑能够很好的保持网络的连通性，支持网络的扩展性和动态性，而且要能够有机 的组织数据的源节点和目标节点，为快速高效、低开效的分发路由提供良好的支 持。上述的结构化和非结构化拓扑结构都无法满足快速数据分发的效率、动态性 以及可扩展性方面的要求。 在数据分发应用中，不同内容的数据往往拥有不同的目标节点群，基于内容 的数据分发在转发数据时能够根据内容的信息动态的选择不同的路径，可以依靠 数据的内容信息将数据引导到对数据感兴趣的节点上。发布订阅模式的数据分发 在数据产生以前将节点对数据的请求以订阅的形式向系统散布，当数据产生以后 根据节点的数据请求将数据发送到目标节点上。在基于内容的发布订阅模式中， 订阅者的兴趣被组织成一种基于内容的拓扑结构，分发时依据数据的内容信息在 拓扑上传送，为动态网络的快速数据分发提供了一个良好的选择。 1 3 分发路由策略 路由策略是决定分发效率的最主要因素，基于覆盖网的数据分发的路由策略 和具体的拓扑结构有着紧密的联系。数据从源节点出发依据一定的路由策略在一 个节点选择适当的节点转发数据，直到到达目标节点。在非结构化的拓扑中，随 机组织的邻居关系无法反映节点之间的物理关系，比如地理位置，应用需求等， 因此路由过程通常采用洪泛或者组播的方式；在结构化拓扑中，数据的放置遵循 严格的规则，因此可以依照规则快速地路由到目标节点。 在基于内容的路由策略中，需要不断的比较匹配数据的内容，因此要求匹配 算法要尽量简单，而且最好能把匹配的过程分布到网络的不同节点上，以平衡节 点的负载。现有的匹配过滤算法大多把匹配的过程集中到一个或者若干个代理节 点上，使得匹配的过程成了分发的瓶颈。 基于内容的快速数据分发要求路由策略能够满足数据的动态产生和实时分发， 因此数据源节点在产生数据以后，要根据数据的内容信息快速地传送数据到相应 的目标节点，路由的过程要产生较小的冗余消息，带给网络较小的负载压力。 1 4 主要研究内容 快速数据分发技术足大规模分布式系统构建的基础性关键技术，对于各种以 第4 页 国防科技大学研究生院硕士学位论文 数据为中心的应月意义重人。然而，厂“域网络的动态性与异构性、数捌集的多样 性与动态型，以及客户请求的多样性，都给构建高效鲁棒的快速数据分发系统带 来了很大的挑战。本文采用基于内容的发布订阅模式，针对动态网络环境下的快 速数据分技术进行了深入研究。主要的研究工作包括两个方面的内容： 基于内容的覆盖网构建和维护技术 传统的结构化拓扑能够快速的定位数据，但是系统的可扩展性不足，不能适 应动态的大规模网络，特别是无法满足数据分发应用中源节点主动推送的需求； 而非结构化拓扑的冗余消息较多，给网络带来了很大压力，无法适应快速数据分 发应用及时准确的要求。 针对动态网络环境中基于内容的快速数据分发的拓扑构建问题，提出了一种 基于内容的双层拓扑结构c b d l o ( c o n t e n t b a s e dd o u b l el a y e r e do v e r l a y ) 。c b d l o 的下层是一个连接所有节点的非结构化的拓扑结构；上层是为每个属性建立的属 性拓扑棵分布式平衡二叉树d a v l ( d i s t r i b u t e da v l ) 。下层的非结构化拓扑 维护网络的连通，并支持网络的动态性，上层的属性拓扑把属于同一个属性的节 点组织到一起，以支持高效的数据分发。 基于内容的数据路由技术和基于计数的属性匹配技术 非结构化拓扑往往采用随机行走的路由方式转发数据，需要解决的问题主要 是消息的开销。为了降低下层非结构化拓扑上数据路由的消息开销，提出了一个 基于内容的带踪迹路由算法( c o n t e n t b a s e dr o u t i n ga l g o r i t h mw i t hl a b e l e dt r a c e ， 简称c r a w l ) 。c r a w l 算法以随机行走的方式在下层的非结构化拓扑上转发数 据并寻找属性拓扑，并且在转发的过程中记录了最近的路径踪迹，从而有效的避 免了数据回路，降低了冗余消息。并通过一种恢复机制来消除因为踪迹而产生的 “路径阻塞”问题。 匹配算法是基于内容的分发系统的研究热点。现有的匹配算法大多把匹配的 过程集中到一个或者有限的几个节点上，不但增加了这些节点的负载，而且也使 得匹配过程成了整个系统效率的瓶颈。为了提高上层分布式平衡二叉树上精确数 据匹配的效率，提出了一个基于计数的分布式匹配算法( c d m ) 。c d m 算法把不同 的属性匹配分布到不同的属性树上，让同一属性的拥有不同属性值的数据的属性 匹配分布到d a v l 的不同虚拟节点，使得属性的匹配过程并行的分布在网络的不 同节点上同时执行。成功匹配的数据被虚拟节点转发到所有可能对该数据感兴趣 的订阅节点上，节点收到数据以后对匹配的属性计数，匹配数达到订阅的属性总 数的数据最后被节点接受。 1 5 论文组织结构 第5 页 国防科技大学研究牛院硕士学位论文 本文共分为五章，各章节组织结构如下： 第一章介绍了快速数据分发的定义、要求和应用背景；介绍了快速数据分发 可以采用的主要技术途径，以及相关的覆盖网拓扑构建和分发路由策略设计需要 研究的主要问题；简述了本文研究的问题以及取得的研究进展； 第二章综述与本文工作相关的研究，根据数据分发系统的层次结构，分别评 析了各种已有的网络拓扑构建维护技术，分发拓扑构建技术，发布订阅技术以及 数据分发中的路由技术； 第三章针对动态网络环境中基于内容的快速数据分发的拓扑构建问题，提出 了一种基于内容的双层拓扑结构c b d l o ，并研究了其构建与维护方法，为基于 内容的数据分发提供拓扑基础，并通过理论分析和p e e r s i m 实验模拟的形式验证了 该拓扑的有效性； 第四章为了降低下层非结构化拓扑上数据路由的消息开销，提出了一个基于 内容的带踪迹路由算法c r a w l ；为了降低下层非结构化拓扑上数据路由的消息开 销，提出了一个基于计数的分布式匹配算法c d m ，并在p e e r s i m 模拟器上模拟验 证了两个算法的有效性； 第五章总结了本文的工作和创新，并指出下一步工作的研究方向。 第6 页 国防科技大学研究生院硕士学位论文 第二章相关研究 根据第一章的介绍，快速数据分发主要涉及的技术有覆盖网的构建和维护， 分发拓扑的构建与维护，以及路由算法的设计，基于内容的数据分发还需要关注 匹配算法的设计。 发布订阅模式的数据分发在拓扑结构上大致可以分为两层：覆盖网层和分发 拓扑层。覆盖网层负责维护系统中所有节点的邻居关系，保证网络的连通性，与 特定内容数据的分发无关；分发拓扑层则是特定内容数据的源节点及需求节点组 成的拓扑，一般基于覆盖网构建，用于特定数据的分发。数据分发时，数据在基 于覆盖网层的分发拓扑层上执行路由转发。 本章依据针对快速数据分发相关的技术展开讨论，介绍数据分发领域已有的 研究工作。 2 1 覆盖网拓扑的构建与维护技术 覆盖网拓扑结构的构建和维护是p 2 p 领域的一个重要研究热点。通常根据分 散度和耦合度对覆盖网进行分类【9 。1 1 】。分散度是指拓扑结构对中央服务器的依赖程 度，而耦合度是用来衡量拓扑构建过程和节点的邻居关系是受某种机制的严格控 制还是动态的、非确定性的。 2 1 1 依据分散度分类的拓扑 根据分散度，覆盖网拓扑可以分为集中式、全分布式、混合式三大类。 2 1 1 1 集中式拓扑 图2 i n a p s t e r 的拓扑结构 第7 页 国防科技大学研究生院硕士学位论文 如图2 1 所示，在集中式拓扑中，存在着一个( 或少数儿个) 中央服务器，作为 目录服务器来协调其它各个节点之间的交互，但节点之间的交互与资源共享等行 为仍是直接以p 2 p 模式进行的。典型系统如n a p s t e r 1 2 1 和b i t t o r r e n t i 】等。 由于在集中式拓扑结构中存在着集中的中央服务器，所以系统的性能严重受 限于中央服务器。这种结构导致集中的中央服务器成了系统的瓶颈和并且引发了 单点失效等问题，因此系统的健壮性较差。 2 1 1 2 全分布式拓扑 在全分布式拓扑中，所有节点都是完全平等的，每个节点既是服务器也是客 户端，系统中没有任何目录服务器。典型系统如g n u t e l l a l l3 1 、f r e e n e t 1 4 j , oc h o r d 1 5 】 等，拓扑结构如图2 2 所示。 图2 2g n u t e l l a 的拓扑结构 因为全分布式拓扑不依赖集中服务器，因此具有较强的可扩展性和鲁棒性， 但是因为不具有固定的结构，消息的转发往往是随机的，因此也增大了系统的冗 余消息，要在这种结构上实现高效的数据分发，所需要的数据路由算法就需要额 外的分发拓扑支持，算法也相对比较复杂。 2 1 1 3 混合式拓扑 在混合式拓扑中，存在一些“超级节点”( s u p e r p e e r ) 。超级节点具有比普通节 点更强的能力和更高的地位，通常充当目录服务器的角色。但这些超级节点通常 可以动态选择和自组织，因此降低了系统失效的可能性，增加了系统的鲁棒性。 典型系统如k a z a a 1 6 f f l b r o c a d e 1 7 1 等，拓扑结构如图2 3 所示。 第8 页 国防科技大学研究生院硕士学位论文 图2 3k a z a a 的拓扑结构 混合式拓扑通常根据节点能力的差异性，把节点分为强节点和弱节点，强节 点之间互连组织成上层结构，并为弱节点提供服务以承担更多的任务，而弱节点 通常与某个特定强节点连接以获取服务。这样的层次结构避免了弱节点的性能对 系统产生影响，从而提高了数据分发的效率。 2 1 2 依据耦合度分类的拓扑 根据耦合度，覆盖网拓扑又可以分为非结构化与结构化两大类。 2 1 2 1 非结构化拓扑 在非结构化拓扑中，节点间的逻辑拓扑关系通常较为松散，具有较大的随意 性。“非结构化指覆盖网没有固定、严格的拓扑结构，是一张随机生成、松散 组织的普通图或随机图，但是理论上随机图可以是任何形状的。类似于今天的 i n t e r n e t ，现有的各种非结构化网络拓扑，虽然其拓扑结构都不严格遵循某种形状， 但总是符合一定的规律一一通常是小世界模型或者幂律模型，本质上这种规律是 由i n t e r n e t 用户自发形成的。除此以外，后来的非结构网络拓扑都发展成了基于超 节点的两层拓扑结构，而超节点之间的连接方式往往也是符合小世界模型或幂律 模型的。 曲小世界模型 在计算机网络中，小世界模型( s m a l l - w o r k im o d e l ) 【1 8 】是指任意两个网络节点间 的距离( 即路由跳数) 一般很短，并且对每个节点而言，其邻居节点彼此相识( 即互 第9 页 圜防科技大学研冗生阮硕士学位论文 相连接) 的概率很高，所以节点簇集现象明显。g n u t e l l a 协议【1 3 】所支持的p 2 p 网络 大多可以用小世界模型来刻画其覆盖网拓扑结构，而对f r e e n e t 【1 4 l 的测试结果也说 明它是符合小世界模型的。 b ) 幂律模型 幂律模型( p o w e r - l a wm o d e l ) 1 9 】也被成为z 币f 定律，它是指网络中拥有的连 接数为l 的节点占网络节点总数的比例正比于l - 。，a 是一个取决于网络本身的常 数因子；因此网络中大多数节点连接数很少，少数节点连接数很多。g n u t e l l a 1 3 j 和f r e e n e t 】等一系列非结构化网络虽然不符合严格的幂律模型，但都可以看成是 它与其它模型的合成体，总体上都具有幂律模型的特点，如面对随机节点失效的 高容错性等。 非结构化拓扑的构建和维护相对简单，易于扩展并具有较强的鲁棒性。但由 于其拓扑结构组织较为松散，节点及数据定位较为困难，通常都是采用泛洪搜索、 随机搜索和选择性转发等方法，其效率和准确率难以保证，且冗余消息较高，网 络的开销也较大。 2 1 2 2 结构化拓扑 在结构化拓扑网络中，节点间的邻居关系通常由确定性的算法严格控制，资 源，或资源的元信息) 的放置也是由确定性的算法精确发布到特定的节点上。结构 化拓扑通常采用分布式哈希表技术( d i s t r i b u t e dh a s ht a b