Nagleアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Nagleアルゴリズム（ネーグルアルゴリズム、Nagle’s algorithm）は、TCP/IP ネットワークで送信しなければならないパケット数を減らし、効率性をあげるためのアルゴリズムである。ジョン・ネーグル (John Nagle) から名づけられた。

Nagleが1984年に書いたRFC文章、Congestion Control in IP/TCP Internetworks (RFC 896) では、彼が「小さなパケット問題」と呼ぶ、アプリケーションが繰り返し1バイトなど小さな粒度で送信する問題を取り上げている。IPv4 で 20バイト、TCP自体で20バイトのヘッダーがあり、合計40バイトになるため、1バイトを送信するのに合計41バイト送信しなくてはならなく、オーバーヘッドが大きい。これは、Telnet セッションなどでよく発生し、キー操作が1バイトのデータを生成し、即時に送信されるからである。悪いケースでは、通信速度が遅い回線では、同時にそのようなパケットが大量に送信され、輻輳崩壊へとつながる可能性がある。

Nagleアルゴリズムでは最大セグメントサイズ以下の複数の送信メッセージを一つに束ね、まとめて送信する。特に、送信パケットで送信側が ACK を受け取っていないのがある場合、送信するに値するまで送信側はバッファリングを行い、そして、一度にまとめて送信する。

アルゴリズム[編集]

Nagleアルゴリズムは以下の条件がどれか1つでも成立するまで送信を遅延させる。

擬似コードでは以下の通り： 

if 新しいデータを送信するとき
  if ウィンドウサイズ >= 最大セグメントサイズ(MSS) and 送信データ >= 最大セグメントサイズ
    最大セグメントサイズ分を即座に全て送信
  else
    if ACK を受け取っていないデータが残っている場合
      ACK を受け取る or タイムアウトになるまでバッファに貯める
    else
      即座に送信
    end if
  end if
end if

このアルゴリズムは TCP遅延ACK との相性が悪い。TCP遅延ACK は別のグループにより1980年代初期に同時期に導入された。両方を有効にすると、アプリケーションが2回書き込みを行い、2回目の書き込みが受信側に届くまで受け取れない読み込みを送信側が行うと、最大 500ms の遅延が発生し、これは「ACK遅延」と呼ばれる。この理由から、TCP の実装は、たいてい、Nagleアルゴリズムを無効にするオプションを提供している。一般にこれは TCP_NODELAY オプションと呼ばれる。

もし、アプリケーションが可能なら、小さな書き込みを複数回連続して行うのを避けるべきであり、すると Nagle アルゴリズムが発動するのを回避できる。アプリケーションはバッファリングを行い、小さな書き込みを1つにまとめるべきである。UNIX などでは writev() で実現できる。各種プログラミング言語のバッファ付きストリームでも良い。

ユーザーレベルでできる解決策は、ソケットに対して、write-write-read の順番で読み書きすることを避けることである。write-read-write-read は大丈夫である。write-write-write は大丈夫である。しかし write-write-read はダメである。それ故、可能なら、TCP での小さな書き込みをバッファリングして一度に一つにまとめて送信するべきである。標準的な UNIX I/O パッケージを使用し、読み込みの前に書き込みのフラッシュを行うならば通常は機能する。 — （引用を和訳）[1]

小さなパケット問題と silly window syndrome は時々混乱される。小さなパケット問題はウィンドウがほとんど空の時に発生する。silly window syndrome はウィンドウがほとんどいっぱいの時に発生する。

Nagleアルゴリズムのタイムアウトは、一般的に200msだが設定で変更も可能。

小さくない書き込みでの負の影響[編集]

このアルゴリズムはいかなるサイズの書き込みにも適用される。もし、1回の書き込みでのデータ量が 2n パケットにわたるならば、最後のパケットは、前のパケットの ACK を受け取るまで保持されることになる[2]。全てのリクエスト－レスポンス型のアプリケーションのプロトコルにおいて、リクエストデータが単一パケットよりも大きいならば、送信側がちゃんとデータをバッファしても、送信側と応答側の間のレイテンシは数百ms以上になる。そのようなケースではNagleアルゴリズムは送信側で無効にしておかなければならない。もし、応答データが単一パケットよりも大きいならば、レスポンス全体を即座に受け取れるように、応答側はNagleのアルゴリズムを無効にしなければならない。

一般的に、Nagleのアルゴリズムは不注意なアプリケーションから守るためにあるので、正しくバッファリングを行うアプリケーションにはメリットがない。そのようなアプリケーションでは、効果がないか、負の効果しかない。

リアルタイムシステムでの応答性[編集]

リアルタイムの反応を期待するアプリケーションでは、Nagle アルゴリズムは悪く働く。例えばオンラインゲームでは操作は即座に送られることが期待されるが、このアルゴリズムはレイテンシを犠牲にして効率性をあげているため意図的に送信を遅延させる。この理由から、低帯域だが応答の反応性を求めるアプリケーションでは一般的に TCP_NODELAY を使い、Nagle 遅延を回避する[3]。

参考文献[編集]

  1. ^ Boosting Socket Performance on Linux - Slashdot
  2. ^ “TCP Performance problems caused by interaction between Nagle's Algorithm and Delayed ACK”. Stuartcheshire.org. 2012年11月14日閲覧。
  3. ^ Bug 17868 – Some Java applications are slow on remote X connections

外部リンク[編集]

「https://ja.wikipedia.org/w/index.php?title=Nagleアルゴリズム&oldid=97836878」から取得