本連載の背景と目的
近年、LTEなどの高速なネットワークの展開とスマートフォンや様々なクラウドサービスの普及により、インターネットを流れるデータ量は急激に増大しています。今後も、新たなスマートデバイスやIoTサービスの普及、5Gサービスの商用展開などに従い、私たちの生活においてインターネットへの接続は不可欠なものとなっていくと考えられます。そのインターネットにおいて広く利用されているプロトコルがTCP/IPです。TCP/IPは1980年頃にその基本形が完成して以来、インターネットの普及とともに広まり、発展を続けてきました。
本連載では、TCP/IPの中でも初学者にとって難しいプロトコルであるTCPに着目します。TCPは通信の信頼性を担保するための様々な機能を備えています。特に、ネットワークの状況に応じて効率的にデータを転送するための輻輳制御アルゴリズムは、今日にいたるまで様々な手法が提案、実装されてきた重要な機能です。輻輳制御アルゴリズムとは、その名の通り輻輳を制御するための手法です。
輻輳とはネットワークの混雑を指します。つまり、インターネットなどのネットワークは多数のルータ等のネットワーク機器から構成されます。これらの機器は、有線（光ファイバケーブル等）あるいは無線で物理的に接続されていますが、それらの通信媒体が単位時間当たりに伝送可能なデータ量には限りがあります。また機器自体が単位時間当たりに処理可能なデータ量にも上限があります。
限界を超える量のデータがネットワークに流入すれば、ネットワーク機器のバッファ（メモリ）に蓄積するデータが増え、その容量を超えたデータは消失してしまいます。すぐに輻輳の発生した箇所やその原因を特定して対策を講じることができれば話は早いのですが、特にインターネットのような多種多様な主体が関わるネットワークでは、それは現実的には不可能です。
この輻輳を防ぐためにTCPに備えられているのが、輻輳制御アルゴリズムです。いかに輻輳を避けつつ効率的にデータ送信量を制御するか、古くから研究が進められ、これまでに非常に多くのアルゴリズムが提案されてきました。輻輳制御アルゴリズムについて理解する上で特に注意が必要なポイントとして、いかに強力な輻輳制御アルゴリズムでも、技術の進歩とともにネットワーク環境が変われば新たな課題が顕在化することがある、という点があります。
そこで、本連載では特に、新たなアルゴリズムが登場してきた背景としてのネットワーク環境の変化に着目しながら、TCP輻輳制御アルゴリズムの変遷を辿り、その概要をみていきます。本連載の構成として、まず第1回である今回は、初学者向けにTCPの輻輳制御の基本的な考え方や仕組みを概説します。次に第2回では、これまでに提案された様々な輻輳制御アルゴリズムについて、大きく3つのタイプに分けて各々の制御の狙いや概要を説明します。第3回では、近年広く利用されてきた標準的なアルゴリズムの1つであるCUBICについて紹介します。最後に、第4回にはGoogleが2016年9月に発表して以来その利用が広がっているBBRについて、その概要を解説します。
TCPの輻輳制御の基本的な考え方
まずは、最も古典的な輻輳制御アルゴリズムであるTahoe（1988年に発表）を例に、ここでは大まかな動作（図1）と、その意義を説明します。Tahoeでは、送信側端末で❶まず徐々に一度に送出するデータ量（＝輻輳ウインドウサイズ）を増加させ、❷輻輳を検知すると、❸輻輳ウインドウサイズを低減させます。Tahoeの目的は、上記の動作によりネットワークの輻輳を抑え、正常な通信が可能な状態に回復させることです。これはつまり、各端末がデータを送信する機会を得ることを中心に考えるのではなく、状況に応じてデータ送出量を調整する、ということです。❷の輻輳検知の方法としては、パケットロスを用いるタイプや、遅延を用いるタイプがあります（詳しくは次回に解説します）。
図1 Tahoeにおける輻輳制御の様子
上記のような動作を実現するために、スロースタート、輻輳回避、高速リカバリといったアルゴリズムを使い分けることで、輻輳ウインドウサイズを上手に制御する方法が、輻輳制御アルゴリズムです。以下では、スロースタート、輻輳回避、高速リカバリについて、それぞれ大まかに解説します。
スロースタート
あるアプリケーションがデータ送信を始めるとき、どの程度のデータレートが適切なのかは送信者からは分かりません。そこで既に混雑しているネットワークに大量のデータが流入することを防ぐために、通信開始時にはスロースタートと呼ばれるアルゴリズムに従ってデータを送信します。
輻輳ウインドウサイズをcwndで表すとき、送信側はまずcwndを1セグメントサイズ（TCPにおけるデータ分割サイズであり、通信経路のMTU（最大伝送サイズ）から定まる）に設定して送信します。これに対するACK（確認応答）を受け取ったとき、cwndを1セグメント増加させます。つまり、送信側はACKを1つ受け取るごとに2つのセグメントを送信できることになります。そして、受信側から通知されたウインドウサイズrwndに達するまでこの式に基づき転送量を上げていきます。セグメントの送信からACKを受信するまでの時間である1RTT（Round Trip Time）ごとに見た場合、cwndは指数関数的に増加していくように見えます。このスロースタートアルゴリズムにより通信開始時のトラヒック量を抑え、輻輳の発生を抑えることができるのです。
スロースタートによる通信フローとスライディングウインドウ、そして輻輳ウインドウサイズcwndの変化の様子を図2に示します。ここでは、最大セグメントサイズは簡単のために1としています。cwndは最小値である1からデータ転送を開始し（❶）、ACKを受け取るごとにcwndは2（❷）、4（❸）、8（❹）と増加していきます。なお、ACKの番号は受信側において未受信のシーケンス番号となっています。ウインドウはACKを受け取るごとにスライドしながら、未送信のセグメントを送信します。最大となるcwndを16とすると、これに到達した後は一定値を保ちます。これ以降はACKを受け取ったとしてもcwndは増加せず、受け取ったACKと同数のセグメントを新規に送信することになります。
図2 スロースタート
輻輳回避
スロースタートでは指数的にcwndが拡大するため、時間の経過とともにデータ転送量が大幅に増えていきます。このスロースタートによるcwndを、輻輳を検知してcwndを低下させた後にも続ければ、またすぐに輻輳を起こしてしまう可能性が高いと考えられます。これを防ぐための方法が、輻輳回避（congestion avoidance）アルゴリズムです。
輻輳回避では、輻輳を検知した時点でのcwndの半分の値をスロースタート閾値（slow start threshold、ssthresh）として設定します。そしてcwndがssthreshに達した後は、ACKを受け取るたびに増やす輻輳ウインドウの増加分を緩やかにすることで、輻輳を発生させにくくします。このときのcwndの更新式は、
cwnd = cwnd + mss / cwnd
となります。こうすることで、ウインドウサイズはRTTごとに1ずつ線形に増加していく形となり、輻輳が発生したときのウインドウサイズまで徐々に転送量を上げていくことになります。
このときの通信フローとスライディングウインドウおよびウインドウサイズの変化の様子を図3に示します。ここに示すフローは、cwnd=8で輻輳および再送が発生した場合を想定して、ssthreshが4に設定され、スロースタートからcwndが4に達した後の動作を例示しています。4つのセグメントを送信し（❶）、それらに対するACKを4つ受信するとcwndを1増やし、5つのセグメントを送信します（❷）。これと同じ要領でACKをcwndの数だけ受信した後にcwndを1ずつ増加し、少しずつデータの転送量を上げていきます（❸❹）。ウインドウサイズの変化からもわかるように、スロースタートではcwndが指数的に増加していきますが、輻輳回避段階（❶以降）では線形的であり、増加の仕方が緩やかであることがわかります。つまり、輻輳状態となったcwndに到達するまでに時間がかかるため、その分多くのデータを転送できることになります。
図3 輻輳回避
高速リカバリ
輻輳の検出時、毎回スロースタートから再開するのは、必ずしも転送効率が良いとは言えません。転送効率を上げるため、輻輳検出による再送後のcwndを小さくし過ぎないようにする方法が、高速リカバリ（fast recovery）です。
高速リカバリは、輻輳の程度が小さい場合に有効です。タイムアウトによる再送は、輻輳の程度が大きいと考えられ、スロースタートからの再開が適しています。一方、輻輳が軽度と考えられる場合の再送制御として重複ACK（duplicate ACK）の受信を契機とする手法があります。これを「高速再転送」と呼び、この場合にスロースタートから再開するのでは転送量を落とし過ぎと考えられます。そこで、高速リカバリによる、ある程度転送量を維持できるようなウインドウ制御を行います。
図4に、高速リカバリによる輻輳ウインドウの変化の様子を示します。詳細な動作フローについては高速再転送とともに説明する必要があるため、ここでは説明に留めます。t=6のときに高速再転送が実施されたとすると、cwndを半分に減少させ、同時にこの値をssthreshとして保存します。そして、cwndにさらに3セグメント加えた大きさに設定します。この3セグメントというのは、高速再転送では重複するACKを3つ受信することを契機に再送されることに基づいており、少なくとも3セグメントは正確に受信側に届いているということが考えられるためです。その後、再送セグメントが正確に受信側に到達するまでは重複ACKは送信され続けますが、これを受け取るたびにウインドウを1ずつ増やし、ウインドウ内に送出していないセグメントがあれば送信します。そのため、t=6以降はcwndは一時的に少し増加し、輻輳検出後の過度なスループットの低下を防ぐことができます。t=8において再送したセグメントに対する新しいACKが到着すると、cwndをssthreshに設定し、輻輳回避段階へ入ります。
図4 高速リカバリ
以上のように、TCPの輻輳制御アルゴリズムは、輻輳が起きない範囲でなるべく転送量を上げること、および輻輳検出後に転送量を下げ過ぎないようにすることで、データ転送効率を向上させているのです。
