UDT拥塞控制算法
導語
我們知道，TCP是通過AIMD算法來控制發送速度的．UDT使用類似的算法來調整數據包的發送周期
SND：
UDT發送周期，即每個數據包之間的間隔時間，初始值為０．
UDT每隔10毫秒都會調整它的發送速度，當收到ACK消息時，會提升發送速度，而當收到NAK（UDT數據包ACK的一種格式，表示不會對某個數據包進行ACK）時則減少發送速度．
另一種情況則是發生了超時，此時按情況調整，可以不減少。
- 注意包發送周期與包間時間是不一樣的．發送周期＝（發送花費的時間＋包間時間）
CWND：
UDT的滑動窗口，表示正在傳輸中的數據包，其初始大小為２，會根據ACK返回的信息更新其窗口大小值，需要注意的是要避免大小為0的情況出現（永遠發送不出數據包，也不會收到ACK），CWND可以跟接收方的緩存大小保持一致。
SYN：
UDT調整發送速率的固定周期，一般為１０ｍｓ。
UDT擁塞控制包含兩個階段，慢啟動階段和常規發送階段，每個連接建立之初處于慢啟動階段，當發生丟包或者滑動窗口CWND已滿時，進入常規發送階段．并且UDT中所有的數據包應當具有相同的大小。
對包（packet pair）：
發送方會連續發送兩個相同大小的數據包，接收方接收到時，會根據包間隔來計算出鏈路帶寬。
在發送端，UDT每發送１６個數據包就會發送一次對包，即第１６，１７號數據包成為一個對包，由于在只有１６號數據包，沒有１７號數據包時（或１７號包很晚才發），接收方計算間隔時間會出現非常大的值，此時鏈路帶寬會出現比較大的波動，所以UDT采用中值過濾法來避免這種情況。
對包窗口：
一個大小為N的循環鏈表，接收方維護了最近N個對包的對包間隔窗口，N可以是任意數值，越大需要的內存和ＣＰＵ消耗越高，在UDT中N=64，每次都會使用最新的間隔時間來替換掉最老的間隔時間，接收方使用中值過濾法來去除噪音，UDT計算出對包窗口中的中值，所有大于中值8倍，或者小于中值1/8的數據都會被忽略掉，然后再計算余下有效的間隔時間的平均值，帶寬就通過平均值來計算出來
B = 包大小 / 平均間隔時間對包窗口內的間隔時間，全部初始化設置為1秒（安全，考慮低帶寬的情況），接收方對鏈路大小進行評估后，將評估值ｂ通過ACK返回給發送方。
發送方接收到新的評估值ｂ后，使用如下公式更新已有帶寬值B（能處理10到1/10倍的錯誤數據）：
RTT：
往返時延，UDT采用一種叫做ACK子序列的方式來計算RTT，接收方記錄下發送的ACK時間和序號，然后等發送方返回ACK2（ACK的ACK）時，根據ACK2中攜帶的ACK序號，計算ACK2的到達時間和ACK的發送時間，即可得出RTT．計算公式如下，RTT表示已有值，rtt表示新計算出來的值
RTT = RTT * 0.875 + rtt * 0.125 RTTVar = RTTVar * 0.875 + abs(RTT - rtt)) * 0.125RTT通過ACK返回給發送方，RTTVar保存在本地，發送方收到新的RTT值時也通過上述公式更新其RTT值，RTTVar表示RTT的差值，用于計算RTO。
RTO：
重傳超時，UDT中最小值為100ms
RTO = RTT + 4 * RTTVar- 注意幾種情況：
- 如果接收方收到數據包就立即ACK，那么RTT可以在發送方通過 ACK到達時間 - 數據包發送時間 計算出來，此時不需要 ACK2
- 如果接收方只在每個SYN時間內ACK，那么 RTO = RTT + 4 * RTTVar + SYN
- UDT中是用ExpCount來表示連續超時次數，此時 RTO = ExpCount * ( RTT + 4 * RTTVar ) + SYN
AS包接收速率：
接收方記錄了最近Ｎ個數據包之間的間隔(我們叫它接收時間窗口，大小為Ｎ)，跟對包技術不同的是，對包只記錄第16，17個數據包之間的時間間隔，包接收速率AS計算公式如下
AS = 1 / 平均間隔時間在計算平均間隔時間時同樣需要采用中值過濾法來過濾噪聲，去除大于中值8倍和小于中值1／8的數據，然后計算平均值。
ACK 事件：
負責修改AS，SND，和CWND．
之前說到，擁塞控制算法有兩個階段，慢啟動和常規階段．在慢啟動階段中，SND初始化為0，CWND初始化為2，當每次ACK到達時設置為已經發送出的數據包總數，當收到NAK包，或者已發送的數據包總量達到CWND最大值時退出慢啟動階段。在慢啟動的末期，SND包發送間隔設置為 1 / 包接收速率
之后進入常規階段，常規階段會調整通過調整 inc 這個參數來調整SND，增量 inc 通過下面公式算出
if (B <= C) inc = 1/MSS; else inc = max(10^(ceil(log10((B-C)*MSS*8))) * Beta/MSS, 1/MSS);B：鏈路帶寬，C：當前發送速率，即C = 1 / SND = AS，MSS：MSS = MTU - UDP/UDT頭大小，通常為1400，Beta：常量 0.0000015
B和C的單位都是 包數量 / 每秒，如果是以 字節 / 每秒為單位，那么可以去除MSS，算出增量 inc 后，SND和CWND通過下面公式更新：
在常規階段，每個SYN周期內，SND只能被更新1次。
NAK事件：
在此我們要知道一個擁塞周期的概念，擁塞周期就是在收到的NAK中數據包序號比已發出的最大數據包序號LastDecSeq還要大時開始，持續到下一個擁塞周期開始時結束。舉例：
LastDecSeq=0 NAK NAK LastDecSeq=100 NAK |----------------60---------80---------------100------------140------->在一開始時 LastDecSeq = 0， 當收到NAK(60)時，判斷有NAK發生，進入擁塞周期，將LastDecSeq=100，然后進行降速處理
在收到NAK(80)時，查看LastDecSeq ，發現LastDecSeq比當前NAK序號大，說明還在同一個擁塞周期內，NAK(60)已經進行過降速處理，此時仍降速，幅度調小
發送方持續發送數據包，當收到NAK(140)時，發現NAK序號比LastDecSeq大，進入下一個擁塞周期，進行降速處理，幅度恢復正常
降速算法：
降速算法中用到4個參數，參數名以及他們的初始值分別如下：
AvgNAKNum = 1 ： 擁塞周期內收到的NAK數量的平均值 NAKCount = 1 ：當前擁塞周期內收到的NAK數量 DecCount = 0 ：發送速率在當前擁塞周期內已經被降速的次數 LastDecSeq = 初始化序列號-1 If this NAK starts a new congestion period{increase SND = SND * 1.125;Update AvgNAKNum;Reset NAKCount to 1;Compute DecRandom to a random (uniform distribution) number between 1 and AvgNAKNum;Reset DecCount to 1;Reset Update LastDecSeq;Stop.}If (DecCount <= 5) and (NAKCount == DecCount * DecRandom){Update SND period: SND = SND * 1.125;Increase DecCount by 1;}Update LastDecSeq and NAKCount.DecRandom是一個位于1 和 周期內平均NAK數量 AvgNAKNum 之間的隨機數，比如DecRandom=2，UDT就會在第1，2，4，6個NAK時進行降速，每次降速1 / 8， 但是因為每個周期內發送速率降速不能超過1 / 2 ，否則就變成AIMD了，所以在收到第6個NAK時就開始不進行降速了。
重傳：
RTO是一個定時器，只會被ACK和NAK重置，RTO事件會觸發重傳和降速，當RTO次數超過一定閾值時，就可以認為鏈接已經斷開了。.
GIT ：[https://github.com/ktlifeng/udt-java] (https://github.com/ktlifeng/udt-java)
總結
- 上一篇： 2019年软件评测师考试大纲
- 下一篇： redis通过hscan导入大hash