UDP可靠性传输KCP实现原理和应⽤
⼀、为什么要做UDP可靠性传输？
UDP与TCP的区别：
TCP是为流量设计的（每秒可以传输多少KB的数据），因此在刚启动的时候会尽量少带宽，讲究的时候充分利⽤带宽。 可靠性UDP设计⽬的是解决：延迟问题。
⼆、如何做到可靠性传输
做到可靠性传输，可以通过以下机制实现：
ACK机制
重传机制
序号机制
重排机制
窗⼝机制
1）ACK机制
如果有确认应答， 说明数据已经成功到达对端。
如果没有收到应答，不能说数据⼀定丢失了，但数据丢失的可能性⽐较⼤。 2）重传机制
数据重传，是发送端发送数据后没有收到对端ACK，继续重发数据。
数据重传，常⽤⽅式是在重发数据前，等待确认应答到来指定超时时间，如果超过了该时间还没收到确认应答，发送端将进⾏重传。
3）序号机制
序号机制，可以保证传送数据包的顺序。
序号既包含在数据发送包，也包含在响应包内。
a）接收端：接收端在收到发送包后，可以根据序号对数据进⾏重组。
b）发送端：在传送⼀个数据包时，会把该数据包放⼊重传队列中，同时启动计时器，如果收到对端收到数据包的确认应答，则通过序号识别，将该数据包从重传队列中删除；如果超时仍未收到对端的确认应答，则重发数据。
4）重排机制
重排机制，指的是对数据段进⾏排序重组。
可借助于序号机制，使⽤序号对数据段进⾏排序。
5）窗⼝机制
窗⼝机制主要⽤于流量控制和拥塞控制。
》》以TCP进⾏说明
a）利⽤窗⼝控制提⾼速度
苹果灯在建⽴TCP连接的同时，也可以确定发送数据包的单位，称其为“最⼤消息长度”(MSS)。
TCP在传输⼤量数据时，是以MSS的⼤⼩将数据进⾏分割发送。进⾏重发时也是以MSS为单位。
TCP以⼀个数据段为单位，每发⼀个数据段进⾏⼀次确认应答处理。这种传输⽅式的缺点：包的往返时间越长，通信性能越低。TCP引⼊窗⼝来解决这个问题。
图1
瑞利衰落图1所⽰，确认应答不再是以每个分段，⽽是以更⼤的单位进⾏确认时，转发时间将被⼤幅度缩短。发送端主机在发送了⼀个段以后不必⼀直等待确认应答，⽽是继续发送。
窗⼝⼤⼩就是指⽆需等待确认应答⽽可以继续发送数据的最⼤值。图1窗⼝⼤⼩为3个段。
如下图所⽰，黄⾊部分表⽰窗⼝。这个窗⼝中的数据即便没有收到应答确认也可以被发送出去。不过，在整个窗⼝的确认应答没有到达之前，如果其中部分数据出现丢包，那么发送端仍然需要重传。在收到确认应答的情况下，将窗⼝滑动到确认应答中的序列号的位置。这样可以顺序得将多个段同时发送提⾼通信性能。这种机制也被称为窗⼝滑动机制。
图2
b）流量控制（窗⼝⼤⼩）
流量控制是对发送端和接收端之间的处理速度进⾏的平衡。
⽐如，发送端⼀直在发送数据，接收端可能由于本⾝业务原因没能够及时接收数据，⼀些本该接收的数据被丢弃，从⽽触发发送端的重发机制，导致⽹络流量的浪费。
TCP通过流量控制可以让发送端根据接收端的实际接收能⼒控制发送数据的数量。
接收端主机向发送端主机通知⾃⼰可以接收数据的⼤⼩，于是发送端会发送不超过这个限度的数据。该⼤⼩限度就被称作窗⼝⼤⼩。
TCP⾸部中，专门有⼀个字段⽤来通知窗⼝⼤⼩。接收主机将⾃⼰可以接收的缓冲区⼤⼩放⼊到这个字段中通知给发送端。这个字段的值越⼤，说明⽹络的吞吐量越⼤。当接收端的这个缓冲区⼀旦⾯临数据溢出时，窗⼝⼤⼩的值也会随之被设置成⼀个更⼩的值发送给发送端，从⽽控制数据发送量。
图3
c）拥塞控制
有了窗⼝控制，发送端和接收端能够连续发送⼤量数据包。不过，如果在通信刚开始的时候就发送⼤量数据，也可能会引发其他问题。
⼀般来说，计算机⽹络都处在⼀个共享的环境。因此也有可能会因为其他主机之间的通信使得⽹络拥堵。在⽹络出现拥堵时，如果突然发送⼀个较⼤量的数据，极有可能导致整个⽹络的瘫痪。
解决⽅案：
柴油脱剂
固态负氢离子在慢启动的时候，将这个拥塞窗⼝的⼤⼩设置为1个数据段(1MSS)发送数据。之后每收到⼀次确认应答，拥塞窗⼝的值就加1。在发送数据包时，将拥塞窗⼝的⼤⼩与接收端主机通知的窗⼝⼤⼩做⽐较，然后按照它们当中较⼩的那个值，发送⽐其还⼩的数据量。
问题：在使⽤窗⼝控制中，如果出现段丢失该怎么办？
① 情况1
丢失描述：发送端没有收到接收端的确认应答。
解决⽅案：这种情况，数据已经给到达对端，不需要进⾏重发。使⽤了窗⼝机制，某些确认应答即使丢失也⽆需重发，可以通过下⼀个确认应答进⾏确认。
②情况2
丢失描述：发送端会重复的收到接收端的同⼀序号应答。
解决⽅案：发送端主机如果连续三次接收到同⼀个确认应答，就会将其对应的数据进⾏重发。
三、UDP可靠性传输KCP协议原理
3.1 KCP简介
KCP是⼀个快速可靠传输ARQ(Automatic Repeat-reQuest)协议，相⽐于TCP，KCP以浪费10%-20%的带宽代价，换取⽐TCP0%-40%的传输速度，并且最⼤延迟降低三倍的传输效果。
KCP为纯算法实现，不负责底层协议的收发，需要使⽤者⾃⼰定义下层数据包的发送⽅式，以callback的⽅式提供给KCP。KCP内部不会有任何的系统调⽤，就连时钟都需要外部传递进来。
KCP整个协议只有ikcp.h，ikcp.c两个源⽂件，使⽤者可以很⽅便的集成到⾃⼰的协议栈中。⽐如，你
实现了⼀个P2P或某个基于UDP的协议，⽽缺乏⼀套完善的ARQ可靠协议，那么简单的拷贝这两个⽂件到已有项⽬中，稍微修改下，即可使⽤。
3.2 KCP特性
相⽐于TCP，KCP具有以下特性：
1）RTO翻倍 vs 不翻倍
TCP超时计算是RTOx2，这样连续丢三次包就变成RTOx8了，⼗分恐怖；
KCP启动快速模式后不x2，只是x1.5（实验证明1.5这个值相对⽐较好），提⾼了传输速度。
2）选择性重传 vs 全部重传
高粱红素TCP丢包时会全部重传从丢的那个包开始以后的数据；
KCP是选择性重传，只重传真正丢失的数据包。
3）快速重传
机制：跳过多少个包马上重传（若使⽤过了快速重传，可以不考虑RTO）。
⽰例：发送端发送了1,2,3,4,5⼏个包，然后收到远端的ACK: 1, 3, 4, 5，当收到ACK3时， KCP知道2被跳过1次，收到ACK4时，知道2被跳过了2次，此时可以认为2号丢失，不⽤等超时，直接重传2号包，⼤⼤改善了丢包时的传输速度。
4）延迟ACK vs ⾮延迟ACK
TCP为了充分利⽤带宽，延迟发送ACK（ NODELAY都没⽤），这样超时计算会算出较⼤ RTT时间，延长了丢包时的判断过程；
KCP的ACK是否延迟发送可以调节。
5）UNA vs ACK+UNA
ARQ模型响应有两种， UNA（此编号前所有包已收到，如TCP）和ACK（该编号包已收到），光⽤UNA将导致全部重传，光⽤ACK 则丢失成本太⾼，以往协议都是⼆选其⼀；
KCP协议中，除去单独的 ACK包外，所有包都有UNA信息。
6）⾮退让流
KCP正常模式同TCP⼀样使⽤公平退让法则，即发送窗⼝⼤⼩由：发送缓存⼤⼩、接收端剩余接收缓存⼤⼩、丢包退让及慢启动这四要素决定。
KCP传送及时性要求很⾼的⼩数据时，可选择通过配置跳过后两步，仅⽤前两项来控制发送频率。以牺牲部分公平性及带宽利⽤率之代价，换取了开着BT都能流畅传输的效果。
3.3 KCP⼀些名词说明
⽤户数据：应⽤层发送的数据，⽐如⼀张图⽚2KB的数据。
MTU：最⼤传输单元，即每次发送的最⼤数据。
RTO：Retransmission TimeOut，重传超时时间。
cwnd：ongestion window，拥塞窗⼝，表⽰发送⽅可发送多少个KCP数据包。与接收⽅窗⼝有关，与⽹络状况（拥塞控制）有关，与发送窗⼝⼤⼩有关。
rwnd：receiver window，接收⽅窗⼝⼤⼩，表⽰接收⽅还可接收多少个KCP数据包。
snd_queue：待发送KCP数据包队列。
snd_nxt：下⼀个即将发送的kcp数据包序列号。
snd_una：下⼀个待确认的序列号。
3.4 KCP协议格式
图4
