選択的ノード破壊による ネットワーク分断に耐性のある 最適ネットワーク設計 関西学院大学理工学部情報科学科 松井知美 巳波弘佳 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 0 / 20
現実のネットワーク 現実世界のネットワークの分析技術の進展! ネットワークのデータ収集の効率化 高速化! 膨大な量のデータを解析できる コンピュータ能力の向上! インターネット! WWWハイパーリンク構造 (Web Graph)! 知人関係! 代謝ネットワーク! など 現実の複雑なネットワークを科学的に分析 効用として, 例えば! アルゴリズムの設計! 新たな性質の発見! 経験則の適用範囲の明確化!... 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 1 / 20
現実のネットワーク 現実のネットワークの例 実ネットワークは 単純ではなく 複雑 一見ランダムだが 生成原理はありそう 複雑ネットワーク (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
複雑ネットワークが持つ性質 現実世界の複雑ネットワークが持つ性質の例 :! スケールフリー 次数分布がべき乗則を満たすこと collaboration network WWW power grid! 平均的な次数 というものが 存在しない ( 適当なスケールがない = スケールフリー )! 大きな次数を持つ少数 ( だが 少なすぎない ) の点 ( ハブ )! 小さな次数を持つ多数の点 (Barabási & Albert, 1999) 次数分布がべき乗則を満たす例 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 3 / 20
スケールフリーネットワーク スケールフリーネットワークの特徴 : 頑健性と脆弱性 (Error and a/ack tolerance of complex networks, R. Albert et. al.)! ランダムな点破壊には頑健 5% 程度の点がランダムに破壊される - ほとんど影響がない - 平均経路長はほぼ変化しない! 選択的破壊には脆弱 次数の高い上位 5% が選択的に破壊される - 小さな連結成分に分断される - 平均経路長は約 2 倍に増大する 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 4 / 20
SF ネットワーク設計 (1) SF ネットワーク設計 : リンク付加するとよい リンク付加は現実のネットワーク設計で使うのは困難 & リンク数を増やせば信頼性が上がるのは自明 & 最小コスト設計の観点からの研究はない 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 5 / 20
SF ネットワーク設計 (2) DetecCng CriCcal Nodes in Sparse Graph, A. Arulselvan et. Al. ネットワークを分断するノード集合を決定する最適化問題 各連結成分ができるだけ小さくなるように これらのノード集合を破壊すると 通信ネットワークの品質に重大なダメージを与える ならば これらのノード集合を守れば ネットワークの信頼性を維持することはできるのか? できない 同程度の損失を出すノード集合は, 一意ではない ネットワークの信頼性を維持するノード集合ではない 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 6 / 20
社会基盤として通信ネットワーク ネットワークの信頼性に関する最近の懸念 スケールフリーネットワークはハブ攻撃に弱い しかし 次数の高い少数のノード破壊で, - すぐに非連結化 - 最大連結成分のサイズが小さくなる これらの指摘に対するこれまでのネットワーク設計法は使えない なぜなら - コスト最小化を追求していない - 信頼性の確保が実はできていない 信頼性の高いネットワーク設計に関するアプローチがない 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 7 / 20
通信ネットワーク設計 高い信頼性が必要 一部が故障しても通信が継続できること 信頼性 の評価尺度は ネットワークやアプリケーションに依存する コストは小さいことが望ましい コストをかければ信頼性は高まるのは自明 必要な信頼性を最小コストで実現することが必要 通信ネットワーク設計 目的関数 : コスト 最小化 制約条件 : 必要な信頼性を満たすこと など最適化問題 通信ネットワーク設計は最適化問題として扱える 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 8 / 20
リンク ノード保護による高信頼化 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
リンク ノード保護による高信頼化 壊れないように 頑健化 ルータ それ以外のノードが破壊しても 通信ネットワークの信頼性は 保たれる 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 10 / 20
リンク ノード保護による高信頼化 リンク ノード保護による高信頼化設計 リンク ノードの高信頼化のためのコストを抑えたい 保護リンク以外の任意の同時 k リンク故障に対しても 直径が指定値以下, サーバと連結しているノード数が指定値以上 などの制約条件の下で保護リンク数最小化 保護ノード以外の任意の同時 k ノード故障に対しても 最小連結成分のサイズが指定値以上 などの制約条件の下で保護ノード数最小化 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 11 / 20
分断抑制点保護問題 (PNC) 最小連結成分のサイズの下限 Instance : 無向グラフ G =( V, E ) 正整数 p, k, L 保護点数 同時削除点数 QuesCon : G にサイズが p 以下の ( k, L ) - 保護点集合 V p は存在するか? V p に含まれないどのような k 個の点を取り除いても, 点を除かれたグラフの各連結成分の点数は L 以上 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 12 / 20
分断抑制点保護問題 (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
削除点数が 1 の場合の多項式時間 アルゴリズム 削除 k=1 L=4 p=1 連結成分のサイズ 8 (1) 点をグラフから削除する (2) 残ったグラフの最小連結成分のサイズを調べる (3) L より大きいので何もしない 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 14 / 20
削除点数が 1 の場合の多項式時間 アルゴリズム 削除 k=1 L=4 p=1 連結成分のサイズ3 次の点でも同じ操作を行う (1) 点を削除 (2) 残ったグラフの最小連結成分のサイズを求める (3) Lより小さいので保護ノードとする 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 15 / 20
削除点数が 1 の場合の多項式時間 アルゴリズム 保護点 削除 k=1 L=4 p=1 この操作 (1) (3) を全ての点に行う 連結成分のサイズ 4 (4) 保護ノード数が p より大きいなら解はなし 保護ノード数が p より小さいなら保護ノードを出力 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 16 / 20
削除点数が 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
ノード保護の例 CAIDA で公開されている ISP バックボーンネットワークの グラフ構造に対して保護ノードを調べた ISP n m L p No.1 22 25 21 5 No.2 82 92 81 20 No.3 14 19 13 2 No.4 48 53 47 21 No.5 78 110 77 17 No.6 14 26 13 1 No.7 13 12 12 4 No.2(L=80) 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 18 / 20
ノード保護の例 CAIDA で公開されている ISP バックボーンネットワークの グラフ構造に対して保護ノードを調べた ISP n m L p No.1 22 25 21 5 No.2 82 92 81 20 No.3 14 19 13 2 No.4 48 53 47 21 No.5 78 110 77 17 No.6 14 26 13 1 No.7 13 12 12 4 9 8 3 4 7 2 6 10 0 11 12 1 No.3(L=12) 5 13 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 19 / 20
まとめ ネットワーク分断を抑制するノード保護問題 (PNC) を定義 PNC は一般に NP 完全であることを証明 PNC において, 同時故障ノード数が 1 である場合に対する 多項式時間アルゴリズムを設計 PNC において, 同時故障ノード数が 2 である場合に対する 2 近似多項式時間アルゴリズムを設計 選択的ノード破壊によるネットワーク分断に耐性のある最適ネットワーク設計 20 / 20