KCP协议基本数据结构和算法图文介绍
在特定的应用场合,单纯的使用 TCP 不能满足需要。直接使用 UDP 数据报不能保证数据的可靠性,常需要在应用层基于 UDP 实现一套可靠的传输协议。
直接使用 KCP 协议是一种选择,它实现了健全的自动重传协议,并在此之上提供了自由的参数调整。通过配置参数和合适的调用方式来适应不同场景的需求。
KCP 简介:
KCP是一个快速可靠协议,能以比 TCP 浪费 10%-20% 的带宽的代价,换取平均延迟降低 30%-40%,且最大延迟降低三倍的传输效果。纯算法实现,并不负责底层协议(如UDP)的收发,需要使用者自己定义下层数据包的发送方式,以 callback的方式提供给 KCP。 连时钟都需要外部传递进来,内部不会有任何一次系统调用。 整个协议只有 ikcp.h, ikcp.c两个源文件,可以方便的集成到用户自己的协议栈中。也许你实现了一个P2P,或者某个基于 UDP的协议,而缺乏一套完善的ARQ可靠协议实现,那么简单的拷贝这两个文件到现有项目中,稍微编写两行代码,即可使用。
本文对 KCP 协议的基础收发流程、拥塞窗口、超时算法作简单介绍,并同时提供了参考的示例代码。
参阅的 KCP 的版本为撰写文章时的最新版本。本文不会完全贴上所有KCP的源代码,会在关键处添加指向源代码相应位置的链接。
IKCPSEG 结构用于存储发送和接收的数据段状态。
IKCPSEG 所有字段描述:
struct IKCPSEG
{
/* 队列节点,IKCPSEG 作为一个队列元素,此结构指向了队列后前后元素 */
struct IQUEUEHEAD node;
/* 会话编号 */
IUINT32 conv;
/* 指令类型 */
IUINT32 cmd;
/* 分片号 (fragment)
发送数据大于 MSS 时将被分片,0为最后一个分片.
意味着数据可以被recv,如果是流模式,所有分片号都为0
*/
IUINT32 frg;
/* 窗口大小 */
IUINT32 wnd;
/* 时间戳 */
IUINT32 ts;
/* 序号 (sequence number) */
IUINT32 sn;
/* 未确认的序号 (unacknowledged) */
IUINT32 una;
/* 数据长度 */
IUINT32 len;
/* 重传时间 (resend timestamp) */
IUINT32 resendts;
/* 重传的超时时间 (retransmission timeout) */
IUINT32 rto;
/* 快速确认计数 (fast acknowledge) */
IUINT32 fastack;
/* 发送次数 (transmit) */
IUINT32 xmit;
/* 数据内容 */
char data[1];
};结构末尾的 data 字段用于索引结构体尾部的数据,额外分配的内存扩展了运行时的 data 字段数组的实际长度 (ikcp.c:173)。
IKCPSEG 结构仅为内存状态,仅有部分字段会编码到传输协议中。
ikcp_encode_seg 函数对传输协议头部编码:
/* 协议头一共 24 字节 */
static char *ikcp_encode_seg(char *ptr, const IKCPSEG *seg)
{
/* 会话编号 (4 Bytes) */
ptr = ikcp_encode32u(ptr, seg->conv);
/* 指令类型 (1 Bytes) */
ptr = ikcp_encode8u(ptr, (IUINT8)seg->cmd);
/* 分片号 (1 Bytes) */
ptr = ikcp_encode8u(ptr, (IUINT8)seg->frg);
/* 窗口大小 (2 Bytes) */
ptr = ikcp_encode16u(ptr, (IUINT16)seg->wnd);
/* 时间戳 (4 Bytes) */
ptr = ikcp_encode32u(ptr, seg->ts);
/* 序号 (4 Bytes) */
ptr = ikcp_encode32u(ptr, seg->sn);
/* 未确认的序号 (4 Bytes) */
ptr = ikcp_encode32u(ptr, seg->una);
/* 数据长度 (4 Bytes) */
ptr = ikcp_encode32u(ptr, seg->len);
return ptr;
}IKCPCB 结构存储了 KCP 协议的所有上下文,通过创建对端的两个 IKCPCB 对象进行协议通讯。
struct IKCPCB
{
/* conv: 会话编号
mtu: 最大传输单元
mss: 最大报文长度
state: 此会话是否有效 (0: 有效 ~0:无效)
*/
IUINT32 conv, mtu, mss, state;
/* snd_una: 发送的未确认数据段序号
snd_nxt: 发送的下一个数据段序号
rcv_nxt: 期望接收到的下一个数据段的序号
*/
IUINT32 snd_una, snd_nxt, rcv_nxt;
/* ts_recent: (弃用字段?)
ts_lastack: (弃用字段?)
ssthresh: 慢启动阈值 (slow start threshold)
*/
IUINT32 ts_recent, ts_lastack, ssthresh;
/* rx_rttval: 平滑网络抖动时间
rx_srtt: 平滑往返时间
rx_rto: 重传超时时间
rx_minrto: 最小重传超时时间
*/
IINT32 rx_rttval, rx_srtt, rx_rto, rx_minrto;
/* snd_wnd: 发送窗口大小
rcv_wnd: 接收窗口大小
rmt_wnd: 远端窗口大小
cwnd: 拥塞窗口 (congestion window)
probe: 窗口探测标记位,在 flush 时发送特殊的探测包 (window probe)
*/
IUINT32 snd_wnd, rcv_wnd, rmt_wnd, cwnd, probe;
/* current: 当前时间 (ms)
interval: 内部时钟更新周期
ts_flush: 期望的下一次 update/flush 时间
xmit: 全局重传次数计数
*/
IUINT32 current, interval, ts_flush, xmit;
/* nrcv_buf: rcv_buf 接收缓冲区长度
nsnd_buf: snd_buf 发送缓冲区长度
nrcv_que: rcv_queue 接收队列长度
nsnd_que: snd_queue 发送队列长度
*/
IUINT32 nrcv_buf, nsnd_buf;
IUINT32 nrcv_que, nsnd_que;
/* nodelay: nodelay模式 (0:关闭 1:开启)
updated: 是否调用过 update 函数
*/
IUINT32 nodelay, updated;
/* ts_probe: 窗口探测标记位
probe_wait: 零窗口探测等待时间,默认 7000 (7秒)
*/
IUINT32 ts_probe, probe_wait;
/* dead_link: 死链接条件,默认为 20。
(单个数据段重传次数到达此值时 kcp->state 会被设置为 UINT_MAX)
incr: 拥塞窗口算法的一部分
*/
IUINT32 dead_link, incr;
/* 发送队列 */
struct IQUEUEHEAD snd_queue;
/* 接收队列 */
struct IQUEUEHEAD rcv_queue;
/* 发送缓冲区 */
struct IQUEUEHEAD snd_buf;
/* 接收缓冲区 */
struct IQUEUEHEAD rcv_buf;
/* 确认列表, 包含了序号和时间戳对(pair)的数组元素*/
IUINT32 *acklist;
/* 确认列表元素数量 */
IUINT32 ackcount;
/* 确认列表实际分配长度 */
IUINT32 ackblock;
/* 用户数据指针,传入到回调函数中 */
void *user;
/* 临时缓冲区 */
char *buffer;
/* 是否启用快速重传,0:不开启,1:开启 */
int fastresend;
/* 快速重传最大次数限制,默认为 5*/
int fastlimit;
/* nocwnd: 控流模式,0关闭,1不关闭
stream: 流模式, 0包模式 1流模式
*/
int nocwnd, stream;
/* 日志标记 */
int logmask;
/* 发送回调 */
int (*output)(const char *buf, int len, struct IKCPCB *kcp, void *user);
/* 日志回调 */
void (*writelog)(const char *log, struct IKCPCB *kcp, void *user);
};
typedef struct IKCPCB ikcpcb;在 KCP 中仅有 2 种队列结构:
IQUEUEHEAD 是一个简单的双向链表,其指向了队列起始(prev)和末尾(next)元素:
struct IQUEUEHEAD {
/*
next:
作为队列时: 队列的首元素 (head)
作为元素时: 当前元素所在队列的下一个节点
prev:
作为队列时: 队列的末元素 (last)
作为元素时: 当前元素所在队列的前一个节点
*/
struct IQUEUEHEAD *next, *prev;
};
typedef struct IQUEUEHEAD iqueue_head;队列为空时 next/prev 会指向队列自身,而不是 NULL。
作为队列元素的 IKCPSEG 结构头部也复用了 IQUEUEHEAD 结构:
struct IKCPSEG
{
struct IQUEUEHEAD node;
/* ... */
}作为队列元素时记录了当前元素所在队列中的前一个(prev)元素和后一个元素(next)。
prev 指向队列时意味着当前元素所在队列首,next 指向队列时意味着当前元素所在队列尾。
所有的 队列操作 以宏的方式提供。
KCP 提供配置的方法有:
工作模式选项:
int ikcp_nodelay(ikcpcb *kcp, int nodelay, int interval, int resend, int nc)最大窗口选项:
int ikcp_wndsize(ikcpcb *kcp, int sndwnd, int rcvwnd);发送窗口大小 sndwnd 必须大于 0,接收窗口大小 rcvwnd 必须大于 128,单位为包,而非字节。
最大传输单元:
KCP 不负责探测 MTU,默认值为 1400 字节,可以使用 ikcp_setmtu 来设置该值。该值将会影响数据包归并及分片时候的最大传输单元。较小的 MTU 会影响路由转优先级。
本文提供了一份能够基础运行 KCP 的代码 kcp_basic.c,不到 100 行的示例代码为对 KCP 进行纯算法调用,不包括任何网络调度。(重要: 跟随文章调试它试试看!)
可以通过它来初步了解 IKCPCB 结构中的基本结构字段:
kcp.snd_queue: 发送队列 (kcp.nsnd_que 记录长度)kcp.snd_buf: 发送缓冲区 (kcp.nsnd_buf 记录长度)kcp.rcv_queue: 接收队列 (kcp.nrcv_que 记录长度)kcp.rcv_buf: 接收缓冲区 (kcp.nrcv_buf 记录长度)kcp.mtu: 最大传输单元kcp.mss: 最大报文长度以及结构 IKCPSEG 中的:
seg.sn: 序号seg.frg: 分片号通过 ikcp_create 函数来创建 KCP 上下文结构 IKCPCB。
IKCPCB 内部会通过外部调用 ikcp_send (用户输入到发送端) 和 ikcp_input 输入数据 (发送端输入到接收端) 来创建对应的 IKCPSEG 结构存储数据和状态。
另外会通过 ikcp_recv (用户从接收端取出) 和 ikcp_input 确认数据 (发送端收到接收端确认) 来移除 IKCPSEG 结构。
详细的数据流动方向见 队列与窗口 小节
IKCPSEG 的创建和销毁主要出现在上述四种情况,其它常见于内部队列之间的移动和其它优化。
在后面的文章中,所有出现的 IKCPCB 与 IKCPSEG 结构字段均会通过
标记来突出显示 (仅限 Markdown 浏览,其它可能看不到)。IKCPCB 结构的所有字段均会加上kcp.前缀,所有 IKCPSEG 结构字段均会加上seg.前缀。通常在源码中对应的变量名或者函数参数名称也为kcp或者seg。
此代码简单地对名为 k1 的 KCP 对象写入指定长度的数据,并从 k2 对象读出数据。KCP 配置为默认模式。
基本流程可以通过伪代码简单描述为:
/* 创建两个 KCP 对象 */
k1 = ikcp_create()
k2 = ikcp_create()
/* 向发送端 k1 写入数据 */
ikcp_send(k1, send_data)
/* 刷出数据,执行 kcp->output 回调 */
ikcp_flush(k1)
/* output 回调接收到带协议包头的分片数据,执行发送 */
k1->output(fragment_data)
/* 接收端 k2 收到输入数据 */
ikcp_input(k2, input_data)
/* 接收端刷出数据,会发送确认包到 k1 */
ikcp_flush(k2)
/* 发送端 k1 收到确认数据 */
recv_data = ikcp_recv(k1, ack_data)
/* 尝试读出数据 */
recv = ikcp_recv(k2)
/* 验证接收数据和发送数据一致 */
assert(recv_data == send_data)在示例代码中,创建的 KCP 对象除了 kcp.output 绑定了 kcp_user_output 函数用于定义 KCP 对象的输出数据的行为。kcp.writelog 也绑定了 kcp_user_writelog 函数用于调试打印。
另外由于 kcp.output 回调不能递归地调用其它 ikcp_input (因为最终会递归到自身的 kcp.output),所以所有输出的数据必须存储在一个中间位置,退出 kcp.output 函数后,再输入到 k2 中。这是示例代码中定义的 OUTPUT_CONTEXT 结构的作用。
尝试运行示例代码,会得到下列输出内容 (# 符号追加的内容为说明):
# k1.output 被调用,输出 1400 字节
k1 [RO] 1400 bytes
# k2 被调用 ikcp_input 输入数据
k2 [RI] 1400 bytes
# psh 数据推送分支处理
k2 input psh: sn=0 ts=0
# k2.output 被调用,输出确认包,数据长度24字节
k2 [RO] 24 bytes
# k1 被调用 ikcp_input 输入数据
k1 [RI] 24 bytes
# 序号 sn=0 被确认
k1 input ack: sn=0 rtt=0 rto=100
k1 [RO] 1400 bytes
k1 [RO] 1368 bytes
k2 [RI] 1400 bytes
k2 input psh: sn=1 ts=0
k2 [RI] 1368 bytes
k2 input psh: sn=2 ts=0
k2 [RO] 48 bytes
k1 [RI] 48 bytes
k1 input ack: sn=1 rtt=0 rto=100
k1 input ack: sn=2 rtt=0 rto=100
# k2 被调用 kcp_recv 取出数据
k2 recv sn=0
k2 recv sn=1
k2 recv sn=2输出内容均为 KCP 代码内置的调试信息打印,通过 kcp_user_writelog 额外追加了 k1/k2 行前缀作为区分。
对此代码的发送确认流程绘制完整的示意图描述为 (两倍大图):
对 k1 调用 ikcp_send: (图步骤 1-1)
向发送端写入了长度为 4096 的数据。依据 kcp.mss 被切割成三个长度为 1376/1376/1344 的包,每个包的 seg.frg 分片标记分别为 2/1/0。
kcp.mtu 最大传输单元 定义了 ikcp.output 回调每次收到的最大数据长度,默认为 1400。
示意图中 ikcp_output 方法最终会调用
ikcp.output函数指针。(ikcp.c:212)
kcp.mss 最大报文长度 由 kcp.mtu 减去协议开销 (24字节) 计算得来,默认为 1376。
此时不会执行任何 kcp.output 回调,所有分片数据均会分配并记录到 IKCPSEG 结构中,并追加到 kcp.snd_queue 队列 (ikcp.c:528)。
此时 k1 的 kcp.snd_queue 队列长度为 3,kcp.snd_buf 队列长度为 0。
对 k1 调用 ikcp_flush: (图步骤 1-2)
这里忽略窗口具体计算流程,只需要知道这里 k1 首次调用 ikcp_flush 时拥塞窗口
kcp.cwnd的值为 1。
因为拥塞窗口限制, 所以首次发包仅能发送一个。将 kcp.snd_queue 队列首数据长度为 1376 的 IKCPSEG 对象被移动到 kcp.snd_buf 队列中 (ikcp.c:1028), 并且依据 kcp.snd_nxt 分配序号 seg.sn 的值为 0 (ikcp.c:1036), seg.cmd 字段为 IKCP_CMD_PUSH, 表示一个数据推送包。
此时 k1 的 kcp.snd_queue 队列长度为 2,kcp.snd_buf 队列长度为 1。
步骤 1-3 中对首次发送的数据执行 ikcp_output 调用 (ikcp.c:1113) 发送出数据包 [PSH sn=0 frg=2 len=1376]。
数据指令类型仅有四种: IKCP_CMD_PUSH (数据推送) IKCP_CMD_ACK (确认) IKCP_CMD_WASK (窗口探测) IKCP_CMD_WINS (窗口应答),定义在 ikcp.c:29
**对 k2 调用 [ikcp_input](https://github.com/skywind3000/kcp/blob/f553d
暂无开放 Issues,或尚未同步最近议题。