自律分散協調システム論 第13回「TCPと輻輳制御/QoS制御」 中村　修 osamu@sfc.wide.ad.jp

TCPと輻輳制御 輻輳制御の重要性 輻輳制御の困難さ TCPによる輻輳制御

輻輳制御の重要性 (1/2) 輻輳は悪化していく傾向がある 三次災害 玉突き事故 二次災害 輻輳発生

輻輳制御の重要性 (2/2) ネットワークに自律的な輻輳回復機能がない エンドノードが輻輳を回避する必要がある ネットワークはできるだけ仕事をしない エンドノードが輻輳を回避する必要がある エンドノードは故意に輻輳を起こせる DoSアタック

輻輳制御技術の大まかな歴史 初期のインターネット:輻輳制御技術なし 1980年初 輻輳崩壊の発生が指摘される 1980年初 輻輳崩壊の発生が指摘される 1980年後半 エンドノード主体による輻輳制御技術の出現 1990年後半 中継ノード主体による輻輳制御技術の出現 現在 広帯域・低遅延要求アプリケーションの台頭 インターネット速度記録（TCP高速化技術）

輻輳制御の困難さ (1/2) エンドノードはネットワークの状態が分からない IPネットワーク 自分で推測してネットワークに送出するだけ パケットを多く出すのか？ パケットを少なく出すのか？ ネットワークは教えてくれない

輻輳制御の困難さ (2/2) なぜインターネットの状態は分かりにくい？ IPの特徴 ネットワークの許容量が不明 ネットワークの混雑度が不明 様々な通信媒体の性質を抽象化 上位プロトコルから通信媒体の性質が見えにくい 中継システムの簡素化 ネットワークの許容量が不明 ネットワークの混雑度が不明

アプリケーションとトラフィックパターン TCP UDP それぞれが異なるトラフィックパターンを有する インタラクティブデータフロー パケットを直ちに送出 アプリケーション例：SSH, Telnet などコンソールアプリケーション バルクデータフロー フロー制御によってパケットを送出 アプリケーション例：http, ftp, メール など UDP フロー制御・輻輳制御を行わない アプリケーション例：ストリーミング, VoIP など それぞれが異なるトラフィックパターンを有する

ポート番号からサービス 特定がしにくい時代 アプリケーショントレンドの推移 ポート番号からサービス 特定がしにくい時代 P2P登場 WWW全盛 出典: WIDE報告書(1994-1999) 2000-2005はdaily sampling

15年前のアプリケーションモデル サーバ・クライアントモデル 情報(データ)のありか 情報(データ)の集まり方 サービスを提供する側と受ける側に役割を分担 情報(データ)は「提供する側」に存在 情報(データ)のありか 情報(データ)が格納されているサーバは「何らかの方法」で探し出す archie プログラム サーバ数が多くない上、有名なサーバには様々な種類の情報(データ)が大量に存在 情報(データ)の集まり方 情報(データ)が一箇所に集まるので、利用者も一箇所に集中してアクセスする 利用者 巨大なサーバ：　A インターネット クライアント ドキュメントファイル サーバAから ソフトウェアを ダウンロードしよう サーバAから ドキュメントを ダウンロードしよう ソフトウェアファイル

10年～5年前のアプリケーションモデル サーバ・クライアントモデル 情報の分散化 情報(データ)のありか： 情報(データ)の集まり方 「置き場所」としてのサーバは変化せず 能動的なクライアントも変化せず 情報の分散化 情報(データ)は、「リンク」が含むようになり、分散したサーバ間で情報が有機的に結びつけられるようになった 情報提供者はリンクを意識して情報(データ)を作成 情報利用者はリンクを辿り新たな情報(データ)を取得 情報(データ)のありか： 情報(データ)が格納されているサーバは「何らかの方法」で探す cf. 検索エンジン、ディレクトリサービス サーバの数が多く、大量の情報(データ)が分散して存在 情報(データ)の集まり方 インターネット中に分散して存在するが、利用者の増加に伴い人気のある情報(データ)を持つサーバにアクセスは集中 インターネット Webサーバ リンク アドレスを指定

最近のアプリケーションモデル P2Pモデル 情報(データ)単位の分散化から、分割した情報(データ)の分散化 情報(データ)のありか あらかじめ役割を決めない (サーバ・クライアントの両方の役割を担う) 対等な関係 情報(データ)単位の分散化から、分割した情報(データ)の分散化 ファイル単位のやり取りから、ファイルの分割を前提とした断片単位のやり取りへ 情報(データ)のありか 断片化した情報(データ)はネットワーク上の任意のホストに存在 情報理論を応用した検索手法(分散ハッシュ etc…) P2Pのピアになるホストの数だけ分散する可能性がある 情報(データ)の集まり方 完全な情報(データ)は、それをリクエストした人のところに存在 ネットワーク上には、断片化されたもの、完全なもの様々な形で存在 ファイルA ファイルの断片化(6分割の例)

メディア通信と遅延 デッドライン バッファ 再生を行うために間に合わせなければならないタイミング これに遅れると映像や音声が乱れる パケットロスや遅延などでデッドラインオーバーが頻繁に起こらないようにデータを一時的に蓄積

TCPによる インターネット最高速度 Interne2 Land Speed Record 東京大学、WIDEプロジェクト、JGN2(NICT)、NTTコミュニケーションズ などによる 2006年12月30日 30000km(実際には32372km)のネットワーク 7.67Gbpsのデータ転送速度 230100 terabit-meters per second (Tb-m/s) 2006年12月31日 同一ネットワーク 9.08Gbpsのデータ転送速度 272400 terabit-meters per second (Tb-m/s)

TCPにおけるフロー制御

フローコントロール ② ③ ① もちょっとゆっくり 送って。 送信者 受信者 もちょっとゆっくり 送るか。 キュー(バッファ) 早すぎてバッファがあふれる

フローコントロール ② もっとはやく 送って。 送信者 受信者 キュー(バッファ) ③ じゃはやくおくるか ① 遅いから余裕があるな

ウィンドウ制御 ウィンドウ広告 ＝ 受信バッファ残量 ウィンドウ更新 ACKを待たずに、複数セグメントを転送 ACKセグメントによる ウィンドウ広告　＝　受信バッファ残量 ウィンドウ更新 ACKセグメントによる ACKを待たずに、複数セグメントを転送 転送効率の向上

スライディングウィンドウ 1 2 3 4 5 6 7 8 直ちに 転送可能 広告 ウィンドウ

スライディングウィンドウ 転送されたが 確認応答されていない 1 2 3 4 5 6 7 8 広告 ウィンドウ 直ちに 転送可能

スライディングウィンドウ 転送されて 確認応答済み 1 2 3 4 5 6 7 8 転送されたが 確認応答されていない 直ちに 転送可能

スライディングウィンドウ 転送されて 確認応答済み 8 1 7 2 転送されたが 確認応答されていない 6 3 新たに広告された ウィンドウ 4 5 6 7 8 転送されたが 確認応答されていない 新たに広告された ウィンドウ 直ちに 転送可能

TCPにおける輻輳制御

TCPの輻輳制御機能 ② ① もちょっとゆっくり 送ろう。 送信者 受信者 輻輳 受信者からしばらく応答がない 輻輳が発生してパケットが届いて なさそうだ

輻輳制御の重要性 輻輳は悪化していく傾向がある 輻輳発生 二次災害 玉突き事故 なんらかの対処をしなければ 悪化する一方　（輻輳崩壊）

TCPの輻輳制御アルゴリズム 非常に多くのアルゴリズムが存在 代表的な例 OSによって実装されているアルゴリズムがことなることも TCP Tahoe スロースタートアルゴリズム，輻輳回避アルゴリズム，高速再転送アルゴリズム TCP Reno (TCP NewReno) 高速再転送アルゴリズム TCP Vegas RTTをベースとしたウィンドウサイズの調整 OSによって実装されているアルゴリズムがことなることも

TCPの輻輳制御アルゴリズム（時代別） 1988年頃 1990年頃 1996年頃 Tahoe Reno NewReno スロースタート、輻輳回避アルゴリズムの採用 高速再転送アルゴリズムの採用 1990年頃 Reno 高速リカバリ・アルゴリズムの採用 1996年頃 NewReno 高速リカバリ・アルゴリズムの修正

Linux Kernel の持つ アルゴリズム (Kernel 2. 6 Linux Kernel の持つ アルゴリズム (Kernel 2.6.18の例, /usr/src/linux/net/ipv4/tcp_*.c) Binary Increase Congestion control for TCP (BICTCP) Lison-Xu, Kahaled Harfoush, and Injong Rhee. TCP Reno / TCP NewReno BSD系OSのデフォルト Binary Increase Congestion control for TCP v2.0 (TCP CUBIC) Injong Rhee, Lisong Xu. High Speed TCP Sally Floyd. H-TCP R.N.Shorten, D.J.Leith. TCP HYBLA C.Caini, R.Firrincieli. TCP Low Priority (TCP-LP) Scalable TCP Tom Kelly TCP Vegas Lawrence S. Brakmo and Larry L. Peterson. TCP Veno C. P. Fu, S. C. Liew. TCP Westwood+: end-to-end bandwidth estimation for TCP Angelo Dell'Aera. Linuxにおけるデフォルトアルゴリズム （変更可能）

TCPの輻輳制御アルゴリズム (1/2) ネットワークの状態推測機構 単純なアルゴリズム ネットワークの情報は直接手に入らない エンド間の通信から得られる情報で推察 単純なアルゴリズム パケットが落ちない 転送量を上げる パケットが落ちた 転送量を落とす

TCPの輻輳制御アルゴリズム (2/2) ウィンドウサイズを増減させ転送制御 2段階の通信状態 送信者の輻輳ウィンドウ 受信者のウィンドウサイズ広告 2段階の通信状態 スロースタート 輻輳回避

スロー・スタート スロー・スタート 輻輳ウインドウ（cwnd） エンドノード間の回線状態はわからない 回線の許容量以下に送信量を制御する必要がある ネットワークへの突発的なトラフィック流入を防止可能 輻輳ウインドウ（cwnd） 送信者が送信可能なセグメント数を決定 送信者が管理するウィンドウ （注）受信者の管理するウィンドウとは別

スロー・スタートの仕組み スロー・スタートのアルゴリズム 通信開始時 Ack受信時 輻輳ウィンドウサイズを1で初期化 輻輳ウィンドウは幾何級数的に増加

スロー・スタートの概要 送信者 受信者 1,2,4,8,,,,と幾何級数的にウィンドウサイズを大きくする 初期windowサイズは1で送信 １に対してAckを返す 送信者 受信者 windowサイズを2で送信 2に対してAckを2つ返す windowサイズを4で送信 1,2,4,8,,,,と幾何級数的にウィンドウサイズを大きくする

輻輳回避状態 スロースタートを開始し、輻輳ウィンドウが増加 送信者は、パケットロスを検知しスロースタートを停止 輻輳回避状態へ移行 輻輳が発生したときの輻輳ウィンドウを記憶 輻輳ウィンドウを１に戻しスロースタートを再初期化 輻輳回避状態へ移行 記憶した輻輳ウィンドウまでは通常のスロースタート 記憶した輻輳ウィンドウに達すると Ack受信ごとに輻輳ウィンドウを上げていかない 輻輳ウィンドウ分のAckを受信して輻輳ウィンドウを開く

TCP Tahoe におけるウィンドウサイズの変化 スロースタート 輻輳回避 ネットワーク の限界 最適な ウィンドウサイズ スロースタート 閾値 t

TCP Reno におけるウィンドウサイズの変化 スロースタート 輻輳回避 ネットワーク の限界 最適な ウィンドウサイズ スロースタート 閾値 t

往復時間の測定 RTTから分かること RTTは非線形に変化 平滑化することでRTTを評価（RTT評価値） 輻輳の度合い パケットロスの指標 外れ値の可能性 平滑化することでRTTを評価（RTT評価値） RはRTT評価値 Mは新しい測定値 αは平滑化係数（推奨値は0.9） R = αR+(1-α)M

再転送タイムアウト値の算出 再転送タイムアウト値（RTT） 再転送タイムアウトするごとに増加 βは遅延分散係数（推奨値は2） 指数バックオフ 最大値64秒 RTO = Rβ (RFC793推奨式)

高速再転送アルゴリズム 受信者のTCPが順番の違うセグメントを受信 確認応答（重複ACK）を生成する必要 高速再転送アルゴリズム 受信者はセグメントを並び替えて上位層に渡す パケットロスが発生した … (b) 送信者は該当するセグメントを再送する必要 高速再転送アルゴリズム (a)、(b)をいち早く調べる方法 以下の場合、パケット損失の可能性高と判断 重複ACKを３つ受信した場合 再送タイマを待たずに直ちに再送する

高速再転送アルゴリズム 再送タイムアウトを待たずに再送 迅速な再送による転送効率の向上 2番のパケットが 届いていない！ ５ ４ ５ 　　2番のパケットが 届いていない！ ５ 発信元 宛て先 インターネット ４ Packet loss ５ 3 2番パケットを転送 ４ 2 3 1 1 3が届いた時点で1番へのACK 1番へのACKが 3が届いた時、4が届いた時、5が通ったとき の合計3回届く

セルフクロッキング (1/3) 経路の一番細い部分がボトルネックとなり、パケットギャップが発生する ボトルネック ボトルネック 送信者 受信者 ルータ ルータ 帯域が広い 帯域が狭い 帯域が広い

セルフクロッキング (2/3) 受信者はパケットギャップの間隔でAckを返してくる 送信者 受信者 ルータ ルータ 帯域が広い 帯域が狭い

セルフクロッキング (3/3) Ackの受信間隔に合わせてパケットを送出する 通信のバースト性が抑えられる 送信者 受信者 ルータ ルータ 帯域が広い 帯域が狭い 帯域が広い

まとめ：TCPにおける輻輳制御 ネットワークの状態を動的に推測 輻輳が発生すれば転送速度を落とす 輻輳が起きないギリギリまで転送速度を上げる できるだけ早く最適なウィンドウサイズに到達する ウィンドウサイズが安定すると通信も安定する

エンドノードによる輻輳制御の限界 エンドノードだけでは、ネットワークの状態を完全に把握することは不可能 ネットワーク全体の安定が各エンドノードの自律的な動作に掛かっている 悪意のあるユーザの攻撃や、無知なユーザの無秩序な利用に対して脆弱 中間ノードでも制御を行う必要性 QoS技術

ネットワークによる輻輳制御 - QoS機構 -

QoSとは？ Quality of Service 利用するサービスに対して品質を考慮 特にインターネットでは、通信品質 スループット レスポンスタイム 到着揺らぎ幅（ジッタ） 自律分散協調型のインターネットでは困難

エンドノードとネットワーク ネットワークでの制御 エンドノードでの制御 ネットワークの状態を把握できる ネットワークの状態は分からない 処理が集中しやすい 重い処理は避けたい ネットワーク全体へ設定が反映される エンドノードでの制御 ネットワークの状態は分からない 重い処理もできる ネットワーク全体に影響を及ぼせない

QoSの必要性 全ての通信をスムーズには行えない サービスの平滑化・差別化 リアルタイムアプリケーションの優先 料金格差 放送（音楽・動画） 対戦型ゲーム IP電話 緊急の電話・緊急でない電話

QoSの実現例 専用の回線を用意する 中間ノードでの優先制御 IPアドレス・ポート番号などヘッダの情報で区別 ヘッダに特別な情報を負荷 問題点 既存のインターネットの概念と反する スケーラビリティとの兼ね合い

輻輳が発生したら ルータはキューを備えている 輻輳が発生 ＝ キューが溢れる キューから溢れたパケットは破棄される ルータ キュー 輻輳が発生　＝　キューが溢れる キューから溢れたパケットは破棄される ルータ キュー 入りきらず,破棄される

パケットの優先制御 優先したいパケットは優先QUEUEに入れる ここでは、青いパケットを優先したいとする 水色のQUEUEが優先QUEUEとする

QoSの実現に必要な構成要素 サービスの記述 中間ノードでの優先制御機構 制御情報の伝播 管理者による手動設定では対処できない 多種多様な要求がある 中間ノードでの優先制御機構 制御情報の伝播 シグナリング技術 管理者による手動設定では対処できない

QoS機構（１）： Intserv + RSVP サービスの記述 フローごとの帯域予約 Intserv 予約メッセージフォーマット FF（Fixed Filter）方式 SE（Shared Explicit）方式 WF（Wildcard Filter）方式

QoS機構（１）： Intserv + RSVP 優先制御機構 RSVP対応ルータ フローの状態を常に監視 フローごとに予約帯域を確保 フローに適合するパケットを優先転送

QoS機構（１）： Intserv + RSVP 制御情報の伝播 RSVPメッセージ エンド間のルータ全てに伝播させる 送信者→受信者：パスメッセージ 受信者→送信者：予約メッセージ

Intserv + RSVPの問題点 エンド間にRSVP対応ルータが不可欠 各ルータがフローの状態を保持 マッチングするヘッダフィールドが様々 管理する情報が膨大 トラフィックが急増すると破綻 ルータの負荷を軽減する必要性

QoS機構（２）： Diffserv + BB サービスの記述 PHB（Per-HOP Behavior） EF（Expedited　Forwarding） AF（Assured　Forwarding） DSCP（Diffserv Code Point） IPヘッダのTOSフィールド（→DSフィールド）中に記述 DS対応ノードはDSCPとPHBのテーブルを保持 DSエッジが記述 DSドメインに入る際

QoS機構（２）： Diffserv + BB Diffservとスケーラビリティ Intservではルータの負荷が問題 DSCPはヘッダ中のビット列 固定長 処理が軽い

QoS機構（２）： Diffserv + BB 優先制御機構 DS対応ルータ（DSコア） トラフィック分類機能 BA（Behavior Aggregate）Classifier MF（Multi Field）Classifier TCA（Traffic Conditioning Agreement）

QoS機構（２）： Diffserv + BB 制御情報の伝播 BB（Bandwidth Broker） DSドメイン内のリソース割り当て 詳細な挙動までは決まっていない 主流となるソフトウェアは未だ無い 研究ベース

MPLSによるトラフィック制御 MPLS（Multi Protocol Label Switching） MPLSを応用したトラフィック制御 パケット転送技術のひとつ パケットにラベルヘッダを付加 ラベルスイッチング MPLSを応用したトラフィック制御 ラベルに通信品質制御情報を付加 RSVP-extension Diffservに類似したモデル ラベル IPヘッダ

通常のIPネットワークからMPLSネットワークへパケットが転送 エッジ 外部ネットワーク LSR ラベルが変更される ラベルが付加される パスが張られる ラベルが削除される ラベルが変更される

まとめ：QoSと輻輳制御 管理ドメイン内での制御 ユーザのニーズを適切に記述 記述された要求に従い制御情報を伝播 中間ノードが優先制御 特定の通信が輻輳を回避