ネットワークシステムにおける可用性測定

信頼性工学の分野では、故障率とフォールトツリー解析（FTA）を用いて、複数の機器で構成される装置全体の稼働率を数値で導出することでシステムの可用性を定量的に導出できると考えられますが、それを実際のネットワークシステム（NS)に適用するのは非常に困難であり、現実的ではありません。

そこで、モデルを用いて、NSにおける各階層ごとの通信の依存関係を考察し、その依存関係を抽出するアルゴリズムを提案することで、よりNSに適した可用性の導出方法を検討します。

可用性の阻害とリンクの依存関係

可用性が阻害される原因として、通信路の故障やアクセス制御状態の不慮の変化が挙げられます。一般的に通信路とは、Layer1（L1）における物理的な配線を指しますが、データ処理は階層内、階層間で行われるため、この部分も通信路と捉えるべきであると言えます。したがって、NSの可用性は各レイヤの通信路を考慮しなければなりません。それら通信路が切断され得る状況としては、L1内ではLANケーブルなどの破損、L2以上ではアクセス制御状態の不慮の変化による通信路の遮断などが考えられます。

右図の冗長化されていないNSにおいて、L1のリンク（10, 11）が切断された場合、その上位のレイヤにおける通信も維持できなくなるため、リンク（7, 8）、（5, 6）、（3, 4）、（1, 2）も切断されます。一方、冗長化されたNSにおいては、L1のリンク（29, 30）が切断された場合、先程と同様に上位のリンク（23, 24）、（17, 18）も切断されますが、L4のリンク（15, 16）は、L1のリンク（29, 31）に基づく冗長化された通信路が存在するため、切断されることはありません。

また、L2のリンク（23, 24）が切断された場合、その上位レイヤのリンク（17, 18）は切断されますが、下位レイヤのリンク（29, 30）は切断されません。これは、経路制御の異常が物理的な断線を引き起こすことは考え難いためです。
このように、NSにおける通信路には
  1. 下位レイヤのリンクの切断は階層間の依存関係により上位レイヤのリンクに影響を及ぼすが、冗長化によって影響を及ぼさない場合が存在する
  2. 上位レイヤのリンクの切断が下位レイヤのリンクに影響を及ぼすことはない

という大きく2つの依存関係が存在します。

リンク依存関係の抽出

上記の依存関係から、リンクが切断されるという事象は、リンクそのものに障害が起きた場合のみならず、下位レイヤのリンクの障害が起きた場合も、その依存関係により引き起こされるということが判明しました。このことを踏まえ、リンクの依存関係を抽出するアルゴリズム（以降アルゴリズム）を提案しました。

アルゴリズムを用いて、上の[冗長化されたNS]のモデルにおいて、L5のノード13、14を接続するリンクの依存関係を抽出します。まず、ノード13，14の下位レイヤ（L4）のノードを見ると、ノード15，16があります。ノード15，16を両端とする通信経路（以降パス）を構成するリンクの集合（以降リンク群）を抽出すると、このパス[15, 16]は冗長化されていないため、リンク群はリンク(15, 16)のみであることが分かります。続いて、ノード15，16の下位レイヤ（L3）のノードを見ると、ノード17，22があります。パス[17, 22]を構成するリンク群を抽出すると、リンク群(17, 19)、(19, 21)、(21, 22)とリンク群(17, 18)、(18, 20)、(20, 22)という2つのリンク群があり、冗長化がなされていることが分かります。

ここで、リンク依存関係を考えます。パス[17, 22]を構成するリンク群の1つであるリンク群(17, 19)、(19, 21)、(21, 22)において、3つのリンクの中の1つでも切断されてしまうと、このリンク群は通信経路としての用をなしません。つまり「リンク群は自らを構成するリンクのいずれかが切断しても用をなさない」と言えます。次にパスを見てみると、片方のリンク群が用をなさなくなっても、もう片方のリンク群が健在であれば、そこを通信経路とすることができます。しかし、リンク群が両方とも用をなさなくなると、パスは通信ができません。つまり「パスは自らを構成するリンク群が全て用をなさなくなると通信経路にならない」と言えます。これがリンクの依存関係です。

以降も、抽出されたリンク群の要素（リンク）に対し同様の操作を行い、L1までパスを構成するリンク群の抽出を行うことで、NS全体のリンク依存関係を抽出できます。

アルゴリズムを用いて、下左図（NSQモデルによるNS）の依存関係を図に起こしたものが下右図（リンク依存図）となります。

リンク群はパスを構成するリンクの集まりを意味しているため、リンク群の要素が1つでも消滅した場合はリンク群自体が意味を成しません。このため、たとえば[18, 36]のリンク群は要素(18, 19)、(19, 35)、(35, 36)のいずれかが消滅するとリンク群は用をなさなくなるため消滅し、この影響で[18, 36]も消滅します。このパスの消滅は、矢印に沿った上位レイヤのリンクやパスにも影響を及ぼし、同様の作業を繰り返すことでリンク切断の影響範囲が明らかになります。一方、[3, 4]では冗長化によりリンク群が2つ存在するため、片方のリンク群が消滅してももう片方のリンク群によって[3, 4]は存続します。このような場合には、上位レイヤには影響を及ぼしません。

これらのアルゴリズムにより、各通信の依存関係とリンク切断の影響範囲が判断可能となります。

稼働率

リンク依存関係抽出アルゴリズムにより、各レイヤの通信の依存関係を考慮した稼働率計算が可能になります。また、リンク切断時の影響範囲も判別可能であることで、リンク切断によるNSの稼働率への影響を考察することができます。NSの稼働率をリンク依存図の頂点にあるパス稼働率とみなし、考察を行いました。

リンク群稼働率

リンク群を構成するリンクは、下位レイヤのパスに依存しています。よって、各レイヤのリンクは、依存する下位レイヤのパス稼働率と自身のリンクが持つリンク稼働率の積となります。ただし、NSQモデルではL5を抽象レイヤとしているため、L5のリンク稼働率は考慮しないこととします。リンク群Gk はパスを構成する集合であるため、すべて直列で構成されます。よって、リンク(i, j )（i, j は同一レイヤ内のノード）の稼働率をq(i, j) とすると、リンク群の稼働率Rkは右のように表すことができます。

パス稼働率

パスはリンク群に依存しています。パス内に複数のリンク群が存在するときは、両方のリンク群が稼働しない場合にのみパスは存続できないとして計算を行います。しかし、パスに存在する複数のリンク群の中に共通するリンクが存在すると、単純に計算を行えば重複を許したパス稼働率が導出されてしまいます。このため、パスを構成する複数のリンク群から共通のリンク稼働率を除いて計算しなければなりません。これらを考慮するため、最初に全てのリンク群の中で共通しているリンクがないかを調査し計算します。

次に、各リンク群から共通部分を除いたリンクを再グループ化して、パス稼働率の計算を行います。よって、共通するリンクの集合をM 、再グループ化したリンク群の集合をG’k とすると、パス稼働率P は右のように表すことができます。共通するリンクが存在する場合の具体例を以下に示します。

S、Gはそれぞれ通信の始点、終点を意味しています。この例では(S, 1), (6, G) が共通するリンクとなります。このような場合は上記の計算式でパス稼働率の計算が可能ですが、例外も存在します。

このネットワークを見ると、各リンク群の中に共通するリンクが複数散らばっていることがわかります。このような場合は、すべてのリンク群の中に共通するリ ンクが存在するわけではないため、上記の計算式を用いることはできず、共通部分を抜き出して厳密解を求めるためには複雑な作業を必要とします。そこで、信頼性工学において「最小パスセット」「最小カットセット」と呼ばれるものを抽出し、稼働率の上限と下限による近似解によって稼働率を導出します。

最小パスセットと最小カットセット

パスセットとは、全体集合Tのうち、Iに属する要素がすべて正常ならシステムが正常となる部分集合を言います。あるパスセットの部分集合にパスセットとなるものが存在しないとき、そのパスセットを最小パスセットと呼びます。上の[リンク群の一部に共通するリンクが存在する場合]を例にあげると、{1, 2}, {3, 4}が最少パスセットとなります。{1, 2, 4}などはパスセットではありますが、最少パスセットではありません。

続いてカットセットとは、全体集合Tのうち、Iに属する要素が全て故障するならシステムが故障となる部分集合を言います。あるカットセットの部分集合にカットセットとなるものが存在しないとき、そのカットセットを最小カットセットと呼びます。上 の[リンク群のすべてに共通するリンクが存在する場合]を例にあげると、{1}, {6}, {2, 4}, {2, 5}, {3, 4}, {3, 5}が最少カットセットとなります。{1, 6}などはカットセットではありますが、最少カットセットではありません。

以上の事を踏まえると、リンク依存抽出アルゴリズムによって抽出された各リンク群は、リンク群を構成するどのリンクが切れても稼働しないため、最小パスセットとなります。よって、最小パスセットの非稼働率すなわちリンク群の非稼働率は右のようになります。

最小パスセットの非稼働率Hk は各リンク群の中から重複を含めずに1つずつリンクを抽出した場合であり、最少カットセットです。というのは、Hk 内のすべてのリンクが切断された場合にのみ、システムに障害が起こるためです。よって、Ck を最小カットセットの稼働率とすると、最少カットセットの非稼働率は右式のようになります。

このようにして最小パスセットを用いたパス稼働率の上限と最小カットセットを用いたパス稼働率の上限を計算することができます。よって、リンク群の一部に共通するリンクが存在する場合のパス稼働率は右式のようになります。

システム稼働率

システム稼働率をリンク依存図の頂点とみなすと、それはL5のパス稼働率であると言えます。パス稼働率について、下の図を用いて説明します。

このNSにおけるシステム稼働率は、[1, 2] のパス稼働率と等しくなります。[1, 2] において(1, 2)と、(1, 2) は[3, 6]と同じ値です。[3, 6] を構成するリンク群(3, 4)、(4, 5)、(5, 6) のリンク群稼働率と[3, 6] のパス稼働率は上記の計算式で導出され、この場合のリンク群稼働率とパス稼働率は等しい値となります。リンク群を構成するリンクの稼働率は、たとえば (3, 4) については、自身のリンク稼働率と[7, 10] のパス稼働率の積となります。

右図のようにL5のリンクが複数ある場合には、どのリンクが切れてもシステム障害とみなして計算を行うこととします。なぜなら、L5は要件として定義され ているため、同レイヤのリンクが切断されることはNSがサービスを正常に提供できないことと同義であるためです。よってこの場合は、[1, 2]、[2, 3]、[3, 4] のパス稼働率の積がシステム稼働率となります。