様々な輻輳制御アルゴリズム
輻輳制御アルゴリズムとは、輻輳ウインドウサイズ（cwndと表されます）をいかに上手にコントロールするか、の方法です。より効率の良いデータ転送を実現するために、これまで非常に多くの輻輳制御アルゴリズムが研究されてきました。
これまでに開発された代表的な輻輳制御アルゴリズムとその関係性を、図1を用いて紹介します。
図1 様々な輻輳制御アルゴリズム
図中では、四角い囲みが各輻輳制御アルゴリズムの名称と提案年を表します。横軸は時間軸で、右に位置するものほど新しい輻輳制御アルゴリズムであることを表します。塗りつぶしの色はフィードバック形式の違いを表し、黄色がLoss-based、濃緑がDelay-based、そして水色がHybridを表します。Loss-basedはパケットロスを、Delay-basedは遅延を、Hybridはその両方を基準に、cwndを更新する輻輳制御アルゴリズムです。また矢印は、cwnd更新式の流用関係を表します。NewRenoは、BBR以外のすべての輻輳制御アルゴリズムで部分的に流用されていることがわかります。CUBICはBICの改良版ですので、BICからCUBICに矢印が引かれています。YeAHは、NewRenoと、その他のアグレッシブな輻輳制御アルゴリズム（CUBIC、HighSpeed、Scalable、H-TCP）を状況に応じて使い分けます。Venoは、名前のとおりNewRenoとVegasを融合した輻輳制御アルゴリズムです。
近年提案・実装された輻輳制御アルゴリズムの中でも、CUBICおよびBBRは特に重要です。CUBICは、Loss-based型で主流の輻輳制御アルゴリズムの一つであり、Linux 2.6.19以降で標準搭載されています。一方でBBRは、Delay-based型で主流の輻輳制御アルゴリズムの一つです。BBRは、Googleが2016年9月に発表して以降、Linuxカーネル4.9以降で利用可能となり、Google Cloud PlatformやYouTube等でも用いられています。これらのアルゴリズムについては、次回以降に詳しくご紹介します。
今回は、先ほど述べた3種類の輻輳制御アルゴリズム（Loss-based、Delay-based、Hybrid）について、その概要や特徴を簡単に解説します。
Loss-based輻輳制御
Loss-based輻輳制御とは、ネットワーク輻輳状態の指標としてパケット廃棄数を用いる手法です。長く標準的なアルゴリズムとして広く利用されてきたNewRenoもこの分類に該当します。一般的に、ネットワークが空いていればパケットは廃棄されず全てのパケットが目的地まで転送される一方で、ネットワークが混雑するほど、バッファあふれ等により経路上で廃棄されるパケット数が増加すると考えられます。
Loss-based輻輳制御では、この考え方をベースに、廃棄されるパケットの数が多いほどネットワークの輻輳状態が悪化していると判断し、輻輳ウインドウサイズを調整します。すなわち基本的には、パケット廃棄が発生するまでは徐々に輻輳ウインドウサイズを増加させていき、パケット廃棄を検出すると輻輳ウインドウサイズを大きく減少させる、という動作を行います。言い換えれば、パケットが廃棄されない範囲でなるべく高いスループットを実現しようとするものです。ただし、ネットワーク上の輻輳状態を直接知ることができないため、徐々にパケット数を増やしていき、廃棄されたところでこれを減少させるのです。このような制御方法はAIMD（Additive-Increase / Multiplicative-Decrease）と呼ばれます。
AIMD制御では、パケット廃棄が発生するまでは徐々に輻輳ウインドウサイズを増加（加算的な増加＝Additive-Increase）させ、パケット廃棄が発生すると大きく輻輳ウインドウサイズを減少（乗算的な減少＝Multiplicative-Decrease）させます。この大まかな動作イメージを図2に示します。
図2 AIMD制御のイメージ
AIMD制御における輻輳ウインドウサイズ制御の一般表現として、時刻tにおける輻輳ウインドウサイズw(t)について、時刻t+1で更新された輻輳ウインドウサイズの値を次の式で表すことができます。なお輻輳ウインドウサイズは、基本的にACK受信ごとに更新されます。
※非輻輳時、輻輳時
ここで変数a、bはそれぞれ、RTTあたりの非輻輳時の輻輳ウインドウサイズ増加量およびパケット廃棄検出時の輻輳ウインドウサイズ減少量を定めるパラメタです。この式が意味するのは、ネットワーク上で輻輳が発生していないときには輻輳ウインドウサイズをaずつ加算していき、輻輳が発生しているときには輻輳ウインドウサイズをw(t)*bだけ乗算的に減少させる、ということです。パラメタa、bを調整することで輻輳ウインドウサイズの増加速度や減少速度が大きく変わってくることが想像できます。例えばaを大きくすれば輻輳ウインドウサイズは速く増加するようになりますし、bを大きくすれば輻輳時の輻輳ウインドウサイズの減少を抑えることができます。
Delay-based輻輳制御
Delay-based輻輳制御では、ネットワークの輻輳状態の指標としてRTTを利用します。RTTが大きくなるほど輻輳状態が悪化していると判断して輻輳ウインドウサイズを調整します。つまり、ネットワーク機器のメモリ上での転送待ち時間は、メモリ上にどれだけデータが蓄積されているかによって大きく変動します。出力リンクからのデータ転送速度は一定なので、この速度に対して単位時間あたりの入力データ量が大きくなれば、出力しきれないデータがメモリ上にどんどん蓄積されてしまい、新しく流入したパケットを転送するまでに時間がかかってしまいます。Delay-based輻輳制御では以上の性質を利用して、RTT増大の原因が経路上における転送待ち遅延の増大によるものであると解釈します。
代表的なDelay-based輻輳制御アルゴリズムであるVegasについて、以下にその要点を記述します。時刻tにおける輻輳ウインドウサイズw(t)について、時刻t+1で更新された輻輳ウインドウサイズの値を次の式で表すことができます。
ここで、dは往復の伝搬遅延であり、D(t)は実際に測定されたRTTを表します。つまりw(t)/dとは期待スループット、w(t)/D(t)は時刻tにおける実際のスループットを指しており、これらの差を閾値αと比較した結果に応じてw(t)を増減させます。なお閾値αは事前に設定するパラメタです。もしネットワーク上でのバッファ遅延が非常に小さければ、期待スループットと実際のスループットとの差はαより小さくなり、その場合には上式に示す通りRTTごとに輻輳ウインドウサイズは1増加します。一方で、輻輳が強まりバッファ遅延が大きくなると、期待スループットと実際のスループットとの差がαを超え、RTTごとに輻輳ウインドウサイズを1減少させることで、パケット送出を抑えます。
Hybrid輻輳制御
Hybrid輻輳制御は、パケット廃棄と遅延の双方を指標にするアルゴリズムです。有名なものとして主に無線通信向けの輻輳制御アルゴリズムであるVenoがあります。NewRenoをはじめとする従来のAIMDでは、ランダムなパケットロスに起因する（つまり輻輳とは関係がない）重複ACKと、輻輳に起因する重複ACKを区別できませんでした。そのため、無線通信において過剰に送信レートが低くなるという課題がありました。そこでVenoは、Vegasで導入された遅延を用いて輻輳度合いを推定することで、この問題を回避する方法を採用しています。Venoの名前の由来はRenoとVegasであり、重複ACKとRTTの両方を用いてデータ送信量を制御するため、Hybrid型の輻輳制御アルゴリズムに該当します。
さて、以上で解説してきたように、TCPの輻輳制御アルゴリズムは大きく分けて3種類あります（図3）。
図3 輻輳制御アルゴリズムの種類
これらは、それぞれに異なった特徴があり、適した環境などが異なるため、どれが優れているかといったことは一概には言えない、という点には注意する必要があります。例えば、複雑な制御を行うアルゴリズムは輻輳ウインドウサイズをきめ細かく増減させやすい傾向がありますが、その一方で、理論的な解析が困難でどのような動作をするかが予測しにくくなったり、さらには性能の低いデバイスでは処理が重くなってしまったりすることがあります。またNewRenoは広帯域・高遅延環境には適していないなど、それぞれの適用領域があります。このように、実際には環境に合わせて適したアルゴリズムを選択して用いるべきであり、そのためには各アルゴリズムの特性をよく知っておくことが重要なのです。
