背景

之前有篇文章介绍了TCP建立连接和断开连接时的状态转移流程，没有详细去讲建立完连接之后的传输控制。这篇文章会就几个常见的TCP传输相关的问题做下简单分享，因为TCP/IP协议很复杂，也不可能通过一篇文章完全写清楚。可能更多的内容，还是要查阅专业的相关书籍和网站。好了，废话不多说，今天会涉及这么几个问题的初步探讨：

1. TCP滑动窗口机制作用是什么？
2. TCP的重传机制和快速重传机制是什么？有什么区别？
3. TCP拥塞控制机制是什么？

TCP滑动窗口机制

滑动窗口其实就是用来控制发送速率，因为网络是复杂多变的，有时候就会阻塞住，而有时候又很通畅。不让让网络抖动的时候，去加剧网络质量的下降，从而造成不必要的雪崩。所以发送方需要知道接收方的情况，好控制一下发送的速率，不至于蒙着头一个劲儿的发然后接受方都接受不过来。因此 TCP 就有个叫滑动窗口的东西来做流量控制，也就是接收方告诉发送方我还能接受多少数据，然后发送方就可以根据这个信息来进行数据的发送。
以下是发送方维护的窗口，就是黑色圈起来的。

图中的 #1 是已收到 ACK 的数据，#2 是已经发出去但是还没收到 ACK 的数据，#3 就是在窗口内可以发送但是还没发送的数据。#4 就是还不能发送的数据。
然后此时收到了 36 的 ACK，并且发出了 46-51 的字节，于是窗口向右滑动了。

TCP/IP Guide 上还有一张完整的图，画的十分清晰，大家看一下。

那么如果接受方回复的窗口一直是0，那怎么办？
上文已经说了发送方式根据接收方回应的 window 来控制能发多少数据，如果接收方一直回应 0，那发送方就杵着？你想一下，发送方发的数据都得到 ACK 了，但是呢回应的窗口都是 0 ，这发送方此时不敢发了啊，那也不能一直等着啊，这 Window 啥时候不变 0 啊？于是 TCP 有一个 Zero Window Probe 技术，发送方得知窗口是 0 之后，会去探测探测这个接收方到底行不行，也就是发送 ZWP 包给接收方。具体看实现了，可以发送多次，然后还有间隔时间，多次之后都不行可以直接 RST。
假设接收方每次回应窗口都很小怎么办？
你想象一下，如果每次接收方都说我还能收 1 个字节，发送方该不该发？TCP + IP 头部就 40 个字节了，这传输不划算啊，如果傻傻的一直发这就叫 Silly Window。那咋办，一想就是发送端等着，等养肥了再发，要么接收端自己自觉点，数据小于一个阈值就告诉发送端窗口此时是 0 算了，也等养肥了再告诉发送端。发送端等着的方案就是纳格算法，这个算法相信看一下代码就知道了。

简单的说就是当前能发送的数据和窗口大于等于 MSS 就立即发送，否则再判断一下之前发送的包 ACK 回来没，回来再发，不然就攒数据。
接收端自觉点的方案是 David D Clark’s 方案，如果窗口数据小于某个阈值就告诉发送方窗口 0 别发，等缓过来数据大于等于 MSS 或者接受 buffer 腾出一半空间了再设置正常的 window 值给发送方。
对了提到纳格算法不得不再提一下延迟确认，纳格算法在等待接收方的确认，而开启延迟确认则会延迟发送确认，会等之后的包收到了再一起确认或者等待一段时候真的没了再回复确认。
这就相互等待了，然后延迟就很大了，两个不可同时开启。

TCP的重传机制和快速重传机制

前面我们提到 TCP 要提供可靠的传输，那么网络又是不稳定的如果传输的包对方没收到却又得保证可靠那么就必须重传。
TCP 的可靠性是靠确认号的，比如我发给你1、2、3、4这4个包，你告诉我你现在要 5 那说明前面四个包你都收到了，就是这么回事儿。
不过这里要注意，SeqNum 和 ACK 都是以字节数为单位的，也就是说假设你收到了1、2、4 但是 3 没有收到你不能 ACK 5，如果你回了 5 那么发送方就以为你5之前的都收到了。
所以只能回复确认最大连续收到包，也就是 3。
而发送方不清楚 3、4 这两个包到底是还没到呢还是已经丢了，于是发送方需要等待，这等待的时间就比较讲究了。
如果太心急可能 ACK 已经在路上了，你这重传就是浪费资源了，如果太散漫，那么接收方急死了，这死鬼怎么还不发包来，我等的花儿都谢了。
所以这个等待超时重传的时间很关键，怎么搞？聪明的小伙伴可能一下就想到了，你估摸着正常来回一趟时间是多少不就好了，我就等这么长。
这就来回一趟的时间就叫 RTT，即 Round Trip Time，然后根据这个时间制定超时重传的时间 RTO，即 Retransmission Timeout。
不过这里大概只好了 RTO 要参考下 RTT ，但是具体要怎么算？首先肯定是采样，然后一波加权平均得到 RTO。
RFC793 定义的公式如下：
先采样 RTT 2、SRTT = ( ALPHA SRTT ) + ((1-ALPHA) RTT) 3、RTO = min[UBOUND,max[LBOUND,(BETA*SRTT)]]
ALPHA 是一个平滑因子取值在 0.8~0.9之间，UBOUND 就是超时时间上界-1分钟，LBOUND 是下界-1秒钟，BETA 是一个延迟方差因子，取值在 1.3~2.0。
但是还有个问题，RTT 采样的时间用一开始发送数据的时间到收到 ACK 的时间作为样本值还是重传的时间到 ACK 的时间作为样本值？

从图中就可以看到，一个时间算长了，一个时间算短了，这有点难，因为你不知道这个 ACK 到底是回复谁的。
所以怎么办？发生重传的来回我不采样不就好了，我不知道这次 ACK 到底是回复谁的，我就不管他，我就采样正常的来回。
这就是 Karn / Partridge 算法，不采样重传的RTT。
但是不采样重传会有问题，比如某一时刻网络突然就是很差，你要是不管重传，那么还是按照正常的 RTT 来算 RTO， 那么超时的时间就过短了，于是在网络很差的情况下还疯狂重传加重了网络的负载。
因此 Karn 算法就很粗暴的搞了个发生重传我就将现在的 RTO 翻倍，哼！就是这么简单粗暴。
但是这种平均的计算很容易把一个突然间的大波动，平滑掉，所以又搞了个算法，叫 Jacobson / Karels Algorithm。
它把最新的 RTT 和平滑过的 SRTT 做了波计算得到合适的 RTO，公式我就不贴了，反正我不懂，不懂就不哔哔了。
那快速重传机制又是什么，既然有了重传机制，为啥又要这个？超时重传是按时间来驱动的，如果是网络状况真的不好的情况，超时重传没问题，但是如果网络状况好的时候，只是恰巧丢包了，那等这么长时间就没必要。
于是又引入了数据驱动的重传叫快速重传，什么意思呢？就是发送方如果连续三次收到对方相同的确认号，那么马上重传数据。
因为连续收到三次相同 ACK 证明当前网络状况是 ok 的，那么确认是丢包了，于是立马重发，没必要等这么久。

看起来好像挺完美的，但是你有没有想过我发送1、2、3、4这4个包，就 2 对方没收到，1、3、4都收到了，然后不管是超时重传还是快速重传反正对方就回 ACK 2。这时候要重传 2、3、4 呢还是就 2 呢？
所以就引入了SACK，即 Selective Acknowledgment，它的引入就是为了解决发送方不知道该重传哪些数据的问题。我们来看一下下面的图就知道了。

SACK 就是接收方会回传它已经接受到的数据，这样发送方就知道哪一些数据对方已经收到了，所以就可以选择性的发送丢失的数据。
如图，通过 ACK 告知我接下来要 5500 开始的数据，并一直更新 SACK，6000-6500 我收到了，6000-7000的数据我收到了，6000-7500的数据我收到了，发送方很明确的知道，5500-5999 的那一波数据应该是丢了，于是重传。
而且如果数据是多段不连续的， SACK 也可以发送，比如 SACK 0-500,1000-1500，2000-2500。就表明这几段已经收到了。
说完了SACK，不得不提D-SACK，这又是什么东西？D-SACK 其实是 SACK 的扩展，它利用 SACK 的第一段来描述重复接受的不连续的数据序号，如果第一段描述的范围被 ACK 覆盖，说明重复了，比如我都 ACK 到6000了你还给我回 SACK 5000-5500 呢？
说白了就是从第一段的反馈来和已经接受到的 ACK 比一比，参数是 tcp_dsack，Linux 2.4 之后默认开启。
那知道重复了有什么用呢？1、知道重复了说明对方收到刚才那个包了，所以是回来的 ACK 包丢了。2、是不是包乱序的，先发的包后到？3、是不是自己太着急了，RTO 太小了？4、是不是被数据复制了，抢先一步呢？

TCP拥塞控制机制

有滑动窗口了为什么还要拥塞控制，前面已经提到了，加了拥塞控制是因为 TCP 不仅仅就管两端之间的情况，还需要知晓一下整体的网络情形，毕竟只有大家都守规矩了道路才会通畅。前面我们提到了重传，如果不管网络整体的情况，肯定就是对方没给 ACK ，那我就无脑重传。如果此时网络状况很差，所有的连接都这样无脑重传，是不是网络情况就更差了，更加拥堵了？然后越拥堵越重传，一直冲冲冲！然后就 GG 了。
主要有以下几个步骤来搞：1、慢启动，探探路。2、拥塞避免，感觉差不多了减速看看 3、拥塞发生快速重传/恢复。

这块确实还不怎么理解，晚点有机会再补充，

总结

TCP/IP实在是很复杂的一个协议，其中的工程设计凝结了很多大师的智慧，在下不才，这篇文章也只能管中窥豹，略作启发，更多详细内容，还是推荐阅读专业的书籍。

引用内容

http://www.tcpipguide.com/
https://www.ionos.com/digitalguide/server/know-how/introduction-to-tcp/
https://www.ibm.com/developerworks/cn/linux/l-tcp-sack/
https://coolshell.cn/articles/11564.html/
https://tools.ietf.org/html/rfc793https://nmap.org/book/tcpip-ref.html

背景介绍

在《UNIX网络编程》经典书籍中，对TCP连接建立和断开描述了11种TCP状态，书里面有一张经典图片。

头一次看（或者过一段时间看）上面这张图，脑袋都会变大，我写这篇文章，就想记录下如何理解这张完整的状态转移图。作用有两个：
一、深入理解TCP的状态转移；
二、针对实际工作种会出现的大量TCP状态（比如TIME_WAIT、CLOSE_WATI），有针对性解决问题的思路。

整体理解

首先，这张图画的是TCP所有的11种状态，以及他们之间转移的条件，可以这样理解，图描述的是一个整体全貌，是所有状态拼在一起的内容，这也就是为啥，我们看着觉得特别复杂。简单来说，我认为在单一的一次TCP传输数据（建立连接->传输数据->断开连接），不会出现所有的11种状态。我总结下来，某一次的TCP连接会有如下几种情况：
一、客户端建立连接，客户端和服务端传输数据，客户端关闭连接；
二、客户端建立连接，客户端和服务端传输数据，服务端关闭连接；
三、客户端建立连接，客户端和服务端传输数据，客户端和服务端同时关闭连接；
也很容易理解，建立连接，只能是客户端主动，只有关闭连接，我们才需要分类讨论。

客户端关闭连接

这个应该是最常规的流程了，从整体图中分离得到的状态转移图如下：

如果转化位流程图，如下：

上面这两张图，应该是比较清晰，也不用太多的解释了吧？有时间补充实际操作的代码，结合代码能够看到状态转移，我想理解会更加深刻的。

服务端关闭连接

和上面客户端关闭连接一样，我也整理两张容易理解的图，

客户端和服务端同时关闭连接

这个情况就相对复杂些，分2种情况讨论下。第一种情况两端同时关闭连接，也同时收到对方发送的FIN包，如下图：

第二种情况两端同时关闭连接，但其中一方先收到FIN包（以客户端先收到FIN包为例，反之亦然），如下图：

异常状态的讨论

实际工作中，会经常遇到服务器出现大量TIME_WAIT或者CLOSE_WATI的状态。
TIME_WAIT根据上面的分析，主动关闭连接方在ACK对端FIN包后处于的状态，也被称为2MSL等待状态。每个具体 TCP 实现必须选择一个报文段最大生存时间 MSL（Maximum Segment Lifetime）。它是任何报文段被丢弃前在网络内的最长时间。这个时间是有限的，因为TCP报文段以IP数据报在网络内传输，而IP数据报则有限制其生存时间的TTL字段。所以TIME_WAIT状态保证了两点：1. 可靠地实现 TCP 全双工连接的终止；2. 允许老的重复分节在网络中消逝。如果服务器上出现大量的TIME_WAIT状态，很可能是有大量的短连接，此时有可能的措施有这么几个，减少MSL的时长、短连接变为长连接。
CLOSE_WAIT状态时被动关闭连接的一方会处于的状态，只要收到了对端的FIN包，回复了对应的ACK包，就变成了CLOSE_WAIT状态，但是如果此时我们服务程序（异常原因）没有继续调用close()函数，导致未发送FIN包，就会造成这个连接一直处于CLOSE_WAIT状态，此时需要排查程序，弄清楚在什么异常场景下，导致程序未发送FIN包。

参考资料：
https://zhuanlan.zhihu.com/p/78540103
https://www.jianshu.com/p/eb0d3e4744f1
https://blog.csdn.net/yu616568/article/details/44677985

导言

什么是主定理，引用维基百科的介绍，在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。所以，在算法复杂度分析时，我们经常需要使用主定理做复杂度的推导，尤其是各种类型的分治算法，比如二分搜索、归并排序、二叉树的遍历等算法。

理论

算法存在递推关系式

证明

总结

以上的证明手写输出，在电脑上面打公式太麻烦，另外证明过程采用的比较简单直接的方式，没有使用特别严格的数学证明方法，便于理解，简单来说，如果a<b^d，那么T(n)主要看O(n^d)这项，如果a==b^d，那么T(n)需要看展开的每一项，如果a>b^d，那么最主要的是看展开后的最后一层子问题，后面有时间，会补充一篇根据主定理推导算法复杂度的文章。