Nagleアルゴリズムと遅延ACK

はじめに
本題に入る前に
- 輻輳・輻輳制御とは
Nagleアルゴリズムとは
- The small-packet problem
The small-packet problem の解決法としてのNagleアルゴリズム
- 余談：Nagleアルゴリズムを無効化する
遅延ACKの前に…
- ウィンドウ
- スライディングウィンドウ
遅延ACK
Nagleアルゴリズムと遅延ACK
おわりに

はじめに

どうも、最近嫌な予感が段々と確信になっていくタイプのサイコホラー映画に弱いという事がわかったけんつです。

諸事情で、Linux カーネルモジュールとして実装したEchoサーバのコードを見なおしていたらNagleアルゴリズムと遅延ACKというものに出会いました。
気になったので色々と調べているとその仕組みが面白いなと思ったのでまとめます。

本題に入る前に

今回紹介することは、ネットワークで特にTCP/IPにおける輻輳制御についてのお話になる。
がしかし、輻輳制御ってなんやねんと思うのでちょっとまずそこに触れておく。

輻輳・輻輳制御とは

輻輳とは、「さまざまな物が1カ所に集中すること」*1 を指している。
ネットワークの分野に置いては「ラピュタが金曜ロードショーで放送されたときTwitterでバルスが流れまくる」ときの様に一箇所にアクセスが集中するときが輻輳のいい例となっている。

対して、輻輳制御とは輻輳が発生しそうになった場合にそれを制御することを指している。インフラにおいては、ロードバランサーがいい例として挙げられる。

Nagleアルゴリズムとは

ネーグルアルゴリズムと言うみたい。
RFC 896「IP/TCPインターネットワークにおける輻輳制御」*2で制定されており、その名の通り輻輳制御に関するアルゴリズムである。
そもそも、これが何故必要かということはある問題がキーになっているとRFCには記載されている。

The small-packet problem

この問題は、アプリケーションが1byte 程のサイズでパケットを送ってしまう際に発生する問題を指している。
何が問題かといえば、IPv4とTCPのそれぞれでヘッダーサイズが20byteあるため 1byte ほどのメッセージを送信するために 41byte のパケットを送信する点にある。
このヘッダーに対して明らかに大きすぎるパケットを送信してしまう現象は、 Telnetセッションでよく見られるらしく通信速度の遅いネットワークを圧迫する。

The small-packet problem の解決法としてのNagleアルゴリズム

この問題を解決するためにNagleアルゴリズムは存在している。
Nagleアルゴリズムは以下の３つの条件を満たすまで、パケットをバッファにためて条件を満たした段階で送信することで効率的にデータを送信するアルゴリズムである。
つまり、「Nagleアルゴリズムでは最大セグメントサイズ以下の複数の送信メッセージを一つに束ね、まとめて送信する。特に、送信パケットで送信側が ACK を受け取っていないのがある場合、送信するに値するまで送信側はバッファリングを行い、そして、一度にまとめて送信する。」アルゴリズムとなる*3

未送信データが最大セグメントサイズ以上になる
過去の送信パケットで ACK が未受信の物がなくなる
タイムアウトになる

このアルゴリズムで注意したい点は送信を遅延させる時間が200~500msであるという点(BDS系は最大200ms)。
これは次にまとめる遅延ACKとの相性が最高に悪く、オンラインゲームやその他のリアルタイム性を要求されるネットワークに於いて
そもそも、Nagleアルゴリズムがレイテンシを犠牲にしている分余計に遅延が発生してしまうという致命的な問題を発生させる。

余談：Nagleアルゴリズムを無効化する

前述の通り、リアルタイム性が要求される場合Nagleアルゴリズムは悪い影響を引き起こす場合がある。
そのため、特にレイヤーの低い分野においてソケットでTCP_NODELAYオプションが提供されている。
これを有効化することで、Nagleアルゴリズムを無効にできる。

遅延ACKの前に…

遅延ACKの前に前提としていくつかTCPについて知らなければならないことがあるのでそっちを先に紹介する。

ウィンドウ

TCPにはウィンドウという概念がある。
これは何かというと、TCPでは送信されてきたデータを一時的にバッファに溜め込んでアプリケーションはそこからデータを取り出し処理していく。
これをウィンドウといい、一度に溜め込める量をウィンドウサイズという。

そしてウィンドウサイズは、送信側が確認応答を待たずに一度に送信できる最大量でもある。

またこのウィンドウサイズはフロー制御によって変更される場合があり常に一定というわけではない。

スライディングウィンドウ

スライディングウィンドウについては以下のサイトがわかりやすくまとまっている。
beginners-network.com

このサイトでは、9000byteのデータを送信したい場合でウィンドウサイズが3000byteの場合を想定している。

まず9000 byteを 1セグメント 1000byte ずつ送信する場合3つのパケットを一度に送信できる。
受信側がACKを送信側に送った場合、3001byte~6000byte分のデータを送信する。

このように、相手側のウィンドウサイズに応じて送信するデータの範囲をずらしていくことをスライディングウィンドウという。

しかし、実際には1000byte送ってスライディングウィンドウすることも可能なのだがそれをしてしまうと1セグメントごとにACKを送る必要があるため
非常に効率が悪くなってしまうという問題が発生する。
これが次の遅延ACKに関連している。

遅延ACK

データを受信した側が即座にACKを返すと、フロー制御が働いて小さいウィンドウサイズが設定される場合がある。
送信側はそれに合わせてデータを送ってしまうと非常に効率が悪くなる。（これはSWS: Silliy WIndow Syndromeと呼ばれている）

そこで、このACKを意図的に送らせて、ネットワークを効率よく利用する方法が挙げられた。
それが遅延ACKとなる。

遅延させる場合は

2 * 最大セグメントサイズのデータを受信するまで確認応答しない。
上記以外の場合は最大200~500ms、ACKを遅延させる。

大体2セグメントごとにACKを送信するように遅延させる場合がおおい。(らしい)

上記で紹介した、遅延ACKとNagleアルゴリズムが両方働くと遅延が余分に働く場合がある
特にサーバが遅延ACKのタイムアウトになるまでリクエストがストップしてしまうという場合。*4

これは以下のサイトにわかりやすい例が記載されている。
postd.cc

特にわかりやすい例を以下にあげる

アプリケーション： やあ、パケット1だよ。
HAProxy：＜無反応で、2つ目のパケットを待っている＞
HAProxy：＜そのうちACKするけど、まあいいか＞
アプリケーション：＜無反応＞
アプリケーション：＜ACKを待っているんだけど、ネットワークが混雑しているのかな＞
HAProxy：もう待ち疲れた。はい、ACKだよ。
アプリケーション：やった！　じゃあ2つ目のパケットを送るよ。
HAProxy：よかった。これで終了だ。

送受信側が意図的に待機している時間があるが、そこで余分な200msが発生している。
これが、リアルタイム性を要求されている場合わりと致命的な遅延となってしまうのでNagleアルゴリズムを無効化するかTCP_CORKで遅延時間を制御する場合がある