CH5-L14 拥塞控制-连接管理

1、第14讲 拥塞控制；连接管理 【第5章 传输层 （第4讲）】上讲小结（快速提问1）上讲的重点是什么？上讲要点复习（快速提问2）TCP 的主要特点 TCP 报文段首部的组成什么是面向字节流的控制方法序号、确认序号、窗 口的作用如何计算加权平均往返时间RTTS如何计算超时重传时间 RTO 流量控制的基本思想TCP如何实现流量控制TCP提高传输效率的措施本讲内容安排1. 拥塞控制 (5.8)1.1 拥塞控制的基本概念 (5.8.1) 1.2 TCP的拥塞控制方法(5.8.2) 1.2.1 拥塞窗口cwnd 1.2.2 慢开始和指数增长 1.2.3 线性增长的拥塞避免算法 1.2.4 提高效率的相关措

2、施：快重传和快恢复1.3 IP层的拥塞控制方法：随机早期检测 RED丢包策略 5.8.32 TCP 的传输连接管理 (5.9)2.1 传输连接的三个阶段 2.2 建立连接(5.9.1)2.3 TCP 的连接释放(5.9.2) 2.4 TCP 的有限状态机 (5.9.3) 本讲预习情况检查（快速提问3）什么是拥塞、拥塞控制拥塞控制与流量控制的关系拥塞控制所起的作用闭环的拥塞控制的主要环节TCP的拥塞控制方法的要点拥塞窗口 cwnd概念：传输轮次、 ssthresh 值慢开始+指数规律增长“加法增大”的拥塞避免“乘法减小”的状态转换传输连接的三个阶段 三次握手：连接请求、确认报文、再次确认TCP

3、的连接释放1. 拥塞控制 (5.8)1.1 拥塞控制的基本概念 (5.8.1)1.1.1 什么是拥塞(congestion) ：在某段时间，对网络中某资源的需求超过该资源能提供的可用部分，整个网络的吞吐量随输入负荷的增大而下降（网络的性能变坏）产生了拥塞 输入的负载吞吐量0拥塞轻度拥塞： 输入负载增加的快，网络吞吐量增长的慢拥塞：网络的吞吐量随着输入负载的增加而下降死锁：网络的吞吐量降为0轻度拥塞输入的负载吞吐量0死锁（吞吐量 = 0）没有拥塞控制的情况拥塞拥塞控制检测、避免、缓解拥塞的措施检测是否发生拥塞，如，记录超时重传的包的数目若较多，减少源站发送数据的速率合理调度资源，避免和缓解拥塞如

4、，需要丢弃分组时，优先丢弃哪些分组拥塞控制的作用 提供的负载吞吐量理想的拥塞控制实际的拥塞控制0死锁（吞吐量 = 0）无拥塞控制拥塞轻度拥塞1.1.2 拥塞控制的一般原理 分析：出现资源拥塞的条件： 对资源需求的总和 可用资源 (5-7) 注意，简单地增加资源，不一定能避免拥塞。如，只增加带宽，造成缓存和CPU资源更缺乏。如，增加A站的缓存，大量分组到达A时，存储等待时间很长，引起源站更多的超时重发，使网络中的负载更重。即，拥塞是全局性、综合性问题拥塞控制的难度大是动态的、全局的、综合的问题。拥塞具有“恶性循环”的可能：与交通类似：开始轻度堵车车速降低占用更多的道路资源堵车加剧部分资源的不足，

5、引起其它资源消耗增加如，高速网络，出现缓存不够而造成丢包 重发需要更多的缓存和带宽（资源的不足）拥塞控制需要开销，占用网络资源， 本身可能引起或恶化拥塞，甚至死锁检测是否发生拥塞反馈拥塞信息二类拥塞控制开环控制闭环控制开环控制开环控制方法：设计网络时，事先考虑有关发生拥塞的因素，力求网络在工作时不产生拥塞。 何时接受新的流量何时开始丢弃分组，丢弃哪些分组流量如何分配，等如，通信量整形法：数据包到达较快时，最多以一种预定的速率转发。闭环控制 基于反馈的思想：网络运行时，检测是否发生或可能将发生拥塞，相应地采取必要措施预防或缓解拥塞。三个主要步骤： 监测网络系统，检测何时、何处发生拥塞，如：检测平

6、均包延迟、平均队列长度；检测超时重传的包的数目、重传次数;检测缺乏缓冲区造成的丢包率；将拥塞发生的信息传送到可采取行动的地方。如：发送拥塞通知到源站；调整网络系统的运行以解决出现的问题。如， 源站放缓发送数据注意：检测拥塞信息、反馈拥塞信息，都占用网络资源，处理不好，可能又引起、或恶化拥塞。拥塞控制与流量控制的关系 类似降低发包速率：既是流量控制的主要措施， 也是拥塞控制的重要措施区别：流量控制是给定的发送端和接收端之间的点对点通信量的控制。控制发送PDU的速率，使接收端来得及接收。 拥塞控制是一个全局性的过程，涉及到所有的主机、所有的路由器多种资源（信道带宽、缓存、处理能力）1.2 TCP的

7、拥塞控制方法(5.8.2)主要包括拥塞窗口 cwnd的概念拥塞窗口的基本控制算法慢开始和指数增大拥塞避免：加法增大线性增长乘法减小（阈值的变化）改进快重传快恢复本节是难点，注意理解一些概念：拥塞窗口 cwnd传输轮次ssthresh 值乘法减小1.2.1 拥塞窗口cwnd (congestion window)对比通知窗口：描述差错控制、流量控制的状态变量（上节介绍）拥塞窗口：描述拥塞控制的状态变量。拥塞窗口大小随网络拥塞程度动态变化，原则是：网络没有出现拥塞，增大拥塞窗口 (允许发送更多的报文）只要网络出现拥塞，就减小拥塞窗口 (减少注入到网络中的报文数)。 发送方最终的发送窗口min(拥塞

8、窗口，通知窗口)区别：通知窗口：由接收端根据接收能力调整（以字节为单位）拥塞窗口：由发送方根据拥塞状态调整（以MSS为单位）为了便于讨论，现在假定通知窗口足够大， 即：发送窗口大小取决于拥塞窗口拥塞窗口congestion window ，记为：cwnd如何发现网络发生拥塞“猜测”：发送方超时（没有按时收到确认）， 就认为网络出现拥塞即：信道误码率足够小时， 超时的主要原因是由于拥塞没有及时到达动态调整拥塞窗口的基本思想初始保守开始：cwnd很小（取1）：慢开始算法（ 避免拥塞：避免新的TCP连接向网络大量发送数据）网络没有出现拥塞时，应该增大拥塞窗口，提高发送效率， 二种情况：快速增长：指数

9、增长慢速增长：线性增长设一个状态变量(阈值)ssthresh，称为慢开始门限， 控制cwnd的增长方式ssthresh初值为M，单位：报文段(MSS)，例，M16当cwnd较小(cwnd 门限)时，采用“线性增长” 拥塞避免网络出现拥塞时，应该减小拥塞窗口，消除拥塞， 二个操作：调整门限ssthreshcwnd*0.5 （乘法减小）急速减小拥塞窗口： cwnd重新回到1（慢开始算法）“传输轮次” (transmission round)的概念传输层通信：一般情况发送时间小于往返时间 RTT传输轮次：把发送窗口所允许发送的报文都连续发送出去，并收到了对这些报文的最后一个字节的确认，为一个传输伦次

10、。一个传输轮次经历的时间大约是往返时间 RTT。即：一个轮次可以且只能传输一个窗口的数据发送方接收方发送 M1 确认 M1cwnd = 1 发送 M8M15cwnd = 8 tt轮次 1发送 M2M3 确认 M2M3 cwnd = 2 轮次 2发送 M4M7 确认 M4M7 cwnd = 4 轮次 3一个轮次可以传输一个窗口的数据2216控制过程初览：每个周期二个阶段“乘法减小”24681012141618200048122024拥塞窗口 cwnd新的 ssthresh 值网络拥塞ssthresh 初始值慢开始慢开始指数增长拥塞避免“加法增长”拥塞避免“加法增长”传输轮次慢开始指数增长一个调整

11、周期的二个阶段一个调整周期1.2.2 慢开始和指数增长 221624681012141618200048122024拥塞窗口 cwndssthresh 的初始值传输轮次慢开始拥塞窗口 cwnd 置为 1，发送第一个报文段 M0。 慢开始和指数增长（续）发送端每收到一个报文的确认 ， cwnd 加 1 （增加一个报文大小）。 221624681012141618200048122024拥塞窗口 cwnd指数规律增长ssthresh 的初始值传输轮次慢开始拥塞窗口 cwnd 置为 1，发送第一个报文段 M0。 难点：窗口门限时，cwnd是指数增长(续)发送端每收到一个确认 ， cwnd 加 1：C

12、wnd1时，一个 “传输轮次”只能发送一个报文，只能收到一个确认cwnd从 1 增大到2Cwnd2时，一个 “传输轮次”可以发送二个报文，可以收到二个确认cwnd从 2增大到4Cwnd4时，一个 “传输轮次”可以发送四个报文，可以收到四个确认cwnd从 4增大到8cwnd 随着“传输轮次”按指数规律增长。 慢开始和指数增长（续）发送端每收到一个报文的确认 ， cwnd 加 1 （增加一个报文大小）。 221624681012141618200048122024拥塞窗口 cwnd指数规律增长ssthresh 的初始值传输轮次慢开始1.2.3 线性增长的拥塞避免算法 当 cwnd 增长到门限值 时

13、，转入拥塞避免算法，每个“传输轮次” cwnd 加 1，cwnd按线性规律增长。221624681012141618200048122024拥塞窗口 cwnd比较：指数规律增长ssthresh 的初始值慢开始拥塞避免“加法增大”传输轮次加法增大(additive increase) 比较发送端每收到一个确认 ， cwnd 加 1指数增长一个往返时间，收到cwnd个确认，所以， cwnd增大一倍发送端收到cwnd内所有确认 ， cwnd 加 1 一个传输伦次，cwnd 加 1 线性增大防止网络过早出现拥塞说明：“拥塞避免”不可能完全能够避免了拥塞。按线性规律增长，减小拥塞的可能性22162468

14、1012141618200048122024拥塞窗口 cwnd超时，认为出现拥塞ssthresh 的初始值慢开始指数增长拥塞避免+“加法增大”发现拥塞时的调整：退回慢开始 网络出现超时，表明网络拥塞了，二个操作： 1）“乘法减小”更新 ssthresh (取cwnd当前值的一半， 即，乘0.5 ）；2）拥塞窗口cwnd重新设置为 1，转入慢开始算法传输轮次新的 ssthresh 值ssthresh 值“乘法减小”重新慢启动221624681012141618200048122024拥塞窗口 cwnd新的 ssthresh 值网络拥塞指数规律增长ssthresh 的初始值慢开始慢开始拥塞避免“加

15、法增大”重新开始下一趟调整cwnd ssthresh (12) 时，慢开始算法，指数增长。cwnd = ssthresh (12) 时，又改为执行拥塞避免算法。传输轮次拥塞避免“加法增大”“乘法减小”1.2.4 提高效率的相关措施：快重传和快恢复接收方每收到一个失序的报文段后就立即发出重复确认，让发送方及早知道有报文段没有到达对方。 发送方收到连续三个重复确认时快重传：立即重传对方尚未收到的报文段。不等到“超时”时间到才重发 快恢复：执行“乘法减小”算法，把慢开始门限 ssthresh 减半cwnd置为 ssthresh 减半后的数值(不置为 1)直接进入“加法增大”的拥塞避免阶段 (没有指数

16、增大阶段)（TCP Reno版本）快重传举例发送方接收方发送 M1 确认 M1t 确认 M2 发送 M2发送 M3发送 M4 ？发送 M5发送 M6 重复确认 M2 立即重传 M3 重复确认 M2 重复确认 M2 t发送 M7收到三个连续的对 M2 的重复确认立即重传 M3丢失 M2 M1 M3 M4 M5 M6 M7 M3 24快恢复：从连续收到三个重复的确认转入拥塞避免 2468101214161820220048121620传输轮次拥塞窗口 cwnd慢开始ssthresh 的初始值拥塞避免“加法增大”TCP Tahoe 版本(已废弃不用）慢开始收到 3 个重复的确认执行快重传算法比较“乘

17、法减小”新的 ssthresh 值拥塞避免“加法增大”TCP Reno版本快恢复说明：发送方监测到“超时”时，仍然采用慢启动算法（即：只有TCP连接建立时和超时，才采用慢启动算法）发送窗口的上限值接收方窗口 rwnd 、拥塞窗口 cwnd 最终的发送窗口的上限值 Min rwnd, cwnd (5-8)当 rwnd cwnd 时， 是接收方的接收能力限制发送窗口的最大值。当 cwnd rwnd 时， 是网络的拥塞限制发送窗口的最大值。 1.3 随机早期检测 RED丢包策略 5.8.3拥塞控制是复杂问题，要从多层加以控制传输层如，TCP的拥塞窗口网络层路由协议：有拥塞控制功能的路由选择算法IP层

18、的丢包策略：随机早期检测 RED (Random Early Discard/Drop/Detection)：网络层的FIFO队列+尾部丢弃策略的问题网络层的FIFO队列+尾部丢弃策略的不足：一连串分组的丢失多个TCP连接同时将发送窗口缩小为1全网通信量大幅下降网络迅速恢复当网络恢复后，通信量又突然大幅增加。改进：IP层将“尾部丢弃策略”改为“随机早期丢弃 ”当队列超过一定长度之后，开始将包少量丢弃以概率 p 丢弃RED 将路由器的到达队列划分成为三个区域 当队列超过一定长度之后，开始将包少量丢弃从队首发送队列最大长度分组到达排队丢弃以概率 p 丢弃随机早期丢弃 RED每个队列保持二个参数队列

19、长度最小门限THmin队列长度最大门限THmax经验数据：THmax = 2*THmin 每到达一个数据报计算平均队列长度LAV丢包策略若LAV THmax ，丢弃分组，丢弃概率 p = 1若THmin LAV THmax， 0 丢弃概率 p pmax (按概率p丢弃，1p的概率将分组存入队列）RED 将路由器的到达队列划分成为三个区域 效果：队列超过THmin之后，少量丢包，使少量TCP连接减小拥塞窗口，避免发生拥塞从队首发送最小门限 THmin最大门限 THmax分组到达平均队列长度 Lav排队丢弃以概率 p 丢弃为什么用平均队列长度计算机通信的“突发性”， 按瞬时队列长度丢包可能引起不必

20、要的丢包。如短时的突发数据，瞬时队列长度可能超过THmin， 但实际的上不会使队列溢出LAV=(1- )* LAV+ *当前队列长度 （0 1）队列长度时间瞬时队列长度平均队列长度瞬时队列长度和平均队列长度的区别丢弃概率 p 与 THmin 和 Thmax 的关系 最小门限 THmin最大门限 THmax平均队列长度 Lav分组丢弃概率 p1.00pmax按线性规律变化，从 0 变到 pmax （ pmax可以实现设定）概率 p的计算方法改进之一（p215）改进思路：使丢弃概率不仅与平均队列长度有关，还与“连续没有被丢弃的数据报的个数count”有关避免分组的丢弃过于集中改进前，过渡期的计算公

21、式重写如下：ptemp= pmax*(Lav-THmin)/(THmax-THmin)改进算法：p= ptemp /(1-count* ptemp)2 TCP 的传输连接管理 (5.9)2.1 传输连接的三个阶段 可靠通信有三个阶段： 连接建立、数据传送和连接释放。连接建立过程中要解决三个问题：使每一方能够确知对方的存在。允许双方协商一些参数,如,最大报文段长度，最大窗口大小，服务质量等。为传输实体分配资源,如,缓存大小，连接表中的项目等。 传输连接管理： 使传输连接的建立和释放都能正常地进行。 客户服务器方式 TCP 连接的建立都是采用客户服务器方式。主动发起连接建立的应用进程叫做客户(cl

22、ient)。被动等待连接建立的应用进程叫做服务器(server)。TCP首部20字节固定首部目 的 端 口数据偏移检 验 和选 项 （长 度 可 变）源 端 口序 号 seq 紧 急 指 针窗 口确 认 号 ack保 留FINSYNRSTPSHACKURG位 0 8 16 24 31填 充同步 SYN = 1 ：表示这是一个连接请求或连接接受报文。 终止 FIN (FINis)1：要求释放传输连接。2.2 建立连接(5.9.1)数据链路层相邻二点建立连接，可以估计连接请求帧延时，能准确判断是否丢失。在传输层不相邻二点建立连接，连接请求在一个甚至多个网络中存转，二次(联络)握手建立连接存在的问题

23、延时难以估计：延迟的重复连接请求错误的连接二次握手建立连接的问题主机A请求建立连接cq1超时，主机A再次请求建立连接主机A收到主机B的应答， 连接成功主机A,B之间通信主机A请求释放连接主机A收到主机B的应答 释放成功主机B收到主机A的、迟到的第一次建立连接请求主机B 接受建立连接请求主机B 发送报文段，主机A不接受主机A主机BTCP 的连接建立：第一次握手SYN = 1, seq = xCLOSEDCLOSED主动打开被动打开AB客户服务器A 的 TCP 向 B 发出连接请求报文段:同步位 SYN = 1，请求建立连接序号 seq = x，本站将传送的第一个数据字节的序号是 x。LISTEN

24、SYN-SENTA进入“同步已发送”状态B进入“监听”状态 TCP 的连接建立：第二次握手SYN = 1, seq = xCLOSEDCLOSED主动打开被动打开AB客户服务器SYN = 1, ACK = 1, seq = y, ack= x 1LISTENSYN-SENTSYN-RCVDB 收到连接请求报文段，如同意，则发回确认报文： SYN = 1、 ACK = 1，确认号ack = x 1，序号 seq = y。B进入“同步已收到”状态 TCP 的连接建立：第三次握手SYN = 1, seq = xCLOSEDCLOSED主动打开被动打开AB客户服务器SYN = 1, ACK = 1,

25、seq = y, ack= x 1LISTENSYN-SENTSYN-RCVDACK = 1, seq = x + 1, ack = y 1ESTAB-LISHEDA 收到确认报文后向 B 给出确认首部 ACK = 1、确认号 ack = y 1。A 的 TCP 通知上层应用进程，连接已经建立。A进入连接已建立(ESTABLISHED)状态 TCP 的连接建立：第三次握手SYN = 1, seq = xCLOSEDCLOSED主动打开被动打开AB客户服务器SYN = 1, ACK = 1, seq = y, ack= x 1LISTENSYN-SENTSYN-RCVDACK = 1, seq

26、= x + 1, ack = y 1ESTAB-LISHEDB 的 TCP 收到主机 A 的确认后，也通知其上层 应用进程：TCP 连接已经建立。进入连接已建立(ESTABLISHED)状态ESTAB-LISHED数据传送2.3 TCP 的连接释放(5.9.2)数据传输结束后，通信的双方都可释放连接。提出释放的一方为客户端。两个方向需要分别释放一个方向释放后，称为半关闭状态。FIN = 1, seq = uCLOSED主动关闭数据传送ESTAB-LISHEDESTAB-LISHEDAB客户服务器CLOSED 现在 A 不再发送数据，主动关闭 TCP连接。 A 在连接释放报文段首部的 FIN =

27、 1，等待 B 的确认。TCP 的连接释放(5.9.2)FIN = 1, seq = uACK = 1, seq = v, ack= u 1主动关闭数据传送通知应用进程ESTAB-LISHEDESTAB-LISHEDAB客户服务器 B 发出确认：确认号 ack = u 1，序号 seq = v。 TCP 服务器进程通知高层应用进程。 从 A 到 B 这个方向的连接就释放了，TCP 连接 处于半关闭状态。B 若发送数据，A 仍要接收。TCP 的连接释放FIN = 1, seq = uACK = 1, seq = v, ack= u 1FIN = 1, ACK = 1, seq = w, ack=

28、 u 1主动关闭被动关闭数据传送通知应用进程ESTAB-LISHEDESTAB-LISHEDAB客户服务器数据传送 若 B 也不需向 A 发送的数据， 也要释放连接：FIN1。 TCP 的连接释放FIN = 1, seq = uACK = 1, seq = v, ack= u 1FIN = 1, ACK = 1, seq = w, ack= u 1主动关闭被动关闭数据传送通知应用进程ESTAB-LISHEDESTAB-LISHEDAB客户服务器数据传送 A 收到连接释放报文段后，必须发出确认报文段： ACK = 1，确认号 ack w 1，序号 seq = u + 1 。 ACK = 1, s

29、eq = u + 1, ack = w 1TCP 的连接释放 B 收到A 确认报文段，释放完成，进入CLOSED状态。但，A发出确认报文后 ，必须经过时间 2MSL 后才真正释放等待 2MSLA 必须等待 2MSL 的时间保证 A 发送的最后一个 ACK 报文段能够到达 B如果该报文丢失。B会重传FIN+ACK报文，A在2MSL时间内可以收到这个重传报文，重发ACK 报文防止 “已失效的连接请求报文段”出现在本连接中。2MSL约4分钟，是较长的时间。经过 2MSL时间，本连接持续的时间内所产生的所有报文段，都将从网络中消失。这样就使下一个新的连接中不会出现这种旧的连接请求报文段。CLOSEDF

30、IN = 1, seq = uACK = 1, seq = v, ack= u 1ACK = 1, seq = u + 1, ack = w 1FIN = 1, ACK = 1, seq = w, ack= u 1FIN-WAIT-1CLOSE-WAITFIN-WAIT-2LAST-ACK等待 2MSLTIME-WAIT主动关闭被动关闭数据传送通知应用进程ESTAB-LISHEDESTAB-LISHEDAB客户服务器数据传送CLOSEDTCP 的连接释放 TCP 连接释放过程中状态的变化 自学：TCP 的有限状态机 (5.9.3)有限状态机是一种用来进行对象行为建模的工具，描述对象在它的生命周

31、期内所经历的状态序列，以及如何响应来自外界的各种事件，状态之间如何转换。由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成TCP的有限状态机 CLOSEDESTABLISHEDLISTENCLOSE_WAITFIN_WAIT_1SYN_RCVDFIN_WAIT_2CLOSINGTIME_WAITSYN_SENTLAST_ACK主动打开被动打开被动关闭主动关闭起点被动打开主动打开 发送 SYN同时打开收到 SYN，发送 SYN, ACK收到 ACK数据传送 阶段 关闭发送 FIN 关闭发送 FIN 关闭发送 FIN收到 RST 收到 SYN发送 SYN, ACK 关

32、闭或超时收到 ACK 收到 SYN, ACK发送 ACK收到 ACK收到 ACK收到 FIN发送 ACK收到 FIN, ACK 发送 ACK收到 FIN发送 ACK同时关闭收到 FIN发送 ACK发送 SYN定时经过两倍报文段寿命后关闭 每一个方框都是可能具有的状态； 方框中的大写英文字符串：状态名状态之间的箭头：表示可能发生的状态变迁。粗线箭头：表示对客户进程的正常变迁。虚线箭头：表示对服务器进程的正常变迁。细线箭头：表示异常变迁。箭头旁边的文字： 表明引起变迁的原因或，表明发生状态变迁后又出现什么动作。TCP的有限状态机 CLOSEDESTABLISHEDLISTENCLOSE_WAITFIN_WAIT_1SYN_RCVDFIN_WAIT_2TIME_WAITSYN_SENTLAST_ACK主动打开被动打开被动关闭主动关闭起点被动打开主动打开 发送 SYN收到 ACK数据传送 阶段 关闭发送 FIN ACK 关闭发送 FIN 收到 S