（计算机应用技术专业论文）非累积分层组播的拥塞控制改进.pdf

摘要 组播是因特网的新型网络应用，利用组播传输多媒体数据可以节约大量的带 宽，而分层组播是异构网络环境下组播通信的有效手段。传统的分层组播对数据 的分层都是累积型的，即要求接收者必须先接收基本层数据，再从低到高依次接 收增强层数据，才能解码出原始数据，不能实现细粒度的速率调整。本文提出了 一种对数据流采用非累积分层的策略，非累积分层采用卿e g 4 编码来实现，按 照指数序列对各层分配速率。首先，基于接收方调整速率的拥塞控制算法将实时 传输控制协议进行扩展，扩展后的协议可支持接收方计算与发送方之间链路的往 返延迟；其次，接收方将此延迟结合当前丢包率和平均包长度，计算出对传输控 制协议友好的接收速率；第三，再根据此速率对目前加入组播层情况进行调整， 使目前的友好接收速率与加入的组播层速率总和最接近，从而充分利用接收端的 带宽；最后，用网络仿真软件n s - 2 对该算法进行了仿真实验，结果表明该算法 可使异构链路接收者的带宽被充分利用。 关键词：组播分层组播拥塞控制非累积分层 a b s t r a c t m u l t i c a s ti san e wn e t w o r ka p p l i c a t i o ni ni n t e r n e t ，i tc a ns a v em u c h o ft h eb a n d w i d t h ，s oi ti su s e dt ot r a n s m i tm u l t i m e d i ad a t a ，a n dl a y e r e d m u l t i c a s ti sa ne f f i c i e n ta p p r o a c hi nm u l t i c a s tc o m m u n i c a t i o n h o w e v e r t h ec o n v e n t i o n a ll a y e r e dm u l t i c a s ti sc u m u l a t i v e ，i no r d e rt od e c o d et h e o r i g i n a ld a t as t r e a m ，h er e c e i v e rs h o u l dj o i nt h el a y e r sg r a d u a l l y ，a n d c a nn o tr e a l i z ef i n e g r a i n e dm u l t i c a s t am u l t i c a s tp o l i c yu s i n g n o n - c u m u l a t i v el a y e r i n gi sp r o p o s e di nt h i sa r t i c l e ，t h em u l t i c a s tp o l i c y u s i n gn o n - c u m u l a t i v el a y e r i n g i sr e a l i z e db y 艘e g 一4c o d e 。w eu s e e x p o n e n t i a ls e q u e n c et oa l l o tt h er a t ei nt h en o n c u m u l a t i v el a y e r s f i r s t ， ar e c e i v e r d r i v e nt c p - f r i e n d l yc o n g e s t i o na r i t h m e t i ch a sb e e np r o p o s e d a sw e l l t h ea r i t h m e t i ce x p a n dt h er t c pp r o t o c o l ( r e a l t i m et r a n s p o r t c o n t r o lp r o t o c 0 1 ) a n di tc a nm a k et h er e c e i v e rg e tt h er o u n d - t r i pt u n e o fl i n kb e t w e e nt h es e n d e ra n di t s e l f ；s e c o n d c a l c u l a t et h et c p - f r i e n d l y r e c e i v er a t e ，a n da d j u s tt h el a y e r si ts h o u l ds u b s c r i b ea c c o r d i n gt o r e c e i v e - r a t eo fi t s e l f t h u s ，t h er e c e i v e rc a na d j u s tt h er a t es l i g h t l y a n dm a k et h eb e t e ro ft h eb a n d w i d t h t h ea r i t h m e t i cw a sb e i n ge m u l a t e d i nn s - 2a tl a s t ，t h er e s u l ts h o wt h a tt h ea r i t h m e t i cc a nm a k et h eb e t e r o ft h eb a n d w i d t ha n ds c a l a b l e k e yw o r d s ：m u l t i c a s t ，l a y e r e dm u l t i c a s t ，c o n g e s t i o nc o n t r o l ， n o n c u m u l a t i v el a y e r i n g 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名：鱼拯 日期：迦! ：! 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：訇逸日期：丝e ! ： 身犯铭：鲺 兰州大学硕士学位毕业论文非累积分层组播的拥塞控制改进 1 1 组播产生的背景 第一章概论 随着计算机技术、通信技术以及因特网的迅速发展，人们对信息的获取不再 仅仅满足于文字或数据的单一形式，而是发展到对视频、图像、声音、文字等集 于一体的多媒体( m u l t i m e d i a ) “1 信息的积极追求。多媒体技术已经深入到人们的 学习、生活、娱乐等各个方面。尤其是因特网在全球范围内爆炸式的发展使得丰 富的信息资源变得“触网可及”，便捷的途径和丰富的资源使得多媒体业务网络 化的趋势不可阻挡。 由于图像和视频等多媒体文件的数据量较大，为了便于存储和传输，必须进 行压缩编码。1 9 4 8 年s h a n n o n 在他的经典论文“通信的数学原理”中首次提出并 建立了信息率失真函数的概念伽，奠定了信息编码的理论基础。此后图像视频 编码的理论和技术得到了很大的发展，人们陆续提出了交换编码、运动估值与补 偿、熵编码等压缩算法。 通常多媒体文件需要从网络服务器上下载之后才能播放。由于多媒体信息尤 其是视频信息的数据量一般都比较大，这不仅会导致较长的下载等待时间，也会 占用较多的存储空间。流媒体( s t r e a m i n gm e d i a ) 脚边下载边播放的特点很好的 解决了这个问题。它以流的形式进行数字媒体的传送，从而使得人们可以即时欣 赏到连续不断的多媒体节目。流媒体的典型应用包括视频点播( v i d e o - o n - d e m a n d ， v o d ) 、视频会议( v i d e oc o n f e r e n c e ) 系统、远程教育( d i s t a n c el e a r n i n g ) 系统 等。在视频会议、远程教育等应用中，相同的数字图像或语音等多媒体信息必须 同时送往多个目的地址，显然，点对点传输的单播方式不能适应多媒体业务传输 特性，因为在单播方式下服务器必须为每一个接收者提供一个相同内容的网际协 议i p ( i n t e r n e tp r o t o c 0 1 ) 报文拷贝，同时网络上也重复地传输相同内容的报文， 占用了大量资源。虽然i p 广播允许一个主机把一个i p 报文发送给同一个网络的所 有主机，但是由于不是所有的主机都需要这些报文，因而浪费了网络资源。此时 组播( m u l t i c a s t ) 应运而生，它的出现提供了一个主机向特定的多个接收者发送 消息的新方法。1 9 8 9 年，因特网工程任务组i g r f ( i n t e r n e te n g i n e e r i n gt a s l c f o r c e ) 通过其请求注解文件r f c ( r e q u e s tf o rc o m m e n t s ) ，即r f c ii1 2 ，它定义了 i n t e r n e t 上的组播方式。 组播是一种允许一个或多个发送者( 也称为组播源) 发送单一的数据包到多 个接收者的网络技术。组播源把数据包发送到特定组播组，只有属于该组播组 兰州大学硕士学位毕业论文非累积分层组播的拥塞控制改进 的地址才能接收到数据包。组播可以大大地节省网络带宽，因为无论有多少个目 标地址，在整个网络的任何一条链路上只传送单一的数据包。它提高了数据传送 效率，减少了主干网出现拥塞的可能性。组播组中的主机可以是在同一个物理网 络，但如果有组播路由器支持的话，主机也可以来自不同的物理网络。 组播、选播或多播( m u l t i c a s t ) 并不是一个很新的概念。在分布式系统中， 它是作为描述分布式进程之间的一种通信模式而提出来的。正如人与人之间的交 流方式一样，进程之间的通信可以按照参与通信的进程关系，分成一对一、一对 多和多对多三种模式。其中，一对一的方式也称为单播( u n i c a s t ) ，后两种模式 则称为组播。i p 组播改变了互联网上传统的一对一的数据传输方式，在组播方式 下，任何人都能够以平等的身份加入组播层，接收所有其他组播参与者发出的数 据，同时向所有组播参与者发送自己的数据。 组播是i n t e r n e t 的新型网络应用，利用组播传输机制进行多媒体数据的传输 非常适合那些需要某种协同关系的松散或耦合的网络分布式应用系统，如远程视 频会议、远程教学系统、大规模分布交互仿真、软件分发等等。1 9 9 2 年3 月，i e t f 小组成功地利用组播技术举行了一次网络会议。1 9 9 2 年7 月，i e t f 在i n t e r n e t 上 建立了的支持i p 组播的组播骨干网m b o n e ( m u l t i c a s tb o n e ) 。之后，m b o n e 作为 一种有效的网络多媒体传输基础设施在美国以及世界各地被广泛的使用，每年都 有各种会议、讨论、演出借助m b o n e 的支持而进行。 然而组播至今无法得到因特网服务提供商i s p ( i n t e r n e ts e r v i c ep r o v i d e r ) 的广泛应用，一个重要的原因在于组播没有提供合适的拥塞控制。近来，组播拥 塞控制得到了广泛的关注，它己成为互联网研究领域中的一个热点课题。 同时，分层组播( l a y e r e dm u l t i c a s t ) 啪啪是异构网络环境下组播通信的有 效手段。分层组播的数据发送方根据特定的编码算法对数据流( 视频、音频信息 或数据) 进行分层编码，并把得到的每一层数据编码用一个组播地址进行发送。 接收者则根据从发送方到其自身路径的可用带宽独立地决定所能接收的层次，从 而使得同一个组播会话的不同接收者可以以不同的速率接收数据。由此，分层组 播是解决网络拥塞控制的一个新的思路和方法，对分层组播的研究是当前网络界 一个非常活跃的领域，我们也相信分层组播在不久的将来会得到广泛的应用。 1 2 国内外研究现状 随着视频编码技术的提高和网络技术的发展以及计算机硬件水平的突飞猛 进，流媒体的广泛应用成为必然。针对i p 视频组播存在的一些问题，国内外近些 年展开了广泛的研究。概括来说，研究主要集中在两个方而：一是以端系统为中 心，主要是通过增加服务器和接收者的功能来实现多速率服务，不对网络提出要 求；二是以网络为中心，通过增加中间节点的功能来保障流传输的服务质量q o s 。 2 兰州大学硕士学位毕业论文非累积分层组播的拥塞控制改进 以端系统为中心是通过在服务器端增加码率适应的功能，通过监测网络传输 的反馈信息来调整编码参数、码率等产生合适的码流，满足用户的需求。由于没 有对现有的网络技术提出新的要求，因此比较容易实现。如文献e g i o 都是通 过监控视频传输的q o s 来反馈调整视频服务器中视频编码的参数等帧率编码参 数，并进行平滑处理，以此来提供适合网络传输的码率。另外一种解决办法是码 流切换，又称为联播( s i m u l c a s t ) ，即将一段视频内容编码成多个不同码率的压 缩视频流，然后将这几个视频流同时用相互独立的组播通道发送到网络，用户可 以根据自己的情况选择合适的流或者在不同的流之间进行切换。这些方法确实 能在一定程度上满足用户对多速率视频流服务的要求，但是又都存在着明显的缺 陷。前者对服务器的要求太高，而目也不适合用于多用户的业务，而后者在加重 服务器的负担、占用较多存储空间的同时，还占用了较多的带宽。 以网络为中心的方法则是要求网络中间节点如路由器、交换机等设备为媒体 流的传输提供带宽、延迟、抖动、丢失率等方面的服务质量的保证。而这种方法 又需要各种设备之间的协调，增加了网络的负担，尤其当用户数量增多时，路由 器负担过重。 1 3 小结 尽管拥塞控制已有了相当的发展，由于网络的规模扩大的速度很快，网络拥 塞仍然是一个十分严峻的问题。特殊的网络应用也需要不同的拥塞控制技术支 持，因而拥塞控制技术对于未来网络的设计、协议工程及网络应用均有着十分重 要的意义。 兰州大学硕士学位毕业论文非累积分层组播的拥塞控制改进 第二章组播拥塞控制技术简介 组播是一种为优化使用网络资源而产生的技术。组播克服了网络的冗余使 用，主要解决单点到多点、多点到多点的数据传输，依托i p 协议完成，强制在数 据传递树的分叉处( 路由器) 进行数据包复制，而不是由源端节点多次重复发送数 据拷贝。因此组播技术减轻了网络负担，充分利用了网络资源，内容发布、流媒 体、多用户游戏、多媒体多用户会话、远程教育等应用都能受益于组播技术。 2 1 i p 组播技术 i p 组播是网络多媒体研究和应用的热点技术。随着视频会议、可视电话、 v 0 d ( v i d e oo nd e m a n d ) 等应用的推广，音频和视频等流媒体逐渐成为网络数据传 输的主要类型。流媒体的传输对网络协议提出了一些新的要求，在这种背景下组 播技术被提出，用于解决流媒体多路传输的问题。 i p 组播也称“多播”或“多点传送”，是一种允许一个或多个发送者( 组播 源) 发送单一的数据包到多个接收者( 一次的，同时的) 的网络技术。组播源把 数据包发送到特定组播组，而只有属于该组播组的地址才能接收到数据包。组播 可以大大地节省网络带宽，因为无论有多少个目标地址，在整个网络的任何一条 链路上只传送单一的数据包。它提高了数据传送效率，减少了主干网出现拥塞的 可能性。组播组中的主机可以是在同一个物理网络，也可以来自不同的物理网络 ( 必须有组播路由器的支持) 。组播和单播在传输多媒体流时对网络的带宽占用 如图2 1 所示。 组播 图2 1 组播和单播对比图 要实现组播技术，其实也是一个很复杂的工程，它要求网络满足如下的前提 条件： 4 兰州大学硕士学位毕业论文非累积分层组播的拥塞控制改进 1 、要实现组播技术，主机的通信协议必须要支持发送和接收组播数据。 因为并不是所有的协议都支持组播通信，对w i n d o w s 3 2 平台而言，仅i p 和异 步传输模式删( a s y n c h r o n o u st r a n s f e rm o d e ) 两种通过w i n d o w s 套接字 ( w i n s o c k ) 内访问的协议才提供对组播通信的支持。组播通信具有两个层面的 重要特性：控制层和数据层。其中，控制层定义了组成员的组织方式，而数据层 决定了不同的成员之间数据的传送方式。各层面的特征也分为两种形式，种是 “有根的”，另一种是“无根的”。a t m 组播采用的是有根方式，而基于i p 网络 的系统一般采用无根方式，无根组播模型如图2 2 所示。 图2 2无根组播模型 2 、要实现组播技术，主机的网络接口( 如网卡) 必须支持组播。 某些型号较老的网卡不能使用i p 组播地址进行数据的发送和接收，因为网卡 对组播通信的支持通常以硬件形式即增加组播过滤器的方式来实现。由于组播i p 地址是一个比较特殊的介质访问控制m a c ( m e d i aa c c e s sc o n t r 0 1 ) 地址，它包 含了一个被编码的i p 地址，网卡的组播过滤器通过扫描m a c 地址便可以判断出进 入的数据包是否属于组播数据，并检查这个数据包的目标组播i p 地址是哪一个。 i p 组播在各种平台上的具体实现方式是不同的，在w i n d o w s 9 5 和w i n d o w s n t 4 上， 通过将网卡置为“混杂”模式来实现组播。在这种模式下，网卡会通过信号线取 得传来的所有数据包，再一起转交给网络驱动程序，由后者负责检查m a c 头的内 容，看看是否有组播数据发送给一个组播组，而且当前系统中有没有属于该组成 员的进程。所以，“混杂模式”实质上是一种软件( 驱动程序) 实现方式，效率 比较低。而在w i n d o w s 9 8 及w i n d o w s 2 0 0 0 等系统中，都是利用网卡自身的能力来实 现数据包的过滤，通过硬件的直接完成，可以获得更高的效率。 3 、要实现组播技术，必须有一套用于加入、退出、查询的组管理协议。 这就是i n t e r n e t 组管理协议i g 押( i n t e r n e tg r o u pm a n a g e m e n tp r o t o c 0 1 ) 。 i g m p 是i p 组播方案的基础，主机使用i g m p 消息通告本地的组播路由器想要接收数 据的组播组地址。如果主机支持i g m p v 2 ，它还可以通告组播路由器退出某组播组。 组播路由器通过i g m p 协议为其每个端口都建立并维护一张组播组成员表，i g m p 协议定期地探询表中的组成员，以确定该组播组是否仍存活。i g m p 消息通过i p 报文进行传送，在i g m p v 2 中，其报文格式如图2 3 所示。 兰州大学硕士学位毕业论文 非累积分层组播的拥塞控制改进 图2 3i g i j n 2 报文格式 4 、要实现组播技术，必须有一套i p 地址分派策略，并能将网络层组播i p 地 址映像到数据链路层的m a c 地址。 i p 组播地址，或称为主机组地址，由d 类i p 地址标记。d 类i p 地址的最高四位 为“1 1 1 0 ”，起止范围从2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 。其中，都分d 类地址被 保留，用作永久组的地址，这段地址扶2 2 4 0 0 o 到2 2 4 0 0 2 5 5 ，中间范围从 2 2 4 0 1 0 到2 3 8 2 5 5 2 5 5 2 5 5 用来在组、内部网和i n t e r n e t 的终端应用程序中使 用，从2 3 9 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 则指定给本地的组播应用程序。因此可由开 发人员自己从2 2 4 0 1 0 到2 3 8 2 5 5 2 5 5 2 5 5 中选择组播组地址。但一定要保证这 个地址在一定的范围内没有其他的组播组也在使用相同的地址。数据链路层的组 播地址( 组播m a c 地址) 可以从i p 组播地址中衍生。计算方法是把i p 地址的最后 2 3 位拷贝到网卡m a c 地址的最后2 3 位，然后把这2 3 位前面的那一位置为0 。组播m a c 地址的前2 4 位必须为o x o i - o o - 5 e 。例如；组播i p 地址2 2 4 0 1 1 2 8 ，1 6 进制表示 为o x e o - 0 0 - o i - 8 0 ，最低的2 3 位为o x 0 0 一o o 0 卜8 0 。计算得出的姒c 地址为 o x o l - o o - 5 e - 0 0 - 0 1 - 8 0 。 5 、要实现组播技术，必须使位于组播源和接收者之间的路由器、集线器、 交换机、t c p i p 栈、防火墙均需支持i g m p 协议。如果某个路由器不支持i c , m p ，那 么当它接收到组播数据时，就会自动丢弃。 只有在网络设备和操作系统平台上满足了以上五个条件，i p 组播才能够得以 实现，所幸的是现在绝大多数的网络设备都支持i g 咿协议和i p 组播，这就使得在 i n t e r n e t 上的组播应用成为可能，而且伴随着组播技术的应用推广，各种关于组 播的网络拥塞控制算法也得到了广泛的研究，如加权公平排队算法等。 然而与传统i p 相同，i p 组播不提供速率控制。因此组播流量可能耗光所有的 网络资源，导致网络拥塞。为i p 维播设计合适的拥塞控制成为最迫切需要解决的 问题。 e t e f 将组播分为两种模式：单点对多点、多点对多点。后者在组播树生成和 组管理等方面存在较大的难度，现阶段在i n t e r n e t 上推广的希望不大，而且它可 以通过多组单点对多点通信来实现。本文的讨论仅限于单点对多点模式。 组播应用在网络拥塞时，如果不能对其正确地进行响应，将会给i n t e r n e t 带来比单点投递应用更为严重的影响“”，这主要因为1 ) 一个组播流可能沿着其 组播树广泛分布于整个i n t e r n e t ：2 ) 异构性是i n t e r n e t 网络的固有特性：对 i n t e r n e t 网络本身而言，主干( b a n k b o n e ) 可以使用t l 和t 3 链路，接入网络则可 能采用高速a f m 网络、以太网或无线网络。同时，用户端系统日益多样化，不同 6 兰州大学硕士学位毕业论文非累积分层组播的拥塞控制改进 的端系统具有不同的处理能力和视频音频硬件配置。比如，无线手机的处理能 力显然不同于具有视频卡的高端工作站。随着未来越来越多不同种类的网络接入 i n t e r n e t ，i n t e r n e t 的规模不断扩大，异构性问题将更加严重。组播流的接收者 显然具有异构性特点“，每个接收者的路径可能有不同的带宽和差错特性，如图 2 4 所示。 图2 4i n t e r n e t 的异构性 为了把数据发送给所有接收者，在没有外界人为干涉的情况下，组播流可能 要持续无限制的时间；3 ) 组播流一般必须处理较多数量的反馈控制信息，如确 认报文、否定确认报文和状态报文。因此，随着越来越多的组播协议在i n t e r n e t 上得到应用，拥塞控制协议研究领域日趋活跃。 2 组播的基本问题和解决办法 2 2 1 可扩展性 在任何组播拥塞控制算法中一个关键的设计原则就是其可扩展性 ( s c a l a b i l i t y ) 。所谓可扩展性叫是指算法在性能开始下降前可以支持多少用户。 在拥塞控制中，可扩展性会直接受到以下两个方面的限制m “”： 1 、当组成员的数量越来越大时，拥塞控制任务也会越来越复杂。可以通过 在发送方和接收方之间进行协作分工的方式来解决此问题； 2 、流量调节算法的限制。从图2 5 中可以看出调节算法的公平性和拥塞预防 的能力，该算法需要依靠组中所有成员来确定。 兰州大学硕士学位毕业论文 非累积分层组播的拥塞控制改进 固2 5 端对端系统中组播拥塞控制的主要任务和设计方法 组播拥塞最核心的问题是可扩展性。在一个组播组中接收方数量往往很大， 而且还可能遍布于整个i n t e r n e t ，因此在发送方需要处理大量的反馈报文( 如确 认报文、否定报文或状态报文等) ，若不及时对这些报文进行正确处理，将会导 致两类经典问题：速率归零( r a t ed r o p - t o - z e r o ) 和反馈风暴( f e e d b a c k i m p l o s i o n ) 。 一般在组播拥塞控制时需要考虑所有组成员的拥塞状况，随着组规模地扩 大，来自接收方的大量反馈报文可能会湮没发送方，从而导致反馈风暴。对于反 馈风暴的问题，可以采用反馈抑制机制“町( f e e d b a c ks u p p r e s s i o n m e c h a n i s m ) 来解决 在当前网络中，通常将数据包的丢失作为网络拥塞的唯一信号。当网络拥塞 时，若发送方对每一个接收方的数据丢失做出响应的话，那么其发送速率可能下 降为零。对于速率归零的问题，可以采用反馈聚集机制“”( f e e d b a c k a g g r e g a t i o nm e c h a n i s m ) 来解决。 在实际网络中，组播一般表现为三种情况n 钔：独立型拥塞( i n d e p e n d e n t c o n g e s t i o n ) 、共享型拥塞( s h a r e dc o n g e s t i o n ) 和混合型拥塞( c o m b i n a t i o no f i n d e p e n d e n ta n ds h a r e dc o n g e s t i o n h y b r i dc o n g e s t i o n ) ，如图2 6 所示。图 中s 表示发送方，r 表示接收方，虚线表示发生拥塞的链路。 兰州大学磺士学位毕业论文非累积分层组播的拥塞控制改进 0 l ， 00 共事堑溺翕耋 图2 6 组播拥塞的类型 在独立型拥塞中，每个因拥塞而丢失报文的接收方将向发送方反馈不同的拥 塞信息，发送方会对每个拥塞信息做出响应，降低发送速率。当独立型拥塞较多 时，最终将导致发送速率归零。在共享型拥塞中，拥塞链路下游的每个接收方都 将向发送方反馈丢失信息，如果下游接收方数目较多时，此时将发生反馈风暴。 而在混合型拥塞中，以上两种现象均会发生。 2 2 2 公平性 组播应用的广泛开展，引起了非t c p 通信量所占比重的增加，这些协议大部 分没有与t c p 兼容的拥塞控制机制嘲，它们以一种不公平的方式与t c p 流竞争。当 遇到拥塞时，所有参与的t c p 流应该立即减小它们的速度试图减轻拥塞，而非t c p 流继续以原速发送，这种极度不公平的情形会遏铝u t c p 通信，甚至导致拥塞崩溃， 当网络中可利用的带宽被耗尽，所有的包在到达目的地之前将会因拥塞而被丢 弃。因而组播应用要想成功地在i n t e r n e t 上应用，必须使用能与t c p 友好共存的 组播拥塞控制机制，即保证t c p 的公平性。公平性研究是网络拥塞控制的难点问 题，目前，还缺少对公平性的一致定义。通常，组播拥塞控制算法至少要考虑两 类公平性：协议间公平性和组播组内部公平性，下面对这两个公平性分别阐述： 1 、协议间公平性 由于i n t e r n e t 上的主流协议为t c p 族协议，所以任何协议要在i n t e r n e t 上成 功应用必须做到“t c p 友好”嘲，也就是说其通信量不能超过网络中可利用的带 宽，而且要与现存的协议保持公平。 组播协议除了保证各种组播应用之间的公平性外，还应确保与其他行为良好 的协议公平分享网络资源。目前t c p 通信量占i n t e r n e t 通信的9 0 以上，因此组播 协议应该首先保证组播流量和t c p 流量之间公平地竞争资源。因此在制定组播拥 塞控制标准时，一般要求组播拥塞控制算法必须做至f j t c p 友好( t o p - f r i e n d l y ) 。 t c p 的吞吐量与下面的参数有关：往返时间t 盯”重传超时值t m ，分组大小s ， 9 ， 兰州大学硕士学位毕业论文 非累积分层组播的拥塞控制改进 丢失率p ，公式2 1 1 2 1 1 给出一个简化模型，近似模拟t c p 在稳定状态下的吞吐量。 该简化模型没有考虑t c p 超时。 公式2 2 蚴给出了一个更复杂的模型：b 是每个h c k 应答的分组数量，w 是拥 塞窗口的最大值，与公式2 1 不同，它考虑t t c p 超时。在高丢失率网络中，公式 2 2 更精确的模拟t t c p 的行为。 t ( t 哪，s ，p ) = 羔年c 是常量，通常取1 52 压7 3 ( 2 1 ) t 册p p ) = m i n i 旦( 2 2 ) 在组播传输用数据报协议u d p ( u s e rd a t ap r o t o c 0 1 ) 封装的数据流时，可 以根据这两个公式，将组播的t c p 友好性描述为：在给定同样的丢失率与往返时 间r t t ( r o u n d - t r i pt i m e ) 时，组播拥塞控制算法获得的吞吐量不超过，r c p 流的 吞吐量。 组播t o p - f r i e n d l y 的定义：组播t c p - f r i e n d l y 存在多种定义，一般认为非t c p 流量的长期吞吐量不超过相同情况下t c p 流量吞吐量，一种更加严格的对 t o p - f r i e n d l y 的定义脚如下： 1 ) 单播t c p - f r i e n d l y ：在相同网络条件下，如果一个单播流量对其它并存 t c p 流量的长期吞吐量的影响不大于另外一个t c p 流量对后者的影响，此单播流量 被认为是t c p f r i e n d l y ； 2 ) 组播t c p - f r i e n d l y ：在发送者与每个接收者之间，如果流量具有单播 t c p - f r i e n d l y 的特性，则此组播流量被认为是t c p f r i e n d l y 的。 对组播t c p - f r i e n d l y 的定义还存在争论，某些定义提出应该允许组播流量使 用比单播流量稍多的带宽，因为组播流量为多个接收者提供服务“”，引入式2 3 来定义组播的t c p 友好性： 口聊s rs d f t c p ( 2 3 ) 其中，r 表示瓶颈路上的组播流的速率，r t c p 表示相同情况下t c p 流的速率，a 和b 是流接收端数目的函数，当b = l 时，两种定义是相同的。 2 、组播组内部的公平性 组播是单点对多点的通信，在组播会话中存在多个接收者，组播组内部公平 性主要指一个拥塞的接收者不应该影响其他接收者的速度，即孤立拥塞的影响， 允许每个接收者根据各自到源端的路径上的拥塞情况来做出正确的判断。 兰州大学硕士学位毕业论文非累积分层组播的拥塞控制改进 目前在组播拥塞控制设计中常用的种公平性标准是s b h a t t a c h a r y y a 在文 献 1 4 中提出的最坏路径公平性，即根据组播树中最拥挤的端到端的路径来为整 个组播会话分配带宽。 如图2 7 所示，源组播数据s 到三个接收者，各条路径的带宽分别是b 、2 b 、 4 b ，其中从s 至i j r l 的路径是组播树中带宽最小的路径，假设有一个单播会话经过 这条路径，那么单播会话与组播会话将各被分配b 2 的带宽，同时在组播树的其 他几条路径上，组播会话也只占b 2 的带宽。其余带宽留给经过这几条链路的其 他会话使用。采用这种公平性设计的算法，组播会话的吞吐量容易受到某几个较 拥塞的接收者的影喻。 图2 7 组播带宽分配 另外，6 0 l e s t a n i a a d 还提出了面向速率的公平性与窗口的公平性m 1 ，文中指 出拥塞控制算法的公平特性主要由调节算法的形式所决定，同时也受到调节算法 的影响。根据调节参数的不同可以将拥塞控制机制分为：基于窗口的拥塞控制和 基于速率的拥塞控制。基于窗口或速率的拥塞控制算法对r t t 的依赖与它们的公 平属性密切相关。在基于速率( 基于窗口) 调节中，如果调节算法独立于r t t ， 它的公平性是面向速率( 面向窗口) 的。如在t c p 中r 竹仅用来设置定时器但调节 算法不依赖于r t t ，所以t c p 拥塞控制有面向窗口的公平性。如果要通过基于窗口 的调节提供面向速率的公平性，或通过基于速率的调节提供面向窗口的公平性， 调节算法又不得不依赖于r t t ，因此要通过基于速率的调节提供面向窗口的公平 性( 与t c p 兼容) ，必须知道r t t 。反之，通过采用与t c p 不同的公平性含义或应 用基于窗口的调节，r t t 的测量可以避免。由于在组播拥塞控制中r t t 是很困难的， 这会增加拥塞控制的复杂性，因而避免调节算法对r t t 的依赖是非常值得尝试的。 但是，必须强调t c p 公平性的主要方面在于它的吞吐量随丢失率的变化而变化。 如果我们选择提供面向速率的公平性，也同样可以保持与t c p 的兼容性。 2 2 3 异构性 异构性。”是指组播的接收方处理能力不同，而且报文到达不同接收方经历的 链路的网络特性( 如带宽、延迟等) 不同。更为重要的是，链路的异构性在组播会 话期间常常是动态变化的，这就更增加了拥塞控制的难度。为保证报文的可靠投 兰州大学硕士学位毕业论文非累积分层组插的拥塞控制改进 递，发送方需要及时地获取由每个接收者或其它网络设备的反馈信息，调整发送 速率、重传丢失报文。因此，组播拥塞控制往往选择最差接收方的发送速率来发 送报文，这在很大程度上浪费了网络资源，降低了组播通信的效率。 2 3 组播的分类 对于组播的分类根据不同的分类条件可以有多种分类结果，下面我们介绍几 种比较常见分类方法。 2 3 1 发送方驱动的组播拥塞控制和接收方驱动的组播拥塞控制 如果按照控制算法的驱动方式可以划分为以下两类： 1 、发送方驱动的组播拥塞控制“4 删( s e n d e r - d r i v e n m u l t i c a s t c o n g e s t i o nc o n t r 0 1 ) 这种方式与t c p 协议类似。拥塞算法放置在发送方，每个接收方按照一定的 时间周期向发送方发送反馈报文，发送方则从反馈报文中获取有关的信息，并以 此来调整发送速率。在这种方式中，发送方需接收并处理大量的反馈报文，极易 发生反馈风暴( f e e d b a c ke x p l o r e ) 。为解决此闯题，目前有一种采用基于代表 的方案“”来减少反馈报文的数目，但却需增加额外的网络设备或向现有网络设备 中添加复杂的归并算法，因此并不能从根本上解决伸缩性问题。 利用发送方驱动的组播拥塞算法，发送方能及时地了解整个组播组的状况， 并可以做出响应。但是在发送方需要处理大量的反馈报文，并且要进行大量的计 算，开销过大，容易造成网络瓶颈，可扩展性较差。 2 、接收方驱动的组播拥塞控制阻“”“删( r e c e i v e r d r i v e n m u l t i c a s t c o n g e s t i o nc o n t r 0 1 ) 在接收方驱动的组播拥塞控制中，数据被组织成不同的层次，发送到不同的 组播组。接收方根据当前网络情况订阅适当的层次。在这种方式中大量的计算任 务交由接收方完成，减轻了发送方的计算开销。 但是接收方驱动的组播方式中也存在不少缺陷阻“蜘：1 ) 在进行大数据传输 时，对数据不易自然分层，而且为了数据的一致性和有序性，分层难以实现；2 ) 由于编码和译码的复杂性，可用层次数较少，因此会限制拥塞的自适应范围；3 ) 当接收方加入和离开组播组时，会增加系统的开销，而且会过分依赖组播路由协 议；4 ) 大多数接收方驱动的协议中主要通过n a k s ( n e g a t i v ea c k n o w l e d g m e n t s ) 来确定网络拥塞程度，如果发送方没有收到反馈的n a k s ，则有可能错误地推断网 络无拥塞或拥塞己清除：5 ) 接收方驱动的协议中采用随机n a k 抑制技术，要求每 个接收者执行复杂度为o ( n 3 ) 的链路往返时间的计算开销，这在一定程度上限制 兰州大学硕士学位毕业论文 非累积分层组播的拥塞控制改进 了协议的伸缩性。 2 3 2 基于速率的组播拥塞控制和基于窗口的组播拥塞控制 如果按照拥塞控制参数来划分，组播可以划分为两类： 1 、基于速率的组播拥塞控制“”4 4 ”蚓( r a t eb a s e d m u l t i c a s t c o n g e s t i o nc o n t r 0 1 ) 根据网络的变化情况动态地调整传输速率，对网络中的拥塞进行控制的方法 称为基于速率的控制。这种方式不需要维护拥塞窗口，而且能保持发送速率平稳 变化，在单播或组播中的实现方法类似，可扩展性好。但是发送端也需要从接收 端收集控制参数，例如分组丢失率和环路延迟r t d ( r o u n dt r i pd e l a y ) ，如果不 提供适当的反馈抑制机制，发送端也将遭遇反馈爆炸问题。基于速率的算法在实 现t c pf r i e n d l y 时，需要获得r t d 信息，然而在组播环境中，对r t d 进行大规模 测量非常困难。为了实现协议间的公平性，通常有以下两种常用的方法： 1 ) 简单的a i 妨拥塞控制“”：这种方法模仿t c p 协议中的a i m d ( a d d i t i v e i n c r e a s ea n dm u l t i p l i c a t i v ed e c r e a s e ) 行为。这种方法实现起来虽然十分简 单，但速率在短期内易出现与t c p 相似的锯齿形； 2 ) 基于方程的拥塞控制( e q u a t i o n - b a s e dc o n g e s t i o nc o n t r 0 1 ) ：这种拥塞 控制方式的主要目的是在对拥塞有反应的前提下，保持平滑的速率变化。基于模 型的拥塞控制根据t c p 流量模型调整速率，因此可以产生非常平滑的速率，适用 于多媒体应用。基于模型的拥塞控制需要在拥塞反应速度和速率振荡之间做出权 衡。 2 、基于窗口的组播拥塞控制“巩删( w i n d o v - b a s e dm u l t i c a s tc o n g e s t i o n c o n t r 0 1 ) 这种方式与t c p 窗口机制类似。在组播窗口拥塞机制中，在端系统维护拥塞 窗口，通过窗口来控制未应答的分组数目，窗口的维护由端系统来完成。发送一 个数据分组，会占用拥塞窗口的一部分：收到一个分组的应答后，会释放占用的 部分；拥塞窗口有空闲时，发送端可以继续发送数据。没有拥塞时，增加拥塞窗 口；拥塞发生时，减小拥塞窗口。发送方始终要保证被所有接收方确认的报文个 数小于窗口的大小。 文献 1 4 指出，将拥塞窗口机制从单播扩展到组播时，为了最大化组播组吞 吐量，发送端需要为每个接收端维护一个独立的拥塞窗口。另外一个值得注意的 结论是：基于窗口的算法只需要采取与t c p 类似的m m d 行为，不需要估计接收端和 发送端之间的r t t ，就能比较容易地保证组播流量的t c p f r i e n d l y ；而对于基于速 率的算法，r t t 信息是必须的。但随着组规模的增大，为每个接收端维护拥塞窗 口会导致发送端的拥塞控制任务变得非常复杂，从而降低了可扩展性。另外，发 兰州大学硕士学位毕业论文 非累积分层组播的拥塞控制改进 送端如果接收所有接收端的反馈，它将遭遇反馈风爆。 2 3 3 单速率组播拥塞控制和多速率组播拥塞控制 如果按照数据发送的方式来分类，组播拥塞控制算法可以划分为： 1 、单速率组播拥塞控制“蜘( s i n g l er a t e m u l t i c a s tc o n g e s t i o n c o n t r 0 1 ) 所谓单速率组播拥塞控制，即发送方只按一种速率来发送数据：一般发送速 率受到具有最差的接收方( 即发送速率最慢的接收方) 的制约，而且整个组播组的 吞吐量会受到拥塞最严重的接收方( 瓶颈接收方) 的限制。 在使用单速率组播拥塞控制时，组播的吞吐量受瓶颈接收端的限制，限制了 协议的可扩展性。文献 2 2 的研究表明，即使在网络情况比较理想时，随着组规 模的增加，单速率组播拥塞控制也可能严重影响组播组的性能。单速率算法的优 势是实现相对简单，无需向多速率组播拥塞控制那样需要考虑对数据分层编码、 决策同步等问题。 2 、多速率组播拥塞控制叭“”( m u l t i - r a t e sm u l t i c a s tc o n g e s t i o n c o n t r 0 1 ) 在多速率组播拥塞控制中，发送方可使用多种速率来进行数据发送，从而在 接收端之间产生更灵活的带宽分配。最具有代表性算法是分层组播( 1 a y e r e d m u l t i c a s t ) 机制。 这种典型的分层