UDP的可靠性传输——KCP

在网络中，我们认为传输是不可靠的，而在很多场景下我们需要的是可靠的数据，所谓的可靠，指的是数据能够正常收到，且能够顺序收到，于是就有了ARQ协议， TCP之所以可靠就是基于此。

ARQ协议(Automatic Repeat-reQuest)，即自动重传请求，是传输层的错误纠正协议之一，它通过使用确认和超时两个机制，在不可靠的网络上实现可靠的信息传输。

2.1、ARQ协议-停等式(stop-and-wait)

1、发送方对接收方发送数据包，然后等待接收方回复ACK并且开始计时。

2、在等待过程中，发送方停止发送新的数据包。

3、当数据包没有成功被接收方接收，接收方不会发送ACK.这样发送方在等待一定时间后，重新发送数据包。

4、反复以上步骤直到收到从接收方发送的ACK。

缺点：较长的等待时间导致低的数据传输速度。

2.2、ARQ协议-回退n帧(go-back-n)

（1）、为了克服停等式协议长时间等待ACK的缺陷，连续ARQ协议会连续发送一组数据包，然后再等待这些数据包的ACK。

（2）、什么是滑动窗口：发送方和接收方都会维护一个数据帧的序列，这个序列被称作窗口。发送方的窗口大小由接收方确定，目的在于控制发送速度，以免接收方的缓存不够大，而导致溢出，同时控制流量也可以避免网络拥塞。协议中规定，对于窗口内未经确认的分组需要重传。

（3）、回退N步(Go-Back-N,GBN)：回退N步协议允许发送方在等待超时的间歇，可以继续发送分组。所有发送的分组，都带有序号。在GBN协议中，发送方需响应以下三种事件：

1、上层的调用。上层调用相应send()时，发送方首先要检查发送窗口是否已满。

2、接收ACK。在该协议中，对序号为n的分组的确认采取累积确认的方式，表明接收方已正确接收到序号n以前(包括n)的所有分组。

3、超时。若出现超时，发送方将重传所有已发出但还未被确认的分组。

（4）、具体的流程：对于接收方来说，若一个序号为n的分组被正确接收，并且按序，则接收方会为该分组返回一个ACK给发送方，并将该分组中的数据交付给上层。在其他情况下，接收方都会丢弃分组。若分组n已接收并交付，那么所有序号比n小的分组也已完成了交付。

因此GBN采用累积确认是一个很自然的选择。发送方在发完一个窗口里的所有分组后，会检查最大的有效确认，然后从最大有效确认的后一个分组开始重传。

总结：GBN采用的技术包括序号、累积确认、检验和以及计时/重传。虽然GBN改善了停等协议中时间等待较长的缺陷，但它依旧存在着性能问题。特别是当窗口长度很大的时候，会使效率大大降低。

2.3、ARQ协议-选择性重传(selective repeat)

SR协议通过让发送方仅重传在接收方丢失或损坏了的分组，从而避免了不必要的重传，提高了效率。

        在SR协议下，发送方需响应以下三种事件：

        1、从上层收到数据：当从上层收到数据后，发送方需检查下一个可用于该分组的序号。若序号在窗口中则将数据发送。

        2、接收ACK：若收到ACK，且该分组在窗口内，则发送方将那个被确认的分组标记为已接收。若该分组序号等于基序号，则窗口序号向前移动到具有最小序号的未确认分组处。若窗口移动后并且有序号落在窗口内的未发送分组，则发送这些分组。

        3、超时：若出现超时，发送方将重传已发出但还未确认的分组。与GBN不同的是， SR协议中的每个分组都有独立的计时器。

         在SR协议下，接收方需响应以下三种事件： (假设接收窗口的基序号为4，分组长度也为4)

        1、序号在[4,7]内的分组被正确接收。该情况下，收到的分组落在接收方的窗口内，一个ACK 将发送给发送方。若该分组是以前没收到的分组，则被缓存。若该分组的序号等于基序号4，则该分组以及以前缓存的序号连续的分组都交付给上层，然后，接收窗口将向前移动。

        2、序号在[0,3]内的分组被正确接收。在该情况下，必须产生一个ACK，尽管该分组是接收方以前已确认过的分组。若接收方不确认该分组，发送方窗口将不能向前移动。

        3、其他情况。忽略该分组对于接收方来说，若一个分组正确接收而不管其是否按序，则接收方会为该分组返回一个ACK 给发送方。失序的分组将被缓存，直到所有丢失的分组都被收到，这时才可以将一批分组按序交付给上层。

3、RTT和RTO

RTO（Retransmission TimeOut）即重传超时时间。

RTT(Round-Trip Time)：往返时延。表示从发送端发送数据开始，到发送端收到来自接收端的确认（接收端收到数据后便立即发送确认），总共经历的时延。

RTT由三部分组成：

1、链路的传播时间（propagation delay）

2、末端系统的处理时间

3、路由器缓存中的排队和处理时间（queuing delay）

其中，前两个部分的值对于一个TCP连接相对固定，路由器缓存中的排队和处理时间会随着整个网络拥塞程度的变化而变化。所以RTT的变化在一定程度上反应网络的拥塞程度。

4、流量控制

双方在通信的时候，发送方的速率与接收方的速率是不一定相等，如果发送方的发送速率太快，会导致接收方处理不过来，这时候接收方只能把处理不过来的数据存在缓存区里（失序的数据包也会被存放在缓存区里）接收缓存。

如果缓存区满了发送方还在疯狂着发送数据，接收方只能把收到的数据包丢掉，大量的丢包会极大着浪费网络资源，因此，我们需要控制发送方的发送速率，让接收方与发送方处于一种动态平衡才好。

对发送方发送速率的控制，称之为流量控制。公平使用带宽100M 10个10M左右。

5、如何进行流量控制（滑动窗口）

接收方每次收到数据包，可以在发送确定报文的时候，同时告诉发送方自己的缓存区还剩余多少是空闲的，我们也把缓存区的剩余大小称之为接收窗口大小，用变量win来表示接收窗口的大小。

发送方收到之后，便会调整自己的发送速率，也就是调整自己发送窗口的大小，当发送方收到接收窗口的大小为0时，发送方就会停止发送数据，防止出现大量丢包情况的发生。

        当发送方停止发送数据后，该怎样才能知道自己可以继续发送数据？

        当接收方处理好数据，接受窗口 win > 0 时，接收方发个通知报文去通知发送方，告诉他可以继续发送数据了。当发送方收到窗口大于0的报文时，就继续发送数据。

        当发送方收到接受窗口 win = 0 时，这时发送方停止发送报文，并且同时开启一个定时器，每隔一段时间就发个测试报文去询问接收方，打听是否可以继续发送数据了，如果可以，接收方就告诉他此时接受窗口的大小；如果接受窗口大小还是为0，则发送方再次刷新启动定时器。

6、流量控制小结

1.通信的双方都拥有两个滑动窗口，一个用于接受数据，称之为接收窗口；一个用于发送数据，称之为拥塞窗口(即发送窗口)。指出接受窗口大小的通知我们称之为窗口通告。

        2. 接收窗口的大小固定吗？接受窗口的大小是根据某种算法动态调整的。

        3. 接收窗口越大越好吗？当接收窗口达到某个值的时候，再增大的话也不怎么会减少丢包率的了，而且还会更加消耗内存。所以接收窗口的大小必须根据网络环境以及发送发的的拥塞窗口来动态调整。

        4. 发送窗口和接收窗口相等吗？接收方在发送确认报文的时候，会告诉发送发自己的接收窗口大小，而发送方的发送窗口会据此来设置自己的发送窗口，但这并不意味着他们就会相等。首先接收方把确认报文发出去的那一刻，就已经在一边处理堆在自己缓存区的数据了，所以一般情况下接收窗口>= 发送窗口。

7、拥塞控制

拥塞控制和流量控制虽然采取的动作很相似，但拥塞控制与网络的拥堵情况相关联，而流量控制与接收方的缓存状态相关联。

二：KCP如何让UDP可靠

1、RTO翻倍 vs 不翻倍

TCP超时计算是RTOx2，这样连续丢三次包就变成RTOx8了，十分恐怖，而KCP启动快速模式后不x2，只是x1.5（实验证明1.5这个值相对比较好），提高了传输速度。以RTO=100ms为例：

2、选择性重传 vs 全部重传

TCP丢包时会全部重传从丢的那个包开始以后的数据，KCP是选择性重传（SR），只重传真正丢失的数据包。

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一样使用公平退让法则，即发送窗口大小由：发送缓存大小、接收端剩余接收缓存大小、丢包退让及慢启动这四要素决定。但传送及时性要求很高的小数据时，可选择通过配置跳过后两步，仅用前两项来控制发送频率。以牺牲部分公平性及带宽利用率之代价，换取了开着BT都能流畅传输的效果。

三：kcp的使用

1、使用方式

1.1：创建KCP对象：ikcpcb *kcp = ikcp_create(conv, user);

1.2：设置发送回调函数（如UDP的send函数）：kcp->output = udp_output; 但是真正发送数据需要调用sendto。

1.3：循环调用update：ikcp_update(kcp, millisec); //在一个线程、定时器5ms/10m做调度

1.4：输入一个应用层数据包（如UDP收到的数据包）：ikcp_input(kcp,received_udp_packet,received_udp_size); 但是需要我们使用recvfrom接收，然后扔到kcp里面做解析。

1.5：发送数据：ikcp_send(kcp1, buffer, 8); 在这里做用户层接口。

1.6：接收数据：hr = ikcp_recv(kcp2, buffer, 10); 在这里用户层读取数据。

2、udp的并发编程

UDP相比TCP中，是不存在listen和accept的，面向无连接的。那要怎么进行并发编程呢？

我们可以在客户端发送数据包的前面存放conv会话id，表示从哪里发送来的数据，代表一种连接。但是每个客户端和服务端之间都会产生一个udp_socket通道。但是这个会话id是由客户端写入的，会不会出现一种情况，导致两个客户端之间存在一样的会话id呢？

确实会存在这样的情况发生。但是我们可以通过uuid算法，生成唯一的id。当然我们可以让服务端产生唯一的会话id，让客户端通过http向服务端请求一个会话id。

3、KCP协议头

[0,3]conv:连接号	UDP是无连接的，conv用于表示来自于哪个客户端。对连接的一种替代
[4]cmd:命令字	IKCP_CMD_ACK确认命令， IKCP_CMD_WASK接收窗口大小询问命令，IKCP_CMD_WINS接收窗口大小告知命令
[5]frg:分片	用户数据可能会被分成多个KCP包，发送出去
[6,7]wnd	接收窗口大小，发送方的发送窗口不能超过接收方给出的数值
[8,11]ts	时间序列
[12,15]sn	序列号
[16,19]una	下一个可接收的序列号。其实就是确认号，收到 sn=10的包，una为11
[20,23]len	数据长度
data	用户数据，这一次发送的数据长度

具体的源码需要自己去看哦，感谢大家的收看！https://xxetb.xetslk.com/s/2D96kH

标签：UDP,可靠性,窗口,重传,ACK,发送,分组,KCP,接收
From： https://blog.csdn.net/2301_76446998/article/details/141286560