umeda_1118web(2).pptx

選択的ノード破壊による

ネットワーク分断に耐性のある

最適ネットワーク設計

 関西学院大学　理工学部　情報科学科

松井　知美　　巳波　弘佳    

現実のネットワーク

現実世界のネットワークの分析技術の進展    

!    ネットワークのデータ収集の効率化・高速化  

!    膨大な量のデータを解析できる    

     コンピュータ能力の向上    

 現実の複雑なネットワークを科学的に分析  

!    アルゴリズムの設計  

!    新たな性質の発見  

!    経験則の適用範囲の明確化  

!    ．．．

効用として，例えば   !    インターネット   !    WWWハイパーリンク構造        （Web  Graph）   !    知人関係   !    代謝ネットワーク   !    など  

現実のネットワーク  

現実のネットワークの例    

単純ではなく

複雑    

実ネットワークは

…

一見ランダムだが  

生成原理はありそう  

複雑ネットワーク    

(Complex Network)

インターネットにおけるAS(Autonomous  System)間の隣接関係図 h/p://sk-­‐aslinks.caida.org/data/2007/のデータに基づき，

複雑ネットワークが持つ性質

現実世界の複雑ネットワークが持つ性質の例：  

!    スケールフリー    

次数分布がべき乗則を満たすこと    

!    「平均的な次数」というものが        存在しない          （適当なスケールがない＝スケールフリー  ） !    大きな次数を持つ少数（だが        少なすぎない）の点（ハブ）   !    小さな次数を持つ多数の点   次数分布がべき乗則を満たす例     (Barabási & Albert, 1999)

collaboration

スケールフリーネットワーク

(Error  and  a/ack  tolerance  of  complex  networks,  R.  Albert  et.  al.)    

スケールフリーネットワークの特徴    :  

頑健性と脆弱性 ５％程度の点がランダムに破壊される

!    ランダムな点破壊には頑健

-ほとんど影響がない -平均経路長はほぼ変化しない 次数の高い上位５％が選択的に破壊される

!  選択的破壊には脆弱

-小さな連結成分に分断される -平均経路長は約２倍に増大する

“アドホックなスケールフリーネットワークの構築法,”    林 幸雄.   ランダムなリンクワイヤリング   しかし、 辺付加のコストが、辺により違う   コスト制約のあるネットワーク設計の観点か ら見て、   現実的とはいえない   リンク付加は現実のネットワーク設計で使うのは困難    ＆  リンク数を増やせば信頼性が上がるのは自明    ＆  最小コスト設計の観点からの研究はない

SFネットワーク設計(1)

リンク付加するとよい SFネットワーク設計　  :  

“DetecCng  CriCcal  Nodes  in  Sparse  Graph,”  A.  Arulselvan  et.  Al.  

ネットワークを分断するノード集合を決定する最適化問題

SFネットワーク設計(2)

なぜなら、ネットワークに重大なダメージを与えるノード が、 ネットワークの品質を保つノードと、直接イコールではな いから 同程度の損失を出すノード集合は，一意ではない つまり、これらのノード集合は、ネットワークの信頼性を 維持する意味合いでのノード集合ではない 各連結成分ができるだけ小さくなるように これらのノード集合を破壊すると 通信ネットワークの品質に重大なダメージを与える これらのノード集合を守れば、ネットワークの 信頼性を維持することはできるのか？ ならば 同程度の損失を出すノード集合は，一意ではない ネットワークの信頼性を維持するノード集合ではない できない

社会基盤として通信ネットワーク  

ネットワークの信頼性に関する最近の懸念    

信頼性の高いネットワーク設計に関するアプローチがない

スケールフリーネットワークはハブ攻撃に弱い       次数の高い少数のノード破壊で，    -  すぐに非連結化          -  最大連結成分のサイズが小さくなる       しかし     これらの指摘に対するこれまでのネットワーク設計法は使えない ASネットワークトポロジはコントロール困難だが     そのノード(AS)を破壊することは非現実的       スケールフリーと脆弱性に関する結果は       個別のネットワークトポロジに関して常に成立する結果では  ない  ことにも注意！       -コスト最小化を追求していない -信頼性の確保が実はできていない なぜなら

通信ネットワーク設計

高い信頼性が必要      

・  一部が故障しても通信が継続できること       ・  「信頼性」の評価尺度は          ネットワークやアプリケーションに依存する      

コストは小さいことが望ましい      

・  コストをかければ信頼性は高まるのは自明       ・  必要な信頼性を最小コストで実現することが必要    

通信ネットワーク設計  

通信ネットワーク設計は最適化問題として扱える  

目的関数：  コスト  ⇒  最小化     制約条件：  必要な信頼性を満たすこと        など         最適化問題

リンク・ノード保護による高信頼化

Link AB が保護されていない　 Link AB が保護されている　 IP 層　 下位 層　 A E _D C   B

Node  E Node  D

Node  C Node  B Node  A E _D C   B A   故障 故障 保護リンク 独立したバックアップリンク

Node  E Node  D

Node  C Node  B Node  A

リンク・ノード保護による高信頼化

ルータ 壊れないように 頑健化 それ以外のノードが破壊しても 通信ネットワークの信頼性は 保たれる

リンク・ノード保護による高信頼化

・  リンク・ノードの高信頼化のためのコストを抑えたい        

リンク・ノード保護による高信頼化設計      

・  保護リンク  

以外

 の任意の同時  k  リンク故障に対しても            「直径が指定値以下」，        「サーバと連結しているノード数が指定値以上」        などの制約条件の下で保護リンク数最小化       ・  保護ノード  

以外

 の任意の同時  k  ノード故障に対しても            「最小連結成分のサイズが指定値以上」        などの制約条件の下で保護ノード数最小化      

分断抑制点保護問題(

PNC)

無向グラフ　

G =( V, E )

正整数　

p, k, L

G

にサイズが

p

以下の

 

( k, L ) -

保護点集合

V

_p

は存在するか？

Instance      :

QuesCon    :

同時削除点数 保護点数 最小連結成分のサイズの下限

V

_p に含まれないどのような

k

個の点を取り除いても，   点を除かれたグラフの各連結成分の点数は

L

以上

分断抑制点保護問題(

PNC)

既知のNP完全問題である点被覆問題VCからの 多項式時間帰着により証明

定理１.

PNCは一般的にNP完全

定理2.

同時故障ノード数が1の場合における_{O(  n}2  _{+  nm  )アルゴリズムが存在する}

定理3.

同時故障ノード数が2の場合における_{2近似  O(  n}3  _{+  n}2_{(  1  +  m  )  +  m(  n+1)  )アルゴリズムが存在する}

削除点数が１の場合の多項式時間

アルゴリズム

(1)  点をグラフから削除する　

ｋ＝1

L＝４

p＝１　

(2)  残ったグラフの最小連結成分のサイズを調べる　　

連結成分のサイズ8　

(3)  Ｌより大きいので何もしない

削除

次の点でも同じ操作を行う　

(3)  Ｌより小さいので保護ノードとする　

連結成分のサイズ3　

(1)  点を削除　　　　(2)  残ったグラフの最小連結成分のサイズを求める

削除点数が１の場合の多項式時間

アルゴリズム

ｋ＝1

L＝４

p＝１　

削除

この操作(1)〜(3)を全ての点に行う　

(4)  保護ノード数がｐより大きいなら解はなし　

     保護ノード数がｐより小さいなら保護ノードを出力

連結成分のサイズ4　

削除点数が１の場合の多項式時間

アルゴリズム

ｋ＝1

L＝４

p＝１　

保護点 削除

幅優先探索を用いて O(  n  +  m  )   ①　点  v をグラフ  G  から削除 ②　最小連結成分のサイズを求める 　　 L より小さければ削除した点を保護点とする 　      点  v を復活させ①に戻る ③　|V_p| ≦ _p ならば保護点集合  V_p を出力 　　そうでなければ解なし 全ての点に対し，①②を繰り返す 無向グラフ  :

G

点数  :  

n

       辺数  :  

m

全ての点に対して実行      _{O(  n  )回}   O(  n(n  +  m)  )  

削除点数が１の場合の多項式時間

アルゴリズム

ノード保護の例

No.2（Ｌ＝80）　 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

CAIDAで公開されている  

ISPバックボーンネットワークの

グラフ構造に対して保護ノードを調べた

ノード保護の例

CAIDAで公開されている  

ISPバックボーンネットワークの

グラフ構造に対して保護ノードを調べた

7 12 11 13 8 9 10 ０ 3 4 6 1 2 5 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.3（Ｌ＝12）　

まとめ

・PNCは一般にNP完全であることを証明　

・PNCにおいて，同時故障ノード数が１である場合に対する　

　多項式時間アルゴリズムを設計　

・ネットワーク分断を抑制するノード保護問題(PNC)を定義　　　

・PNCにおいて，同時故障ノード数が2である場合に対する　

　2近似多項式時間アルゴリズムを設計