快恢复算法及其作用

⑴ tcp如何实现拥塞控制

TCP拥塞控制是传输控制协议（英语：Transmission Control Protocol，缩写TCP）避免网络拥塞的算法，是互联网上主要的一个拥塞控制措施。它使用一套基于线增积减模式的多样化网络拥塞控制方法（包括慢启动和拥塞窗口等模式）来控制拥塞。在互联网上应用中有相当多的具体实现算法。

在TCP中，拥塞窗口（congestion window）是任何时刻内确定能被发送出去的字节数的控制因素之一，是阻止发送方至接收方之间的链路变得拥塞的手段。他是由发送方维护，通过估计链路的拥塞程度计算出来的，与由接收方维护的接收窗口大小并不冲突。

1、慢开始算法：

简单的说，开始传输时，传输的数据由小到大递增到一个值(即发送窗口由小到大(指数增长)逐渐增大到拥塞窗口的数值)。

2、拥塞避免算法：

数据发送出去，并发到接收方发回来的确认收到，拥塞窗口每次值加1地线性增大。

3、快重传算法：

数据传输时(数据被分成报文，每个报文都有个序号)，中间的一部分丢失接收方没收到，接收方连续接到后面的数据，则发回对丢失前的数据的重复确认，这样发送方就知道有部分数据丢失了，于是从丢失出重传数据。

4、快恢复算法：

快恢复是与快重传配合的算法，在发生数据丢失时，发送方收到接收方发回的三个重复确认信息时，就把每次传输的数据量减为原来的一半，拥塞窗口也修改为这个值,然后又开始拥塞避免的算法。

⑵ 简述拥塞控制的四种基本算法

慢开始,拥塞避免,快重传,快恢复.
首先要明白什么TCP协议可靠传输,还有什么是拥塞窗口:表示当前发送数据的上限,但是它会根据网络好坏状况动态改变.
慢开始:简单的说,开始传输时,传输的数据由小到大递增到一个值(即发送窗口由小到大(指数增长)逐渐增大到拥塞窗口的数值).
拥塞避免:数据发送出去,并发到接收方发回来的确认收到,拥塞窗口每次值加1地线性增大.
快重传:数据传输时(数据被分成报文,每个报文都有个序号),中间的一部分丢失接收方没收到,接收方连续接到后面的数据,则发回对丢失前的数据的重复确认,这样发送方就知道有部分数据丢失了,于是从丢失出重传数据.
快恢复:快恢复是与快重传配合的算法,在发生数据丢失时,发送方收到接收方发回的三个重复确认信息时,就把每次传输的数据量减为原来的一半,拥塞窗口也修改为这个值,然后又开始拥塞避免的算法.

⑶ 快重传和快恢复的简介

协议
在TCP/IP中，快速重传和恢复（fast retransmit and recovery，FRR）是一种拥塞控制算法，它能快速恢复丢失的数据包。没有FRR，如果数据包丢失了，TCP将会使用定时器来要求传输暂停。在暂停的这段时间内，没有新的或复制的数据包被发送。有了FRR，如果接收机接收到一个不按顺序的数据段，它会立即给发送机发送一个重复确认。如果发送机接收到三个重复确认，它会假定确认件指出的数据段丢失了，并立即重传这些丢失的数据段。有了FRR，就不会因为重传时要求的暂停被耽误。 当有单独的数据包丢失时，快速重传和恢复（FRR）能最有效地工作。当有多个数据信息包在某一段很短的时间内丢失时，它则不能很有效地工作。快速重传快速恢复算法是在4.3BSD Reno中提出的，并在RFC 2001和RFC2581中描述。 FRR也指误拒绝率（false rejection rate），一个在生物安全系统中使用的术语。

⑷ 在TCP的拥塞控制中,什么是慢开始、拥塞避免、快重传和快恢复算法

慢开始：在主机刚刚开始发送报文段时可先将拥塞窗口cwnd设置为一个最大报文段MSS的数值。在每收到一个对新的报文段的确认后，将拥塞窗口增加至多一个MSS的数值。

拥塞避免：当拥塞窗口值大于慢开始门限时，停止使用慢开始算法而改用拥塞避免算法。

快重传算法：发送端只要一连收到三个重复的ACK即可断定有分组丢失了，就应该立即重传丢手的报文段而不必继续等待为该报文段设置的重传计时器的超时。

接下来执行的不是慢启动算法而是拥塞避免算法。这就是快速恢复算法。.

防止拥塞的方法

（1）在传输层可采用：重传策略、乱序缓存策略、确认策略、流控制策略和确定超时策略。

（2）在网络层可采用：子网内部的虚电路与数据报策略、分组排队和服务策略、分组丢弃策略、路由算法和分组生存管理。

（3）在数据链路层可采用：重传策略、乱序缓存策略、确认策略和流控制策略。

⑸ [计算机网络之六] 传输层

  传输层向它上面的应用层提供通信服务，它属于面向通信部分的最高层，同时也是用户功能中的最底层。

  从传输层的角度，通信的真正端点并不是主机而是主机中的进程。

  传输层有 分用 和 复用 的功能。 “复用” 是指在发送方不同的应用进程都可以使用同一个运输层协议传送数据， “分用” 是指接收方的运输层在剥去报文的首部后能够把这些数据正确交付目的应用进程。

  网络层和运输层有明显的区别，网络层为主机之间提供逻辑通信，而运输层为应用进程之间提供端到端的逻辑通信。

知名端口号 ：0~1023
登记端口号 ：1024~49151
客户端短暂端口号 ：49152~65535

① 无连接。 发送数据之前不需要建立连接，因此减少了开销和发送数据之前的时延。
② 尽最大努力交付。 即不保证可靠交付，因此主机不需要维持复杂的连接状态表。
③ 面向报文的。 对应用层交下来的报文，既不合并，也不拆分，而是保留这些报文的边界，UDP 一次交付一个完整的报文。

  用户数据报 UDP 有两个字段：数据字段和首部字段。首部字段很简单，只有 8 个字节，由四个字段组成，每个字段的长度都是两个字节。各字段意义如下：

① 源端口 在需要对方回信时选用。不需要时可用全0。
② 目的端口 目的端口号。这在终点交付报文时必须使用。
③ 长度 用户数据报的长度，最小值为 8 （仅有首部）。
④ 检验和 检测用户数据报在传输中是否有错。有错就丢弃。

  用户数据报首部检验和的计算和校验都要计算出一个伪首部。

① 面向连接。

  应用程序在使用 TCP 协议之前，必须先建立 TCP 连接；传送数据完毕后，必须释放已经建立的 TCP 连接。类似于打电话：通话前要先拨号建立连接，通话结束后要挂机释放连接。

② 一对一。

  TCP 连接只能是点对点的（一对一）。

③ 可靠交付。

  通过 TCP 连接传送的数据，无差错、不丢失、不重复，并且按序到达。

④ 全双工通信。

  通信双方的应用进程在任何时候都能发送和接收数据，TCP 连接的两端都设有发送缓存和接收缓存，用来临时存放双向通信的数据。

⑤ 面向字节流。

  TCP 中的 “流” 指的是流入到进程或从进程流出的字节序列。

  “面向字节流” 的含义：虽然应用程序和 TCP 的交互式一次一个数据块（大小不等），但 TCP 把应用程序交下来的数据仅仅看成是一连串无结构的字节流。TCP 并不知道所传送的字节流的含义。TCP 不保证接收方应用程序锁收到的数据块和发送方应用程序所发出的数据块具有对应的大小关系。但接收方应用程序收到的字节流必须和发送方应用程序发出的字节流完全一样，当然接收方的应用程序必须有能力识别收到的字节流，把它还原成有意义的应用层数据。

  TCP 连接是协议软件提供的一种抽象，每一条 TCP 连接唯一地被通信两端的两个端点（即两个套接字）所确定，即：

  TCP 连接 ::= {socket1, socket2} = {(IP1: port1), (IP2: port2)}

  IP1 和 IP2 分别是两个端点主机的 IP 地址，port1 和 port2 分别是两端端点主机中的端口号。

  网络只能提供最大努力的服务，是不可靠的，因此 TCP 必须采用适当的措施才能使得两个运输层之间的通信变得可靠。当出现差错时让发送方重传出现差错的数据，同时在接收方来不及处理收到的数据时，及时告知发送方适当降低发送数据的速度，这样就可以在不可靠的传输信道实现可靠传输。

  ARQ（Auto Repeat-reQuest）：自动重传请求。

  发送方每发送完一个分组就停止发送，等待接收方确认，在收到确认后再发送下一个分组。
  A 是发送方，B 是接收方。

  A 每发送一个分组后，等待 B 对该分组的确认后，再接着发送下一个分组。

【发送方】A 发送的分组在传输过程中出错，可能是丢失了，也可能是分组受到干扰出错了
【接收方】这时 B 直接丢弃分组，什么也不做（也不通知 A 受到的分组有差错）。

【解决方案】发送方在每发送完一个分组时设置一个 超时计数器 ，只要超过一段时间仍然没有接收到确认，就认为刚才发送的分组丢失了，因而重传前面发送过的分组，这叫 超时重传 。反之在超时计时器到期之前收到了相应的确认，就撤销该超时计时器。

第一，A 在发送完一个分组后， 必须暂时保留已发送的分组的副本 （在发生超时重传时使用）。只有在收到相应的确认后才能清楚暂时保留的分组副本。

第二，分组和确认分组都必须进行 编号 。这样才能明确是哪一个发送出去的分组受到了确认，而哪一个分组还没有收到确认。

第三，超时计时器设置的 重传时间应当比数据在分组传输的平均往返时间更长一些 。

【发送方】超时重传时间内没有收到确认报文，无法确认是发送出错、丢失，还是接收方的确认丢失，超时计时器到期后就要重传。
【接收方】丢弃收到的重复分组，不向上层交付；向发送方发送确认。

【发送方】收下迟到的确认，并且丢弃

  发送方大部分时间都在等待确认，信道的利用率低

  使用流水线的 ARQ 可以提高信道利用率

【发送方】维持一个发送窗口，位于发送窗口内的分组都可连续发送出去，而不需要等待对方的确认。

回退N帧协议 ：如果发送方发送了多个分组，但中间的某个分组丢失了，这时接收方只能对丢失分组之前的分组发出确认，而发送方无法知道丢失分组及后面分组的接收情况，只好把丢失分组及后面的分组重传一次，这叫 Go-back-N ，表示需要再退回来重传已发送过的 N 个分组。

  前面 20 个字节固定，因此 TCP 首部最小长度是 20 字节。

  TCP 的滑动窗口以字节为单位，窗口后沿的部分表示已发送且已收到通知，窗口里的序号表示允许发送的序号，窗口前沿之前的数据暂时不允许发送，需要等待收到接收方的确认后前沿往前移才可发送。

描述一个发送窗口需要三个指针：P1、P2 和 P3，如图所示：

  小于 P1 的是已发送并已收到确认的部分，而大于 P3 的是不允许发送的部分。

  P3 - P1 = A 的发送窗口

  P2 - P1 = 已发送但尚未收到确认的字节数

  P3 - P2 = 允许发送但当前尚未发送的字节数（又称为 可用窗口 或 有效窗口 ）

  接收方 B 接收窗口大小为20，因为未收到 31 的数据，即使已收到后面的序号 32、33 的数据，返回的确认号仍然是 31。

  现在接收方收到了 31、32、33，并返回确认号 33，接收窗口往前滑动 3 个序号，发送方接收到确认，发送窗口也向前滑动 3 个序号大小，现在 A 可以发送序号 51~53 的数据了。

  当发送方将发送窗口内的数据都发送出去，但是接收方的确认可能由于网络拥塞滞留，这时发送方发送窗口已满，可用窗口为 0，只能等待接收方的确认报文到达。

  TCP 为了保证可靠传输，要求必须受到对已发送报文的确认，如果超过一定时间未受到确认报文，则重传已发送的报文。这个时间就叫 超时重传时间 ，很明显超时重传时间的大小设置应该更贴近网络的实际情况，如果网络状况好，就设短一点，否则使网络的空闲时间增大，降低了传输效率；网络差就设长一点，否则会引起很多不必要的重传，使网络负荷增大。

  TCP 采用了一种自适应的算法：

  RTT（报文段的往返时间）、RTTs（加权平均往返时间），RTTs 的计算公式：

RTTd（RTT 的偏差的加权平均值）、RTO（RetransmissionTime-Out 超时重传时间）:

【场景】TCP 的接收方在接收对方发送过来的数据字节流的序号不连续，形成一些不连续的字节块，如果简单按照回退N帧协议处理，意味着要重传第一个未收到的序号数据块及之后的数据，如果能通知发送方已收到了哪些数据（选择确认），就可以让发送方只发送接收方未收到的数据。

  流量控制就是让发送方的发送速率不要太快，要让接收方来得及接收。

  当发送方收到接收方通知，将窗口缩小为 0 时，发送方将暂时不能发送数据了，必须等接收方通知更新接收窗口大小，但是这个通知又有可能丢失，导致发送方没收到通知。

  为了避免双方互相等待死锁，TCP 为每个链接设有一个 持续计时器 ，只要 TCP 连接的一方收到对方的零窗口通知，就启动持续计时器。若持续计时器设置的时间到期，就发送一个零窗口 探测报文段 （仅携带 1 字节的数据），而对方就在确认这个探测报文段时给出了现在的窗口值。如果窗口仍然是零，那么受到这个报文段的一方就重新设置持续计时器；如果窗口不是零，那么死锁的僵局就可以打破了。

【优点】提高网络利用率
【缺点】可能会发生某种程度的延迟

【场景】接收数据的主机如果每次都立刻回复确认应答的话，可能会返回一个较小的窗口，因为接收方刚接收完数，缓冲区已满。

【糊涂窗口综合征问题】
TCP 接收方缓存已满，而交互式的应用进程一次只从接收缓存中读取 1 个字节（这样就使接收缓存空间仅腾出 1 个字节），然后向发送方发送确认，并把窗口设置为 1 个字节（但发送的数据报是 40 字节长，TCP 首部 + IP 数据报首部）。接着，发送方又发来 1 个字节的数据（注意发送方发送的 IP 数据报是 41 字节长）。接收方发回确认，仍然将窗口设置为 1 个字节。这样进行下去，使网络的效率很低。

  TCP 文件传输中，就采用了两个数据段返回一次确认应答，并且等待一定时间后没有其他数据包到达时也依然发送确认应答。

  当对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏，这种情况就叫做 拥塞 。

  慢开始（slow-start）、拥塞避免（congestion avoidance）、快重传（fast retransmit）和快恢复（fast recovery）。

【算法思路】

  当主机开始发送数据时，由于并不清楚网络的负荷情况，所以如果立即把大量数据字节注入网络，那么就有可能引起网络发生拥塞。较好的方法是先探测一下，即 由小到大逐渐增大发送窗口 ，也就是说， 由小到大逐渐增大拥塞窗口数值 。

【处理过程】

   慢开始门限值 ssthresh 决定了拥塞窗口达到多大时要执行什么算法。

① 当 cwnd < ssthresh 时，使用慢开始算法；
② 当 cwnd > ssthresh 时，停止使用慢开始算法而改用拥塞避免算法；
③ 当 cwnd = ssthresh 时，既可使用慢开始算法，也可使用拥塞避免算法。

  在拥塞窗口 cwnd 达到门限值之前，发送方每一轮次收到确认应答后，cwnd 就增大为原来的两倍；达到门限值后，执行拥塞避免算法。

PS. 慢开始只是表示初始发送数据少，不代表发送速率增长速度慢，实际上是指数级增长非常快。

【算法思路】

  让拥塞窗口 cwnd 缓慢地增大，即每经过一个往返时间 RTT 就把发送方的拥塞窗口 cwnd 加 1，而不是像慢开始阶段那样加倍增长。拥塞避免阶段有 “加法增大” 的特点，按线性规律缓慢增长，使网络比较不容易出现拥塞 。

【处理过程】

  在执行拥塞避免算法阶段，当网络出现超时时，发送方判断为网络拥塞，调整门限值为当前拥塞窗口的一半，即 ssthresh = cwnd / 2，同时拥塞窗口重置为 1，即 cwnd = 1，进入慢开始阶段。

【算法原理】

① 快重传

【场景】有时，个别报文段会在网络中丢失，但实际上网络并未发生拥塞。如果发送方迟迟收不到确认，就会产生超时，就会误认为网络发生了拥塞，导致发送方错误地启动慢开始，把拥塞窗口 cwnd 又设置为 1，因而降低了传输效率。

【方案】接收方不要等待自己发送数据时才进行捎带确认，而是要立即发送确认，即使收到了失序的报文段也要立即发出对已收到的报文段的重复确认，当发送方 一连收到 3 个重复确认 ，就知道接收方确实没有收到某个报文段，因而应当 立即进行重传 。

② 快恢复：

  发送方知道只是丢失了个别的报文段，于是不启动慢开始，而是执行快恢复算法，调整发送方门限值 ssthresh = cwnd / 2，同时设置拥塞窗口 cwnd = ssthresh = 8，并开始执行拥塞避免算法。

拥塞控制的流程如下：

  拥塞窗口 cwnd，接收方窗口 rwnd， 发送方发送窗口的上限值 = Min[rwnd, cwnd] 。

① 当 rwnd < cwnd，接收方的接收能力限制发送方窗口大小；
② 当 cwnd < rwnd，网络的拥塞程度限制发送方窗口大小。

【问题背景】

  路由器采取分组丢弃策略，即按照 先进先出（FIFO） 规则处理分组，当队列已满时，则丢弃后面到达的分组，这叫 尾部丢弃策略 。

  丢失的分组会导致发送方出现超时重传，发送方转而执行慢开始算法，不同分组属于不同 TCP 连接，导致很多 TCP 同时进入慢开始状态，这种现象称为 全局同步 。

【解决方案】

  主动队列管理 AQM：不等到路由器的队列长度已经达到最大值时才不得不丢弃后面到达的分组，而是在队列长度达到某个警惕值时就主动丢弃到达的分组，这样就提醒了发送方放慢发送的速率，因而有可能使网络拥塞的程度减轻，甚至不出现网络拥塞。

  TCP 是面向连接的协议，运输连接有三个阶段： 连接建立、数据传送、连接释放 。

  TCP 连接建立过程要解决的几个问题：

① 使每一方能够确知对方的存在；
② 允许双方协商一些参数（如最大窗口值、是否使用窗口扩大选项和时间戳选项以及服务质量等）；
③ 能够对运输实体资源（如缓存大小、连接表中的项目等）进行分配。

  TCP 建立连接的过程叫做握手，握手需要在客户和服务器之间交换三个 TCP 报文段，即 三次握手 。

  最初客户端和服务端都处于 CLOSED（关闭） 状态，A（Client）主动打开连接，B（Server）被动打开连接。

  一开始，B 的 TCP 服务器进程先创建 传输控制块 TCB ，准备接受客户进程的连接请求。然后服务器进程就处于 LISTEN（收听）状态，等待客户端的连接请求。如有，即作出响应。

   第一次握手 ：A 的 TCP 客户进程也是首先创建传输控制块 TCB，准备接受客户进程的连接请求。然后在打算建立 TCP 连接时，向 B 发出连接请求报文段，这时首部中的同步位 SYN = 1，同时选择一个初始序号 seq = x。TCP 规定，SYN 报文段（即 SYN = 1 的报文段）不能携带数据，但要 消耗掉一个序号 。这时，TCP 客户进程进入 SYN-SENT（同步已发送） 状态。

   第二次握手 ：B 收到连接请求报文段后，如同意建立连接，则向 A 发送确认。在确认报文段中应把 SYN 位和 ACK 位都置 1，确认号是 ack = x + 1，同时也为自己选择一个初始序号 seq = y。请注意，这个报文段也不能携带数据，但同样 要消耗掉一个序号 。这时 TCP 服务器进程进入 SYN-RCVD（同步收到） 状态。

   第三次握手 ：TCP 客户进程收到 B 的确认后，还要向 B 给出确认。确认报文段的 ACK 置 1，确认号 ack = y + 1，而自己的序号 seq = x + 1。TCP 的标准规定，ACK 报文段可以携带数据。但 如果不携带数据则不消耗序号 ，在这种情况下，下一个数据报文段的序号仍是 seq = x + 1。这时，TCP 连接已经建立，A 进入 ESTABLISHED（已建立连接） 状态。当 B 收到 A 的确认后，也进入 ESTABLISHED（已建立连接）状态。

  数据传输结束后，通信的方法都可释放连接。现在 A 和 B 都处于 ESTABLISHED 状态。

   第一次挥手 ：A 的应用进程先向其 TCP 发出连接释放报文段，并停止再发送数据，主动关闭 TCP 连接。A 把连接释放报文段首部的终止控制位 FIN 置 1，其序号 seq = u，它等于前面已传送过的数据的最后一个字节的序号加 1。这时 A 进入 FIN-WAIT-1（终止等待 1）状态，等待 B 的确认。请注意，TCP 规定，FIN 报文段即使不携带数据，它也消耗掉一个序号。

   第二次挥手 ：B 收到连接释放报文后即发出确认，确认号是 ack = u + 1，而这个报文段自己的序号是 v，等于 B 前面已传送过的最后一个字节的序号加 1。然后 B 就进入 CLOSE-WAIT（关闭等待）状态。TCP 服务器进程这时应通知高层应用程序，因而从 A 到 B 这个方向的连接就释放了，这时的 TCP 连接处于半关闭（half-close）状态，即 A 已经没有数据要发送了，但 B 若发送数，A 仍要接收。也就是说，从 B 到 A 这个方向的连接并未关闭，这个状态可能会持续一段时间。A 收到来自 B 的确认后，就进入 FIN-WAIT-2（终止等待 2）状态，等待 B 发出的连接释放报文段。

   第三次挥手 ：若 B 已经没有要向 A 发送的数据，其应用进程就通知 TCP 释放连接。这时 B 发出的连接释放报文段必须使 FIN = 1。现假定 B 的序号为 w（在半关闭状态 B 可能又发送了一些数据）。B 还必须重复上次已发送过的确认号 ack = u + 1。这时 B 就进入 LAST-ACK（最后确认）状态，等待 A 的确认。

   第四次挥手 ：A 在收到 B 的连接释放报文段后，必须对此发出确认。在确认报文段中把 ACK 置 1，确认号 ack = w + 1，而自己的序号是 seq = u + 1（根据 TCP 标准，前面发送过的 FIN 报文段要消耗一个序号）。然后进入 TIME-WAIT（时间等待）状态。请注意，现在 TCP 连接还没有释放掉。必须经过时间等待计时器（TIME-WAIT timer）设置的时间 2MSL 后，A 才进入到 CLOSED 状态，然后撤销传输控制块，结束这次 TCP 连接。当然如果 B 一收到 A 的确认就进入 CLOSED 状态，然后撤销传输控制块。所以在释放连接时，B 结束 TCP 连接的时间要早于 A。

⑹ 快重传和快恢复的具体算法

(1) 当发送端收到连续三个重复的 ACK 时，就重新设置慢开始门限 ssthresh。
(2) 与慢开始不同之处是拥塞窗口 cwnd 不是设置为 1，而是设置为 ssthresh + 3 &acute; MSS。
(3) 若收到的重复的 ACK 为 n 个（n> 3），则将 cwnd 设置为 ssthresh + n&acute; MSS。
(4) 若发送窗口值还容许发送报文段，就按拥塞避免算法继续发送报文段。
(5) 若收到了确认新的报文段的 ACK，就将 cwnd 缩小到 ssthresh。 其中：拥塞窗口 cwnd
如果收到3个相同的ACK。TCP在收到乱序到达包时就会立即发送ACK，TCP利用3个相同的ACK来判定数据包的丢失，此时进行快速重传，快速重传做的事情有：
1.把ssthresh设置为cwnd的一半
2.把cwnd再设置为ssthresh的值(具体实现有些为ssthresh+3)
3.重新进入拥塞避免阶段。
后来的“快速恢复”算法是在上述的“快速重传”算法后添加的，当收到3个重复ACK时，TCP最后进入的不是拥塞避免阶段，而是快速恢复阶段。快速重传和快速恢复算法一般同时使用。快速恢复的思想是“数据包守恒”原则，即同一个时刻在网络中的数据包数量是恒定的，只有当“老”数据包离开了网络后，才能向网络中发送一个“新”的数据包，如果发送方收到一个重复的ACK，那么根据TCP的ACK机制就表明有一个数据包离开了网络，于是cwnd加1。如果能够严格按照该原则那么网络中很少会发生拥塞，事实上拥塞控制的目的也就在修正违反该原则的地方。
具体来说快速恢复的主要步骤是：
1.当收到3个重复ACK时，把ssthresh设置为cwnd的一半，把cwnd设置为ssthresh的值加3，然后重传丢失的报文段，加3的原因是因为收到3个重复的ACK，表明有3个“老”的数据包离开了网络。
2.再收到重复的ACK时，拥塞窗口增加1。
3.当收到新的数据包的ACK时，把cwnd设置为第一步中的ssthresh的值。原因是因为该ACK确认了新的数据，说明从重复ACK时的数据都已收到，该恢复过程已经结束，可以回到恢复之前的状态了，也即再次进入拥塞避免状态。
快速重传算法首次出现在4.3BSD的Tahoe版本，快速恢复首次出现在4.3BSD的Reno版本，也称之为Reno版的TCP拥塞控制算法。
可以看出Reno的快速重传算法是针对一个包的重传情况的，然而在实际中，一个重传超时可能导致许多的数据包的重传，因此当多个数据包从一个数据窗口中丢失时并且触发快速重传和快速恢复算法时，问题就产生了。因此NewReno出现了，它在Reno快速恢复的基础上稍加了修改，可以恢复一个窗口内多个包丢失的情况。具体来讲就是：Reno在收到一个新的数据的ACK时就退出了快速恢复状态了，而NewReno需要收到该窗口内所有数据包的确认后才会退出快速恢复状态，从而更一步提高吞吐量。

⑺ TCP/IP的快恢复算法怎么理解

struct tcp_sock {
...
/* Congestion window at start of Recovery. 进入Recovery前的拥塞窗口*/
u32 prior_cwnd;

/* Number of newly delivered packets to receiver in Recovery.
* 实际上用于统计data_rate_at_the_receiver，数据离开网络的速度。
*/
u32 prr_delivered;

/* Total number of pkts sent ring Recovery.
* 实际上用于统计sending_rate，数据进入网络的速度。
*/
u32 prr_out;
...
}
@net/ipv4/tcp_input.c
[java] view plain
static inline void tcp_complete_cwr (struct sock *sk)
{
struct tcp_sock *tp = tcp_sk(sk);
/* Do not moderate cwnd if it's already undone in cwr or recovery. */
if (tp->undo_marker) {
if (inet_csk(sk)->icsk_ca_state == TCP_CA_CWR)
tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_ssthresh);

else /* PRR */
tp->snd_cwnd = tp->snd_ssthresh; /* 防止不必要的进入慢启动*/

tp->snd_cwnd_stamp = tcp_time_stamp;
}
tcp_ca_event(sk, CA_EVENT_COMPLETE_CWR);
}
[java] view plain
/* This function implements the PRR algorithm, specifically the PRR-SSRB
* (proportional rate rection with slow start rection bound) as described in
* http://www.ietf.org/id/draft-mathis-tcpm-proportional-rate-rection-01.txt.
* It computes the number of packets to send (sndcnt) based on packets newly
* delivered:
* 1) If the packets in flight is larger than ssthresh, PRR spreads the cwnd
* rections across a full RTT.
* 2) If packets in flight is lower than ssthresh (such as e to excess losses
* and/or application stalls), do not perform any further cwnd rections, but
* instead slow start up to ssthresh.
*/

static void tcp_update_cwnd_in_recovery (struct sock *sk, int newly_acked_sacked,
int fast_rexmits, int flag)
{
struct tcp_sock *tp = tcp_sk(sk);
int sndcnt = 0; /* 对于每个ACK，可以发送的数据量*/
int delta = tp->snd_ssthresh - tcp_packets_in_flight(tp);

if (tcp_packets_in_flight(tp) > tp->snd_ssthresh) {

/* Main idea : sending_rate = CC_rection_factor * data_rate_at_the_receiver，
* 按照拥塞算法得到的减小因子，按比例的减小pipe，最终使pipe收敛于snd_ssthresh。
*/
u64 dividend = (u64) tp->snd_ssthresh * tp->prr_delivered + tp->prior_cwnd - 1;
sndcnt = div_u64(dividend, tp->prior_cwnd) - tp->prr_out;

} else {
/* tp->prr_delivered - tp->prr_out首先用于撤销之前对pipe的减小，即首先让网络中的数据包恢复守恒。
* 然后，tp->prr_delivered < tp->prr_out，因为目前是慢启动，网络中数据包开始增加：
* 对于每个ACK，sndcnt = newly_acked_sacked + 1，使pipe加1，即慢启动。
* delta使pipe最终收敛于snd_ssthresh。
*/
sndcnt = min_t(int, delta, max_t(int, tp->prr_delivered - tp->prr_out, newly_acked_sacked) + 1);
}

sndcnt = max(sndcnt, (fast_rexmit ? 1 : 0));
tp->snd_cwnd = tcp_packets_in_flight(tp) + sndcnt;
}
@tcp_ack()
[java] view plain
/* count the number of new bytes that the current acknowledgement indicates have
* been delivered to the receiver.
* newly_acked_sacked = delta(snd.una) + delat(SACKed)
*/
newly_acked_sacked = (prior_packets - tp->packets_out) + (tp->sacked_out - prior_sacked);

...

tcp_fastretrans_alert(sk, prior_packets - tp->packets_out, newly_acked_sacked, flag);

⑻ TCP 如何保证可靠性

[TOC]

1. TCP可靠性的保证机制总结

2. 网络基础：TCP协议-如何保证传输可靠性

3. TCP协议的流量控制和拥塞控制

4. TCP 的那些事儿（下）

5. TCP拥塞控制：慢开始、拥塞避免、快重传、快恢复

TCP检验和的计算与UDP一样，在计算时要加上12byte的伪首部，检验范围包括TCP首部及数据部分，但是UDP的检验和字段为可选的，而TCP中是必须有的。计算方法为：在发送方将整个报文段分为多个16位的段，然后将所有段进行反码相加，将结果存放在检验和字段中，接收方用相同的方法进行计算，如最终结果为检验字段所有位是全1则正确（UDP中也是全为1则正确），否则存在错误。

TCP将每个数据包都进行了编号，这就是序列号。
序列号的作用：
a、保证可靠性（当接收到的数据总少了某个序号的数据时，能马上知道）
b、保证数据的按序到达
c、提高效率，可实现多次发送，一次确认
d、去除重复数据
数据传输过程中的确认应答处理、重发控制以及重复控制等功能都可以通过序列号来实现

TCP通过确认应答机制实现可靠的数据传输。在TCP的首部中有一个标志位——ACK，此标志位表示确认号是否有效。接收方对于按序到达的数据会进行确认，当标志位ACK=1时确认首部的确认字段有效。进行确认时，确认字段值表示这个值之前的数据都已经按序到达了。而发送方如果收到了已发送的数据的确认报文，则继续传输下一部分数据；而如果等待了一定时间还没有收到确认报文就会启动重传机制。

当报文发出后在一定的时间内未收到接收方的确认，发送方就会进行重传（通常是在发出报文段后设定一个闹钟，到点了还没有收到应答则进行重传）。
一种情况是发送包丢失了，其基本过程如下：

另一种情况是ACK 丢失，过程如下：

当接收方接收到重复的数据时就将其丢掉，重新发送ACK。而要识别出重复的数据，前面提到的序列号就起作用了。

重传时间的确定：
重传时间的确定：报文段发出到收到应答中间有一个报文段的往返时间RTT，显然超时重传时间RTO会略大于这个RTT，TCP会根据网络情况动态的计算RTT，即RTO是不断变化的。在Linux中，超时以500ms为单位进行控制，每次判定超时重发的超时时间都是500ms的整数倍。其规律为：如果重发一次仍得不到应答，就等待2 500ms后再进行重传，如果仍然得不到应答就等待4 500ms后重传，依次类推，以指数形式递增，重传次数累计到一定次数后，TCP认为网络或对端主机出现异常，就会强行关闭连接。

连接管理机制即TCP建立连接时的三次握手和断开连接时的四次挥手。

接收端处理数据的速度是有限的，如果发送方发送数据的速度过快，导致接收端的缓冲区满，而发送方继续发送，就会造成丢包，继而引起丢包重传等一系列连锁反应。
因此TCP支持根据接收端的处理能力，来决定发送端的发送速度，这个机制叫做流量控制。
在TCP报文段首部中有一个16位窗口长度，当接收端接收到发送方的数据后，在应答报文ACK中就将自身缓冲区的剩余大小，放入16窗口大小中。这个大小随数据传输情况而变，窗口越大，网络吞吐量越高，而一旦接收方发现自身的缓冲区快满了，就将窗口设置为更小的值通知发送方。如果缓冲区满，就将窗口置为0，发送方收到后就不再发送数据，但是需要定期发送一个窗口探测数据段，使接收端把窗口大小告诉发送端。

注意：窗口大小不受16位窗口大小限制，在TCP首部40字节选项中还包含一个窗口扩大因子M，实际窗口大小是窗口字段的值左移M位。

流量控制解决了两台主机之间因传送速率而可能引起的丢包问题，在一方面保证了TCP数据传送的可靠性。然而如果网络非常拥堵，此时再发送数据就会加重网络负担，那么发送的数据段很可能超过了最大生存时间也没有到达接收方，就会产生丢包问题。
为此TCP引入慢启动机制，先发出少量数据，就像探路一样，先摸清当前的网络拥堵状态后，再决定按照多大的速度传送数据。
此处引入一个拥塞窗口：
发送开始时定义拥塞窗口大小为1；每次收到一个ACK应答，拥塞窗口加1；而在每次发送数据时，发送窗口取拥塞窗口与接送段接收窗口最小者。
慢启动：在启动初期以指数增长方式增长；设置一个慢启动的阈值，当以指数增长达到阈值时就停止指数增长，按照线性增长方式增加；线性增长达到网络拥塞时立即“乘法减小”，拥塞窗口置回1，进行新一轮的“慢启动”，同时新一轮的阈值变为原来的一半。
“慢启动”机制可用图表示：

1）连接建好的开始先初始化cwnd = 1，表明可以传一个MSS大小的数据。

2）每当收到一个ACK，cwnd++; 呈线性上升

3）每当过了一个RTT，cwnd = cwnd*2; 呈指数让升

4）还有一个ssthresh（slow start threshold），是一个上限，当cwnd >= ssthresh时，就会进入“拥塞避免算法”（后面会说这个算法）

1）收到一个ACK时，cwnd = cwnd + 1/cwnd

2）当每过一个RTT时，cwnd = cwnd + 1

这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。很明显，是一个线性上升的算法。

当出现ack超时的时候，需要重传数据包。

TCP认为这种情况太糟糕，反应也很强烈。
快速重传在收到3个plicate ACK时就开启重传(三次 ack 就认为丢包的原理见 关于TCP乱序和重传的问题 、 TCP 快速重传为什么是三次冗余 ACK )，而不用等到RTO超时。

TCP Reno的实现是：

快速重传和快速恢复算法一般同时使用。快速恢复算法是认为，你还有3个Duplicated Acks说明网络也不那么糟糕，所以没有必要像RTO超时那么强烈。 注意，正如前面所说，进入Fast Recovery之前，cwnd 和 sshthresh已被更新：

然后，真正的Fast Recovery算法如下：
cwnd = sshthresh + 3 * MSS （3的意思是确认有3个数据包被收到了）
重传Duplicated ACKs指定的数据包
如果再收到 plicated Acks，那么cwnd = cwnd +1
如果收到了新的Ack，那么，cwnd = sshthresh ，然后就进入了拥塞避免的算法了。
如果你仔细思考一下上面的这个算法，你就会知道，上面这个算法也有问题，那就是——它依赖于3个重复的Acks。注意，3个重复的Acks并不代表只丢了一个数据包，很有可能是丢了好多包。但这个算法只会重传一个，而剩下的那些包只能等到RTO超时，于是，进入了恶梦模式——超时一个窗口就减半一下，多个超时会超成TCP的传输速度呈级数下降，而且也不会触发Fast Recovery算法了。

通常来说，正如我们前面所说的，SACK或D-SACK的方法可以让Fast Recovery或Sender在做决定时更聪明一些，但是并不是所有的TCP的实现都支持SACK（SACK需要两端都支持），所以，需要一个没有SACK的解决方案。而通过SACK进行拥塞控制的算法是FACK（可参见 关于TCP乱序和重传的问题 ）