-
Nagle算法
鎖定
Nagle算法是以他的發明人John Nagle的名字命名的，它用於自動連接許多的小緩衝器消息；這一過程（稱為nagling）通過減少必須發送包的個數來增加網絡軟件系統的效率。
- 中文名
- Nagle算法
- 發明人
- John Nagle
- 優 點
- 減少擁塞控制
- 所屬領域
- 計算機
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.
Nagle算法算法
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確認延遲機制的影響。
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算法的話，則可能做不到這一點。
