TCP 和 UDP 是传输层两个主要的传输协议, TCP 是面向连接、面向字节流的传输协议, 向应用层提供可靠的服务, 而 UDP 是面向 Packet (如同 IP 分组, 对等协议栈进行通信时, 无需事先建立连接), 不可靠, 尽最大努力交付 (best-effort) 的传输协议, TCP 保证传递给应用层的数据按序交付、不丢失、不重复, 为了达到这样的目标, TCP 设计了报文编号、确认、超时重传、滑动窗口、拥塞控制等模块, 这也使得 TCP 协议在工作中要付出较大的代价, 一般来说, 一个网络协议的设计目标主要有三个: 实时性、可靠性、公平性, 而实际上这 3 个评价维度无法同时达到最优, 每种网络协议都有其设计的目标, 对于 TCP 来说, 它的设计目标主要是可靠性和公平性, 因而 TCP 的传输效率实际上比较低下, 尤其是对于网络游戏来说, TCP 的延时往往是不可接受的, 鉴于 UDP 的不可靠性, 因此衍生出了一些对 UDP 的改进, 当然无论协议如何设计, 实时性、可靠性与公平性三者仍然无法同时达到, 本文主要讨论 KCP 协议的设计与实现, KCP 在 UDP 的基础上, 实现了用户态的确认、ARQ、流量控制与拥塞控制, 它的设计目标是实时性与可靠性, 一定程度上破坏了公平性, KCP 不是 RFC 的标准协议, 但在实际应用中表现出了较好的效果, 目前已经有很多基于 KCP 的开源案例, 如 kcptun, v2ray, shadowsocks

7.1 可靠传输的目标

当通信双方使用 UDP 进行通信时, 无需事先建立连接, 自然地, 当通信结束时也无需释放连接, 因为整个过程都没有连接的建立, 因此相对于 TCP, UDP 省去了 3 次握手与 4 次挥手的工作; 其次, UDP 没有类似于 TCP 的 MSS (最大报文段) 概念, 每次将数据交付给网络层时, 不会对数据包分片, 它将应用层传递的数据加上 UDP Header 后便交付给网络层, 即 UDP 每次交付都是一个完整的报文, 这也意味着网络层收到的 UDP 包大小实际是应用层控制的; 另外, UDP 不设置拥塞控制, 因此无论网络状况如何, UDP 都可以按恒定速率持续发送, 当网络拥挤时, UDP 将产生大量的丢包, 要在 UDP 的基础上实现可靠传输, 则首先要明确可靠传输的目标

参考 TCP 的设计, 要保证可靠传输, 需要做以下几点工作:

  1. 保证交付给上层的数据是完整的, 即不丢失, 因此需要设置确认机制
  2. 保证交付给上层的数据是有序的
  3. 控制向应用层交付数据的速率, 避免应用层来不及消费数据而丢包
  4. 需要有拥塞控制机制, 当网络拥挤时, 进行拥塞控制

因此, 可靠传输的 UDP 协议同样需要有报文序号、确认、自动重传、滑动窗口、拥塞控制等特性

7.2 ARQ (自动重传请求)

ARQ 即 Automatic Repeat reQuest, 自动重传请求, 对于可靠传输协议, 当发送方向接收方发送报文以后, 必须需要等待接收方发回的确认才能保证这个数据包已经到达了接收方, 为此发送方需要设置发送缓存用于暂存已经发送但未收到确认的数据包, 当接收到另一方的确认报文后才能将数据包从发送缓存中移除, 对于每一个数据包, 发送方需要设置一个超时计时器, 当超过指定时间未收到对方的确认后, 需要重传这个数据包, 这个过程是自动进行的, 因此称之为自动重传请求, 为了提高通信效率, 发送方不必等待上一个报文被确认后再发送下一个报文, 而是可以采用流水线的方式连续发送多个数据包, 当然可以连续发送的数据包的数量是有限制的, 它受对方的接收窗口以及当前的拥塞窗口控制 (将在下面讨论), 对于 ARQ 来说, 一个关键的问题是超时时间如何确定, 我们来分析 KCP 和 TCP 的策略

超时时间(RTO, 即 Retransmission Time-Out)的确定实际上是一个比较复杂的问题, 若设置的过短, 则会引起数据包不必要的重传, 而设置的过长则会导致不能及时判断到丢包的状态, 因而降低传输的效率, RFC 6298 提出了一种自适应的算法, 这也是 TCP 采用的策略, 具体来说, 首先定义 RTT 的概念(RTT 即 Round-Trip Time), RTT 是从报文发出开始直到接收到对方发来的确认的时间间隔, 即报文的往返时间, RFC 6298 同时定义了一个平滑的往返时间 Smoothed RTT(我们下面简写为 SRTT), 引入平滑 RTT 的目的是为了避免 RTT 数值的震荡, 因为网络环境比较复杂, 每次获取的 RTT 值可能有较大的变化, 而平滑 RTT 便是尽可能地将 RTT 的变化放缓, SRTT 的计算方式如下:

SRTT <- (1 - α) * SRTT + α * RTT

其中 RTT 是获得的最新的 RTT 数值, 用代码来表达也可以简写为 , 其中 , 可以称为平滑因子, 越接近于 0 则 SRTT 的变化越小, 而 越接近于 1, 则表示 SRTT 受新的 RTT 数值的影响越大, RFC 6298 推荐的 值为 0.125, 因为 SRTT 是估计的报文的往返时间, 所以 RTO 应该略大于 SRTT, RFC 6298 推荐的 RTO 计算方式为:

上式中的 RTTVAR 是 Round-Trip Time VARiation 的缩写, K 为参数, G 为 TCP 时钟周期粒度, 在 TCP 的实现中, RTO 的计算采用的是软件时钟, G 为软件时钟的时钟周期, 可以称之为一个 「滴答」, 目前的 Linux Kernel 中, G 的值为 1 ms, 所以计算 RTO 时几乎不需要考虑这个值, 对于第一次获得 RTT 样本数值时, K 的推荐值为 4, 并且初始化 SRTT = R, 以及 RTTVAR = R/2, 所以第一次获得 RTT 样本数值后, 有

在此之后, 使用如下的方式更新 RTTVAR(每次计算出新的 RTT 后应首先更新 PTTVAR, 然后将新的 PTTVAR 代入 SRTT 公式计算新的 SRTT):

RTTVAR <- (1 - β) * RTTVAR + β * |SRTT -RTT|

其中 RFC 6298 建议的 β 取值为 1/4, KCP 对于 RTO 的计算的源码参见 kcp/ikcp.c#ikcp_update_ack

7.3 RTT 计算与 Karn 算法

在 7.2 中我们讨论了基于 RTT 来计算 RTO 的方法, 但有一个重要的问题没有提及, 那就是关于 RTT 的计算问题, 由于超时重传的存在, 如果不加以特别的处理, 这里会产生 Retransmission Ambiguity Problem, 即重传多义性问题, 对于可靠传输协议来说, 任何一个报文只有在收到接收方发来的确认之后才可以认为报文成功传输给了对方, 当发送方发送一个报文后, 如果在 RTO 到来之际没有收到对方的确认, 则会重传对应的报文, 倘若第二次重传报文后收到了对方的确认, 这时如何判断此次收到的确认是对重传后的报文确认还是对第一次发送的报文的确认, 这就是重传多义性问题, 分类来讨论, 如果此次收到的确认实际是对重传报文的确认, 而发送方误认为是对第一次发送报文的确认, 那么计算出的 RTT SRTT 以及 RTO 都会偏大, 如果这种状况持续下去则 RTO 将会越来越大; 而如果此次收到的确认实际是对第一次发送报文的确认, 却被发送方误认为是对重传报文的确认, 那么计算出的 RTT SRTT 以及 RTO 都会偏小, 如果这种状况继续下去, 那么 RTO 将会越来越小, 进而使得超时重传的情况发生的越来越频繁(因为 RTO 变小了, 所以很快就达到重传时间需要发起重传)

对此, RFC 6298 要求对于 TCP 必须(MUST) 采用 Karn 算法来计算 RTT, Karn 算法的第一版本的处理策略是当发生了重传后, 则不计算此次的 RTT, 这样计算出的 SRTT 和 RTO 相对比较准确, 但实际上这种处理方式是有漏洞的, 这种处理方式会导致当报文时延增大后, 比如网络发生了拥塞, 那么大量的报文都被重传, 而 Karn 算法的第一版对于重传报文不计算 RTT, 那么 RTT 就不会更新, RTO 自然也不会更新, 所以发送端继续使用原来的 RTO, 即便大量报文重传了也不会扩大重传等待时间, 使通信陷入恶性循环

改进的 Karn 算法是当报文段每重传一个, RTO 就翻倍, 这样可以规避上面的问题, 既解决了重传二义性问题而又不至于出现重传增多时 RTO 不更新的问题

7.4 KCP 的 RTO 更新策略

TCP 的 Karn 算法实际上一定程度是在做拥塞控制, 当重传包增多时, 有理由认为网络发生了拥塞, 因此将 RTO 翻倍, 降低发送端的发送速率, 由于 Karn 算法是翻倍递增的, 因此 RTO 增长的速度其实很快, 实际上 TCP 设计的目标之一就是公平性, 拥塞控制是一个全局性的问题, 当网络发生拥塞时, TCP 希望所有的发送端都能放慢发送速率, 而 KCP 修改了 RTO 的增长策略, KCP 在快速模式下, 每次将 RTO*1.5, 在实际测试中, 提高了传输速度, 当然这样做也一定程度上破坏了公平性

7.5 Selective ACK(选择性确认)

TCP 使用滑动窗口来进行流量控制, 每个 TCP 报文段都有 32 位的序列号以及 32 位的确认号, 序列号是每个报文段的标识, 序列号的范围是 , 握手阶段, 双方会创建一个随机序列号, 之后的通信中在这个随机序列号的基础上进行递增, 当序号到达最大值后也会重新回到 0, 确认号是对对方报文段的确认, 当 A 收到 B 发来的确认号为 N 的报文时, 意味着 B 已经收到了 A 发送的直到 N-1(包括 N - 1 在内)的所有报文段, TCP 使用流水线方式发送数据包, 并非是停止等待, 即并不是每次收到确认报文后再继续发下一个, 而是持续性地发送多个报文段, 直到将发送窗口用完, 如果发送的报文段超过了重传超时时间, 则必须要重传报文, 这里涉及到重传报文范围的问题, 刚提到, 对 TCP 来说, 确认号为 N 代表目前 N - 1 及其之前的报文都已经经过了确认, 而对于连续发送的 TCP 报文段, 若接收方已经收到了大序号的报文, 但缺少了前面的报文, 例如接收方收到了序号为 1, 2, 4, 5 的报文段, 没有收到 3 号报文段, 按照确认号的定义, 接收方只能向发送方发送确认号为 3 的报文(即代表 2 号及之前的报文段都已经收到了), 这样发送方得到的信息便是 3, 4, 5 号报文都没有成功传递到接收方, 因而发送方需要将这些报文重传, 即便接收方已经收到了 4, 5 号报文段

RFC 2018 提出了 SACK(选择确认)的概念, 如果通信双方需要进行 SACK, 则需要在建立 TCP 连接时进行协商, 协议信息需要放在 TCP Header 的选项字段中, 在之后的通信中, 将要确认的字节块边界序号放到 TCP 报文的选项字段, 但是 RFC 2018 没有指明 SACK 的响应方式, 因此目前大多数的 TCP 实现仍然是重传所有未确认的报文

7.6 KCP 改进的重传机制

TCP 丢包后需要重传从丢失包起之后的所有数据包, 即便只是中间丢失了一个包, 也需要重传之后所有的, 这实际上做了不必要的传输, 对此 KCP 做了改进, 在 TCP 中标识报文确认信息只有确认号这一个字段, KCP 采用了两种方式来处理确认, 其中 una 类似于 TCP 的 ACK, 当 A 收到 B 发来的 una = n 的 KCP 报文时, 则意味着 B 已经收到了 A 发送的直到 n-1 的 KCP 报文, 除此之外, KCP 还采用了 ACK 用于选择性确认, 具体来说是这样的, KCP Header 的 Layout 如下图所示

其中 cmd 字段为命令字段, 在 KCP 中共有 ack、push、ask、tell 共四种, 当 cmd 为 ack 时代表这是一个 ACK 报文, 该报文只有 Header, sn 字段便指示了此次确认的报文序号, 在 KCP 中, 接收到的每一个报文都需要通过 ACK 报文向发送方予以确认, 因此实际上 KCP 相比于 TCP 浪费了一定的带宽, 但基于 una + ack 可以实现选择性确认以及快重传机制

举例来说, 假设 A 向 B 发送 1, 2, 3, 4, 5 共 5 个报文段, B 收到了 1, 2, 4, 5, 对于 TCP 来说, B 只能向 A 发送 ACK = 2 的确认信息, 当达到 RTO 之后, A 需要重传 3, 4, 5 共 3 个报文段, 而对 KCP 来说, B 每收到一个字段, 就向 A 发送 ACK, 即 B 会向 A 发送 ack=1, ack=2, ack=4, ack=5 的确认报文, 当 A 收到 B 发来的 ack=4 时, 由于 ack 序号是不连续的, 即没有收到 ack=3 的确认信息, 此时 A 记录下 3 号报文段被 「跳过了」 一次, 当 A 收到 B 发来的 ack=5 时, A 知道 3 号报文段被跳过了 2 次, 当报文段被跳过的次数超过设定的次数时, A 可以认为 3 号报文段已经丢失, 此时无需等待 RTO 的到来, 直接向 B 重发 3 号报文, 而 B 收到 3 号报文之后, 再向 A 发送 ack=3 的确认信息, 此时 A 可以知道 3 号报文已被成功接收了, 这样通过 una + ack 机制, 实现了选择确认(每次确认一个报文段), 同时可以选择性重传以及快重传(跳过次数达到阈值即发起重传, 无需等待 RTO), 提高了通信效率, 源码参见 kcp/ikcp.c#ikcp_flush

7.7 KCP 窗口探测

KCP 采用与 TCP 一样的滑动窗口机制, 发送端允许发送的数据受发送端的发送窗口大小、接收端的接收窗口大小以及当前的拥塞窗口大小控制, 如果远端的接收窗口减少到了 0, 那么意味着发送端就无法再继续发送报文段了, 但如果迟迟也没有收到远端发来的新报文则这种境况会一直持续下去, 因此在远端接收窗口为 0 时, KCP 等待一段时间后便向远端发送窗口探测报文, 窗口探测报文即将 cmd 字段设置为 ask, 远端接收到窗口询问报文后, 应予以应答, 向发送端传回 tell 报文, 即将 KCP Header 的 cmd 字段设置为 tell, 并在 wnd 字段报告自己当前的接收窗口大小, 源码参见kcp/ikcp.c#ikcp_flush 和 kcp/ikcp.c#ikcp_input

7.8 KCP 拥塞控制

拥塞控制和流量控制的上层表现有点类似, 但本质上将它们是不同的概念, 流量控制是两个 Endpoint 之间的事情, 流量控制的目的是为了控制发送速率, 不至于太慢造成传输效率低, 也不至于太快造成接收端缓冲区溢出而丢包, 而拥塞控制是全局的事情, 是为了整体的网络性能, 在 TCP 中, 拥塞控制有慢开始、拥塞避免、快重传和快恢复等处理方式, 默认情况下, KCP 采用与 TCP 相同的拥塞控制方式, 使用慢开始算法, 即每收到一个确认报文就可以将发送窗口增大一, 对于慢开始来说, 每经过一个传输轮次, 发送窗口就翻倍, 因此慢开始的窗口增长速率非常大, RFC 6937 定义了 ssthresh, 即慢开始阈值, 当窗口达到阈值之后就开始改用拥塞避免(RFC 5681), 相对于慢开始的指数增长, 拥塞避免的窗口是线性增长的, 对于 KCP 来说, 当发生了快重传(即某个报文段被跳过的次数超过一定阈值), 便将慢开始阈值调整为当前发送窗口的一半大小, 当发生了丢包, 即某报文段达到了 RTO, 则将慢开始阈值降为当前拥塞窗口的一半大小, 并将拥塞窗口减小到一, 在非退让模式下, KCP 将摒弃慢开始和丢包退让, 仅仅使用发送窗口和接收窗口来通信, 换句话说, 这实际上摒弃了 TCP 的拥塞控制, 以破坏部分公平性来换取相对较高的传输效率

7.9 总结

总的来说, KCP 采用了与 TCP 几乎相同的架构, 在用户态实现了确认、ARQ、流量控制与拥塞控制机制, 但 KCP 一定程度上破坏了公平性, TCP 设计的初衷之一便是在全局角度达到公平, 因此会有慢开始、丢包退让等机制(RFC 5681), 而 KCP 在多处修改了相应的策略, 当网络环境不佳时, KCP 将比 TCP 拥有更好的性能, TCP 经过了这么多年的发展, 本身已经是一个足够完善的协议, 对于拥塞控制也做了大量的工作, 所做的一切就是为了能让全局的平均性能达到最好, 对于 KCP 的争议也有很多, 单一维度无法直接评判 KCP 协议本身, 但可以确定的是当大量客户端都开始采用 KCP 时, 那 KCP 也就失去它的优势了