轉：http://blog.csdn.net/windcsn/archive/2006/01/04/570242.aspx

1.   介紹
隨著網絡帶寬時延產品(BDP)的增加，通常的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.   協議說明
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’ <0，就不需要等待了）。這個等待間隔需要一個高精確度的實現，推薦使用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<=C) inc = 1/MSS

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<0.5 *rsp）設置STP為（0.5 * rsp）。

6．  如果（STP<1.0），設置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
      http://sourceforge.net/projects/dataspace

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/windcsn/archive/2006/01/04/570242.aspx