（计算机应用技术专业论文）高速网络中拥塞控制算法的研究.pdf

南京邮【乜大学硕l 研究生学位论文 摘要 摘要 t c pr e n o 是目前成熟的、通行的、应用广泛的一种拥塞控制算法。t c pr e n o 采用 数据包丢失作为网络拥塞度量的标志。该算法所包含的慢启动、拥塞避免、快速重传和 快速恢复机制是之后很多算法的技术基础。t c pr e n o 采用加性增长和乘性减少机制 ( a i m d ) 来调整其拥塞控制窗口。然而，t c pr e n o 在高带宽大延迟网络中带宽的利用 率并不高，这是t c pr e n o 的一个缺陷。 针对r e n o 在高带宽网络中效率不高的问题，业界提出了很多新版本的t c p 算法， h s t c p 是其中的一个典型算法。与t c pr e n o 相比，h s t c p 重新调整了a i m d 的参数 因子，从而使h s t c p 的拥塞窗口增长更激进，减少更保守。通过这种方式，h s t c p 在 高速网络中获得更大的吞吐量。但当h s t c p 流和t c pr e n o 流在同一链路上竞争时， h s t c p 会占据绝大部分带宽，造成了严重的公平性问题。 论文从拥塞控制算法研究的必要性入手，介绍了拥塞控制算法的设计方法和与之相关 的评估指标，特别对t c pr e n o 算法和h i g h s p e e dt c p ( h s t c p ) 算法进行了深入研究，在 此基础上给出了一个新的改进算法- m h s t c p ，改善了公平性，并通过n s 仿真实验验证 了m h s r c p 算法的有效性，最后给出了研究工作的总结和展望。 关键词：t c p 拥塞控制算法，t c pr e n o 算法，h i g h s p e e dt c p ，a i m d 南京邮电大学硕l ：研究生学位论文 a b s t r a c t a b s t r a c t t c pr e n oi sam a t u r e ，p o p u l a rc o n g e s t i o nc o n t r o la l g o r i t h ma p p l i e di nn e t w o r k sa l lo v e rt h e w o r l d t c pr e n ou s e sp a c k e tl o s s 鹊t h es i g n a lo fc o n g e s t i o n i tc o n s i s t so ft h es l o ws t a r t ， c o n g e s t i o na v o i d a n c e ，f a s tr e t r a n s m i s s i o na n df a s tr e c o v e r ya n di sc o n s i d e r e dt ob et h es t a n d a r d p r o t o c o lo ft c pc o n g e s t i o nc o n t r o la l g o r i t h m t c pr e n ou t i l i z e sa na d d i t i v ei n c r e a s ea n d m u l t i p l i c a t i v ed e c r e a s em e c h a n i s m ( a i m d ) t oa d j u s ti t sc o n g e s t i o nw i n d o w h o w e v e r ，i nt c p r e n ot h e r ei sap r o b l e mt h a tt h eb a n d w i d t hu t i l i z a t i o ni sl o w e re s p e c i a l l yi nh i g h s p e e da n d l a r g e d e l a yn e t w o r k a i m i n ga tt h el o w e rb a n d w i d t hu t i l i z a t i o no ft c pr e n o ，t h ei n d u s t r yr e l e a s e sm a n yn e w r e l e a s e so fc o n g e s t i o nc o n t r o la l g o r i t h m sf o rt c pp r o t o c 0 1 h s t c pi sat y p i c a lc o n g e s t i o n c o n t r o la l g o r i t h m c o m p a r e dt ot c pr e n o ，h s t c pr e a d j u s t st h ea i m dp a r a m e t e r st oe n h a n c e t h ei n c r e a s eo ft h ec o n g e s t i o nw i n d o ws i z er a p i d l ya n dt or e d u c et h ed e c r e a s eo ft h ec o n g e s t i o n w i n d o ws i z es l o w l y b yt h i ss t r a t e g y ，h s t c pc a l lp r o v i d et h et h r o u g h p u ti nh i 曲- s p e e dn e t w o r k m o r et h a nb e f o r e w h e nh s t c pa n dt c pr e n of l o w sc o m p e t ei nt h es a m el i n k ，h s t c pg a i n s t h em o s tb a n d w i d t h s ot h ee q u i t a b l e n e s sa p p e a r s a c c o r d i n gt ot h er e s e a r c ho ft h ec o n g e s t i o nc o n t r o la l g o r i t h m ，t h i sp a p e ri n t r o d u c e s t h e d e s i g nt e c h n i q u eo ft h ec o n g e s t i o nc o n t r o la l g o r i t h ma n dt h er e l a t e de v a l u a t i o nc r i t e r i o n a f t e r t c pr e n oa n dh s t c pa r ed i s c u s s e d ，t h i sp a p e rp r o p o s e san e wi m p r o v e dc o n g e s t i o nc o n t r o l a l g o r i t h mm h s t c p m h s t c pc a n e n h a n c et h ef a i r n e s s w i t hn e t w o r k i n gs i m u l a t o r ( n s 2 ) ，t h e v a l i d i t ) ，o fm h s t c p i ss i m u l a t e d f i n a l l yt h e r ea r e t h er e s e a r c hs u m m a r ya n dp r o s p e c t k e yw o r d s ：t c pc o n g e s t i o nc o n t r o la l g o r i t h m ，t c pr e n o ，h i g h s p e e dt c p ，a i m d 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：嫩日期：芈，乙 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：雠导师签 参孚 南京邮l u 人学硕l j 研究生学位论文第一章引苦 1 1 问题的提出 第一章引言 拥塞是一种持续过载的网络状态，此时用户对链路带宽、存储空间和处理器处理能 力等网络资源的需求超过了其固有的容量。就i n t e m e t 的体系结构而言，拥塞的发生是 其固有的属性。拥塞导致的直接结果是分组丢包率提高，端到端时延加大，甚至有可能 使整个系统发生崩溃。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效 吞吐量急剧下降。 拥塞崩溃对i n t e r n e t 的威胁可以追溯到早期的发展中，1 9 8 4 年n a g l e 报告了由于t c p 连接中不必要的重传所诱发的拥塞崩溃【l 】，1 9 8 6 - 1 9 8 7 年间这种现象曾经多次发生，严 重时一度使l b l 到u cb e r k e l e y 之间的数据吞吐量从3 2k b p s 跌落到了4 0 b p s 【2 j 。除此之 外，还有其他一些诱发拥塞崩溃的原因，例如，不可达分组导致的网络崩溃，它不是一 种稳定状态，当负载减小时，拥塞可以自动恢复。f l o y d 报告【3 】中指出了另一种形式的拥 塞崩溃现象，即分片拥塞崩溃，网络传输了大量的分组分片，但因为无法在接收端重装 成有效的分组而只好将它们丢弃。网络传输中大量的、用户不再需要的陈旧分组会导致 另一种形式的捌塞崩溃现象。图1 1 是负载、吞吐量、响应时间的关系图。 负找 喇耋i i 负拔 图l _ l负载、响应时间、吞吐量之间的关系 图1 - 1 说明了负载与吞吐量之间的关系。当负载较小时，吞吐量与负载之间呈线性 关系，到达膝点之后，随着负载的增加，吞吐量的增量逐渐变小：当负载越过崖点之后， 吞吐量却急剧下降。通常将膝点附近区域称为拥塞避免区间，膝点与崖点之间是拥塞恢 复区间，而崖点之外是拥塞崩溃区间。为了最大限度地利用资源，使网络工作在轻度拥 塞状念时应该是较为理想的，但这也增n t 滑向拥塞崩溃的可能性。因此需要相关的拥 塞控制机制来加以约束和限制拥塞问题，这导致了人们开始研究有效的拥塞控制算法。 l 南京邮l u 人学倾【。研究生学位论文 第章引言 1 2 研究现状 网络中的拥塞来源于网络资源和网络流量分布的不均衡性。拥塞不会随着网络处理 能力的提高而消除。 拥塞控制算法是在网络中相互竞争用户上运行的分布式算法，其用于竞争用户之间 网络资源的分配。由于网络中可用资源和竞争用户都是随机变化的( 用户的需求在传输 起始时间、需求速率、持续时间上变化很大，在很多情况下具有突发性) ，在这样的环境 下有效地分配资源是非常重要的。拥塞控制算法正是各个网络用户用来依据网络环境变 化所提供的反馈信息自适应地调整网络行为，以达到整个网络系统的最佳运行性能的分 布式算法。拥塞控制算法的分布性、网络的复杂性和对拥塞控制算法的性能要求又使拥 塞控制算法的设计具有很高的难度。 一般解决拥塞问题方法是：一是增加网络资源；二是降低用户需求。前者一般通过 动态配置网络资源来提高系统容量。如在高峰期增加接入线路、通过路径分裂( p a t h s p l i t t i n g ) 、用多条不同的物理路径来满足用户需求。而降低用户需求主要表现在三个方 面：拒绝服务、降低服务质量和调度。拒绝服务是在拥塞发生时，拒绝接纳新的用户请 求，例如电话网中的忙音，此方法多用于面向连接的网络。降低服务质量是所有用户( 包 括新用户) 在搠塞时降低其发送速率，例如分组交换网络中的滑动窗1 2 1 算法等。调度是指 合理安排用户对网络资源的使用，保证总需求永远小于网络可用资源，例如轮询、加入 优先级、资源预留等。 传统的拥塞控制算法主要有t a h o e ，r e n o ，以及在r e n o 基础上演变而来的v e g a s 和 n e w r e n o ，其中以r e n o 应用最为广泛。在传统网络中，r e n o 及其演化版本表现出了较 好的性能。 随着i n t e r n e t 的发展，其拥塞控制机制不断改进以适应网络的发展。技术的发展趋势 导致网络中包含了极多的高带宽的链路，同时还会出现越来越多的高延迟的网络。已有 的研究表明，不管采用何种队列机制，传统的t c p 拥塞控制算法都将无法适应这些高带 宽或高延迟的情况。由于采用加性增长机制，传统的t c p 拥塞控制算法在每个i m 中 增加发送的包过于缓慢，这在高带宽的网络环境下会浪费若干i 册才能充分利用网络带 宽。钊j 对传统t c p 算法在高速网络中的缺陷，业界提出了诸如f a s t ，h i g h s p e e dt c p ， x c p ，快启动等新的拥塞控制算法，较好的解决了上述缺陷，但也引出了新的问题，即 高速t c p 流与传统t c p 流共存时的公平性问题。 本文将着重讨论高速网络环境下t c pr e n o 拥塞控制算法和h i g h s p e e dt c p 算法的性 2 南京邮i u 丈学硕i - ：f i f f 究生学位论文 第一章弓i 言 能，以及本论文对h i g h s p e e dt c p 算法的改进方案。 1 3 论文组织结构 本文针对t c p 拥塞控制算法进行了研究，介绍和分析了两种典型拥塞控制算法t c p r e n o 和h s t c p 的原理和运行性能，指出二者在共享同一链路时会发生公平性问题。在 此基础上提出了一种改进的解决方案m h s t c p ，并通过仿真实验验证了其可行性和有效 性。全文的组织结构如下： 第一章概述了拥塞控制算法问题的提出与研究现状。 第二章分析与说明t c p 拥塞控制算法及其性能评价标准。 第三章介绍了r e n o 算法的慢启动、拥塞避免以及快速重传快速恢复机制，给出了 r e n o 算法的性能分析。 第四章针对r e n o 算法在高速网络环境下存在的问题，引出h s t c p 算法的基本思想， 并对算法实现的主要部分做出了较详细的说明。在分析和比较h s t c p 与其他高速网络 环境下t c p 拥塞控制算法的基础上，指出了h s t c p 的缺陷，即在与t c pr e n o 并存时 的公平性问题，在此基础上给出了一种解决方案，即h s t c p 的改进算法仰h s t c p 。 第五章利用n s 仿真实验，验证第三章和第四章中的理论分析观点，验证了m h s t c p 改进方案的有效性。 第六章给出了总结全文和进一步工作的展望。 南京邮l u 人学f ! i j 研究生学位论文 第二章拥采控制及其算法 2 1 拥塞控制算法 第二章拥塞控制及其算法 拥塞控制算法的基本设计目标是获取高利用率、低排队时延、低丢失率、可接受的 公平性和稳定性等，实现端到端传输的有效控制。由于算法设计的出发点不同，拥塞控 制算法的实现主要在流层( f l o w - l a y e r ) 和数据报层( p a c k e t - l a y e r ) 。 一个网络是由一组容量为c = f ，q ，三夕的链路组成，它们连接了一组源端，标记为 i 。每一个源端f 使用一组三，sl 的链路，而每一条链路又被一组源端1 1 互，所共享。可 以论证：，l ，i ，这样就定义了一个三，的路由矩阵： 耻锯蒜p q ， 图2 1 为网络拓扑的抽象图。 幻b 图2 一l 网络拓扑图 可以看出，每条链路在，时刻的链路使用率是由使用该条链路的各个源端的传输速 率z ，( ，) 产生的链路总速率y l ( f ) 决定，而它直接关系到链路的拥塞量，即p f ( ，) 的值。反 过来链路的拥塞量又影响到每个源端的传输速率一( ，) 。由此，可以将拥塞控制算法分成 两部分： ( 1 ) 端节点( 发送端和接收端) 上的t c p 拥塞控制算法： ( 2 ) 中间节点( 如路由器) 上的增强机制：如报文分类、队列管理、分组调度、 流量整形等。其中队列管理是研究最多的一个方面，尤其是主动队列管理1 4 ( a c t i v eq u e u e 4 南京邮l u 人学颁i j 训：究生学位论文第二章拥塞控制及其算法 m a n a g e m e n t ，a q m ) ，包括：尾丢弃、早期随机检测( r a n d o me a r l yd e t e c t i o n ，r e d 5 1 ) 及r e d 的变种算法、b l u e l 6 1 、a v q 7 1 、p i 控制器【8 1 。文献【9 】给出了有关a q m 的详细 讨论。t c p a q m 算法的网络分布如图2 - 2 所示。图2 - 3 给出t c p a q m 的数学模型。 图2 - 2t c p a q m 算法体系结构 图2 - 3t c p a q m 算法的数学模型 t c p 协议由一个函数f 来建模，该函数描述了源端的传输速率t ( f ) 与端到端拥塞量 g ，( f ) 的关系： 戈，( ，) = e ( x ，( ，) ，q 心) ) ( 2 4 ) 不同的t c p 协议有不同的f 函数来建模。 a q m 由函数g ，来建模，描述了链路拥塞量p 以) 是如何根据链路总体速率j ，) 来更 新的： p f ( ，) = g ，( y ( f ) ，p f ( ，) ) ( 2 5 ) 总之，一个t c p a q m 协议组是由( f ，g ) = ( e ，g ，f ，l ) 建模。 双模型结构( 2 4 和2 5 ) 很大程度上取决于( 2 4 ) 中的t c p 函数e 。平衡速率x ，和端到 端拥塞量q 之间的关系为： s 南京邮f u 人学硕，l 研究生学位论文 第二章拥塞控制及其算法 q 。= f , ( x j ) 0 定义每个源端的效用函数为 u ( t ) = d ( t ) 出，t o 最大总体使用率 ( 2 6 ) ( 2 7 ) m 砼a 。x 一 - u ，( x i ) 取决于戤sc ( 2 8 ) 在此有个条件，即每条链路f ，它的总体速率乃不能超过链路容量q 。等式( 2 4 2 5 ) 中的x ( ，) 作为初始变量，p ( ，) 作为双重变量，( f ，g ) = ( ，g ，f ，i l ) 作为一个由网络 上源端和链路共同运作的分布式双重等式。不同的t c p a q m 协议可被建模成不同的分 布式初始双重等式来解决相同的全局优化问题，在此用到不同的利用率函数u ，它由等 式( 2 7 ) 给出。 利用率等式以及潜在的初始问题都仅仅取决于t c p 函数e 。只要a q m 函数g ，使 总速率y ? 在每个瓶颈链路上和链路的容量c ，相等( 这里p ? 0 ) ，等式( x p ) 就成为初 始双重最优化等式。这样就可以把t c p 函数f ，的设计看作选择一个平衡点( 比如，带 宽分配和公平性考虑) ，而a q m 函数g ，的作用就是平衡给定t c p 和队列动态的平衡点。 本文的基本观点是把t c p 函数e 作为动态系统，而拥塞量p ( f ) 作为这个动态系统的控 制输入。 流层的设计中已经考虑了诸如传输速率，拥塞度量以及两者之间的关系等问题，但 是仅有这些模型是远远不够的，还必须考虑具体的实现问题，比如如何设定r 阿的最小 时间刻度问题，判断一个包丢失到底是依据几个重复a c k ，以及每收到一个确认，估算 模块如何计算平均队列延迟，脉冲控制模块又如何决定是否可以向网络中发送数据了等 等，这些都不可能在流层中说明清楚，所以必须依赖数据报层的设计。在数据报层上， 将考虑流层未考虑的问题，包括和操作平台相关的实现细节以及参数估计等问题。 本文研究的重点将放在端节点t c p 拥塞控制算法上。 2 2t c p 拥塞控制和流量控制 t c p 的流量控制是i n t e r n e t f 常运行的基础。据统计，i n t e m e t 上9 5 的数据流使用 的是t c p 协议，非弹性的u d p 业务只占很小的份额，围绕着t c p 流量控制的拥塞控制 6 甬京邮l 也入学硕l 研箩z 生学位论文第二二章拥塞控制及l e 算法 直是i n t e r n e t 研究的一个热点。 在i n t e m e t 设计的初期，对拥塞的控制是通过传输控制协议【1 0 l 中端到端基于滑动窗 口的流量控制来完成的。1 9 8 8 年，v a nj a c o b s o n 指出了t c p 在控制网络拥塞方面的不足， 并提出了“慢启动”和“拥塞避免”算法【1 1 1 ，该算法几乎被所有的i n t e r a c t 主机支持。 在很长一段时闯内，端驱动的t c p 流量控制是唯一可行的拥塞控制方法，这也导致 了“流量控制”和“拥塞控制 两个概念经常被混淆。实际上，前者只是实现后者的一 种技术实现途径而已。拥塞控制和流控制主要有以下两个不同点： ( 1 ) 流量控制的主要目的是为避免超出接收端的接收能力，因而更关心接收端的缓 存：而搠塞控制主要目的是为了避免使路由器缓存溢出而引起网络拥塞，主要是着眼于 网络的高吞吐量和低延迟。 ( 2 ) 两者采用不同的窗口机制。流量控制采用的窗口记为w n d ，拥塞控制有自己 的拥塞窗口c w n d ，最终发端的发送窗口大小为两者的最小值m i n ( w n d ，c w n d ) 。 t c p 流量控制遵守了两个主要原理，即流控自同步( s e l f - c l o c k i n g ) 的分组守恒定理和 加性增加乘性减d 、( a d d i t i v ei 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 ，a i m d l l 2 1 ) 的窗1 2 管理算 法。 a i m d 依赖其简洁的实现机制，在多个相互冲突的目标之间实现了较为理想的平衡 与协调，虽然无法保证具有不同属性的终端系统( 比如不同l m 时间、不同分组大小、 经历不同跳数的拥塞链路等) 能够分配到等量的带宽，但却能确保大致相似的用户得到基 本相等的网络资源。这是t c p 拥塞控制中最本质、最重要的特性。 2 3 算法性能的分析 对拥塞控制算法的性能分析主要看两个方面：平衡性能和动态性能。平衡性能主要讨 论的是系统在平衡点处的各种运行性能及表现，包括吞吐量、有效性、丢包率、公平性、 可扩展性等。动态性能则体现于系统的稳定性和响应度上。 2 3 1 平衡性能 ( 1 ) 吞吐量 对于每个端节点来说，吞吐量也就是传输速率，是一个端节点在单位时间内向网络 中发送的数据量，单位一般是呐。我们定义每个端节点j 在时刻，的传输速率为x ，( f ) 。 7 南京邮i u 人学硕i j l i j f 究生学位论文 第二章拥塞控制及其算法 由于发送速率一( f ) 和发送端的拥塞窗口大小w 心) 存在着z 心) = w ( ，) z ( f ) 的关系，z ( f ) 为来网时延( r o u n dt r i pt i m e ，r t t ) ，一般由网络环境的变化所决定。通过这个关系式 可以简单地来理解复杂的网络行为，一方面发送端通过调整的拥塞窗口大小以，) 来调节 发送速率工，( f ) ，另方面网络环境的变化通过z ( r ) 也会影响发送速率x ，( f ) 。 ( 2 ) 有效性 一个网络是由一组容量为c = ( q ，三) 的链路组成，设与该网络相关的每个端节点f 在时刻，的传输速率是x ，( ，) ，平衡速率x 。和端到端拥塞量g ，之间的关系为： g ，= ，( x ，) 0 ( 2 6 ) 定义每个端节点的效用函数为 配( ) = i f j ( x 。) d x ，0 ( 2 7 ) 那么最大总体使用率就是 m a x u ，( ) 取决于戤c ( 2 8 ) 显然，每条链路，的总体速率y ，不能超过链路容量c ，。 ( 3 ) 丢包率 数据报丢失主要是由于网络拥塞产生的。假设瓶颈链路路由器上运行的算法是 d r o p t a i l ，当路由缓冲已经塞满了的时候，后来的数据报将予以丢弃，这样就产生了数 据报丢失。当然，也有可能是其他原因造成数据报丢失，比如，由于各个i p 包的路由选 择不同而造成失序，当接收端收到一个失序报文时，一般会给发送端返回一个重复a c k ， 以告知产生了失序，当发送端收到甩( 刀一般取为3 ) 个重复a c k 时，发送端就认为发 生了数掘报丢失。当拥塞控制算法和路由器队列管理算法经常导致网络拥塞现象发生时， 会直接引发丢包率的上升。 ( 4 ) 公平性 当多个不同的流共享多个瓶颈资源，而每个流的价值取向不同时，公平性是一个非 常复杂的问题。然而，当所有流共享唯一的瓶颈资源，而且网络对所有的流都等同视之 时，公平性可以很简单地退化为在所有流间平均分配的问题。当流量分配偏离此值时， 必须刷一个量化的标准来度量其公平的程度。公平性评价的主要方法包括m a x m i n f a i r n e s s l l3 1 ，f a i r n e s si n d e x t l 4 1 和p r o p o r t i o n a lf a i r n e s s t l 5 1 等。m a x m i nf a i r n e s s 的含义是指： 每个用户的吞吐量至少和其它共享相同瓶颈的用户的吞吐量相同。m a x m i nf a i r n e s s 是 r 南京邮i 【人学硕f ：徊f 究生学位论文 第二章拥塞控制及其算法 “种理想的状况，但是它不能给出公平的程度。f a i r n e s si n d e x 提供了一个计算公式，通 过计算公平指数f ( x ) 来评价公平的程度，f ( x ) 定义如下： ( 再) 2 只柳2 哥 q 一 其中，疗为流的总数。 ( 2 9 ) 式的公平性定义满足以下性质： f ( x ) 的值域为 o ，1 。当所有流平均分配时( 五= 而= = 而) ，( x ) 为最大值1 ； 1 在最不公平的时候( 薯= a ；z ，= 0 ，当歹，时) ，f ( ) 为最小值二。当刀趋近于 刀 无穷大时，f ( x ) 趋近于0 ； 此值无量纲。x 可以取任何单位： 当所有流的速率按比例扩大( 或缩小) i 倍时，公平性不变； f ( x ) 为连续函数。分配时公平性的任何微小变化，都可以在f ( x ) 上体现出来； 当船个用户中的k 个平均分配资源，而疗一k 个用户不占用任何资源时，公平性的 值为! 。 玎 ( 5 ) 可扩展性 解决拥塞问题的途径主要是增加网络资源或降低用户需求。随着物理层、链路层技 术的完善及网络互连设备相对费用的降低，互连网络的带宽飞速增长( 1 g b i t s 、1 0 g b i t s 甚至1 t b i t s ) 。如何设计一个比较合理的拥塞控制算法以适应带宽的不断增长，且具有较 合理的丢包率( 1 0 - 7 - - 1 0 8 ) 是至关重要的。可扩展性就是衡量一个算法在不同网络带 宽条件f 是否具有较好的反应，或是说是否具有较好的平衡性能和动态性能。 ( 6 ) 延迟 延迟主要分两部分：传输延迟和排队延迟。传输延迟指的是数据在网络上无等待( 即 没有经过缓冲等待) 的来回传输时间。由于信息是以光速进行传播的，所以这个延迟的 时问取决于双方的距离大小，一般不随时间变化而变化( 除非路径选择有所变化) 。排队 延迟主要是指数据在经过网络上路由器等路由设备时，在缓冲队列中排队等待的时间总 和。由r 设备的负载程度不同，其缓冲队列长度会长短不一，队列长度长，排队等待的 时问! j ! l j 长，反之则短。在流层分析中，用d j 表示传输延迟，g ，( ，) 表示排队延迟，总的来 9 南京邮i u ，f 4 学侦i j 研究生学位论文 第二章拥塞控制及j 乓算法 凹延迟：勾z ( ) = 盔+ 吁，0 ) 。 2 3 2 动态性能 ( 1 ) 稳定性 “平衡”是系统运作良好的一种状态，因此这种状态被期望保持稳定。也就是说， 当网络拓扑结构或者网络背景流量变化时，这个网络能汇聚到一个新的平衡点，而不是 发生振荡或者崩溃，这就是稳定性问题。 稳定性既与端节点的t c p 算法相关，又与路由器上的a q m 算法相关。比如，如果 路由器使用早期的d r o p t a i l 算法，当链路上的总体速率y ，已达到链路容量c ，时，路由器 上的缓冲填满，路由器就会丢弃其后来的数据报，而报文的丢失造成了端节点进入慢启 动状态，降低吞吐率，直到t c p 开始接收到a c k 报文并增大拥塞窗口。但是当多个端 节点都因此而同时进入慢启动状态时，就会造成全局性同步。慢启动实际上是一种指数 形式的增长( 如r e n o 算法中每个r t t 期间吞吐率几乎增长一倍) ，当多个源端同时进入 慢启动状念时，增长速度是惊人的，网络很快会陷入拥塞状态。如此循环往复，网络显 然是不可能到达一个平衡点的。a q m 算法尽可能避免采用尾部丢弃的方法来解决这种 全局性同步问题。 可以通过一个稳定性指数s ，来衡量流的稳定程度，即在时间间隔r o ，m 】期间墨可以 通过如f 公式计算： 弘专熹静吲2 汜 那么门条流的平均稳定指数s = - e s 。，稳定指数s 越小表示t c p 流越稳定。 刀百 ( 2 ) 响应度( 收敛性) 当网络环境发生变化时( 一条流加入或断开) ，这条链路上其它流将经历一段时间稳 定在一个新的平衡状念，这种汇聚速度反映了该t c p 流对网络环境变化的适应程度，可 以通过响应度指标来衡量此性能。从网络环境发生变化时刻开始计时，设i ( 七) 为 0 ，j | 】采 样间隔f 均速度： 置( 七) = x ，( 七) ( 2 1 1 ) i t t = l 南京i u 人学顾l ：研多( 生学位论文第二章拥塞控制及其算法 贾，表示达到新平衡的平衡速率，那么响应度指数可以表示如下： r ：m a x 刚掣i 0 1 ) ( 2 1 2 ) 网络系统总的响应度指数r = m a x r ，) 。显然r 越小响应度越高，网络系统的汇聚速 度越快。 2 4 本章小结 本章说明了拥塞控制算法的有关概念和数学描述，根据算法空间分布的不同将算法 分成两部分，处于源端的t c p 拥塞控制算法和位于链路路由器上的a q m 算法，讨论了 流层和数据报层的不同处理策略，并对t c p a q m 的数学模型进行了分析。最后着重给 出了衡量拥塞控制算法性能的主要指标，即平衡性能和动态性能。 南京邮i u 大学顾。l j 研究生学位论文 第三章r e n o 算法及分析 第三章r e n o 算法及分析 早期的t c p 协议只有基于窗口的流量控制机制而没有拥塞控制机制，因此容易导致 网络拥塞。1 9 8 8 年j a c o b s o n 针对t c p 在网络拥塞控制方面的不足，提出了“慢启动 和“拥：塞避免”算法。1 9 9 0 年出现的t c pr e n o 版本增加了“快速重传 和“快速恢复” 算法，避免了网络拥塞不严重时采用“慢启动”算法而造成过度减小发送窗口尺寸的现 象。此后所形成的t c p 拥塞控制就主要由这4 个核心算法组成：慢启动、拥塞避免、快 速重传和快速恢复。文献【1 6 】【1 7 】给出了这些算法的设计方法，文献 1 8 】给出了这些算法 的标准化。 3 1r e n o 拥塞控制机制 t c pr e n o 算法主要具有五个状态：s l o w s t a l l 、c o n g e s t i o n a v o i d a n c e 、 f a s t r e t r a n s m i s s i o n 、f a s t r e c o v e r y 和r e t r a n s m i s s i o n - t i m e o u t 。t c pr e n o 拥塞控制机制如 图3 1 听示。 3 2r e n o 拥塞控制算法 3 2 1 慢启动与拥塞避免 慢启动和捌塞避免算法都基于一个假设，即绝大部分数据报的丢失是由于网络拥塞， 而不是数据报的损坏而产生的，这样数据报的丢失意味着在发送端和接收端之间的某处 网络上发生了拥塞。 t c p 发送端采用慢启动和拥塞避免算法来控制向网络输送的数据量。为了实现这些 算法，必须向t c p 每连接状态加入三个参量： ( 1 ) 搁塞窗口( c w n d ) ，它是对发送端收到确认( a c k ) 之前能向网络传送的最 大数据量的一个发送端的限制。 ( 2 ) 接收端通知窗口( r w n d ) ，它是对未完成数据量的接收端的限制，( c w n d 和 r w n d 的最小值决定了数据传送) 。 ( 3 ) 慢启动阈值( s s t h r e s h ) ，被用来确定是用慢启动还是用拥塞避免算法来控制 数据传送，具体用法如下：当c w n d s s t h r e s h 时使 1 2 南京l l i l j f u 人学顾i j 研究生学位论文第三章r e n o 算法及分析 j f j 捌塞避免算法：当c w n d = s s t h r e s h 时，发送端既可以使用慢启动也可以使用拥塞避免。 s s t h r e s h 的初始值可以任意大( 比如，些实现中使用接收端通知窗口的尺寸) ，但是 旦对拥塞响应之后，其大小可能会被减小。 图3 - 1t c pr e n o 拥塞控制机制有限状态机 在不清楚刚络环境的情况下向网络传送数据时，要求t c p 缓慢地探测网络以确定可 用带宽，以避免突然传送大量数据而使网络拥塞。为达此目的，在传送开始时，采用了 慢启动机制，这个机制在修复了由重发定时器探测到的数据丢失之后也被采用。 t c p 实体初始化c w n d = 1 。这就是说t c p 只被允许发送1 个报文段，然后就必须 等待接收到a c k 再传输第二个报文段。在慢启动期间，每收到一个新的a c k ，c w n d 增 长1 ( 即1 s m s s 个字节) ，直到c w n d 等于或者超过s s t h r e s h ，则转入拥塞避免阶段，在 慢启动期间，c w n d 是以指数规律增长的。显然，慢启动并非表面意义上的“慢启动 。 实际上，慢启动机制探测网络以确保它不会把太多报文段发送进一个已经拥塞的环 境。随着确认的到达，t c p 就扩大其拥塞窗口，直到流量最终由收到的确认a c k 而非 c w n d 所控制。 慢启动机制在初始化连接时很有效，它使得发送t c p 实体可以快速地为连接确定 合理的窗 f 大小。但当网络丌始出现拥塞时继续采用上述机制却是有缺陷的，这是由于 慢启动的窗口实际上是以指数速度增长。具体地，可以参考一个t c p 实体发起一个连 接并经历慢启动过程。某个时刻，在c w n d 达到另一端分配的信用量大小之前或之后， 一个报文段被丢失( 超时) 了。这是发生拥塞的信号，拥塞的严重程度并不清楚。因此， 一种明智的方法是复位c w n d = 1 并重新开始慢启动过程。这似乎是一种合理的保守方法， 南京邮l u 人学侦i j 研究生学位论文第三章r c n o 算法及分析 但实际上它还不够合理。 j a c o b s o n 在文献 1 6 1 q 口指出“让网络进入饱和状态很容易，但让网络从饱和状态中 恢复却很困难”。换一种说法即是一旦拥塞发生了，要将拥塞清除掉可能需花很长时间。 因此，慢启动中e w n d 的指数增加就可能使拥塞更严重。j a c o b s o n 提出开始时使用慢启 动机制，然后当c w n d s s t h r e s h 时采用拥塞避免机制，即让c w n d 线性增长 1 6 】，这一过 程为拥塞避免。 在拥塞避免期间，c w n d 在每个a c k 以的速度增长( g p 每个i m 后增加1 个 c w ，l d s m s s ) 。拥塞避免算法一直保持直到检测出拥塞。( 3 1 ) 式给出了一个在拥塞避免期 间用来修i ec w n d 值的公式： c w n d + = 1 c w n d( 3 1 ) 每收到一个非重复的a c k 都采用( 3 1 ) 式来调整c w n d 。( 3 1 ) 式用于近似拥塞避 免算法的增长。相对于慢启动算法的指数增加，拥塞避免阶段是线性增长。 s s t h r e s h = m a x ( m i n ( e w n d ，r w n d ) 2 ，2 s m s s ) ( 3 2 ) 一旦t c p 检测到拥塞发生时，( 3 2 式) 表示s s t h r e s h 就被设为当前窗口大小的 半，c w n d 和r w n d 的较小值，但最少为2 s m s s 。如果是超时引发的拥塞，则c w n d 被设 置为1 s m s s ，即重新进入慢启动状态。图3 2 说明了慢启动与拥塞避免的处理过程。 拥塞窗口 图3 2 慢启动和拥塞避免处理过程 3 2 2 快速重传与快速恢复 当接收端收到一个失序的数据报时，会立即发回一个重复a c k ，这个a c k 的目的 是告知发送端收到一个失序的数据报并说明其所期望的接受序号。从发送端的角度看， 重复a c k 可能是由多种网络问题引起的：首先，它们有可能是因为包丢失而引起，在 1 4 叫 m 2 可 ， 饼州 s s 堕室些! ! 查兰堡塑堕! ! 圭兰垡丝茎兰三童垦! 里! 簦鲨墨坌塑 此情况下，丢失数据段之后的所有数据段都会触发重复a c k ；其次，重复a c k 可能是 由于网络对数拆：段的重新排序引起的：再者，重复a c k 有可能是a c k 或数据段被网络 复制所引起的。因此，当接收端部分或完整地填补了序号空缺应立即发送一个a c k ，这 样可以更及时地通知发送端，使其迅速从重发状态中恢复过来。 t c p 发送端应该使用快速重传算法来探测或者修复数据丢失，在收到三个重复a c k ( 即连续的四个相同a c k ，标志着一个数据段已丢失) 时，t c p 就立即重传被认定丢失 的数据段，而不必等待重传定时器超时。快速重传后启用快速恢复算法来进行新的数据 传输，直到一个非重复a c k 到达。 图3 3 是快速重传与快速恢复的一个实例，其中，发送方对每一个步骤都有一个编 号。 发送方 接收方 【i ) 发送p a c k e t l ( 2 ) 发送p a c k e t 2 发送p a c k e t 3 1 1 ) 发送p a c k e t 4 ( i ) 发送p a c k e t 5 m ) 收到a c k l 发送 p a c k e t 6 ( 7 j 收剑a c k 2 ，发送 p a c k e t 7 ( 8 ) 收剑筇。个重复的a c k 2 ( q ) 收纠撕二个重复的a r k 2 ( 1 0 ) 收纠 ji 个重复 i 勺a c k 2 ， 削断i i p a c k e t 3 t 2 丢失巫发 p a c k e t ：i 肝进入快速重传 f 1 1 ) 快选i e f 之后收剑第。 个巫艇的x o x 2 宙i j 增人。个 p a c k e t 发送p a c k e t 8 ( 1 2 ) 收刊 c k 6 退快速恢 奠状志发j 差p a c k e t 9 收到p a c k e t l 返回a c k i 收到p a c k e t 2 返匝 a c k 2 收到p a c k e t 4 ，发现失序返回重艇的a c k 2 收到p a c k e t 5 ，发现失序返回重复的 c 旺 l 姻j p a c k e t 6 发现失序返回重复的 c 舷 姻j p a c k e t 7 发现失序返回重复的 c k 2 收到p a c k e t 3 ，填补了序列空缺。返i 司 c k 7 收到p a c k e t 8 返同a c k 8 图3 - 3 快速重传与快速恢复的实例 结合图3 3 ，为了便于说明快速重传与快速恢复的处理，采用简化的表示方法p a c k e t n 和a c kr i ，并使用p a c k e t 个数来度量窗口大小。假设拥塞窗口初始大d 、c w n d 为5 个p a c k e t 。 卜焉麓几c k e t s1 r c w ，l 矿一5 p a - _ 1 图3 - 4 最初拥塞窗口大小 1 5 南京邮电人学倾i j 训z 生学位论文第三章r e n o 算法及分析 在步骤( 7 ) 之后，窗口已经移了两个p a c k e t ： 卜口z 瓣坠硌_ r +口们臼，1 5 p a c k 。硌_ 1 图3 - 5 步骤( 7 ) 之后拥塞窗口大小 在发送p a c k e t 3 时发生了包丢失，所以在步骤( 1 0 ) ，当发送方收到三个重复的a c k 3 时，重发p a c k e t 3 ，并进入快速重传状态，c w n d = s s t h r e s h + 3 s m s s ，对窗口“充气”。根据 ( 3 2 ) 式，s s t h r e s h = 2 p a c k e t