Nagle算法

Nagle算法是以他的發明人John Nagle的名字命名的，它用於自動連線許多的小緩衝器訊息；這一過程（稱為nagling）通過減少必須傳送包的個數來增加網路軟體系統的效率。

基本介紹

• 中文名：Nagle算法
• 發明人：John Nagle
• 用於：自動連線許多的小緩衝器訊息
• 優點：減少擁塞控制

簡介

Nagle算法於1984年定義為福特航空和通信公司IP/TCP擁塞控制方法，這使福特經營的最早的專用TCP/IP網路減少擁塞控制，從那以後這一方法得到了廣泛套用。Nagle的文檔里定義了處理他所謂的小包問題的方法，這種問題指的是應用程式一次產生一位元組數據，這樣會導致網路由於太多的包而過載（一個常見的情況是傳送端的"糊塗視窗綜合症(Silly Window Syndrome)"）。從鍵盤輸入的一個字元，占用一個位元組，可能在傳輸上造成41位元組的包，其中包括1位元組的有用信息和40位元組的首部數據。這種情況轉變成了4000%的消耗，這樣的情況對於輕負載的網路來說還是可以接受的，但是重負載的福特網路就受不了了，它沒有必要在經過節點和網關的時候重發，導致包丟失和妨礙傳輸速度。吞吐量可能會妨礙甚至在一定程度上會導致連線失敗。Nagle的算法通常會在TCP程式里添加兩行代碼，在未確認數據傳送的時候讓傳送器把數據送到快取里。任何數據隨後繼續直到得到明顯的數據確認或者直到攢到了一定數量的數據了再發包。儘管Nagle的算法解決的問題只是局限於福特網路，然而同樣的問題也可能出現在ARPANet。這種方法在包括網際網路在內的整個網路里得到了推廣，成為了默認的執行方式，儘管在高互動環境下有些時候是不必要的，例如在客戶/伺服器情形下。在這種情況下，nagling可以通過使用TCP_NODELAY 套接字選項關閉。

MSDN:

A TCP/IP optimization called the Nagle Algorithm can also limit data transfer speed on a connection. The Nagle Algorithm is designed to reduce protocol overhead for applications that send small amounts of data, such as Telnet, which sends a single character at a time. Rather than immediately send a packet with lots of header and little data, the stack waits for more data from the application, or an acknowledgment, before proceeding.

算法

　　
TCP/IP協定中，無論傳送多少數據，總是要在數據前面加上協定頭，同時，對方接收到數據，也需要傳送ACK表示確認。為了儘可能的利用網路頻寬，TCP總是希望儘可能的傳送足夠大的數據。（一個連線會設定MSS參數，因此，TCP/IP希望每次都能夠以MSS尺寸的數據塊來傳送數據）。Nagle算法就是為了儘可能傳送大塊數據，避免網路中充斥著許多小數據塊。
Nagle算法的基本定義是任意時刻，最多只能有一個未被確認的小段。 所謂“小段”，指的是小於MSS尺寸的數據塊，所謂“未被確認”，是指一個數據塊傳送出去後，沒有收到對方傳送的ACK確認該數據已收到。
Nagle算法的規則（可參考tcp_output.c檔案里tcp_nagle_check函式注釋）：

（1）如果包長度達到MSS，則允許傳送；

（2）如果該包含有FIN，則允許傳送；

（3）設定了TCP_NODELAY選項，則允許傳送；

（4）未設定TCP_CORK選項時，若所有發出去的小數據包（包長度小於MSS）均被確認，則允許傳送；

（5）上述條件都未滿足，但發生了逾時（一般為200ms），則立即傳送。

偽代碼：

    if there is new data to send #有數據要傳送        # 傳送視窗緩衝區和佇列數據 >=mss，佇列數據（available data）為原有的佇列數據加上新到來的數據        # 也就是說緩衝區數據超過mss大小，nagle算法儘可能傳送足夠大的數據包        if the window size >= MSS and available data is >= MSS             send complete MSS segment now # 立即傳送        else            if there is unconfirmed data still in the pipe # 前一次傳送的包沒有收到ack                # 將該包數據放入佇列中，直到收到一個ack再傳送緩衝區數據                enqueue data in the buffer until an acknowledge is received             else                send data immediately # 立即傳送            end if        end if    end if　

Nagle算法只允許一個未被ACK的包存在於網路，它並不管包的大小，因此它事實上就是一個擴展的停-等協定，只不過它是基於包停-等的，而不是基於位元組停-等的。Nagle算法完全由TCP協定的ACK機制決定，這會帶來一些問題，比如如果對端ACK回復很快的話，Nagle事實上不會拼接太多的數據包，雖然避免了網路擁塞，網路總體的利用率依然很低。

Nagle算法是silly window syndrome(SWS)預防算法的一個半集。SWS算法預防傳送少量的數據，Nagle算法是其在傳送方的實現，而接收方要做的是不要通告緩衝空間的很小增長，不通知小視窗，除非緩衝區空間有顯著的增長。這裡顯著的增長定義為完全大小的段（MSS）或增長到大於最大視窗的一半。
注意：BSD的實現是允許在空閒連結上傳送大的寫操作剩下的最後的小段，也就是說，當超過1個MSS數據傳送時，核心先依次傳送完n個MSS的數據包，然後再傳送尾部的小數據包，其間不再延時等待。（假設網路不阻塞且接收視窗足夠大）

舉個例子，client端調用socket的write操作將一個int型數據（稱為A塊）寫入到網路中，由於此時連線是空閒的（也就是說還沒有未被確認的小段），因此這個int型數據會被馬上傳送到server端，接著，client端又調用write操作寫入‘\r\n’（簡稱B塊），這個時候，A塊的ACK沒有返回，所以可以認為已經存在了一個未被確認的小段，所以B塊沒有立即被傳送，一直等待A塊的ACK收到（大概40ms之後），B塊才被傳送。

這裡還隱藏了一個問題，就是A塊數據的ACK為什麼40ms之後才收到？這是因為TCP/IP中不僅僅有nagle算法，還有一個TCP確認延遲機制 。當Server端收到數據之後，它並不會馬上向client端傳送ACK，而是會將ACK的傳送延遲一段時間（假設為t），它希望在t時間內server端會向client端傳送應答數據，這樣ACK就能夠和應答數據一起傳送，就像是應答數據捎帶著ACK過去。在我之前的時間中，t大概就是40ms。這就解釋了為什麼'\r\n'（B塊）總是在A塊之後40ms才發出。
當然，TCP確認延遲40ms並不是一直不變的，TCP連線的延遲確認時間一般初始化為最小值40ms，隨後根據連線的重傳逾時時間（RTO）、上次收到數據包與本次接收數據包的時間間隔等參數進行不斷調整。另外可以通過設定TCP_QUICKACK選項來取消確認延遲。

　　2. TCP_NODELAY 選項
　　

默認情況下，傳送數據採用Nagle 算法。這樣雖然提高了網路吞吐量，但是實時性卻降低了，在一些互動性很強的應用程式來說是不允許的，使用TCP_NODELAY選項可以禁止Nagle 算法。

此時，應用程式向核心遞交的每個數據包都會立即傳送出去。需要注意的是，雖然禁止了Nagle 算法，但網路的傳輸仍然受到TCP確認延遲機制的影響。
3. TCP_CORK 選項
　　

所謂的CORK就是塞子的意思，形象地理解就是用CORK將連線塞住，使得數據先不發出去，等到拔去塞子後再發出去。設定該選項後，核心會盡力把小數據包拼接成一個大的數據包（一個MTU）再傳送出去，當然若一定時間後（一般為200ms，該值尚待確認），核心仍然沒有組合成一個MTU時也必須傳送現有的數據（不可能讓數據一直等待吧）。
然而，TCP_CORK的實現可能並不像你想像的那么完美，CORK並不會將連線完全塞住。核心其實並不知道套用層到底什麼時候會傳送第二批數據用於和第一批數據拼接以達到MTU的大小，因此核心會給出一個時間限制，在該時間內沒有拼接成一個大包（努力接近MTU）的話，核心就會無條件傳送。也就是說若套用層程式傳送小包數據的間隔不夠短時，TCP_CORK就沒有一點作用，反而失去了數據的實時性（每個小包數據都會延時一定時間再傳送）。
4. Nagle算法與CORK算法區別
　　
Nagle算法和CORK算法非常類似，但是它們的著眼點不一樣，Nagle算法主要避免網路因為太多的小包（協定頭的比例非常之大）而擁塞，而CORK算法則是為了提高網路的利用率，使得總體上協定頭占用的比例儘可能的小。如此看來這二者在避免傳送小包上是一致的，在用戶控制的層面上，Nagle算法完全不受用戶socket的控制，你只能簡單的設定TCP_NODELAY而禁用它，CORK算法同樣也是通過設定或者清除TCP_CORK使能或者禁用之，然而Nagle算法關心的是網路擁塞問題，只要所有的ACK回來則發包，而CORK算法卻可以關心內容，在前後數據包傳送間隔很短的前提下（很重要，否則核心會幫你將分散的包發出），即使你是分散傳送多個小數據包，你也可以通過使能CORK算法將這些內容拼接在一個包內，如果此時用Nagle算法的話，則可能做不到這一點。