ロングファットパイプにおけるReno/NewRenoの課題

インターネットの普及に伴って日常的にTCPが利用されるようになって以来、輻輳制御アルゴリズムとしてはReno/NewRenoが標準的に用いられてきました。これらのアルゴリズムは代表的なLoss-basedアルゴリズムであり、提案された当時のネットワーク環境では有効に機能していたのですが、時が過ぎ、技術の進展によるネットワーク環境の変化とともに、当初は思いもよらなかったような課題が顕在化してきました。

すなわち、転送レートの高速化やクラウドサービスの普及などにより、ロングファットパイプ（図1）と呼ばれる広帯域・高遅延環境が一般化してきました。このような環境においては、Reno/NewRenoでは高速リカバリによるスループット回復に要する時間が長くなってしまい、広帯域を十分に活用できないのです。

これは、輻輳ウィンドウサイズの増加幅がリンク速度に対して遅過ぎる、という点に起因します。図2に示すように、輻輳回避フェーズにおける高速リカバリによるスループット回復に要する時間は、リンク速度が大きくなるほど長くなるため、輻輳ウィンドウサイズが相対的に小さい時間が長くなってしまいます。

ロングファットパイプ向け輻輳制御アルゴリズムの開発

この課題に対して、HighSpeed TCPやScalable TCPといったロングファットパイプ向けの輻輳制御アルゴリズムがいくつか提案されました。これらのアルゴリズムでは、高速リカバリ時の輻輳ウインドウサイズ増加の高速化を図ることで、輻輳ウインドウサイズを大きく保つことが可能でした。Loss-based輻輳制御は基本的にパケットロスが発生するまでは徐々に輻輳ウィンドウサイズを増加させ、パケットロスが発生すると大きくを減少させる仕組み（図3、AIMD：Additive-Increase/Multiplicative-Decreaseと呼ばれます）で動作しますが、この増加速度を上げ、減少幅を小さくすることで、上記の特性を実現しています。

ただし、輻輳ウインドウサイズを大きく保とうとする傾向が強すぎて（＝アグレッシブ過ぎて⁠）⁠、Reno/NewRenoとの親和性が低いという課題がありました。つまり、HighSpeed TCPやScalable TCPが帯域を独占してしまうため、Reno/NewRenoと併用することができませんでした。インターネットでは不特定多数の人々／モノによる通信データが転送されるため、このようなアグレッシブ性の高すぎるアルゴリズムは適していません。

また、もう一つの観点として、RTT公平性が低いという課題もありました。RTT公平性とは、RTTが大きく異なるフロー間でのスループットの公平性を指す概念です。つまりHighSpeed TCPやScalable TCPでは、RTTが異なるフローがボトルネックリンクを共有した際に、RTTが小さいフローがRTTが大きいフローを追い出し、ほとんど通信できなくしてしまうという問題がありました。

BIC-TCP

BIC-TCP（Binary Increase Congestion Control TCP）は、2004年に発表された後、Linux2.6.8から2.6.18まで、つまりCUBIC-TCPに置き換わるまで標準搭載されていたアルゴリズムです。BIC-TCPも基本的にはロングファットパイプへの適用を前提に開発されたアルゴリズムであり、安定性とスケーラビリティに優れます。また、先ほど述べた既存アルゴリズムとの親和性にも配慮されています。そしてBIC-TCPが開発された最大の目的が、RTT公平性の改善です。

BIC-TCPにおける輻輳ウインドウサイズ増加イメージを図4に示します。

BIC-TCPでは、Additive increaseとBinary searchという2つのフェーズによって輻輳ウインドウサイズを増加させます。直前にパケット廃棄が発生した時点の輻輳ウインドウサイズ（W_max）に対する、現在の輻輳ウインドウサイズの大きさに応じてフェーズを切り替えます。すなわち、輻輳ウインドウサイズが小さいときには、Additive increaseにより輻輳ウインドウサイズを急速に増加させることで、スケーラビリティとRTT公平性を高めます。そして輻輳ウインドウサイズが大きくなってからは、Binary searchにより徐々に輻輳ウインドウサイズを増加させ、過剰なパケット廃棄を起こさないようにします。また、輻輳ウインドウサイズがW_maxを超えると、Max probingと呼ばれるフェーズとなり、輻輳ウインドウサイズ増加関数がW_maxとなる点に対して対称となるように輻輳ウインドウサイズを増加させることで、次のパケット廃棄を探索します。

ただし、BIC-TCPにもいくつかの課題がありました。すなわち、狭帯域であったり低遅延なネットワーク環境において帯域幅を不当に消費してしまうという点や、そして上記のような複雑なフェーズ制御により解析が困難であり、性能の予測やネットワークの設計が困難である点です。

CUBIC-TCPの登場

CUBIC-TCPは、Linux2.6.19以降で標準搭載されている輻輳制御アルゴリズムであり、現在主流となっているアルゴリズムの一つであると言えます。CUBIC-TCPは、BIC-TCPの改良バージョンという位置づけであり、BIC-TCPの複雑な輻輳ウインドウサイズ制御手法を大幅に簡略化したものです。すなわち、図4に示されているBIC-TCPにおける輻輳ウインドウサイズ増加関数を、三次関数（Cubic function）で置き換えることで、フェーズ切り替えなどを省略し、シンプル化しています。

CUBIC-TCPにおける輻輳ウインドウサイズ増加関数を図5に示します。

これを見ると、BIC-TCPの輻輳ウインドウサイズ増加の様子と非常によく似ていることが分かります。これはつまり、高速リカバリ開始からの経過時間を変数とした三次関数を用いることで、BIC-TCPの複雑な輻輳ウインドウサイズ制御を上手く近似できている、ということを表しています。結果として、輻輳ウインドウサイズの増加量が二つの連続した輻輳イベント間の時間間隔のみで表される、という点が大きな特徴として挙げられます。これはつまり、輻輳ウインドウサイズ増加速度がRTTに依存しない、ということを意味し、RTT公平性の向上に寄与します。また、RTTが小さい場合には輻輳ウインドウサイズ増加量を抑えるように設計されているため、既存TCPとの親和性が高いという長所があります。また、RTTが小さい場合には輻輳ウインドウサイズ増加量を抑えるように設計されているため、既存TCPとの親和性が高いという長所もあります。CUBIC-TCPは、これまでのLoss-based輻輳制御アルゴリズムの集大成とも言えます。