流体近似法および待ち行列理論を組み合わせた TCPのフィードバック型

流体近似法および待ち行列理論を組み合わせた
TCPのフィードバック型制御機構のモデル化
大阪大学大学院基礎工学研究科
久松潤之
[email protected]
1
発表の構成
• 流体近似法と待ち行列理論を用いた
TCPのモデル化
• 過渡特性の解析
2
研究の背景
• TCP (Transmission Control Protocol)
– インターネットにおけるトランスポート層のプロトコル
– 輻輳制御機構
• これまでのTCPの輻輳制御機構に関する解析
– ネットワークにおけるパケット棄却率を一定と仮定
– 定常状態におけるTCPの振る舞いをモデル化
– 過渡特性についてはあまり解析されていない
• 実際のネットワーク
– TCPのウィンドウサイズが変化するとパケット棄却率も変化
3
研究の目的
• TCPのウィンドウフロー制御の過渡特性を解析
• ネットワーク全体を２つのシステムが相互に作用
するフィードバックシステムとしてモデル化
– TCPの送信側からみたネットワーク
• M/M/1/m待ち行列
– TCPの輻輳制御機構
• 流体近似法
• バックグラウンドトラヒックの影響を考慮
4
解析モデル
• 複数のTCPコネクション
• バックグラウンドトラヒックを考慮
バックグラウンドトラヒック
ルータ
送信側ホスト
TCP トラヒック
受信側ホスト
5
ネットワーク全体のモデル化
• フィードバックシステムとしてモデル化
– TCPから見たネットワーク
– TCPの輻輳制御機構
TCPの輻輳制御機構
w:ウィンドウサイズ
TCPから見た
ネットワーク
p:パケット棄却率
6
TCPから見たネットワークのモデル化
• ボトルネックルータをDrop-Tailルータと仮定
• M/M/1/m待ち行列を用いてモデル化
• 入力トラヒック
– TCPトラヒック
– バックグラウンドトラヒック
TCP
ウィンドウサイズ
w1
・・
・
wN
バックグラウンドトラヒックの
パケット到着率
B
N
wi
    B
i 1 ri
M/M/1/m
パケット
棄却率

p
m
7
TCPの輻輳制御機構のモデル化
• TCPの輻輳回避フェーズ
– ACKパケットを受信するごとにウィンドウサイズを増加
– パケット棄却を検出するとウィンドウサイズを減少
• シーケンスが同じ複数のACKパケットにより検出
• タイムアウトにより検出
8
TCPの輻輳制御機構のモデル化
• ４種類のモデル化を検討
– モデルA1
定常状態でのウィンドウサイズの変化をモデル化
– モデルA2
モデルA1のサブセット
– モデルB
• ACKパケットの受信もしくはパケット棄却の検出ごとのウィン
ドウサイズの変化をモデル化
– モデルC：Ohsaki
• パケット棄却から次のパケット棄却までのウィンドウサイズの
変化をモデル化
9
TCPの輻輳制御機構：モデルA１
• モデルA１
– パケット棄却率pを一定と仮定
– 定常状態でのウィンドウサイズの変化をモデル化
10
TCPの輻輳制御機構：モデルA２
• モデルA２
– モデルA１をパケット棄却率pが小さいところで近
似
11
TCPの輻輳制御機構：モデルB
• ACKパケットの受信もしくはパケット棄却の検出
ごとのウィンドウサイズの変化をモデル化
確率
ウィンドウサイズの変
化量
ACKパケットを受信
シーケンスの同じ複数のACKパ
ケットを受信することによりパケッ
ト棄却を検出
タイムアウトによりパケット棄却
を検出
:タイムアウトによりパケット棄却を検出する確率
12
TCPの輻輳制御機構：モデルC
• スロット：パケット棄却から次のパケット棄却
• スロット間のウィンドウサイズの変化をモデル化
• REDルータを対象
• 本解析ではDrop-Tailルータの場合のウィンドウ
サイズの変化を参考文献と同様の方法で導出
13
TCPから見たネットワークのモデル
• ルータへのパケット到着レートとパケット棄却率の関係
– M/M/1/m待ち行列
– シミュレーション結果
Offered Traffic Load
3
Simulation
M/M/1/m
M/M/1
2.5
2
1.5
1
0.5
0
0.01
0.1
Packet Loss Probability
1
M/M/1/mの曲線に沿ってシミュレーション結果が分布
14
TCPの輻輳制御機構のモデル
• ウィンドウサイズとパケット棄却率の関係
Average Window Size [packet]
– TCPの輻輳制御機構のモデル（４種類）
– シミュレーション結果
20
Simulation
Model A
Model A'
15
Model B
Model C
10
5
0
0.001
0.01
0.1
Packet Loss Probability
A,A’,B付近に集中
BとCの間
1
15
TCPの過渡特性解析
• 過渡特性
– ウィンドウサイズが初期値から定常状態での値までに
どのように変化するか
• ウィンドウサイズは実際には確率的に変動
– 平均的な振る舞いを調べる
• TCPの輻輳制御機構：モデルB
ウィンドウ
サイズ
時間
16
過渡特性解析
• ネットワークを離散時間システムとしてモデル化
– スロット：ACKパケットの到着間隔
– システムの状態
• TCPコネクションのウィンドウサイズ
• ネットワークにおけるパケット棄却率
• システムの状態遷移方程式
17
過渡特性解析
• 平衡点の導出
• 状態方程式を平衡点の近傍で線形化
 w(k )  w *
,
x(k )  
 p(k )  p * 
x(k  1)  Ax (k )
A:システムの状態遷移行列
18
過渡特性解析
• Aの固有値を s1 , s2
| s | max(| s1 |, | s2 |)
• |s|の値が収束の速度をあらわす
– |s|>1→不安定
– 0<|s|<1→安定
– |s|が0に近いほど収束の速度が速い
19
数値例：バックグラウンドトラヒックの量を
変化させた場合
0.9
eigenvalue
0.85
0.8
|s|
0.75
0.7
0.65
0
1
2

3
4
5
バックグラウンドトラヒックの量が多い
-過渡特性は向上
20
まとめ
• TCPの動的な振る舞い
– ２つのシステムからなるフィードバックシステム
• TCPから見たネットワーク
• TCPの輻輳制御機構
• TCPの過渡特性を解析
– バックグラウンドトラヒックの量が多い
過渡特性が向上
21

Download Report