今日、インターネットに代表されるコンピュータネットワークは、人々の生活および社会に欠かすことのできない重要で密接なものである．
そのため、ネットワークで障害が起きた際には、早い障害復旧が望まれる。しかし、大規模なネットワークでは構成要素が多いため、障害推定は複雑で、十分な調査や経験が必要とされる。そこで、本研究は人間の経験や勘に頼らないネットワーク障害推定の開発を目指す。
従来よりネットワーク障害における故障箇所同定の研究が行われてきた。屏ら[1]はOSPF のLSA 広報パターンを基に、故障箇所の同定を行う手法を提案した。彼らの手法の中で、LSAの広報パターンから具体的な障害への辞書的なデータを用意する必要があった。彼らは、「自律ルータ障害」など、故障を意味毎の単位で分割し、それ毎に経路制御アルゴリズムであるOSPF の振る舞いを明かにし、経路制御中に生成されるLSAのパターンを導いていた。本研究の当初の目的は、元々屏らの手法で必要とされる、LSA広告パターンから障害パターンへの辞書を効率よく生成する手法を開発することであった。そこで、まず障害パターンを効率よく扱う技術が必要となる。しかし、Line 状のネットワークや木構造などの冗長構造を持たないネットワークにおいては、構成機器すべてが完璧に動作した時のみネットワークが正常に動作し、それ以外の状態では特定の端点から別の特定の端点への通信は途絶えてしまう。すると障害パターンとして端点から端点への通信の不能から導かれる機器故障のパターンは、機器数に対して2 のべき乗数となってしまう。
ところが、近年、ZDD という論理式を高効率で圧縮して表記できる手法が開発された[2],[3],[4]。そして、これのアプリケーションとして、大量のグラフの要素からなる集合を演算できるツールであるGraphillion が開発された[5]。Graphillion はPython 言語のライブラリとして実装されている。GraphillionではUniverse として設定したグラフに対して、部分グラフ全体集合や、Path の全体集合を得ることができ、さらに、集合演算も可能である。さらに、辺重みに対して、集合の要素を辺重みの合計値の順に取り出すこともできる。Graphillion により、電力網の電力故障の組み合わせを選択する手法が開発されている[6]。
本研究では、このGraphillion を用いて、ネットワーク内のノード間の通信ができているかできていないかの情報を与えて、どの通信リンクが切れている可能性が高いかを可能性の高い順に表示するツールを提案する。
2.1 グラフ
2.1.1 グラフの基本
グラフとは頂点とそれを結ぶ辺からなるもので、辺に向きがないグラフを無向グラフ、辺に向きがあるグラフを有向グラフとよぶ。
図2.1.1-1：無向グラフの例
図2.1.1-2：有向グラフの例
互いに接続している頂点の列をパスと言う。頂点iと頂点jのパスの中で最も辺の数が少ないパスを距離という。
そして無向グラフにおいて、全ての頂点の組合せについてパスがある場合、そのグラフは連結であると言う。
頂点に接続している辺の数をその頂点の次数、有向グラフにおいては出る辺の数を出次数、入る辺の数を入次数と言う。
2.1.2 典型的なグラフ構造
- サイクルグラフ
頂点を環状につないだグラフ
図2.1.2-1：サイクルグラフの例
- 正則グラフ
-
全ての頂点の次数が等しいグラフ
図2.1.2-2：正則グラフの例
頂点の次数がkの正則グラフを「k-正則グラフ」または「次数kの正則グラフ」と呼ぶ。
(a)0-正則グラフ (b)1-正則グラフ (c)2-正則グラフ (d)3-正則グラフ
図2.1.2-3：k-正則グラフ
- 完全グラフ
-
任意の2頂点間に辺があるグラフ
図2.1.2-4：完全グラフの例
- スモールワールドグラフ
-
任意の2つの頂点が中間にわずかな数の頂点を介するだけで接続されるという性質を持つグラフ。
図2.1.2-5：スモールワールドグラフの例
平均距離Lを次のように定義する。
ノードiに隣接するk個のノードがある
時、クラスタ係数Ciを次のように定義する。
クラスタ係数Ciは隣接してい
るノード間が隣接している割合を表す。
また、全ノードのクラスタ係数の平均を平均クラスタリング係数という。
スモールワールドグラフを定義すると、「小さい平均距離を取りながら、大きなクラスタ係数を持つグラフ」である。スモールワールドグラフでは平均距離LはlogN程度に比例する。
スモールワールドグラフの生成モデル
スモールワールドグラフの生成モデルにWSモデル（Watts and Storogatz model）がある。WSモデルのパラメータはノード数N、各ノードの次数K（Kは偶数）、確率βである。
パラメータは次の関係を満たす。
WSモデルがスモールワールドグラフを生成する手順は以下のとおりである。
まず、各ノードに
n0…n(N-1)とラベ
ルを付けた際に、辺を(ni
,nj)と表わし、下の条件式を
満たすようにノード数N、各ノードの次数
がK（Kは偶数）であるサイクルグラフを作
る。
次に、作ったサイクルグラフの各辺(ni ,nj)を確率βで(ni ,nk)に張り替える。このとき、kはi≠k かつ、辺の重複が起こらない範囲内で一様な確率で決定される。
WSモデルのパラメータβを0にすると次数Kのサイクルグラフ、１にするとランダムグラフになる。
- スケールフリーグラフ
-
1部の頂点が他のたくさんの頂点と辺で繋がっており大きな次数を持っている一方で、大多数の頂点はごくわずかな頂点としか繋がっておらず、次数は小さいという性質を持ったグラフ。大きな次数を持つ少数の頂点をハブと呼ぶ。
図2.1.2-6：スケールフリーグラフの例
スケールフリーグラフの次数分布は冪法則に従う。
つまり、枝の数がkである頂点の数を
N(k)とすると、N(k)は次の式を満たす。
スケールフリーグラフの生成モデル
スモールワールドグラフの生成モデルにBAモデル（Barabási-Albert model）がある。BAモデルのパラメータはノード数N、新規ノードから既存ノードへ張る辺の数mである。
ただし、1 ≤ m < nを満たさなければならない。
BAモデルがスモールワールドグラフを生成する手順は以下のとおりである。
m個のノードからなる完全グラフKmに対して、新しい頂点niを1個追加する。その頂点からm個の頂点に対して(6)式の確率で辺を張る。これをノード数がNになるまで繰り返す。
2.2 BDD
BDDはグラフ構造による論理関数の表現である。BDDは論理関数の値をすべての変数について場合分けした結果を2分決定木で表わし、これを圧縮することにより得られる。さらに開始ノードから降りて行ったとき、どの経路でも変数の出現順序が同じものを順序付きBDDと呼ぶ。以降、慣例に基づき、1を表す有向辺をラベル1を付けて実線の矢印で、0を表す有向辺をラベル1を付けて点線の矢印で表わす。なお、一般の有向辺はラベルなしの実線の矢印で表わす。
圧縮は次の規則に従って行う。
- ①：0でも1でも分岐先が同じ場合は分岐節点を削除して直結(図2.2-1)。
- ②：等価な節点は共有する(図2.2-2)。
図2.2-1：圧縮規則①
図2.2-2：圧縮規則②
ここでF(a,b,c)=(a∧ ¬b ∧c) ∨ ((¬a)∧b∧(¬c))という論理関数を表す例を示す。F(a,b,c)の2分決定木は、図2.2-3になり、これを圧縮することにより得られるBDDは図2.2-4になる。
図2.2-3：F(a,b,c)における2分決定木
図2.2-4：F(a,b,c)におけるBDD
2.3 ZDD
ZDD(Zero-suppressed binary Decision Diagram : ゼロサプレス型2分決定グラフ)は、1996年に湊が考案・命名したデータ構造[2],[3],[4]で、BDDに対しさらに圧縮規則を加えるものである。
ZDDはBDD(binary Decision Diagram : 場合分け2分木)を圧縮規則に従って圧縮することにより得られる。ここでいうBDDは各節点にアイテム名を表すラベルが割り当てられており、0と1のラベルが付与された2本の枝が分岐している。以降では0のラベルを持つ枝を0-枝、1のラベルを持つ枝を1-枝と表現する。1-枝はその節点のアイテムを採用する事を意味し、0-枝はその節点のアイテムを採用しない事を意味する。
ZDDの圧縮規則は下の通りである。
- ①：0の葉を指す1-枝を持つ節点を取り除き、取り除いた節点に向かって入る有向辺を0-枝に直結させる(図2.3-1)。
- ②：等価な節点は共有する(図2.3-2)。
図2.3-1：圧縮規則①
図2.3-2：圧縮規則②
ここでF(a,b,c)=(a∧ ¬b ∧c) ∨ ((¬a)∧b∧(¬c)) という論理関数をZDDで表現した例を示す。F(a,b,c)の2分決定木は図2.3-3になり、この2分決定木にBDD圧縮規則を適応することにより図2.3-4に示すBDDが得られ、このBDDにZDD圧縮規則を適応することにより図2.3-5に示すZDDが得られる。
図2.3-3：F(a,b,c)における2分決定木
図2.3-4：F(a,b,c)におけるBDD
図2.3-5：F(a,b,c)におけるZDD
図2.3-4、図2.3-5からZDDはBDDに比べてコンパクトに表現できる事が分かる。論理式によっては要素の数に対して指数関数的なサイズの比になる。したがって、前述のBDDを改変してZDDを構築するのは効率が悪い。
さて、ZDDにはZDD同士で集合演算ができるという性質がある。この性質を利用してZDD同士の集合演算を繰り返し行うことにより、目的のZDDを構築する方法を湊らは開発している[7]。また、KnuthはZDDを構築するより高速なアルゴリズムSimpathを開発した[3]。
2.4 NetworkX
NetworkX[8]はスケールフリーグラフなどの様々なグラフの生成、操作を行うことできるPythonライブラリである。NetworkXにおいて、グラフは1つのオブジェクトとして取り扱う。
2.5 Graphillion
Graphillionパッケージはグラフ集合演算をZDDを利用して高速に行うPythonライブラリである。全体グラフをset_universeメソッドで指定し、サブグラフの集合を扱える。Graphillionはグラフを辺のリストとして表現し、辺は頂点のタプルとして表わす。図2.5-1のグラフは式(2-7)のように表現する。
図2.5-1：無向グラフの例（再載）
Graphillionを用いると、全サブグラフの集合の他、2頂点間のパスリスト、集合同士の演算、重み順の列挙、要素の数え上げなどを行うことができる。なお、Graphillionは頂点集合を扱えない。
3.1 Simpathのアルゴリズム
Knuthは与えられたグラフの2頂点s,tを結ぶパス(s-tパス)を全列挙するアルゴリズムSimpathを示した[3]。これはs-tパス集合を表すZDDを構築するアルゴリズムである。
Simpathアルゴリズムは、与えられたグラフの辺にE={e1, e2, e3…em}という順序をつける。s-tパスが辺eiを採用する場合は１-枝、採用しない場合は0-枝という場合分けをe1から順に繰り返していき、幅優先探索で2分決定木を作成していく。
ただし、2分決定木を作成していく段階で、s-tパスにならないと分かった場合は枝をその時点で0の葉に直結させる。0-葉はs-tパスが成立しないことを意味する。例えば、図3.1-1の様なグラフにおいて、e1=0, e2=0ならばs-tパスができることはない。よって図3.1-2のようなZDDになる。また、e1=1, e3=1の場合も分岐が生じてしまうため、s-tパスができることはない。よって図3.1-3のようなZDDになる。
図3.1-1：グラフの例
図3.1-2：構築中のZDD1
図3.1-3：構築中のZDD2
さらに、Simpathでは“等価な途中状態”を持つ複数の葉を1つに共有する。“等価な途中状態”とは残りの辺の取捨選択によってs-tパスになるか否かが同じ結果になる辺の組合せを意味する。
図3.1-4と図3.1-5を比較すると、どちらもv2とtを結ぶとs-tパスが完成する。つまり、図3.1-4と図3.1-5において、以降の辺の取捨選択は全く同じになる。この状態を等価な途中状態という。等価な途中状態を見つけることができれば、以降のZDDの木の共有ができる（図3.1-6）。
図3.1-4：等価な途中状態のグラフの例1
図3.1-5：等価な途中状態のグラフの例2
図3.1-6：等価なグラフの共有
Simpathでは等価な途中状態を持つ葉を一つに共有させることで計算量の大幅な短縮を実現している。等価な途中状態を見つけるために、フロンティアと呼ばれる処理済みの辺と未処理の辺の両方に接続する頂点集合に含まれる頂点が「端点であるか否か、端点である場合にはもう一方の端点はどこか」ということを途中状態の情報として記憶する。この途中状態の情報をmateと呼ぶ。つまり、図3.1-4と3.1-5はそれぞれ同じmateを持つ（図3.1-7）。
図3.1-7：同じmateを持つグラフ
3.2 LSAの広報パターン解析に基づくOSPF障害特定
屏らはOSPFネットワークにおける複数のLSAの関連性、LSAの遅延を考慮したLSAの監視と解析を行うことで、「どのような障害が起きているのか」を特定する手法を提案している[1]。
OSPFは動的ルーティングを実現するアルゴリズムである。ネットワーク内のルータはネットワークの障害を監視し、ルータとネットワーク接続状況をリンクステート広告（LSA）としてネットワーク内にマルチキャストを行う。
そのため、ネットワークの障害が発生したときにはそれに対応したLSAを受信することができる。しかし、LSAは各ルータが見たネットワークの接続状況しか送ってこない。そこで彼らは典型的なネットワークの故障に対するLSAのパターンを導き受信したLSAから故障を導けるようにした。
彼らは、検出可能な障害を意味毎に分割して図3.2-1のように定義し、それぞれの障害に対応するLSAの広報パターンを導いている。
- 自律ルータ障害：ルータの再起動など自律的にルータプロセスが落ちる障害
- ルータ障害：不意にルータプロセスが落ちる障害
- トランジットネットワーク障害：トランジットネットワーク全体の障害
- P to Pリンク障害：Point-to-Pointリンクの障害
- トランジットネットワークリンク障害：トランジットネットワークに接続するリンクの障害
- スタブネットワーク障害：スタブネットワークの障害
- エリア外ネットワーク障害：エリア外のプレフィックスが広報されない障害
- 外部ネットワーク障害：外部ネットワークのプレフィックスが広報されない障害
図3.2-1：障害の分類
なお、彼らの手法はネットワークのトポロジーや規模により、LSAのパターンを上手く取り扱えるかについては明らかでない。
本研究では発生確率の高い故障順に故障パターンを出力するのでこの問題を解決している。
3.3 電力網解析
井上らは、電力網において、電線スイッチ故障の組合せを列挙する手法を提案している[2]。
電力網において、ノードは家庭あるいは電気を供給する変電所を指す。電力網の目的は全家庭に安全に電気を供給することである。目的を達成するために制約を設ける。この制約を破るような電力網を故障電力網とする。制約の例を図3.3-1に示す。
図3.3-2のような電力網があるとする。図3.3-2におけるa,b,c,d,eはそれぞれ電線スイッチを意味する。図3.3-2の電力網における実行可能な電線スイッチの構成を図3.3-3に示す。
もし、スイッチaとスイッチbが故障すると、実行可能な構成を作れなくなる。つまり、スイッチaとスイッチbの組合せが列挙する組合せの一つである。
図3.3-1：構造制約と電気制約の例
図3.3-2：電力網の例
図3.3-3：実行可能な構成の例
彼らはZDDに圧縮したグラフ同士の集合演算により、全ての実行可能解に共通する部分集合を列挙することにより、実行可能な構成をなくしてしまうような電線スイッチ故障の組合せを求めている。
本研究ではグラフトポロジー、各辺の故障確率は判明している。頂点間の通信の可能性、不可能性から故障パターンを出力するプログラムをGraphillionを用いて構成する。初めに、単純な例を用いてアルゴリズムの概要を示す。
4.1 単純故障による例
図4.1-1：ネットワーク例
Python言語では丸括弧内で要素をカンマで区切ったデータをタプルと呼ぶ。また角カッコ内で要素をカンマで区切ると線形リストを表す。Graphillionでは2要素のタプルを辺とし、2要素のタプルの線形リストを、辺集合とみなすグラフとして取り扱う。図図4.1.1のグラフの表現は(4-1)式となる。
(1)Python において、Graphillionライブラリをロードし、取り扱うグラフを図1に設定するには次の手順を行う。
(2)そして、図1の全サブグラフ（サブグラフの制約無し）は一命令で得られる。
これにより、変数sgは(4-2) 式の値になる。
(3)さて、ここで、ノード1 とノード3 との通信が途切れたとしよう。すると、ノード1 とノード3 の間のすべての経路において、どこかが切断されていることになる。まず、ノード1 とノード3 の間の全経路は次で得られ、pの値は(4-3)式のようになる。
この経路を含んでいるサブグラフはノード1 とノード3の間で通信可能であると考えられる。従って、この経路を含まないサブグラフ全体が、ノード1 とノード3 間で通信不能なネットワークとなる。この様な計算は下記により行うことができ、変数dcの値は(4-4)式のようになる。
これで故障している可能性のあるネットワークをすべて見つけることができた。
(4)さて、この故障している可能性のあるネットワークであるが、それぞれのネットワークに対して、補グラフを求めると、それが故障箇所になる。変数comp は(4-5) 式となる。
(5)ここで、Graphillionには、このグラフの集合に対して、辺重みの合計値に対して大きい順に出力する機能がある。各辺eの故障が独立に起き、辺e故障の確率がexp(pe) で与えられると仮定する。そして、故障ネットワークの辺の重みとして、peを与える。
すると、グラフG の辺集合をE(G)で表した場合、故障ネットワーク辺重みの合計値は(4-6) 式で計算できるので、これは発生確率の対数値になる。
対数関数は単調増加関数であるから、辺重みの合計値の大きい順に表示することは、確率の大きい順に表示する事と等価である。
表4.1-1 ネットワーク辺故障確率例
| 辺 |
確率 |
| (1,2) |
10-5 |
| (1,3) |
10-5 |
| (2,3) |
10-3 |
先ほどの例において、各辺の故障確率の想定値が表4.1-1 の通りだとする。すると、対数関数は一様増加関数なので、対数の底の違いは全体の大小関係には影響しないので、辺重みとしてそのまま指数部分を与えることとする。すると下記の表示を得ることとなる。
これらが故障する確率は表4.1.2の通りなので、表示順序は正しい。
表4.1-2 故障確率の計算例
| 障害箇所 |
確率 |
| (1,2),(2,3) |
10-8 |
| (1,2),(1,3) |
10-10 |
| (1,2),(1,3)(2,3) |
10-13 |
4.2 通信可能なノード対の指定
ノード1とノード2とは通信ができているなど、特定のノード間で接続が確認できている場合の計算は次のように行う。
前節ではuniverseに設定されたネットワークに対して、全てのサブグラフを対象にして、通信不能なノード対の経路を取り除いた。もし、特定のノード対間で通信が行える場合、そのノード間の経路を含んでいるサブグラフだけを対象にする必要がある。
そのため、前節の(2)サブグラフ全体を求めた後、(3)不通の経路を求める前に、対象となるネットワークの集合をサブグラフ全体集合ではなく、ノード間の経路を一つ以上含むサブグラフに限定する必要がある。そのためには、指定のノード間の経路を一つも含んでいないサブグラフを取り除く必要がある。この計算は次のように行う。例としてノード1とノード2が通じるとすると、変数sgの値は(4-7)式となる。
4.3 実装
実際の実装はA.付録に示した。実装にはオブジェクト指向を用いた。
- （1） Network クラスのコンストラクタの引数には、ネットワークの構造を与える。また、辺の重みの辞書や、デフォルトの重みを指定することもできる。
- （2） 次に不通のネットワークのノード対のリストをsetNoConnectionメソッドで与える。
- （3） 次に必要であれば、接続が確認できているノード対のリストをsetConnection メソッドで与える。
- （4） 故障リンクのリストの集合はfailuresメソッドで得られる。また、iterメソッドで確率の大きい順に故障リンクリストを取り出せる。
以下に使用例のプログラムを示す。
Python 2.7.10 (default, Oct142015, 16:09:02)
[GCC5.2.120151010] on linux2
Type"help", "copyright", "credits" or "license
"for more information.
>>>from proposalsystem import Network
>>>o = Network([(1,2),(2,3),(1,3)])
>>>o.setNoConnection([(1,3)])
>>>o.weight=f(1,2):..5,(1,3):..5,(2,3):..3g
>>>for g in o.iter():
>>> print g
...
[(1,3),(2,3)]
[(1,2),(1,3)]
[(1,2),(1,3),(2,3)]
>>>o.setConnection([(1,2)])
>>>for g in o.iter():
>>> print g
...
[(1,3),(2,3)]
5.1 実験の目的
提案アルゴリズムの有効性を検証する。そのために、図5.1に示す代表的な5つのネットワークモデルに対して故障箇所を推定する計算時間が現実的であるか調べる。
図5.1-1：実験グラフ(a):サイクルグラフ,(b)正則グラフ,(c)完全グラフ,(d) スモールワールドグラフ,(e)スケールフリーグラフ
5.2 実験の方法
実験環境は以下の通りである。
- PC名：HP Pavilion Slimline s5350jp
- OS：Windows7 Home Premium 64bit
- CPU：intel CORE i7 860 @ 2.80GHz
- メモリ：4GB
- プログラム実行環境：Python2.7.8
実験1： サイクルグラフ、完全グラフ、正則グラフ、スモールワールドグラフ、スケールフリーグラフの5つのグラフトポロジーに対して頂点数を変化させた時の提案アルゴリズムの実行時間を求める。各グラフの生成にはNetworkXライブラリを用いた。
正則グラフについては次数が3の場合と4の場合でそれぞれ測定した。
スモールワールドグラフのパラメータについては各ノードの次数K＝6,確率β=0.01とした。スケールフリーグラフのパラメータについては新規ノードから既存ノードへ張る辺の数m=2とした。
実験2：大きすぎる頂点数に対してはPC から返答が返ってこなくなるので， 各グラフトポロジーに対して提案アルゴリズムの測定限界の頂点数を求める.
5.3 実験結果
実験1：提案アルゴリズムの実行時間の測定結果を時間軸が対数の方対数グラフにまとめたものを図5.3-1に示す。
図5.3-1：頂点数対提案アルゴリズム実行時間方対数グラフ
実験2：各グラフにおける提案アルゴリズムの限界頂点数の測定結果を表5.3-1に示す。
表5.3-1 提案アルゴリズムの限界頂点数
| グラフトポロジー |
限界頂点数 |
| サイクルグラフ |
3924 |
| 正則グラフ |
38（次数3
22（次数4） |
| 完全グラフ |
10 |
| スモールワールドグラフ |
17 |
| スケールフリーグラフ |
35 |
5.4 実験のまとめ
図5.3-1の方対数グラフを見ると、およそ線形になっていることが確認できる。このことから、アルゴリズムの実行時間はグラフの頂点頂点数にたいして指数関数的に増加することが分かる。
図5.3-1を見ると、同頂点数で比較するとサイクルグラフが最も実行時間が短く、完全グラフが最も実行時間が長い。また、表5.3-1を見るとアルゴリズムの限界頂点数においてはサイクルグラフの限界頂点数が最も大きく、完全グラフ限界頂点数が最も小さい。
このことから、提案アルゴリズムの実行時間および限界頂点数はグラフの辺の数に大きく依存すると考えられる。
Pythonによるアルゴリズムの実装を下に示す.
from graphillion import GraphSet
class Network:
def __init__(self,topology,weight={},dw=-3):
self.topology=topology
self.weight=weight
self.defaultWeight=dw
self.conList=[]
self.noList=[]
def weightDic(self):
w={}
for e in self.topology:
if e in self.weight:
w[e] = self.weight[e]
else:
w[e] = self.defaultWeight
return w
def setConnecting(self,conList):
self.conList = conList
def setNoConnection(self,noList):
self.noList = noList
def failures(self):
GraphSet.set_universe(self.topology)
connects = GraphSet({})
for connect in self.conList:
paths=GraphSet.paths(connect[0],connect[1])
connects = connects - connects.excluding(paths)
for connect in self.noList:
paths=GraphSet.paths(connect[0],connect[1])
connects = connects.excluding(paths)
return connects.complement()
def iter(self):
return self.failures().max_iter()