Nagle’s Algorithm 和 Delayed ACK 以及 Minshall 的加強版

fcamel

Published in

fcamel的程式開發心得

10 min readOct 14, 2017

原本想寫篇文章討論 TCP_NODELAY、TCP_QUICKACK、TCP_CORK、MSG_MORE 的效果並寫程式實測比較，結果發現有些背景知識不太好說明，所以先寫這篇說明比較繁瑣的背景知識。

這篇的目的是那天我忘光這些東西時，可以只讀這篇就好。換句話說，讓你只要大概知道 TCP 是啥，不用 K 一些 TCP 瑣碎的文件，可以徹底搞懂這兩個演算法在作什麼 (盡量啦…)。

Nagle’s Algorithm

問題描述: 傳送 TCP 封包的時候， TCP header 占 20 bytes， IPv4 header 占 20 bytes，若傳送的資料太小， TCP/IPv4 headers 造成的 overhead (40bytes) 並不划算。想像傳送資料只有 1 byte，卻要另外傳 40 bytes header，這是很大的浪費。若網路上有大量小封包，會占去網路頻寬，可能會造成網路擁塞。

於是有了 Nagle’s Algorithm，用來避免產生大量的小封包。網路上對於 Nagle’s Algorithm 的說明都差不多，但是有些細節不夠清楚，對照 Wikipedia 和 RFC 896，不確定完整的規則是什麼。轉念一想，Linux kernel 的實作總不會錯吧，然後在原始碼裡看到另一份規範 draft-minshall-nagle-01。這個就說明得很清楚了，摘要相關部份:

If a TCP has less than a full-sized packet to transmit,
and if any previous packet has not yet been acknowledged,
do not transmit a packet.

就這麼簡單的一句話，不過要搞懂它的意思，得先了解一些相關名詞:

full-size packet: MSS (maximum segment size) 是 TCP 封包的最大值，預設是 536 bytes。有些人提到由於 Ethernet 公定可處理 1500 bytes 的封包，所以也可以設 MSS 為: 1500–40=1460 (bytes) [*1]。對 full-size packet 來說，這個值愈大，TCP / IP header 的 overhead 相對封包大小愈小。
acnowledged: TCP 傳送封包時會帶有流水號，起始值隨機，後面每傳 1 byte 就 +1。對方收到後會回傳 ACK 封包，帶有最後收到 byte 的數字。比方說收到 100 bytes，再收到 200 bytes，只要 ACK「起始值+300」即可。
sliding window: 允許傳送 unacked bytes 的最大值，確保在網路不佳的情況下，傳送端不會傳送過多封包加重擁塞。sliding window 的最大值是 2¹⁶ = 64 (KB)。下面是一個示意圖， window size = 20 bytes:

TCP Sliding Window Acknowledgment System For Data Transport, Reliability and Flow Control

換句話說，若一直有 full-sized packet，只要 sliding window 還有空間，Nagle’s Algorithm 會一直送，不會等 ACK。

反之，若應用層陸續送出小封包， Nagle’s Algorithm 送出第一個封包後 (第一個沒滿也會送)，即使 sliding window 還有空間，也會停住不送。直到集滿 MSS 的量再送出 full-size packet。或是等收到上個小封包的 ACK 後，再送下個小封包。同段時間內最多只會傳一個小封包出去。

這裡要留意一點: Nagle’s Algorithm 是處理 TCP 層級的資料。若應用層一次送出的資料剛好被切成兩個 packet 且第二個 packet 沒滿，Nagle’s Algorithm 送完第一個 packet 後，也會等收到 ACK 後才會再送第二個 packet。這造成應用層意外的延遲，有時有害(後述)。

Delayed ACK

ACK 也是小封包，為了避免產生太多小封包，所以接收端不會每次收到封包都立即發 ACK，如果之後剛好需要送資料，順便帶上 ACK去可以省去小封包。實例: telnet server 會回傳使用者剛打的字，順便送 ACK 就可以省去小封包。

這裡一樣引用 draft-minshall-nagle-01 的說明:

This process, known as ``delayed ACKing'' [RFC1122],
typically causes an ACK to be generated for every other received
(full-sized) data packet.  In the case of an ``isolated'' TCP
packet (i.e., where a second TCP packet is not going to arrive
anytime soon), the delayed ACK policy causes an acknowledgement for
the data in the isolated packet to be delayed up to 200
milliseconds of the receipt of the isolated packet (the actual
maximum time the acknowledgement can be delayed is 500ms [RFC1122],
but most systems implement a maximum of 200ms

重點:

通常最多延遲 200ms，RFC 規定不能超過 500ms。
每收到兩個 full-sized packet，一定要回一次 ACK。

Linux 的實作在 __tcp_ack_snd_check()，規則是以下其中一個條件滿足就會送出 ACK

收到且還沒 ACK 的資料超過 MSS (用發送端的 MSS 計算)，並且應用層讀取資料速度夠快。
在 quickack mode: 應用層可以強迫啟用這個模式。
收到 out-of-order 資料，要馬上通知發送端收到的部份 (用 SACK)，避免重傳。

兩者合用的問題

假設傳送端有開 Nagle’s Algorithm，接收端有開 delayed ACK (兩者在 Linux 都是預設值)。

以 HTTP 為例，若 server 的 response 被切成兩次 send，一次送 header，一次送 body，兩者都 <MSS。

server 送完 header 後，因為 client 沒有回 ACK (delayed ACK)，server 也不會送 body (應用層覺得它已經送出了，但 kernel 還沒送)。
client 過了 200ms，送出收到 header 的 ACK。
server 收到 ACK 後，送出 body。

於是 client 多等了 200ms 才收到完整的 response。

這是真實發生的例子，在許多地方出現過 (例1、例2、例3)。

即使 header 和 body 合在一起送，若兩者合起來 >MSS 但沒有剛好是 MSS 的整數倍，還是會有最後一個未滿 MSS 的封包，造成額外 200ms 的延遲。

Minshall 對 Nagle’s Algorithm 的修改

早在 1999 年，Minshall 提出了一點小修改，減少 Nagle’s Algorithm 和 delayed ACK 合在一起造成的問題。他提出的修改版本如下:

If a TCP has less than a full-sized packet to transmit,
and if any previously transmitted less than full-sized
packet has not yet been acknowledged, do not transmit
a packet.

引用文中的 pseudo code 會比較好理解修改版 (以下稱為新版) 和舊版的差異:

// Nagle's Algorithm
if ((packet.size < Eff.snd.MSS) && (snd.nxt > snd.una)) {
    do not send the packet;
}// Minshall's version
if (packet.size < Eff.snd.MSS) {
    if (snd.sml > snd.una)) {
        do not send the packet;
    } else {
        snd.sml = snd.nxt+packet.size;
        send the packet;
    }
}

snd.nxt: 下一個要送的 byte。
snd.una: 最小的 unack byte。
snd.sml: 最近一個送出的小 packet (這裡和未滿的 packet 等義) 的最後一個 byte。

考慮應用層送了一份資料，被拆成兩個 packet，第一個滿了，第二個沒滿。在送出第一個 packet 後：

舊版不考慮上一個送出的 packet 是否有滿，只要沒收到 ACK，就不送第二個。
新版只有在上一個送出的 packet 未滿且沒收到 ACK 的情況，才不送第二個。
所以，這個情況新版會接著送出第二個 packet，不會等 ACK。

如果 HTTP 的 response header 和 body 合在一起送，不論是剛好一個 packet 裝滿，或是拆成多個 packet，新版都能避免額外的延遲。但若應用層拆成兩次送，新版一樣要等 header 的 ACK (假設 header 大小不是 MSS 整數倍) 才會送出帶有 body 的封包。

Linux kernel 相關的程式碼在這裡和這裡，有閒的時候會在另一篇文章和 TCP_CORK 一起分析。

避免延遲的解法

應用層維持 write-read-write-read 的模式，這樣寫完後對面會回傳資料，自然會帶上 ACK (=沒有 delayed ACK)。注意，舊版 Nagle’s Algorithm 在單次 write 量超出 MSS 的情況，在 TCP 層會變成 write-write-read，所以還是會受 delayed ACK 影響; 新版 (Minshall 的版本) 則無此問題。可以確定 Linux 是用新版，其它 OS 要再查證 [*2]。
傳送端設定 TCP_NODELAY (關掉 Nagle’s Algortihm) 或接收端設 TCP_QUICKACK (關掉 delayed ACK)。但關掉後可能會產生大量小封包，浪費 Internet 的頻寬，理論上網路擁塞時，效果更慘。有閒時寫個程式實驗看看 trade-off，然後在另一篇文章討論 (更新: 結果見《Linux 上 TCP QUICKACK 的效果》)。

備註

*1 這讓我有些疑問，如果不是 Ethernet，不會因為封包太大被 router 掉包嗎？有閒再來查查這個設定是否可靠。
( 2017–11–13 更新: 《TCP maximum segment size 是什麼以及是如何決定的》有進一步說明 )
*2 《TCP Performance problems caused by interaction between Nagle’s Algorithm and Delayed ACK》文末提到 OS X v10.5 開始和 iOS 都有實作 Minhall 的版本，但我搜了一下沒找到官方的公告消息。