（通信与信息系统专业论文）组播拥塞控制协议研究.pdf

摘要 组播拥塞控制是当前i n t e m e t 研究的重点问题 本文首先介绍了组播拥塞控 制 提出了组播拥塞控制机制的两个焦点问题 t c p 公平性和可扩展性 并综 述介绍了当今组播拥塞控制的一些常见协议 比较了各个协议的优缺点 在此基 础之上 提出了单速率组播拥塞控制协议t e a r m 该协议在每个接收端独立的 维护拥塞窗口并模拟t c p 的拥塞控制来改变窗口大小 其后将窗口值转换为期望 速率反馈给发送端 其中反馈的速率为一段时问内的加权平均 仿真表明t e a r m 适用于流媒体组播业务的传输 为了进一步改进t e a r m 的可扩展性 基于分层 组播框架 提出一种新的分层组播拥塞控制协议t l m c c 该协议向不同拥塞等 级的用户提供不同速率的数据传输 在每层使用t e a r m 协议来进行层内的拥塞 控制 仿真表明该协议具有良好的可扩展性和灵活性 同时保持了t c p 公平性和 平滑性 体现了良好的应用前景 关键词 组播拥塞控制t e a r mt l m c c a b s t r a c t m u l t i c a s tc o n g e s t i o nc o n t r o l i so n eo ft h em o s ti m p o r t a n tp r o b l e m si nt h er e s e a r c h o fi n t e m e t a tf i r s t c o n g e s t i o nc o n t r o lm e c h a n i s m sf o rm u l t i c a s ta r ei n t r o d u c e di nt h e p a p e r a n dt w ok e yp o i n t s t c p f r i e n d l i n e s sa n ds c a l a b i l i t y w h i c ha r eu s e dt oe v a l u a t e m u l t i c a s tc o n g e s t i o nc o n t r o lp r o t o c o l s a l ed e s c r i b e d t h e ns e v e r a lk i n d so fm a t u r e m u l t i c a s tc o n g e s t i o nc o n t r o lp r o t o c o l sa r ea n a l y z e da n dc o m p a r e di ne v e r ya s p e c t b a s e do nt h o s ea b o v e an e ws i n g u l a rr a t em u l t i c a s tc o n g e s t i o nc o n t r o lp r o t o c o l t e a r m t c p e m u l a t i o na tr e c e i v e r sm u l t i c a s tc o n g e s t i o nc o n t r 0 1 i sp r o p o s e d t h ep r o t o c o lm a i n t a i n sa ni n d e p e n d e n tc o n g e s t i o nw i n d o wa te a c hr e c e i v e ra n d i m i t a t e st c pt oc h a n g et h ew i n d o ws i z e w h i c hi st h e nc o n v e r t e di n t ot h ee x p e c t e dr a t e t h a ti saw e i g h t e da v e r a g ed u r i n gap e r i o do ft i m e a n dt h e nt h er a t ei sf e db a c kt ot h e s e n d e r t h es i m u l a t i o n si n d i c a t et h a ti ti sag o o dc h o i c ef o rs t r e a m i n gm e d i a t r a n s p o r t a t i o n i no r d e rt oi m p r o v et h es c a l a b i l i t yo ft e a r m b a s e do nl a y e r e df r a m e an e wl a y e r e dm u l t i c a s tm u l t i r a t ec o n g e s t i o nc o n t r o lp r o t o c o li sd e v e l o p e d c a l l e d t l m c c t e a rl a y e r e dm u l t i c a s tc o n g e s t i o nc o n t r 0 1 t h ep r o t o c o lu s e sl a y e r e d c o n s t r u c t i o n i no r d e rt op r o v i d ed a t at r a n s p o a i n ga td i f f e r e n tr a t e st or e c e i v e r si n d i f f e r e n tc o n g e s t i o nl e v e l s t h es i m u l a t i o n si n d i c a t et h a tt h ep r o t o c o lc o m b i n e st h e s c a l a b i l i t y a n d f l e x i b i l i t y o fl a y e r e dc o n g e s t i o n c o n t r o lm e c h a n i s m a n d t c p f r i e n d l i n e s sa n ds m o o t h n e s s i ti sp r o v e dt h a tt l m c cw i l lb ew e l lu s e di nf u t u r e k e y w o r d c o n g e s t i o nc o n t r o l m u l t i c a s t t e a r m t l m c c 创新性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果 尽我所知 除了文中特别加以标注和致谢中所罗列的内容以外 论文 中不包含其他人已经发表或撰写过的研究成果 也不包含为获得西安电子科技大 学或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究 所做的任何贡献均己在论文中做了明确的说明并表示了谢意 申请学位论文与资料若有不实之处 本人承担一切相关责任 本人签名 匾坐日期 q 211 型 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定 即 研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学 本人保证毕 业离校后 发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学 学校有权保留送交论文的复印件 允许查阅和借阅论文 学校可以公布论文的全 部或部分内容 可以允许采用影印 缩印或其它复制手段保存论文 保密的论 文在解密后遵守此规定 本人签名 厦达本人签名 整逃 导师签名 主影 群一 4 7i 日期 日期 第一章绪论 1 1 1 组播拥塞控制问题 第一章绪论 1 1 组播拥塞控制 随着信息产业的快速发展 网络已经成为人们社会生活中必不可缺的一部分 网络的应用从最初的文件传输 电子邮件和网页浏览 已经发展到在线医疗 视 频和音频的传送以及远程教育等等 网络已经渗透到人们日常生活的方方面面 人们对网络的需求呈快速增长的趋势 而且在当今网络中出现许多新的应用 这 就对原始的因特网 i m e m e t 产生了巨大的挑战 面对新的形势 原有的数据传 输方式单播和广播越来越不能满足人们对网络的新需求 而组播 m u l t i c a s t 数 据投递 即一个主机向多个主机或者多个主机向多个主机发送数据的传输方式 作为一种有效的数据传输手段 更高效的利用了网络资源 在一对多或多对多的 数据传输业务中 组播的性能不仅比传统的传输方式有了较大的提高 而且节约 了大量的网络资源 在十余年的研究和开发中 组播已经成为人们关注的焦点 由于组播自身的特点 传统的端到端拥塞控制 l c o n g e s t i o nc o n t r 0 1 不能 适用于组播的范畴 所以组播的拥塞控制问题随着组播日益广泛的应用而变得越 来越重要 组播中的拥塞因其独特性对拥塞控制协议的设计提出了新的要求 而 且也提供了一个对已有的控制方法进行重新认识的机会 组播的实现仍旧依赖于 t c p i p 协议簇 t c p 拥塞控制和i p 拥塞控制对组播的拥塞控制仍然有较大的参 考价值 也是组播拥塞控制的出发点和基础 t c p 公平性和可扩展性是组播拥塞控制中的两个重要评价标准 2 在现今的 i n t e m e t 中 基于t c p 流的业务占大多数 而且在今后相当长的一段时间内仍是 占绝对的多数 所以 为保证网络对t c p 流的公平 我们设计的新拥塞控制协议 必须要保证对t c p 流的公平性 也就是在相同的网络环境下与t c p 占用资源相 当 这个基本的要求被称为t c p 友好 t c p f r i e n d l i n e s s 也称为t c p 公平 t c p f a i m e s s 组播的特点是接收端众多 随着组规模的不断扩大 发送端的 任务越来越繁重 如果协议设计的不合理 很可能会引起整体吞吐量的下降 协 议的可扩展性成为需要考虑的重要问题 所以 组播拥塞控制协议主要是围绕着 这两点来设计的 组播拥塞控制协议研究 1 1 2 组播拥塞控制机制的研究现状 正如i e t f 在 3 1 q b 所指出的 相对于单播拥塞控制协议所具有的通用性而言 组播拥塞控制协议一般都具有很强的针对性 协议都是就某种特定的应用类型而 设计的 现有的组播拥塞控制研究都是针对不同的应用背景 主要有如下三个方 面 第一 针对流媒体应用的非可靠组播拥塞控制多采用基于速率的拥塞处理机 制 在公平性标准方面则尽量实现与t c p 拥塞控制的兼容 从而适应t c p 拥塞 控制协议 如t f m c c l 4 j t c pf r i e n d l ym u l t i c a s tc o n g e s t i o nc o n t r 0 1 r l c l 5 j r e c e i v e r d r i v e nl a y e r e dc o n g e s t i o nc o n t r 0 1 和f l i d d l t 0 1 f a i rl a y e r e d i n c r e a s e d e c r e a s ew i t hd y n a m i cl a y e r i n g 等 其常见的应用如视频点播等 第二 大规模可靠组播拥塞控制适用于一个源端到众多目的端的大量数据的 可靠传输 如m t c p t 7 m u l t i c a s tt c pc o n g e s t i o nc o n t r 0 1 和t r a m 嗍 t r e e b a s e d r e l i a b l em u l t i c a s tp r o t o c 0 1 等 此类的研究一般侧重于机制的可靠性和可扩展性 常见的应用有文件群发 软件发布和信息发布等 第三 适用于小规模组播组的可靠拥塞控制机制 如s r m p s c a l a b l er e l i a b l e m u l t i c a s t 此类应用一般组播组规模不大 组成员既是源端也是目的端 组成员 之间需要及时的信息交互 如电子白板 协同编辑等 近些年来 虽然在组播研究领域出现了众多的组播拥塞控制协议 但都不够 完善 所以i e t f 仍然没有提出组播拥塞控制的标准协议 下述的各种组播拥塞 控制协议均处于草案 d r a f t 状态 1 2 本文的工作及内容安排 本文工作来源于国家自然科学基金项目 因特网拥塞控制机制的研究 本 文研究组播拥塞控制机制 论文首先简介了组播和拥塞控制的基础 针对组播拥 塞控制中的主要问题 从组播拥塞控制协议设计的角度出发 深入分析了可行的 解决机制 并分析了现有的组播拥塞控制协议 以此为基础 本文重点研究了作 者作为i c c g i n t e m e tc o n g e s t i o nc o n t r o lg r o u p 课题组主要成员之一参与提出 的一种在接收端模拟t c p 的单速率组播拥塞控制协议t e a r m 以及一种新的分 层组播拥塞控制协议t l m c c 并对其进行了深入详细的仿真试验 本文采用的研究方法主要是仿真分析 在实验过程中 主要使用了n s 2 i l o j n e t w o r ks i m u l a t o r 它是离散事情驱动的多协议网络模拟软件平台 n s 2 采 用分离式编程模式 n s 内核即模拟使用的基本单元使用c 语言编写 而用t c l 第一章绪论 t o o lc o n t r o ll a n g u a g e 语言定义模拟过程 配置和控制脚本 n s 2 的最大优 点在于其源代码开放 使得研究人员可以针对自己的目标 更加方便的修改和测 试其代码 本文的内容安排如下 第二章研究组播拥塞控制 详细讨论了组播拥塞控制 机制的主要问题 解决思路和协议的设计 分析了几种具有代表性的组播拥塞控 制协议 第三章对在接收端模拟t c p 的单速率组播拥塞控制协议t e a r m 进行分 析和仿真研究 第四章对一种新的分层组播拥塞控制协议t l m c c 进行了分析和 仿真研究 最后一章总结全文 并指出今后工作方向 第二章组播拥塞控制问题研究 第二章组播拥塞控制问题研究 2 1 组播的基本概念 面对新的形势 传统的数据传输方式单播及广播越来越凸现其自身缺陷 单 播方式要求发送端向所有的接收端独立发送数据包 如果接收端的数目很多 那 么将给网络的资源造成极大的浪费 而且也会导致发送端的响应时间过长 而广 播由于要向全局域网发送数据 但有时并不是网络内所有的接收端都需要发送端 的数据 同样浪费了网络的资源 所以广播也难以满足当今灵活而多变的业务要 求 人们在不断寻找新的数据传输模式 由于许多应用都要求一个源点发送数据 到多个终点 即一对多的通信 因此人们提出了组播的概念 组播又称多播 图 2 1 说明组播的特点 图2 1 组播方式传输数据 图中三个主机a c 和d 构成一个组播组 主机s 向组播组的接收端进行组 播 s 可以不属于组播组 也可以不知道组播组的成员情况 主机s 在进行组播 时只发送一个数据包 只是到了路由器r 2 才进行复制 然后到了r 6 再复制一次 也就是 组播的数据包仅在传送路径分岔时才将数据复制后继续转发 若不是组 播 那么发送端在一开始就要发送3 个数据包 分别发送给a c 和d 显然 采用组播方式传播数据可以减少网络资源的消耗 在i n t e m e t 上进行组播就叫做i p 组播i l h o 组播依托于i p 协议簇实现 i p 组播 强制网络在数据传递的分岔处进行数据包复制 而不是由源节点重复发送相同的 数据包 这是i p 组播的精髓所在 6 组播拥塞控制协议研究 本文将从下面几个方面描述组播 1 组播的地址 i p 使用d 类地址支持组播 d 类i p 地址的前缀为1 1 l o 所以组播的地址范 围是从2 2 4 0 0 0 到2 3 9 2 5 5 2 5 5 2 5 5 d 类地址的分配是由因特网号码指派管理局 i a n a i n t e m e ta s s i g n e dn u m b e r sa u t h o r i t y 指定的 i p 网络采用的是 尽力而 为 的服务 所以i p 层并不保证组播组的所有接收端都能收到发送的数据包 在以太网内 可以利用硬件组播 i a n a 分配给以太网地址块为高2 4b i t 为 o o 0 0 5 e 的地址段 但只有当以太网硬件地址字段中的第1 字节的最低位为l 时 才为组播地址 而且只用其中的一半作为组播地址 所以其范围为 0 1 0 0 5 e 0 0 0 0 0 0 到0 1 o o 一5 e 7 f f f f f 以太网用2 3 位比特作为组播地址 这 只能和d 类i p 地址中的2 3 位比特一一对应 所以2 8 位比特的i p 组播地址中前 5 位不能映射以太网硬件地址 也就是 3 2 个i p 地址映射同一个m a c 地址 如 图2 2 所示 o81 62 43 l 3 2 位d 类i p 地址匝 鲷 二 二二 二二1 二二工二二工二二工 0l005e 4 8 位硬件地址匝亟西互匝 亟逐 亟匝 耍蓟1 面砸 二工二二 二二 二二 二 一一一 一一 以太网中可用的2 3 位组播地址 图2 2i p 地址与以太网组播地址的映射关系 2 i g m p i n t e m 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 g m p 消息周期轮询本地网络的主机 看它们是否还 在组播组内 若经过几次轮询 在本地网络中已经没有活跃的主机了 则不再向 其他的组播路由器通告本地的组成员情况 如果主机不想再接收数据了 它将发 送i g m p 消息快速离开组播组 目前 i g m p v 3e 1 2 j 是提案标准协议 3 组播路由协议 在i n t e m e t 上使用的第一个组播路由选择协议是距离向量组播路由选择协议 d v m r p d i s t a n c ev e c t o rm u l t i c a s tr o u t i n gp r o t o c 0 1 1 1 3 1 它是对于r i p r o u t i n g i n f o r m a t i o np r o t o c 0 1 单播路由选择协议的扩展 并且采用了l 冲m r e v e r s ep a t h m u l t i c a s t 算法 另外 它提出了 隧道 的机制 让组播数据包封装在单播分 组中穿过无组播能力的网络 除此之外 当前存在其他几种组播路由选择协议 第二章组播拥塞控制问题研究 7 如开放最短通路优先的组播扩展m o s p f m u l t i c a s te x t e n s i o n st oo s p f r f c 1 5 4 8 以及协议无关组播一稀疏方式p i m s m p r o t o e o li n d e p e n d e n t m u l t i c a s t s p a r s em o d e r f c2 3 6 2 和协议无关组播一密集方式p i m d m p r o t o c o l i n d e p e n d e n tm u l t i c a s t d e n s em o d e r f c2 3 6 2 等 但现在的组播路由协议都没有 成为因特网的正式标准 4 组播传输协议 1 9 9 9 年 评价可靠组播传输和应用协议的标准 3 中明确指出 由于技术的原 因 单一的可靠组播传输协议不可能满足所有组播应用的需要 已经有不同的可 靠组播协议针对不同的实际应用来设计不同的解决方案 例如 可扩展的可靠组 播s r m1 9 是针对于分布式白板的应用而提出的 在s r m 中 所有的成员地位都 相等 既是发送端又是接收端 当任意成员有新数据时 向全组组播 每个组成 员自己负责探测丢失和请求重传 任意组成员若有请求数据的拷贝 都可以响应 重传请求 此外 可靠组播传输协议r m t p t l 4 1 r e l i a b l em u l t i c a s tt r a n s p o r t p r o t o c 0 1 是针对于适合于中心式信息发布而提出的 r m l l p 的目的是在t c p m 的网络上实现完全可靠的大量数据从一个服务器 发送端 组播投递到成千上万 个接收端 5 0 0 0 1 0 0 0 0 服务器与n 个接收端建立l n 的连接 服务器以组播的 方式发送数据 当服务器收到终端的否定应答 则可用组播和单播两种方式进行 数据重传 所有传输完成后 拆除连接 r m t p 适用于软件更新 音乐视频发布 以及公司向顾客传递电子数据等应用 组播的传输协议仍有许多 如面向否定应 答的可靠组播n o r m n a c ko r i e n t e dr e l i a b l em u l t i c a s t 还有许多基于新的m 组播的传输协议 如l m s l a r g e s c a l em u l t i c a s t 和p g m p r a g m a t i cg e n e r a l m u l t i c a s t 组播也需要拥塞控制机制来响应网络负载状况 防止网络崩溃 于是 出现 了很多独立的协议 它们的目标仅仅是组播的拥塞控制 这些协议需要与组播传 输协议配合使用 这是由组播拥塞问题本身的特点所决定的 下面 本文就从拥 塞控制的基本问题出发 进一步说明组播拥塞控制问题和各种组播拥塞控制协议 及其优劣 2 2 1 拥塞和拥塞控制 2 2 组播拥塞控制问题 当网络中存在过多的包时 网络的性能会下降 这种现象称为拥塞 拥塞的 表现形式为 发送端吞吐量下降 包的时延增加 在路由器中包的丢弃概率增大 组播拥塞控制协议研究 等等 若在拥塞产生后 网络不采取措施控制 拥塞将会继续蔓延 最终导致部 分网络瘫痪 即发生了拥塞崩溃 拥塞产生的直接原因为 一是存储空间不足 二是带宽容量不足 三是处理 器处理能力不足 速度慢 但是 如果仅仅提高其中某一部分的性能 例如单一 的增加存储空间 或是加快处理器速度 这根本无法避免拥塞 只是使拥塞的瓶 颈转移到网络中其他部分 而拥塞产生的根本原因在于用户提供给网络的负载大 于网络资源容量和处理能力 也就是说 网络的资源与网络的流量不均衡 用户 对网络的需求和网络的供给不匹配 就会产生拥塞 使用图2 3 来描述拥塞的发生 当负载较小时 吞吐量的增长和负载相比基本 呈线性关系 延迟增长缓慢 在负载超过k n e e 之后 吞吐量增长缓慢 延迟增 长较快 当负载超过c l 濉之后 吞吐量急剧下降 延迟急剧上升 可以看出 负 载在k n e e 附近时网络的使用效率最高 拥塞控制就是网络节点采取措施来避免 拥塞的发生或者对拥塞的发生做出反应 在图2 3 中就是使负载保持在k n e e 附近 拥塞控制主要考虑端节点之间的网络环境 目的是使负载不超过网络的传送能力 而流量控制主要考虑接收端 目的是使发送端的发送速率不超过接收端的接收能 力 番 譬 ki o if 一 一 端曼裁 图2 3 拥塞现象过程 为了避免拥塞的发生 以及在拥塞发生后减少拥塞带来的性能下降等不利影 响 网络应采取措施 这就是拥塞控制 拥塞控制是一个全局性的问题 若是提 高局部性能 反会加重拥塞 所以拥塞控制应该着眼于全网的资源均衡性以及负 载与网络能力的匹配 拥塞控制机制分为三个阶段 拥塞检测 拥塞指示和拥塞控制算法 拥塞检 测的位置可以在端节点和中间节点 对于在端节点的拥塞控制 探测拥塞的判断 依据通常是包丢失 例如判断t c p 的定时器超时 或者是重复的a c k 对于在 中间节点的拥塞控制 其判断拥塞的依据可以是判断平均队长是否超过门限 例 如r e d t l 5 r a n d o me a r l yd e t e c t i o n 和其他一些a q m a c t i v eq u e u em a n a g e m e n t 机制 拥塞指示有两种方式 隐式通告和显式通告 e x p l i c i tc o n g e s t i o n 第二章组播拥塞控制问题研究9 n o t i f i c a t i o n e c n 如果拥塞检测在源端节点 则不需要拥塞指示 拥塞控制算 法就是能够实现拥塞控制 维持网络性能的算法 根据控制参数选择的不同 拥 塞控制算法可分为 基于窗口的拥塞控制 例如t c p 1 6 1 7 以及基于速率的拥塞 控制 例如t f r c 1 引 t c pf r i e n d l yr a t ec o n t r 0 1 在实际中 应该针对不同的应 用需求选择适当的拥塞控制协议 2 2 2 组播拥塞控制的评价标准 以上主要说明的是单播的拥塞控制机制 组播发生拥塞将带来比单播更为严 重的影响 这是由其自身的复杂性决定的 首先 组播流沿着组播树广泛分布于 整个i n t e m e t 其次 组播的接收端具有异构性 接收端的接收能力各不相同 最 后 组播的接收端数目不明确 发送端需要处理更多的反馈信息 所以 组播的 拥塞控制随着组播应用规模的不断扩大而越来越受到人们的重视 在不同的组播 应用中 组播拥塞控制需要针对不同的需求来具体设计 但无论何种应用都要求 组播拥塞控制解决两个最基本的问题 即t c p 公平性和可扩展性 2 2 2 1t c p 公平性问题 公平性可分为会话内公平性 协议内公平性 i n t r a f a i r n e s s 和协议间公平性 i n t e r f a i r n e s s 会话内公平性是指同一会话内的不同接收者之间的公平性 即当 他们处于同一个瓶颈带宽之下时 应该能够具有相同的带宽利用率 协议内公平 性是指同一拥塞控制协议之下的几个流在相互竞争时能够公平地分享网络带宽 协议间公平性是指不同拥塞控制协议的几个流在竞争网络带宽时能够公平的分享 网络带宽 协议与t c p 流的协议间公平性即为t c p 公平性 t c p 公平性是组播拥塞控制机制能否得到广泛应用的基础 也是每个拥塞控 制机制追求的设计目标之一 由于现有的i n t e m e t 中t c p 通信量仍然占主导地位 而且在今后相当长的一段时间内仍占绝对的多数 组播拥塞控制机制主要考虑和 t c p 的公平性 即组播流应该具有与t c p 流之间资源分配的公平性 也就是t c p 公平性 所以t c p 公平性问题是组播拥塞控制算法要考虑的一个重点 目前 在组播拥塞控制研究中己经引入了多种标准来评判组播拥塞控制协议 的t c p 公平性 一种说法是非t c p 流如果在一段较长的时间内的吞吐量不超过 t c p 流的吞吐量 就认为该流具有t c p 公平性 而在文献 1 9 1 给出了3 种协议问 公平性的评判标准 t c p 友好公平 t c p f r i e n d l yf a i m e s s 基本公平 e s s e n t i a l f a i r n e s s 和少公平 f a i r n e s si n d e xf a i r n e s s 1 t c p 友好公平 通过对于t c p 拥塞控制机制的分析 发现其吞吐量t t h r o u g h p u t 与数据 包丢失率p 满足 l o 组播拥塞控制协议研究 丁 r t t s p 高妨 其中c 1 5 厉 2 1 尺玎为往返时间 s 为数据包大小 如果一个组播流吞吐量r 和丢失率p 之间 满足 t 叱l x p 2 2 则认为该拥塞控制机制是t c p 友好公平的 2 基本公平 由于组播流有更多的接收端 所以可以比t c p 拥有更多的资源 假设组播的 平均吞吐量乃而一个t c p 流在该组播流的瓶颈链路 组播投递树中具有最小共 享带宽的链路 上的平均吞吐量为 如果两者满足 口 t b t t c p 其中a b n 2 3 式中 a 和b 是组播接收端数目n 的函数 则称其拥塞控制机制对t c p 是基 本公平的 显然 当a b l 时为绝对公平 3 妒公平 假设n 个数据流 组播流和t c p 流 共享瓶颈链路带宽 t 0 n 1 为 它们各自的平均吞吐量 定义如下的公平指数 疗 i zl f i 一 荨酷 其中j t 1 1 2 4 z 2 州r q 川 u u q 公平指数 反映了公平的程度 如果 1 则说该组播拥塞控制机制对t c p 是绝对公平的 否则 说组播拥塞控制机制对t c p 是 j 公平的 2 2 2 2 组播拥塞控制机制的可扩展性问题 可扩展性是评价组播拥塞控制算法的另一个主要方面 也是组播拥塞控制的 研究难点 可扩展性指的是拥塞控制算法在开始性能退化前 所能容纳的最多接 收端数目 组播拥塞控制算法的可扩展性受到如下三个方面的制约 任务复杂性问题 丢失路径多样性问题 2 0 l o s sp a t hm u l t i p l i c i t y l p m 和反馈内爆问题 2 1 l a c k i m p l o s i o n 1 任务复杂性问题 端到端的拥塞控制机制有两种控制模式 集中式和分布式 如果采用集中式 控制 发送端需要为每个接收端保存状态信息 由于组播组成员的数目往往很大 第二章组播拥塞控制问题研究 而且组成员动态改变 那么发送端的任务随着组规模的扩大而急剧加重 采用分 布式控制可将部分工作转移到各个接收端 这种收发分工的方式有效的减轻了发 送端的负担 2 l p m 问题 由于组播投递树中存在着多条不同的端到端路径 这样一个包在传输中可能 在这些不同的路径上发生独立的丢失事件 从图2 4 可以看到 组播数据包在路 由器r 1 被复制为3 份 沿着不同的路径转发出去 因此 在r 1 到r 2 的链路 r l 到i 玛的链路和r l 到d 2 的链路所经历的丢失被不同的接收端感知 这就是 独立丢失1 2 引 然而 发送端s 到r 1 的链路是通向所有接收端的公共链路 如果 在此处发生丢失事情 那么所有的接收端都能感知 这就是相关丢失 2 7 1 图2 4 相关丢失和独立丢失 独立丢失与相关丢失是与接收端的空间位置密切相关的 丢失路径多样性问 题就是在存在大量独立丢失的情况下产生的 组播组成员变得越来越多 端到端的路径也随之增多 从而同一包的不同拷 贝在传输过程中发生丢失的概率总和将大大增加 我们下面从数学角度来分析这 个问题 假设组播组成有为n 该组播树中至少存在n 条不同的链路 每条链路 上发生丢失的概率为p 那么每个包丢失概率为 q 1 一 1 一p r 2 期 当接收端数目 寸0 0 时 q 寸l 如果对每一个丢失事件发送端都进行拥塞响应 将导致速率调节过度 组播流发送速率将会趋于零 d r o p t o z e r o 3 反馈内爆问题 组播组成员的数目往往很大而且可能分布在整个i n t e m e t 上 为了实现组播协 议的有效性 组成员要发送各种状态和控制信息 因此组播需要处理大量的反馈 消息 包括确认包 a c k 否认包 n a k 状态包 s t a t u sp a c k s 如果大量 组播接收端同时向发送端发送反馈报告时 会造成反向路径的严重拥挤 同时 组播拥塞控制协议研究 对大量反馈包进行处理也加重发送端的处理负担 进一步降低了发送端协议的性 能 严重时甚至导致发送端的崩溃 当在网络中发生了一次相关丢失的时候 所 有的接收端都感知了该丢失 如果没有反馈抑制或是聚合策略 将会引发反馈内 爆 2 2 2 4 组播拥塞控制机制的其他问题 针对不同的应用业务 组播拥塞控制机制还需额外考虑其他性能 针对流媒 体业务的组播拥塞控制算法而言 还需要考虑发送速率的平滑性 以适应流媒体 的业务特性 平滑性指发送速率的瞬时抖动小 速率平滑变化 一般采用偏差系 数 2 2 1 c o e f f i c i e n to f v a r i a t i o n c o y 来衡量算法的平滑性 算法实现的协议流的 偏差系数越小 表明该协议的平滑性越好 如果一个流的顺时速率v 其偏差系 数c o v 为 c o v 妲坠坐塑 2 6 目v 组播拥塞控制还需考虑响应性 响应性是指拥塞控制机制对网络拥塞变化的 动态响应的速率 响应速度太慢 容易使一些瞬时的拥塞情况得不到及时的处理 t c p 的瞬时响应速度是比较快的 如果组播拥塞控制机制的响应速度比t c p 慢得 太多的话 会造成短时间内的不公平性 因此 设计中要求组播拥塞控制机制的 反应速度跟得上网络中负载动态变化的速度 但是如果响应速率太快 对于网络 的抖动反应过于敏感 不利于机制的平滑性 因此 设计时应该权衡考虑 2 3 组播拥塞控制的基本方法 2 3 1 如何保证t c p 公平性 接下来 我们介绍协议如何保证t c p 公平性 在此之前 简单介绍一下t c p 拥塞控制机制 t c p 的拥塞控制是一种端到端的闭环控制机制 采用基于窗口的 拥塞控制机制 在发送端维护拥塞窗口 c o n g e s t i o nw i n d o w 用来控制发送速 率 t c p 拥塞控制机制最明显的特性就是a i m d a d d i t i v ei n c r e a s em u l t i p l i c a t i v e d e c r e a s e 特性 也就是 在拥塞避免阶段 当数据包无丢失时 说明网络没有 出现拥塞 线性增大拥塞窗口 当数据包丢失了 说明出现了拥塞 发送端拥塞 窗口减半 迅速降低发送速率 p a d h y e 等人通过分析t c pr e n o 的拥塞控制过程 建立了t c p 流量模型1 2 3 1 发现t c p 流的吞吐量与下列参数有关 往返时间尺玎 重传超时值r t o 数据包 大小s 数据包丢失事件率p t c p 流量模型公式为 第二章组播拥塞控制问题研究 邢珊 加州箫 司琢i 蠢颥h 7 其中 b 为每个a c k 确认的包数目 是最大的拥塞窗口值 为了保证t c p 公平性 组播通常采用类似于t c p 的拥塞控制机制 常见的策 略分为两类 公式法和模拟法 公式法就是组播发送速率遵循t c p 流量模型公式 协议实时采集网络的状态 往返时间r 瓜丢失事件率p 代入t c p 流量模型公 式中求得该条件下的速率作为组播流发送速率 在此方法中 如何准确而及时的 测量参数是是一个难点 例如估计丢失事件率需要了解已发送数据包的达到情况 如果过多考虑数据包历史到达情况 这样的计算代价会较高 而且在网络状态突 变的情况下 计算的丢失事件率会严重失真 但是如果考虑历史不足 计算的丢 失事件率变化剧烈 f l o y d 等人提出了平均丢失间隔法 a v e r a g el o s si n t e r v a l 来 估计丢失率 此算法被t f m c c l 4 1 协议采用 其他基于公式的协议还有p g m c c 2 4 1 s m c c 2 5 f l i d d l 6 等 模拟法是模拟t c p 拥塞控制算法的行为特点 使得发送速率在较长的时间尺 度上和t c p 流保持相当 采用此类方法的协议有m t c p 7 1 和t e a r i 凋 t c p e m u l a t i o na tr e c e i v e r 等 模拟法除了可直接模拟现有t c p 的a i m d 机制 还 可采用其他的与t c p 的a i m d 机制保持兼容的窗口调整算法 常见的有 g a i m d l 2 7 1 g e n e r a la i m d g a i m d 和二项式算法 2 钔 b i n o m i a l 1 g a i m d g a i m d 是对a i m d 的推广 数学式表示为 a d 麓麓p 焉 0p p 8 形 毋卜 形 o 2 1 0 d 彬 所卜形一 彬 0 7 在每轮的末尾 如果第k 个e p o c h 没有结束 其速率样本值不能反映该e p o c h 的平均速率 所以t e a r m 接收端计算两个加权平均的e p o c h 速率 一是对第舡1 个e p o c h 到第肛 胁1 个e p o c h 样本做加权平均 另一是从第七个e p o c h 到第缸似1 个e p o c h 的加权平均 从两个平均值中选择较大的一个乘以包大小作为向发端反 馈的反馈速率 见公式 3 8 如果速率样本少于m 个e p o c h 也就是 k 8 0 2 0 0 佶 0 铂 0 i i i 醚时n u 尺度嚣 椭 图3 5t f m c c 和t e a r m 的等价比明图3 6t f m c c 和 r e a r m 的偏差系数c o v 由图3 5 可以看出 t c p 在0 m b p s 和3 m b p s 之间剧烈抖动 而t e a r m 在 1 5 m b p s 和2 m b p s 之间波动 t e a r m 速率抖动的范围远比t c p 小 从图3 6 对 不同时间尺度下偏差系数c o v 的分析上来看 t f m c c 的c o v 曲线和t e a r m 的 曲线几乎重合 说明二者具有相同的速率平滑性 平滑的速率能够避免视频数据 组播拥塞控制协议研究 的振荡 因此t e a r m 适用于流媒体业务的传输 3 2 2t e a r m 协议可扩展性分析 采用哑铃型拓扑 瓶颈链路带宽为8 m b p s 时延为5 0 m s 队列采用d r o p t a i l 方式 队列大小为1 5 0 接收端数目按照2 的指数次幂增加 l 2 4 5 1 2 记录每次仿真的平均吞吐量 即发端的发送速率 以及a c k 的数目与数据包数 目比率的平均值 褥 丑 毒 垦 2 接收者数目 图3 7t e a r m 和t f m c ca c k 数目和数据包数目的比率 随着接收端数目的增加 t e a r m 和t f m c c 的发送速率一直很稳定 另一方 面 从图3 7 可见 虽然t e a r m 的a c k 与数据的比率随着接收端数目的增加而 不断的增大 但是却一直低于在同样仿真环境中t f m c c 的比率 t e a r m 成功 的解决了反馈内爆问题 由此看出 随着接收端数目的增加 t e a r m 在吞吐量 并没有出现明显的下降的情况下 反馈抑制机制也将a c k 的数目控制在可以接 受的范围内 所以说t e a r m 具有良好的可扩展性 3 2 3t e a r m 响应性分析 1 对链路丢失率的响应性 图3 8 星型拓扑结构 第三章t e a r m 协议的仿真研究2 9 采用星型的拓扑结构 t e a r m 有四个接收端 分别设置4 个接收端的链路 丢失率为为0 1 o 5 2 5 和1 2 5 在0 s 时丢失率为o 1 的接收端加入 从2 0 0 s 开始 每1 0 0 s 按丢失率从小到大依次a n 在5 0 0 s 时 接收端按丢失率 从大到小依次退出 om o 嘲1 0 1 1 0 时闻 s 图3 9 t e a r m 和t c p 的接收速率 当丢失率更高的接收端加入组播组 3 臼 i 平2 擎 辎 o o2 0 04 0 0嘲枷 1 0 0 0 时间 s 图3 1 0 t e a r m 对c l r 的选取 t e 删可以很快选出合适的c l r 一 链路丢失率最高的接收端 选择新的c l r 的时延粗略地为1 s 至3 s 图3 1 0 中 c l r 在5 0 0 s 6 0 0 s 和7 0 0 s 为一l 是因为在当前c l r 退出之后 组播组内暂时没有 代表 发送速率也可以非常迅速的调整到与t c p 流相当的水平 图3 9 发送速 率随着丢失率高的接收端加入不断下降 随着其退出不断升高 在1 0 s 内可以迅 速调整到准确的速率 总之 t e a r m 能够很好的响应不同程度的链路丢失率 2 对低速带宽的响应性 采用哑铃型拓扑 t e a r m 有两个接收端 接收端r 0 与一条t c p 流竞争8 m 带宽 在1 0 0 s 时 接收端r 1 加入t e a r m 组播组 并且与一条t c p 流竞争4 m 带宽 并且该接收端在2 0 0 s 退出组播组 6 曼 v 静 卿 魍2 翁 o 1 国 蝥 辎 1 1 5 02 0 0 瑚 3 0 0 0 5 01 0 0 1 5 02 2 5 0 3 0 0 时间 s 时问 s 图3 1 1t e a r m 和t c p 的接收速率 图3 1 2 t e a r m 对c l r 的选取 瑚 嘲 钳 删 蛳 甜 伽 o 耋v哥溜擎鞲 3 0 组播拥塞控制协议研究 o 1 1 5 0瑚拗如 时闯 b o 时 接收端应订阅的最高层为 l l l 0 9 2 瓦el 4 1 而订阅的层数s i 应为s i l i l 例如 基层的最大发送速率b o 为4 m 如果某个接收端的期望速率为1 2 m 那么该接收端需要订阅基层l o l l 和l 2 三个层 在表l 中列出t l m c c 所使用到的符号定义 表1 符号定义 定义 b i 从基层 第0 层 到第i 层的最大累计发送速率 l i 第i 层 r i第i 层的实际发送速率 s j接收端j 的累计订购层数 e 接收端的期望速率 4 1 1 2 层速率动态调整 一个接收端在其订阅的最高层上被称为主动接收端 而在订阅的其他层中被 称为被动接收端 每一层的主动参与者对该层速率的调整负有责任 表现为它有 资格作为该层c l r 决定该层的速率变化 在每一层中 t l m c c 都选择主动接收 端中期望速率最小的作为该层的c l r 该层实际的发送速率r i 根据l i 层的代表 来动态调整 1 们 厶 曼 料 蝴 删 踩 时间 s 图4 1t l m c c 的框架 第四章t l m c c 协议的仿真研究 如图4 1 中 基层速率为4 m b p s 时 三个接收端分别加入l o 层 l l 层和l 2 层 如果l o 层的发送速率为 那么l l 层的实际发送速率r l 是l l 层c l r 的期 望速率e l