クライアント要求による強制再送の導入

EŵĂdž

ZdKŵŝŶ

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

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

;ĚсEŵĂdžͿ

ŝ

ZdK

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

7&3

6XSHU YLVRU 7&3

&OLHQW 6ZLWFK 6HUYHU

WKURXJKSXW

7&3

7&3

7&3 WKHVDPHEDUULHU

V\QFKURQL]HGDSSOLFDWLRQ

WKURXJKSXW

図4.8: 統括TCP

まず，クライアント側の変更点について述べる．クライアントが，バリア同期アプリケーション のスループットの低下を検知できるようになるために，図4.8に示すような統括TCPを新たに導 入する．統括TCPは，同一のバリア同期アプリケーションに属するすべてのTCP^{コネクション} のスループットを監視する．今日のデータセンターのネットワークのRTT^は，数100^{マイクロ秒} であるため，スループットの計測は，その10RTT^分である1msecごとに行う．このように計測す ることで，パケット到着間隔の変動幅の影響を吸収させる．

統括TCPは，アイドル状態であるかどうかを判断するために，直近5msec間に計5回計測し

た1msec毎のスループットの平均値（以下，移動平均スループットと呼ぶ）を使う．もし，移動

平均スループットが，ある基準よりも小さくなった時に，統括TCPは，アイドル状態が発生した と判断して，サーバに再送要求を送信するように，未送信のSRUを持つサーバと接続している各 TCPに対して指示する．その指示を受けた各TCPは，新しく導入する再送要求オプション付き の重複ACK^{を一斉に送信する．（つまり，}SRUの送信が完了したサーバに対しては，再送要求オ プション付きACKは送信されないように実現できる．）この再送要求オプションは，単に再送要 求を示す1つのkindフィールド（すなわち，lengthは2）から構成される新しいオプションとし て実装する．クライアントが，このオプションの付いた重複ACKを送信してから，もし，統括 TCPが計測する移動平均スループットが依然として低いままだった場合，統括TCP^{は，要求オ} プション付きの重複ACKを再度送るように指示する．

クライアントが再送要求を送信した後，数ミリ秒の間は，サーバは，帯域幅を使い切るだけの十 分なパケットを送信することができない可能性がある．この理由は，後述するように，サーバは，

再送要求オプションを受信したときに，再送タイムアウトを強制的に引き起こすことで，スロー スタート閾値（ssthreshold）はその時点の輻輳ウィンドウの値の1/2になり，また，輻輳ウィンド ウの値は1MSSになるためである．通常，クライアントからの再送要求が必要となる場合を考え ると，サーバは再送タイムアウトを繰り返し発生していると想定できるため，ssthreshold^は，輻 輳ウィンドウの最小値の1/2^である1/2MSSであると考えられる．このため，輻輳ウィンドウの 成長速度は低下するため，再送要求を送信した直後のスループットは低いことが予想される．従っ て，クライアントは，移動平均スループットが低ければ，再送要求オプションを送信すると前述し たが，このようなACK送信の繰り返しを避けるために，統括TCPは，前回の再送要求オプショ ン付きACK^{を送信してから}3msecの間は，移動平均スループットを評価しないように設計する．

Ɨ Ɨ ƗƗ ƗƗ WLPH 1HWZRUN

6HUYHU6Y

$OOVHUYHUVVWDUW658WUDQVPLVVLRQV VWUHWUDQVPLVVLRQIDLOXUH

QGUHWUDQVPLVVLRQIDLOXUH

UGUHWUDQVPLVVLRQIDLOXUH

UHTXHVWHGUHWUDQVPLVVLRQ VXFFHVV

572 572 572 572 EXV\VWDWH

FRQJHVWLRQRFFXUV

LGOHVWDWH FRQJHVWLRQILQLVKHV

000000000000000

000000000000000 0000000000000000000

0000000000000000000 00000000000000000000 00000000000000000000

'DWDWUDQVPLVVLRQ

&OLHQW VXSHUYLVRU7&3

ORZHUWKURXJKSXWGHWHFWLRQ

DQGVHQGDUHWUDQVPLVVLRQUHTXHVW GDWDDUULYHV

PRQLWRULQJWKURXJKSXW

図 4.9: 再送要求オプション

次に，サーバ側の変更点について述べる．サーバが再送要求オプション付きのACK^{を受信した} ときは，上述したように，サーバは，再送タイマを強制的にタイムアウトさせる．このタイムア ウトによって，サーバは，確認応答を受け取っていない最小のシーケンス番号を持つパケットを，

即時に再送する．このとき，通常の再送タイマのタイムアウト時と同様に，指数バックオフに従っ て再送タイマに，現在のRTO^を2倍にした値をセットし，再送したパケットに対する再送タイマ をリスタートさせる．また，輻輳ウィンドウサイズを1MSS^に，ssthreshold^{を直前の輻輳ウィン} ドウサイズの半分の値に，それぞれ更新する．さらに，TCP New Reno^{が利用する}recover^変数 を更新する．一方，サーバは，このACKを使ってRTT推定値の更新や，重複ACK数の更新は 行わない．この理由は，ここで受信したACKは，単に再送要求を示すためのものであり，RTT の計測のためのACKや，順序違いのパケットが到着したことを示す重複ACKではないからであ る．なお，このようなオプションを使って再送要求を行うTCP^{のことを，本論文では}NOBTCP

（New Option Based TCP^{）と呼ぶ．}

この動作の例として，図4.9に再送要求オプションを使用したときのクライアントとサーバの動 作を示す．この例では，時刻t₀において，すべてのサーバが一斉にSRU送信を開始し，時刻t₁に おいて，ネットワークがビジー状態になる．ビジー状態が終わるまで，サーバSvは，再送を繰り 返し失敗する．時刻t₂において，ネットワークのビジー状態が終了したとする．前述したように，

統括TCPは，移動平均スループットを計測しているため，もし，その値が一定の基準値よりも小 さくなれば，統括TCPは，ネットワークがアイドル状態になったと推測して，SRU^{の送信を終} えていないすべてのサーバに対して，再送要求オプション付きのACK^{を送信する．時刻}t5にお いて，サーバSvが再送要求オプションを受信したとすると，Svは，対応する再送パケットを即時 にクライアントに送信する．このとき，ネットワークはアイドル状態にあるため，この再送は高 い確率で成功する．図4.1と比べて，この再送は，より早いタイミングで実行されていることがわ かる．

ůŝĞŶƚ ^ĞƌǀĞƌ

ϭͲϭϰϲϬ;ϭϰϲϬͿ ϭϰϲϭͲϮϵϮϬ;ϭϰϲϬͿ ϭϰϲϬ͛

ϭϰϲϭͲϮϵϮϬ;ϭϰϲϬͿ ϮϵϮϭͲϰϯϴϬ;ϭϰϲϬͿ ϰϯϴϭͲϱϴϰϬ;ϭϰϱϬͿ

ůŝĞŶƚ ^ĞƌǀĞƌ

ϭͲϭϰϲϬ;ϭϰϲϬͿ ϭϰϲϭͲϮϵϮϬ;ϭϰϲϬͿ ϭϰϱϬ͛

ϭϰϱϭ͛

ZĞƚƌĂŶƐŵŝƐƐŝŽŶ ƌĞƋƵĞƐƚ

ϭϰϲϭͲϮϵϮϬ;ϭϰϲϬͿ ϮϵϮϭͲϰϯϴϬ;ϭϰϲϬͿ ϰϯϴϭͲϱϴϯϬ;ϭϰϱϬͿ

ZdyƚŝŵĞŽƵƚ ZĞƚƌĂŶƐŵŝƐƐŝŽŶƚŝŵĞŽƵƚ

ĂĐŬŽĨĨ сϭΘZdyƚŝŵĞƚ ƌĞƐƚĂƌƚ

ƚ ƚ

EŽƌŵĂůdW <,ŽůĚŝŶŐdW

図 4.10: 保留ACKによる再送要求 4.4.2 保留ACKの導入

前節では，再送要求オプションによる再送要求の方法を提案したが，この方法を使う場合は，新 しいオプションを解釈するための処理をTCPに加える必要があった．本節では，オプションを使 わずに，ACKの操作だけでクライアントからサーバに対して再送要求を伝える方法について検討 する．

分散ファイルシステムのようなバリア同期アプリケーションでは，TCP^は，SRU^{送信の最後の} パケットを除いて，常にMSSサイズのパケットを送信することになる．この性質を考慮して，1 バイトのみを確認応答するACKを，再送要求という特別な意味を持たせることを検討する．この 時に返送する丁度1バイトを確認応答するACKは，サーバにとって有効なACKである必要があ る．すなわち，ACKの確認応答番号は，サーバが過去に送信したことがあるシーケンス番号を含 み，さらに，重複ACKを含む過去に受信した確認応答番号ではなく，新しい1^{バイトを確認応答} するものである．このACKを任意のタイミングで送信するためには，図4.10^{に示すように，ク} ライアントは，順序通りに受信したパケットの最大シーケンス番号を確認応答番号とするACK^を 常に返送するのではなく，一定バイト（図中は10バイト）を差し引いた値を確認応答番号とする ACKを返送する．クライアントが，再送要求を行うときには，保留ACKにより保留状態にある シーケンス番号について，1バイト分のACKを新たに作成して，サーバに送信する．このような ACK^{のことを保留}ACK^{と呼び，これを使う}TCP^のことをAHTCP^（ACK Holding TCP^）と 呼ぶ．

サーバは，SYNに対する確認応答を除く，丁度1^{バイトの新鮮な}ACK^{を受信したときは，ク} ライアントからの再送要求と判断して，前節の再送要求オプションを受信したときと同じように，

再送タイマを強制的にタイムアウトさせる．また，このとき，再送タイマに再設定するタイムアウ ト値や，輻輳ウィンドウサイズ，ssthreshold変数，TCP New Renoにおけるrecover変数は，そ れぞれ，通常の再送タイムアウトが発生したときと同様に更新する．また，再送要求オプション を受信したときと同様に，このACK^を使ったRTT推定値の更新は行わない．

このときに，サーバが再送するパケットは，再送要求オプションの時とは異なって，確認応答さ

ZĞĐŝǀĞĚ

ϭ ϭϰϲϬ

͍;ƌŽƉƉĞĚͿ ͍;ƌŽƉƉĞĚͿ

ϭϰϲϭ ϮϵϮϬ ϮϵϮϭ ϰϯϴϬ

ůŝĞŶƚ

^ĞƌǀĞƌ

; ƚ

Ϳ

ϭϰϲϬ

ϭϰϱϭ

hŶĂĐŬĞĚ hŶĂĐŬĞĚ ĐŬĞĚ

,ŽůĚ;ϭϬLJƚĞƐͿ

͍ hŶĂĐŬĞĚ

ĐŬĞĚ Zdy

ϮϵϮϬ

ƐŶĚͺŵĂdž

ƐŶĚͺŶdžƚ ƐŶĚͺŵĂdž

;ƌĞĐŽǀĞƌͿ ƐŶĚͺƵŶĂ

ϮϵϭϬ ĐǁŶĚ сϭ

^ĞƋƵĞŶĐĞŶƵŵďĞƌ

^ĞƌǀĞƌ

; ƚ

Ϳ

͍ hŶĂĐŬĞĚ

ĐŬĞĚ

ϮϵϭϬ

ĐŬĞĚ

,ŽůĚ;ϭϬLJƚĞƐͿ

^ĞƌǀĞƌ

; ƚ

Ϳ

図4.11: 保留ACK受信時のサーバの振舞い

れていない最小のシーケンス番号（snd una）から始まるパケットではなく，保留ACKにより確 認応答が保留されているシーケンス番号を考慮して，MSSで正規化したパケットを再送する．す なわち，サーバが再送するパケットのシーケンス番号（snd nxt）は，以下の式で求められる．

snd nxt=

⌈

snd una MSS

⌉

×MSS + 1 (4.2)

これは，再送要求を示す1バイトの新鮮なACKを受信をトリガーとした再送のときだけでなく，

3^{個目の重複}ACKを受信したときに行う高速再送や，再送タイムアウトによる再送，高速リカバ リ（部分ACKの受信）による再送のときも同様に，保留ACKによって送信保留状態のシーケン ス番号を考慮して，MSSで正規化したシーケンス番号から開始するパケットを再送する．

例えば，図4.11に示すように，サーバが3つのパケット（シーケンス番号1 ∼1460と，1461

∼ 2920，2921 ∼ 4380）をクライアントに送信して，そのうちの1つ目のパケットのみがクライ アントに到着し，残りの2つのパケットが，ネットワーク内で消失したことを考える．クライア ントは，1つ目のパケットを受け取ったときに，10バイト分のシーケンス番号を除いて確認応答 する保留ACKをサーバに返送する．時刻t1において，サーバはその保留ACK^{を受信すること} で，シーケンス番号1 ∼1450までが確認応答されて，サーバのsnd una^は1451^{になる．時刻}t2