QUICのBBR(Bottleneck Bandwidth and RTprop) congestion control

#ひとことで

進捗ありました(ㅍ_ㅍ)

BBR(Bottleneck Bandwidth and RTprop)とは

Googleが公開したTCPの輻輳制御のアルゴリズムです。

next LTS kernelであるLinux 4.9へパッチを投げて取り込まれています。

linux 4.9 patch:
https://patchwork.ozlabs.org/patch/671069/

BBRの実装を読んだ感想は私のBlogで多少詳しく書いています。
http://nothingcosmos.blog52.fc2.com/blog-entry-187.html

BBRの特徴

特徴や性能に関してACM QUEUEで紹介されています。

内容を予約すると、、

loss-basedは右側の変化点で輻輳を検知するため、途中経路のBufferを埋めてしまいBufferBloatなどの問題を引き起こしますが、
BBRは左側の変化点に着目して輻輳を検知しようとし、途中経路のBufferを埋めないないように考慮します。

またGoogle B4 WANではCUBICと比較して、BBRは2-25倍スループットが出たとのことで、
大変興味深い結果になっております。

全て読むにはこのリンクをクリック！(ΦωΦ)
http://queue.acm.org/detail.cfm?id=3022184

QUICのBBR

BBRの実装はQUICにも取り込まれており、
NewBBRという名前で実装が追加されています。
https://chromium.googlesource.com/chromium/src/+/6e6381c2d2b079e34b33bf60534df7cf1c2cc5e3

サラッと内容を参照するとLinux TCPの実装とほぼ同じアルゴリズムとなっていたようですが、
実際にproto-quicを使ってどんな感じが測定してみました。

性能測定

低帯域のネットワークと広帯域のネットワークにおいて、
Bandwidthの測定値とRTPropの測定値がどのように変化するのか見てみます。
また、BBRとQUBICでそれぞれ測定し比較してみたいと思います。

proto-quicは12/17時点の最新を利用します。

  commit 6f545c4011cd25621c3d2581faa9bf7312ab548a
  Author: Cherie Shi <[e-mail]>
  Date:   Mon Dec 12 21:01:47 2016 -0800
  Updating to 57.0.2950.0 (#21)

仮説

バッファに負荷を与えるような場面を想定すると、
RTPropをcubicとbbrで比較した場合、
cubicはある閾値まで線形でRTPropが増加して行きあとある敷地を超えるとがくんと下がるような挙動を繰り返すと予測します。
逆にbbrはRTPropが線形に増加せず、多少上下しつつもRTPropの下限付近に張り付くと予測します。

バッファに負荷を与えるために、
1GBのファイルをQUICでアップロード/ダウンロードを行えば、
上位のような挙動が観察できるはずです。

クライアントの環境

(1) 自宅PC
Windows10上でVirtualBox上のUbuntu16
4CPUの8GBメモリ
ネットワークはブリッジアダプター
ソフトバンクのネットワークで100Mbps

(2) AWSのマシン
AWS Singaporeリージョンに立てたec2 M4 large

サーバの環境

(3) AWS Tokyoリージョンに立てたec2 M4 large

#測定結果

自宅からAWS TokyoまでのRTTは6msec程度です。※pingで計測

縦軸がRTT(usec)
横軸はサンプリング回数で、だいたい10,000回行っています。

CUBIC (RTProp(μsec)/sample)

BBR(RTProp(μsec)/sample)

BBRのほうは最初に3回爆発！！！してますけど、
爆発の後はおとなしい感じで、6ms～10msくらいで落ち着いてていい感じです。
残念！ その後はbbrとcubicで大して変わらない(ㅍ_ㅍ)

この測定結果はおかしい！！！と思ってログを追加してみた結果、
BBRにおいてModeの遷移がStartupとProbeRTTの2モード間でしか遷移していませんでした。。
Startupモードだと、BBRとCUBICで差なんか出ないよね、、と思いつつ、
なんでStartupからDrainに遷移しないんだよ、とproto-quicのソースコードを調査してみましたが、
StartupからDrainに遷移させない見えないcapが存在するらしく、
まだよくわかってないです、、ごめんなさい orz

追試！

原因を追究したところ、configの設定方法に問題があり、
サーバサイドはbbr, クライアントサイドはcubicで測定していたようですので、
双方cubic, 双方bbrで再測定してみました。
10,000件のサンプリングを、さらに200件ごとにサンプリングしています。

追試！のバージョンは12/19版に手を入れて測定しています。

commit 661577d951ac9b0293a269bc4d71d9d105570129
Merge: 6f545c4 1a677ea
Author: Ryan Hamilton <[e-mail]>
Date:   Mon Dec 19 16:08:21 2016 -0800

    Merge pull request #23 from google/merge-to-57.0.2957.0v2
    
    Updating to 57.0.2957.0

まずはCUBICの結果から

CUBIC(RTProp(μsec)/sample)

縦軸はRTT,横軸はサンプリング数、青線がRTT,赤線が平均偏差です。
平均してRTTは20.5msec, 平均偏差は597μsecです。
経路的に25msecくらいが閾値になるのか、そのくらいのRTTが壁になっています。
スループットは70Mbps~67Mbpsくらいでしたが、一貫して70Mbps出ていました。

BBR(RTProp(μsec)/sample)

縦軸はRTT,横軸はサンプリング数、青線がRTT,赤線が平均偏差です。
平均してRTTは8.8msec, 平均偏差は533μsecです。
BBRもちゃんとSTARTUP-DRAIN-PROBE_BB-PROBE_RTTと遷移していました。
BBRは予告通りRTTが抑えめになりますし、CUBICと比較すると差がはっきりとわかります。
ping 6msecくらいなので、ほぼRTTの下限に張り付いていると言えるのではないでしょうか。

しかしスループットの面では68Mbps-67Mbps-61Mbpsくらいを行ったり来たりでしたので、
CUBICのほうがやはり高いです。

今回は自宅からAWSに1GBのアップロード1本だけで測定していますので、
複数本張った場合などのスループットの変化や帯域の譲り具合なども検証してみたいです。※宿題

##追試!2

tokyo-singapore間においても簡単に測定してみましたが、
cubicは一貫して50Mbpsくらいで、RTTも70ms安定、
bbrは25Mbpsくらいで、RTTも70~100くらいまでブレブレでした。
bbrはRTTを測定しつつも平滑化しますが、ある程度以上のRTTがある遠距離を苦手とするのかもしれません。
勘違いしてたので、再測定です。

追試!2のバージョンは12/19版に手を入れて測定しています。

commit 661577d951ac9b0293a269bc4d71d9d105570129
Merge: 6f545c4 1a677ea
Author: Ryan Hamilton <[e-mail]>
Date:   Mon Dec 19 16:08:21 2016 -0800

    Merge pull request #23 from google/merge-to-57.0.2957.0v2
    
    Updating to 57.0.2957.0

測定は、SingaporeからTokyoへ1GBのアップロードのみ行いました。
Singaporeからtokyoへpingで67.9msecです。

BBR(RTProp(μsec)/sample)

BBRとCUBICでそれぞれ比較してみましたが、どちらも似たようなグラフになったのでCUBICは省略です。

BBRは安定して68msec程度のRTPropを記録し、平均で68.9msecでした。0.9上振れているのは、BBRのグラフにおいてところどころ見られるRTPropが爆発するポイントがあるためです。
ModeやCycleと関係があるかもしれませんが、原因は未調査です。

CUBICは安定して71.1msec程度のRTPropを記録し、平均で71.14msecでした。
またCUBICのほうがRTPropのバラつきが少なかったです。

またSingapore-tokyo間のuploadにおけるスループットも比較してみましたが、
BBRのほうが良好でした。これはBBR同時2-3本、CUBIC同時2-3本でも同様の結果です。
1GBをuploadはBBRが260Mbps程度,CUBICが240Mbps程度です。
Tokyo側からiftopで観察する限りにおいては、
BBR側が400-380-360mbpsなのに対して、CUBIC側が330-300-280mbpsです。

スループットと比較するとiftopのBBRが上振れ過ぎな気がしますし、
BBRのSTARTUPモード中でQUIC_BUG_IFに突っ込んでいたので、バグってるかもしれません。。

#まとめ

私が測定した環境において、BBRはCUBICと比較しRTPropの増加を抑え良好なパフォーマンスを示しました。
※QUICのBBRはまだ実験段階だけど。。