JP4981829B2 - Ｍｒｃファイル作成装置、ｍｒｃファイル作成方法およびそのプログラム - Google Patents

Description

本発明は、ＩＰ（Internet Protocol）網等のパケット交換網におけるルーチング技術に関する。

ネットワーク事業者において、ノードやリンクの故障の発生に対して、迅速に経路を切り替えることで故障復旧を行い、転送品質の維持を行うことが重要である。ＩＰ網における故障復旧方法として、ＯＳＰＦ（Open Shortest Path First）等のルーチングプロトコルを用いた故障復旧方法がある（非特許文献１参照）。このＯＳＰＦでは、故障を検知したノードは、全ノードから故障箇所を除いたトポロジデータベース情報をもとに迂回経路を計算し、自動的に転送経路を切り替える。しかし、ＯＳＰＦでは、ノードは故障発生後に迂回経路を計算するため、故障復旧に時間を要するという問題がある。

このような問題を解決する方法として、迂回経路を事前に計算しておくことで高速な故障復旧を実現するＭＲＣ（Multiple Routing Configurations)方式が提案されている。このＭＲＣ方式は、事前に迂回情報格納ファイル（以下、ＭＲＣファイルと呼ぶ）を用意しておき、故障発生時には、この故障に対応したＭＲＣファイルに基づき転送経路へ切り替えを行う。

ここで、図１１を用いて、ＭＲＣファイルについて説明する。ＭＲＣファイルは、与えられたトポロジに対し、通常ノードと、isolated nodeと、通常リンクと、isolated linkと、restricted linkとの組み合わせにより、故障時の迂回情報を示したファイルである。isolated linkは、故障リンクを示し、isolated nodeは、故障ノードを示す。また、restricted linkは、isolated nodeへの最終ホップとしてのみ利用可能なリンクである。

例えば、図１１の符号１０２に示す状態のＭＲＣファイル＃１は、符号１０１に示すようなノードＮ１〜Ｎ６からなるトポロジのＭＲＣファイルである。このＭＲＣファイル＃１において、（１）ノードＮ２，Ｎ３間のリンクが故障したとき、（２）ノードＮ２が故障したとき、（３）ノードＮ６が故障したとき、および、（４）ノードＮ１，Ｎ６間のリンクが故障したときの迂回経路を示す。ここで、迂回経路は、通常リンクを用いるが、restricted linkも、isolated nodeへの最終ホップとしてならば利用可能である。実際には、このＭＲＣファイルのisolated linkには非常に大きなコスト（例えば、ＯＳＰＦで規定される最大値「65535」）を設定することで、そのリンクを使用不能とする。つまり、ＯＳＰＦでは、できるだけ低いリンクコストのリンクを選択するので、このように非常に大きなリンクコストのリンクは選択されない。また、restricted linkには、このisolated linkよりも低いけれども、充分大きな値（例えば、すべての通常リンクのコストの合計値）を設定することで、最終ホップでのみ使用されるようにする。

なお、このように、ＭＲＣファイルにrestricted linkを設ける理由は、ノード間が通信不能となる原因が、リンク故障の場合とノード故障の場合との両方の可能性があるからである。例えば、符号１０１に示すトポロジにおいて、ノードＮ３，Ｎ２間が通信不能になる原因としては、（１）ノードＮ３，Ｎ２間のリンク故障、（２）ノードＮ２のノード故障等が考えられる。ここでもし、ノード間が通信不能となった原因が、（１）ノードＮ３，Ｎ２間のリンク故障であれば、例えば、ノードＮ４からノードＮ１への経路は、ノードＮ３を経由のものと、ノードＮ２経由のものとが考えられる。しかし、もしノードＮ３，Ｎ２間が通信不能となった原因が、（２）ノードＮ２のノード故障であれば、実際にはノードＮ４，Ｎ２間およびノードＮ２，Ｎ１間のリンクは通信不能なので、このリンクは迂回経路として使えない。したがって、例えば、符号１０２に示すＭＲＣファイル＃１のように、isolated nodeであるノードＮ２の少なくとも１本のリンクに充分大きなリンクコストの値を設定したrestricted linkを設けることで、通信不能な状態になった原因が単なるリンク故障であった場合の、ノードＮ２への到達性を確保することができる。また、通信不能となった原因が、ノードＮ２のノード故障であった場合において、このノードＮ２を経由する経路をできるだけ選択しないようにできる。

このようなＭＲＣファイルを作成するには、以下の条件を満たす必要がある。
（条件１）ＭＲＣファイルにおいて、isolated linkを除いたリンク（つまり、通常リンクとrestricted link）は、連結グラフとなることが必要である。これは、isolated link以外のリンクにより構成される経路の経路到達性を確保するためである。
（条件２）すべてのＭＲＣファイルにおけるisolated nodeとisolated linkとの和集合が、もとのトポロジに一致することが必要である。これは、トポロジに起こりうるノード故障およびリンク故障をすべてのＭＲＣファイルによりカバーする必要があるからである。
（条件３）isolated nodeには少なくとも一本のrestricted linkが接続され、それ以外のリンクはisolated linkであることが必要である。また、restricted linkの対向ノードは、その通常ノードとする。これは、前記したとおり、ＭＲＣファイルにおける迂回経路の作成において、リンク故障による通信不能の場合と、ノード故障による通信不能の場合との両方の場合を考慮する必要があるからである。

ここで、引き続き、図１１を用いて、従来技術によるＭＲＣファイルの作成アルゴリズムを説明する。ここでは、符号１０１に示すトポロジに対し、ＭＲＣファイル数＝４を指定した場合を例に説明する。まず、符号１０１に示すトポロジのリンクについて、すべて通常リンクと通常ノードとで構成されるＭＲＣファイルを作成する。そして、このＭＲＣファイルから任意のノードを選択する。例えば、ノードＮ１を選択する。次に、この選択したノードＮ１に接続されるリンクのうち、１つのリンクをrestricted linkとする。他のリンクはisolated linkとする。このとき、どのリンクをrestricted linkとするかはランダムに決める。以上の処理により、このノードＮ１のリンクはすべてisolated linkまたはrestricted linkとなるので、このノードＮ１はisolated nodeとなる。このようにしてＭＲＣファイル＃０を作成する（Ｓ１）。以下、このようにトポロジから、ノードを選択し、そのノードをisolated nodeとするまでの処理を基本処理と呼ぶ。

次に、ＭＲＣファイル＃１の作成処理に移る。ここでは、ＭＲＣファイル＃０で、isolated linkにできなかったリンク（例えば、restricted linkにしたリンク）の対向ノードを対象として、基本処理を行う。つまり、ノードＮ１，Ｎ６間のリンクをisolated linkとし、ノードＮ５，Ｎ６間のリンクをrestricted linkとする。そして、ノードＮ６をisolated nodeとして、ＭＲＣファイル＃１を作成する（Ｓ２）。このような基本処理を、ノードＮ６のrestricted linkの対向ノードであるノードＮ５に実行して、ＭＲＣファイル＃２を作成し（Ｓ３）、ノードＮ５のrestricted linkの対向ノードであるノードＮ４に実行して、ＭＲＣファイル＃３を作成する（Ｓ４）。

ここで、４つ目のＭＲＣファイル（ＭＲＣファイル＃３）まで作成したが、まだ符号１０１に示すトポロジのすべてのノードをisolated nodeとして選択していない。よって、Ｓ１で作成したＭＲＣファイル＃０に対し、基本処理を行う。つまり、ＭＲＣファイル＃３におけるノードＮ４のrestricted linkの対向ノードであるノードＮ３に対して基本処理を行い、符号１０３に示すＭＲＣファイル＃０へ更新する（Ｓ５）。さらに、まだ符号１０１に示すすべてのノードをisolated nodeとして選択していないので、ＭＲＣファイル＃１に対し、基本処理を行う。つまり、ノードＮ３のrestricted linkの対向ノードであるノードＮ２に対して基本処理を行い、符号１０２に示すＭＲＣファイル＃１へ更新する（Ｓ６）。以上の処理により、トポロジのすべてのノードがisolated nodeとなったので、処理を終了する。そして、符号１０３に示すＭＲＣファイル＃０、符号１０２に示すＭＲＣファイル＃１、Ｓ３で作成したＭＲＣファイル＃２、Ｓ４で作成したＭＲＣファイル＃３を出力する。

このようなアルゴリズムによれば、前のＭＲＣファイルではisolated linkにできなかったリンクを、次のＭＲＣファイルでisolated linkとするので、トポロジのすべてのノードをisolated nodeとし、また、すべてのリンクをisolated linkとすることができる。また、所定数のＭＲＣファイルに対し順に基本処理を行っていき、最後のＭＲＣファイルまで基本処理を行っても、まだすべてのノードをisolated nodeにできていなければ、最初に作成したＭＲＣファイルに戻り、基本処理を実行し、この基本処理の結果（isolated link、restricted linkおよびisolated node）を当該ＭＲＣファイルに追加していく。したがって、１つのＭＲＣファイルに複数の故障（故障ノードおよび故障リンク）が発生したときの迂回経路を記憶することができるので、必ずしも故障ごとにＭＲＣファイルを用意する必要がなくなる。

IETF RFC2328"OSPF Version 2"、1999年4月 A.Kyalbein,et.al "FAST IP NETWORK RECOVERY USING multiple routing configurations"in proceeding of infocom、2006年4月

しかし、前記した技術は、単一故障（単一のノードの故障および単一のリンクの故障）に対する迂回経路をすべて網羅することを主な目的としており、ＭＲＣファイル１つあたりの故障パターン（isolated nodeやisolated link）の集約効率は必ずしも高くない。よって、ルータが記憶すべきＭＲＣファイルが多くなってしまうこともある。例えば、図１１で説明した例では符号１０１に示すトポロジについて、合計４つのＭＲＣファイルを作成した。しかし、符号１０１に示すトポロジのすべての故障パターンの迂回経路を網羅するＭＲＣファイル群は、この４つのＭＲＣファイルに限定されず、たとえば、図１２に示す３つのＭＲＣファイル（ＭＲＣファイル＃０〜＃２）も考えられる。そこで、本発明は、前記した課題を解決し、ルータが保持すべきＭＲＣファイルの数を低減することを目的とする。

前記した課題を解決するため、請求項１に記載の発明は、ネットワークにおけるノード故障発生時およびリンク故障発生時の迂回経路を示したＭＲＣ（Multiple Routing Configurations)ファイルを作成するＭＲＣファイル作成装置であって、ネットワークのトポロジを示したトポロジ情報と、そのトポロジに対し、今まで作成されたＭＲＣファイルにおいてisolated nodeとなったノードおよびisolated linkとなったリンクを示したＭＲＣファイル作成管理情報とを記憶する記憶部と、乱数を用いて、トポロジにおけるリンクそれぞれのリンクコストの初期値の集合である初期値Ｗ０を生成するリンクコスト初期値作成部と、生成した初期値Ｗ０を用いて、Kruskal法によりトポロジのリンクの少なくとも一部を削除し、トポロジの全域木を作成する全域木作成部と、トポロジを参照して、全域木作成部により作成された全域木における末端のノードを、ＭＲＣファイルにおけるisolated nodeとし、この末端のノードに接続するリンクをrestricted linkとし、全域木の作成において削除されたリンクをisolated linkとして、トポロジのＭＲＣファイルを作成し、その作成したＭＲＣファイルにおいて、isolated nodeとなったノードおよびisolated linkとなったリンクをＭＲＣファイル管理情報に記録していくＭＲＣファイル作成部と、ＭＲＣファイル作成部により、ＭＲＣファイルが作成された後、ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれの値に、ランダムな値を加算した新たなリンクコストの集合Ｗ’をＮ個作成するリンクコスト値変更部と、全域木作成部、ＭＲＣファイル作成部およびリンクコスト値変更部の制御を行う反復制御部と、ＭＲＣファイル作成部により作成されたＭＲＣファイル群を出力する出力部とを備え、反復制御部は、（１）全域木作成部に、新たなリンクコストの集合Ｗ’１〜Ｗ’Ｎそれぞれのリンクコストの値を用いて全域木を作成させ、この作成させた全域木のうち、当該全域木によりＭＲＣファイルを作成した場合、ＭＲＣファイル管理情報に示される今まで作成したＭＲＣファイルに対し、新規にisolated nodeになる数およびisolated linkになる数が最も多い全域木を選択する処理と、（２）ＭＲＣファイル作成部に、選択された全域木によりＭＲＣファイルを作成させる処理と、（３）リンクコスト値変更部に、ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれの値に、ランダムな値を加算した新たなリンクコストの集合Ｗ’をＮ個作成させる処理とをＭＲＣファイル作成管理情報において、トポロジに示されるすべてのノードがisolated nodeとなり、かつ、すべてのリンクがisolated linkとなるまで実行させることを特徴とする。

請求項６に記載の発明は、ネットワークにおけるノード故障発生時およびリンク故障発生時の迂回経路を示したＭＲＣファイルを作成し、ネットワークのトポロジを示したトポロジ情報と、そのトポロジに対し、今まで作成されたＭＲＣファイルにおいてisolated nodeとなったノードおよびisolated linkとなったリンクを示したＭＲＣファイル作成管理情報とを記憶する記憶部を備えるＭＲＣファイル作成装置が、乱数を用いて、トポロジにおけるリンクそれぞれのリンクコストの値の集合である初期値Ｗ０を生成するステップと、リンクコストの集合の初期値Ｗ０を用いて、Kruskal法によりトポロジのリンクの少なくとも一部を削除し、トポロジの全域木を作成するステップと、トポロジを参照して、全域木作成部により作成された全域木における末端のノードを、ＭＲＣファイルにおけるisolated nodeとし、この末端のノードに接続するリンクをrestricted linkとし、全域木の作成において削除されたリンクをisolated linkとして、トポロジのＭＲＣファイルを作成し、その作成したＭＲＣファイルにおいて、isolated nodeとなったノードおよびisolated linkとなったリンクをＭＲＣファイル管理情報に記録していくステップと、ＭＲＣファイルが作成された後、ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれの値に、ランダムな値を加算した新たなリンクコストの集合Ｗ’をＮ個作成するステップと、作成されたＭＲＣファイル群を出力するステップとを実行し、ＭＲＣファイル作成装置が、（１）新たなリンクコストの集合Ｗ’１〜Ｗ’Ｎそれぞれのリンクコストの値を用いてＮ個の全域木を作成し、この作成した全域木のうち、当該全域木によりＭＲＣファイルを作成した場合、ＭＲＣファイル管理情報に示される今まで作成したＭＲＣファイルに対し、新規にisolated nodeになる数およびisolated linkになる数が最も多い全域木を選択するステップと、（２）選択した全域木によりＭＲＣファイルを作成するステップと、（３）ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれの値に、ランダムな値を加算した新たなリンクコストの集合Ｗ’をＮ個作成するステップとを、ＭＲＣファイル作成管理情報において、トポロジに示されるすべてのノードがisolated nodeとなり、かつ、すべてのリンクがisolated linkとなるまで実行することを特徴とするＭＲＣファイル作成方法とした。

このようなＭＲＣファイル作成装置は、まず、トポロジの全域木を作成し、この全域木をベースとしてＭＲＣファイル作成する。つまり、ＭＲＣファイルにおけるトポロジにおいて各ノードの経路到達性を確保しつつ、リンクの数をできるだけ減らしたトポロジを作成する。これにより、１つのＭＲＣファイルに集約される故障パターン数をできるだけ多くすることができる。この後、このＭＲＣファイル作成装置は、トポロジにおけるすべての故障パターンを網羅するＭＲＣファイルを順次作成していくが、あるＭＲＣファイルの作成後、次のＭＲＣファイルを作成するとき、ＭＲＣファイル管理情報を参照して、今まで作成したＭＲＣファイルに対し、新規なisolated node、isolated linkの数が最も増えるような全域木を作成し、この全域木を用いてＭＲＣファイルを作成する。このようにすることで、ＭＲＣファイル作成装置が、ＭＲＣファイル群を作成するとき、そのＭＲＣファイル同士でできるだけ故障パターンの重複のないＭＲＣファイル群を作成することができる。従って、ＭＲＣファイル作成装置は、トポロジに対するＭＲＣファイルの数を低減できる。なお、このＭＲＣファイル作成装置において全域木作成に用いるKruskal法は、リンクコストの値が比較的高いリンクを除去して全域木を作成するものである。よって、この性質を利用し、リンクコストの集合作成部が新たなリンクコストの集合を作成するとき、ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストの値それぞれを、ランダムに増加させたリンクコストの集合Ｗ’を作成することで、前回作成した全域木とは異なる全域木を作成しやすくなる。また、リンクコストの集合Ｗ’もＮ個（Ｎパターン）作成するので、バリエーションに富んだ全域木を作成できる。よって、ＭＲＣファイル作成装置が作成するＭＲＣファイルもバリエーションに富んだものになり新規のisolated nodeおよびisolated linkの数が大きく増えるようなＭＲＣファイルを発見しやすくなる。したがって、ＭＲＣファイル作成装置は、与えられたトポロジに対し、そのトポロジにおける故障パターンをすべて網羅するＭＲＣファイル群ができるだけ少なくなるようなＭＲＣファイル群を発見しやすくなる。

請求項２に記載の発明は、請求項１に記載のＭＲＣファイル作成装置におけるリンクコスト値変更部が、（１）ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれに、ランダムな値を加算して新たなリンクコストの集合Ｗ’をＮ個作成した後、（２）作成したＮ個の新たなリンクコストの集合Ｗ’それぞれについて、ＭＲＣファイルにおけるisolated node以外のノードに接続するリンクのリンクコストを１つ選択し、その選択したリンクコストを、ＯＳＰＦ（Open Shortest Path First）において設定可能な最小値に変更し、isolated node以外のノードに接続するリンクのリンクコストのうち、選択したリンクコスト以外のリンクのリンクコストを、ＯＳＰＦにおいて設定可能な最大値に変更することを特徴とする。

このようにすることで、ＭＲＣファイル作成装置は、新規のisolated nodeおよびisolated linkの数が大きく増えるようなＭＲＣファイルを発見しやすくなる。したがって、ＭＲＣファイル作成装置は、与えられたトポロジに対し、そのトポロジにおける故障パターンをすべて網羅するＭＲＣファイル群ができるだけ少なくなるようなＭＲＣファイル群を発見しやすくなる。

請求項３に記載の発明は、請求項１または請求項２に記載のＭＲＣファイル作成装置におけるリンクコスト初期値作成部は、乱数を用いて、初期値ＷＯを複数個生成し、反復制御部は、生成した初期値Ｗ０をもとに、全域木作成部、ＭＲＣファイル作成部およびリンクコスト値変更部によりＭＲＣファイル群を作成させる処理を、生成した初期値Ｗ０の個数分実行させ、作成したＭＲＣファイル群のうち、最もファイル数が少ないＭＲＣファイル群を選択し、出力部は、選択されたＭＲＣファイル群を出力することを特徴とする。

このようにすることで、ＭＲＣファイル作成装置は、様々なＭＲＣファイル群を作成し、その中から最もファイル数が少ないＭＲＣファイル群を選ぶので、よりＭＲＣファイル数の少ないＭＲＣファイル群を発見しやすくなる。

請求項４に記載の発明は、請求項１または請求項２に記載のＭＲＣファイル作成装置における反復制御部が、（１）ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれに、ランダムな値を加算して作成したＮ個の新たなリンクコストの集合Ｗ’をもとに全域木を作成し、この作成した全域木をもとにＭＲＣファイルを作成した場合、そのいずれの全域木によっても、ＭＲＣファイル作成管理情報に示される今まで作成したＭＲＣファイルに対し、新規にisolated nodeになるノードを増やすＭＲＣファイルを作成できなかったと判断したとき、（２）リンクコスト値変更部に、作成したＮ個の新たなリンクコストの集合Ｗ’それぞれについて、ＭＲＣファイルにおけるisolated node以外のノードに接続するリンクのリンクコストを１つ選択し、その選択したリンクコストを、ＯＳＰＦにおいて設定可能な最小値に変更し、isolated node以外のノードに接続するリンクのリンクコストのうち、選択したリンクコスト以外のリンクのリンクコストを、ＯＳＰＦにおいて設定可能な最大値に変更する処理を実行させることを特徴とする。

このようにすることでも、ＭＲＣファイル作成装置は、新規に作成するＭＲＣファイルを、今まで作成したＭＲＣファイルではカバーしきれていない新規なisolated nodeを含むようなＭＲＣファイルとすることができる。ここで、ＭＲＣファイル作成装置は、リンクコストの値をランダムに増加させたＮ個のリンクコストの集合Ｗ’のいずれによっても、新規なisolated nodeを増やすようなＭＲＣファイルが作成できないと判断したときに、（２）に示す処理を実行する。よって、ＭＲＣファイル作成装置は必要以上に（２）に示す処理を実行する必要がなくなる。

請求項５に記載の発明は、請求項１から請求項４のいずれか１項に記載のＭＲＣファイル作成装置により作成されたＭＲＣファイル群を用いて、ネットワーク内のノード故障またはリンク故障発生時の経路制御を行う経路制御装置とした。

このようにすることで、経路制御装置の保持するＭＲＣファイル数を低減できる。

請求項７に記載の発明は、請求項６に記載のＭＲＣファイル作成方法をコンピュータに実行させるためのプログラムとした。

このようなプログラムによれば、一般的なコンピュータ（例えば、ルータ）に請求項６に記載のＭＲＣファイル作成方法を実行させることができる。

本発明によれば、ルータが保持すべきＭＲＣファイルの数を低減できる。

本実施の形態のＭＲＣファイル作成方法の概要を説明した図である。 本実施の形態のＭＲＣファイル作成方法の概要を説明した図である。 本実施の形態のルータの機能ブロックである。 図３のルータの処理手順の概要を示したフローチャートである。 図４のＳ１１の処理の詳細を示したフローチャートである。 図４のＳ１１の処理の詳細を示したフローチャートである。 （ａ）は、本実施の形態におけるリンクコストの集合の初期値Ｗ０を例示した図である。（ｂ）は、本実施の形態におけるリンクコストの集合Ｗ１〜ＷＮの値の増加を概念的に説明した図である。（ｃ）は、本実施の形態における全域木ＧＸの選択処理を概念的に示した図である。 （ａ）は、比較例となるＭＲＣファイル作成方法を説明した図である。（ｂ）は、図３のルータにより作成されるＭＲＣファイル群を例示した図である。 本実施の形態のＭＲＣファイル作成装置の効果を説明するために引用した図である。 本実施の形態の故障復旧装置の機能ブロック図である。 比較例となるＭＲＣファイル作成方法を説明した図である。 ＭＲＣファイルを例示した図である。

以下、本発明を実施するための形態について説明する。まず、図１および図２を用いて本実施の形態のＭＲＣファイルの処理手順の概要を説明する。ここでは、図１のトポロジ３０１のＭＲＣファイルを作成する場合を例に説明する。このトポロジ３０１を構成するリンクそれぞれには、乱数により発生させたリンクコストの初期値が与えられているものとする。ＭＲＣファイル作成装置は、このトポロジ３０１をもとに、全域木３０２を作成する。なお、全域木とは、各ノード間のリンクを一部除去し、経路到達性を確保できる最低限のリンクで構成したツリートポロジである。そして、この全域木３０２において、末端となっているノード（リーフのノード）を、isolated node（故障ノード）とする。また、このリーフのノードに接続するリンクをrestricted link（最終ホップでのみ用いるリンク）とする。そして、この全域木３０２を作成するときに削除したリンクをisolated link（故障リンク）とし、図１に示すようなＭＲＣファイル＃０を作成する。このような方法によれば、前記したＭＲＣファイルの作成条件、すなわち、前記した（条件１）ＭＲＣファイルにおいて、isolated linkを除いたリンクは、連結グラフとなること、および、（条件３）isolated nodeには少なくとも一本のrestricted linkが接続され、それ以外のリンクはisolated linkであることを満たすＭＲＣファイルを作成することができる。

ここで、ＭＲＣファイル作成装置は、トポロジの全域木をもとにＭＲＣファイルを作成するので、経路到達性を確保しつつ、１つのＭＲＣファイルが多数の故障パターンの迂回経路を網羅できる。ＭＲＣファイル作成装置は、このようにしてＭＲＣファイルを１つ作成すると、今度は、トポロジの各リンクのリンクコストの値を変更して、別の全域木を作成する。なお、本実施の形態で用いる全域木の作成方法は、Kruskal法を用いる（石畑清、「アルゴリズムとデータ構造」ｐ280-283、岩波書店、1991年、参照）。このKruskal法では、リンクコストの値が高いものから優先的にリンクを除去して全域木を作成する。よって、トポロジの各リンクのリンクコストの値を変更することで、異なる全域木を作成することができる。そして、ＭＲＣファイル作成装置は、作成した全域木をもとにＭＲＣファイルを作成する。このような処理を、前記したＭＲＣファイルの作成条件、（条件３）すべてのＭＲＣファイルにおけるisolated nodeとisolated nodeとの和集合が、もとのトポロジに一致する、という条件を満たすまで繰り返す。

すなわち、ＭＲＣファイル作成装置は、図２に示すように、まず、（１）入力トポロジに対し、（２）全域木を作成する。ここでの全域木の作成は、乱数により生成された入力トポロジのリンクコストの初期値をもとに行われる。作成した全域木をもとに（３）ＭＲＣファイル（ＭＲＣファイル＃０）を作成する。そして、この作成したＭＲＣファイルの情報を（Ａ）ＭＲＣファイル作成管理情報に記録する。ここで、（Ａ）ＭＲＣファイル作成管理情報にまだisolated linkになっていないリンク、isolated nodeになっていないノードがある。よって、ＭＲＣファイル作成装置は、（３）で、isolated linkとならなかったリンクのリンクコストの値にランダムな値を加算して、リンクコストの値を変更する。そして、（４）この変更したリンクコストの値を用いて全域木を作成し、作成した全域木をもとに、（５）ＭＲＣファイル（ＭＲＣファイル＃１）を作成する。そして、この作成したＭＲＣファイルの情報を（Ｂ）ＭＲＣファイル作成管理情報に記録する。

ここで、（Ｂ）ＭＲＣファイル作成管理情報にはまだisolated linkになっていないリンクおよびisolated nodeになっていないノードがある。よって、ＭＲＣファイル作成装置は、さらに、（５）で、isolated linkとならなかったリンクのリンクコストの値にランダムな値を加算して、リンクコストの値を変更する。そして、（６）この変更したリンクコストの値を用いて全域木を作成し、作成した全域木をもとに（７）ＭＲＣファイル（ＭＲＣファイル＃２）を作成する。この作成したＭＲＣファイルの情報を（Ｃ）ＭＲＣファイル作成管理情報に記録する。ここで、ＭＲＣファイル作成管理情報の、すべてのリンクがisolated linkであり、すべてのノードがisolated nodeとなっていることを確認すると、処理を終了する。この後、再度乱数を発生させて各リンクのリンクコストの初期値を設定し、全域木作成と、その作成した全域木に基づくＭＲＣファイル作成処理を所定回数繰り返す。そして、ＭＲＣファイル作成装置は、以上の処理により作成されたＭＲＣファイル群のうち、そのファイル数が最も少ないＭＲＣファイル群を出力する。このようにすることで、ＭＲＣファイル作成装置は、入力トポロジに対しできるだけファイル数の少ないＭＲＣファイル群の組み合わせを発見することができる。

＜構成＞
次に、図３を用いて、このようなＭＲＣファイル作成装置の構成を説明する。ここでは、ＭＲＣファイル作成装置がネットワーク内で経路制御を行うルータ（経路制御装置）により実現される場合を例に説明する。

図３に示すように、ルータ１０の機能は、大きく入出力部１１と、処理部１２と、記憶部１３とに分けられる。入出力部１１は、他のルータ１０との間でトポロジ情報１３１（後記）や経路情報１３４のもととなるデータや、他のルータ１０との間のパケットの入出力を司る。処理部１２は、ＭＲＣファイルの作成処理や、作成したＭＲＣファイルに基づく経路制御等を行う。記憶部１３は、ＭＲＣファイルの作成ために必要なトポロジ情報１３１や経路情報１３４を記憶する。このような入出力部１１は、ネットワーク経由でパケットの送受信を行うための通信インタフェースや、入出力インタフェースから構成される。また、処理部１２は、このルータ１０が備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部１３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、ルータ１０をプログラム実行処理により実現する場合、記憶部１３には、ルータ１０の機能を実現するためのプログラムが格納される。

処理部１２は、ＭＲＣファイルの作成を行うＭＲＣファイル作成処理部１２１と、受信したパケットの経路制御を行う経路制御部１２８とを備える。

このＭＲＣファイル作成処理部１２１は、リンクコスト初期値作成部１２２と、全域木作成部１２３と、ＭＲＣファイル作成部１２４と、リンクコスト値変更部１２５と、反復制御部１２６と、ＭＲＣファイル群出力処理部１２７とを備える。

このうち、リンクコスト初期値作成部１２２は、乱数を発生させて、トポロジ情報１３１に示されるネットワークのリンクそれぞれのリンクコストの値の集合である初期値Ｗ０（ＷＯ＝｛ｗ_０１，ｗ_０２，ｗ_０３，…，ｗ_０Ｘ,…｝）を作成する。なお、このリンクコスト初期値作成部１２２は、この初期値Ｗ０を複数個（Ｍ個）作成する。

全域木作成部１２３は、与えられたリンクコストの集合の値を用いて、Kruskal法によりトポロジ情報１３１に示されるトポロジの全域木を作成する。このKruskal法による全域木の作成処理は、以下の手順により行われる。
（１）グラフ（トポロジ）が与えられたとき全リンクにフラグ「０」を付与する。
（２）このグラフから、リンクコスト最小のリンクを選び、そのリンクのフラグを「１」とする。
（３）残りのフラグ「０」のリンクから、コスト最小の辺を取り出す。
（４）（３）で選んだリンクのフラグを「１」としたときに、すべてのフラグ「１」のリンクによりサイクル（ループ）ができるとき、このリンクをグラフから削除する。サイクルができないときは、このリンクのフラグを「１」とする。
（５）グラフにフラグ「１」にできるリンクがなければ、そのフラグ「１」のリンクと、全ノードにより全域木が作成される。もし、グラフにフラグ「１」にできるリンクがあれば（３）へ戻る。
以上の処理により、全域木作成部１２３は、トポロジ情報に示されるトポロジの全域木（スパニングツリー）を作成することができる。このKruskal法では、リンクコストの値が高いリンクが除去されやすいという特性がある。

また、この全域木作成部１２３は、複数のリンクコストの集合Ｗ’１〜Ｗ’Ｎの入力を受け付けたときには、そのそれぞれの値を用いてＮ個の全域木を作成する。

ＭＲＣファイル作成部１２４は、トポロジ情報１３１に示されるネットワークのトポロジと、全域木作成部１２３が作成した全域木とを比較することで、ＭＲＣファイルを作成する。このＭＲＣファイルの作成手順は、以下の通りである（図１参照）。
（１）全域木のリーフ（leaf）、つまり、全域木の末端のノードをisolated nodeとする。例えば、図１に全域木３０２において、リーフはノードＮ３，Ｎ５，Ｎ６であるので、これらのノードをisolated nodeとする。
（２）全域木のリーフに接続するリンクをrestricted linkとする。つまり、リーフに接続するリンクは１本であるので、このリンクをrestricted linkとする。例えば、図１に全域木３０２において、リーフはノードＮ３，Ｎ５，Ｎ６であるので、これらのノードに接続するリンクをrestricted linkとする。
（３）全域木の作成によって、トポロジから削除されたリンクをisolated linkとする。例えば、トポロジ３０１と、全域木３０２とを比較して、ノードＮ２，Ｎ３の間のリンク、ノードＮ３，Ｎ４の間のリンク、ノードＮ５，Ｎ６の間のリンクが削除されているので、これらのリンクをisolated linkとする。

また、図３のＭＲＣファイル作成部１２４は、ＭＲＣファイルを作成するたび、そのＭＲＣファイルにおいてisolated nodeとなったノード、isolated linkとなったリンクとを、ＭＲＣファイル作成管理情報１３３（詳細は後記）に記録していく。このようなＭＲＣファイル作成管理情報１３３を参照することで、今まで作成したＭＲＣファイル（ＭＲＣファイル群）により、どのノードがisolated nodeとなり、どのリンクがisolated linkとなったかが分かる。

リンクコスト値変更部１２５は、Ｗｏｐｔ（前回全域木作成に用いたリンクコストの集合）を変更した新たなリンクコストの集合Ｗ’をＮ個作成する。ここで、リンクコスト値変更部１２５は、（１）Ｗｏｐｔに示されるリンクコストのうち、非isolated linkのリンクコストの値をランダムに増加させ、（２）この非isolated nodeの中からランダムに選択した１つのノードについて、そのノードに接続するリンクのうち１本のリンクコストの値を設定可能な最小値とし、そのノードに接続する残りのリンクのリンクコストの値を最大値とする。

すなわち、（１）リンクコスト値変更部１２５は、前回全域木作成に用いたリンクコストの集合Ｗｏｐｔを読み出すと、この値をＮ個コピーする。そして、そのコピーしたＮ個のリンクコストの集合（Ｗ１〜ＷＮ）のうち、前回作成したＭＲＣファイルにおいて非isolated linkとなったリンクのリンクコストの値に、ランダムな値（ｗｍｉｎ〜ｗｍａｘ）を加算する（後記する図７（ｂ）参照）。ここで、非isolated linkのリンクのリンクコストの値を増加させるのは、前記したKruskal法においてリンクコストの値が高いリンクが除去されやすいからである。つまり、リンクが除去されると、ＭＲＣファイルにおいてそのリンクはisolated linkとなるので、isolated linkを増加させることができるからである。また、（２）リンクコスト値変更部１２５は、このＮ個の新たなリンクコストの集合Ｗ’それぞれについて、ＭＲＣファイルにおけるisolated node以外のノード（非isolated node）に接続するリンクを１つ選択する。そして、その選択したリンクのリンクコストを、ＯＳＰＦ（Open Shortest Path First）において設定可能な最小値（例えば、「１」）とする。また、その非isolated nodeに接続するリンクのうち、この最小値を設定したリンク以外のリンクコストを、ＯＳＰＦにおいて設定可能な最大値（例えば、「65535」）とする。

すなわち、リンクコスト値変更部１２５は、全域木作成部１２３が、このリンクコストに基づき全域木を作成すると、少なくとも１つの非isolated nodeをリーフとなるようにリンクコストを変更する。つまり、リンクコスト値変更部１２５は、ＭＲＣファイル作成部１２４が作成するＭＲＣファイルにおいてisolated nodeが増加するようなリンクコストに変更する。

反復制御部１２６は、前記した条件２（ＭＲＣファイルにおけるisolated nodeとisolated linkとの和集合が、トポロジ情報１３１に示すトポロジと一致すること）を満たすまで、リンクコスト値変更部１２５にリンクコスト値変更処理を実行させ、全域木作成部１２３に全域木作成処理を実行させ、ＭＲＣファイル作成部１２４にＭＲＣファイル作成処理を実行させる。

具体的には、反復制御部１２６は、全域木作成部１２３に、新たなリンクコストの集合Ｗ’１〜Ｗ’Ｎそれぞれのリンクコストの値を用いてＮ個の全域木を作成させる。そして、この全域木の中から、当該全域木によりＭＲＣファイルを作成したときに、新規にisolated nodeになる数およびisolated linkになる数が最も多い全域木を選択する。そして、反復制御部１２６は、ＭＲＣファイル作成部１２４に、この選択した全域木によりＭＲＣファイルを作成させる。ここで、新規にisolated nodeになる数およびisolated linkになる数が最も多い全域木を選択するのは、１つのファイルあたり、できるだけ多くの故障パターンの迂回経路の情報を含むＭＲＣファイルを作成するためである。そして、反復制御部１２６は、ＭＲＣファイル作成管理情報１３３における非isolated linkおよび非isolated nodeがなくなるまで、リンクコスト値変更部１２５、全域木作成部１２３およびＭＲＣファイル作成部１２４に、リンクコスト値変更処理、全域木作成処理およびＭＲＣファイル作成処理を実行させる。つまり、ＭＲＣファイル作成管理情報１３３に非isolated linkまたは非isolated nodeが残っていれば、反復制御部１２６は、リンクコスト値変更部１２５に再度リンクコスト値を変更させ、全域木作成部１２３にこの変更後のリンクコスト値をもとに全域木を作成させ、ＭＲＣファイル作成部１２４にＭＲＣファイルを作成させる。反復制御部１２６は、このような処理を、リンクコスト初期値作成部１２２が作成したリンクコストの集合の初期値ＷＯの個数分（例えば、Ｍ回）実行させる。そして、反復制御部１２６は、その結果作成されたＭＲＣファイル群のうち、最もファイル数が少ないＭＲＣファイル群（ＭＲＣファイルのセット）を選択する。この反復制御部１２６の処理手順の詳細は、フローチャートを用いて後記する。

ＭＲＣファイル群出力処理部（出力部）１２７は、反復制御部１２６が選択したＭＲＣファイル群を記憶部１３へ出力する。

次に、経路制御部１２８を説明する。経路制御部１２８は、経路計算部１２９と、パケット転送部１３０とを備える。経路計算部１２９は、トポロジ情報１３１やＭＲＣファイル群１３２に基づき、転送経路の計算を行い、経路情報１３４（後記）や、故障パターンごとの迂回経路情報１３５（後記）を作成する。例えば、経路情報１３４は、パケットの宛先アドレスごとに、このパケットを出力するためのインタフェースを示した情報である。また、迂回経路情報１３５は、故障パターンごとに、その故障パターンの故障が発生した場合における、パケットの宛先アドレスごとの、当該パケットを出力するためのインタフェースを示した情報である。

パケット転送部１３０は、受信したパケットの宛先アドレスをもとに、経路情報１３４または迂回経路情報１３５を参照して、このパケットの出力インタフェースを選択し、この選択した出力インタフェースからパケットを出力する。ここで、故障発生時にはパケット転送部１３０は迂回経路情報１３５を参照して、パケットの出力インタフェースを選択するが、どの迂回経路情報１３５を用いればよいかは、このルータ１０に入力される故障情報に基づき判断される。

次に、記憶部１３を説明する。記憶部１３は、トポロジ情報１３１と、ＭＲＣファイル群１３２と、ＭＲＣファイル作成管理情報１３３と、経路情報１３４と、迂回経路情報１３５とを記憶する。

トポロジ情報１３１は、ネットワーク内の各ノード（ルータ）の識別情報や、そのそれぞれのノードがどのリンクにより接続されているか等を示した情報である。このトポロジ情報１３１は、例えば、図１のトポロジ３０１に示すような情報である。このトポロジ情報１３１は、全域木の作成やＭＲＣファイルの作成において参照される。

ＭＲＣファイル群１３２は、ＭＲＣファイル群出力処理部１２７により出力されたＭＲＣファイル群である。このＭＲＣファイル群は、迂回経路情報１３５の作成に用いられる。

ＭＲＣファイル作成管理情報１３３は、ＭＲＣファイル作成部１２４が作成したＭＲＣファイルにおいて、isolated linkとなったリンク、isolated nodeとなったノードを記録した情報である（図２の（Ａ）〜（Ｃ）に示すＭＲＣファイル作成管理情報参照）。反復制御部１２６は、このＭＲＣファイル作成管理情報１３３を参照することで、与えられたトポロジに対し、すべてのノード故障およびリンク故障をカバーするようなＭＲＣファイル群を作成できたか否かを判断できる。

経路情報１３４は、パケットの宛先アドレスごとに、このパケットを出力するためのインタフェースを示した情報である。また、迂回経路情報１３５は、故障パターンごとに、その故障パターンの故障が発生した場合における、パケットの宛先アドレスごとの、当該パケットを出力するためのインタフェースを示した情報である。

＜処理手順＞
図３を参照しつつ、図４を用いてルータ１０によるＭＲＣファイル作成処理の概要を説明する。まず、図３のルータ１０は、リンクコスト初期値作成部１２２により、リンクコストの初期値Ｗ０をＭ個（Ｍパターン）作成すると、その作成したＭ個の初期値ＷＯの中から選択した初期値Ｗ０を用いてＭＲＣファイル群を作成する（Ｓ１１）。そして、この作成したＭＲＣファイル群を記憶部１３に記録する（Ｓ１２）。なお、このＳ１１におけるＭＲＣファイル群の作成処理の詳細は後記する。次に、ルータ１０の反復制御部１２６は、Ｓ１１に示すＭＲＣファイル群の作成処理をＭ回実行したか否かを判断する（Ｓ１３）。つまり、作成したＭ個の初期値Ｗ０すべてについてＭＲＣファイル群を作成した否かを判断し、作成したＭ個の初期値Ｗ０すべてについてＭＲＣファイル群を作成したと判断したとき（Ｓ１３のＹｅｓ）、作成したＭＲＣファイル群のうち、ファイル数が最も少ないＭＲＣファイル群（ＭＲＣファイル群のセット）を選択し、記憶部１３へ出力する（Ｓ１４）。一方、反復制御部１２６がまだＭＲＣファイル群の作成処理をＭ回実行していないと判断したとき（Ｓ１３のＮｏ）、Ｓ１１へ戻り、ＭＲＣファイル群の作成処理を実行する。

このようにルータ１０は、Ｍ個（Ｍパターン）のリンクコストの集合の初期値Ｗ０それぞれについて、ＭＲＣファイル群を作成するので、様々なＭＲＣファイル群を作成することができる。よって、ルータ１０は、できるだけファイル数の少ないＭＲＣファイル群（ＭＲＣファイルのセット）を発見しやすくなる。

次に、図３を参照しつつ、図５および図６を用いて、図４のＳ１１の処理の詳細を説明する。まず、図３のルータ１０のリンクコスト初期値作成部１２２は、乱数を発生させ、リンクコストの集合の初期値Ｗ０を生成する（Ｓ２１）。そして、この初期値Ｗ０を、Ｗｏｐｔに代入し（Ｓ２２）、ＭＲＣファイルの管理変数ｉ＝０とする（Ｓ２３）。

次に、ルータ１０の全域木作成部１２３は、このＷｏｐｔの値に基づき全域木を作成し、ＭＲＣファイル作成部１２４は、この全域木によりＭＲＣファイルを作成し（Ｓ２４）、管理変数ｉの値を１増加させる（Ｓ２５）。作成したＭＲＣファイルは、記憶部１３の所定領域に記憶される。また、作成したＭＲＣファイルにより新規にisolated nodeとなったノードおよびisolated linkとなったリンクは、ＭＲＣファイル作成管理情報１３３（図２の（Ａ）〜（Ｃ）参照）に記録する。ここで、反復制御部１２６は、このＭＲＣファイル作成管理情報１３３を参照して、全ＭＲＣファイルにおける非isolated nodeＶ’および非isolated nodeの集合であるＧ’＝（Ｖ’，Ｅ’）を作成する（Ｓ２６）。そして、このＧ’が空集合であれば（Ｓ２７のＹｅｓ）、ＭＲＣファイル群出力処理部１２７は全ＭＲＣファイル（ＭＲＣファイル群）を出力する（Ｓ３０）。

一方、Ｓ２７において、このＧ’が空集合でなければ（Ｓ２７のＮｏ）、反復制御部１２６は、このＧ’に含まれるノードとリンクを、それぞれisolated node、isolated linkとして１つのＭＲＣファイルを作成可能か否かを判断する（Ｓ２８）。ここで、１つのＭＲＣファイルを作成可能であれば（Ｓ２８のＹｅｓ）、ＭＲＣファイル作成部１２４によりＭＲＣファイルを作成し（Ｓ２９）、ＭＲＣファイル群出力処理部１２７は作成した全ＭＲＣファイル（ＭＲＣファイル群）を出力する（Ｓ３０）。

一方、Ｓ２８において１つのＭＲＣファイルを作成可能でなければ（Ｓ２８のＮｏ）、図６のＳ３１へ進む。図３のリンクコスト値変更部１２５は、まず、Ｗｏｐｔの値をコピーしたＮ個のリンクコストの集合Ｗ１〜ＷＮを作成する（Ｓ３１）。そして、リンクコスト値変更部１２５は、リンクコストの集合Ｗ１〜ＷＮの中から選択したリンクコストの集合Ｗに対し、以下の処理を実行する。すなわち、リンクコスト値変更部１２５は、このリンクコストの集合Ｗのうち、非isolated linkのリンクコストの値をｗｍｉｎ〜ｗｍａｘの範囲でランダムに増加させる（Ｓ３２）。

例えば、図７（ａ）に示すように初期値Ｗ０が｛ｗ_０１，ｗ_０２，ｗ_０３,…,ｗ_０Ｘ，…｝であった場合、リンクコスト値変更部１２５は、（ｂ）に示すように、まずこの初期値ＷＯをＮ個コピーし、Ｗ１〜ＷＮを作成する。そして、そのＷ１〜ＷＮの中から今回の処理の対象のＷを選択し、この選択したＷのリンクコストのうち、非isolated linkのリンクコストにｗｍｉｎ〜ｗｍｉｎの値を加算する。例えば、ｗ_０２、ｗ_０Ｘが非isolated linkのリンクコストである場合、Ｗ１におけるｗ_０２、ｗ_０Ｘの値に、ｗｍｉｎ〜ｗｍａｘからランダムに選択した値（ｗａ，ｗｃ）を加算する。

図６の説明に戻る。このようにしてリンクコスト値変更部１２５が、初期値Ｗ０におけるリンクコストの値を増加させると、次に、リンクコスト値変更部１２５は、ＭＲＣファイル作成管理情報１３３を参照して、非isolated nodeを選択する。そして、その選択した非isolated nodeに接続するリンクに対し、１つのリンクはＯＳＰＦで設定可能な最小のリンクコスト（例えば、「１」）を設定し、残りのリンクには設定可能な最大のリンクコスト（例えば、「65535」）を設定する。これにより、全域木作成部１２３がこのリンクコストをもとに全域木を作成すると、選択した非isolated nodeは全域木のリーフ（図１の全域木３０２参照）となる。つまり、この全域木をもとにＭＲＣファイルを作成すると、このノードはisolated nodeになるので、ＭＲＣファイル作成部１２４は、新規のisolated nodeを増やすようなＭＲＣファイルを作成することができる。

ここで、反復制御部１２６が、Ｓ３１で作成したリンクコストの集合Ｗ１〜ＷＮについて処理を終了していると判断したとき（Ｓ３４のＹｅｓ）、全域木作成部１２３は、Ｓ３２およびＳ３３の処理後のリンクコストの集合Ｗ１〜ＷＮを用いて全域木Ｇ１〜ＧＮを作成する（Ｓ３５）。一方、Ｓ３４において、まだリンクコストの集合Ｗ１〜ＷＮについて処理を終了していなければ（Ｓ３４のＮｏ）、Ｓ３２へ戻る。Ｓ３５の後、反復制御部１２６は、ＭＲＣファイル作成管理情報１３３を参照して、全域木Ｇ１〜ＧＮの中から、新規にisolated node、isolated linkとなる数が最も多い全域木ＧＸを選択する（Ｓ３６）。

例えば、図７（ｂ）に示すように、全域木作成部１２３は、リンクコストの集合Ｗ１〜ＷＮに基づき、全域木Ｇ１〜ＧＮを作成する。そして、反復制御部１２６は、（ｃ）に示すようにＭＲＣファイル作成管理情報１３３と、全域木Ｇ１〜ＧＮそれぞれに基づきＭＲＣファイルを作成したときに、新規にisolated link、isolated nodeとなる数が最も多い全域木ＧＸを選択する（Ｓ３６）。そして、反復制御部１２６は、この全域木ＧＸ作成のもととなったリンクコストの集合ＷＸを、Ｗｏｐｔに代入する（Ｓ３７）。そして図５のＳ２４へ戻る。

ルータ１０が以上のような処理を行うことで、ＭＲＣファイル１つあたりに集約できる故障パターンをできるだけ多くすることができる。よって、入力されたトポロジに対するＭＲＣファイル数をできるだけ少なくすることができる。

また、本実施の形態のルータ１０によれば、従来技術にはない以下のような効果を得ることができる。例えば、図８（ａ）に示すようなトポロジにおいて、従来技術により、３つＭＲＣファイルを作成しようすると、ＭＲＣファイルを作成できない場合もある。つまり、ノードＮ１，Ｎ６間のリンクをrestricted linkとし、このノードＮ１に接続するその他のリンクをisolated linkとし、ノードＮ１をisolated nodeとする（Ｓ８１）。また、ノードＮ６，Ｎ５間のリンクをrestricted linkとし、ノードＮ１，Ｎ６間のリンクをisolated nodeとする（Ｓ８２）。そして、ノードＮ５，Ｎ４間のリンクをrestricted linkとし、ノードＮ６，Ｎ５間のリンクをisolated nodeとする（Ｓ８３）。ここで、まだすべてのノードをisolated nodeとし、すべてのリンクをisolated linkにできていない。また、目標とするＭＲＣファイル数は「３」なので、Ｓ８１で作成したＭＲＣファイル＃０に戻って処理を続ける。しかし、ＭＲＣファイル＃０に対し、ノードＮ５，Ｎ４間のリンクを除去すると、つまりisolated linkとすると接続性（経路到達性）を確保できないので、このリンクをisolated linkにできない。すなわち、ノードＮ５，Ｎ４間のリンクを除去すると、ノードＮ６，Ｎ５間のリンクが孤立するので、前記した（条件１）ＭＲＣファイルにおいて、isolated linkを除いたリンクは、連結グラフとなることが必要である、という条件を満たすことができない。よって、与えられたトポロジに対するＭＲＣファイルを作成できないことになる。

一方、本実施の形態のルータ１０によれば、図８（ｂ）に示すように、（条件１）〜（条件３）を満たす３つのＭＲＣファイル（ＭＲＣファイル＃０〜＃２）を作成することができる。つまり、例えば、図８（ａ）（ｂ）に示すような対称性がないトポロジに対し、従来技術によりＭＲＣファイルを作成しようとすると、故障パターン（故障による迂回経路のパターン）の集約が非効率になる。よって、目標とするＭＲＣファイル数では、すべての故障パターンを網羅することができない場合もある。一方、本実施の形態のルータ１０によれば、（１）ＭＲＣファイルにおいて故障箇所除去したトポロジを全域木により作成し、また、（２）できるだけ新規にisolated node、isolated linkを増やすようなＭＲＣファイルを探索するという処理を行うので、ＭＲＣファイル１つあたりに含まれる故障パターンの数をできるだけ多くし、対称性がないトポロジであっても、少ないＭＲＣファイル数で故障パターンを網羅できるようなＭＲＣファイル群を作成することができる。

なお、前記した実施の形態において、図３のルータ１０のリンクコスト値変更部１２５は、Ｗ１〜ＷＮそれぞれのリンクコストの値をランダムに増加させて新たなリンクコストの集合Ｗ１’〜ＷＮ’を作成した後、反復制御部１２６が、このＮ個の新たなリンクコストの集合Ｗ’をもとに全域木を作成し、ＭＲＣファイルを作成した場合、新規にisolated nodeになるノードがあると判断したとき、図６のＳ３３に示す処理を省くようにしてもよい。つまり、ルータ１０は、リンクコストの値をランダムに増加させることだけでも、確実に新規のisolated nodeを増やせることが分かっていれば、Ｓ３３に示す処理を行わないようにしてもよい。また、リンクコスト値変更部１２５は、このように図６のＳ３２に示す処理をスキップして、Ｓ３３に示す処理を実行したが、このＳ３３に示す処理の実行により新規にisolated linkとなるリンクの数が所定の閾値よりも少なかったとき、Ｓ３２に示す処理を実行するようにしてもよい。

なお、本実施の形態のＭＲＣファイル作成装置を、図９に示す故障復旧装置４０として実現するようにしてもよい。前記した実施の形態と同様の構成要素は、同じ符号を付して説明を省略する。この故障復旧装置４０は、ネットワーク情報取得装置５０によりネットワーク内のルータ２０およびルータ２０間を接続するリンクの故障を監視し、故障発生時には、ネットワーク内の各ルータ２０に対し、ＭＲＣファイルに基づく迂回経路への経路変更を指示する。このようなシステムは、故障復旧装置４０と、ネットワーク情報取得装置５０と、複数のルータ２０からなるネットワークとを含んで構成される。故障復旧装置４０は、ルータ２０へ経路制御を指示するコンピュータであり、例えば、ＰＣＥ（Path Computation Element）により実現される。ネットワーク情報取得装置５０は、ネットワーク内のルータ２０やルータ２０間を接続するリンクの故障等を検出すると、この故障が発生したルータ２０やリンクを故障復旧装置４０へ通知する。ルータ２０は、この故障復旧装置４０の指示に基づき経路制御を行うＩＰルータである。

このような故障復旧装置４０の機能は、図１０に示すように、大きく入出力部４１、処理部４２および記憶部４３に分けられる。入出力部４１は、ネットワーク内のルータ２０と通信を行うための通信インタフェースや、入出力インタフェースから構成される。また、処理部４２は、この故障復旧装置４０の備えるＣＰＵによるプログラム実行処理や、専用回路等により実現される。さらに、記憶部４３は、ＲＡＭ、ＲＯＭ、ＨＤＤ、フラッシュメモリ等の記憶媒体から構成される。なお、故障復旧装置４０の機能をプログラム実行処理により実現する場合、記憶部４３には、故障復旧装置４０の機能を実現するためのプログラムが格納される。

処理部４２は、図３のルータ１０の経路制御部１２８に代えて、ネットワーク内のルータ２０に対し、経路制御の指示を行う経路制御部４２８を備えることを特徴とする。この経路制御部４２８は、経路計算部１２９と、経路制御指示部４３０とを備える。この経路制御指示部４３０は、故障発生前は、経路情報１３４に示される経路情報をもとにルータ２０に対し経路制御を指示する。一方、図９のネットワーク情報取得装置５０経由で故障情報を受信したときには、迂回経路情報１３５を参照して、故障したルータ２０やリンクを避けるような迂回経路をルータ２０に対し指示する。なお、この故障発生時にどの迂回経路情報１３５を用いればよいかは、故障復旧装置４０に入力される故障情報に基づき判断される。このようなＭＲＣファイル作成部１２４を備えることで、故障復旧装置４０の保持するＭＲＣファイル数、迂回経路情報をできるだけ削減できる。

本実施の形態に係るルータ１０および故障復旧装置４０を実現するプログラムは、コンピュータによる読み取り可能な記録媒体（ＣＤ−ＲＯＭ等）に記憶して提供することが可能である。また、そのプログラムを、インターネット等のネットワークを通して提供することも可能である。

１０，２０ ルータ
１１，４１ 入出力部
１２，４２ 処理部
１３，４３ 記憶部
４０ 故障復旧装置
５０ ネットワーク情報取得装置
１２１ ＭＲＣファイル作成処理部
１２２ リンクコスト初期値作成部
１２３ 全域木作成部
１２４ ＭＲＣファイル作成部
１２５ リンクコスト値変更部
１２６ 反復制御部
１２７ ＭＲＣファイル群出力処理部
１２８，４２８ 経路制御部
１２９ 経路計算部
１３０ パケット転送部
１３１ トポロジ情報
１３２ ＭＲＣファイル群
１３３ ＭＲＣファイル作成管理情報
１３４ 経路情報
１３５ 迂回経路情報
４３０ 経路制御指示部

Claims (7)

1. ネットワークにおけるノード故障発生時およびリンク故障発生時の迂回経路を示したＭＲＣ（Multiple Routing Configurations)ファイルを作成するＭＲＣファイル作成装置であって、
   前記ネットワークのトポロジを示したトポロジ情報と、そのトポロジに対し、今まで作成されたＭＲＣファイルにおいてisolated nodeとなったノードおよびisolated linkとなったリンクを示したＭＲＣファイル作成管理情報とを記憶する記憶部と、
   乱数を用いて、前記トポロジにおけるリンクそれぞれのリンクコストの初期値の集合である初期値Ｗ０を生成するリンクコスト初期値作成部と、
   前記生成した初期値Ｗ０を用いて、Kruskal法により前記トポロジのリンクの少なくとも一部を削除し、前記トポロジの全域木を作成する全域木作成部と、
   前記トポロジを参照して、前記全域木作成部により作成された全域木における末端のノードを、前記ＭＲＣファイルにおけるisolated nodeとし、この末端のノードに接続するリンクをrestricted linkとし、前記全域木の作成において削除されたリンクをisolated linkとして、前記トポロジのＭＲＣファイルを作成し、その作成したＭＲＣファイルにおいて、isolated nodeとなったノードおよびisolated linkとなったリンクを前記ＭＲＣファイル管理情報に記録していくＭＲＣファイル作成部と、
   前記ＭＲＣファイル作成部により、前記ＭＲＣファイルが作成された後、前記ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれの値に、ランダムな値を加算した新たなリンクコストの集合Ｗ’をＮ個作成するリンクコスト値変更部と、
   前記全域木作成部、前記ＭＲＣファイル作成部およびリンクコスト値変更部の制御を行う反復制御部と、
   前記ＭＲＣファイル作成部により作成されたＭＲＣファイル群を出力する出力部とを備え、
   前記反復制御部は、
   （１）前記全域木作成部に、前記新たなリンクコストの集合Ｗ’１〜Ｗ’Ｎそれぞれのリンクコストの値を用いて全域木を作成させ、この作成させた全域木のうち、当該全域木によりＭＲＣファイルを作成した場合、前記ＭＲＣファイル管理情報に示される今まで作成したＭＲＣファイルに対し、新規に前記isolated nodeになる数およびisolated linkになる数が最も多い全域木を選択する処理と、
   （２）前記ＭＲＣファイル作成部に、前記選択された全域木によりＭＲＣファイルを作成させる処理と、
   （３）前記リンクコスト値変更部に、前記ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれの値に、ランダムな値を加算した新たなリンクコストの集合Ｗ’をＮ個作成させる処理とを
   前記ＭＲＣファイル作成管理情報において、前記トポロジに示されるすべてのノードがisolated nodeとなり、かつ、すべてのリンクがisolated linkとなるまで実行させることを特徴とするＭＲＣファイル作成装置。
2. 前記リンクコスト値変更部は、
   （１）前記ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれに、ランダムな値を加算して新たなリンクコストの集合Ｗ’をＮ個作成した後、
   （２）前記作成したＮ個の新たなリンクコストの集合Ｗ’それぞれについて、前記ＭＲＣファイルにおけるisolated node以外のノードに接続するリンクのリンクコストを１つ選択し、その選択したリンクコストを、ＯＳＰＦ（Open Shortest Path First）において設定可能な最小値に変更し、前記isolated node以外のノードに接続するリンクのリンクコストのうち、前記選択したリンクコスト以外のリンクのリンクコストを、ＯＳＰＦにおいて設定可能な最大値に変更することを特徴とする請求項１に記載のＭＲＣファイル作成装置。
3. 前記リンクコスト初期値作成部は、
   乱数を用いて、前記初期値ＷＯを複数個生成し、
   前記反復制御部は、
   前記生成した初期値Ｗ０をもとに、前記全域木作成部、前記ＭＲＣファイル作成部および前記リンクコスト値変更部によりＭＲＣファイル群を作成させる処理を、前記生成した初期値Ｗ０の個数分実行させ、
   前記作成したＭＲＣファイル群のうち、最もファイル数が少ないＭＲＣファイル群を選択し、
   前記出力部は、前記選択されたＭＲＣファイル群を出力することを特徴とする請求項１または請求項２に記載のＭＲＣファイル作成装置。
4. 前記反復制御部は、
   （１）前記ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれに、ランダムな値を加算して作成したＮ個の新たなリンクコストの集合Ｗ’をもとに全域木を作成し、この作成した全域木をもとにＭＲＣファイルを作成した場合、そのいずれの全域木によっても、前記ＭＲＣファイル作成管理情報に示される今まで作成したＭＲＣファイルに対し、新規にisolated nodeになるノードを増やすＭＲＣファイルを作成できなかったと判断したとき、
   （２）前記リンクコスト値変更部に、前記作成したＮ個の新たなリンクコストの集合Ｗ’それぞれについて、前記ＭＲＣファイルにおけるisolated node以外のノードに接続するリンクのリンクコストを１つ選択し、その選択したリンクコストを、ＯＳＰＦにおいて設定可能な最小値に変更し、前記isolated node以外のノードに接続するリンクのリンクコストのうち、前記選択したリンクコスト以外のリンクのリンクコストを、ＯＳＰＦにおいて設定可能な最大値に変更する処理を実行させることを特徴とする請求項１または請求項２に記載のＭＲＣファイル作成装置。
5. 請求項１から請求項４のいずれか１項に記載のＭＲＣファイル作成装置により作成されたＭＲＣファイル群を用いて、前記ネットワーク内のノード故障またはリンク故障発生時の経路制御を行う経路制御装置。
6. ネットワークにおけるノード故障発生時およびリンク故障発生時の迂回経路を示したＭＲＣファイルを作成し、前記ネットワークのトポロジを示したトポロジ情報と、そのトポロジに対し、今まで作成されたＭＲＣファイルにおいてisolated nodeとなったノードおよびisolated linkとなったリンクを示したＭＲＣファイル作成管理情報とを記憶する記憶部を備えるＭＲＣファイル作成装置が、
   乱数を用いて、前記トポロジにおけるリンクそれぞれのリンクコストの値の集合である初期値Ｗ０を生成するステップと、
   前記リンクコストの集合の初期値Ｗ０を用いて、Kruskal法により前記トポロジのリンクの少なくとも一部を削除し、前記トポロジの全域木を作成するステップと、
   前記トポロジを参照して、前記全域木作成部により作成された全域木における末端のノードを、前記ＭＲＣファイルにおけるisolated nodeとし、この末端のノードに接続するリンクをrestricted linkとし、前記全域木の作成において削除されたリンクをisolated linkとして、前記トポロジのＭＲＣファイルを作成し、その作成したＭＲＣファイルにおいて、isolated nodeとなったノードおよびisolated linkとなったリンクを前記ＭＲＣファイル管理情報に記録していくステップと、
   前記ＭＲＣファイルが作成された後、前記ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれの値に、ランダムな値を加算した新たなリンクコストの集合Ｗ’をＮ個作成するステップと、
   前記作成されたＭＲＣファイル群を出力するステップとを実行し、
   前記ＭＲＣファイル作成装置が、
   （１）前記新たなリンクコストの集合Ｗ’１〜Ｗ’Ｎそれぞれのリンクコストの値を用いてＮ個の全域木を作成し、この作成した全域木のうち、当該全域木によりＭＲＣファイルを作成した場合、前記ＭＲＣファイル管理情報に示される今まで作成したＭＲＣファイルに対し、新規に前記isolated nodeになる数およびisolated linkになる数が最も多い全域木を選択するステップと、
   （２）前記選択した全域木によりＭＲＣファイルを作成するステップと、
   （３）前記ＭＲＣファイルにおけるisolated link以外のリンクのリンクコストそれぞれの値に、ランダムな値を加算した新たなリンクコストの集合Ｗ’をＮ個作成するステップとを、
   前記ＭＲＣファイル作成管理情報において、前記トポロジに示されるすべてのノードがisolated nodeとなり、かつ、すべてのリンクがisolated linkとなるまで実行することを特徴とするＭＲＣファイル作成方法。
7. 請求項６に記載のＭＲＣファイル作成方法をコンピュータに実行させるためのプログラム。

Images