（计算机应用技术专业论文）基于优先级的动态分层应用层组播模型.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 i p 组播是工作在网络层的从一个源节点向一个组播组的多个目的节点发送数据的 一种传输机制。通过合并重复数据传输，源节点只需向所有目的节点发送一个单一的拷 贝，而无需向每个节点发送一遍数据，减少了带宽浪费和降低了服务器负担。源节点的 数据通过节点间构建的组播树来传输，在每个树节点处( 即路由器处) 复制转发，每条 路径只需传输一次数据。 虽然i p 组播在概念上很简单，但却一直未能广泛部署。这主要是由于它需要路由 器的支持从而不利于推广，另外还存在可扩展性和网络管理问题。应用层组播( a l m ) 作为i p 组播的替代在互联网中得到广泛的应用并且极具潜力。两种传输方式的主要区 别在于a l m 不需要额外的路由器的支持，数据的复制转发在各端点间进行而非路由器， 这使得a l m 极易被部署。 本文提出一个新的基于优先级的动态分层应用层组播模型c d m p ，模型通过固定的 三层模式对不同性质的节点进行分层来搭建整个架构，通过分域将性质接近的节点放在 一起以保证数据传输的效率和数据共享的公正性，并且减少了节点寻找路由的代价，加 快了当节点失败时的路由修复速度；通过增加一个考核层降低了当恶意节点增多时因为 频繁地加入退出而引发的整个系统的动荡。通过分析和仿真实验证明，c d m p 协议具有 良好的上述性质。 关键词：应用层组播；拓扑结构：优先级；分层；动态 a b s t r a c t i pm u l t i c a s ti san e t w o r kl a y e rm u l t i c a s tm e c h a n i s mf o rs e n d i n gd a t af r o ma s o u r c et oa l l t h em u l t i c a s tg r o u pm e m b e r s i n s t e a do f s e n d i n g as e p a r a t ec o p yo ft h ed a t at oe a c hm e m b e r o ft h eg r o u p ，t h es o u r c es e n d sas i n g l ec o p yt oa l lt h em e m b e r s b ym e r g i n gt h ed u p l i c a t e d d a t a w i t ham u l t i c a s t i n gt r e ec o n n e c t i n gt h em e m b e r s ，d a t ag e n e r a t e db yt h es o l j c et r a v e r s e e a c ht r e ee d g ee x a c t l yo n c ea n d b e i n gr e p l i c a t e da te a c hb r a n c h i n gn o d e ( i e t h er o u t e r ) a l t h o u g hc o n c e p t u a l l y s i m p l ea n de l e g a n t ，i pm u l t i c a s th a sn o ty e tb e e nw i d e l y d e p l o y e d t h i si sd u et ot h en e e do fr o u t e r ss u p p o nf o rm u l t i c a s ta n da l s ot h es c a l a b i l i t ya n d t h en e t w o r km a n a g e m e n t a p p l i c a t i o n - l a y e rm u l f i c a s t ( a l m ) ，a sa na l t e r n a t i v et o i p m u l t i c a s t ，h a sb e e nt h em o s tp r o s p e c t i v em e a n si nt h ei n t e m e ta n db e e nw i d e l yd e p l o y e d t h e m a j o rd i f f e r e n c eb e t w e e nt h e mi st h a ta l md o e sn o tr e q u i r ea d d i t i o n a lr o u t e rs u p p o r tf o r m u l t i c a s t ，a n dt h ep a c k e t s 毅er e p l i c a t e da te n d h o s t sw h e r e a si nt h ei pm u l t i c a s tt h ep a c k e t s a r er e p l i c a t e da tr o u t e r s t h i st h e s i sp r e s e n t san o v e la l m p r o t o c o l ，w h i c ha l l o w st h es t a b i l i t ya n di u s t n e s sw i t h s i m p l i c i t y , c a l l e dt h ec l a s s i f i e dd y n a m i cm o d e lb a s e do nt h ep r i o r i t yi na p p l i c a t i o n l a y e r m u l t i c a s t ( c d m p ) t h ec d m pc l a s s i f i e st h en o d e si n t od i f f e r e n tl e v e l st oe s t a b l i s ht h ew h 0 1 e m o d e l ，a n da l s oi nd i f f e r e n tz o n e sa c c o r d i n gt ot h en o d e s p r o p e r t i e s ，s oa st og u a r a n t e et h e s t a b i l i t ya n dt h ej u s t n e s s ，a sw e l la sl e s st r a f f i cd u r i n gt h ed y n a m i cr o u t ed i s c o v e r yp r o c e s s a n dt h eb r o k e nr o u t e sc o u l db er e p a i r e dl o c a l l yw i t h o u tr e d i s c o v e r y b yt h ea n a l y s i sa n d s i m u l a t i o n ，t h ep r o t o c o lc a l l e dc d m ph a sa c h i e v e de x c e l l e n tp e r f o r m a n c e k e y w o r d s ：a p p l i c a t i o n - l a y e rm u l t i c a s t ；t o p o l o g y ；p r i o r i t y ；c l a s s i f i e d ；d y n a m i c i l 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了中文特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得南京邮电大学或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 研究生签名：熟日期：j 衅 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。 除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京 邮电大学研究生部办理。 研究生妊蜱翩虢毕吼业 南京邮电大学硕士研究生学位论文第一章绪论 第一章绪论 1 1 研究背景 随着互联网的日趋普及和新技术的迅速发展，一大批新兴的网络多媒体应用开始涌 现并成为人们工作、生活中重要的组成部分，例如：网络电视、体育赛事广播、在线游 戏、远程教育等，这已经远远颠覆了我们以往的互联网应用。 2 0 0 4 年6 月是互联网历史上的一个分水岭，根据i d g ( i n t e m a t i o n a ld a t ag r o u p ， 国 际数据集团) 报告，视频流量首次超过音频流量，这标志着一个巨大全新的无形的掠夺 网络资源的应用开始蔓延。 德国宽带管理方案开发商i p o q u e 公司2 0 0 7 年8 - 9 月份对大约1 0 0 万用户的 3 p b ( 3 0 0 0 t b ) _ _ _ 互联网数据进行了分析统计，调查地区包括澳大利亚、东欧、德国、中东 和南欧地区。调查发现，目前网络带宽“消费大户”是p 2 p 文件共享，在中东占据了 4 9 ，东欧地区占据了8 3 ，如图l - l 。从全球来看，晚上时段的网络带宽有9 5 被p 2 p 占据。据国内权威部门统计，当前p 2 p 流量已经占整个互联网流量的约7 0 ，并且正 在以每年3 5 0 的速度增长。p 2 p 流量消耗了巨大的网络带宽，尤其是国际带宽，使网 络基础设施不堪重负，运营商苦不堪言。 r e l a t i v ep 2 pt r a f f i cv o l u m e 10 0 9 台一 8 3 黪。一缵 襄嚣 6 9 爹霪 ；秀 蓼霪 6 4 匿豸嚣凄 习 5 7 # ，。鬈 4 9 引 缎z 錾霪 斟 绣7t 鹆 苏确 雾霪 静，譬 豺，；枯 | 7鬓 彩7一 雾7 彩一；黔：缴貉；j * ，二荔级，t 二。葫缓 鍪! i 彰，“笤 霎，嚣 弱锄；# 二 ，i 荔 g e r m a n y e a s t e r ne u r o p es o u t h e r ne u r o p em i d d l ee a s t a u s t r a l i a 图l - 1 各国的p 2 p 流量 南京邮电大学硕士研究生学位论文第一章绪论 就具体的p 2 p 应用而言，i p o q u e 公司对当前最流行的协议b i t t o r r e m , e - d o n k e y , g n u t e l l o ，d i r e c t c o n n e c t 进行了统计分析，如表1 一l ，可见： b i t - t o r r e n t 在各地的使用比例都相当大，最多的澳大利亚已达7 3 ，接下来的德 国和东欧也都分别有6 7 、6 6 ：南欧的b i t t o r r e n t 虽然最少，只有4 1 ，但 e d o n k e y 比例却是最高的，达5 7 ，也是唯一过半的；东欧则是另一个很有趣的地 方，e d o n k e y 比例仅仅可怜的3 ，d i r e c t - c o n n e c t 却有2 9 ，而在其他地方几乎找不 到该项协议。 表格1 1p 2 p 协议的分布 诛p r o 。b i t - t o t r e n t e - d o n k e y d i r e c t c o n n e c tg f l u t e l l o o t h e r g e r m a n y 6 7 2 9 4 e a s t e r ne u r o p e 6 6 3 2 9 2 s o u t h e r ne u r o p e4 0 5 7 2 1 m i d d l ee a s t 5 6 3 9 3 2 a u s t r a l i a7 3 1 4 9 4 向大规模的用户群提供高质量、可交互的流媒体服务一直都被认为是当今i n t e r n e t 上的“杀手级”应用之一。传统的c l i e n t s e r v e r 架构的流媒体服务远远不能满足大量并 发用户对高质量流媒体服务的需求。上世纪8 0 年代，以微软的t i g e rs h a r k 流媒体集群 文件系统和美国南加州大学的y i m a 集群视频服务系统为代表的技术希望通过集群技术 来提高流媒体服务系统中s e r v e r 端的服务能力。然而，由于流媒体服务中高带宽、高 实时性的需求，使得这类系统在服务能力上仍然只能停留在同时服务并发上千人的规 模之上。 在面对如此巨大的网络负荷挑战时，有两种思想在学术研究届得到了广泛的认 同。其一就是通过i p 层的组播技术和客户端流合并技术来提高系统的并发服务量。然 而，由于i p 层组播在可靠性、安全性等方面存在的缺陷，现有的i n t e m e t 缺乏对i p 层 组播技术的支持，使得这种技术在产业界没有得到有效的实现。其二是同过高性能的 中心服务器和靠近用户的边缘代理服务器来组建多媒体c d n 网络( c o m e n td i s t r i b u t i o n n e t w o r k ) 的方式为大规模的用户提供高质量的流媒体服务。然而，极其昂贵的c d n 造价使得大多数的流媒体服务商望而却步，另外尽管相对于单机服务的模式相比，它 的规模理论上是可扩大的，性价比也更高，但是在地域上难以分布。 2 南京邮电大学硕士研究生学位论文 第一章绪论 1 2a l m 与i p 组播 1 2 1i p 组播 早在1 9 8 8 年，d e e r i n g 提出了将组播的功能机制增加到数据网i p 层的组播实现体 系结构，这种体系结构称为i p 组播( i pm u l t i c a s t ) 。i e t fr f c l l l 2 对i p 组播的业务提 供的方式和形式进行了描述和定义，被看成是i p 组播的标准业务模型的定义。 标准i p 组播业务模型定义了主机和路由器i p 层应有的功能机制和上层所看到的组 播业务的形式。主机组( h o s tg r o u p ) 是i p 组播概念的核心，多个主机组成主机组，用 一个i p 组播地址标识，以组地址为目的地址的组播数据以i p 数据报的b e s t - e f f o r t 方式 转发到主机组的各个主机。组播路由器承担组播数据的寻路和转发控制功能，这些路 由器及链路在网络中形成了一个控制组播数据传送的逻辑结构，称为组播转发结构 ( d e l i v e r ys t r u c t u r e ) ，这种结构一般是树形的结构，称为转发树，在转发树上的组播路 由器接收、复制、转发组播数据。 历经2 0 多年的研究和发展，i p 组播已经形成了较为完整的组播协议体系，包括组 播主机和网络的交互协议、组播路由协议、组播的地址管理协议等。i p 组播是对互联 网的“单播、尽力发送 模型的重要扩充，组播的主要功能在路由器上实现，通过合并 重复信息传输来减少带宽浪费和降低服务器的负担。从因特网发展的过程和口网络的 体系结构看，阻碍i p 组播业务发展的主要因素为f 1 】【2 】f 3 】1 4 】f 5 】： ( 1 ) i p 组播体系结构缺乏可扩展性 路由器需要为每个活动的组维护路由状态信息，而且这些组播地址不能聚合，网络 中大量的活动组将需要路由器巨大的存储和处理开销。此外，组播组成员的动态使网络 必须动态维护路由状态，更增加了组播路由器的处理开销。 ( 2 ) 开放的i p 组播模型难以支持有效的管理和控制机制 在开放的因特网环境中，标准的d 组播业务模型是一种a n ys o u r c e 、a n yr e c e i v e r 的开放模型，任何节点都可以创建组，可以向组发送数据，节点可以加入任何感兴趣的 组接收数据，发送节点不知道具体的单个接收节点，接收节点也不需要知道发送数据的 节点。在这种模型下，接入控制、组管理、组地址的协调机制一直没有有效的解决方案。 ( 3 ) i p 组播还没有清晰的商业费用模型，网络运营商之间有不同的利益取向 目前骨干网运营商以带宽使用获得收益，对承载的是口单播业务还是i p 组播业务 3 南京邮电大学硕士研究生学位论文第章绪论 没有必要区分，也就没有动力在路由器中增加对i p 组播的支持。 综上，由于i p 组播在传输技术和管理上存在的很多问题，目前没有在互联网中普 遍采用。 l ，2 2 应用层组播 面对i p 组播业务在因特网中的困境，一些研究者开始反思i p 组播体系结构本身的 问题，继i p 组播提出大概1 0 年后，提出将复杂的组播功能放在端系统实现的新思想。 端系统实现组播业务的思想是将组播作为一种叠加的业务，并将之实现为应用层的服 务，因此，端系统组播又称为应用层组播( a p p l i c a t i o n 1 a y e rm u l t i c a s t ) 。应用层组播是 指组播功能是实现在终端主机的应用层而不是网络层路由器上。 a l m 的主要思想为使各项应用自我组织到到一个逻辑覆盖网络，通过该网络进行 点到点的单播传输。相比于i p 组播，a l m 显然在效率上低一些，但a l m 更加容易部 署： ( 1 ) 不需要网络层的组播支持，比如支持组播的路由器； ( 2 ) 也不需要一个全局的认证号( 比如i p 地址) ： ( 3 ) 由于a l m 传输时为点对点单播，单播的优点( 诸如流量控制，拥塞控制， 信任传输) 都可以在a l m 中研究并利用。 但另外一方面，a l m 自有其自身的一些缺陷，由于数据在终端之间传输，端与端 之间的延迟将会较大，转发速率小：再诸如，端系统对i p 网络的了解有限，节点参与 组网时，只能通过探测获得一些网络性能参数，选取的逻辑链路难以优化；主机不了 解i p 网络的拓扑结构，只能通过带宽和时延等外在的特性参数，以启发式的方式建立 叠加网，逻辑链路不能较好地利用质量较好的底层网络资源，叠加网的多条链路可能 经过同一条物理链路，当覆盖层的多条边映射到一条相同的网络层链路时，则会导致相 同数据的多个拷贝在同一条链路传输，致使带宽使用率降低。所以，在与网络层比较 时，端对端的延迟和带宽的利用是两个比较重要的衡量标准。 1 3 本文结构 本文共分为五大章，第一章即本章为绪论，着重介绍了应用层组播提出的研究背景， 应用层组播及其相关的诸如i p 组播等相关概念的阐述，接下来几章的内容重点如下： 4 南京邮电大学硕士研究生学位论文 第一章绪论 第二章将主要通过历史上出现的国内外著名的涉及a l m 概念的协议介绍，及其现 状： 第三章将引入本文重点提出一个全新的模型c d m p ( 基于优先级的动态分层应用层 组播协议) ，通过介绍它的相关理念，借着详细阐述的该模型的各个层的性能特点以及 分层的原理，对节点的加入、退出，以及之后的整个模型维护并调整都进行了细节的介 绍。 第四章为仿真部分，对仿真时用到的指标，相关的定义，以及仿真的环境都进行详 细的介绍，最后的仿真的结果进行了演示并加以分析说明。 第五章为最后一章结束语，章中对本模型提供了综合性的说明，并对照当今网络的 现状以及国内外研究的情况，进行了相关的比较和展望。 南京邮电大学硕士研究生学位论文 第二章国内外研究历史以及现状 第二章国内外研究历史以及现状 数据共享一直是网络的一个目的，故数据传输一直是优化网络应用的热门技术，随 着网络应用的越发广泛，数据传输方式已不满足于简单的一对一的方式，而更多的开始 使用一对多甚至多对多的方式，即所谓的群发。组播是支持数据群发的个极好的方式， 并且随着i p 组播的黯淡，应用层组播声势越来越浩大，截止目前，许多a l m 系统已经 被开发，有相当一部分进入了实际使用并取得广泛的使用，例如本文第一章中i p o q u e 公司统计中提到的b i t t o r r e n t ，e d o n k e y , 再如直播，由于其特点是一对多，正好是组播 的优势，这使得比如奥运会、世界杯这样的实时热点节目可以最大范围以及最大畅通度 的供应在互联网上。 本章先简单介绍数据群发的方式，接着引进a l m ，并且根据各个著名的代表性a l m 协议出现的顺序以及与商业化运作结合的程度以及体现的作用，我们可以大体上将之分 为几个时期。 2 1 数据群发方式 数据群发是指将同一数据发送到多个接收终端，目前的数据群发主要有以下三种方 式： ( 1 ) 单播方式 所谓单播通信是指一份数据只能有一个接受方，这就意味着数据提供方收到一份请 求，就需要发送一份数据，而不管请求的数据是否相同。基于传统单播传输模式的c s 架构是最简单的单播通信方式。如图2 1 所示服务器向每个节点发送一份数据，这种单 播模式在消耗巨大而昂贵的服务器资源的同时，客户端却依然难以获得令人满意的服务 质量。原因在于c s 架构完全依赖于服务器的性能( 包括带宽和计算能力) ，其性能瓶颈 是难以克服的固有症结。当一台主机服务器同时只给少量的接收者提供服务，则客户端 的服务质量能得到有效的保证。但如果有大量客户端主机向服务器提出需求时，将导致 服务器主机网络负载沉重导致出口堵塞的情况出现。与此同时对于服务器、客户端之间 的网络链路，会引发网络延迟增大、拥塞等诸多问题，为保证一定的服务质量需增加硬 件和带宽。 6 南京邮电大学硕士研究生学位论文 第二章国内外研究历史以及现状 接收者1 接收者2接收者3接收者4接收者5 1 6 图2 i 单播方式实现群发 ( 2 ) 广播方式 数据群发的另一种实现方式是广播。如图2 2 所示，源主机向同一网段中的所有主 机发送广播包。广播包目的地址中的主机地址部分根据使用的不同网络层协议进行设 置。 网络中的主机都能识别出广播地址作为目标地址的数据包，一个子网中的所有主机 都接收地址为本子网广播地址的数据包。除非特别配置，路由器一般不会转发广播信息 包，否则可能造成路由环路将引起广播风暴。广播通信方式一般出现在本地的子网内。 在广播通信方式中，源主机只需发送一份数据包，交换机负责复制和转发。通过发 送广播数据包实现多点传送的办法虽然最简单，但是这将强制子网内所有计算机接收该 数据包，终端主机只有决定是否处理的权力，而没有决定是否接受的权力。采用这种方 式发送数据包不仅占用了不需要此数据包的主机处理时间，而且也造成了局域网带宽的 浪费，易诱发网络拥塞。而且对于跨网段的主机之间无法相互发送广播包。 j- f 7 八 _ i i ii j 愈哦感血愈 接收者接收者数据源 接收者 接收者 图2 - 2 广播方式实现群发 7 南京邮电大学硕士研究生学位论文第二章国内外研究历史以及现状 ( 3 ) 组播方式 组播是介于单播和广播通信之间的一种数据传送方式。组播的特点是能够在网络上 提供单点到多点( o n e - t o m a n y ) 通信以及多点到多点( m a n y - t o - m a n y ) 通信。相对于单 播、广播来说，组播可以更有效地利用网络带宽、降低网络流量、提高数据传输效率。 目前的组播技术主要分为两种：一种是在网络层实现的，即传统的i p 组播；另一 种是在应用层实现的，即应用层组播。 7 6 接收者1接收者2接收者3接收者4接收者5 图2 - 3 组播方式实现群发 目前网络发展的总体趋势是：网络业务多层次实现，骨干网业务简单高速。核心网 只提供单一的口单播业务，而其它在网络核心中难以实现的功能迁移到网络的边缘或 者网络端系统，是保持i p 网络核心简单高效的根本。叠加网层将成为未来网络体系结 构中一个重要的业务实现层次，而将来的网络也将有可能通过提供某些基本的业务，比 如向上层提供组成逻辑链路的物理链路信息或者网络的拓扑信息，专门支持叠加网业务 的实现。随着应用层组播研究的深入，最终将通过叠加网层实现_ 个功能强大的，支持 多种组播应用的组播业务。 2 2a l m 与商业运作结合的历史 a l m 作为i p 组播的一个替代，本身有其不可取代的优势，另外也得力于它有成熟 的商业应用模型。本文将之分为四个时期，分别阐述如下： 8 南京邮电大学硕士研究生学位论文第二章国内外研究历史以及现状 2 2 1a l m 萌芽时期 上世纪9 0 年代末期，正当流媒体服务技术的发展举步维艰时。桌面p c 、多媒体p d a 以及i n t e r n e t 底层技术却得到了飞速的发展。在此基础之上，一项利用终端桌面p c 计 算能力以及终端带宽在用户之间进行文件共享的新技术一e e r t op e e r 技术悄然而生。 1 9 9 8 年，美国学者在i e e em u l t i m e d i a 杂志上发表了第一篇关于利用p e e r - t o p e e r 技术 来实现大规模流媒体点播和直播系统的论文w e b c a s t 。w e b c a s t 的想法虽然很简单( 仅 仅只利用一棵二叉组播树在用户之间进行实时多媒体数据的传输和共享) ，但其高度可 扩展性和可行性给工业界和学术届的研究带来了极大的冲击。 n a p s t e r 系统率先利用该技术在音乐共享方面席卷全球。这是一个在线音乐共享服 务，由还就读于在b o s t o n 的n o r t h e a s t e r nu n i v e r s i t y 的s h a w nf a n n i n g 开发并提供。由 于版权问题并且n a p s t e r 对非法行为一直采取包庇，终于激起数家主要唱片公司的忿怒， 他们联合起来于1 9 9 9 年1 2 月递交了对该共享服务的诉讼。尽管诉讼的目的是要关闭 n a p s t e r ，然而随着审讯的深入，该服务却愈加流行，审讯反而成了对该服务最好的推广 和宣传。不久吸弓1 了上百万的用户，其中大部分为学生，在2 0 0 1 的二月是n a p s t e r 使用 流量的顶峰。这是个备受争议的协议，反对者以c a r l s o n 为代表的发表文章n a p s t e rw a s n o t h i n gc o m p a r e dw i t ht h i sy e a r sb a n d w i d t hp r o b l e m s 【6 1 。虽然版权纠纷最终还是使得 n a p s t e r 关门大吉，然而其底层的p e e r t op e e r 技术却给众多的应用领域带来了强烈的冲 击。 2 2 2a l m 起步时期 2 0 0 0 年，美国c m u 大学的华人科学家张辉带领的团队率先实现了第一套p 2 p 视频 直播系统的原型e s m 7 1 ( e n ds y s t e mm u l t i c a s t ) ，并且使用该原型系统向全球学者直播 当年的a c m 学术盛会s i g c o m 。该系统利用了在用户网状结构互连的基础上面构造最 优媒体数据组播树的方法来在用户之间传播实时的多媒体内容。 2 0 0 1 年，通过在因特网中实际运行基于e s m 的视频会议，验证了e s m 采用的自组 织协议可以在动态的、异构的因特网中支持较小规模的视频应用。虽然该系统中重量级 的网状系统维护协议和最优组播树构建算法使得这套系统仅仅只能扩展到几千人同时 在线的服务能力，但是这套系统的出现却标志着p 2 p 流媒体直播系统进入了系统实现 9 南京邮电大学硕士研究生学位论文第二章国内外研究历史以及现状 期。由于e s m 在学术界的极度成功，基于p 2 p 思想的应用层组播技术的流媒体直播服 务在产业界的研究院和各个大学研究机构得到了更加广泛的研究。 n a r a d a 8 l 是e s m 的组网协议。n a r a d a 协议首先在组播成员之间建立一个网状的叠加 网，然后在叠加网上运行组播路由协议，建立一棵组播转发树。通过动态探测网络状态， n a r a d a 动态地对叠加网进行维护和改良。该协议的第一步是建立连通子图，它是建立 在完全连通图的基础之上( c o m p l e t ev i r t u a lg r a p h ) 。第二步是采用最短路径树算法在连 通子图上建组播树。n a r a d a 建树过程中采用了距离矢量路由算法( d i s t a n c ev e c t o r r o u t i n g ) 。每一组成员都记录了本节点到别的节点的最短路径。 2 2 3a l m 兴盛时期 在2 0 0 0 年到2 0 0 3 年期间，各种原型系统、高度可扩展的应用层组播协议铺天盖地， 席卷而来。其中s t a n d f o r d 大学的p e e r c a s t 和德国学者开发的p 2 p r a d i o 系统是开放源代 码原型系统中的典型代表。而以微软研究院的c o o p n e t s p l i t s t r e a r n t 9 1 协；$ ( 、c i s c o 研究院 的o v e r c a s t 1 0 】协议、马里兰大学的n i c e t l l l 协议、伯克利大学的g o s s i p 协议等是p 2 p 直 播系统中应用层组播协议的代表。 其中，o v e r c a s t 被设计用于单源组播，一个o v e r c a s t 覆盖网络由一个源服务器( 为 了应付可能出现的故障一般会有备份) 、任意数目分布在因特网上的o v e r c a s t 中间节点 和标准的h t t p 客户端构成。o v e r c a s t 使用一个简单的建树协议( t r e e b u i l d i n gp r o t o c 0 1 ) 将中间节点组织成一棵转发树，使用一种叫做“上下行协议 ( u p d o w n p r o t o c 0 1 ) 的协 议来有效地维护o v e r c a s t 网络的全局状态。 n i c e 协议是一种可扩展的应用层组播协议，支持带有大量接收者的低带宽数据流 应用。它的优点在于根据建立的覆盖( o v e d a y ) 网络来隐性的确定组播树，这样在覆盖 网络的顶部就不需要额外的路由算法。n i c e 协议中有两种路径：一种是控制路径，一 种是数据传输路径。为了使得控制信息更快更好的在控制路径上汇聚且不产生比较高的 开销，n i c e 协议采用了一种连通性比较高的控制路径结构团集，而组播数据分发 的传播路径要求是无环的，因此选用树作为数据传输路径。n i c e 协议中的数据路径是 由控制路径隐性决定的，给定一个源就唯一地决定了一组组播路径。所以，用源树作为 n i c e 组播树的结构。也就是说，在控制路径上决定了一个分发数据的源点，也就决定 了一棵做为组播树的源树。 1 0 南京邮电大学硕士研究生学位论文第二章国内外研究历史以及现状 而g o s s i p 协议，又称r u m o rm o n g e f i n g 协议，因为消息在网络中的传播与流行病在 易感人群中传播的方式相似，传播的下跳是随机的，故又称流行病协议 ( e p i d e m i o l o g i c a lp r o t o c 0 1 ) 。 虽然，这些系统和协议在实用过程中存在一些缺陷，但是原型系统的实用以及基础 协议研究工作的开展为p 2 p 直播技术进入商业领域运作打下了坚实的理论基础。与此同 时，应用层组播协议在文件共享领域和数据存储领域也得到了广泛的应用。 2 2 4a l m 商业运作时期 2 0 0 4 年5 月欧洲杯期间，香港科技大学张欣研开发的c 0 0 1 s t r e a m i n g 原型系统在 p l a n e t 上进行试用，这是一种互联网上实现的没有规模限制的并有质量保证的i p t v ， 可以实时地收看和收听世界各地各个电视台的直播节目。这套系统使用g o o s i p 协议在 用户之间传播控制信令，使用类似于b t 的多点对多点数据传播协议在用户之间传送媒 体数据包。g o o s i p 协议的高度可扩展性、多点对多点数据传输协议的高度稳定性、以 及与当今i n t e m e t 底层构架异构性的高度适应使得用户的使用体验得到了质的飞跃。 传统和普通的i p l v 随着用户数量的增长，系统设备需要扩充，随之带来投资增大 的问题。而c 0 0 1 s t r e a m i n g 利用a l m 技术，大大降低大规模流媒体直播的服务器压力， 用户可以通过互联网收看听我们与世界各地电视台的直播节目而不受收看人数规模的 限制。实际上，同时收看某一节目的在线人数越多，收视效果越好。并且由于频道列表 是实时从服务器上获得的，时看时新，彻底从集中控制的节目表中解放出来。另外也由 于数据缓存在内存里，而不是不在硬盘，故对硬盘不会造成任何伤害。这套系统在2 0 0 4 年底得到了广大用户的普遍认同。c 0 0 1 s t r e a m i n g 系统是第一个真正将高可扩展和高可 靠性的网状组播协议应用在p 2 p 直播系统当中，真正实现了互联网上任意规模电视电 台直播的能力。 至此，p 2 p 直播技术进入准商业运作阶段，后期出现的p p l i v e 、p p s t r e a m 等也大多 都沿用了c 0 0 1 s t r e a m i n g 的网状组播模式。 2 3a l m 的相关协议 应用层组播协议不仅要提供有效的数据组播转发树，还要针对节点的动态性提供可 靠的组管理算法。协议设计强调在动态网络环境下维持网络的稳定性。应用层组播路由 南京邮电大学硕士研究生学位论文第二章国内外研究历史以及现状 协议设计面临的主要问题是如何在广域环境下针对节点的动态性在节点上建立必要的 状态信息，并根据这些信息构建和维护优化的组播路由协议。目前出现了多种应用层组 播协议，根据算法设计可以分为以下几类： 2 3 1 小规模的多源组播方案 代表是e n ds y s t e mm u l t i c a s t 7 1 和a l m i f l 2 】，针对小规模、多数据源的情况，典型应 用是视频会议系统。e n ds y s t e mm u l t i c a s t 的方案是：首先将组播组的成员组织成一个 “网( m e s h ) ，每个成员都维护所有组成员的列表，提高了组播组的可靠性；在m e s h 上 以每个数据源为根各构造一个生成树( s p a n n i n gt r e e ) ，这样可针对每个数据源进行性能 优化。其缺点是系统开销比较大，降低了系统的可扩展性，适合小规模组播组的情况。 a l m i 在组播成员之间维护一个“最小生成树 ( m s t ：m i n i m u ms p a n n i n gt r e e ) ，减小 了维护开销，但从每个源出发传输开销无法单独优化。生成树的维护开销限制了组播组 的规模。 2 3 2 大规模的单源组播方案 代表是n i c e 1 1 1 和z i g z a g 1 3 1 ，它们解决在只有一个数据源时构造大规模组播树的问 题，都使用了“分层 ( h i e r a r c h i c a l ) 和“分群 ( c l u s t e r ) 的思路。大部分组成员位于 分层结构的底层，只和少量固定数目的节点存在联系，这样就降低了大部分组播成员的 处理开销。它们的不同是：n i c e 把c l u s t e r 管理和数据分发这两个功能放在一个节点 上；而在z i g z a g 中是由不同节点完成的，目的是提高系统的可靠性。 2 3 3 基于多树的方案 代表是c o o p n e t t l 4 1 。它假设网络带宽比较充足，而组播节点的稳定性不能保证。主 要思路是：在组成员之间同时维护多个组播树；利用m d c 算法把媒体编码成n 个媒体 流，沿多个组播树传播；组成员收到n 个媒体流中的任何m ( m n ) 个就可完成解码。 算法的问题是：维护多个组播树开销较大；在“多路同时传送 机制下，数据的同步是 一个难点；m d c 编码和单路编码相比效率较低，对网络带宽的浪费较大。 1 2 南京邮电大学硕士研究生学位论文 第二章国内外研究历史以及现状 2 3 4 应用层网关的方案 代表是s c a t t e r c a s t 1 5 1 和o v e r c a s t 1 0 1 。主要思路是：在网络中部署一些专用服务器， 在应用层构造一个实现组播转发功能的特殊网络。这和完全基于用户主机的方案相比具 有更高的稳定性；但使用专用的服务器降低了灵活性。 2 3 5 应用层组播和i p 组播结合的方案 代表是y o i d 1 q 和h o s tm u l t i c a s t t l 7 1 。主要思想是在局部、小规模、支持i p 组播的 网络中使用i p 组播，而在i p 组播构成的“小岛 或没有i p 组播支持的主机之间使用 应用层方式连接。它是一种混合方案，不受网络条件的限制，而且可以充分利用i p 组 播的优点。 2 3 6 利用拓扑信息的方案 代表是t a g 1 引。它把组播节点之间的拓扑信息用于组播树构造，减少报文的转发 延迟和在同一链路上重复传递的报文数。拓扑测量时它将延迟作为最重要的指标，也考 虑带宽。构造组播树时它使新加入的节点和父节点能够共用尽可能长的网络路径。t a g 使用拓扑信息获得性能提高，但它破坏了网络的分层结构；拓扑测量和网络性能测量还 需要研列1 9 1 。 2 4a l m 的相关概念 2 4 1 覆盖网( o v e r l a yn e t w o r k ) 经过几十年的发展i n t e m e t 无论在学术还是商业上都取得了巨大的成功，i n t e r n e t 的体系结构也日趋成熟和完善。但新标准跟已有标准兼容的压力以及商业利益限制导致 了i n t e m e t 在智能和基础结构方面的僵化，研究人员很难向低层网络引入新的能力。另 一方面，在网络层次式的体系结构中，应用层位于该体系结构的最高层。应用层协议通 过传输层协议提供的服务完成相应的功能。但在网络技术日新月异的今天，相对稳定的 传输层协议所提供的服务已经不能满足迅速膨胀的应用需求。 1 3 南京邮电人学硕士研究生学位论文第二章国内外研究历史以及现状 在网络发展处于两难的形势下，覆盖网络( o v e r l a yn e t w o r k ) 技术为网络研究的指出 了个方向，即在原来i n t e r n e t 单播路由转发的网络架构基础上，在服务器或主机之间 构造一个应用层的网络来支持新的功能。如图2 4 所示为覆盖网协议位于t c p i p 协议 栈中的位置。 图2 4 覆盖网协议位于协议栈中的位置 覆盖网络是在物理网络之上实现的逻辑网络。应用层覆盖网络中的每个节点在对应 基础网络中的端系统主机或服务器。与路由器不同，端系统在网络层没有分组转发能力， 它们在应用层以特有的方式处理和转发分组。连接覆盖网络节点的链路被实现为通过基 础网络的隧道。在同一基础网络的顶上可以存在着多个覆盖网络，每一个都有它们自己 的特有行为。 覆盖网络屏蔽下层网络的拓扑结构，构造一个全互连的覆盖网络拓扑。与实际网络 中h o pt oh o p 的物理链路不同，覆盖网络中的链路是端到端的逻辑链路。这些逻辑链 路同样有其性能指标，如延迟、误码率、带宽等。 在覆盖网络中，底层网络只提供基本的数据通路，数据的分割、重组、寻址、路由、 转发、可靠性及有序性保证都上移到端系统实现。当需要向网络中添加删除的某一项 功能时只需要在端系统安装卸载相应的软件，不需要底层路由器的变更，更无须国际 标准化机构制定相应的标准，各个应用独立运行，没有兼容性的问题。 但覆盖网络也有其不足之处。根据网络层次式的体系结构，上层协议无法获得下层 网络的拓扑和性能参数，这给在覆盖网络上构造数据传递路径带来了巨大的困难。即使 覆盖网络中的节点能够完全获得底层网络的拓扑和链路性能参量，但由于端系统和其临 1 4 南京邮电大学硕士研究生学位论文第二章国内外研究历史以及现状 界的路由器之间的迂回转发不可避免，覆盖网络的效率不如底层网络。 图2 - 5 位于物理网络上的覆盖网络 如图2 5 所示为覆盖网的概念示意图，基础网络中的八个节点中的两个子集通过彼 此之间的单播连接，形成了具有星型拓扑和环型拓扑的两个虚拟覆盖网。覆盖网的概念 提出很早，因特网也可以认为是一种建立在各类局域网上的覆盖网。 2 4 2 覆盖网络的的维护和优化算法 一方面由于组成员的动态加入和退出和网络拓扑结构和链路状态的变化都可能导 致覆盖网络的割裂和性能的下降；另一方面受组成员加入策略的限制和加入时机的影 响，初始建立的覆盖网络结构不一定是最优的，因此覆盖网络的拓扑结构需要实时的维 护和动态的更新，以反映最新的网络状况，现在研究的应用层组播协议中，多强调它的 可维护性和可衡量性，比如【2 引。应用层组播协议一般周期性的通过发送保持( k e e p a l i v e ) 消息向邻居节点报告自身的活动状态或通过探针( p r o b e ) 消息探测其它节点的链路状 态并检测失效的节点( 如果需要还可能将链路状态信息提交通告相应节点处理) ，在 获得全局或局部链路信息的基础上节点执行既定的拓扑优化算法，寻找新的邻居节点。 在网络从旧的拓扑结构向新的拓扑结构转化的瞬间可能造成覆盖网络传输信息的 丢失，因此进行覆盖网络拓扑结构优化需要在网络的稳定性和传输效率之间进行折中。 当拓扑结构改变带来的利益不足以抵消转变过程中付出的代价时不进行拓扑的调整。