システム同定を用いた

anced
Network
Architecture
Research
Group
Studies on Modeling Packet Delay Dynamics
of the Internet using System Identification
and its Application
for Designing a Rate-Based Congestion Control Mechanism
ソフトウェア科学コース 村田研究室
森田 光茂
[email protected]
2002年 2月20日
修士論文発表会
1
anced
Network
Architecture
Research
Group
研究の背景
receiver
sender
• パケット伝送遅延時間の特性がわかれば
– QoS (Quality of Service) を向上できる
– 効率的な輻輳制御の実現が可能
• パケット伝送遅延時間の特性とは
– 送信レートの変化により、伝送遅延時間がどのように
変化するのか
パケット伝送遅延時間の特性の
モデル化が必要
2002年 2月20日
修士論文発表会
2
anced
Network
Architecture
Research
Group
研究の目的
• パケット伝送遅延時間の特性をモデル化
–
–
–
–
ネットワークをブラックボックスとして扱う
モデルに対する入出力データを測定
システム同定を用いてパラメータを決定
2種類の検証方法でモデルの妥当性を検証
• レート制御機構の設計
– 得られたモデルに制御理論を適用
2002年 2月20日
修士論文発表会
3
anced
Network
Architecture
Research
Group
ネットワークのモデル化
sender
ブラックボックス receiver
入力
出力
• 本研究での入出力の定義
入力
出力
2002年 2月20日
パケット送信レート
ラウンドトリップ時間
修士論文発表会
4
anced
Network
Architecture
Research
Group
ARX(Auto-Regressive eXogenous)モデル
e(k)
雑音
(他のトラヒックの影響)
u(k)
入力
(送信レート)
y(k)
ARX モデル
出力
(ラウンドトリップ時間)
y (k ) = -a1 y (k - 1) - ..... - ana y (k - na )
+ b1u (k - 1) + ..... + bnb u (k - nb ) + e(k )
システム同定によりパラメータを決定
2002年 2月20日
修士論文発表会
5
anced
Network
Architecture
Research
Group
モデル化の流れ
入力データ
出力データ
ARXモデル
パラメータ
システム同定
1.入出力データを測定する
2.測定した入出力データをARXモデルにあてはめ、
システム同定を用いてパラメータを決定する
3.モデルの妥当性を評価する
2002年 2月20日
修士論文発表会
6
anced
Network
Architecture
Research
Group
測定環境
• 測定環境により同定精度は大きく変化
– 雑音の影響
– ボトルネックリンクの特性
N1:LAN
ネットワーク構成が単純な場合
N2: WAN ネットワーク構成が複雑、かつ
アクセス回線がボトルネックの場合
N3: WAN ネットワーク構成が複雑、かつ
アクセス回線がボトルネックでない場合
2002年 2月20日
修士論文発表会
7
anced
Network
Architecture
Research
Group
ネットワークN1
sender
receiver
100Mbps
FTP server
120
FTP client
Mbps
入
力
(
パ
ケ 80
ッ
ト
送
信 40
レ
ー
ト 0
) 2000
slot
2150
ms
出
力
(
ラ
ウ 0.43
ン
ド
ト 0.42
リ
ッ
プ
時
間 0.412000
)
0.44
slot
2150
サンプリング周期 = 0.9ms
2002年 2月20日
修士論文発表会
8
anced
Network
Architecture
Research
Group
ネットワークN2
bottleneck
Internet
ISP
sender
Access link
0.08
Mbps
入
力
(
パ 0.06
ケ
ッ 0.04
ト
送
信
レ 0.02
ー
ト 0
) 2000
slot
2150
出
力
(
ラ
ウ
ン
ド
ト
リ
ッ
プ
時
間
)
500
receiver
ms
slot
2150
150
2000
サンプリング周期 = 125ms
2002年 2月20日
修士論文発表会
9
anced
Network
Architecture
Research
Group
ネットワークN3
Internet
bottleneck
sender
receiver
入20 Mbps
力
(
パ 15
ケ
ッ
ト 10
送
信 5
レ
ー
ト 02000
)
slot
2150
出
力
(
ラ
ウ
ン
ド
ト
リ
ッ
プ
時
間
)
80
ms
60
40
20
2000
slot
2150
サンプリング周期 = 6ms
2002年 2月20日
修士論文発表会
10
anced
Network
Architecture
Research
Group
シミュレーションによる妥当性の評価
入力データ1
出力データ1
モデル化した
ARXモデル
入力データ2
モデルの出力
モデルの出力と測定した出力データを比較
出力データ2
2002年 2月20日
修士論文発表会
11
anced
Network
Architecture
Research
Group
ボード線図による妥当性の評価
unknown
sin(w t )
A sin(wt + j )
A ゲイン特性
j 位相特性
ARXモデルの
モデル化した
ARXモデル
周波数特性
スペクトル解析による
周波数特性
入力データ
出力データ
周波数特性が一致すればモデルの妥当性がいえる
2002年 2月20日
修士論文発表会
12
anced
Network
Architecture
Research
Group
N1 シミュレーション
sender
receiver
100Mbps
FTP server
FTP client
measured data
model output
ラ
ウ
0.42
ン
ド
ト
リ
ッ
プ 0.415
時
間
0.41
2250
2260
2270
2280
2290
2300
slot
2002年 2月20日
修士論文発表会
13
anced
Network
Architecture
Research
Group
N1 ボード線図
Amplitude
10
-2
ARX モデル
スペクトル解析
10
-4
-6
Phase(degrees)
1010 -2
10
-1
10
0
10
1
0
100
200
10
-2
10
-1
10
0
10
1
Frequency (rad/s)
2002年 2月20日
修士論文発表会
14
anced
Network
Architecture
Research
Group
N2 シミュレーション
bottleneck
Internet
sender
receiver
450
ラ
ウ
ン
ド
ト
リ
ッ
プ
時
間
400
350
300
250
200
150
2250
2002年 2月20日
measured data
model output
2260
2270
修士論文発表会
slot
2280
2290
2300
15
anced
Network
Architecture
Research
Group
N2 ボード線図
Amplitude
10
10
4
3
ARX モデル
スペクトル解析
2
Phase(degrees)
1010 -2
10
-1
10
0
10
1
0
200
400
10
-2
10
-1
10
0
10
1
Frequency (rad/s)
2002年 2月20日
修士論文発表会
16
anced
Network
Architecture
Research
Group
N3 シミュレーション
Internet
bottleneck
sender
receiver
40
ラ
ウ
ン
ド
ト
リ
ッ
プ
時
間
35
30
25
20
2250
2002年 2月20日
measured data
model output
2270
2260
修士論文発表会
slot
2280
2290
2300
17
anced
Network
Architecture
Research
Group
N3 ボード線図
Amplitude
10
2
ARX モデル
スペクトル解析
10
0
2
Phase(degrees)
1010 -2
10
-1
10
0
10
1
0
500
1000
10
-2
10
-1
10
0
10
1
Frequency (rad/s)
2002年 2月20日
修士論文発表会
18
anced
Network
Architecture
Research
Group
輻輳制御機構の設計
パケット送信側ホスト
u(k)
(transmission rate)
regulator
ネットワーク
e(k)
ARXモデル
x(k)
state
observer
ABC
2002年 2月20日
y(k)
(round-trip time)
system
identification
修士論文発表会
19
anced
Network
Architecture
Research
Group
まとめ
• パケット伝送遅延時間の特性をモデル化
– ネットワークをブラックボックスとして扱う
– モデルに対する入出力データを実際のネットワークで
測定
– システム同定を用いてパラメータを決定
– モデルの妥当性を検証
送信レートがラウンドトリップ時間に
大きな影響を与える場合はモデル化が可能
2002年 2月20日
修士論文発表会
20