（计算机应用技术专业论文）p2p流媒体分发网络中路由热区问题的研究.pdf

北京邮电大学博士学位论文p 2 p 流媒体分发网络中路由热区问题的研究 p 2 p 流媒体分发网络中路由热区问题的研究 摘要 路由热区问题是p 2 p 流媒体分发网络的固有问题。路由热区问题又称为瞬间 拥塞问题，其产生的典型原因是由于大量不可预知的用户同时向某个特定的服务 节点请求流服务，从而临时地导致该服务节点分发能力的淹没( 即节点软失效) 和网络连接的过载。通过现有的p 2 p 路由协议很难从根本上解决路由热区问题。 因此，必须研究一套有效的方法来解决p 2 p 流媒体分发网络中的路由热区问题， 保证高质量的流媒体传输。 本文的研究从三个方面解决p 2 p 流媒体分发网络中的路由热区问题。包括： 如何避免路由热区、如何快速诊断及定位路由热区、如何有效地恢复路由热区。 概括起来，本文的主要贡献如下： ( 1 ) 从博弈论的角度来解决p 2 p 流媒体分发网络中的路由热区避免问题。将路 由热区避免问题归结为一个非协作的博弈问题，提出了路由热区避免的系 统分析模型。在此系统模型基础之上，提出了一个激励兼容的定价策略以 驱动网络达到与最优状态一致的纳什均衡，从而有效地避免路由热区的产 生。在此基础上给出了分布式算法以求解激励兼容的定价策略。通过理论 分析和仿真证明了这个算法可有效地避免路由热区的出现。 ( 2 ) 对p 2 p 流媒体分发网络中的路由热区诊断及定位问题进行了深入研究。首 先给出了一个基于图的系统分析模型，这个模型考虑的p 2 p 流媒体分发网 络中各个对象之间的依赖关系，因而适用于大规模的网络。其次，基于这 个模型，我们证明了路由热区诊断及定位问题是一个n p 完全问题，并设 计了一个多项式时间的启发式算法- - m m d h d 算法。对时间复杂度和相 对误差的理论分析显示了在大多数的情况下，该算法可求得近似最优解。 最后，仿真结果也表明了该算法能快速有效地诊断及定位路由热区。 ( 3 ) 对p 2 p 流媒体分发网络中的路由热区恢复问题进行了深入研究。我们给出 了一个分层的路由热区恢复机制：l r h r ；并给出了l r h r 机制的两种变 形g n p l r h r 和r r n s l r h r 。g n p l r h r 机制使用b o w y e r - w a t s o n 算 法构造d e l a u n a y 三角网，并利用d e l a u n a y 三角网的性质寻找最优的路由 热区恢复方案。r r n s l r h r 机制则随机选取恢复邻居。对计算复杂度和 恢复时延的性能分析表明：l r h r 是有效的路由热区的恢复机制。仿真结 果显示了l r h r 机制对路由热区恢复的有效性。 ( 4 ) 对p 2 p 流媒体分发网络的应用实例一基于p 2 p s i p 的视频会议系统进行了 深入研究。提出了基于p 2 p s i p 的视频会议系统的框架，它是动态可扩展 北京邮电大学博士学位论文 p 2 p 流媒体分发网络中路由热区问题的研究 的。基于这个框架，我们设计和实现了一个基于p 2 p s i p 的视频会议原型 系统- - s o p v c 系统。s o p v c 系统采用单人发言的会议模式。在该会议模 式基础上，我们对先前提出的路由热区避免机制、路由热区诊断和定位机 制以及路由热区恢复机制进行了初步的实验。实验结果再次表明这些机制 对于解决p 2 p 流媒体分发网络中路由热区问题是有效的。 关键词：p 2 p ，流媒体、路由热区、瞬间拥塞、p 2 p 流媒体分发网络 北京邮电大学博士学位论文 p 2 p 流媒体分发网络中路由热区问题的研究 r e s e a r c ho nr o u t i n gh o t s p o tf o rp e e r - t o - p e e rm e d i as t r e a m i n g d i s t r i b u t i o nn e t w o r k a b s t r a c t r o u t i n gh o t s p o t , a k f t f l a s h 凹o w d i n g i so n eo ff u n d a m e n t a li s s u e s i np 2 p s t r e a m i n g d i s t r i b u t i o nn e t w o r k ar o m i n gh o t s p o ti st y p i c a l l yc r e a t e db ya l l u n a n t i c i p a t e dn e we v e n tt h a tt r i g g e r sa l lu n a n t i c i p a t e ds u r g eo fu s e r st h a tr e q u e s t s t r e a m i n gs e r v i c ef l o r as o m ep a r t i c u l a rp e e r s ，t e m p o r a r i l yo v e r w h e l m i n gt h ep e e r s d e l i v e r yc a p a b i l i t i e sa n do v e r l o a d i n gn e t w o r kc o n n e c t i o n s h o w e v e r , f o rp 2 ps t r e a m i n g d i s t r i b u t i o nn e t w o r k , i ti sd i f f i c u l tt or e s o l v et h er o u t i n gh o t s p o tp r o b l e mo n l yd e p e n d e d o nt h ec u r r e n tm u t i n gm e c h a n i s m s t h u s ，i ti sn e c e s s a r yt od e s i g nas e r i e so fs c h e m e st o r e s o l v et h er o u t i n gh o t s p o tp r o b l e mi np 2 ps t r e a m i n gd i s t r i b u t i o nn e t w o r ka n dd i s t r i b u t e m e d i as t r e a m i n gc o n t e n t sw i t hh i g hq u a l i t y i nt h i st h e s i s ，w er e s o l v et h er o u t i n gh o t s p o tp r o b l e mi np 2 ps t r e a m i n gd i s t r i b u t i o n n e t w o r kf r o mt h ef o l l o w i n ga s p e c t s ：( 1 ) h o wt oa v o i dt h er o u t i n gh o t s p o tp r i o rt oa h o t s p o te v e n t ；( 2 ) h o w t od i s c o v e rt h er o u t i n gh o t s p o tl o c a t i o nf a s t l y ；( 3 ) h o wt or e c o v e r t h er o u t i n gh o t s p o t se f f i c e n t l y i ns u m m a r y , t h em a j o rc o n t r i b u t i o n so ft h i st h e s i sa r ea s f o l l o w s ： ( 1 ) w ec o n s i d e rt h i sh o t s p o ta v o i d i n gp r o b l e mf r o mag a m et h e o r e t i c a ls t a n d p o i n t t h ep r o b l e mi sp o s e da san o n c o o p e r a t i v eg a m e , f o rw h i c ht h en a s h e q u i l i b r i u mw a si n v e s t i g a t e d w ep r o p s ea na n a l y s i sm o d e lf o rt h ep r o b l e m b a s e do nt h em o d e l ，w ep r o p o s ea ni n c e n t i v e - c o m p a t i b l ep r i c i n gm e c h a n i s m ， w h i c hc a nd r i v e rt h en e t w o r kt ot h en a s he q u i l i b r i u m w ea l s op r o p o s ea n a d a p t i v ea l g o r i t h mf o rd i s t r i b u t e dc o m p u t a t i o no ft h ei n c e n t i v ec o m p a t i b l e p r i c i n gm e c h a n i s m 1 1 1 e t h e o r e t i ca n ds i m u l a t i o nr e s u l t ss h o wt h a tt h e m e c h a n i s ma n da l g o r i t h mc a na v o i dt h er o u t i n gh o t s p o te f f i c i e n t l y ( 2 ) w - cc o n s i d e rh o w t od i s c o v e rt h er o u t i n gh o t s p o tl o c a t i o n f i r s t , w ep r o p o s ea g r a p h - b a s e ds y s t e mm o d e l ，w h i c ht a k e si n t oa c c o u n tt h ed e p e n d e n c i e sa m o n g m u l t i p l ed i f f e r e n tp e e r sa n di ss u i t a b l ef o rh o t s p o tl o c a l i z a t i o ni nl a r g e - s c a l e r e a l t i m ep 2 pn e t w o r k s s e c o n d , b a s e do nt h i sm o d e l ，w ep r o v et h a tt h e p r o b l e mi sn p - c o m p l e t ea n dt h u sd e s i g nah e u r i s t i ca l g o r i t h m ( m m d h d a l g o r i t h m ) f o rf i n d i n g an e a r - o p t i m a ls o l u t i o nt oh o t s p o tl o c a t i o n t h e t h e o r 硝ca n a l y s i ss h o w st h a to u ra l g o r i t h mi san e a r - o p t i m a ls o l u t i o nf r o mt h e t w oa s p e c t s ：c o m p u t a t i o n a lc o m p l e x i t ya n dt h ea c c u r a c yo fh o t s p o tl o c a t i o n f i n a l l y , t h ee x t e n s i v es i m u l a t i o n sa r e a l s oc o n d u c t e dt ov m f yt h a t t h e m m d h d a l g o r i t h mc a n l o c a t er o u t i n gh o t s p o t sq u i c k l ya n de f f i c i e n t l y n 1 北京邮电大学博士学位论文p 2 p 流媒体分发网络中路由热区问题的研究 ( 3 ) w ea d d r e s st h ep r o b l e mo fe f f i c i e n th o t s p o tr e c o v e r yi np 2 ps t r e a m i n g d i s t r i b u t i o nn e t w o r k s w ep r o p o s el a y e r e dr o u t i n gh o t s p o tr e c o v e r y ( l r h r ) m e c h a n i s ma n da l s o p r e s e n tt w ov a r i a n t s o fl r h r ：g n p l r h ra n d r r n s - l r h r g n p l r h rc o n s t r u c td e l a u n a yt r i a n g u l a t i o n ( d t ) m e s h e s a m o n gt h eh o s t sb yt h eb o w y e r - w a t s o na l g o r i t h ma n dt h e nf i n dt h eo p t i m a l h o t s p o tr e c o v e r ys c h e m eu s i n gt h ep r o p e r t yo fd t r r n s l r h rs e l e c t st h e r e c o v e r yn e i g h b o u rr a n d o m a l y w ep r e s e n tt h ea n a l y s i so nt h ec o m p l e x i t ya n d h o t s p o tr e c o v e r yd e l a yo nl r h ra n dt h er e s u l t ss h o wt h a tl r h ri sa l l e f f e c t i v eh o t s p o tr e c o v e r ym e c h a n i s m t h es i m u l a t e dr e s u l t ss h o wt h a tl r h r i se f f e c t i v et or e c o v e r yt h er o u t i n gh o t s p o t ( 4 ) w ea d d r e s sat y p i c a la p p l i c a t i o ni n s t a n c eo fp 2 ps t r e a m i n gd i s t r i b u t i o n n e t w o r k ：t h ev i d e oe o n f e r e n c i n gb a s e do np 2 p s i p w ep r o p o s ead y n a m i c s c a l a b l ef r a m e w o r ko fp 2 p s i pv i d e oc o n f e r e n c e b a s e do nt h ef r a m e w o r k ，w e i m p l e m e n tap r o t o t y p eo fp 2 p - s i pv i d e oc o n f e r e n c e ：s o p v c t h es o p v c a d o p t st h es i n g l e s p e a k e rc o n f e r e n c i n gm o d e b a s e do nt h i sm o d e ，w es i m p l y e x p e r i m e n tt h e s ep r o p o s e dm e c h a n i s m s t h ee x p e r i m e n tr e s u l t ss h o wt h a t t h e s em e c h a n i s m sa l ee f f i c i e n tt os o l v i n gt h er o u t i n gh o t s p o tp r o b l e mi nt h e p 2 p s t r e a m i n gd i s t r i b u t i o nn e t w o r k k e yw o r d s ：p e e r - t o p e e r , s t r e a m i n gm e d i a , m u t i n gh o t s p o t , f l a s hc r o w d ，p 2 p s t r e a m i n gd i s t r i b u t i o nn e t w o r k i v 北京邮电大学博士学位论文p 2 p 流媒体分发网络中路由热区问题的研究 图表目录 图2 1p 2 p 与c s 模式的对比6 图2 2p 2 p 流媒体分发网络体系结构9 图2 3c j n u s t r e a m 网络采用的洪泛搜索算法。1 l 图2 - 4p r o m i s e 网络的消息路由12 图2 5z i g z a g 网络1 3 图2 6 单源的流媒体数据提供方式1 4 图2 7 多源的流媒体数据提供方式1 5 图2 8 基于源节点速率调整的路由热区避免机制1 9 图3 1t p m d n 框架31 图3 - 2m - t p m d n 框架3 2 图3 3 两个媒体会话共享一个a g 进行媒体转发3 5 图3 4 权重因子的值与迭代次数的比较4 4 图3 5a g 的平均拥塞和迭代次数的关系4 5 图3 - 6 四种热区避免机制的平均时延比较4 5 图3 7 改变节点共享存储容量时四种机制的视频质量比较4 6 图3 8 改变丢包率时四种机制的视频质量比较4 7 图4 - l ( a ) p 2 p 网络拓扑实例；( b ) 对应的决策图5 0 图4 - 2 ( a ) 实例的决策图；( b ) 对应的告警簇。5 7 图禾3m m d h d 算法的分割阶段5 8 图4 - 4m m d h d 算法的选择阶段5 8 图4 _ 5m m d h d 算法的相对错误6 0 图4 6m m d h d 算法找到正确解的频度6 l 图4 - 7 随节点数增加四种机制检测时间的比较6 2 图4 _ 8 随路由热区数增加四种机制检测时间的比较6 3 图4 9 随节点数增加四种机制控制开销的比较6 4 图4 1 0 随路由热区数增加四种机制控制开销的比较6 4 图5 1 分层的路由热区恢复框架6 7 图5 29 点v o r o n o i 图与对应的d e l a u n a y 三角网6 8 图5 3d e l a u n a y 三角网节点插入示意图6 9 图5 - 4 ( a ) 9 点d e l a u n a y 网格剖分图；( b ) 去除边框的三角网格6 9 图5 5 节点x 在第，层查找最近恢复邻居y j 的集中式方法7 1 图5 6 节点x 在第，层查找最近恢复邻居y j 的分布式方法7 2 图5 7 恢复邻居选择的时序图7 3 图5 8r d p 与网络中节点数目的关系7 6 图5 9p l s 与网络中节点数目的关系7 7 图5 1 0r l r 与每层中恢复邻居节点的数目k 之间的关系7 7 图5 1 1r l r 与随机恢复邻居的数目m 之间的关系7 8 图5 1 2r l r 与路由热区恢复时延界限妒之间的关系7 8 图5 1 3r l r 与路由热区节点比率7 9 图5 1 4 不同路由热区恢复机制的r l r 的比较7 9 图5 1 5 几种不同恢复机制的平均重传开销8 0 图6 1s o p v c 系统的网络模型8 5 图6 2s o p v c 系统的p 2 p s i p 节点模型8 6 北京邮电大学博士学位论文p 2 p 流媒体分发网络中路由热区问题的研究 岳3 会议客户端程序界面8 7 6 - 4 会议管理界面8 7 每5a l m 树的构造8 9 6 _ 6 路由热区避免机制的实验环境9 0 6 - 7 用户节点实验路由热区避免机制的流程图9 2 6 8 超级节点实验路由热区避免机制的流程图9 3 6 - 9 平均时延的比较9 5 6 1 0 视频质量的比较9 5 6 - 1 l 路由热区诊断及定位机制的实验环境9 6 昏1 2 用户节点实验路由热区诊断及定位机制的流程图9 7 6 - 1 3 超级节点实验路由热区诊断及定位机制的流程图。9 9 6 - 1 4 路由热区诊断及定位的检测时间1 0 0 6 1 5 路由热区诊断及定位的控制开销1 0 0 岳1 6 超级节点实验路由热区恢复机制的流程图1 0 2 昏1 7 执行g n p l r h r 机制后的a l m 树1 0 4 6 1 8g n p l r h r 机制下r l r 与受限节点总数之间的关系1 0 4 6 1 9g n p l r h r 机制下平均重传开销与受限节点总数之间的关系1 0 5 表2 1 四种不同网络拓扑结构的p 2 p 流媒体分发网络性能比较1 4 表2 2 不同的路由热区避免机制的性能比较2 1 表2 3 四类不同的路由热区诊断及定位机制的性能比较2 3 表2 4 两类不同的路由热区恢复机制的性能比较2 6 表3 1 系统分析模型的符号定义3 7 表3 2 符号定义3 7 表4 _ 1m m d h d 算法5 6 表5 1 仿真主要性能指标7 6 表5 2 仿真主要参数配置7 6 表6 1s p 协议的六种请求消息8 3 表6 2s 口协议的六种响应消息8 3 表6 - 3p 2 p s i p 的三种会议模式8 4 表6 4 带权重因子的o p t i o n s 消息的实例9 3 表6 5 作为拥塞通知的o p t i o n s 消息的实例9 8 图图图图图图图图图图图图图图图图图 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包 含其它人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论 本人签名： ，本人承担一切相关责任。 日期：_ j 娑丑业 ， 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释 本 导 北京邮电大学博士学位论文 绪论 1 1 选题背景与意义 第1 章绪论 随着各类数字终端、服务器、网络带宽等资源持续保持类摩尔定律式的增长， 通过更直接有效的共享方式来提高沟通效率，减少资源浪费并保障信息服务安全 将为信息社会带来新一轮的发展高潮。i n t e r a c t 规模在不断扩大，接入设备以及计 算单元的数量和种类也越来越多。然而，目前这些设备以及计算单元并没有得到 充分的利用，如果能够将这些设备以及计算单元的处理器计算能力、磁盘存储能 力以及网络带宽等资源进行充分利用将会有效缓解目前i n t e r n e t 所面临的资源瓶颈 问题。p e e r - t o p e e r ( 简称p 2 p ，中译：对等计算) 网络技术正是这种新共享方式的 主要候选者之一，其主要目的就是充分利用i n t e r a c t 中所蕴含的潜在资源。 p 2 p 作为一种网络体系结构在本质上是分布式系统，p 2 p 网络中所有的节点 ( p e e r ) 是对等的，各节点具有相同的责任与能力并协同完成任务，节点之间通过 直接互连共享信息资源、处理器资源、存储资源甚至高速缓存资源等，无需依赖 集中式服务器或资源就可完成。这种模式与传统的客户端月艮务器( c l i e n t s e r v e r ， 简称c s ) 的网络模式形成鲜明对比。就目前发展状况而言，p 2 p 技术为服务共享、 分布式计算和信息交流提供了更灵活高效的模式，也为信息技术的发展带来了新 的挑战。 随着1 9 9 9 年n a p s t e r 文件共享系统的出现，p 2 p 网络已经变得越来越流行。 在2 0 0 3 年，p 2 p 已经成为了w e b 应用的主流支撑技术，在2 0 0 4 年底，基于p 2 p 的网络流量已经占据了超过6 0 的i n t e r n c t 流量。在p 2 p 网络技术的推动下，i n t e r n c t 的信息存储模式正由现在的“内容位于网络中心 模式逐渐转变为“内容位于网 络边缘 模式。这将有效地均衡网络负载，充分利用网络带宽，挖掘网络中所有 空闲主机的计算能力，有效地提高信息查询与搜索的效率，从而彻底改变人们发 布与获取信息的方式。因此，p 2 p 网络技术研究成为了目前的一个热点研究领域， 并被财富( f o r t u n e ) 杂志誉为将改观i n t e r n c t 未来的四大新技术之一。有理由 相信，随着更多的杀手级的p 2 p 应用的开发，p 2 p 网络将得到持续快速地发展， 拥有更广阔的市场应用前景。 目前i n t e r n e t 上的传输内容已逐渐由单纯的文字传输转变成为包含文本、音频、 视频的多媒体数据传输。这样的改变不仅使i n t e r n e t 使用者能获得更为丰富多样的 信息，同时也代表着多媒体网络时代的来临。面对有限的带宽和拥挤的拨号网络， 要实时地实现窄带网络的视频、音频传输，最好的解决方案之一就是采用p 2 p 流 式媒体( s t r e a m i n gm c d i a ) 的传输方式。 本论文的研究对象就是采用p 2 p 网络技术进行流媒体分发，即p 2 p 流媒体分 北京邮电大学博上学位论文绪论 发网络。p 2 p 流媒体分发网络利用各个终端用户的上行能力，将媒体流分发给大量 的终端用户。和p 2 p 文件传输网络相似，p 2 p 流媒体分发网络的媒体流传输是通 过分布式协议完成的，它将节点自组织成为分发树、环或m e s h 结构。而和p 2 p 文 件传输网络最大的区别在于，p 2 p 流媒体分发网络为所有连接用户提供的是实时服 务，有严格的q o s 要求。相对于传统的内容分发网络( c o n t e n td i s t r i b u t i o nn e t w o r k 简称c d n ) 而言，p 2 p 流媒体分发网络更具有吸引力，它不需要任何专用的下层 结构的支持，且随着用户数的增加可利用的网络资源也随之增加。 然而，通过p 2 p 流媒体分发网络分发高质量的实时多媒体内容仍然存在许多 迫切需要解决的问题。路由热区( r o u t i n g h o t s p o t ) ，又称为瞬间拥塞( f l a s hc r o w d ) ， 就是其中的一个问题。路由热区产生的典型原因是由于大量不可预知的用户同时 向某个节点请求服务，临时地导致该节点分发能力的淹没( 即节点的软失效) 和 网络连接的过载，进而使得该节点的下游节点无法得到满意的服务。著名的路由 热区现象出现在2 0 0 1 年9 月1 1 日，美国遭受9 1 1 袭击后，海量用户在很短时间内 同时访问了新闻网站w w w c l l l l o , , o m 和w w w n y t i m e s e o m ，导致这两个网站临时不 可用。 对于p 2 p 文件下载等非实时业务类而言，当路由热区发生时，现有的路由热 区解决方法有足够时间从其它备选节点上找到下载对象的副本，从而使得软失效 节点的部分下游节点能够切换到这些备选节点上继续进行下载。 然而对于本文关注的p 2 p 实时流媒体业务而言，这种仅依赖于现有路由协议 来解决路由热区的方案并不足以保障实时流媒体业务的q o s 要求，路由热区会造 成服务中断持续时间长以及数据包的大量丢失。从用户的角度而言，这是无法接 受的。因此，有必要提出一系列新的路由热区解决方案以满足p 2 p 流媒体分发网 络的q o s 需求。 1 2 项目背景和主要研究内容 本论文的研究是在国家自然科学基金资助项目( n o 9 0 6 1 2 0 1 3 ) 、教育部新世 纪优秀人才支持计划( n c e t - 0 4 0 1 1 0 ) 、国家“8 6 3 ”高技术研究发展计划项目 ( n o 2 0 0 6 a a 0 1 2 3 0 4 ) 和高等教育博士点基金( 2 0 0 5 0 0 1 3 0 1 0 ) 等项目的支持下进 行的，由于结合了当前p 2 p 网络技术发展前沿和流媒体业务的应用需求。因此， 论文的选题具有较强的前瞻性和实用意义。 在这些项目的支持下，作者在攻读博士学位期间的研究工作主要包括以下几 个方面： ( 1 ) 对p 2 p 流媒体分发网络进行了深入的研究。总结和分析了p 2 p 流媒体分 发网络的研究现状，并对p 2 p 流媒体分发网络中的路由热区问题进行了深 入的探讨和分析。 北京邮电大学博士学位论文绪论 ( 2 ) 采用博弈论的方法对p 2 p 流媒体分发网络中的路由热区避免问题进行了 深入研究，并将路由热区避免问题归为一个非协作的博弈问题。提出了路 由热区避免的系统分析模型。在此系统模型基础之上，提出了一个激励兼 容的定价策略以驱动网络达到与最优状态一致的纳什均衡，从而有效地避 免路由热区的产生。在此基础上给出了分布式的a w c 算法以求解激励兼 容的定价策略。通过理论分析和仿真论证了a w c 算法可有效地避免路由 热区的出现。 ( 3 ) 采用图论的方法对p 2 p 流媒体分发网络中的路由热区诊断及定位问题进 行了深入研究。首先给出了一个基于图的系统分析模型，这个模型考虑的 p 2 p 流媒体分发网络中各个对象之间的依赖关系。基于这个模型，利用最 优化理论证明了路由热区诊断及定位问题是一个n p 完全问题，并设计了 一个多项式时间的启发式算法m m d h d 算法，它为路由热区的定位找到 近似最优的解。该算法相对于穷举查找算法和贪婪查找算法而言，其时间 复杂度低，相对误差小。在大多数的情况下，m m d h d 算法可求得与穷 举查找算法相同的最优解。理论分析和仿真结果都表明了m m d h d 算法 能快速而准确地诊断及定位p 2 p 流媒体分发网络中的路由热区。 ( 钔采用三角剖分原理对p 2 p 流媒体分发网络中的路由热区恢复问题进行了 深入研究。提出了一个分层的路由热区恢复机制，即l r h r 机制，并给出 了l r h r 机制的两种变形g n p l r h r 和r r n s l r h r ；l r h r 机制利用 节点的网络坐标构造相应的v o r o n o i 图；在v o r o n o i 图中使用 b o w y e r - w a t s o n 算法构造d e l a u n a y 三角网；利用d e l a u n a y 三角网的性质 求解出最优的路由热区恢复方案。性能分析表明l r h r 是有效的路由热区 的恢复机制，它的时间复杂度低，适合于p 2 p 流媒体分发网络中的路由热 区恢复。仿真结果进一步验证了l r h r 对路由热区恢复的有效性。 ( 5 ) 对p 2 p 流媒体分发网络的典型应用实例基于p 2 p s i p 的视频会议系统进 行了深入研究。提出了基于p 2 p s 口的视频会议系统的框架，它是动态可 扩展的。基于这个框架，我们设计和实现了一个基于p 2 p s i p 的视频会议 原型系统- - s o p v c 系统。s o p v c 系统采用单人发言的会议模式。在该会 议模式基础上，我们对先前提出的路由热区避免机制、路由热区诊断和定 位机制以及路由热区恢复机制进行了初步的实验，并给出了实验流程及实 验结果。 1 3 研究工作的创新点 论文工作的主要创新点可以简要归纳如下： ( 1 ) 将博弈论原理用于p 2 p 流媒体分发网络中路由热区的避免问题。给出了一 北京邮电大学博士学位论文绪论 个激励兼容的定价策略以驱动网络达到与最优状态一致的纳什均衡，并提 出分布式的a w c 算法计算激励兼容的定价策略，从而有效地避免路由热 区。 ( 2 ) 对路由热区诊断及定位问题采用图论的方法进行研究。提出基于图的路由 热区定位模型。利用最优化理论证明路由热区诊断及定位问题是一个n p 完全问题；并设计了一个多项式时间的启发式算法快速准确地定位路由热 区。 ( 3 ) 对路由热区恢复问题采用三角剖分原理进行研究。提出一种分层的路由热 区恢复机制。它为网络构造v o r o n o i 图，并使用b o w y e f - w a t s o n 算法构造 d e l a u n a y 三角网，利用三角网属性快速而有效地进行路由热区的恢复。 ( 4 ) 提出了一个动态可扩展的基于p 2 p s i p 的视频会议系统框架，基于这个框 架，我们设计和实现了一个基于p 2 p s i p 的视频会议原型系统- - s o p v c 系统。在单人发言的会议模式之上对我们提出的路由热区避免机制、路由 热区诊断和定位机制以及路由热区恢复机制进行了初步的实验。 1 4 本文结构和安排 本文研究的主要内容包括p 2 p 流媒体分发网络中的路由热区避免机制、路由 热区诊断和定位机制、以及路由热区恢复机制。论文共包括七章，除了绪论和结 束语之外，其它章节的主要内容如下： 第2 章p 2 p 流媒体分发网络及路由热区综述 本章对p 2 p 的定义及特点、p 2 p 流媒体分发网络的体系结构、分类以及数据 提供方式进行了详细的介绍。并分析了p 2 p 流媒体分发网络的研究现状和未来研 究方向，从而进一步引出了本文的研究问题p 2 p 流媒体分发网络中路由热区问题， 并对该问题的研究现状和研究方法进行了深入的阐述与分析。 第3 章路由热区避免机制 本章采用博弈论的原理分析和解决p 2 p 流媒体分发网络中的路由热区避免问 题。首先我们对路由热区避免问题进行了概述，并简单介绍了策略型博弈的基本 概念和主要结论。接着给出了路由热区避免问题的系统分析模型，从该模型给出 了路由热区避免问题的数学描述。进而提出了基于激励兼容机制的定价策略，它 能有效地避免路由热区的出现。在此定价策略的基础上，提出了分布式的a w c 算 法以实现基于激励兼容机制的定价策略。理论分析和仿真结果表明a w c 算法可有 效地避免路由热区的出现。 第4 章路由热区诊断和定位机制 本章首先分析了p 2 p 流媒体分发网络中路由热区诊断和定位问题的背景。进而 给出了路由热区诊断及定位的分析模型。在这个模型基础上，我们利用最优化理 北京邮电大学博士学位论文 绪论 论证明了p 2 p 流媒体分发网络中路由热区诊断及定位问题是一个n p 完全问题。 接着我们给出了解决路由热区问题经典的非多项式时间的穷举查找算法和贪婪算 法，以及一个多项式时间的启发式算法m m d h d 算法。并通过理论分析说明了 m m d h d 算法的时间复杂度低并在大部分时间内能达到与穷举查找算法和贪婪算 法相同的最优解。仿真结果进一步说明了m m d h d 算法对于p 2 p 流媒体分发网络 中路由热区的诊断和定位的有效性。 第5 章路由热区恢复机制 本章研究的问题是p 2 p 流媒体分发网络中路由热区的恢复机制。首先，我们讨 论路由热区恢复问题的背景，并简单介绍了d e l a u n a y 方法的基本原理。接着我们 给出了一个分层的路由热区恢复机制l r h r 机制：并对l r h r 机制的两种变形 g n p l r h r 机制和r r n s l r h r 机制分别进行了讨论g n p l r h r 利用了 d e l a u n a y 三角网的性质寻找最优的路由热区恢复方案，而r r n s l r h r 则是随机 的路由热区恢复方案。性能分析表明了l r h r 机制是有效的路由热区恢复机制， l r h r 机制的时间复杂度低，适合于p 2 p 流媒体分发网络中的路由热区恢复。仿 真结果也验证了l r h r 机制对路由热区恢复的有效性。 第6 章实例研究 在本章中，我们研究了一个p 2 p 流媒体分发网络的应用实例一基于p 2 p s i p 的 视频会议系统。作为背景知识，我们首先介绍了s i p 、p 2 p s i p 以及视频会议系统 的基本概念和相关内容。接着，本章提出了动态可扩展的基于p 2 p s i p 的视频会议 系统的框架。基于这个框架，我们设计和实现了一个基于p 2 p s i p 的视频会议原型 系统一s o p v c 系统。在s o p v c 系统中，会议模式是单人发言的会议模式。在该 会议模式之上，初步地实验了我们提出的路由热区避免机制、路由热区诊断和定 位机制以及路由热区恢复机制。 北京邮电大学博士学位论文 p 2 p 流媒体分发网络及路由热区综述 第2 章p 2 p 流媒体分发网络及路由热区综述 本章对p 2 p 的定义及特点、p 2 p 流媒体分发网络的体系结构、分类和数据提供 方式进行了详细的介绍。分析了p 2 p 流媒体分发网络的研究现状和未来研究方向 从而进一步引出了本文的研究问题- - p 2 p 流媒体分发网络中路由热区问题，并对该 问题的研究现状和研究方法进行了深入的阐述与分析 2 1p 2 p 流媒体分发网络 2 1 1p 2 p 定义及特点 最近几年，p 2 p 迅速成为了学术界关注的热门话题，财富杂志更将p 2 p 列 为影响i n t e r n e t 未来的四项科技之一。目前，在学术界、工业界对于p 2 p 并没有一 个统一的定义，下面列举几个常用的定义仅供参考： p 2 p 是一类i n t e r a c t 网络，它允许一群有相同网络程序的计算机用户互相 连接可直接访问他人计算机存储的文件【1 】； p 2 p 网络是一类应用，它运行在个人计算机上，可共享其它接入i n t e r n e t 网络用户的文件；p 2 p 网络通过互相连接的计算机而不是集中