【Linux】輻輳制御アルゴリズムの紹介

2019年5月14日

輻輳（ふくそう）とは物が一か所に集中して混雑する様子をいう言葉であり、通信工学の分野では「congestion」の訳語として充てられた専門用語です。

通信工学の分野で輻輳とは通信要求の過多により正常な通信が成立しづらくなる状況を言います。

輻輳制御とはネットワークで通信の効率化や混雑の回避のために輻輳状態に至らないように通信を制御することです。

Linuxでは通信用途に応じた様々な異なる制御アルゴリズムの中から輻輳制御を選択して使用できるようになっています。

輻輳制御の中でも代表的なものや比較的最近カーネルに取り込まれたものを紹介していきたいと思います。

輻輳制御とは

輻輳制御とは通信において輻輳や輻輳崩壊を防ぐためにネットワークの混雑状況を見ながらトラフィックなどを調整する仕組みのことです。

通信工学の分野において英語で「congestion control」と呼ばれている専門用語の日本語訳が「輻輳制御」です。

ちなみに受信側のバッファが溢れないようにするフロー制御というものもありますが、輻輳制御とは異なる概念です。

輻輳制御アルゴリズム設定の確認

以下のカーネルパラメータを参照することにより現在設定されている輻輳制御アルゴリズムを確認することができます。

net.ipv4.tcp_congestion_control

特にアプリケーション側で通信オプションに輻輳制御アルゴリズムを指定していない場合は、ここで設定されているアルゴリズムが使用されます。

輻輳制御アルゴリズム

CUBIC

CUBICは現在のLinuxではデフォルトで設定されている一番ポピュラーな輻輳制御アルゴリズムとなっています。

CUBICは元になったBICというアルゴリズムを改良してウィンドウサイズ制御関数を簡素化しており、既存の通信およびRTTでの公平性を改善するアルゴリズムとなっています。

CUBICはパケットロスを輻輳の判断に用いるロスベースの輻輳制御アルゴリズムであり、最後にパケットが破棄されてからの経過時間によってウィンドウサイズが3次関数的に増加します。

BBR

BBR(Bottleneck Bandwidth and Round-trip propagation time)はGoogleが開発した輻輳制御アルゴリズムで、GCP(Google Cloud Platform、Googleのクラウド環境)では標準で使用できるようになっています。

最近のカーネルにも取り込まれていますので、カーネルコンパイル時にCONFIG_TCP_CONG_BBRを設定すれば使用できます。

近年ではロスベースの輻輳制御アルゴリズムによるバッファブロートという新たなパフォーマンス上の問題が出てきておりロスベースのアルゴリズムでは限界が見えていました。

そこで最近のネットワーク環境において輻輳を回避しながらも最大スループットと最小RTTという目的を達成するために設計されたのがBBRというアルゴリズムです。

BBRでは観測と推定を繰り返すことによってロスベースやディレイベースとは異なるアプローチで輻輳検知を行っています。

Googleではこの輻輳制御アルゴリズムを広域WANやGoogleおよびYouTubeのWebサーバに導入して、CUBICと比較して大幅なスループットとレイテンシの改善が確認されたとしています。

CDG

CDG(CAIA-Delay Gradient)はパケット遅延の変化勾配を利用して輻輳を検知する輻輳制御アルゴリズムです。

通常輻輳の検出アルゴリズムにロスベースとディレイベースを併用すると互いに悪影響を与える可能性があります。

CDGではロスベースのアルゴリズムと共存が可能ということが特徴となっています。

最近のLinuxカーネルにもこのCDGのアルゴリズムは取り込まれていますので、CONFIG_TCP_CONG_CDGを設定してカーネルをコンパイルすることで使用可能になります。

その他アルゴリズム

Linuxには紹介した以外にも様々な輻輳制御アルゴリズムが取り込まれています。

WiFi通信のようなパケットロスが多い環境での使用を想定したWestwood+

データセンターのようなパケットロスの少ない低遅延での環境を想定したDCTCP

それぞれに特徴がありますので気になったアルゴリズムがあったら調べてみると面白いと思います。

各アルゴリズムの簡単な説明はカーネルコンフィグのヘルプから見ることもできますので機会があれば参照してみて下さい。

まとめ

あまり表立って設定されることのない輻輳制御アルゴリズムですが、通信の世界では地味ですがとても重要な要素だったりします。

Linuxにデフォルトで設定されている輻輳制御アルゴリズムのCUBICが安定しているので通常のサービスであまり変更する技術者はいないのかもしれません。

しかしGoogleなどアグレッシブな企業では積極的に輻輳制御アルゴリズムの実験を行っています。

現在のネットワークにおいて輻輳制御アルゴリズムの技術は益々重要になってきていると言えると思います。