スケールフリーネットワークにおける
経路制御のためのフラッディング手法
の提案と評価
大阪大学基礎工学部情報科学科4年
村田研究室 牧野 暢孝
<[email protected]>
2004/2/26
特別研究報告発表会
1
研究の背景
インターネットにおける経路制御

BGP, OSPF
フラッディングによる経路情報の交換


受け取った情報をすべての隣接ノードに配布
制御メッセージの重複が発生
ネットワークの大規模化
→フラッディング時の制御メッセージ量,重複数が
増加
2004/2/26
特別研究報告発表会
2
インターネットのトポロジー特性
インターネットでは,隣接ノード数がべき乗則に従う
スケールフリーネットワーク


多くの隣接ノードを持つ,少数の ハブノード
あまり隣接ノードを持たない,多数の 非ハブノード
1
0.1
リンク数50~60
のノードが4つ
(ハブノード)
リンク数2~3の
ノードが80%
(非ハブノード)
0.01
0.001
2004/2/26
1
10
K : number of links
特別研究報告発表会
100
ノード数1000のスケー
ルフリーネットワークに
おける隣接ノード数の
分布
3
研究の目的
従来のフラッディング手法の評価

スケールフリーネットワークに適用した際の制御
メッセージ量の評価
新手法の提案・評価



2004/2/26
スケールフリーネットワークの特性を利用
フラッディング時の制御メッセージ量の改善
到達率を保ちつつ,制御メッセージ量を抑える
特別研究報告発表会
4
従来のフラッディング手法(1)
FSLS (Fuzzy Sighted Link State)
制御メッセージに TTL (Time to Live) を設定
制御メッセージが広がる範囲を限定

周期的なフラッディング
近傍ノードには頻繁に,遠くのノードには間をあけて送信
制御メッセージの集約を行い,メッセージ量を減らす


問題点
Full Flooding
TTL
S1
0
2004/2/26
1
S2
2
S4
S3
S1
3
S1
4
5
S2
6
S1
7
特別研究報告発表会
8
Full Flooding
TTL が大きい場合に制御メッセージの重複が発生

使用するTTLの系列
単位時間あたり,
S1は1回,S2は1/2回
S3は1/4回とフラッディン
グが行われる.Si ≦ Si+1
time
5
従来のフラッディング手法(2)
確率によるフラッディング手法
各隣接ノードへ確率 p で中継

伝達率が100%となる確率 p の下限値 pc の
導出手法[1]
シミュレーションによる評価

文献[1]の手法で求めた結果 pc =0.90
制御メッセージの重複を 1 割削減

p を変えて評価
p = 0.7 で90% のノードに伝わりつつ 制御メッセージ
量を 3 割削減
→ 制御メッセージ量をさらに削減できる可能性がある
しかし,確率を小さくするとネットワーク全体に広まらない
[1] F. Banaei-Kashani and C. Shahabi, “Criticality–based analysis and design of unstructured peer-to-peer
networks as ’complex systems’,” in Proceedings of GP2PC, pp. 22–32, May 2003.
2004/2/26
6
特別研究報告発表会
提案手法 (1/2)
従来手法


FSLS: 制御メッセージの重複数は減らない
確率 : 高い確率では制御メッセージの削減の効果が少ない
低い確率では近隣のノードにも届かない可能性
提案手法


確率p の値を小さくし,複数回フラッディング
周期的なTTL設定
近隣のノードには複数回フラッディングが行われる
→近隣ノードには高い確率で情報が伝わる
フラッディングが発生
S1
S2
S3
2004/2/26
特別研究報告発表会
7
提案手法 (2/2)
TTL系列を設定


数式により,TTL毎の重複メッセージ数を計算
重複メッセージ量が急激に増大するTTLを求め,
その直前の値を初期TTL値S1として用いる
→ 重複しない範囲で積極的にフラッディング
2004/2/26
特別研究報告発表会
8
提案手法の評価




1000 ノードのスケールフリーネットワーク
1ノード(非ハブ)が連続してフラッディングを行う
フラッディングの間隔;平均 100 ms の指数分布
提案手法の確率 p=0.5
400
経路情報を
受信した累積ノード数
80
OSPF,p=0.9
60
TTL
提案手法
p=0.7
40
p=0.5
20
0
0
1
2004/2/26
2
3
4
5
6
time (sec)
7
8
9
10
Cumulative packet count (x 1000)
Cumulative advertised nodes (x 1000)
100
ネットワークに流れた
制御メッセージの数
(累積)
350
300
p=0.7
250
OSPF
200
P=0.9
150
FSLS
p=0.5
100
提案手法
50
0
0
特別研究報告発表会
1
2
3
4
5 6
time (sec)
7
8
9
10
※p=n は確率による従来手法 9
まとめと今後の課題
まとめ

スケールフリーネットワークにおけるフラッディング方式の
提案と評価
低確率で複数回フラッディング

制御メッセージの重複を削減
周期的にTTLを設定し,近隣ノードに情報が伝わる確率を高める
OSPFと比較して制御メッセージ数を95%削減
今後の課題


経路情報が遅れて各ノードに到着することによるスルー
プット性能への影響
経路情報の不整合の影響
パケットの到達性,ループ検出
2004/2/26
特別研究報告発表会
10
ダウンロード

ppt - 先進ネットワークアーキテクチャ研究室