UDT協(xié)議-基于UDP的可靠數(shù)據(jù)傳輸協(xié)議

1、1. 介紹隨著網(wǎng)絡(luò)帶寬時延產(chǎn)品(BDP)的增加，通常的TCP協(xié)議開始變的低效。這是因為它的AIMD（additive increase multiplicative decrease）算法徹底減少了TCP擁塞窗口，但不能快速的恢復(fù)可用帶寬。理論上的流量分析表明TCP在BDP增加到很高的時候比較容易受包損失攻擊。另外，繼承自TCP擁塞控制的不公平的RTT也成為在分布式數(shù)據(jù)密集程序中的嚴重問題。擁有不同RTT的并發(fā)TCP流將不公平地分享帶寬。盡管在小的BDP網(wǎng)絡(luò)中使用通常的TCP實現(xiàn)來相對平等的共享帶寬，但在擁有大量BDP的網(wǎng)絡(luò)中，通常的基于TCP的程序就必須承受嚴重的不公平的問題。這個RTT基于

2、的算法嚴重的限制了其在廣域網(wǎng)分布式計算的效率，例如：internet上的網(wǎng)格計算。一直到今天，對標準的TCP的提高一直都不能在高BDP環(huán)境中效率和公平性方面達到滿意的程度（特別是基于RTT的問題）。例如：TCP的修改，RFC1423（高性能擴展），RFC2018（SACK）、RFC2582（New Reno）、RFC2883（D-SACK）、和RFC2988（RTO計算）都或多或少的提高了點效率，但最根本的AIMD算法沒有解決。HS TCP（RFC 3649）通過根本上改變TCP擁塞控制算法來在高BDP網(wǎng)絡(luò)中獲得高帶寬利用率，但公平性問題仍然存在。考慮到上面的背景，需要一種在高BDP網(wǎng)絡(luò)支持高

3、性能數(shù)據(jù)傳輸?shù)膫鬏攨f(xié)議。我們推薦一個應(yīng)用程序級別的傳輸協(xié)議，叫UDT或基于UDP的數(shù)據(jù)傳輸協(xié)議并擁有用塞控制算法。本文描述兩個正交的部分，UDP協(xié)議和UDT擁塞控制算法。一個應(yīng)用層級別的協(xié)議，位于UDP之上，使用其他的擁塞算法，然而這些本文中描述的算法也可以在其他協(xié)議中實現(xiàn)，例如：TCP。一個協(xié)議的參考實現(xiàn)叫UDT；詳細的擁塞控制算法的性能分析在GHG04中可以找到。1 / 162. 設(shè)計目標UDT主要用在小數(shù)量的bulk源共享富裕帶寬的情況下，最典型的例子就是建立在光纖廣域網(wǎng)上的網(wǎng)格計算，一些研究所在這樣的網(wǎng)絡(luò)上運行他們的分布式的數(shù)據(jù)密集程序，例如，遠程訪問儀器、分布式數(shù)據(jù)挖掘和高分辨率的多

4、媒體流。UDT的主要目標是效率、公平、穩(wěn)定。單個的或少量的UDT流應(yīng)該利用所有高速連接提供的可用帶寬，即使帶寬變化的很劇烈。同時，所有并發(fā)的流必須公平地共享帶寬，不依賴于不同的帶寬瓶勁、起始時間、RTT。穩(wěn)定性要求包發(fā)送速率應(yīng)該一直會聚可用帶寬非?？欤⑶冶仨毐苊鈸砣鲎?。UDT并不是在瓶勁帶寬相對較小的和大量多元短文件流的情況下用來取代TCP的。UDT主要作為TCP的朋友，和TCP并存，UDT分配的帶寬不應(yīng)該超過根據(jù)MAX-MIN規(guī)則的最大最小公平共享原則。（備注，最大最小規(guī)則允許UDT在高BDP連接下分配TCP不能使用的可用帶寬）。我們3. 協(xié)議說明3.1. 概述UDT是雙工的，每個UDT

5、實體有兩個部分：發(fā)送和接收。發(fā)送者根據(jù)流量控制和速率控制來發(fā)送（和重傳）應(yīng)用程序數(shù)據(jù)。接收者接收數(shù)據(jù)包和控制包，并根據(jù)接收到的包發(fā)送控制包。發(fā)送和接收程序共享同一個UDP端口來發(fā)送和接收。接收者也負責(zé)觸發(fā)和處理所有的控制事件，包括擁塞控制和可靠性控制和他們的相對機制，例如RTT估計、帶寬估計、應(yīng)答和重傳。UDT總是試著將應(yīng)用層數(shù)據(jù)打包成固定的大小，除非數(shù)據(jù)不夠這么大。和TCP相似的是，這個固定的包大小叫做MSS（最大包大?。?。由于期望UDT用來傳輸大塊數(shù)據(jù)流，我們假定只有很小的一部分不規(guī)則的大小的包在UDT session中。MSS可以通過應(yīng)用程序來安裝，MTU是其最優(yōu)值（包括所有包頭）。UD

6、T擁塞控制算法將速率控制和窗口（流量控制）合并起來，前者調(diào)整包的發(fā)送周期，后者限制最大的位被應(yīng)答的包。在速率控制中使用的參數(shù)通過帶寬估計技術(shù)來更新，它繼承來自基于接收的包方法。同時，速率控制周期是估計RTT的常量，流控制參數(shù)依賴于對方的數(shù)據(jù)到達速度，另外接收端釋放的緩沖區(qū)的大小。3.2. 包結(jié)構(gòu)UDT有兩種包：數(shù)據(jù)包和控制包。他們通過包頭的第一位來區(qū)分（標志位）。如果是0，表示是數(shù)據(jù)包，1表示是控制包。3.2.1. 數(shù)據(jù)包數(shù)據(jù)包結(jié)構(gòu)如下顯示：0 1 3 40 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 10包序號應(yīng)用數(shù)

7、據(jù)包序號是UDT數(shù)據(jù)包頭中唯一的內(nèi)容。它是一個無符號整數(shù)，使用標志位后的31位，UDT使用包基礎(chǔ)的需要，例如，每個非重傳的包都增加序號1。序號在到達最大值231-1的時候覆蓋。緊跟在這些數(shù)據(jù)后面的是應(yīng)用程序數(shù)據(jù)。3.2.2. 控制包控制包結(jié)構(gòu)如下：0 1 3 40 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 11類型保留ACK序號控制信息字段有6種類型的控制包在UDT中，bit1-3表示這些信息。前32位在包頭中必須存在。控制信息字段包括0（例如，它不存在）或者多個32位無符號整數(shù)，這由包類型決定。UDT使用應(yīng)答子序號

8、的方法。每個ACK/ACK2包有一個無符號的16位序號，它獨立于數(shù)據(jù)包需要。它使用位16-31。應(yīng)答需要從0到（216-1）。位16-31在其他控制包中沒有定義。類型說明控制信息000協(xié)議連接握手132位 UDT版本232位 內(nèi)部順序號332位 MSS（字節(jié)）432位 最大流量窗口大?。ㄗ止?jié)）001?；顩]有010應(yīng)答，位16-31是應(yīng)答序號132位包序號，先前接收到的包序號232位，RTT（微秒）332位，RTT 變量或者RTTVar (微秒)432位，流量窗口大?。ò臄?shù)量）532位，連接容量估計（每秒包的數(shù)量）011Negative應(yīng)答（NAK）丟失信息的32位整數(shù)數(shù)組，見3.9節(jié)100保

9、留這種類型的控制信息保留作為擁塞警告使用，從接收到發(fā)送端。一個擁塞警告能被ECN或包延遲增加趨勢的度量方法觸發(fā)。101關(guān)閉110應(yīng)答一個應(yīng)答（ACK2）16-31位，應(yīng)答序號。1114-15的解釋保留將來使用注意，對于數(shù)據(jù)和控制包來說，可以從UDP協(xié)議頭中得到實際的包大小。包大小信息能被用來得到有效的數(shù)據(jù)負載和NAK包中的控制信息字段大小。3.3. 定時器UDT在接收端使用4個定時器來觸發(fā)不同的周期事件，包括速率控制、應(yīng)答、丟失報告（negative應(yīng)答）和重傳/連接維護。UDT中的定時器使用系統(tǒng)時間作為源。UDT接收端主動查詢系統(tǒng)時間來檢查一個定時器是否過期。對于某個定時器T來說，其擁有周期

10、TP，將定變量t用來記錄最近T被設(shè)置或復(fù)位的時間。如果T在系統(tǒng)時間t0（t= t0）被復(fù)位，那么任何t1（t1-t=TP）是T過期的條件。四個定時器是：RC定時器、ACK定時器、NAK定時器、EXP定時器。他們的周期分別是：RCTP、ATP、NTP、ETP。RC定時器用來觸發(fā)周期性的速率控制。ACK定時器用來觸發(fā)周期性的有選擇的應(yīng)答（應(yīng)答包）。RCTP和ATP是常量值，值為：RCTP=ATP=0.01秒。NAK被用來觸發(fā)negative應(yīng)答（NAK包）。重傳定時器被用來觸發(fā)一個數(shù)據(jù)包的重傳和維護連接狀態(tài)。他們周期依賴于對于RTT的估計。ETP值也依賴于連續(xù)EXP時間溢出的次數(shù)。推薦的RTT初始

11、值是0.1秒，而NTP和ETP的初始值是：NTP=3*RTT，ETP=3*RTT+ATP。在每次bounded UDP接收操作（如果收到一個UDP包，一些額外的必須的數(shù)據(jù)處理時間）時查詢系統(tǒng)時間來檢查四個定時器是否已經(jīng)過期。推薦的周期粒度是微秒。UDP接收時間溢出值是實現(xiàn)的一個選擇，這依賴于循環(huán)查詢的負擔(dān)和事件周期精確度之間的權(quán)衡。速率控制事件更新包發(fā)送周期，UDT發(fā)送端使用STP來安排數(shù)據(jù)包的發(fā)送。假定一個在時間t0被發(fā)送，那么下一次包發(fā)送時間是（t0+ STP）。換句話說，如果前面的包發(fā)送花費了t時間，發(fā)送端將等待（STP-t）來發(fā)送下一個數(shù)據(jù)包（如果STP-t 16)并且自上次從對方接收

12、到一個包以來的總時間超過3秒，或者這個時間已經(jīng)超過3分鐘了，這被認為是連接已經(jīng)斷開，關(guān)閉UDT連接。D如果沒有數(shù)據(jù)，也就沒有應(yīng)答，發(fā)送一個?；畎o對端，否則將所有未應(yīng)答包的序號放入發(fā)送丟失列表中。E 更新exp-count為：exp-count= exp-count+1F 更新ETP為：ETP=exp-count*（RTT+4*RTTVar）+ATP。3.5.6. 收到應(yīng)答包A 更新最大的應(yīng)答序號B 更新RTT和RTTVar為：RTT = rtt， RTTVar = rv；rtt和rv是ACK包中的RTT和RTTVar值。C 更新NTP和ETP為：NTP=RTT+4*RTTVar；ETP=ex

13、p-count*（RTT+4*RTTVar）+ATP。D 更新連接容量估計：B=（B*7+b）/8，b是ACK包帶的值。E 更新流量窗口大小為ACK中的值。F 發(fā)送ACK2包，并設(shè)置與ACK序號相同的應(yīng)答號到對端G 復(fù)位EXP定時器3.5.7. 當收到NAK包的時候A 將所有NAK包中帶的序號放入發(fā)送方的丟失列表中B 通過速率控制來更新STP（見3.6）C 復(fù)位EXP定時器3.5.8. 當收到ACK2包 在ACK歷史窗口中根據(jù)接收到的ACK2序列號查找行營的ACK包。 更新曾經(jīng)被應(yīng)答的最大應(yīng)答號 根據(jù)ACK2的到達時間和ACK離開時間計算新的rtt值，并且更新RTT和RTTVar值為：RTTV

14、ar = (RTTVar *3 +abs(rtt-RTT)/4RTT = (RTT *7+rtt)/8RTT和RTTVar的初始值是0.1秒和0.05秒。 更新NTP和ETP為：NTP = RTT；ETP = (exp-count +1)* RTT+ATP3.5.9. 當收到保活包的時候什么也不做3.5.10. 當收到連接握手和關(guān)閉包的時候見3.8節(jié)3.6. 速度控制算法3.6.1. 速率控制快啟動STP被初始為最小的時間精度（1個CPU周期或1毫秒）。這是在快啟動階段，一般收到一個ACK包其攜帶的估計帶寬大于0這個階段就停止了。包的發(fā)送周期被設(shè)置為1/W，W是ACK攜帶的流量窗口的大小?？靻?/p>

15、動階段僅僅在開始一個UDT連接的時候發(fā)生，且不會在UDT連接的以后再出現(xiàn)。在快啟動階段之后，下面的算法就要工作了。3.6.2. 當RC定時器時間到1 如果在上一個RCTP時間內(nèi)，沒有收到一個ACK，停止2 計算在上個RCTP時間內(nèi)的丟失率，計算方法是根據(jù)總共發(fā)送的包與NAK反饋中總共丟失包的數(shù)量。如果丟失率大于0.1%，停止。3 下個RCTP時間內(nèi)發(fā)送包的增加數(shù)量如下計算：(inc)If (B=C) inc = 1/MSSElse inc = max (10(ceil(log10(B-C)*MSS*8)*Beta/MSS,1/MSS)B是連接容量估計，C是當前的發(fā)送速度。兩個都計算為每秒多少個

16、包。MSS是以字節(jié)計算的；Beta是值為0.0000015的常量。4 更新STP：STP=（STP*RCTP）/（STP*inc + RCTP）5 計算真正的數(shù)據(jù)發(fā)送周期（rsp），從SND PKT歷史窗口中得到，如果（STP0.5 *rsp）設(shè)置STP為（0.5 * rsp）。6 如果（STP0，流量窗口大小更新為應(yīng)答包的總數(shù)量。2 否則，如果（AS0），W更新為：（AS是包的到達速度）W= ceil (W *0.875+AS* (RTT +ATP) *0.125)3 限制W到對方最大流量窗口大小。3.8. 連接建立和關(guān)閉一個UDT實體首先作為一個SERVER啟動，當一個客戶端需要連接的時候

17、其發(fā)送握手包?？蛻舳嗽趶姆?wù)端接收到一個握手響應(yīng)包或時間溢出之前，應(yīng)該每隔一段時間發(fā)送一個握手包（時間間隔由響應(yīng)時間和系統(tǒng)overhead來權(quán)衡）。握手包有如下信息：1 UDT版本：這個值是兼容的目的。當前的版本是22 初始序號：這是發(fā)送這個UDT實體將來用于發(fā)送數(shù)據(jù)包的起始序號。它必須是一個在1到（231-1）之間的隨機值。另外，建議這個值在合理的時間歷史窗口中不應(yīng)該重復(fù)。3 MSS：數(shù)據(jù)包的大?。ㄍㄟ^IP有效負載來度量）4 最大的流量窗口大?。哼@是接收到握手信息的UDT實體允許的最大流量窗口大小，窗口大小通常限制為接收端的數(shù)據(jù)結(jié)構(gòu)大小。服務(wù)器接收到一個握手包之后，比較MSS值和他自己的值并

18、設(shè)置它自己的值為較小的值。結(jié)果值也在握手響應(yīng)中被發(fā)送到客戶端，另外還有服務(wù)器的版本信息，初始序列號，最大流量窗口大小。版本字段用來檢查兩端的兼容性。初始序列號和最大流量窗口大小用于初始化接收到這個握手包的UDT實體參數(shù)。服務(wù)器在第一步完成以后就準備發(fā)送或接收數(shù)據(jù)。然而，只要從同一個客戶端接收任何握手包，其應(yīng)該發(fā)送響應(yīng)包。客戶端一旦得到服務(wù)器的一個握手響應(yīng)其就進入發(fā)送和接收數(shù)據(jù)狀態(tài)。設(shè)置它自己的MSS為握手響應(yīng)包中的值并初始化相應(yīng)的參數(shù)為包中的值（序列號、最大流量窗口）。如果收到任何其他的握手信息，丟掉它。如果其中的UDT實體要關(guān)閉，它將發(fā)送一個關(guān)閉信息到對端；對方收到這個信息以后將自己關(guān)閉。這

19、個關(guān)閉信息通過UDP傳輸，僅僅發(fā)送一次，并不保證一定收到。如果消息沒有收到，對方將根據(jù)時間溢出機制來關(guān)閉連接。3.9. 丟失信息的壓縮方案NAK包中攜帶的丟失信息是一個32-bit整數(shù)的數(shù)組。如果數(shù)組的中數(shù)字是一個正常的序號（第1位是0），這意味著這個序號的包丟失了，如果第1位是1，意味著從這個號碼開始（包括該號碼）到下一個數(shù)組中的元素（包括這個元素值）之間的包（它的第1位必須是0）都丟失。例如，下面的NAK中攜帶的信息：0x00000002, 0x80000006, 0x0000000B, 0x0000000E上面的信息表明序號為：2，6，7，8，9，10，11，14的包都丟了。4. 效率和公平性UDT能夠充分利用當前有線網(wǎng)絡(luò)的獨立于連接容量的可用帶寬 、RTT、后臺共存流、給定的連接比特錯誤率。UDT在沒有數(shù)據(jù)包丟失的情況下從0bits/s到90%帶寬需要一個常量時間，這個時間是7.5秒。UDT并不適合無線網(wǎng)絡(luò)。UDT的確滿足單瓶勁網(wǎng)絡(luò)拓撲的最大-最小公平性。在多個瓶勁情況下，根據(jù)最大