バックオフ機能の改良

前節でみたように，FGTCPを使用したとき，かつ，サーバ数が多いときには，再送が繰り返 し発生するために，RTOが指数的に増加して，その結果，アイドル時間の長期発生によるグッド

Ϭ ϮϬϬϬ ϰϬϬϬ ϲϬϬϬ ϴϬϬϬ ϭϬϬϬϬ ϭϮϬϬϬ

Ϭ ϰϬ ϴϬ ϭϮϬ ϭϲϬ ϮϬϬ ϮϰϬ ϮϴϬ

&'dWͺϬ͘ϮŵƐ &'dWͺϭŵƐ &'dWͺϱŵƐ &'dWͺϭϬŵƐ EdW

dŚĞŶƵŵďĞƌŽĨĂĐƚŝǀĞƐĞƌǀĞƌƐ

'ŽŽĚƉƵƚ΀DďƉƐ΁

図4.4: V = 10 Gbps，S = 512 KBのときのグッドプット

Ϭ ϭϬ ϮϬ ϯϬ ϰϬ ϱϬ

Ϭ ϰϬ ϴϬ ϭϮϬ ϭϲϬ ϮϬϬ ϮϰϬ ϮϴϬ

&'dWͺϬ͘ϮŵƐ &'dWͺϭŵƐ &'dWͺϱŵƐ &'dWͺϭϬŵƐ EdW

dŚĞŶƵŵďĞƌŽĨƌĞƚƌĂŶƐŵŝƐƐŝŽŶƚŝŵĞŽƵƚƐƉĞƌĐŽŶŶĞĐƚŝŽŶ

dŚĞŶƵŵďĞƌŽĨĂĐƚŝǀĞƐĞƌǀĞƌƐ

図4.5: V = 10 Gbps^，S= 512 KBのときのコネクションごとの平均再送タイムアウト回数

Ɨ Ɨ Ɨ Ɨ Ɨ Ɨ Ɨ WLPH 1HWZRUN

D([SRQHQWLDO GHIDXOW

$OOVHUYHUVVWDUW658WUDQVPLVVLRQV VWUHWUDQVPLVVLRQIDLOXUH

QGUHWUDQVPLVVLRQIDLOXUH UGUHWUDQVPLVVLRQ

IDLOXUH WKUHWUDQVPLVVLRQ

VXFFHVV

572 572 572 572

EXV\VWDWH FRQJHVWLRQRFFXUV

LGOHVWDWH FRQJHVWLRQILQLVKHV

000000000000000

000000000000000 00000000000000000000

00000000000000000000 00000000000000000000

00000000000000000000

'DWDWUDQVPLVVLRQ

E/LQHDU

572 572 572 572

000000000000000

000000000000000 0000000000000000000

0000000000000000000

F+\EULG

572 572 572

1'PD[ 1'PD[ 572

000000000000000

000000000000000 00000000000000000000

00000000000000000000

図4.6: バックオフの改良

プットの低下が起こることを見た．本節では，データセンターのネットワークを前提に，RTOが，

過度に大きな値にならないように制限する方法を2つ提案する．

ネットワークの輻輳状態が長期化して，再送が繰り返し発生すると，指数バックオフによって，

RTOが再送の度に指数倍されるため，非常に大きな値になる．例えば，6^{回再送タイムアウトが} 連続した場合，7回目の再送タイムアウトに必要な時間は，RTO^の64^（= 2^{6）倍になる．この方} 式は，インターネットのように，通信先までの経路が特定できないネットワークでは，パケット を送信してから対応するACKを受信するまでの時間が大きく変動する可能性があるため，有効 に機能する．一方で，データセンターのネットワークのように，通信先までの経路が特定できる ネットワークでは，RTTの変動が少ないため，再送時に設定する再送タイムアウトの値は，イン ターネットのときよりも変動幅を小さく設定することにより，より適切なタイミングで再送が行 える可能性がある．

この考え方に基づいて，データセンター内で使用するTCP^のRTOのバックオフ方法の改良に ついて検討を進める．まず，バックオフによるRTOの増加幅をゆるやかにするために，タイムア ウトの値を線形的に増加させるような改良が考えられる．すなわち，i回目の再送タイムアウト時 間には，i×RTOを設定する方法である．この方法使ったTCPのことを，線形バックオフTCP

（LNRTCP: Linear backoff TCP）と呼ぶ．

次に，2つ目の方法について述べる．上述したLNRTCPを単純に使おうとすると，図4.6^の (b)^{に例示するように，}3回目の再送タイムアウト時間は，指数バックオフ（図中(a)^{）よりも短}

い3×RTO^{が設定がされる．}RTOが小さい値になると，再送がより早いタイミングで行われるた め，ネットワークのアイドル状態を早く解消できる可能性があるが，一方で，輻輳状態が続いて いる場合にも関わらず，再送による追加のパケットをネットワークに流入させることで，輻輳が さらに悪化する可能性も増える．そのため，最初は指数バックオフによりRTOを増加させて，ど こかのタイミングで線形バックオフに切り替える方法を検討する．そこで，再送発生時にセット するRTOを計算するときに，指数バックオフを利用するか，または，線形バックオフを利用する か，判定する基準を導入する．

バックオフの計算方法の使い分けをするための検討にあたって，データセンターのネットワー クは，通常，冗長化がなされているため，厳密には通信経路を固定化することはできないが，サー バからクライアントまでのスイッチの最大段数は，ほぼ特定できると仮定する．また，各スイッチ の最大バッファ容量は，設計書や仕様書などから事前に知ることができると想定する．この2^つ の前提のもとでは，サーバがパケットを送信してから，対応するACKを受信するまでの時間の最 大値（NDmax）は，以下のように求めることができる．

NDmax= Bmax×Hmax

V + BaseRTT (4.1)

ただし，Bmaxはデータセンターのネットワークにあるスイッチの最大ポートバッファ容量で，Hmax

はサーバからクライアントまでに経由するスイッチの最大段数を示す．また，V ^{は帯域幅を示す．}

帯域幅が異なるリンクが混在する場合は，その中で最も小さい帯域幅を計算に使う．なお，クラ イアントは，サーバからパケットを受信すると，最速でACKを返送するものとし，途中のスイッ チは，伝送のための計算時間は無視できるほど小さいものと仮定する．

上述したように，データセンターのネットワークでは，ネットワーク構成の概略や利用するス イッチの性能の情報があるため，RTTの最大値を事前に知ることができる．すなわち，仮に，す べてのスイッチのポートバッファが満杯だったとしても，サーバがパケットを送信してから，対応 するACK^{を受け取るまでに，}NDmaxよりも多くかかることはない．従って，この時間待っても ACKが返送されなければ，そのパケットは消失している可能性が高いとみなせる．そこで，バッ クオフの計算方法を使い分ける基準として，前回再送タイマに設定したRTOがこの値を超える ときは，増加分dがND_maxである線形バックオフを利用することとする．この方式のバックオフ のことをハイブリッドバックオフと呼び，このバックオフを使ったTCPのことを，ハイブリッド バックオフTCP^（HYBTCP: Hybrid backoff TCP^{）と呼ぶ．}

図4.6^の(c)に，ハイブリッドバックオフTCPにおける指数バックオフと線形バックオフを，

NDmaxを閾値として使い分ける例を示す．ここではNDmax = 4 RTO^{と想定している．}RTO^が この値を超えているときに，再送タイムアウトが発生すると，指数バックオフではなく，ND_max を基準にして，ND_maxずつ線形に増加させる．すなわち，この方法を使った時のRTOの変化を 図4.7に示す．

このように，RTO^がNDmaxに対して小さいときには，標準のTCPと同様に，指数バックオフ により指数的にRTO^{を増加させる．他方，}RTO^がNDmaxに対して大きいときは，そのRTO^が データセンターのネットワークの最大遅延時間に対して十分に大きいと判断して，線形バックオ フに切り替える．そのため，線形バックオフを単純に使用するときよりも，アグレッシブの度合 いは小さくなる．これにより，輻輳を悪化させることなく，インキャストの原因であるアイドル 状態の発現期間を小さくすることが期待できる．

EŵĂdž

ZdKŵŝŶ

dŚĞŶƵŵďĞƌŽĨĐŽŶƚŝŶƵŽƵƐƌĞƚƌĂŶƐŵŝƐƐŝŽŶƚŝŵĞŽƵƚ džƉŽŶĞŶƚŝĂůďĂĐŬŽĨĨ

>ŝŶĞĂƌďĂĐŬŽĨĨ

;ĚсEŵĂdžͿ

ŝ

ZdK

図4.7: 再送回数とハイブリッドバックオフTCP^のRTO^の関係