スケールフリーネットワークにおける経路制御のためのフラッディング手法の提案と評価大阪大学基礎工学部情報科学科４年村田研究室牧野暢孝 <[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は１回，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% のノードに伝わりつつ制御メッセージ量を３割削減 → 制御メッセージ量をさらに削減できる可能性があるしかし，確率を小さくするとネットワーク全体に広まらない [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 の値を小さくし，複数回フラッディング周期的なＴＴＬ設定近隣のノードには複数回フラッディングが行われる →近隣ノードには高い確率で情報が伝わるフラッディングが発生 S1 S2 S3 2004/2/26 特別研究報告発表会 7 提案手法 (2/2) TTL系列を設定   数式により，TTL毎の重複メッセージ数を計算重複メッセージ量が急激に増大するTTLを求め，その直前の値を初期TTL値S1として用いる → 重複しない範囲で積極的にフラッディング 2004/2/26 特別研究報告発表会 8 提案手法の評価     1000 ノードのスケールフリーネットワーク１ノード（非ハブ）が連続してフラッディングを行うフラッディングの間隔；平均 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