拥塞控制算法课件.ppt

《拥塞控制算法课件.ppt》由会员分享，可在线阅读，更多相关《拥塞控制算法课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、拥塞控制算法第1页，此课件共40页哦一、拥塞控制 拥塞现象 拥塞现象是指到达通信子网中某一部分的分组数量过多,使得该部分网络来不及处理,以致引起这部分乃至整个网络性能下降的现象,严重时甚至会导致网络通信业务陷入停顿。网络吞吐量 吞吐量是指在没有帧丢失的情况下，设备能够接受的最大速率。网络的吞吐量与通信子网负荷(即通信子网中正在传输的分组数)有着密切的关系。第2页，此课件共40页哦拥塞现象的产生 当通信子网负荷比较小时,网络的吞吐量随网络负荷的增加而线性增加。当网络负荷增加到某一值后,若网络吞吐量反而下降,则表征网络中出现了拥塞现象。在一个出现拥塞现象的网络中,到达某个节点的分组将会遇到无缓冲区

2、可用的情况,从而使这些分组不得不由前一节点重传,或者需要由源节点或源端系统重传。当拥塞比较严重时,通信子网中相当多的传输能力和节点缓冲器都用于这种无谓的重传,从而使通信子网的有效吞吐量下降。第3页，此课件共40页哦拥塞与死锁提供的负提供的负载载吞吐量吞吐量理想的拥塞控制拥塞拥塞死锁（吞吐量死锁（吞吐量 =0=0）无拥塞控制实际的拥塞控制轻度轻度拥塞拥塞0(单位时间内输入给单位时间内输入给网络的分组数目网络的分组数目)(单位时间内从网络单位时间内从网络输出的分组数目输出的分组数目)第4页，此课件共40页哦区别区别流量控制流量控制只在只在一对一对给定的给定的发送方和接收方之间发送方和接收方之间，控

3、制发送，控制发送方不以超过接收方处理能力的速率发送数据。方不以超过接收方处理能力的速率发送数据。拥塞控制拥塞控制是一个是一个全局性全局性的过程，涉及到的过程，涉及到网络中所有的网络中所有的主机、主机、所有的路由器，以及与降低网络传输性能有关的所有因素。所有的路由器，以及与降低网络传输性能有关的所有因素。联系联系 流量控制限制了进入网络中的信息总量，可以在一定流量控制限制了进入网络中的信息总量，可以在一定程度上减缓拥塞的作用。程度上减缓拥塞的作用。拥塞控制与流量控制区别联系拥塞控制与流量控制区别联系第5页，此课件共40页哦拥塞控制策略拥塞控制策略策略一：开环控制方法策略一：开环控制方法。重在重在

4、预防预防，希望通过完美的设计来避免拥塞的发生，希望通过完美的设计来避免拥塞的发生 需精心设计网络的各个环节，尽可能减少不必要的数据重传和避免需精心设计网络的各个环节，尽可能减少不必要的数据重传和避免数据过分集中在某个局部，同时还要严格控制进入子网的数据量以及数数据过分集中在某个局部，同时还要严格控制进入子网的数据量以及数据流入的速度。据流入的速度。策略二策略二：闭环控制方法闭环控制方法。重在重在解决解决，在拥塞发生后设法控制和缓解拥塞。，在拥塞发生后设法控制和缓解拥塞。需监视拥塞的发生，网络中要定期收集一些性能参数，一旦需监视拥塞的发生，网络中要定期收集一些性能参数，一旦参数值超过一定的门限，

5、检测到拥塞的结点立即通知有关结点，参数值超过一定的门限，检测到拥塞的结点立即通知有关结点，以便采取措施。以便采取措施。第6页，此课件共40页哦通信量整形通信量整形目标：迫使分组按照预定的速率进入网中目标：迫使分组按照预定的速率进入网中漏桶算法漏桶算法基本思想基本思想：在主机和网络之间接入一个在主机和网络之间接入一个“漏桶漏桶”。无论主机以多大的速率发送分组，无论主机以多大的速率发送分组，“漏桶漏桶”中的分组总是以恒中的分组总是以恒定的速率注入网中。定的速率注入网中。如果主机发送过快，当如果主机发送过快，当“漏桶漏桶”满了之后，多余的分组即被满了之后，多余的分组即被丢弃。丢弃。优点优点：无论数据

6、量有多大，数据总是以平均速率发送。：无论数据量有多大，数据总是以平均速率发送。缺点缺点：漏桶满后数据会丢失。：漏桶满后数据会丢失。第7页，此课件共40页哦漏桶模型漏桶模型说明说明绿绿色色-未整形的流未整形的流量量紫紫色色-整形后的流量整形后的流量红红色色-丢失的分组丢失的分组第8页，此课件共40页哦漏桶的本质漏桶的本质 就是一个固定长度的分组队列，主机发送的就是一个固定长度的分组队列，主机发送的每一个分组都加入到队列中排队，如果队列满则每一个分组都加入到队列中排队，如果队列满则分组被丢弃，同时队列按照约定的速率向网络发分组被丢弃，同时队列按照约定的速率向网络发送分组。送分组。两种情况：两种情况

7、：分组长度固定分组长度固定让队列每隔一个固定的时间发送一个分组。让队列每隔一个固定的时间发送一个分组。分组长度可变分组长度可变规定队列每次可以发送的最大字节数。规定队列每次可以发送的最大字节数。第9页，此课件共40页哦令牌桶算法漏桶算法的缺点漏桶算法的缺点：数据总以平均速率发送，突发数据到来时不能较：数据总以平均速率发送，突发数据到来时不能较快给予响应，有时还会丢失数据。希望能改进快给予响应，有时还会丢失数据。希望能改进于是有于是有令牌桶算法令牌桶算法，特点：，特点：q令牌桶中装的令牌桶中装的不是分组而是不是分组而是令牌令牌。q桶中每隔桶中每隔t时间产生出一个令牌，当桶装满后，时间产生出一个令

8、牌，当桶装满后，随后产生的令牌就被丢弃。随后产生的令牌就被丢弃。q分组在桶外的缓冲区中等待发送，桶中有多少个令分组在桶外的缓冲区中等待发送，桶中有多少个令牌就允许发送多少个分组。牌就允许发送多少个分组。(也可以规定：一个令也可以规定：一个令牌表示允许发送牌表示允许发送 k k 个字节个字节)q每个令牌用后即销毁，当桶中没有令牌时必须停止每个令牌用后即销毁，当桶中没有令牌时必须停止发送。发送。第10页，此课件共40页哦令牌桶模型令牌桶模型 说明说明 绿绿色色-未整形的流量未整形的流量紫紫色色-整形后的流量整形后的流量红红色色-桶内令牌桶内令牌黄黄色色-丢失的令牌丢失的令牌 特点特点允许主机在空闲

9、时积累令牌，空闲时允许主机在空闲时积累令牌，空闲时间越长令牌积累就越多，当有突发数据到来间越长令牌积累就越多，当有突发数据到来时，一次允许发送的数据量就大，可以时，一次允许发送的数据量就大，可以较快地响应突发输入。较快地响应突发输入。另外，当令牌桶装满时，丢弃令牌而不丢弃另外，当令牌桶装满时，丢弃令牌而不丢弃分组，因而不会造成数据丢失分组，因而不会造成数据丢失第11页，此课件共40页哦令牌桶算法 算法实现算法实现如一个令牌表示允许发送一个分组，如一个令牌表示允许发送一个分组，令牌桶实际上就是一个令牌计数器。令牌桶实际上就是一个令牌计数器。如一个令牌表示允许发送如一个令牌表示允许发送 k k 个

10、字节，个字节，令牌桶实际上就是一个字节计数器。令牌桶实际上就是一个字节计数器。优点：丢弃令牌，但不会造成数据的丢失优点：丢弃令牌，但不会造成数据的丢失 缺点：有时突发数据量仍较大缺点：有时突发数据量仍较大 改进措施：改进措施：在令牌桶之后再加一个漏桶，并令漏桶的输出速率在令牌桶之后再加一个漏桶，并令漏桶的输出速率大于令牌桶的大于令牌桶的值但小于网络的峰值速率。值但小于网络的峰值速率。第12页，此课件共40页哦常见拥塞控制方法常见拥塞控制方法缓冲区预分配法缓冲区预分配法 该法用于虚电路分组交换网中。在建立虚电路时,让呼叫请求分组途经的节点为虚电路预先分配一个或多个数据缓冲区若某个节点缓冲器已被占

11、满,则呼叫请求分组另择路由,或者返回一个忙信号给呼叫者。这样,通过途经的各节点为每条虚电路开设的永久性缓冲区(直到虚电路拆除),就总能有空间来接纳并转送经过的分组分组丢弃法分组丢弃法 该法不必预先保留缓冲区,当缓冲区占满时,将到来的分组丢弃定额控制法定额控制法 这种方法在通信子网中设置适当数量的称做许可证的特殊信息,一部分许可证在通信子网开始工作前预先以某种策略分配给各个源节点,另一部分则在子网开始工作后在网中四处环游。当源节点要发送来自源端系统的分组时,它必须首先拥有许可证,并且每发送一个分组注销一张许可证。目的节点方则每收到一个分组并将其递交给目的端系统后,便生成一张许可证。这样便可确保子

12、网中分组数不会超过许可证的数量,从而防止了拥塞的发生第13页，此课件共40页哦二、基于的二、基于的TCP拥塞控制算法拥塞控制算法 由于TCP是目前Internet上应用广泛的传输层协议因此下面介绍TCP基于窗口的端到端的拥塞控制机制 实施拥塞控制是TCP的两个主要任务之一，由于IP层在发生拥塞时不向端系统提供任何显式的反馈信息，因而TCP拥塞控制采用的是基于窗口的端到端的闭环控制方式。第14页，此课件共40页哦基本概念基本概念拥塞窗口(cwnd):拥塞控制的关键参数，控制源端在拥塞情况下一次最多能发送多少数据包。通告窗口(awnd):接收端对源端发送窗口大小所做的限制，在建立连接时山接收方通过

13、ACK确认带给源端 慢启动阀值(ssthresh):拥塞控制中用来限制发送窗口大小的门限值，它是慢启动阶段与拥塞避免阶段的分界点，初始值设为65535 bytes或awnd的大小。回路响应时间(RTT):一个数据包从源端发送到接收端直至源端收到接收端R寸该数据包确认信息所经历的时间间隔。超时重传计数器(RTO):描述数据包从发送到失效的时间间隔，是源端用来判断数据报是否丢失和网络拥塞的重要参数，通常设为2RTT或SRTT第15页，此课件共40页哦加法增加乘法减少加法增加乘法减少(AIMD)窗口算法窗口算法在现有的TCP/IP 协议体系下，TCP拥塞控制机制主要基于加法增加乘法减少(AIMD)算

14、法。由于计算机计算能力和存储能力的提高，通告窗口一般都比较大，因此当前发送窗口的大小大多数情况下等于拥塞窗口的大小。第16页，此课件共40页哦AIMD 的具体工作过程为：的具体工作过程为：(1)源端每收到一个ACK，拥塞窗口按下式增加：IncrMSS(MSS/cwnd)(MSS 为分组大小)cwndcwndIncr 也就是如果每个发出的分组都在最近的RTT(往返时延)时间内获得确认，源端就将cwnd 增加1，即加法增加。(2)当发生超时，TCP 将超时看作拥塞的标志，并减小发 送速率。每发生一次超时，源端重新计算拥塞窗口值：cwndcwnd/2 也就是，一次超时，拥塞窗口值减为当前值的一半，即

15、乘法减少。第17页，此课件共40页哦TCP 拥塞控制的四个阶段拥塞控制的四个阶段启动阶段拥塞避免阶段快速重传阶段快速恢复阶段第18页，此课件共40页哦1启动阶段 当连接刚建立或超时时，进入慢启动阶段。当新建TCP 连接时，拥塞窗口(cwnd)被初始化为一个数据包大小(缺省为512或536bytes)。实际发送窗口win取拥塞窗口与接收方提供的通告窗口的较小值，即win=min(cwnd,awnd)，每收到一个ACK 确认，就增加一个数据包发送量，这样慢启动阶段cwnd 随RTT呈指数级增长(1个、2个、4个、8个)第19页，此课件共40页哦优点：慢启动采用逐渐增大cwnd 的方法，可以防止TC

16、P 在启动一个连接时向网络发送过多的数据包而造成不必要的数据丢失和网络拥塞，并且它还能够避免采用单纯的AIMD 算法造成的吞吐量增加过慢的问题为了防止cwnd 的无限制增长引起网络拥塞，引入一个状态变量：慢启动阈值ssthresh 当cwndssthresh 时，使用下面的拥塞避免算法，减缓cwnd 的增长速度。第20页，此课件共40页哦2拥塞避免阶段当TCP 源端发现超时或收到3 个相同的ACK 确认帧时，即认为网络将发生拥塞，此时进入拥塞避免阶段。在拥塞避免阶段，慢启动域值ssthresh 将被设置为当前cwnd 的一半，当发生超时时，cwnd 被置为初始值1。此时，如果cwnd=ssth

17、resh，则执行拥塞避免算法，即cwnd 在每次收到一个ACK 确认时只增加1/cwnd 个数据包。拥塞避免阶段cwnd 随RTT 呈线性增长。第21页，此课件共40页哦 算法描述如下：初始化:cwnd=1 ssthresh=65535bytes win=min(cwnd,awnd)当新的ACK确认到达时，执行以下算法:for every arrived packets if cwndssthresh cwnd+=1；慢启动 else cwnd+=SMSS*SMSS/cwnd;拥塞避免阶段 当检测到丢包时，发送方执行以下操作:ssthresh=maxmin(cwnd/2,awin),2;如果检

18、测到定时器超时，cwnd=1;其中SMSS是发送方的最大报文段长度.第22页，此课件共40页哦 从以上算法看出：在拥塞避免阶段，当数据包超时时，cwnd 被置为1，重新进入慢启动阶段，这会导致过大地减小发送窗口尺寸，降低TCP 连接的吞吐量。因此，引入了快速重传和快速恢复机制。第23页，此课件共40页哦3快速重传阶段当网络发生拥塞时，如果源端等待超时之后再进行拥塞控制，那么从出现拥塞到实施控制有一定的时延。除了超时之外，源端还可以使用重复ACK作为拥塞信号。源端在接收到重复ACK时并不能确定是由于分组丢失还是分组乱序产生的，通常假定如果是分组乱序，在目的端处理之前源端只可能收到一个或两个重复的

19、ACK;如果源端连续接收到三个或更多的重复ACK，表明网络中某处已经发生了拥塞，这时，源端不等到重传定时器超时就重发这个可能丢失的分组，这就是快速重传算法。第24页，此课件共40页哦在快速重传阶段，当源端收到3 个或3 个以上重复的ACK 时，就判定数据包丢失，同时ssthresh 设置为当前cwnd的一半，并重传丢失的包，进入快速恢复阶段。第25页，此课件共40页哦4快速恢复阶段当快速重传算法重传了可能丢失的分组之后，如果TCP重新进入慢启动阶段，将会使拥塞窗口减为1，重新开始探测网络带宽，从而严重影响网络吞吐量，因此快速恢复算法在快速重传之后转去执行拥塞避免算法，避免了过大地减小发送窗口而

20、导致的网络性能下降。第26页，此课件共40页哦在快速恢复阶段，每收到重复的ACK，则cwnd 加1；收到非重复ACK 时，置cwndssthresh，转入拥塞避免阶段；如果发生超时重传，则置ssthresh 为当前cwnd 的一半，cwnd1，重新进入慢启动阶段。第27页，此课件共40页哦算法描述如下：step 1:if (dupacks=3)ssthresh=max(2,cwnd/2);cwnd=ssthresh+3*segsize;step 2:重传丢失的分组 step 3:此后每收到一个重复的ACK确认时cwnd=cwnd+1 step 4:当收到对新发送数据的ACK确认时，cwnd=s

21、sthresh，这个ACK能够对那些在丢失的分组之后，第一个重复ACK之前发送的所有包进行确认第28页，此课件共40页哦三、典型三、典型TCP 拥塞控制算法拥塞控制算法 -Vegas 算法分析分析Vegas 算法以RTT 的变化作为拥塞信号，调节源端的发送速率。如果发现RTT 变大，Vegas 就认为网络发生拥塞，开始减小cwnd；如果RTT 变小，Vegas 则解除拥塞，再次增加cwnd。这样，在理想情况下，cwnd 值会稳定在一个合适的范围内。Vegas 的重传策略与上述算法也不同，它是在收到一个重复ACK 后，比较数据包发出的时间和当前时间，然后决定是否重发。这样能更及时地重传丢失的数据

22、包，提高响应速度。该算法采用RTT 的改变来判断网络的可用带宽，能较好的预测网络带宽的使用情况，其公平性、效率都较好。第29页，此课件共40页哦TCP Vegas中最重要的就是拥塞避免阶段，拥塞避免阶段主要是通过计算期望的吞吐量和实际的吞吐量之间的差值来决定如何改变发送窗口的大小，而期望的吞吐量与实际吞吐量之间的差值为:其中 代表传输延时，也是当缓存中数据包为空时的RTT值(BaseRTT),cwnd代表源端在每个往返时间(RTT)中允许发送窗口的大小，期望的吞吐量为cwnd/T，设r代表实际网络中的RTT，实际的吞吐量为cwnd/r第30页，此课件共40页哦由(3.1)式得到路由器缓存中的数

23、据包个数为 （1）TCP Vegas通过计算d值和两个参数 ,之间的关系来改变窗口,是两个常数，一般取1和3。表明如果缓存中数据包数目保持在 和 之间，所以TCP Vegas拥塞避免的目标就是要控制在路由器中的队列长度第31页，此课件共40页哦使用图的网络拓扑模型，即是由n个源端和n个目的端通过一段由两个路由器之间的链路而组成，由于源端的发送窗口在每个RRT只会变化一次，所以网络模型可以看成是离散的，采样时间是RRT，需要说明的是，RTT是随着网络情况的变化而变化的，不是一个固定的值第32页，此课件共40页哦假定各个连接的RTT都是相同的。用cwnd.(k)(1_m=ssthresh 时，Ta

24、hoe 进入拥塞避免阶段。第36页，此课件共40页哦(2)拥塞避免：限制传输过程中无限制的速率增长，避免由此可能导致的拥塞。cwnd 以线性方式增长。如果发生超时或者连续收到3 个重复ACK，Tahoe 认为发生了拥塞。对于超时，置ssthresh 为当前拥塞窗口的一半，cwnd=1，转入慢启动。如果收到3 个连续ACK，则Tahoe 进入快速重传阶段。第37页，此课件共40页哦(3)快速重传：根据3 个重复的应答报文来判断丢包，减少了超时重传的发生，加快了源端对拥塞的响应，使得拥塞能快速消除。立即重传丢失的分组，同时置ssthresh 为当前拥塞窗口的一半，cwnd=1，转入慢启动。Taho

25、e 算法存在着不足之处：在收到3 个重复ACK 或在超时的情况下，Tahoe 置cwnd 为1，然后进入慢启动阶段。这一方面会引起网络的激烈振荡，另一方面大大降低了网络的利用率。第38页，此课件共40页哦算法描述赋初值：Cwnd=1；Ssthresh=65535bytes;Win=min(cwnd,awnd)；Number=1;Loop:+number;If(cwnd=Ssthresh)Cwnd+=1 /*慢启动*/Else /*拥塞避免*/cwnd+=mss*(mss/cwnd)If(overtime)Ssthresh=(1/2)*cwnd;Cwnd=1;Goto loop;If number=3win=losscwnd;Ssthresh=1/2*cwnd;Cwnd=1;/*快速重传*/第39页，此课件共40页哦 谢谢！谢谢！第40页，此课件共40页哦