基本から学ぶ TCPと輻輳制御 ……押さえておきたい輻輳制御アルゴリズム

第4回 BBRの出現

この記事を読むのに必要な時間:およそ 2.5 分

バッファサイズ増加とバッファ遅延増大

近年,ルータやスイッチ等のネットワーク機器に搭載されるバッファメモリのサイズが増加してきました。この主な要因としては,メモリの低価格化が進んだことが挙げられます。またネットワーク機器に限らず,メモリサイズは大きい方が良い,という通念が主流となってきたことも大きく影響しているでしょう。ネットワーク機器のバッファサイズが大きくなることで,パケット廃棄が起こりにくくなるという利点があります図1)⁠すなわち,ネットワーク機器に一度に大量のパケットが到着した場合にも,それらのパケットをメモリに蓄積しておき,順番に送出することができるようになります。

図1 バッファサイズとパケットロス

図1 バッファサイズとパケットロス

しかしながら,バッファサイズが大きくなることによる弊害もあり,それがバッファ遅延の増大です。バッファ遅延の増大によって生じる遅延の増加現象はバッファブロートBufferbloatと呼ばれ,2009年前後から広く問題として認識されてきました。特にTCPでは,新たなデータを送出するためには受信側ノードからのACKを受け取る必要があります。そのため,図2に示すように,バッファ遅延の増大によってデータ到着までの遅延が伸びることで,ACKの到着も遅れ,従ってデータ送信間隔が伸びスループットが低下することになります。

図2 RTTとスループットの関係

図2 RTTとスループットの関係

そして,特にLoss-based輻輳制御アルゴリズムでは,パケット廃棄を輻輳の指標とします。そのためパケット廃棄が発生するまでは,輻輳ウインドウサイズを増加させていきます。近年はデータ伝送における信頼性(誤りの少なさ)が向上したことから,パケット廃棄の主な要因はバッファあふれによるものです。すなわちバッファあふれが発生するまでデータ送信量をどんどん増加させていき,送出されたパケットが各ネットワーク機器のバッファを埋め尽くすことによる影響が,RTTの増大として表れてきます。つまりTCPフロー自身がバッファブロートを引き起こす原因となるとともに,その悪影響が自らに及んでしまう,といった状況になるのです。タイムアウトによるデータ再送なども考慮すると,Loss-based輻輳制御アルゴリズムはバッファ遅延増大を悪化させやすい傾向が非常に強いと言えます。

従来のDelay-based輻輳制御の特徴と課題

TCPの輻輳制御アルゴリズムの中で,RTTを輻輳の指標として用いるのがDelay-based輻輳制御です。RTTが大きくなるほど輻輳状態が悪化していると判断して輻輳ウインドウサイズを調整します。RTTは,往復のend-to-end遅延の合計として計算されます。end-to-end遅延の構成要素図3として,経路上のネットワーク機器における処理遅延と,各ノードでのバッファメモリ上での転送待ち時間であるキューイング遅延,ノード間リンクの信号伝搬に要する物理的な伝搬遅延があります。この中で,伝搬遅延や処理遅延はほぼ一定(厳密には装置や条件によって少し揺らぎます)です。それに対してキューイング遅延は,メモリ上にどれだけデータが蓄積されているかによって大きく変動します。出力リンクからのデータ転送速度は一定なので,この速度に対して単位時間あたりの入力データ量が大きくなれば,出力しきれないデータがメモリ上にどんどん蓄積されてしまいます。つまり,Delay-based輻輳制御では以上の性質を利用して,RTT増大の原因が経路上におけるキューイング遅延の増大によるものであると解釈します。

図3 end-to-end遅延の構成要素

図3 end-to-end遅延の構成要素

有名なDelay-based輻輳制御アルゴリズムとして,Vegasがあります。Vegasは,バッファ遅延が少し伸びてきたところで輻輳ウィンドウサイズの増加を抑え,それによって輻輳の悪化を防ぎ安定したスループットを得ることができます。ただし,確かに理想的な環境ではパケット廃棄が発生せず,安定して低遅延性と高いスループットを実現可能なのですが,特にインターネットのような不特定多数の主体が関わる環境においては,理想的でない環境が非常に多く含まれてしまいます。具体的には,まずVegasはアグレッシブ性が非常に低く,RTTが増大するとすぐに輻輳ウインドウサイズを減少させるため,Loss-based輻輳制御に追い出されてしまう,という課題があります。そもそも従来から一般的に利用されてきた手法がLoss-based輻輳制御であるNewRenoであり,その代替がCUBICである状況を考えると,Vegasを実際にインターネットで利用するのは難しかった,ということが分かります。

BBRの出現

BBRBottleneck Bandwidth and Round-trip propagation timeは,Google社が2016年9月に発表して以降,Linuxカーネル4.9以降で利用可能となり,Google Cloud PlatformGCP等でも用いられるなど,その利用が広がり注目を集めています。またGoogleではYouTube等のサービスでもBBRを利用し始めており,結果として高いスループットおよび50%以上のRTT削減を達成したとの報告があります。

BBRの基本的な考え方は,従来主流だったLoss-based輻輳制御におけるパケットロスを契機とした輻輳検知では遅すぎる,というものです。その代わりに,パケットがバッファに蓄積され始める直前,つまりネットワークの帯域はフルに活用しつつ,バッファ遅延を発生させない,という状態を理想的な状況とします。ただし,経路上のネットワーク機器の状態を直接知る術はないため,スループットとRTTを常にモニタリングし,データ送出量とRTTの関係を把握しながらデータ送信速度を調節することで,ネットワークが処理可能な範囲内での最大スループットを出すことを目指します。

BBRでは,RTpropround-trip propagation timeとBtlBwbottleneck bandwidthという2つの指標を用いて輻輳ウインドウサイズを調節します。RTpropとはRTTのことであり,ACKを用いて計測した値です。BtlBwとはボトルネックリンク帯域のことであり,これに着目する理由は,TCPフローが転送される際にいくつのリンクを通っていたとしても,そのスループットを決定付けるのはボトルネックリンクにおける転送速度だからです。BBRについてよく理解するために,図4を用います。

図4 送信データ量とスループット,RTTの関係

図4 送信データ量とスループット,RTTの関係

この図では,横軸はinflightと呼ばれるネットワーク上に存在する送信中データ量であり,縦軸は上側のグラフではRTT,下側のグラフではデータ送信量となっています。全くデータを送信していない状態から徐々にinflightの量を増やしていくと,最初のうちはデータ送信量がそれに応じて上昇していき,RTTには変化がありません。これは単純に,空いているネットワーク上をパケットが待ち時間なしに転送されていくことを表しています。そして,inflightが一定の値超過すると,データ送信量はそれ以上増えなくなります。これはネットワーク上のいずれかのリンクが輻輳状態にあり,これがボトルネックリンクとなり,TCPのスループットがこのボトルネックリンク帯域に律速される,ということを意味します。inflightを増加させても,データ送信量はこのときのBtlBwを超えることはないのですが,その一方でRTTは増加していきます。これはボトルネックリンクのバッファにパケットが蓄積していき,キューイング遅延が増えていくことを示します。そして,inflightが大きくなり過ぎれば,バッファサイズを超過してパケット廃棄が発生します。

上記の説明の中で,CUBIC-TCP等のLoss-based輻輳制御による輻輳が始まるのは,inflightが大きくなりバッファサイズを超過してパケット廃棄が発生したときです。もしバッファサイズが大きく,データ送信量がBtlBwに達してからパケット廃棄が発生するまでに時間がかかるようなときには特に,この方法では効率が低下してしまうことが分かります。データ送信量がBtlBwに達した時点で,これ以上スループットが上がることはないため,それ以上にinflightを増大させることは,いたずらにバッファ量を増加させることにしかならないためです。そこでBBRが目指すのが,inflight = BtlBw × RTpropとなる状態であり,この値をBDPbandwidth-delay productと呼びます。このとき,データ送信量がちょうど閾値であるBtlBwに達する計算となるのです。

BBRは,多くの場合において適切な輻輳制御が可能であることが確認されています。ただし,BBRはまだ比較的新しい輻輳制御アルゴリズムであるため,今後様々な検証や改良が加えられていくと考えられます。

著者プロフィール

中山悠(なかやまゆう)

2006年東京大学農学部卒業,2008年東京大学大学院新領域創成科学研究科自然環境学専攻修了,同年日本電信電話株式会社入社。2018年東京大学大学院情報理工学系研究科電子情報学専攻博士課程修了。博士(情報理工学)。現在,東京農工大学工学研究院・准教授。モバイルコンピューティング,低遅延ネットワーク,IoT等の研究に取り組む。平成29年度東京大学大学院情報理工学系研究科長賞等。