运输层的拥塞控制课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,课件制作人：谢希仁,#,课件制作人：谢希仁,计算机网络,第,7,章 运输层的拥塞控制,课件制作人：谢希仁计算机网络第 7 章 运输层的拥塞控制,1,课件制作人：谢希仁,四种拥塞控制的方法,慢开始,拥塞避免,快重传,快恢复,课件制作人：谢希仁四种拥塞控制的方法慢开始,2,课件制作人：谢希仁,两个参数,拥塞窗口,cwnd,：发送方维持的一个状态变量，拥塞窗口的大小取决于网络的拥塞程度，并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口。,慢开始门限,ssthresh,：其用法如下,当,cwnd ssthresh,时，停止使用慢开始算法而,改用拥塞避免算法,当,cwnd=ssthresh,时，既可使用慢开始算法，,也可使用拥塞避免算法。,课件制作人：谢希仁两个参数拥塞窗口cwnd：发送方维持的一个,3,课件制作人：谢希仁,慢开始算法的原理,由小到大逐渐增大发送窗口，也就是逐渐增大拥塞窗口；,在主机刚刚开始发送报文段时可先将,拥塞窗口,cwnd,设置为一个最大报文段,MSS,的数值；,在每收到一个对新的报文段的确认后，将拥塞窗口增加至多一个,MSS,的数值；,每经过一个传输轮次，,拥塞窗口,cwnd,就加倍；,用这样的方法逐步增大发送端的拥塞窗口,cwnd,，可以使分组注入到网络的速率更加合理。,课件制作人：谢希仁慢开始算法的原理 由小到大逐渐增大发送窗口,4,课件制作人：谢希仁,拥塞避免算法,条件：拥塞窗口,cwnd,慢开始门限,ssthresh,时，停止使用慢开始算法而改用拥塞避免算法；,原理：没经过一个往返时间,RRT,（即传输轮次），就把拥塞窗口,cwnd,加,1,，而不是加倍；,拥塞窗口,cwnd,按,线性,规律缓慢增长，比慢开始算法的拥塞窗口增长速率缓慢得多。,课件制作人：谢希仁拥塞避免算法条件：拥塞窗口cwnd 慢开,5,课件制作人：谢希仁,要点,无论在慢开始阶段还是拥塞避免阶段，只要发送方判断网络出现拥塞（,其依据就是没有按时收到确认,）：,要将,慢开始门限,ssthresh,设置为出现拥塞时的发送窗口值的一半（但不能小于,2,）,拥塞窗口,cwnd,重新设置为,1,，执行慢开始算法；,目的：迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕。,课件制作人：谢希仁要点无论在慢开始阶段还是拥塞避免阶段，只要,6,慢开始和拥塞避免算法的实现举例,当,TCP,连接进行初始化时，将,拥塞窗口,=1,。图中的窗口单位不使用字节而使用,报文段,。,慢开始门限的初始值设置为,16,个报文段，,即,ssthresh=16,。,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,线性规律增长,ssthresh=16,慢开始,慢开始,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,慢开始和拥塞避免算法的实现举例 当 TCP 连接进行初始化时,7,慢开始和拥塞避免算法的实现举例,在执行慢开始算法时，拥塞窗口,cwnd,的初始值为,1,，发送第一个报文段,M,0,。,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,线性规律增长,ssthresh=16,慢开始,慢开始,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,慢开始和拥塞避免算法的实现举例 在执行慢开始算法时，拥塞窗口,8,慢开始和拥塞避免算法的实现举例,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,线性规律增长,ssthresh=16,慢开始,慢开始,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,发送端收到,ACK,1,（确认,M,0,，期望收到,M,1,）后，将,cwnd,从,1,增大到,2,，于是发送端可以接着发送,M,1,和,M,2,两个报文段。,慢开始和拥塞避免算法的实现举例 24681012141618,9,慢开始和拥塞避免算法的实现举例,接收端发回,ACK,2,和,ACK,3,。发送端每收到一个对新报文段的确认,ACK,，就把发送端的拥塞窗口加,1,。现在发送端的,cwnd,从,2,增大到,4,，并可发送,M,4,M,6,共,4,个报文段。,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,线性规律增长,ssthresh=16,慢开始,慢开始,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,慢开始和拥塞避免算法的实现举例 接收端发回 ACK2 和 A,10,慢开始和拥塞避免算法的实现举例,发送端每收到一个对新报文段的确认,ACK,，就把发送端的拥塞窗口加,1,，因此拥塞窗口,cwnd,随着传输次数按,指数规律,增长。,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,线性规律增长,ssthresh=16,慢开始,慢开始,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,慢开始和拥塞避免算法的实现举例 发送端每收到一个对新报文段的,11,慢开始和拥塞避免算法的实现举例,当拥塞窗口,cwnd,增长到慢开始门限值,ssthresh,时（即当,cwnd=16,时），就改为执行拥塞避免算法，拥塞窗口按,线性规律,增长。,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,ssthresh=16,慢开始,慢开始,线性规律增长,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,慢开始和拥塞避免算法的实现举例 当拥塞窗口 cwnd 增长到,12,慢开始和拥塞避免算法的实现举例,假定拥塞窗口的数值增长到,24,时，网络出现超时（表明网络拥塞了）。,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,线性规律增长,ssthresh=16,慢开始,慢开始,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,慢开始和拥塞避免算法的实现举例 假定拥塞窗口的数值增长到 2,13,慢开始和拥塞避免算法的实现举例,更新后的,ssthresh,值变为,12,（即发送窗口数值,24,的一半），拥塞窗口再重新设置为,1,，并执行慢开始算法。,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,线性规律增长,ssthresh=16,慢开始,慢开始,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,慢开始和拥塞避免算法的实现举例 更新后的 ssthresh,14,慢开始和拥塞避免算法的实现举例,当,cwnd=12,时改为执行拥塞避免算法，拥塞窗口按按线性规律增长，每经过一个往返时延就增加一个,MSS,的大小。,2,4,6,8,10,12,14,16,18,20,22,0,0,4,8,12,16,20,24,传输次数,拥塞窗口,cwnd,进入拥塞避免,发生超时,指数规律增长,线性规律增长,ssthresh=16,慢开始,慢开始,拥塞避免,拥塞避免,更新后的,ssthresh=12,进入拥塞避免,慢开始和拥塞避免算法的实现举例 当 cwnd=12 时改,15,课件制作人：谢希仁,AIMI,算法,Additive Increase,加法增大,Multiplicative Decrease,乘法减小,课件制作人：谢希仁 AIMI算法 Add,16,课件制作人：谢希仁,乘法减小,(multiplicative decrease),“,乘法减小“是指不论在慢开始阶段还是拥塞避免阶段，只要出现一次超时（即出现一次网络拥塞），就把慢开始门限值,ssthresh,设置为当前的拥塞窗口值乘以,0.5,。,当网络频繁出现拥塞时，,ssthresh,值就下降得很快，以大大减少注入到网络中的分组数。,课件制作人：谢希仁乘法减小(multiplicative,17,课件制作人：谢希仁,加法增大,(additive increase),“,加法增大”是指执行拥塞避免算法后，当收到对所有报文段的确认就将拥塞窗口,cwnd,增加一个,MSS,大小，使拥塞窗口缓慢增大，以防止网络过早出现拥塞。,课件制作人：谢希仁加法增大(additive increa,18,课件制作人：谢希仁,必须强调指出,“,拥塞避免”并非指完全能够避免了拥塞。利用以上的措施要完全避免网络拥塞还是不可能的。,“拥塞避免”是说在拥塞避免阶段把拥塞窗口控制为按线性规律增长，使网络比较不容易出现拥塞。,课件制作人：谢希仁必须强调指出“拥塞避免”并非指完全能够避,19,课件制作人：谢希仁,快重传和快恢复,快重传算法首先要求接收方每接到一个,失效的报文段,后就立即发出重复确认（为的是使发送方及早知道报文段没有到达对方）而不要等待自己发送数据时才进行捎带确认。,快重传算法,规定：发送端,只要一连收到三个重复确认,ACK,即可断定有分组丢失了，就应立即重传对方尚未收到的即丢失的报文段，而不必继续等待为该报文段设置的重传计时器的到期。,由于发送方,尽早重传未被确认的报文段,，因此采用快重传后可以使整个网络的吞吐率提高约,20%,。,不难看出，快重传并非取消重传计时器，而是在某些情况下可更早地重传丢失的报文段。,课件制作人：谢希仁快重传和快恢复快重传算法首先要求接收方每接,20,快重传举例,M,1,M,2,ACK,2,ACK,3,M,4,主机,A,主机,B,B,确认,M,1,和,M,2,A,发送,M,1,和,M,2,A,收到了三个重复的确认,ACK,3,，就立即重传,M,3,，而不必等待超时重传。,M,3,丢失！,A,发送,M,3,但丢失了,A,发送,M,4,ACK,3,M,5,A,发送,M,5,ACK,3,B,发送第二个重复确认,ACK,3,M,6,A,发送,M,6,ACK,3,M,3,B,发送第三个重复确认,ACK,3,B,只能再次确认,M,2,(,因为,M,3,没有收到）,快重传举例M1,M2ACK2,ACK3M4主机 A主机,21,课件制作人：谢希仁,快恢复算法,与快重传配合使用,过程：,（,1,）发送方连续收到三个重复确认时，就执行,“,乘法减小,”,算法，把慢开始门限,ssthresh,减半，这是为了预防网络发生拥塞，请注意：接下去不执行慢开始算法（即拥塞窗口,cwnd,不设置为,1,）；,（,2,）而是把拥塞窗口,cwnd,设置为慢开始门限,ssrhresh,减半后的数值，然后开始执行拥塞避免算法（,“,加法增大,”,），使拥塞窗口缓慢地线性增大。,课件制作人：谢希仁快恢复算法与快重传配合使用,22,课件制作人：谢希仁,注意,在采用快恢复算法时，慢开始算法只是在,TCP,连接建立时和网络出现超时时才使用。见,P212,图,5-27,所示。,请做,P222,第,5-39,题,课件制作人：谢希仁注意 在采用快恢复算法时，慢开始算法只是在,23,课件制作人：谢希仁,书后作业,P220,5-13,5-21,（,1,）,5-23,5-28,5-38,5-39,5-41,5-46,课件制作人：谢