learning kcp protocol
1.0.0
在特定的應用場合，單純的使用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: (圖步驟2-1)
輸入資料包[PSH sn=0 frg=2 len=1376] ，進行解析包頭以及合法性檢查。 (ikcp.c:769)
解析資料包的類型，進入資料推送分支處理。 (ikcp.c:822)
記錄封包的seq.sn值和seq.ts值到確認列表kcp.acklist中(ikcp.c:828),請注意:這個範例中seq.ts的值永遠為0。
將接收的資料包加入kcp.rcv_buf佇列。 (ikcp:709)
對kcp.rcv_buf佇列檢查的首個資料包是否可用，若為可用的資料包，則移至kcp.rcv_queue佇列中。 (ikcp.c:726)
對於kcp.rcv_buf中的可用的封包定義為:期望接收的下一個資料序號(取自kcp.rcv_nxt ，這裡下一個資料序號應該為seg.sn == 0) 且kcp.rcv_queue佇列的長度小於接收視窗大小。
此步驟中直接將kcp.rcv_buf佇列唯一的資料包直接移動到了kcp.rcv_queue佇列。
此時k2 的kcp.>rcv_queue列長度為1， kcp.snd_buf佇列長度為0。下一個接收資料序號kcp.rcv_nxt的值從0 更新到了1。
對k2 呼叫ikcp_flush: (圖例步驟2-2)
在k2 的首次ikcp_flush 呼叫中。因為確認列表kcp.acklist中有數據，所以會編碼確認包並發送出(ikcp.c:958)。
其中確認包中的seg.una值被賦值為kcp.rcv_nxt =1。
這個包記為[ACK sn=0 una=1] :表示在ack 確認中，包序號0 被確認。在una 確認中，包序號1 之前的所有包都被確認。
步驟2-3 中呼叫kcp.output發出資料包。
對k2 呼叫ikcp_recv: (圖步驟2-4)
檢查kcp.rcv_queue佇列中是否含有seg.frp值為0 的的包(ikcp.c:459)，若含有此包，則記錄首個seg.frp ==0 的包以及此包之前的包的數據總長度作為返回值傳回。若沒有則此函數傳回失敗值-1。
因為此時kcp.rcv_queue只有套件[PSH sn=0 frg=2 len=1376] ，所以嘗試讀取失敗。
如果是流模式下(kcp.stream != 0), 所有的包都會被標記為
seg.frg=0。此時kcp.rcv_queue佇列有任何包，都會被讀取成功。
對k1 呼叫ikcp_input: (圖步驟3-1)
輸入資料包[ACK sn=0 una=1] 。
UNA確認:
收到的任何套件都會先嘗試進行UNA 確認(ikcp.c:789)
透過確認包的seg.una值確認並移除了所有kcp.snd_buf佇列中seg.sn值小於una 值的包(ikcp:599)。
[PSH sn=0 frg=2 len=1376]在k1 的kcp.snd_buf佇列中被確認並移除。
ACK確認:
解析資料包的類型，進入確認分支處理。 (ikcp.c:792)
將確認包的序號進行比對並移除對應的包。 (ikcp.c:581)
在步驟3-1 執行ACK 確認時， kcp.snd_buf佇列已經為空，因為唯一的套件[PSH sn=0 frg=2 len=1376]預先被UNA 確認完畢。
若kcp.snd_buf佇列頭部資料發生了確認( kcp.snd_una發生了變化)，此時重新計算擁塞視窗大小cwnd 值更新為2 (ikcp.c:876)。
UNA / ACK 確認示意圖, 此圖額外記錄了流程示意圖中未標記的kcp.snd_una的狀態:
對於順序到達的確認包，ACK 確認不會起作用。對於亂序到達的包，透過ACK 確認後單獨移除此包:
對k1 呼叫ikcp_flush: (圖步驟3-2)
如步驟1-2 一樣，新的壅塞視窗kcp.cwnd的值已經更新為2，此次會發出剩餘的兩個資料包: [PSH sn=1 frg=1 len=1376] [PSH sn=2 frg=0 len=1344] 。
步驟3-3 實際會呼叫兩次kcp.output分別發出封包。
對k2 呼叫ikcp_input: (圖步驟4-1)
輸入資料包[PSH sn=1 frg=1 len=1376]和[PSH sn=2 frg=0 len=1344] 。
每個包被加入kcp.rcv_buf佇列中，其都是可用的，最終全部被移到kcp.rcv_queue佇列。
此時k2 的kcp.rcv_queue佇列長度為3， kcp.snd_buf長度為0。預期接收的下一個包kcp.rcv_nxt的值從1 更新到了3。
對k2 呼叫ikcp_flush: (圖步驟4-2)
kcp.acklist中的確認訊息會被編碼為套件[ACK sn=1 una=3]和[ACK sn=2 una=3]在步驟4-3 傳送。
實際上這兩個包會被寫入一個緩衝區然後進行一次kcp.output呼叫。
對k2 呼叫ikcp_recv: (圖步驟4-4)
現在kcp.rcv_queue中有三個未讀取的封包: [PSH sn=0 frg=2 len=1376] [PSH sn=1 frg=1 len=1376]和[PSH sn=2 frg=0 len=1344]
此時符合讀取到一個seg.frg值為0 的包，計算可讀取總長度為4096。繼而會全部讀取三個套件中的資料寫入讀取緩衝區並回傳成功。
需要注意另一種情況: 若此時kcp.rcv_queue佇列中含有seg.frg值為2/1/0/2/1/0 的2 次使用者傳送包被分片成6 個資料包時，對應的也需要呼叫2 次ikcp_recv 來讀出全部收到的完整資料。
對k1 呼叫ikcp_input: (圖步驟5-1)
輸入確認封包[ACK sn=1 una=3]和[ACK sn=2 una=3] ，解析到seg.una =3 時。包[PSH sn=1 frg=1 len=1376] [PSH sn=2 frg=0 len=1344]從kcp.snd_buf佇列中透過una 確認完畢並移除。
所有發送的數據均已確認。
視窗用於流量控制。它標記了隊列邏輯上的一段範圍。由於佇列因為實際資料的處理，位置不斷向序號高位移動。邏輯上此視窗也會不斷移動，同時也會伸縮大小，所以也稱為滑動視窗( Sliding window )
此示意圖為"基本資料發送與接收流程" 小節中流程示意圖步驟3-1 至步驟4-1 的另一種表現形式。作為步驟範圍外的操作，資料方向均以半透明的箭頭表示。
所有資料透過箭頭指向的函數處理前往新的位置(兩倍大圖):
傳送端ikcp_send函數傳入數據，會經過資料切片處理後直接存入kcp.snd_queue傳送佇列中。
每次呼叫ikcp_flush時。會依據傳送視窗大小kcp.snd_wnd和遠端視窗大小kcp.rmt_wnd以及壅塞視窗大小kcp.cwnd來計算此傳送的視窗大小，其值為三者最小值: min( kcp.snd_wnd , kcp.rmt_wnd , kcp.cwd ) (ikcp.c:1017)。
若透過ikcp_nodelay函數將nc 參數設定為1 透過關閉控流模式，忽略計算擁塞視窗的值。發送視窗的計算結果就是min( kcp.snd_wnd , kcp.rmt_wnd ) (ikcp.c:1018)。
在僅關閉控流模式的預設設定下，首次可傳送的資料包數量為kcp.snd_wnd的預設大小值32。這與基本收發流程範例中不一樣，範例中首次僅能發出一個包，因為預設開啟了控流。
新增傳送的封包會被移到kcp.snd_buf佇列。
對於ikcp_send 的資料僅有切片上限127的限制(即127*
kcp.mss=174752 位元組)。對於處於發送佇列中資料包的總數量沒有任何限制。見: 如何避免快取累積延遲
kcp.snd_buf在傳送緩衝區中儲存了即將或已經傳送過的資料。
每次呼叫ikcp_flush時，計算此次傳送視窗並且從kcp.snd_queue移動封包到目前佇列後。對目前佇列所有資料包會有三種情況的處理:
1.首次資料發送(ikcp.c:1053)
封包被傳送的次數會被記錄在seg.xmit中，首次傳送的處理比較簡單，會初始化一些用於重傳逾時的參數seg.rto / seg.resendts 。
2.資料超時(ikcp.c:1058)
當內部記錄的時間kcp.current超過套件本身的逾時時間seg.resendts時，發生逾時重傳。
3.資料跨越確認(ikcp.c:1072)
當資料端被跨越確認，跨越次數seg.fastack超過了跨越重送配置kcp.fastresend時，發生跨越重傳。 ( kcp.fastresend預設為0 ，為0 時計算為UINT32_MAX, 永遠不會發生跨越重傳。)發生逾時重傳後會重設目前套件seg.fastack為0。
確認列表是一個簡單的記錄列表，它原始地按照包的接收順序記錄序號和時間戳( seg.sn / seg.ts )。
因此在本文的示意圖中
kcp.ack_list都不會有任何留白的元素位置畫出。因為它不是一個邏輯上有序的隊列(同理，雖然在snd_queue隊列中包還未分配序號，但其邏輯上其序號已經確定)。
接收端中快取暫時無法處理的資料包。
ikcp_input 傳入的所有資料包會優先到達此佇列, 同時會按照原始到達順序記錄資訊到kcp.ack_list 。
只有兩種情況資料會依舊滯留在此佇列:
這裡先收到了包[PSH sn=0] ，符合可用包的條件，移動到kcp.rev_queue 。
緊接著收到了包[PSH sn=2] ，不為期望接收的下一個包( seg.sn == kcp.rcv_nxt ), 導致此包滯留在kcp.rcv_buf中。
收到包[PSH sn=1] , 兩個移動滯留的包[sn=1] [sn=2]到kcp.rcv_queue 。
kcp.rcv_queue接收佇列長度達到了接收視窗大小kcp.rcv_wnd (未及時呼叫ikcp_recv)。接收端中儲存了可被上層讀取的資料。
在流模式下會讀取所有可用資料包，在非流模式下會讀取分片資料段並組合成完整的原始資料。
讀取完成後會嘗試從kcp.rcv_buf移動資料到此佇列(可能是從滿接收視窗狀態中復原)。
發送視窗kcp.snd_wnd值是一個配置的值，預設為32。
遠端視窗kcp.rmt_wnd是發送端收到接收端的包時(不僅只是確認包) 會被更新的值。它記錄的是當前封包被接收端傳送時, 接收端接收佇列kcp.rcv_queue的可用長度(ikcp.c:1086)，初始值為128。
擁塞視窗是透過計算的值，在每次透過ikcp_input 收到資料時會按照演算法來增長。
若在刷出資料ikcp_flush 時偵測到遇到丟包和快速重傳則依照演算法重新計算。
初始化
kcp.cwnd的位置為1 時的位置在首次ikcp_update 時對ikcp_flush 呼叫中。
接收視窗kcp.rcv_wnd值是一個配置的值，預設為128。它限制了接收佇列kcp.rcv_queue的最大長度。
在本小節中，提供了一個基於"基本資料發送與接收"小節範例程式碼改進的版本kcp_optional.c，可以透過修改巨集定義來進一步觀察協定行為。
範例程式碼透過指定向k1 寫入指定次數的固定長度資料後，並完整地在k2 中讀出後，結束流程。
提供了巨集來控制指定的功能:
擁塞視窗透過kcp.cwnd和kcp.incr的值來記錄。由於kcp.cwnd所記錄的單位為包，需要額外的kcp.incr來記錄以位元組長度為單位表示的擁塞視窗。
與TCP 一樣，KCP 擁塞控制也分為慢啟動和擁塞避免兩個階段:
擁塞視窗成長；在確認資料包的過程中，每次kcp.snd_buf佇列頭部資料發生確認時(有效UNA 確認, kcp.snd_una發生變化時)。且擁塞視窗小於記錄的遠端視窗kcp.rmt_wnd時，進行擁塞視窗成長。 (ikcp:875)
1.若擁塞視窗小於慢啟動閾值kcp.ssthresh時，處於慢啟動階段，此時壅塞視窗成長相對激進。擁塞視窗增長一個單位。
2.若擁塞視窗大於等於慢啟動閾值時，處於擁塞避免階段，擁塞視窗成長相對保守。若kcp.incr每次增加mss/16 時，需要16 個有效UNA 確認後才成長一個單位壅塞視窗。實際的擁塞避免階段視窗增長為:
(mss * mss) / incr + (mss / 16)
由於incr=cwnd*mss 即:
((mss * mss) / (cwnd * mss)) + (mss / 16)
等價於:
(mss / cwnd) + (mss / 16)
擁塞視窗進行每cwnd 個和每16 個有效UNA 確認的疊加增長。
擁塞視窗減少: 當ikcp_flush 函數偵測到跨越重傳或逾時丟包時，進行壅塞視窗會減少。
1.發生跨越重傳時，慢啟動閾值kcp.ssthresh設定為未確認序號跨距的一半。擁塞視窗大小為慢啟動閾值加上快速重傳的設定值kcp.resend (ikcp:1117):
ssthresh = (snd_nxt - snd_una) / 2
cwnd = ssthresh + resend
2.偵測到丟包逾時時，慢啟動閾值設定成目前壅塞視窗的一半。擁塞視窗設定為1 (ikcp:1126):
ssthresh = cwnd / 2
cwnd = 1
觀察慢啟動1 : 以預設配置運行範例程式碼，會觀察到很快跳過慢啟動過程，這是由於預設的慢啟動閾值為2:
t=0 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
# 收到一个确认包且拥塞窗口小于慢启动阈值，incr 增加一个 mss
t=100 n=1 una=1 nxt=2 cwnd=2|2 ssthresh=2 incr=2752
# 开始拥塞避免
t=200 n=1 una=2 nxt=3 cwnd=2|2 ssthresh=2 incr=3526
t=300 n=1 una=3 nxt=4 cwnd=4|4 ssthresh=2 incr=4148
t=400 n=1 una=4 nxt=5 cwnd=4|4 ssthresh=2 incr=4690
...
輸出內容的t 為邏輯時間，n 為週期內k1 發送資料的次數，cwnd=1|1 的值表示豎線符號前面的1 為ikcp_flush 時計算出來的窗口，即控流模式下的min(kcp. snd_wnd, kcp.rmt_wnd, kcp.cwnd)，後面1的值為kcp.cwnd 。
以圖形化的方式來觀察預設配置下的擁塞視窗成長情況:當處於擁塞避免階段時，擁塞視窗越大時，擁塞視窗的成長越平穩。
觀察慢啟動2 : 調整範例設定慢啟動閾值初始值KCP_THRESH_INIT為16:
#define KCP_THRESH_INIT 16
t=0 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=16 incr=1376
t=100 n=1 una=1 nxt=2 cwnd=2|2 ssthresh=16 incr=2752
t=200 n=1 una=2 nxt=3 cwnd=3|3 ssthresh=16 incr=4128
t=300 n=1 una=3 nxt=4 cwnd=4|4 ssthresh=16 incr=5504
...
t=1300 n=1 una=13 nxt=14 cwnd=14|14 ssthresh=16 incr=19264
t=1400 n=1 una=14 nxt=15 cwnd=15|15 ssthresh=16 incr=20640
t=1500 n=1 una=15 nxt=16 cwnd=16|16 ssthresh=16 incr=22016
# 开始拥塞避免
t=1600 n=1 una=16 nxt=17 cwnd=16|16 ssthresh=16 incr=22188
t=1700 n=1 una=17 nxt=18 cwnd=16|16 ssthresh=16 incr=22359
...
僅截取傳輸回合前一小段，可以觀察到預設慢啟動也是以線性方式成長的。
觀察關閉延遲確認: 盡可能發送較多的數據，且關閉延遲發送選項ACK_DELAY_FLUSH , 同時模擬一次丟包:
#define KCP_WND 256, 256
#define KCP_THRESH_INIT 32
#define SEND_DATA_SIZE (KCP_MSS*64)
#define SEND_STEP 16
#define K1_DROP_SN 384
//#define ACK_DELAY_FLUSH
t=0 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=32 incr=1376
t=100 n=2 una=1 nxt=3 cwnd=2|2 ssthresh=32 incr=2752
t=200 n=4 una=3 nxt=7 cwnd=4|4 ssthresh=32 incr=5504
t=300 n=8 una=7 nxt=15 cwnd=8|8 ssthresh=32 incr=11008
t=400 n=16 una=15 nxt=31 cwnd=16|16 ssthresh=32 incr=22016
...
t=1100 n=52 una=269 nxt=321 cwnd=52|52 ssthresh=32 incr=72252
t=1200 n=56 una=321 nxt=377 cwnd=56|56 ssthresh=32 incr=78010
t=1300 n=62 una=377 nxt=439 cwnd=62|62 ssthresh=32 incr=84107
t=1400 n=7 una=384 nxt=446 cwnd=62|62 ssthresh=32 incr=84863
t=1500 n=1 una=384 nxt=446 cwnd=1|1 ssthresh=31 incr=1376
t=1600 n=2 una=446 nxt=448 cwnd=2|2 ssthresh=31 incr=2752
t=1700 n=4 una=448 nxt=452 cwnd=4|4 ssthresh=31 incr=5504
t=1800 n=8 una=452 nxt=460 cwnd=8|8 ssthresh=31 incr=11008
t=1900 n=16 una=460 nxt=476 cwnd=16|16 ssthresh=31 incr=22016
...
在此情況下，得到了一張經典的慢啟動和擁塞避免的圖。在第15傳輸回合時(t=1500) 偵測到丟包:
關閉延遲傳送選項表示接收資料方每執行一次ikcp_input 後會立即呼叫ikcp_flush 傳送回確認包。
此時的慢啟動過程以每RTT (Round-Trip Time, 往返時間) 以指數方式增長，因為每一個確認包會獨立發送讓發送方擁塞窗口增長, 又因為擁塞窗口的增長導致每RTT 內發送的包翻倍。
若延遲確認，會合併發送確認包。每次呼叫ikcp_input 函數時增長擁塞視窗的流程只會執行一次，所以合併接收的多個確認包不會起多次增長擁塞視窗的效果。
若時脈週期interval 大於RTT，那麼會以每interval 的時間進行指數增長，示意圖展示了一種可能的情況:
指數方式成長的前提是下次一發送的資料能夠滿足上一次資料包數量的兩倍之多，若本身向發送端寫入的資料不足，會無法達成指數成長的情況。
需要注意的是:範例程式碼即使進行了發送立即確認也僅僅只是影響接收端發出確認的方式。發送端也需要等待下一個週期才會處理這些確認包。所以這裡的時間t 僅供參考，除非在實際網路收發程式碼中也像這樣收到包不馬上處理存起來，一定要等到更新周期才回應。
以KCP 的特性來說肯定有更直接的方式讓擁塞窗口變得更大, 直接關閉流量控制以獲取更激進的發送:
#define KCP_NODELAY 0, 100, 0, 1
#define SEND_DATA_SIZE (KCP_MSS*127)
#define SEND_STEP 1
t=0 n=32 una=0 nxt=32 cwnd=32|1 ssthresh=2 incr=1376
t=100 n=32 una=32 nxt=64 cwnd=32|2 ssthresh=2 incr=2752
t=200 n=32 una=64 nxt=96 cwnd=32|2 ssthresh=2 incr=3526
t=300 n=31 una=96 nxt=127 cwnd=32|4 ssthresh=2 incr=4148
也可以依需求直接修改擁塞視窗的值。
觀察遠端視窗已滿:若發送資料的長度接近預設遠端視窗大小，且接收端不及時讀出，會發現一個無法發送任何資料的週期(注意在範例程式碼中接收端是先發送確認包後再讀出內容):
#define KCP_NODELAY 0, 100, 0, 1
#define SEND_DATA_SIZE (KCP_MSS*127)
#define SEND_STEP 2
t=0 n=32 una=0 nxt=32 cwnd=32|1 ssthresh=2 incr=1376
t=100 n=32 una=32 nxt=64 cwnd=32|2 ssthresh=2 incr=2752
t=200 n=32 una=64 nxt=96 cwnd=32|2 ssthresh=2 incr=3526
t=300 n=32 una=96 nxt=128 cwnd=32|4 ssthresh=2 incr=4148
t=400 n=0 una=128 nxt=128 cwnd=0|4 ssthresh=2 incr=4148
t=500 n=32 una=128 nxt=160 cwnd=32|4 ssthresh=2 incr=4148
t=600 n=32 una=160 nxt=192 cwnd=32|4 ssthresh=2 incr=4690
t=700 n=32 una=192 nxt=224 cwnd=32|4 ssthresh=2 incr=5179
t=800 n=30 una=224 nxt=254 cwnd=31|4 ssthresh=2 incr=5630
接收端中記錄的遠端視窗大小kcp.rmt_wnd為0 時, ikcp_flush 內會啟動探查等待階段(probe wait, ikcp.c:973)。 kcp.ts_probe會記錄一個初始為7000 毫秒(記錄在kcp->probe_wait中) 後的時間。
到達時間時，進行額外編碼一個類型為IKCP_CMD_WASK 的包發送給接收端(ikcp.c:994) 以請求遠端發回一個IKCP_CMD_WINS 類型的包來更新kcp.rmt_wnd
若遠端視窗大小一直為0, 每次kcp->probe_wait增加目前值的一半，然後更新等待時間，最大等待時間為120000 毫秒(120秒)。
遠端視窗大小不為0 時清空上述探測狀態。
在這個例子中，並沒有等到初始的7秒後才恢復記錄的遠端視窗大小。因為在接收端的ikcp_recv 讀出資料的操作中，當kcp.rcv_queue佇列的長度在讀取資料之前大於等於接收視窗kcp.rcv_wnd時(讀取視窗已滿)，讀取結束會設定一個標記位(ikcp .c:431) 並在下次ikcp_flush 時傳送IKCP_CMD_WINS 類型的套件(ikcp.c:1005)以通知發送端更新最新的遠端視窗大小。
避免這個問題，需要及時在接收端讀出數據，僅僅如此還是會因為遠端視窗變小導致發送端的發送視窗變小，導致額外的延遲。同時也需要增大接收端的接收視窗。
嘗試修改RECV_TIME的值為一個比較大的值時(例如300 秒)，然後觀察IKCP_CMD_WASK 套件的傳送。
在kcp.snd_buf佇列說明中已經描述過，在呼叫ikcp_flush 時會遍歷所有佇列中的包, 若包不為首次發送。那麼會檢查包是否被跨越確認指定的次數，或檢查是否到達超時時間。
往返時間和超時計算相關欄位有:
kcp.rx_rttval : 平滑網路抖動時間kcp.rx_srtt : 平滑往返時間kcp.rx_rto (Receive Retransmission Timeout) : 重傳逾時時間, 初始值200kcp.rx_minrto : 最小重傳逾時時間，初始值100kcp.xmit : 全域重傳次數計數seg.resendts : 重傳時間戳seg.rto : 重傳逾時時間seg.xmit : 重傳計次在討論包如何計算超時之前，先看看往返時間和超時的相關欄位是如何計算的:
往返時間記錄:每處理一個ACK 確認包時，確認包會攜帶序號以及該序號在發送端被發送的時間( seg.sn / seg.ts )，合法時執行往返時間更新流程。
rtt 的值為單一套件的往返時間，即rtt= kcp.current - seg.ts 。
若平滑往返時間kcp.rx_srtt為0 則表示執行初始化: kcp.rx_srtt直接記錄為rtt, kcp.rx_rttval記錄為rtt 的一半。
非初始化流程時，則計算一個delta 值，它代表了此次rtt 與記錄的kcp.rx_srtt的波動值(ikcp.c:550):
delta = abs(rtt - rx_srtt)
新的kcp.rx_rttval透過舊的kcp.rx_rttval和delta 的加權值來更新:
rx_rttval = (3 * rx_rttval + delta) / 4
新的kcp.rx_srtt透過舊的kcp.rx_srtt和rtt 的加權值來更新, 且不能小於1:
rx_srtt = (7 * rx_srtt + rtt) / 8
rx_srtt = max(1, rx_srtt)
新的rx_rto為平滑往返時間kcp.rx_srtt加上時鐘週期kcp.interval與4 倍rx_rttval的最小值來更新, 且範圍限制為[ kcp.rx_minrto , 60000]:
rto = rx_srtt + max(interval, 4 * rttval)
rx_rto = min(max(`kcp.rx_minrto`, rto), 60000)
理想的情況下, 當網路僅有固定的延遲而無抖動時， kcp.rx_rttval的值就會趨近於0, kcp.rx_rto的值就為平滑往返時間和時脈週期來決定。
平滑往返時間計算示意圖:
首次發包計時(ikcp.c:1052):
seg.rto會記錄kcp.rx_rto狀態，且封包首次逾時時間為seg.rto + rtomin 毫秒後。
rtomin 由kcp.rx_rto計算得出，如果開啟了nodelay 模式。 rtomin 為0，否則為kcp.rx_rto / 8。
未啟用nodelay 的超時時間:
resendts = current + rx_rto + rx_rto / 8
啟用nodelay 的超時時間:
resendts = current + rx_rto
超時重傳(ikcp.c:1058):
內部時間到達資料包的逾時時間seg.resendts時，重傳此序號的包。
未啟用nodelay 模式下， seg.rto的增量為max( seg.rto , kcp.rx_rto ) (翻倍成長):
rto += max(rto, rx_rto)
啟用nodelay 且nodelay 為1 時每次增加seg.rto的一半(1.5倍增長):
rto += rto / 2
啟用nodelay 且nodelay 為2 時每次增加kcp.rx_rto的一半(1.5倍增長):
rto += rx_rto / 2
新的超時時間為seg.rto毫秒後:
resendts = current + rx_rto
跨越重傳(ikcp.c:1072):
當封包跨越指定次數後觸發跨越重傳，跨越計次僅在ikcp_input 中累積一次(ikcp:872)，合併的確認包不會疊加。
跨越重傳時不更新seg.rto ，直接重新計算下次逾時重送時間:
resendts = current + rto
觀察預設超時
僅發送一個包，並且對其丟包四次，觀察其超時重傳時間。
對於預設的配置， kcp.rx_rto初始值為200 毫秒, 首次超時時間在225 毫秒，由於時脈精度的問題，在300 毫秒才進行超時重傳，此後每次的超時重傳時間翻倍。
#define SEND_STEP 1
#define K1_DROP_SN 0,0,0,0
t=0 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=300 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=700 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=1500 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=3100 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
觀察基於包自身RTO 的1.5倍增長
#define KCP_NODELAY 1, 100, 0, 0
#define SEND_STEP 1
#define K1_DROP_SN 0,0,0,0
t=0 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=200 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=500 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=1000 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=1700 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
觀察基於RTO 的1.5倍增長
#define KCP_NODELAY 2, 100, 0, 0
#define SEND_STEP 1
#define K1_DROP_SN 0,0,0,0
t=0 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=200 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=500 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=900 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
...
t=1400 n=1 una=0 nxt=1 cwnd=1|1 ssthresh=2 incr=1376
觀察跨越重傳
合併處理的確認包不會觸發跨越重傳, 這裡丟棄了包[sn=0]包[sn=1] [sn=2]的確認被合併處理，導致僅跨越一次。最終還是透過超時重傳。
#define KCP_NODELAY 0, 100, 2, 1
#define SEND_DATA_SIZE (KCP_MSS*3)
#define SEND_STEP 1
#define K1_DROP_SN 0
t=0 n=3 una=0 nxt=3 cwnd=32|1 ssthresh=2 incr=1376
t=100 n=0 una=0 nxt=3 cwnd=32|1 ssthresh=2 incr=1376
t=200 n=0 una=0 nxt=3 cwnd=32|1 ssthresh=2 incr=1376
t=300 n=1 una=0 nxt=3 cwnd=32|1 ssthresh=16 incr=1376
當分兩步驟發送出資料包時，第二組包執行ikcp_input 確認時讓[sn=0]累計到跨越了兩次，將在下一次ikcp_flush 時進行跨越重傳。
#define KCP_NODELAY 0, 100, 2, 1
#define SEND_DATA_SIZE (KCP_MSS*2)
#define SEND_STEP 2
#define K1_DROP_SN 0
t=0 n=2 una=0 nxt=2 cwnd=32|1 ssthresh=2 incr=1376
t=100 n=2 una=0 nxt=4 cwnd=32|1 ssthresh=2 incr=1376
t=200 n=1 una=0 nxt=4 cwnd=32|4 ssthresh=2 incr=5504
t=300 n=0 una=4 nxt=4 cwnd=32|4 ssthresh=2 incr=5934
文章以知識共享署名-非商業性使用-禁止演繹4.0 國際授權協議授權。
專案中程式碼使用MIT 協定開源。
關於圖片字體: Noto Sans SC
