TCPと輻輳制御
 輻輳制御の重要性
 輻輳制御の困難さ
 TCPによる輻輳制御
輻輳制御の重要性 (1/2)
 輻輳は悪化していく傾向がある
玉突き事故
三次災害
二次災害
輻輳発生
輻輳制御の重要性 (2/2)
 ネットワークに自律的な輻輳回復機能がない
 ネットワークはできるだけ仕事をしない
 エンドノードが輻輳を回避する必要がある
 エンドノードは故意に輻輳を起こせる
 DoSアタック
輻輳制御技術の大まかな歴史
 初期のインターネット:輻輳制御技術なし
 1980年初
輻輳崩壊の発生が指摘される
 1980年後半
エンドノード主体による輻輳制御技術の出現
 1990年後半
中継ノード主体による輻輳制御技術の出現
 現在
広帯域・低遅延要求アプリケーションの台頭
インターネット速度記録(TCP高速化技術)
輻輳制御の困難さ (1/2)
 エンドノードはネットワークの状態が分からない
 自分で推測してネットワークに送出するだけ
パケットを少なく出すのか?
パケットを多く出すのか?
ネットワークは教えてくれない
IPネットワーク
輻輳制御の困難さ (2/2)
なぜインターネットの状態は分かりにくい?
 IPの特徴
 様々な通信媒体の性質を抽象化
 上位プロトコルから通信媒体の性質が見えにくい
 中継システムの簡素化
 ネットワークの許容量が不明
 ネットワークの混雑度が不明
アプリケーションとトラフィックパターン
 TCP
 インタラクティブデータフロー
 パケットを直ちに送出
 アプリケーション例:SSH, Telnet などコンソールアプリケーション
 バルクデータフロー
 フロー制御によってパケットを送出
 アプリケーション例:http, ftp, メール など
 UDP
 フロー制御・輻輳制御を行わない
 アプリケーション例:ストリーミング, VoIP など
それぞれが異なるトラフィックパターンを有する
アプリケーショントレンドの推移
トラフィックの推移
100%
90%
ポート番号からサービス
特定がしにくい時代
80%
70%
データ量(%)
60%
Others
Napster
SMTP
HTTP/HTTPS
FTP
P2P登場
50%
40%
WWW全盛
30%
20%
出典: WIDE報告書(1994-1999)
2000-2005はdaily sampling
10%
0%
1994
1995
1996
1997
1998
1999
2000
年
2001
2002
2003
2004
2005
15年前のアプリケーションモデル
 サーバ・クライアントモデル


サービスを提供する側と受ける側に役割を分担
情報(データ)は「提供する側」に存在
 情報(データ)のありか

情報(データ)が格納されているサーバは「何らかの方法」で探し出す

archie プログラム
サーバ数が多くない上、有名なサーバには様々な種類の情報(データ)が大量に存
在
ソフトウェアファイル
ドキュメントファイル

サーバAから
サーバAから
 ソフトウェアを
情報(データ)の集まり方
巨大なサーバ: A
ドキュメントを
ダウンロードしよう
ダウンロードしよう
 情報(データ)が一箇所に集まるので、利用者も一箇所に集中してアクセスする
インターネット
利用者
クライアント
クライアント
利用者
10年~5年前のアプリケーションモデル

サーバ・クライアントモデル



「置き場所」としてのサーバは変化せず
能動的なクライアントも変化せず
情報の分散化

情報(データ)は、「リンク」が含むようになり、分散したサーバ間で情報が有機的に結びつけられ
るようになった



情報(データ)のありか:

情報(データ)が格納されているサーバは「何らかの方法」で探す



情報提供者はリンクを意識して情報(データ)を作成
情報利用者はリンクを辿り新たな情報(データ)を取得
cf. 検索エンジン、ディレクトリサービス
アドレスを指定
アドレスを指定
サーバの数が多く、大量の情報(データ)が分散して存在
情報(データ)の集まり方

Webサーバ
インターネット中に分散して存在するが、利用者の増加に伴い人気のある情報(データ)を持つ
サーバにアクセスは集中
Webサーバ
インターネット
アドレスを指定
Webサーバ
アドレスを指定
Webサーバ
最近のアプリケーションモデル


P2Pモデル

あらかじめ役割を決めない

(サーバ・クライアントの両方の役割を担う)

対等な関係
情報(データ)単位の分散化から、分割した情報(データ)の分散化



ファイル単位のやり取りから、ファイルの分割を前提とした断片単位のやり取りへ
情報(データ)のありか

断片化した情報(データ)はネットワーク上の任意のホストに存在

情報理論を応用した検索手法(分散ハッシュ etc…)

P2Pのピアになるホストの数だけ分散する可能性がある
情報(データ)の集まり方
ファイルA

完全な情報(データ)は、それをリクエストした人のところに存在

ネットワーク上には、断片化されたもの、完全なもの様々な形で存在
ファイル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)
フローコントロール
②
もちょっとゆっくり
送って。
受信者
送信者
もちょっとゆっくり
③ 送るか。
①
キュー(バッファ)
早すぎてバッファがあふれる
フローコントロール
②
もっとはやく
送って。
受信者
送信者
③
じゃはやくおくるか
①
キュー(バッファ)
遅いから余裕があるな
ウィンドウ制御
 ウィンドウ広告 = 受信バッファ残量
 ウィンドウ更新
 ACKセグメントによる
 ACKを待たずに、複数セグメントを転送
 転送効率の向上
スライディングウィンドウ
8
1
7
6
直ちに
転送可能
2
広告
ウィンドウ
3
5
4
スライディングウィンドウ
8
転送されたが
1 確認応答されていない
7
2
6
広告
ウィンドウ
3
5
4
直ちに
転送可能
スライディングウィンドウ
8
7
1
転送されて
確認応答済み
2
転送されたが
確認応答されていない
6
3
5
4
直ちに
転送可能
スライディングウィンドウ
8
7
1
転送されて
確認応答済み
2
転送されたが
確認応答されていない
6
3
5
新たに広告された
ウィンドウ
4
直ちに
転送可能
TCPの輻輳制御機能
②
もちょっとゆっくり
送ろう。
送信者
受信者
輻輳
①
受信者からしばらく応答がない
輻輳が発生してパケットが届いて
なさそうだ
輻輳制御の重要性
 輻輳は悪化していく傾向がある
輻輳発生
二次災害
なんらかの対処をしなければ
悪化する一方 (輻輳崩壊)
玉突き事故
TCPの輻輳制御アルゴリズム
 非常に多くのアルゴリズムが存在
 代表的な例
 TCP Tahoe
 スロースタートアルゴリズム,輻輳回避アルゴリズム,高速再転送
アルゴリズム
 TCP Reno (TCP NewReno)
 高速再転送アルゴリズム
 TCP Vegas
 RTTをベースとしたウィンドウサイズの調整
 OSによって実装されているアルゴリズムがことなるこ
とも
TCPの輻輳制御アルゴリズム(時代別)
 1988年頃
 Tahoe
 スロースタート、輻輳回避アルゴリズムの採用
 高速再転送アルゴリズムの採用
 1990年頃
 Reno
 高速リカバリ・アルゴリズムの採用
 1996年頃
 NewReno
 高速リカバリ・アルゴリズムの修正
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の続き
 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.
TCPの輻輳制御アルゴリズム
(1/2)
 ネットワークの状態推測機構
 ネットワークの情報は直接手に入らない
 エンド間の通信から得られる情報で推察
 単純なアルゴリズム
 パケットが落ちない
 転送量を上げる
 パケットが落ちた
 転送量を落とす
TCPの輻輳制御アルゴリズム
(2/2)
 ウィンドウサイズを増減させ転送制御
 送信者の輻輳ウィンドウ
 受信者のウィンドウサイズ広告
 2段階の通信状態
 スロースタート
 輻輳回避
スロー・スタート
 スロー・スタート
 エンドノード間の回線状態はわからない
 回線の許容量以下に送信量を制御する必要がある
 ネットワークへの突発的なトラフィック流入を防止可能
 輻輳ウインドウ(cwnd)
 送信者が送信可能なセグメント数を決定
 送信者が管理するウィンドウ
 (注)受信者の管理するウィンドウとは別
スロー・スタートの仕組み
 スロー・スタートのアルゴリズム
 通信開始時
 輻輳ウィンドウサイズを1で初期化
 Ack受信時
 輻輳ウィンドウをAck受信毎に増加
 輻輳ウィンドウは幾何級数的に増加
スロー・スタートの概要
初期windowサイズは1で送信
1に対してAckを返す
送信者
受信者
windowサイズを2で送信
2に対してAckを2つ返す
windowサイズを4で送信
1,2,4,8,,,,と幾何級数的にウィンドウサイズを大きくする
輻輳回避状態
1. スロースタートを開始し、輻輳ウィンドウが増加
2. 送信者は、パケットロスを検知しスロースタートを停止
 輻輳が発生したときの輻輳ウィンドウを記憶
 輻輳ウィンドウを1に戻しスロースタートを再初期化

輻輳回避状態へ移行
 記憶した輻輳ウィンドウまでは通常のスロースタート
 記憶した輻輳ウィンドウに達すると
 Ack受信ごとに輻輳ウィンドウを上げていかない
 輻輳ウィンドウ分のAckを受信して輻輳ウィンドウを
開く
TCP Tahoe
におけるウィンドウサイズの変化
スロースタート
輻輳回避
ネットワーク
の限界
最適な
ウィンドウサイズ
スロースタート
閾値
t
TCP Reno
におけるウィンドウサイズの変化
スロースタート
輻輳回避
ネットワーク
の限界
最適な
ウィンドウサイズ
スロースタート
閾値
t
往復時間の測定
 RTTから分かること
 輻輳の度合い
 パケットロスの指標
 RTTは非線形に変化
 外れ値の可能性
 平滑化することでRTTを評価(RTT評価値)
R = αR+(1-α)M
 RはRTT評価値
 Mは新しい測定値
 αは平滑化係数(推奨値は0.9)
再転送タイムアウト値の算出
 再転送タイムアウト値(RTT)
RTO = Rβ (RFC793推奨式)
 βは遅延分散係数(推奨値は2)
 再転送タイムアウトするごとに増加
 指数バックオフ
 最大値64秒
高速再転送アルゴリズム
 受信者のTCPが順番の違うセグメントを受信
 確認応答(重複ACK)を生成する必要
 単に順番が入れ替わった … (a)
 受信者はセグメントを並び替えて上位層に渡す
 パケットロスが発生した … (b)
 送信者は該当するセグメントを再送する必要
 高速再転送アルゴリズム
 (a)、(b)をいち早く調べる方法
 以下の場合、パケット損失の可能性高と判断
 重複ACKを3つ受信した場合
 再送タイマを待たずに直ちに再送する
高速再転送アルゴリズム
 再送タイムアウトを待たずに再送
2番のパケットが
 迅速な再送による転送効率の向上
届いていない!
5
5
4
3
4
2番パケットを転送
Packet
loss
2
3
1
1
インターネット
発信元
3が届いた時点で1番へのACK
1番へのACKが
3が届いた時、4が届いた時、5が通ったとき
の合計3回届く
宛て先
セルフクロッキング (1/3)
 経路の一番細い部分がボトルネックとなり、パケットギャッ
プが発生する
ボトルネック
送
信
者
ルータ
帯域が広い
ルータ
帯域が狭い
パ
ケ
ッ
ト
ギ
ャ
ッ
プ
帯域が広い
受
信
者
セルフクロッキング (2/3)
 受信者はパケットギャップの間隔でAckを返してくる
送
信
者
受
信
者
ルータ
帯域が広い
ルータ
帯域が狭い
帯域が広い
セルフクロッキング (3/3)
 Ackの受信間隔に合わせてパケットを送出する
 通信のバースト性が抑えられる
送
信
者
受
信
者
ルータ
帯域が広い
ルータ
帯域が狭い
帯域が広い
まとめ:TCPにおける輻輳制御
 ネットワークの状態を動的に推測
 輻輳が発生すれば転送速度を落とす
 輻輳が起きないギリギリまで転送速度を上げる
 できるだけ早く最適なウィンドウサイズに到達する
 ウィンドウサイズが安定すると通信も安定する
エンドノードによる輻輳制御の限界
 エンドノードだけでは、ネットワークの状態を完全に把握す
ることは不可能
 ネットワーク全体の安定が各エンドノードの自律的な動作
に掛かっている
 悪意のあるユーザの攻撃や、無知なユーザの無秩序な利
用に対して脆弱
 中間ノードでも制御を行う必要性
 QoS技術
QoSとは?
 Quality of Service
 利用するサービスに対して品質を考慮
 特にインターネットでは、通信品質
 スループット
 レスポンスタイム
 到着揺らぎ幅(ジッタ)
 自律分散協調型のインターネットでは困難
エンドノードとネットワーク
エンドノードでの制御
ネットワークでの制御
 ネットワークの状態は分
からない
 ネットワークの状態を把
握できる
 重い処理もできる
 処理が集中しやすい
 ネットワーク全体に影響
を及ぼせない
 重い処理は避けたい
 ネットワーク全体へ設定
が反映される
QoSの必要性
 全ての通信をスムーズには行えない
 サービスの平滑化・差別化
 料金格差
 リアルタイムアプリケーションの優先
 放送(音楽・動画)
 対戦型ゲーム
 IP電話
 緊急の電話・緊急でない電話
QoSの実現例
 専用の回線を用意する
 中間ノードでの優先制御
 IPアドレス・ポート番号などヘッダの情報で区別
 ヘッダに特別な情報を負荷
問題点
既存のインターネットの概念と反する
スケーラビリティとの兼ね合い
輻輳が発生したら
 ルータはキューを備えている
 輻輳が発生 = キューが溢れる
 キューから溢れたパケットは破棄される
ルータ
キュー
入りきらず,破棄される
パケットの優先制御
 優先したいパケットは優先QUEUEに入れる
 ここでは、青いパケットを優先したいとする
 水色のQUEUEが優先QUEUEとする
QoSの実現に必要な構成要素
 サービスの記述
 多種多様な要求がある
 中間ノードでの優先制御機構
 制御情報の伝播
 シグナリング技術
管理者による手動設定では対処できない
QoS機構(1): Intserv + RSVP
サービスの記述
 フローごとの帯域予約
 Intserv
 予約メッセージフォーマット
 FF(Fixed Filter)方式
 SE(Shared Explicit)方式
 WF(Wildcard Filter)方式
QoS機構(1): Intserv + RSVP
優先制御機構
 RSVP対応ルータ
 フローの状態を常に監視
 フローごとに予約帯域を確保
 フローに適合するパケットを優先転送
QoS機構(1): Intserv + RSVP
制御情報の伝播
 RSVPメッセージ
 エンド間のルータ全てに伝播させる
 送信者→受信者:パスメッセージ
 受信者→送信者:予約メッセージ
Intserv + RSVPの問題点
 エンド間にRSVP対応ルータが不可欠
 各ルータがフローの状態を保持
 マッチングするヘッダフィールドが様々
 管理する情報が膨大
 トラフィックが急増すると破綻
ルータの負荷を軽減する必要性
QoS機構(2): 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機構(2): Diffserv + BB
Diffservとスケーラビリティ
 Intservではルータの負荷が問題
 DSCPはヘッダ中のビット列
 固定長
処理が軽い
QoS機構(2): Diffserv + BB
優先制御機構
 DS対応ルータ(DSコア)
 トラフィック分類機能
 BA(Behavior Aggregate)Classifier
 MF(Multi Field)Classifier
 TCA(Traffic Conditioning Agreement)
QoS機構(2): Diffserv + BB
制御情報の伝播
 BB(Bandwidth Broker)




DSドメイン内のリソース割り当て
DSエッジを設定
詳細な挙動までは決まっていない
主流となるソフトウェアは未だ無い
 研究ベース
MPLSによるトラフィック制御
 MPLS(Multi Protocol Label Switching)
 パケット転送技術のひとつ
 パケットにラベルヘッダを付加
ラベル IPヘッダ
 ラベルスイッチング
 MPLSを応用したトラフィック制御
 ラベルに通信品質制御情報を付加
 RSVP-extension
 Diffservに類似したモデル
MPLSネットワーク
通常のIPネットワーク
からMPLSネットワー
外部ネットワーク
クへパケットが転送
LSR
MPLS
エッジ
ラベルが付
加される
パスが張られる
LSR
LSR
ラベルが
変更される
ラベルが
変更され
る
ラベル
が削除
MPLSされる
エッジ
外部ネットワーク
まとめ:QoSと輻輳制御
 管理ドメイン内での制御
 ユーザのニーズを適切に記述
 記述された要求に従い制御情報を伝播
 中間ノードが優先制御
 特定の通信が輻輳を回避
ダウンロード

授業資料