（计算机应用技术专业论文）p2p流媒体点播的cache技术及节点选择研究.pdf

，f 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 。尽我所知，除了文巾特别加以标注和致谓 的地方外，论文中不包含其他人已经发 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 示了谢意。 研究生签名：塑：图9 日期：趔尘f 髟 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电予文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 畛 、 研究生签名：盟导师签名：锉日盛。、3 j 彳 于f i f o 和l r u ，在启动延迟、根节点依赖度方面与l s b 相仿，而在副本数量上则优于l s b 。 3 在点播用户之间共享缓存后，系统中存在了人量服务节点，客户节点需要从这些服务节点 中选择更加适合自己的节点。同时，客，_ 节点也有可能为新节点提供服务，因此节点在流媒体内容 分发树中位置非常重要。针对p 2 p 节点性能与合作意愿差异，兼顾节点自身利益和系统整体性能， 本文提出了基于节点性能和贡献的树结构调整算法。存客户节点选择服务节点并发出请求后，由服 务节点根据新、老节点在性能和贡献上的差异决定是否接受该请求以及调整原有节点在转发树上位 置。在实验中，通过与基于时延的选择算法对比发现，我们的调整算法可以提升节点的贡献度，降 低内容分发树结构的深度、新节点加入系统所需要的平均跳数以及信号中断的次数。 4 与其他应用类似，点播服务的用户在兴趣、爱好方面也存在相似特性，如果在构建网络时 能够利用这一特性，将有助于应用的开展。于是，本文引入分群概念，将兴趣相近的节点分在同一 个群，每个群由一个群首维护，所有的群首构成卜层恤吗络，而群内的其他普通节点则构成下层网络。 这样，随着群数量的增加，普通节点所需维护的路由表长度将显著缩短，而群内节点的加入和退出 行为也将不会影响其他群的成员。尤其是，对群内流媒体对象的请求只需在群内就可以得到响应， 请求所经历的转发次数得到降低。并且，即使跨越多个群的请求，其所需的平均路径长度也没有明 显的增加。 最后，本文详细阐述了一个基于c c m 的流媒体点播系统的设计，包括应用背景、系统架构、 模块设计、对等层之间的消息、主要数据列表的结构等内容。通过一个实际的p 2 p 平台，比较了使 用c a c h e 技术前后的差异。采用c a c h e 技术后，超节点的网络带宽开销降至之前的2 5 3 0 ，c p u 占用率峰值也只有2 0 左右，能够正常运行。即使并发连接5 0 0 个叶节点。其带宽开销也不到l m b p s 。 关键词：p 2 p 网络：流媒体；点播；缓存；共享；置换算法；节点选择 a b s t r a c t w i t hb r e a k t h r o u g h si nn e t w o r kb a n d w i d t h ，c o d ea n dd e c o d et e c h n o l o g i e so f m u l t i m e d i aa n dp e r s o n a l c o m p u t e r sp e r f o t l l l a n c e ，s u c hk i n do fa p p l i c a t i o n sa n ds e l v i c e sb a s e do np 2 p ( p e e 卜t o p e e r ) t e c h n o l o g i e s h a sb e e na ni n d i s p e n s a b i ep 踟1o fi n t e r n e t i nr e c e n ty e a r s ，m e d i as t r e a m i n gb a s e do np 2 ph a ss u r p a s s e d m a n yo t h e ra p p i i c a t i o n ss ot h a ti to c c u p i e sam a i o r i t yo fi n t e m e t ”a f n c e s p e c i a l l y ，v b d ( v i d e oo nd e m a n d ) s e r v i c eh a sa t t r a c k e dm o r ea t t e n t i o nf r o mt h ep u b j i c u n f o n u n a t e ly m 0 s to fs t r e a m j n gv b ds e r v j c e sb a s e d o np 2 pc a nn o tp r o v i d es a t i s f i e dp i a y b a c kq u a l t y b e s i d e sd i f f e r e n c ei nt e c h n i c a ls o l u t i o na d o p t e db yv b d a n dl i v eb r o a d c 够t ，s u c hp h e n o m e n o nm a yh a v em o r er e i a t i o nw i t ht h ef o l l o w i n gf a c t o r s ：p o p u l a r i t yo fa m e d i af i l e ，q u a n t i t yo fu s e rc o m m u n i t y ，b e h a v i o ro fu s e rp a r t i c i p a t i o no rd e p a n u r e i no r d e rt oi m p r o v et h eq u a l i t yo fv r o ds e r v i c e ，u s e r s c o l l a b o r a t i o na n dr e s o u r c es h a r i n ga m o n gt h e m a r es e i e c t e d 觞r e s e a r c ho b i e c t so f t h i sd i s s e r t a t i o na n dt h ef o l i o w i n gs u b i e c t sa r es t u d i e d ： 1 i nv b d ，t h es k i l lo fp i a y b a c ka f t e rd o w n l o a d i n gi so r e ne m p l o y e da tc l i e n tt oa c h i e v es m 0 0 t h d l a y b a c k ac a c h ec o i l a b o r a t i o nm o d e l ( a c m ) i sp r o p o s e dt os h a r em e d i ac o n t e n tc a c h e db yc l i e n t sf o r v r o dw i t hr e f e r e n c ef 而mp 2 pt e c h n o l o g y c c mh a st w ot o p i c sa n dt h e ya r ec o n s t r u c t i o no fp 2 pn e t w o r k a n dam e c h a n i s mo fs h a r i n gs t r e a m i n gc o n t e n t c c m sn e t w o r kc o n s i s t so ft w ol a y e r s ：t h eu p p e ra n dt h e l o w e r t h o s eu l t r a p e e r sf o n nt h eu p p e ri a y e rw h i l ea l l l e a fp e e r sl i ei nt h ei o w e ro n e u l t r a p e e r sc o n s t r u c t t h eu p p e rn e t w o r kw i t ha i do fd i s t r i b u t e dh a s ht a b l e ( d h t ) w h i c hc a ng u a r a n t e et h a t1 0 0 k u pr e q u e s t sa r e r e s p o n s e di nl i m i t e dh o p s al e a fc a ne s t a b l i s hs e v e r a lc o n n e c t i o n sw i t hu l t r a p e e r st 0e n h a n c es y s t e m r e l i a b i l i t y f o rt h ep u r p o s eo fl o a db a l a n c eo fs o u r c es e r v e r s ，am e c h a n i s mo fs h a r i n gs t r e a m i n gc o n t e n ti s p r e s e n tt oe x p l o r eo p e r a t i o n a lc a p a b i l i 毗s t o r a g es p a c ea n dn e t w o r kt h m u g h p u to fc l i e n t sb yc o n t e n t s t o r a g ea n dr e t r a n s m i s s i o n f r o mt h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lp r o o eo c mc 锄r e d u c e 他q u i r e m e n t so fo u t s i d eb a n d w i d t he f 拜c i e n t ly ，i m p r o v er a t eo fc l i e n t sc a c h em u l t i p l e x i n ga n dc u td o w n c o s to fs o u r c es e r v e r s 2 d i 行b r e n t 。w i t hl i v eb r o a d c a s t av - o dc l i e n tc a nf 弧f o n ：v a r d ，b a c k w i n do rp u l lt h ep r o g r e s s i v e s l i d e rt oa n yp o s i t i o nh ew a n t s a l it h e s eo p e r a t i o n sb r i n ga d d i t i o n a lp r o b l e m sw h e ns h a r i n gc a c h eo fc l i e n t s i d e f o rt h ep u r p o s eo fe s t a b l i s h i n gc o l l a b o r a t i o na m o n gc l i e n t st oag r e a t e re x t e m ，t w or e p l a c e m e n t a l g o r i t h m sa r ep m d o s e di nt h i sd i s s e r t a t i o n ：o n ei sb a l s e do ns u p p i y d e m a n dr e l a t i o no fm e d i as t r e a m i n 2 a n da n o t h e ri sc o n c e m e dw i t ht h en u m b e ro fm e d i af i l e s b e s i d e st h e o r e t i c a la n a l y s i sw i t hf lf oa n dl r u ， e x p e r i m e n ti sa i s op e r f o r m e dt oc o m p a r et h eb o t ha i g o r i t h m sw i t hf i f o ，l r ua n dl s b ( 1 e a s ts e n tb y t e s ) i n t e 丌n so fs t a r t u pd e i a y t h en u m b e ro fr e p “c a sa n dd e p e n d e n c yo ns o u r c es e r v e r s t h er e s u l t ss h o wt h a tt h e b o t ha l g o r i t h m sa l m o s te x c e e df i f oa n dl r ui na i la s p e d sa n dp r e c e d el s bi nt h en u m b e ro fr e p l i c 嬲 w h i l eh a v i n gs i m i l a rp e r f b m l a n c ew i t hl s bi na n o t h e rt w of i e l d s 3 t h e r ea r eag r e a tn u m b e ro fs e r v e rp e e r sw h i c hc a nb e n e f i to t h e r ss i m u i t a n e o u s i yi np 2 pn e t w o r k a r e rs h a r i n 2t h e i ro w nc a c h e t h ec l i e n t sh a v et 0s e l e c tt h em o s ta p p r o p r i a t ep e e r sf r o mt h e s es e n ，e ro n e s m e a n w h i l e 。t h e s ec i i e n t sm a ys e en e wp e e r s t h e r e f o r e ，t h ep o s i t i o nw h e r eap e e rl i e s i nat r e ei s b e c o m i n gm o r ei m p o r t a n t ap e e rs e l e c t i o na l g o r i t h mi sp r o p o s e di nt e n n so fp e e r sp e r f b m a n c ea n d c o n t r b u t i o nf o rt h et r e e - b a s e dc o n t e n td e l i v e 眄s c h e m e i nt h i ss c h e m e ，t h ep e e rs e l e c t i o ni sa c c o m p l i s h e d b yp e e r sw h op r o v i d es e i c ef o ro t h e r st oa d j u s tc h i l d r e n ，sp o s i t i o ni nt h et r e ea c c o r d i n gt oc o m p a r e d r e s u l t sb e t w e e nn e wp e e r sa n do l do n e si nt e r m so fv a l u e so fp e e r sp e 晌m a n c ea n dc o n t r i b u t i o n f r o m e x p e r i m e n t s ，i ti sf o u n dt h a tc o n t r i b u t i o no fp e e r si sr a i s e d ；d e p t ho ft h et r e e ，a v e r a g eh o p su s e dt oj o i na s y s t e mf o rn e wp e e r s 锄dm en u m b e ro fs i g n a l t n t e r m p ti sr e d u c e dg r e a t i y 4 l i k eo t h e ra p p l i c a t i o n s ，t h e r ee x i s t su s e r sp r e f e r e n c eo ri n t e r e s t si nm e d i as t 陀a m i n g i ft h i s f e a t u r ec a nb et a k e ni n t oc o n c e mw h e ns e t t i n gu pp 2 pn e 似o r k ，“m a yo 仃e rh e i pt 0o p e r a t i o n 觚d m a i n t e n a n c eo fa p p l i c a t i o n s u p o nt h a t ，t h i sd i s s e r t a t i o na t t e m p st oi n t r o d u c eg r o u po rl a y e ds c h e m ei n t o t h es t m c t u r e do v e r i a yw h i c hh 舔af o m e r l yn a tn e 觚o r kt o p o l o g y e a c hg m u pc a nb ef o m e db yp e e r s h a “n gs i m i i a ri n t e r e s t s 柚dr e p r e s e n t e db yag r o u pl e a d e r - a i ll e a d e r sc o n s t i t u t et h eu p p e rn e t w o r ka n d o t h e rp e e r si nag m u pm a k eu pw i t ht h el o w e ro n e h e n c e ，t h es i z eo fr o u t i n gt a b i em a i n t a i n e db ya n o r d i n a r yp e e rc a nb es h o r t e n e dr e m a r k a b l y a n db e h a v i o rl i k ea r r i v a lo rd e p a r t u 陀o fap e e rw i t h i no n e g r o u pw 订ln o ta f f e c tm e m b e r so fo t h e rg r o u p s m o r e o v e r ，al o o k u p 他q u e s tf o rc o n t e n tw i t ht h es a m e p r e f e r e n c ec a nb er e s p o n s e dw i t h i nag r o u p e v e nf o rr e q u e s t sh a v i n gt ot r a v e r s em u l t i g r o u p s ，t h ea u g m e n t o fa v e r a g eh o p si sm i n i m a la n dc a nb ei g n o r e d a tt h ee n do ft h i sd i s s e r t a t i o n ，t h ed e s i g no fav b ds y s t e mb a s e do nc c mi sd e s c r i b e di nd e t a i l ，s u c h a sb a c k g r o u n d ，s y s t e ma r c h i t e c t u r e ，m o d u l e s ，m e s s a g e s ，e ta 1 b e s i d e s ，ac o m p a r i s o ni sm a d ef o rar e a l i s t i c p 2 pp i a t f o r mw i t h o u t 锄dw i t hc a c h et e c h n i q u e w i t hc a c h i n g ，t h en e t w o r kb a n d w i d t hi na nu i t r a p e e ri s r e d u c e dt o2 5 3 0 o ft h a tw i t h o u tc a c h i n g a n dt h et o pc p uu s a g ei so n l ya b o u t2 0 m o r e o v e r ，t h e b a n d w i d t hi sb e l o wlm b p se v e nt h i su l t r a p e e rk e e pc o n n e c t i o nw i t h5 0 0l e a v e ss i m u l t a n e o u s l y 1 0 y w o r d s ：p 2 pn e t w o r k s ：s t r e a m i n gm e d i a ；v b d ；c a c h e ；s h a r i n g ；r e p l a c e m e n ta i g o r i t h m ；p e e rs e l e c t i o n u 目录 摘要1 a b s t r a c t l l 目 录一l i i 论文插图索引 论文表格索引v i l 第l 章 绪论1 1 1 p 2 p 点播系统的组成及特征1 1 2 p 2 p 流媒体技术的研究现状4 1 2 1 p 2 p 流媒体内容分发技术的研究现状4 1 2 2 流媒体缓存技术的研究现状5 1 2 3 p 2 p 网络节点选择的研究现状7 1 3 研究h 标及内容8 1 4 论文主要贡献9 l ，5 论文组织结构1 0 第2 章 2 1 2 2 2 3 流媒体点播的客厂i 端缓存合作模犁1 l 弓l 言1l 相关的研究ll 客户端缓存合作模犁c c m 1 2 2 3 i c c m 的网络拓扑1 3 2 3 2 节点的加入和退出1 4 2 3 3 节点及分片命名与分片信息发布1 4 2 3 4 分片信息的搜索1 5 2 3 5 分片的存储与转发机制1 6 2 3 6 源服务器负载理论分析，1 6 2 4 分片存储与转发机制的实验及评估2 0 2 4 1 日忠特征分析2 l 2 4 2 节点的存储负载2 l 2 4 3 外部网络流量需求和命中率2 2 2 4 4 延时2 3 2 4 5 不同缓存尺寸的性能比较2 3 2 5 本章小结2 5 第3 章 3 1 3 2 3 3 流媒体缓存的内容置换算法2 6 弓l 育2 6 相关的研究2 6 对f i f o 和l r u 的分析2 7 3 3 1 f i f o 队列2 8 3 3 2 l r u 算法2 8 流媒体对象的置换算法2 9 3 4 1 基于分片供求关系的置换算法( s u p p l y d e m a n d ，s d 算法) 2 9 3 。4 2 基于分片副本数量的置换( r e p i i c a ，r e p 算法) 3 0 3 4 3 算法描述3l n l 3 4 4 s d 和r e p 算法的伪码表示3 2 3 5 仿真实验3 3 3 5 1 实验配置。3 3 3 5 2 源服务器带宽开销3 3 3 5 3启动延迟3 4 3 5 4 副本数量3 5 3 5 5源服务器依赖度3 6 3 6 本章小结3 7 第4 章流媒体内容分发结构中的节点选择算法3 8 4 1引言3 8 4 2 相关的研究3 8 4 3节点选择和调整算法一3 9 4 3 1 系统测度3 9 4 3 2客广的选择与调整4 0 4 3 3节点退出4 1 4 3 4 算法描述4 2 4 3 5树深度4 3 4 3 6 的取值4 3 4 4实验和结果分析4 3 4 4 1 实验配置4 4 4 4 2内容分发树深度4 4 4 4 3贡献度4 5 4 4 4 平均跳数4 6 4 4 5信号中断4 6 4 5 本章小结4 6 第5 章分群结构化o v e r l a y 网络4 8 5 1 引。言4 8 5 2 相关的研究4 8 5 3g c h o r d 模型4 9 5 3 1 g c h o r d 的拓扑结构4 9 5 3 2节点的命名与路由表设计。5 0 5 3 3 节点定位和路由5 l 5 3 4 节点的加入和退出5l 5 4 性能评估5 2 5 4 1节点的度5 2 5 4 2网络直径5 2 5 5 实验与分析5 3 5 5 1g c h o r d 与c h o r d 的平均路径长度5 3 5 5 2 不同分群数量的路由结果5 3 5 6本章小结5 4 第6 章基于c c m 的流媒体点播系统设计5 5 6 1 设计目标5 5 6 2 系统架构。5 5 6 3 模块设计5 6 6 3 1 p 2 p 网络5 6 6 3 2 请求响应及转发6 0 6 3 3 分片访问信息维护6 l 6 3 4 分片访问信息发布一6 l 6 3 5流媒体分片化处理6 2 6 3 6 流媒体服务6 3 6 3 7 分片转发一6 4 6 3 8 缓存管理6 6 6 3 9 节点选择6 7 i v ! ：! ? 孽蝥冀型二6 9 ，3 jl 妻挚磐展示i ：i ； ! !重篓彗型：一：_ ：t _ ：= 一i i ：i 磊 6 5 p 2 p 系统r f l 的消息缓存i ：i ：藉 第? ，芋氅蹇语7 2 ：!璺结：= ：= 二：荔 7 2 下一步工作：z ：荔 参考文献7 5 致谢8 0 攻读博士学位期间发表或录用的学术论文8 l 攻读博士学位期问参加的科研项目8 2 v 论文插图索引 图1 1 媒体流行度的重尾分布2 图1 2 点播服务中的用户行为特征3 图2 1c c m 的源端和客户端模块1 3 图2 2c c m 网络拓扑结构1 4 图2 3 分片信息的定位过程一l 5 图2 4 源服务器的理论负载1 8 图2 5 源服务器上流行度最高的理论负载1 9 图2 6 缓存比率为1 5 时不同流行度的源服务器负载2 0 图2 7 采用缓存共享前后的存储空间比较一2 2 图2 8 各跳数值对应请求的数量分布一2 3 图2 9 不同缓存尺寸对二j 二存储、外部网络流量和总跳数的影响2 4 图2 1 0 缓存尺寸为l 和l o o 时非0 跳数对应请求数量的比较2 5 图3 1 节点到达间隔的三种不同情形一2 8 图3 2s d 算法的置换过程3 0 图3 3r e p 算法的置换过程3l 图3 4s d 和r e p 置换的伪码表示3 2 图3 5c c m 与c s 模式下源服务器的带宽开销比较3 4 图3 6 不同到达间隔的启动延迟比较。3 5 图3 7 不同到达问隔的副本数量比较3 6 图3 8 不同到达间隔的源服务器依赖度比较。3 7 图4 1 服务节点连接资源未达到饱和时的连接模式。4 0 图4 2 服务节点连接资源达到饱和时的连接模式一4 l 图4 3 节点c 离开系统后其客，_ 节点f 和g 重新查找服务节点4 2 图4 4 客户节点选择算法的伪码表示4 2 图4 5 树深度均值及标准差4 4 图4 6g p s 与c p s 在树深度方面的比较4 5 图4 7 不同贡献度对应节点数量的比较4 5 图4 8g p s 与c p s 在平均跳数的比较。4 6 图5 1g c h o r d 中节点的组织结构示意图5 0 图5 2 群l 首领节点维护的跨群路由表5 l 图5 3 群l 首领节点维护的群内路由衷5 2 图5 4g c h o r d 与c h o r d 平均路径长度办面的比较5 3 图5 5 不同分群数量的平均路径长度比较5 4 图6 1 基于c c m 的流媒体点播系统5 5 图6 2 源端和客户端的功能模块5 6 图6 3 采用p o n gc a c h e 前后节点间消息数量比较7 1 论文表格索引 2 1b u 日志的特点和数据分析2 l 2 2 各节点使用缓存共享后的存储量2 2 3 1 符号及其含义2 7 3 2 动态参数及其取值3 3 4 1 实验参数配置4 4 4 2c p s 算法引起的中断总数及其均值4 6 6 1 分组首部数据结构。5 7 6 2c h o r d 路由农结构5 7 6 3c h o r d 网络模块消息及其结构5 7 6 4 查询及响应消息的结构。5 8 6 5 超节点的查询请求列表结构。5 8 6 6 节点信息结构。5 9 6 7 叶节点加入网络交互消息及其结构一5 9 6 8 节点与b s 交互消息发其结构6 0 6 9 索引节点返回目标节点的消息结构。6 0 6 1 0 叶节点维护的查询请求列表结构6 0 6 1 l 节点信息结构一。6 l 6 1 2 分片访问信息结构6 l 6 1 3 更新分片访问信息的消息结构6 1 6 1 4 分片元数据结构6 2 表6 1 5 点播请求内容6 3 表6 1 6 会话信息结构6 4 表6 17 分片清求列表数据结构6 5 表6 18 分片数据转发的消息结构6 5 表6 19 缓存分片信息列表数据结构6 6 表6 2