PowerPoint プレゼンテーション

Advanced Network Architecture Lab.
Design Method of Logical Topologies
in WDM Network with Quality of Protection
WDMネットワークにおける障害回復時間を考慮した
ＱｏＰを実現する論理トポロジー設計手法の提案
大阪大学村田研究室
加藤潤一
E-mail: [email protected]
Feb. 21. 2002
NS研究会＠長野
1
Advanced Network Architecture Lab.
WDMネットワーク
WDM (Wavelength Division Multiplexing)
1本の光ファイバに複数の波長を多重化
各波長ごとに異なるデータを伝送
1波長の伝送容量は従来の光リンクの伝送容量と等量
多重化することによって伝送容量を8～1024倍
ノードへの負荷の増大
10Gbps
10Gbps
10Gbps
10Gbps
従来の光リンク
Feb. 21. 2002
WDM技術を適応した光リンク
NS研究会＠長野
2
Advanced Network Architecture Lab.
WDMネットワークアーキテクチャ
論理トポロジー
物理トポロジー
A
光パス
D
30Gbps
10Gbps
10Gbps
30Gbps
30Gbps
C
20Gbps
30Gbps
B
10Gbps
10Gbps
E
B
C
10Gbps
10Gbps
D
論理トポロジー設計問題
どの経路で？（経路選択問題）
どの波長に？（波長割当問題）
E
Feb. 21. 2002
NS研究会＠長野
3
Advanced Network Architecture Lab.
WDMネットワークにおける障害回復
WDMネットワーク：大容量の伝送容量
障害発生時のデータ損失が大きい
上位層の障害回復では遅い
WDM層での高速な障害回復機能が必要
Feb. 21. 2002
NS研究会＠長野
4
Advanced Network Architecture Lab.
WDMネットワークにおける障害回復方法
Protection : プロテクション
通常時トラヒックを流すプライマリ光パスと同時に、
バックアップ用のパスを予約
障害発生時、あらかじめ決められた経路にトラヒックを
流して障害から回復
Backup Path
Primary Lightpath
Feb. 21. 2002
NS研究会＠長野
5
Advanced Network Architecture Lab.
バックアップパスによる波長の共有
バックアップパスの波長の共有: shared protection
単一障害を前提
１つの障害で同時に断線しないプライマリ光パスの
バックアップパスは波長を共有できる
D
A
E
C
B
λ1
X
Y
λ2
F
Feb. 21. 2002
G
NS研究会＠長野
6
Advanced Network Architecture Lab.
従来の障害回復に関するQoS
波長資源の
利用効率
従来の研究
Shared Protection
Protection
確率的な
障害回復
障害回復 N%
なし障害回復
Feb. 21. 2002
本研究
100%
障害回復
NS研究会＠長野
高品質な
障害回復
100%障害回復
＋
α
信頼性に
関するQoS
7
Advanced Network Architecture Lab.
研究の目的
• 高品質な障害回復のための新しいQoS
メトリックの提案
• 新しいQoSメトリックを考慮した論理トポ
ロジー設計手法の提案
Feb. 21. 2002
NS研究会＠長野
8
Advanced Network Architecture Lab.
QoP (Quality of Protection) の提案
QoP:
最大障害回復時間(障害発生から回復までの最大待ち時間)を指定
QoP1
QoP2
Dmin
Dmin+ 1×Dscale
…
…
QoPn
Dmin+ (n-1)×Dscale
…
…
QoP∞
プロテクション経路なし
Dmin：保障可能な障害回復時間の最小値
Dscale : 各QoPの刻み幅
これらの値はネットワークによって適宜決定
Feb. 21. 2002
NS研究会＠長野
9
Advanced Network Architecture Lab.
QoPijへの変換
A
10ms
20ms
G
B
10ms
ノード間によっては物理的な制約によ
り実現不可能なQoPクラスがある
各ノード(i, j)間に対して、実現可能な
最も高いQoPをQoPijと設定
15ms
C
F
10ms
5ms
10ms D
QoP３
E
Dmin
Dmin+ 1×Dscale
Dmin+ ２×Dscale
QoPij
----QoPij(1)
…
…
Feb. 21. 2002
I
最大障害回復時間
…
H
QoP
QoP1
QoP2
QoP∞
バックアップ経路なし
QoPij(∞)
NS研究会＠長野
10
Advanced Network Architecture Lab.
SLSP (Short Leap Shared Protection)
P２
P1
P３
P４
全てのバックアップパスPxに対して
QoPij(n)
Dmin+ (n-1)×Dscale
Pxに対する
障害回復時間
となるように各バックアップパスPxの始点、終点を決定する
Feb. 21. 2002
NS研究会＠長野
11
Advanced Network Architecture Lab.
障害回復時間モデル
バックアップパスPx : Hxホップ
m-1 m m+1
n-1
n
n+1
主経路の保護する領域の伝播遅延時間 Dp
Pxに対するの障害回復時間 = Dp
最大障害検知時間
+
Dnode×Hx パス設定時間
+
Dconf
Feb. 21. 2002
NS研究会＠長野
パス切り替え時間
12
Advanced Network Architecture Lab.
階層化グラフアルゴリズム
物理トポロジー
階層化グラフは波長に対応し
波長数＝５
階層化グラフ
λ1
λ2
λ3
λ4
た波長グラフで構成される
各波長グラフは対応する波長
の使用状況を反映したグラフ
各波長グラフを用いて経路選
択することによって、波長の使用
状況を考慮した経路選択を可能
とする
新規に波長を使用するリンク
数をコストとする
コストが最小となる波長に割当
λ5
Feb. 21. 2002
NS研究会＠長野
13
Advanced Network Architecture Lab.
比較する論理トポロジー設計アルゴリズム
経路選択はともに固定：
プライマリ経路は最短経路、
バックアップパスは最小ホップ経路
First-Fit アルゴリズム
割当可能な最も添え字の小さい波長に割当
Max-Shared アルゴリズム
バックアップパスがもっとも波長を共有する波長に割当
Feb. 21. 2002
NS研究会＠長野
14
Advanced Network Architecture Lab.
評価モデル
2.8ms
1.4ms
3.5ms
9.1ms
11.2ms
1.4ms
3.5ms
4.7ms
1.4ms
3.5ms
2.8ms
2.8ms
3.5ms
8.4ms
7.0ms
5.6ms
8.4ms
0.7ms
3.5ms
3.5ms
Dmin
Dscale
Dnode
Dconf
10ms
2ms
1ms
0ms
4.9ms
ネットワークモデル： NSFNET(14ノード, 21リンク)
トラヒック量： NSFNETの実トラヒックの計測値（1992）を利用
波長帯域： 10Gbps
QoPij ：各ノード間が同一のQoPijを要求
評価指標：必要波長数
Feb. 21. 2002
NS研究会＠長野
15
Advanced Network Architecture Lab.
評価結果：必要波長数
各トラヒックは一様に同一のQoPijを要求
初期トラヒック量のα倍のトラヒックを与える
階層化グラフを用いた設計アルゴリズムが少
ない波長数で論理トポロジーを設計
α=1
α=5
100
180
First-Fit
Max-Shared
Layered-Graph
60
40
the number of wavelengths
80
the number of wavelengths
First-Fit
160
120
100
80
60
40
20
Max-Shared
140
Layered-Graph
20
0
0
2
4
6
8
10
12
14
QoPij
Feb. 21. 2002
2
4
6
8
10
12
14
QoPij
NS研究会＠長野
16
Advanced Network Architecture Lab.
評価結果：ブロッキング数
波長数＝５０
α＝１
the number of blocked connections
波長数が限定の
場合、設定できな
いコネクションがで
てくる。この設定で
きなかったコネク
ション数は階層化
グラフを用いること
によって、少なく抑
えることができる。
100
80
First-Fit
60
Max-Shared
40
Layered-Graph
20
0
2
4
6
8
10
12
14
QoPij
Feb. 21. 2002
NS研究会＠長野
17
Advanced Network Architecture Lab.
まとめ
 ＷＤＭネットワークにおける信頼性に対するQoSとし
てQoPを提案
 QoPを考慮した３つの論理トポロジー設計手法を提案
 波長数に制約が無い場合で、各アルゴリズムが論理
トポロジーを設計するのに必要な波長数を比較した
 波長数に制約がある場合で、各アルゴリズムが設定
に失敗したコネクションの数を比較した
 ２つの比較において、階層化グラフを用いた論理トポ
ロジー設計手法が効率的な波長利用が行えているこ
とを明らかにした
Feb. 21. 2002
NS研究会＠長野
18
Advanced Network Architecture Lab.
今後の課題
• Dmin, Dscaleの決定方法に対するガイドライ
ンの提案
• コネクションごとにQoPを要求するモデルに
対する論理トポロジー設計手法の提案
• 上位層の障害回復機能も考慮した論理ト
ポロジー設計
Feb. 21. 2002
NS研究会＠長野
19

Download Report