UDT

基於UDP的數據傳輸協定(UDP-based Data Transfer Protocol,簡稱UDT)是一種網際網路數據傳輸協定。UDT的主要目的是支持高速廣域網上的海量數據傳輸,而網際網路上的標準數據傳輸協定TCP在高頻寬長距離網路上性能很差。 顧名思義,UDT建於UDP之上,並引入新的擁塞控制和數據可靠性控制機制。UDT是面向連線的雙向的套用層協定。它同時支持可靠的數據流傳輸和部分可靠的數據報傳輸。 由於UDT完全在UDP上實現,它也可以套用在除了高速數據傳輸之外的其它套用領域,例如點到點技術(P2P),防火牆穿透,多媒體數據傳輸等等。

介紹

隨著網路頻寬時延積(BDP:the product of a data link's capacity (in bits per second) and its end-to-end delay)的增加,通常的TCP協定開始變的低效。這是因為它的AIMD(additive increase multiplicative decrease)算法完全減少了TCP擁塞視窗,但不能快速的恢復可用頻寬。理論上的流量分析表明TCP在BDP增加到很高的時候比較容易受包損失攻擊。

另外,繼承自TCP擁塞控制的不公平的RTT也成為在分散式數據密集程式中的嚴重問題。擁有不同RTT的並發TCP流將不公平地分享頻寬。儘管在小的BDP網路中使用通常的TCP實現來相對平等的共享頻寬,但在擁有大量BDP的網路中,通常的基於TCP的程式就必須承受嚴重的不公平的問題。這個RTT基於的算法嚴重的限制了其在廣域網分散式計算的效率,例如:internet上的格線計算。

一直到今天,對標準的TCP的提高一直都不能在高BDP環境中效率和公平性方面達到滿意的程度(特別是基於RTT的問題)。例如:TCP的修改,RFC1423(高性能擴展),RFC2018(SACK)、RFC2582(New Reno)、RFC2883(D-SACK)、和RFC2988(RTO計算)都或多或少的提高了點效率,但最根本的AIMD算法沒有解決。HS TCP(RFC 3649)通過根本上改變TCP擁塞控制算法來在高BDP網路中獲得高頻寬利用率,但公平性問題仍然存在。

考慮到上面的背景,需要一種在高BDP網路支持高性能數據傳輸的傳輸協定。我們推薦一個套用程式級別的傳輸協定,叫UDT或基於UDP的數據傳輸協定並有用擁塞控制算法。

本文描述兩個正交的部分,UDP協定和UDT擁塞控制算法。一個套用層級別的協定,位於UDP之上,使用其他的擁塞算法,然而這些本文中描述的算法也能夠在其他協定中實現,例如:TCP。

一個協定的參考實現叫[UDT];周詳的擁塞控制算法的性能分析在[GHG04]中能夠找到。

2. 設計目標

UDT主要用在小數量的bulk源共享富裕頻寬的情況下,最典型的例子就是建立在光纖廣域網上的格線計算,一些研究所在這樣的網路上運行他們的分散式的數據密集程式,例如,遠程訪問儀器、分散式數據挖掘和高解析度的多媒體流。

UDT的主要目標是效率、公平、穩定。單個的或少量的UDT流應該利用任何高速連線提供的可用頻寬,即使頻寬變化的很劇烈。同時,任何並發的流必須公平地共享頻寬,不依賴於不同的頻寬瓶頸、起始時間、RTT。穩定性需要包傳送速率應該一直會聚可用頻寬很快,並且必須避免擁塞碰撞。

UDT並不是在瓶頸頻寬相對較小的和大量多元短文檔流的情況下用來取代TCP的。

UDT主要作為TCP的朋友,和TCP並存,UDT分配的頻寬不應該超過根據MAX-MIN規則的最大最小公平共享原則。(備註,最大最小規則允許UDT在高BDP連線下分配TCP不能使用的可用頻寬)。

3.1. 概述

UDT是雙工的,每個UDT實體有兩個部分:傳送和接收。傳送者根據流量控制和速率控制來傳送(和重傳)套用程式數據。接收者接收數據包和控制包,並根據接收到的包傳送控制包。傳送和接收程式共享同一個UDP連線埠來傳送和接收。

接收者也負責觸發和處理任何的控制事件,包括擁塞控制和可靠性控制和他們的相對機制,例如RTT估計、頻寬估計、應答和重傳。

UDT總是試著將套用層數據打包成固定的大小,除非數據不夠這么大。和TCP相似的是,這個固定的包大小叫做MSS(最大包大小)。由於期望UDT用來傳輸大塊數據流,我們假定只有很小的一部分不規則的大小的包在UDT session中。MSS能夠通過套用程式來安裝,MTU是其最優值(包括任何包頭)。

UDT擁塞控制算法將速率控制和視窗(流量控制)合併起來,前者調整包的傳送周期,後者限制最大的未被應答的包。在速率控制中使用的參數通過頻寬估計技術來更新,他繼承來自基於接收的包方法。同時,速率控制周期是估計RTT的常量,流控制參數依賴於對方的數據到達速度,另外接收端釋放的緩衝區的大小。

3.2. 包結構

UDT有兩種包:數據包和控制包。他們通過包頭的第一位來區分(標誌位)。假如是0,表示是數據包,1表示是控制包。

3.2.1. 數據包

數據包結構如下顯示:

0 1 3 4

0 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 1

0

包序號

套用數據

包序號是UDT數據包頭中唯一的內容。他是個無符號整數,使用標誌位後的31位,UDT使用包基礎的需要,例如,每個非重傳的包都增加序號1。序號在到達最大值2^31-1的時候覆蓋。緊跟在這些數據後面的是套用程式數據。

3.2.2. 控制包控制包結構如下:

0 1 3 4

0 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 1

1

類型

保留

ACK序號

控制信息欄位

有6種類型的控制包在UDT中,bit1-3表示這些信息。前32位在包頭中必須存在。控制信息欄位包括0(例如,他不存在)或多個32位無符號整數,這由包類型決定。

UDT使用應答子序號的方法。每個ACK/ACK2包有一個無符號的16位序號,他單獨於數據包需要。他使用位16-31。應答需要從0到(2^16-1)。位16-31在其他控制包中沒有定義。

類型

說明

控制信息

000

協定連線握手

1.32位 UDT版本

2.32位 內部順序號

3.32位 MSS(位元組)

4.32位 最大流量視窗大小(位元組)

001

保活

沒有

010

應答,位16-31是應答序號

1.32位包序號,先前接收到的包序號

2.32位,RTT(微秒)

3.32位,RTT 變數或RTTVar (微秒)

4.32位,流量視窗大小(包的數量)

5.32位,連線容量估計(每秒包的數量)

011

Negative應答(NAK)

丟失信息的32位整數數組,見3.9節

100

保留

這種類型的控制信息保留作為擁塞警告使用,從接收到傳送端。一個擁塞警告能被ECN或包延遲增加趨勢的度量方法觸發。

101

關閉

110

應答一個應答(ACK2)

16-31位,應答序號。

111

4-15的解釋

保留將來使用

注意,對於數據和控制包來說,能夠從UDP協定頭中得到實際的包大小。包大小信息能被用來得到有效的數據負載和NAK包中的控制信息欄位大小。

3.3. 定時器

UDT在接收端使用4個定時器來觸發不同的周期事件,包括速率控制、應答、丟失報告(negative應答)和重傳/連線維護。

UDT中的定時器使用系統時間作為源。UDT接收端主動查詢系統時間來檢查一個定時器是否過期。對於某個定時器T來說,其擁有周期TP,將定變數t用來記錄最近T被配置或復位的時間。假如T在系統時間t0(t= t0)被復位,那么任何t1(t1-t>=TP)是T過期的條件。

四個定時器是:RC定時器、ACK定時器、NAK定時器、EXP定時器。他們的周期分別是:RCTP、ATP、NTP、ETP。

RC定時器用來觸發周期性的速率控制。ACK定時器用來觸發周期性的有選擇的應答(應答包)。RCTP和ATP是常量值,值為:RCTP=ATP=0.01秒。

NAK被用來觸發negative應答(NAK包)。重傳定時器被用來觸發一個數據包的重傳和維護連線狀態。他們周期依賴於對於RTT的估計。ETP值也依賴於連續EXP時間溢出的次數。推薦的RTT初始值是0.1秒,而NTP和ETP的初始值是:NTP=3*RTT,ETP=3*RTT+ATP。

在每次bounded UDP接收操作(假如收到一個UDP包,一些額外的必須的數據處理時間)時查詢系統時間來檢查四個定時器是否已過期。推薦的周期粒度是微秒。UDP接收時間溢出值是實現的一個選擇,這依賴於循環查詢的負擔和事件周期精確度之間的權衡。

速率控制事件更新包傳送周期,UDT傳送端使用STP來安排數據包的傳送。假定一個在時間t0被傳送,那么下一次包傳送時間是(t0+ STP)。換句話說,假如前面的包傳送花費了t’時間,傳送端將等待(STP-t’)來傳送下一個數據包(假如STP-t’ ,就無需等待了)。這個等待間隔需要一個高精確度的實現,推薦使用CPU時鐘周期粒度。

3.4. 傳送端算法

3.4.1. 數據結構和變數A. SND PKT歷史視窗:一個循環數組記錄每個數據包的開始時間

B. 傳送端丟失鍊表:傳送段丟失列表是個連線鍊表,用來存儲被接收方NAK包中返回的丟失包序號。這些數字以增加的順序存儲。

3.4.2. 數據傳送算法A. 假如傳送端的丟失鍊表是非空的,重傳第一個在list中的包,並刪除該成員,到5。

B. 等待有套用程式數據需要傳送

C. 假如未應答的包數量超過了兩量視窗的大小,轉到1。假如不是包裝一個新的包並傳送他。

D.假如當前包的序號是16n,n是個整數,轉第2步。

E. 在SND PKT歷史視窗中記錄包的傳送時間

F. 假如這是自上次傳送速率降低之後的第一個包,等外SYN時間。

G.等外(STP – t)時間,t是第1到第4步之間的總時間,然後轉到1。

3.5. 接收端算法

3.5.1. 數據結構和變數A. 接收端丟失鍊表:是個duple連線鍊表,元素的值包括:丟失數據包的序號、最近丟失包的反饋時間和包已被反饋的次數。值以包序號增序的方式存儲。

B. 應答歷史視窗:每個傳送ACK的和時間一個循環數組;由於其循環的特性,意味著假如數組中沒有更多空間的時候新的值將覆蓋老的值。

C. RCV PKT歷史視窗:一個用來記錄每個包到達時間的循環數組。

D.對包視窗:一個用來記錄每個探測包對之間的時間間隔。

E. LRSN:一個用來記錄最大接收數據包需要的變數。LRSN被初始化為初始序號減1。

3.5.2. 數據接收算法A. 查詢系統時間來檢查RC、ACK、NAK、或EXP定時器是否過期。假如任一定時器過期,處理事件(本節下面介紹)並復位過期的定時器。

B. 啟動一個時間bounded UDP接收。假如每個包到,轉1。

C. 配置exp-count為1,並更新ETP為:ETP=RTT+4*RTTVar + ATP。

D.假如任何的傳送數據包已被應答,復位EXP時間變數。

E. 檢查包頭的標誌位。假如是個控制包,根據類型處理他,然後轉1。

F. 假如當前數據包的需要是16n+1,n是個整數,記錄當前包和上個在對包視窗中數據包的時間間隔。

G.在PKT歷史視窗中記錄包到達時間

H. 假如當前數據包的序號大於LRSN+1,將任何在(但不包括)這兩個值之間的序號放入接收丟失鍊表,並在一個NAK包中將這些序號傳送給傳送端。假如序號小於LRSN,從接收丟失鍊表中刪除他。

I. 更新LRSN,轉1。

3.5.3. RC定時器到通過速率控制算法來更新STP(見3.6節)。

過程如下:

A. 按照下面的原則查找接收端所接收到的任何包之前的序號:假如接收者丟失鍊表是空的,ACK號碼是LRSN+1,否則是在接收丟失佇列中的最小序號。

B. 假如應答號不大於曾被ACK2應答的最大應答號,或等於上次應答的應答號並且兩次應答之間的時間間隔小於RTT+4*RTTVar,停止(不傳送應答)。

C. 分配這個應答一個唯一增加的ACK序列號,推薦採用ACK序列號按步驟1增加,並且重疊在達到最大值之後。

D.根據下面的算法來計算包的抵達速度:使用PKT歷史視窗中的值計算最近16個包抵達間隔(AI)中值。在這16個值中,刪除那些大於AI*8或小於AI*8的包,假如最後剩餘8個值,計算他們的平均值(AI’),包抵達速度是1/AI’(每秒包的數量),否則是0。

E. 根據3.7節中的內容為每端(W)計算流量視窗。然後計算有效的流量視窗大小為:最大(W,可用接收方緩衝大小),2)。

F. 根據下面的算法來計算連線容量估計。假如流量控制快啟動階段(3.7)一直繼續,返回0,否則計算最近16個對包間隔(PI),這些值在對包視窗中,那么連線容量就是1/PI(每秒包的數量)。

G.打包應答序列號,應答號,RTT,RTT 變數,有效的流量視窗大小並估計連線,將他們放入ACK包中,然後傳送出去。

H. 記錄ACK序列號,應答號和這個應答的開始時間,並放入歷史視窗中。

3.5.4. 處理NAK定時器到時Ø 查找接受方的丟失鍊表,找到任何上次反饋時間是(k*(RTT+4*RTTVar ) )前的包,k當前這個包的反饋次數加1,假如沒有反饋丟失,停止。

Ø 壓縮第一步中得到的序號(見3.9),然後在一個NAK包中傳送他們到傳送方。

Ø 假如不是停止流量控制快啟動階段。

3.5.5. 處理EXP定時器A. 假如傳送端的丟失鍊表不是空的,停止

B. 將任何未應答的包放到傳送端的丟失鍊表中

C. 假如(exp-count>16)並且自上次從對方接收到一個包以來的總時間超過3秒,或這個時間已超過3分鐘了,這被認為是連線已斷開,關閉UDT連線。

D.假如沒有數據,也就沒有應答,傳送一個保活包給對端,否則將任何未應答包的序號放入傳送丟失列表中。

E. 更新exp-count為:exp-count= exp-count+1

F. 更新ETP為:ETP=exp-count*(RTT+4*RTTVar)+ATP。

3.5.6. 收到應答包A. 更新最大的應答序號

B. 更新RTT和RTTVar為:RTT = rtt, RTTVar = rv;rtt和rv是ACK包中的RTT和RTTVar值。

C. 更新NTP和ETP為:NTP=RTT+4*RTTVar;ETP=exp-count*(RTT+4*RTTVar)+ATP。

D. 更新連線容量估計:B=(B*7+b)/8,b是ACK包帶的值。

E. 更新流量視窗大小為ACK中的值。

F. 傳送ACK2包,並配置和ACK序號相同的應答號到對端

G. 復位EXP定時器

3.5.7. 當收到NAK包的時候A. 將任何NAK包中帶的序號放入傳送方的丟失列表中

B. 通過速率控制來更新STP(見3.6)

C. 復位EXP定時器

3.5.8. 當收到ACK2包Ø 在ACK歷史視窗中根據接收到的ACK2序列號查找行營的ACK包。

Ø 更新曾被應答的最大應答號

Ø 根據ACK2的到達時間和ACK離開時間計算新的rtt值,並且更新RTT和RTTVar值為:

RTTVar = (RTTVar *3 +abs(rtt-RTT)/4

RTT = (RTT *7+rtt)/8

RTT和RTTVar的初始值是0.1秒和0.05秒。

Ø 更新NTP和ETP為:

NTP = RTT;

ETP = (exp-count +1)* RTT+ATP

3.5.9. 當收到保活包的時候什麼也不做

3.5.10. 當收到連線握手和關閉包的時候見3.8節

3.6. 速度控制算法

3.6.1. 速率控制快啟動STP被初始為最小的時間精度(1個CPU周期或1毫秒)。這是在快啟動階段,一般收到一個ACK包其攜帶的估計頻寬大於0這個階段就停止了。包的傳送周期被配置為1/W,W是ACK攜帶的流量視窗的大小。

快啟動階段僅僅在開始一個UDT連線的時候發生,且不會在UDT連線的以後再出現。在快啟動階段之後,下面的算法就要工作了。

3.6.2. 當RC定時器時間到1. 假如在上一個RCTP時間內,沒有收到一個ACK,停止

2. 計算在上個RCTP時間內的丟失率,計算方法是根據總共傳送的包和NAK反饋中總共丟失包的數量。假如丟失率大於0.1%,停止。

3. 下個RCTP時間內傳送包的增加數量如下計算:(inc)

If (B

Else inc = max (10^(ceil(log10((B-C)*MSS*8)))*Beta/MSS,1/MSS)

B是連線容量估計,C是當前的傳送速度。兩個都計算為每秒多少個包。MSS是以位元組計算的;Beta是值為0.0000015的常量。

4. 更新STP:STP=(STP*RCTP)/(STP*inc + RCTP)

5. 計算真正的數據傳送周期(rsp),從SND PKT歷史視窗中得到,假如(STP)配置STP為(0.5 * rsp)。

6. 假如(STP),配置STP為1.0。

3.6.3. 當收到NAK包時3.6.3.1. 數據結構和變數1. LSD:自上次速率降低後傳送的最大序號

2. NumNAK:自上次LSD更新以後的NAK數量

3. AvgNAK:當最大序號大於LSD時兩次事件之間的NAK移動的平均數。

4. DR:在1到AvgNAK之間的隨機平均數。

3.6.3.2. 算法1. 假如NAK中最大的丟失序列號大於LSD:

增加STP為:STP=STP*(1+1/8)

更新AvgNAK為:AvgNAK = (AvgNAK *7 +NumNAK)/8

更新DR

復位 NumNAK = 0

記錄LSD

2. 否則,增加NumNAK按照1個步驟增加;假如NumNAK % DR = 0;增加STP為:STP=STP*(1+1/8);記錄LSD。

3.7. 流量控制算法

流量控制視窗大小(W)初始值是16。

3.7.1. 當ACK定時器到的時候1. 流量控制快啟動:假如沒有NAK產生或W沒有到達或超過15個包,並且AS>0,流量視窗大小更新為應答包的總數量。

2. 否則,假如(AS>0),W更新為:(AS是包的到達速度)

W= ceil (W *0.875+AS* (RTT +ATP) *0.125)

3. 限制W到對方最大流量視窗大小。

3.8. 連線建立和關閉

一個UDT實體首先作為一個SERVER啟動,當一個客戶端需要連線的時候其傳送握手包。客戶端在從服務端接收到一個握手回響包或時間溢出之前,應該每隔一段時間傳送一個握手包(時間間隔由回響時間和系統overhead來權衡)。

握手包有如下信息:

1. UDT版本:這個值是兼容的目的。當前的版本是2

2. 初始序號:這是傳送這個UDT實體將來用於傳送數據包的起始序號。他必須是個在1到(2^31-1)之間的隨機值。另外,建議這個值在合理的時間歷史視窗中不應該重複。

3. MSS:數據包的大小(通過IP有效負載來度量)

4. 最大的流量視窗大小:這是接收到握手信息的UDT實體允許的最大流量視窗大小,視窗大小通常限制為接收端的數據結構大小。

伺服器接收到一個握手包之後,比較MSS值和他自己的值並配置他自己的值為較小的值。結果值也在握手回響中被傳送到客戶端,另外更有伺服器的版本信息,初始序列號,最大流量視窗大小。

版本欄位用來檢查兩端的兼容性。初始序列號和最大流量視窗大小用於初始化接收到這個握手包的UDT實體參數。

伺服器在第一步完成以後就準備傳送或接收數據。然而,只要從同一個客戶端接收任何握手包,其應該傳送回響包。

客戶端一旦得到伺服器的一個握手回響其就進入傳送和接收數據狀態。配置他自己的MSS為握手回響包中的值並初始化相應的參數為包中的值(序列號、最大流量視窗)。假如收到任何其他的握手信息,丟掉他。

假如其中的UDT實體要關閉,他將傳送一個關閉信息到對端;對方收到這個信息以後將自己關閉。這個關閉信息通過UDP傳輸,僅僅傳送一次,並不確保一定收到。假如訊息沒有收到,對方將根據時間溢出機制來關閉連線。

3.9. 丟失信息的壓縮方案

NAK包中攜帶的丟失信息是個32-bit整數的數組。假如數組的中數字是個正常的序號(第1位是0),這意味著這個序號的包丟失了,假如第1位是1,意味著從這個號碼開始(包括該號碼)到下一個數組中的元素(包括這個元素值)之間的包(他的第1位必須是0)都丟失。

例如,下面的NAK中攜帶的信息:

0x00000002, 0x80000006, 0x0000000B, 0x0000000E

上面的信息表明序號為:2,6,7,8,9,10,11,14的包都丟了。

4. 效率和公平性

UDT能夠充分利用當前有線網路的單獨於連線容量的可用頻寬 、RTT、後台共存流、給定的連線比特錯誤率。UDT在沒有數據包丟失的情況下從0bits/s到90%頻寬需要一個常量時間,這個時間是7.5秒。UDT並不適合無線網路。

UDT的確滿足單瓶頸網路拓撲的最大-最小公平性。在多個瓶頸情況下,根據最大最小原則他能確保較小瓶頸連線或至少一半的平等共享(it guarantees that flows over smaller bottleneck links obtain at least half of their fair share according to max-min rule)。RTT對公平性都一點影響。

當和大塊的TCP流共存的時候,TCP能占用比UDT更多的頻寬,除了三種情況:

1. 網路BDP很大,TCP不能利用他們的公平共享頻寬。這種情況下,UDT將占用TCP不能利用的頻寬。

2. 連線容量是如此的小,從而導致UDT的頻寬估計技術不能最有的工作;模擬顯示這個極限連線容量大約是100kb/s。

3. 在使用FIFO佇列作為網路路徑的網路中,假如佇列大小大於BDP,TCP的共享頻寬隨著佇列大小的增加而降低。然而,抵達UDT的共享頻寬是,佇列大小通常超過實際路由器/交換機提供的數量。

當短(timewise)類似web的TCP流和小的並發UDT流共存的時候,UDT在TCP流上的效果很小。

更多的分析在[GHG03]。

5. 安全考慮UDT並沒有使用特定的安全機制,相反,他依賴於套用程式提供的授權和底層提供的安全機制。

然而,由於UDP是無連線的,UDT實現應該檢查任何達到的包是否是預期的來源。這是從socket的API連線概念中繼承而來,其連線只是接收指定來源的數據。

6.UDT SOURCE CODE LINK

美國海軍水下爆破隊

UDT:Underwater Demolition team

美國海軍水下爆破隊 美國海軍水下爆破隊

UDT是美國海軍在二戰期間成立的精英部隊,他們曾參與韓戰和越南戰爭。它們的主要功能是偵察和摧毀敵方的阻礙兩棲登入的海灘防禦。他們還搜尋阿波羅載人航天計畫返回的太空人。

UDT的偵察的海灘和海域只是其中會干擾登入艇的岩石和暗礁。他們還用炸藥摧毀敵人設定的水下障礙物。作為美國海軍的游泳精英作戰隊員,他們受僱癱瘓保護敵人港口的電纜和網,在敵艦上安置炸彈,並為掃雷艇找到和標記地雷。他們還指揮河流偵查和外國的軍事訓練。

UDT的首創戰鬥游泳,閉路潛水,水下爆破,以及小型潛水艇(乾式和濕式潛水)操作。他們是現今美國海軍海豹突擊隊的先驅。

在1983年,經過額外的海豹突擊隊訓練,UDT的被重新指定為海豹突擊隊或游泳配送車輛小組(SDVTs),至今已調任海豹配送車輛隊伍。

通用變形工具

UDT:Rhinoceros(犀牛)軟體里的一類工具總稱,即Universal Deformation Tools,通用變形工具。主要有變形控制器、定位、流動、扭轉、縮放、彎曲、錐狀化/傾斜等。

UDT(user defined type) 用戶自定義類型(Java)

相關搜尋

熱門詞條

聯絡我們