Note
[toc]
1. TCP協(xié)議
傳輸控制協(xié)議（TCP，Transmission Control Protocol）是為了在不可靠的互聯(lián)網(wǎng)絡(luò)上提供可靠的端到端字節(jié)流而專門設(shè)計的一個傳輸協(xié)議捏萍。是傳輸層的協(xié)議壳坪。
TCP是為流量設(shè)計的（每秒內(nèi)可以傳輸多少KB的數(shù)據(jù)），講究的是充分利用帶寬。而 KCP是為流速設(shè)計的（單個數(shù)據(jù)包從一端發(fā)送到一端需要多少時間），以10%-20%帶寬浪費的代價換取了比 TCP快30%-40%的傳輸速度肢执。TCP信道是一條流速很慢，但每秒流量很大的大運河译红，而KCP是水流湍急的小激流。
超時重傳機制
TCP協(xié)議要求：發(fā)送端每發(fā)送一個報文段兴溜，就會啟動一個定時器等待確認(rèn)接收信息侦厚。接收端收到報文段后就要返回確認(rèn)信息ACK。在定時器超時前數(shù)據(jù)沒被確認(rèn)拙徽，TCP就認(rèn)為“丟包”刨沦。接著會重傳這個包，直到接收端確認(rèn)為止膘怕。這也是TCP可靠性的來源想诅。
RTO RTT
重傳超時時間（RTO，Retransmission TimeOut）岛心，TCP使用自適應(yīng)算法動態(tài)調(diào)整RTO的值来破。
往返時延 （RTT，Round Trip Time）也就是數(shù)據(jù)包從發(fā)出去到收到對應(yīng) ACK 的時間忘古。RTT 是針對連接的徘禁，每一個連接都有各自獨立的 RTT。
TCP中對于RTO髓堪、RTT的控制算法有很多種送朱，但都比較極端，比如Karn/Partidge Algorithm的算法采用是若超時則直接將RTO翻倍干旁。如果還沒收到就再 * 2... 也有如Jacobson/ Karels算法驶沼，是一種加權(quán)平均的經(jīng)驗算法。但其中的參數(shù)確實有點神秘魔法含義争群，反正能用就行回怜。
快速重傳機制
發(fā)送端收到來自接收端的三個相同的ACK時就會觸發(fā)快速重傳，（其實就算報文沒丟失祭阀，也有可能因為報文到達(dá)的順序不一致導(dǎo)致ACK的重復(fù)發(fā)送鹉戚，而報文丟失必定會出現(xiàn)3個ACK鲜戒，分別來自N-1和后邊的兩個報文）。
普通的超時重傳太過笨重抹凳。丟失一個報文后就會重發(fā)之后的所有報文（為了確倍舨停可靠性而過分的慎重）。但快速重傳機制下赢底，發(fā)送端收到某個報文的三次ACK后就會立即重傳失都，而接收端會將之前收到的報文先緩存起來，然后在收到丟失的報文后幸冻，繼續(xù)正常工作粹庞。
延遲 ACK
接收端收到數(shù)據(jù)時要發(fā)送一個ACK（期待的下一個報文編號）表示確認(rèn)收到。但只發(fā)送確認(rèn)對帶寬有所浪費洽损，所以會延遲等待看是否有響應(yīng)數(shù)據(jù)需要發(fā)送庞溜，若有則附著其中發(fā)送回去。一般等待最多200ms左右碑定。這里的200ms指的是一個內(nèi)部的計時器流码，每隔200ms檢查有沒有ACK要發(fā)送。例如有一個數(shù)據(jù)段在185ms到達(dá)延刘，那么它最遲在200ms發(fā)送ACK漫试，而不是等待到385ms看沒有響應(yīng)數(shù)據(jù)再發(fā)送。（這對網(wǎng)絡(luò)延遲造成了更嚴(yán)重的影響）
ACK碘赖，UNA
ARQ響應(yīng)模型有兩種驾荣，即UNA（當(dāng)前未收到確認(rèn)信息的包編號，或理解成：此編號前所有包已收到普泡，如TCP）和ACK（該編號包已收到）播掷，光用UNA將導(dǎo)致全部重傳，光用ACK則丟失成本太高劫哼，二者取長補短會更好叮趴。
滑動窗口
一般來說，發(fā)送端的數(shù)據(jù)可以分為四類
-
Sent and Acknowledged：數(shù)據(jù)已發(fā)送权烧，且收到來自接收端的ACK眯亦。 -
Sent , But Not yet Acknowledged：數(shù)據(jù)已發(fā)送，但尚未收到來自接收端的ACK般码。 -
Not Sent, Recipient Ready to Receive：數(shù)據(jù)未發(fā)送妻率，且接收端已經(jīng)準(zhǔn)備好接收 -
Not Sent, Recipient Not Ready to Recieve: 數(shù)據(jù)未發(fā)送，且接收端也尚未準(zhǔn)備好接收板祝。
而所謂的滑動窗口宫静，就是指的一個動態(tài)的 發(fā)送/接收 隊列。如上圖，發(fā)送端的滑動窗口可以分為兩部分孤里，即發(fā)送窗口（已經(jīng)發(fā)送但未收到ACK）和可用窗口（接收端還能接收但發(fā)送端尚未發(fā)送）伏伯。
而接收端的滑動窗口也是類似的，其響應(yīng)的WIN值所表示的就是窗口大邪仆唷（剩余可以接收的大兴到痢），這樣發(fā)送端在收到后可以動態(tài)調(diào)整發(fā)送的數(shù)據(jù)大小虏等，甚至是暫停發(fā)送（讓接收端先把之前的數(shù)據(jù)消化掉）弄唧，以此達(dá)到流量控制，減少堵塞的目的霍衫。
2. KCP協(xié)議
KCP是一個純粹的ARQ協(xié)議候引，通過重傳機制實現(xiàn)UDP數(shù)據(jù)包的可靠傳輸，是一個在UDP之上SESSION之下的協(xié)議敦跌。以比 TCP 浪費 10%-20% 的帶寬的代價澄干，換取平均延遲降低 30%-40%，且最大延遲降低三倍的傳輸效果峰髓。是純算法實現(xiàn)傻寂，所以要自己定義下層數(shù)據(jù)包的收發(fā)方式。
KCP 提高流速
KCP啟動快速模式后RTO超時x1.5（實驗證明1.5這個值相對比較好）携兵，提高了傳輸速度。相較于TCP搂誉，若三次超時則變成RTO * 8徐紧。
KCP是選擇性重傳，只重傳真正丟失的數(shù)據(jù)包炭懊。KCP也有基本的超時重傳機制與快速重傳機制并级。KCP會直接重傳失序次數(shù)過多的報文，而非等待其超時侮腹。
假設(shè)發(fā)送方依次發(fā)送了 1, 2, 3, 4 號報文, 隨后收到 1, 3, 4 號 ACK. 收到 3 號 ACK 時, 我們知道 2 號 ACK 失序了一次, 收到 4 號 ACK 時, 我們知道 2 號失序了兩次. ACK 失序次數(shù)越多說明它丟包的概率越大嘲碧。
- KCP的ACK是否延遲發(fā)送是可以調(diào)節(jié)的。KCP中除了單獨的ACK包之外父阻，其他所有包都包含有UNA信息愈涩。
KCP 報文結(jié)構(gòu)
KCP中共有四種報文，分別是
- 數(shù)據(jù)報文
IKCP_CMD_PUSH - 確認(rèn)報文
IKCP_CMD_ACK - 窗口探測報文
IKCP_CMD_WASK - 窗口通知報文
IKCP_CMD_WINS
報文結(jié)構(gòu)如下：
0 4 5 6 8 (BYTE)
+---------------+---+---+-------+
| conv |cmd|frg| wnd |
+---------------+---+---+-------+ 8
| ts | sn |
+---------------+---------------+ 16
| una | len |
+---------------+---------------+ 24
| |
| DATA (optional) |
| |
+-------------------------------+
- cmd：域用來區(qū)分是具體哪種報文加矛。
- conv：用來表示連接標(biāo)識履婉。
- frg：其后報文數(shù)量。
- wnd：剩余接收窗口大小斟览。
- ts：時間戳毁腿。
- sn：報文編號
- una：尚未收到ACK的報文編號（小于una的都接收了）
- len：數(shù)據(jù)長度
- data：數(shù)據(jù)部分
利用ts計算出RTT（往返時間）從而判斷是否需要超時重傳。同時還有一個MSS（最大報文段大小）用來限制數(shù)據(jù)包的大小已烤，超過了就要切片成多個報文鸠窗。因此引入frg表示報文數(shù)量。
KCP 隊列與緩沖區(qū)
注意到struct IKCPCB里有四個struct IQUEUEHEAD胯究，是表示隊列稍计，也即發(fā)送隊列，接收隊列唐片，發(fā)送緩沖區(qū)丙猬，接收緩沖區(qū)，都是手動實現(xiàn)的雙向循環(huán)鏈表费韭。且用大量的宏定義實現(xiàn)了隊列的相關(guān)操作茧球。這些隊列有一個初始的頭結(jié)點Head（不存數(shù)據(jù)），隨后可在頭尾進行插入刪除等操作星持。
https://luyuhuang.tech/2020/12/09/kcp.html
KCP 發(fā)送 接收 重傳
KCP 的整個發(fā)送, 接收與重傳的流程大體如下:
- 調(diào)用 ikcp_send 發(fā)送數(shù)據(jù), 創(chuàng)建報文段實例, 加入 snd_queue 中.
- ikcp_update 會在合適的時刻調(diào)用 ikcp_flush.
- ikcp_flush 會做:
- 發(fā)送 ACK 列表中所有的 ACK;
- 檢查是否需要發(fā)送窗口探測和通知報文, 如果需要就發(fā)送相應(yīng)的報文;
- 根據(jù)發(fā)送窗口大小, 將適量的報文段從 snd_queue 移入到 snd_buf 中;
- 將 snd_buf 中滿足條件的報文段都發(fā)送出去. 這里的條件有:
- 新加入 snd_buf 中, 從未發(fā)送過的報文直接發(fā)送出去;
- 發(fā)送過的, 但是在 RTO 內(nèi)未收到 ACK 的報文, 需要重傳;
- 發(fā)送過的, 但是 ACK 失序若干次的報文, 需要執(zhí)行快速重傳.
- 根據(jù)丟包情況計算 ssthresh 和 cwnd.
- 這樣, 剛才調(diào)用 ikcp_send 傳入的數(shù)據(jù)就在 ikcp_flush 中被發(fā)送出去了.
- 報文到達(dá)對端.
- ikcp_input 會被調(diào)用, 解析收到的數(shù)據(jù):
- 所有的報文都有 una 字段, 根據(jù) una 將相應(yīng)的報文標(biāo)記為已送達(dá);
- 如果是 ACK 報文, 就將相應(yīng)的報文標(biāo)記為已送達(dá);
- 如果是數(shù)據(jù)報文, 就將它放入 rcv_buf, 然后將 rcv_buf 中順序正確的報文移入 rcv_queue; 接著將相關(guān)信息插入 ACK 列表, 在稍后的 ikcp_flush 調(diào)用中會發(fā)送相應(yīng)的 ACK;
- 如果是窗口探測報文, 就標(biāo)記 "需要發(fā)送窗口通知". 在稍后的 ikcp_flush 調(diào)用中會發(fā)送窗口通知報文;
- 包括窗口通知報文在內(nèi)的所有報文都有 wnd 字段, 據(jù)此更新 rmt_wnd;
- 根據(jù) ACK 失序情況決定快速重傳;
- 計算 cwnd.
- 調(diào)用 ikcp_recv 接收數(shù)據(jù), 從 rcv_queue 中讀取數(shù)據(jù).
KCP 擁塞控制
與TCP相同抢埋，KCP也有擁塞窗口、慢啟動督暂、快速恢復(fù)等擁塞控制措施揪垄。
開始時cwnd=1,（congestion window，擁塞窗口逻翁，即發(fā)送端的一個可滑動窗口）饥努。每經(jīng)過一個RTT時間后就翻倍，但也不會無限指數(shù)增長八回。超過閾值后就是線性增長酷愧，這個階段叫擁塞避免，這個閾值叫做慢啟動閾值（ssthresh缠诅，Slow Start Threshold）溶浴。整個過程就叫慢啟動。
隨著cwnd的增大管引，網(wǎng)絡(luò)最終被填滿士败，就會出現(xiàn)丟包。此時說明cwnd應(yīng)該減小褥伴，即丟包退讓谅将。KCP對此的處理是：如果發(fā)生超時重傳, 就進入慢啟動（將ssthresh置為cwnd的一半，然后cwnd重新從1開始慢啟動）; 如果發(fā)生快速重傳, 就進入快速恢復(fù)（將ssthresh置為cwnd的一半噩翠，cwnd設(shè)置比ssthresh略微大一點戏自，再以擁塞避免的方式線性增長）.
[圖片上傳失敗...(image-4153eb-1628154473200)]
KCP 源碼
KCP的代碼是比較精煉的，只有ikcp.c 和 ikcp.h 兩個文件伤锚。
其中 ikcp.h 提供了結(jié)構(gòu)體定義擅笔，隊列操作志衣，接口函數(shù)聲明等。ikcp.c 是對各函數(shù)方法的具體實現(xiàn)猛们。
ikcp_create創(chuàng)建一個KCP的實例念脯，將其中的各項成員初始化后返回該實例的指針。其中IUINT32 conv參數(shù)用于標(biāo)識該KCP連接弯淘。通信雙方必須協(xié)商相同的conv才可以交流绿店。該連接發(fā)出的每個報文段都會帶上conv，同理也只接受包含conv的報文段庐橙。
