umeda_1118web(2).pptx

Size: px

Start display at page:

Download "umeda_1118web(2).pptx"

たつやけいれい
7 years ago
Views:

1 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計関西学院大学理工学部情報科学科松井知美巳波弘佳選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 0 / 20

2 現実のネットワーク現実世界のネットワークの分析技術の進展! ネットワークのデータ収集の効率化高速化! 膨大な量のデータを解析できるコンピュータ能力の向上! インターネット! WWWハイパーリンク構造 (Web Graph)! 知人関係! 代謝ネットワーク! など現実の複雑なネットワークを科学的に分析効用として, 例えば! アルゴリズムの設計! 新たな性質の発見! 経験則の適用範囲の明確化!... 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 1 / 20

3 現実のネットワーク現実のネットワークの例実ネットワークは単純ではなく複雑一見ランダムだが生成原理はありそう複雑ネットワーク (Complex Network) インターネットにおけるAS(Autonomous System)間の隣接関係図 h/p://sk- aslinks.caida.org/data/2007/のデータに基づき h/p://xavier.informaccs.indiana.edu/lanet- vi/のツールを用いて描画電子情報通信学会第6回情報ネットワーク科学研究会 (2013/11/22) 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 2 / 20

4 複雑ネットワークが持つ性質現実世界の複雑ネットワークが持つ性質の例 :! スケールフリー次数分布がべき乗則を満たすこと collaboration network WWW power grid! 平均的な次数というものが存在しない ( 適当なスケールがない = スケールフリー )! 大きな次数を持つ少数 ( だが少なすぎない ) の点 ( ハブ )! 小さな次数を持つ多数の点 (Barabási & Albert, 1999) 次数分布がべき乗則を満たす例選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 3 / 20

5 スケールフリーネットワークスケールフリーネットワークの特徴 : 頑健性と脆弱性 (Error and a/ack tolerance of complex networks, R. Albert et. al.)! ランダムな点破壊には頑健 5% 程度の点がランダムに破壊される - ほとんど影響がない - 平均経路長はほぼ変化しない! 選択的破壊には脆弱次数の高い上位 5% が選択的に破壊される - 小さな連結成分に分断される - 平均経路長は約 2 倍に増大する選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 4 / 20

6 SF ネットワーク設計 (1) SF ネットワーク設計 : リンク付加するとよいリンク付加は現実のネットワーク設計で使うのは困難 & リンク数を増やせば信頼性が上がるのは自明 & 最小コスト設計の観点からの研究はない選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 5 / 20

7 SF ネットワーク設計 (2) DetecCng CriCcal Nodes in Sparse Graph, A. Arulselvan et. Al. ネットワークを分断するノード集合を決定する最適化問題各連結成分ができるだけ小さくなるようにこれらのノード集合を破壊すると通信ネットワークの品質に重大なダメージを与えるならばこれらのノード集合を守ればネットワークの信頼性を維持することはできるのか? できない同程度の損失を出すノード集合は, 一意ではないネットワークの信頼性を維持するノード集合ではない選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 6 / 20

8 社会基盤として通信ネットワークネットワークの信頼性に関する最近の懸念スケールフリーネットワークはハブ攻撃に弱いしかし次数の高い少数のノード破壊で, - すぐに非連結化 - 最大連結成分のサイズが小さくなるこれらの指摘に対するこれまでのネットワーク設計法は使えないなぜなら - コスト最小化を追求していない - 信頼性の確保が実はできていない信頼性の高いネットワーク設計に関するアプローチがない選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 7 / 20

9 通信ネットワーク設計高い信頼性が必要一部が故障しても通信が継続できること信頼性の評価尺度はネットワークやアプリケーションに依存するコストは小さいことが望ましいコストをかければ信頼性は高まるのは自明必要な信頼性を最小コストで実現することが必要通信ネットワーク設計目的関数 : コスト最小化制約条件 : 必要な信頼性を満たすことなど最適化問題通信ネットワーク設計は最適化問題として扱える選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 8 / 20

10 リンクノード保護による高信頼化 Link AB が保護されていない Link AB が保護されている B 保護リンク B IP 層 A C A C E D E D Node A バックアップリンク Node B 独立したバックアップリンク Node A Node B 下位層故障 Node C 故障 Node C Node E Node D Node E Node D 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 9 / 20

11 リンクノード保護による高信頼化壊れないように頑健化ルータそれ以外のノードが破壊しても通信ネットワークの信頼性は保たれる選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 10 / 20

12 リンクノード保護による高信頼化リンクノード保護による高信頼化設計リンクノードの高信頼化のためのコストを抑えたい保護リンク以外の任意の同時 k リンク故障に対しても直径が指定値以下, サーバと連結しているノード数が指定値以上などの制約条件の下で保護リンク数最小化保護ノード以外の任意の同時 k ノード故障に対しても最小連結成分のサイズが指定値以上などの制約条件の下で保護ノード数最小化選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 11 / 20

13 分断抑制点保護問題 (PNC) 最小連結成分のサイズの下限 Instance : 無向グラフ G =( V, E ) 正整数 p, k, L 保護点数同時削除点数 QuesCon : G にサイズが p 以下の ( k, L ) - 保護点集合 V p は存在するか? V p に含まれないどのような k 個の点を取り除いても, 点を除かれたグラフの各連結成分の点数は L 以上選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 12 / 20

14 分断抑制点保護問題 (PNC) 定理 1. PNC は一般的に NP 完全既知の NP 完全問題である点被覆問題 VC からの多項式時間帰着により証明定理 2. 同時故障ノード数が 1 の場合における O( n 2 + nm ) アルゴリズムが存在する定理 3. 同時故障ノード数が 2 の場合における 2 近似 O( n 3 + n 2 ( 1 + m ) + m( n+1) ) アルゴリズムが存在する選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 13 / 20

15 削除点数が 1 の場合の多項式時間アルゴリズム削除 k=1 L=4 p=1 連結成分のサイズ 8 (1) 点をグラフから削除する (2) 残ったグラフの最小連結成分のサイズを調べる (3) L より大きいので何もしない選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 14 / 20

16 削除点数が 1 の場合の多項式時間アルゴリズム削除 k=1 L=4 p=1 連結成分のサイズ3 次の点でも同じ操作を行う (1) 点を削除 (2) 残ったグラフの最小連結成分のサイズを求める (3) Lより小さいので保護ノードとする選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 15 / 20

17 削除点数が 1 の場合の多項式時間アルゴリズム保護点削除 k=1 L=4 p=1 この操作 (1) (3) を全ての点に行う連結成分のサイズ 4 (4) 保護ノード数が p より大きいなら解はなし保護ノード数が p より小さいなら保護ノードを出力選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 16 / 20

18 削除点数が 1 の場合の多項式時間アルゴリズム無向グラフ : G 点数 : n 辺数 : m 全ての点に対し,12 を繰り返す全ての点に対して実行 O( n ) 回 1 点 v をグラフ G から削除 2 最小連結成分のサイズを求める L より小さければ削除した点を保護点とする点 v を復活させ 1 に戻る幅優先探索を用いて O( n + m ) 3 V p p ならば保護点集合 V p を出力そうでなければ解なし O( n(n + m) ) 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 17 / 20

19 ノード保護の例 CAIDA で公開されている ISP バックボーンネットワークのグラフ構造に対して保護ノードを調べた ISP n m L p No No No No No No No No.2(L=80) 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 18 / 20

20 ノード保護の例 CAIDA で公開されている ISP バックボーンネットワークのグラフ構造に対して保護ノードを調べた ISP n m L p No No No No No No No No.3(L=12) 5 13 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 19 / 20

21 まとめネットワーク分断を抑制するノード保護問題 (PNC) を定義 PNC は一般に NP 完全であることを証明 PNC において, 同時故障ノード数が 1 である場合に対する多項式時間アルゴリズムを設計 PNC において, 同時故障ノード数が 2 である場合に対する 2 近似多項式時間アルゴリズムを設計選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 20 / 20

Microsoft PowerPoint - 13approx.pptx

Microsoft PowerPoint - 13approx.pptx I482F 実践的アルゴリズム特論 13,14 回目 : 近似アルゴリズム上原隆平 (uehara@jaist.ac.jp) ソートの下界の話比較に基づく任意のソートアルゴリズムはΩ(n log n) 時間の計算時間が必要である証明 ( 概略 ) k 回の比較で区別できる場合の数は高々 2 k 種類しかない n 個の要素の異なる並べ方は n! 通りあるしたがって少なくとも k n 2 n!