故障復旧方法およびノードならびにネットワーク
【課題】 リンクの故障が発生した場合にネットワークに負荷を与えることなく迅速に経路変更を実行しパケットに故障箇所を回避させる。
【解決手段】 自ノードが設置されたネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握し、この把握したツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出し、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知し、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けとったときには、経路を再計算する。また、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う。また、前記通知は、予め経路を指定して行う。
【解決手段】 自ノードが設置されたネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握し、この把握したツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出し、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知し、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けとったときには、経路を再計算する。また、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う。また、前記通知は、予め経路を指定して行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの故障復旧に利用する。特に、インターネットなどの大規模ネットワークに利用するに適する。
【背景技術】
【０００２】
インターネットが社会インフラとして整備されつつある現在、その信頼性の向上、中でもネットワーク故障時の迅速な復旧は極めて重要な課題である。伝送路の故障（光ファイバの切断など）やノードの故障（ルータやスイッチの故障）に対しては様々な対処方法が提案されて実用化されている。
【０００３】
一般的には装置および伝送路の冗長化が簡便で迅速かつ確実な復旧方法として広く用いられる。伝送路冗長化の具体例としては世界標準となっているＳＤＨ／ＳＯＮＥＴ(Synchronous Digital Hierarchy/Synchronous Optical Network)のＡＰＳ切替(Automatic Protection Switching)やＥｔｈｅｒｎｅｔ（登録商標）のＬｉｎｋ Ａｇｇｒｅｇａｔｉｏｎ等が挙げられる（非特許文献１参照）。装置の冗長としては主信号部や制御部の二重化等が行われる。
【０００４】
しかし、冗長化は装置およびネットワークの規模とコストを増大させるため全てを冗長化することは現実的でない。しかも、もともとインターネットは多数のネットワークの集合体であり、メッシュ状のトポロジーを基本としているため、本来的にネットワークとしての冗長性を有している。したがって、故障発生時には多くの場合に、パケットの経路変更を行って故障箇所を迂回させることが可能であり、復旧方法としてはその方がコストメリットが大きい。しかし、それを行うためには関係するノードで故障情報に基づいた経路の再計算を行い、新しい経路を設定することが必要となる。
【０００５】
インターネットはいくつもの自律系システム(Autonomous System)が相互接続されて構成されており、各自律系システムは基本的に一つの組織によって管理、運営され内部では同一のルーティングプロトコルが使用される。自律系システム内部のルーティングプロトコル(IGP:Interior Routing Protocol)としては、ＯＳＰＦ(Open Shortest Path First)やＩＳ−ＩＳ(Intermediate System to Intermediate System)が代表的であり世界的に広く使用されている（ＯＳＰＦはＩＥＴＦのＲＦＣ２３２８で標準化されている）。
【０００６】
これらはリンクステート(Link State)型のルーティングプロトコルと呼ばれ、概略、以下のような方法で経路を設定する。まず、各ノードに出入りするリンクには予めコスト(Cost)と呼ばれる重みがマニュアルで設定される。一般的にはリンクの伝送容量に逆比例するようにコストが設定されることが多い。
【０００７】
次に、各ノードはそこに繋がるリンクの状態とコストとを定期的にネットワーク内にフラッディング（ブロードキャスト）する。この結果、全ノードがネットワークトポロジーの情報を共有することとなる。しかる後に各ノードは経路コストが最小になるように各ノードへの経路を決定する。この経路計算には主にＤｉｊｋｓｔｒａのアルゴリズムと呼ばれる計算方法が用いられる。
【０００８】
経路計算の結果はツリー(shortest path treeまたはspanning tree)と呼ばれるリンクの集合となる。ツリーは全ノードを連結する最小限のリンクの集合である。このツリーの情報に基づいてルーティングテーブルを更新し、さらにフォワーディングテーブルを更新する。装置構成上、ルーティングテーブルは制御部に格納され、フォワーディングテーブルは各インタフェース部に格納される場合が多い。
【０００９】
以上述べた情報の収集と通知、経路計算およびその設定は通常、全てソフトウェアで周期的に処理される。図１は本発明実施例および従来例のノードにおけるルーティングプロトコルの実装位置を示す図である。図１に示すように、ノードは、制御部と主信号部とから構成され、制御部は、制御部ソフトウェア４および制御部ハードウェア７を含み、主信号部は、共通部（スイッチ）８およびインタフェース部９を含む。さらに、制御部ソフトウェア４は、アプリケーションソフトウェア５およびＯＳ（通信プロトコルを含む）６を含む。また、アプリケーションソフトウェア５は、ルーティングプロトコル１およびルーティングテーブル２を含む。また、インタフェース部９は、フォワーディングテーブル３を含む。
【００１０】
ソフトウェアの実装位置は図１に太枠で囲った部分（ルーティングプロトコル１）である。既存ルーティングプロトコルの処理フローを図３に示す（Ｓ１〜Ｓ８）。なお、経路の更新に必要な時間は設定する周期によって変わるが、通常、数秒から場合によっては数百秒となる。
【００１１】
すなわち、図３に示すように、定周期タイマが起動されると（Ｓ１）、まず、自ノードのリンク状態を取得し（Ｓ２）、取得したリンク状態をフラッディングにより他ノードに通知する（Ｓ３）。また、他ノードから通知されたリンク状態を取得し（Ｓ４）、これによりツリー計算を行って（Ｓ５）、ネットワークのツリー構造を把握すると共に、ルーティングテーブル２およびフォワーディングテーブル３を更新する（Ｓ６、Ｓ７）。この処理Ｓ１〜Ｓ７は、定周期タイマがタイムアウトすると（Ｓ８）、再び繰り返し実行される。
【００１２】
なお、図３は処理を簡単化して示しており、実際には故障やトポロジーに変化があった場合にも通知と経路の再計算が行われる。しかし、制御情報が氾濫したネットワークに負荷をかけることを避けるため、フラッディングの最小間隔が定められており、その間は故障を検出しても通知できないようになっている。ＯＳＰＦではこの最小間隔は５秒である。図３ではフラッディングの最小間隔の意味も含めてタイマによる周期的な処理として表現している。
【００１３】
周期を短く設定すると故障時の復旧時間が短くなるが、制御情報のフラッディングが頻繁に行われることでネットワークに負荷がかかり、主信号パケットの転送が圧迫される。周期は両者のトレードオフを勘案して設定される。ある箇所に故障が発生した場合には、次回の経路更新まではそこを通過するパケットが廃棄され信号断が継続する。信号断の時間をできるだけ短くするため、いくつかの提案がなされている（非特許文献２参照）。
【００１４】
【非特許文献１】ＩＴＵ−Ｔ標準Ｇ．８４１、ＩＥＥＥ８０２．３ａｄ
【非特許文献２】Ｓ．Ｒａｉ ｅｔ ａｌ．“ＩＰ Ｒｅｓｉｌｉｅｎｃｅ ｗｉｔｈｉｎ ａｎ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ：Ｃｕｒｒｅｎｔ Ａｐｐｒｏａｃｈｅｓ，Ｃｈａｌｌｅｎｇｅｓ，ａｎｄ Ｆｕｔｕｒｅ Ｄｉｒｅｃｔｉｏｎｓ”ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ Ｏｃｔｏｂｅｒ ２００５ ｐ１４２−１４９
【非特許文献３】Ｃ，Ａｌａｅｔｔｉｎｏｇｌｕ ｅｔ ａｌ．“Ｔｏｗａｒｄｓ Ｍｉｌｌｉｓｅｃｏｎｄ ＩＧＰ Ｃｏｎｖｅｒｇｅｎｃｅ”ＩＥＴＦ Ｉｎｔｅｒｎｅｔ Ｄｒａｆｔ ２０００
【非特許文献４】Ｓ．Ｌｅｅ ｅｔ ａｌ．“Ｐｒｏａｃｔｉｖｅ ｖｓ Ｒｅａｃｔｉｖｅ Ａｐｐｒｏａｃｈ ｔｏ Ｆａｉｌｕｒｅ Ｒｅｓｉｌｉｅｎｔ Ｒｏｕｔｉｎｇ”Ｐｒｏｃ．ＩＮＦＯＣＯＭ，Ｍａｒ．２００４
【非特許文献５】Ｓ．Ｖｅｌｌａｎｋｉ ｅｔ ａｌ．“Ｉｍｐｒｏｖｉｎｇ Ｓｅｒｖｉｃｅ Ａｖａｉｌａｂｉｌｉｔｙ Ｄｕｒｉｎｇ Ｌｉｎｋ Ｆａｉｌｕｒｅ Ｔｒａｎｓｉｅｎｔｓ ｔｈｒｏｕｇｈ Ａｌｔｅｒｎａｔｅ Ｒｏｕｔｉｎｇ”Ｔｅｘａｓ Ａ ＆ Ｍ Ｕｎｉｖ．，Ｔｅｃｈ．ｒｅｐ．ＴＡＭＵＥＣＥ−２００３−０２，Ｆｅｂ．２００３
【特許文献１】特開２００１−２３０７７６号公報
【特許文献２】特開２００３−２３４７７６号公報
【特許文献３】特表平５−５０２３４６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１５】
従来より提案されている方法の一つ（非特許文献３参照）は経路更新の周期を短縮し、迅速な経路再計算を行うものであるが、先に述べたように情報がネットワーク内に頻繁にフラッディングされるため、ネットワークに過度の負荷を与え、かつ局所的な故障に対しても全ノードで経路の再計算が行われるため、ノードのソフトウェアの負担も大きくなる。また、故障発生に備えて予め予備経路を計算しておく方法（非特許文献４または５参照）もあるが、全ての故障に対処するためには計算量が増大するため実現が難しい。
【００１６】
また、特許文献３には、故障発生を検出したノードが当該故障に関連するノードに限定して故障発生通知を行う方法が提案されている。当該提案によれば、故障発生通知がネットワーク全体に及ぼす影響を少なくすることができる。しかしながら、当該提案では、故障を検出したノードが、周辺ノードと連携して故障を効率良く迅速に復旧するための提案はなされていない。
【００１７】
本発明は、このような背景の下に行われたものであって、自律系パケット転送ネットワークにおいてリンクの故障が発生した場合にネットワークに負荷を与えることなく迅速に経路変更を実行しパケットに故障箇所を回避させることができる故障復旧方法およびノードならびにネットワークを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明は故障復旧方法であって、本発明の特徴とするところは、ネットワークに設置されたノードが、当該ネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握し、この把握したツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出し、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知し、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けとったときには、経路を再計算するところにある。
【００１９】
これによれば、故障の復旧に無関係のノードに対する故障通知を無くすことができるため、故障復旧に際し、ネットワークに負荷を与えることがない。さらに、自ノードの入出力リンクをツリーの一部とするノードの集合を予め抽出しておき、これらのノードと連携して故障復旧を行うことができるため、効率の良い故障復旧を迅速に行うことができる。なお、本発明を実現するためには、ネットワークのツリー構造を把握しておく必要があるが、ツリー情報の取得は、例えば、特許文献１または２による提案中にも記述されているように、フラッディング等により全ノード相互間でツリー情報を交換することにより実現することができる。
【００２０】
ここで、本発明の特徴を、前述した特許文献３による提案との比較によって説明する。特許文献３による提案では、既に説明したように、故障発生を検出したノードが当該故障に関連するノードに限定して故障発生通知を行うので、故障発生通知がネットワーク全体に及ぼす影響を少なくすることができるが、故障を検出したノードが、周辺ノードと連携して故障を効率良く復旧するための提案はなされていない。
【００２１】
すなわち、特許文献３の提案では、単に、伝送路における故障を検出し、その故障によって影響を受けているノードを通過する仮想回線に対して故障通知を送出しており、本発明のように、ツリー情報を各ノードで共有し、自ノードの入出力リンクをツリーの一部とするノードの集合に対して故障通知を行うものではない。
【００２２】
言い換えると、特許文献３による提案では、故障通知の送出先は、当該故障により直接影響を受けるノードのみである。これに対し、本発明による提案では、当該故障により直接影響を受けるノードでなくても、当該故障を復旧するために有用となるノード（迂回路を形成するために有用となるノード）に対しては故障通知が行われ、必要最小限のツリー構造の変更が行われる。よって、特許文献３の提案と比較して本発明の方が故障復旧をより効率良く行うことができる。
【００２３】
また、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行うことが望ましい。すなわち、自ノードの出力リンクの故障については、当該出力リンクを入力リンクとする他ノードからの通知を待たなければ実際の故障の有無はわからないが、自ノードで故障を検出した入力リンクと対になっている出力リンクについては、他ノードからの通知を待つこと無く、故障しているものとして扱うことにより、迅速かつ確実に故障復旧を行うことができる。
【００２４】
また、前記通知は、予め経路を指定して行うことが望ましい。これは途中のノードが現状（故障発生前）のフォワーディングテーブルを使用すると誤った転送が行われる可能性があるため、経路指定を行うことにより、確実に他ノードに情報を到達させることができる。
【００２５】
また、本発明をノードの観点からみることができる。すなわち、本発明は、ネットワークに設置されたノードであって、本発明の特徴とするところは、当該ネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握するツリー情報管理手段と、このツリー情報管理手段が把握するツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出するリンク共有ノード抽出手段と、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知する故障通知手段と、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けったときには、経路を再計算する経路計算手段とを備えたところにある。
【００２６】
また、前記経路計算手段は、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う手段を備えることが望ましい。さらに、前記故障通知手段は、予め経路を指定して前記通知を行う手段を備えることが望ましい。
【００２７】
また、本発明を、本発明のノードにより構成されたネットワークとしての観点からみることもできる。
【００２８】
さらに、本発明を、汎用の情報処理装置にインストールすることにより、その情報処理装置に、本発明のノードに相応する機能を実現させるプログラムとしての観点からみることもできる。本発明のプログラムは記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００２９】
これにより、汎用の情報処理装置を用いて、本発明のノードを実現することができる。
【発明の効果】
【００３０】
本発明によれば、自律系パケット転送ネットワークにおいてリンクの故障が発生した場合にネットワークに負荷を与えることなく迅速に経路変更を実行しパケットに故障箇所を回避させることができる。
【発明を実施するための最良の形態】
【００３１】
本発明実施例の故障復旧方法およびノードならびにネットワークを図１ないし図１４を参照して説明する。自律系システム内のルーティングプロトコルの一般的な説明は「背景技術」で述べたとおりである。本発明は、図１に示すように、ネットワークに設置されたノードのソフトウェアとして実装される。図１の太枠で囲ったルーティングプロトコル１の部分が実装位置を示す。
【００３２】
また、図２は本実施例のノードの機能ブロック構成図であるが、本実施例のルーティングプロトコル１を実装したノードを機能ブロックにより構成すると、図２に示すように、自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出するリンク共有ノード抽出部１１と、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知する故障対応部１２と、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けとったときには、経路を再計算する経路計算部１３とを備えたことを特徴とするノードである。
【００３３】
経路計算部１３は、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う。また、故障対応部１２は、予め経路を指定して前記通知を行う。
【００３４】
また、ツリー情報管理部１０は、他ノードからツリー情報を受信してネットワークのツリー構造を把握すると共に、他ノードに対してツリー情報を転送する。あるいは、自ノードに関係するリンクの状態を把握して自ノードを含むツリー情報を自ら計算して自ノードを含むツリー構造を把握すると共に、他ノードに対して計算した当該ツリー情報を転送する。また、経路計算部１３は、計算した経路に基づいてルーティングテーブル２またはフォワーディングテーブル３を生成または更新する。
【００３５】
さらに、本実施例は、汎用の情報処理装置にインストールすることにより、その情報処理装置に、本実施例のノードに相応する機能を実現させるプログラムとして実施することができる。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、本実施例のノードに相応する機能を実現させることができる。
【００３６】
本実施例の処理フローを図４に示す。図３に示す既存のリンクステート型ルーティングアルゴリズムＳ１〜Ｓ８（以下で既存アルゴリズムと記す）を基本とし、定周期のループの中に大きく２つの処理（処理♯１および処理♯２）を追加している。処理♯１はツリー情報の通知と受信および共有ノードの抽出である。処理♯２はリンク故障発生時のツリーの再計算と共有ノードへの通知である。
【００３７】
処理♯１（Ｓ２０〜Ｓ２５）および処理♯２（Ｓ３０〜Ｓ３４）の詳細をそれぞれ図５および図６に示す。すなわち、処理♯１は、図５に示すように、ツリー情報管理部１０により自ノードのツリー情報を他ノードに配信し（Ｓ２０）、他ノードからツリー情報を受信し（Ｓ２１）、受信したツリー情報の転送が必要ならば（Ｓ２２）、他ノードにもこのツリー情報を転送する（Ｓ２３）。これにより、全ノードのツリー情報が取得できたら（Ｓ２４）、リンク共有ノード抽出部１１によりリンク共有ノードの抽出を行う（Ｓ２５）。リンク共有ノードの定義は以下の説明の中で述べる。なお、ステップＳ２０の処理には、自ノードに関係するリンクの状態を把握して自ノードを含むツリー情報を自ら計算して自ノードを含むツリー構造を把握すると共に、他ノードに対して計算した当該ツリー情報を転送する処理を含む場合もある。
【００３８】
また、処理♯２は、図６に示すように、故障対応部１２によりリンク状態の変化を検出またはツリー情報管理部１０により通知パケットを受信したときには（Ｓ３０）、経路計算部１３は、自ノードに関係するツリーの再計算を行う（Ｓ３１）。これにより、ルーティングテーブル２を更新し（Ｓ３２）、フォワーディングテーブル３を更新する（Ｓ３３）。また、故障対応部１２は、自ノードが故障を検出したノードである場合には、故障検出を通知するパケットを作成してリンク共有ノードに対して送出する（Ｓ３４）。
【００３９】
本発明の基本的な考え方は、リンク故障の影響範囲（関係するノードの集合）を予め抽出しておき、故障検出時には直ちに経路を計算し影響範囲に通知すると共に通知先で経路の再計算を実行させるというものである。
【００４０】
故障の復旧に無関係のノードに対しては通知を行わないことで制御情報の転送を最小限に抑圧しネットワークに負荷をかけないようにする。ノードは、既存アルゴリズムで計算されるツリーの情報（リンクの集合）をこのツリーの経路に沿って全ノードに通知する。この通知パケットの構成を図７に示す。通知を受けたノードはこのツリー情報をメモリに格納すると共に他ノードへの転送の必要性を判断する。
【００４１】
通知を受けたノードがツリーの末端に位置していれば、さらなる転送は必要ない。ツリーの末端でなければ受け取った経路に沿って情報を転送する。ツリーの末端か否かは受け取ったリンクの集合の中に自ノードの出力リンクが含まれるか否かで判断する。この一種のマルチキャスト処理を全ノードが行うことにより全てのノードが互いのツリー情報を共有する。
【００４２】
次に、ノードは自装置の入出力リンクをツリーの一部とするノードの集合を抽出する。これらのノードをそれぞれのリンクの共有ノードと呼ぶ。共有ノードとはリンク故障時にもパケットの転送を継続するためにツリーを変更しなければならないノードの集合である。各ノードはリンクの故障に備えてそれぞれのリンクの共有ノードを予め抽出しておく。
【００４３】
今、ある入力リンクに故障が発生した場合を考える。検出したノードがそのリンクを自身のツリーの一部としていた場合は故障を加味してツリーの再計算を行わなければならない。また、故障リンクと対になる出力方向のリンクも同時に故障している可能性があるため、故障検出ノードはそのリンクへのパケットの転送を停止する。すなわち、故障検出ノードは双方向のリンクに故障が発生したとしてツリーを再計算する。また、この入出力リンクの共有ノードもツリーの再計算を行って故障リンクを回避する必要がある。
【００４４】
故障リンクおよびその対リンクがいずれのノードのツリーにも含まれていなければ再計算は必要でない。故障検出ノードは自身のツリーを再計算した後に故障リンクの共有ノードに故障発生を通知する。このとき、故障通知パケットはユニキャストとし、再計算された木（ツリー構造）に沿って転送を行う。この故障通知パケットの構成を図８に示す。故障通知パケットはルートオプションで経路を指定して送信する。これは途中のノードが現状（故障発生前）のフォワーディングテーブルを使用すると誤った転送が行われる可能性があるため、経路指定を行って確実に共有ノードに情報を到達させるためである。
【００４５】
通知を受け取ったノードは故障情報に基づいて経路すなわちツリーの再計算を行い、ルーティングテーブルとフォワーディングテーブルを更新する。これらの更新は既存アルゴリズムの次回の定周期動作までの暫定的なものであり、ネットワーク全体が最終的に正確なトポロジー情報を共有することは既存アルゴリズムの次回の定周期処理によって確保される。
【００４６】
以下、図９のネットワークを具体例として上記アルゴリズムを説明する。図９のＡ〜Ｆはノードを示し、それらを結ぶ直線はリンクを示している。リンクは双方向独立に存在する。例えば、ノードＣはＢ→Ｃ、Ｄ→Ｃ、Ｆ→Ｃの３つの入力リンクとＣ→Ｂ、Ｃ→Ｄ、Ｃ→Ｆの３つの出力リンクとを有する。リンクに付された数字はコストを示しており、経路計算を行う際に使用される。この例では双方向で同じ値のコストを使用する。
【００４７】
図１０は各ノードについて計算されたツリーを太線の矢印で示している。リンクＢ→ＣはノードＡとノードＢのツリーで共有されている。また、リンクＣ→ＢはノードＣとノードＦのツリーで共有されている。したがって、リンクＢ→Ｃのリンク共有ノードはＡ、Ｂ、Ｃ、Ｆとなる。
【００４８】
リンクＢ→Ｃに故障が発生した場合には、ノードＡ、Ｂ、Ｃ、Ｆがツリーの再計算を迫られることを意味している。そこで図１１（ａ）に示すように実際にリンクＢ→Ｃに故障が発生したとする。これはノードＣで検出され、Ｃはこの情報に基づいてツリーを再計算し、ルーティングテーブルとフォワーディングテーブルを更新する。再計算されたツリーを図１１（ｂ）に示す。
【００４９】
次に、ノードＣは新しく計算されたツリーに沿ってノードＡ、ノードＢ、ノードＦにユニキャストで個別に故障を通知する。このとき、通知パケットにはルートオプションを使用し経路指定を行う。通知を受けたノードＡ、Ｂ、ＦはリンクＢ→ＣとリンクＣ→Ｂとを回避するようにツリーを再計算する。それぞれのノードで再計算されたツリーを図１１（ｃ）、（ｄ）、（ｅ）に示す。ノードＤとノードＥとはリンクＢ→ＣとリンクＣ→Ｂのいずれもツリーには含んでおらず、再計算は必要でない。したがって、これらのノードに対する故障の通知も必要でない。図１２はリンクＣ→Ｄに故障が発生した場合の各ノードのツリー変更を示している。この場合はノードＤ、Ｃ、Ｆにツリー変更が必要となり、ノードＡ、Ｂ、Ｅはツリー変更は必要でない。
【００５０】
図１３に示すテーブル♯１は全ノードの入力リンクの共有ノードを示したものである。共有ノードは以上説明したように故障発生に備えて予め抽出しておくノードの情報である。図１４に示すテーブル♯２はリンクに故障が発生した場合の通知先および通知パケット送出リンクを示している。送出リンクは故障発生後に新しいツリーを計算した上で決定される。
【００５１】
以上述べたように本発明はリンク故障の影響範囲を予め特定しておき、故障情報を必要な箇所のみ転送することで新たな経路を迅速に計算させ故障箇所の迂回を実現する。必要最小限の情報を最短経路で配信するためネットワークへ負荷をかけることなく迅速な経路変更を行えるという効果がある。
【００５２】
また、本発明は、既存ルーティングプロトコルを新たなソフトウェアで置き換えることにより実現できるが、適切なソフトウェアインタフェースを設定することにより既存プロトコルと協働動作をする（追加処理）ソフトウェアとして実現することもできる。
【産業上の利用可能性】
【００５３】
本発明によれば、自律系パケット転送ネットワークにおいてリンクの故障が発生した場合にネットワークに負荷を与えることなく迅速に経路変更を実行しパケットに故障箇所を回避させることができるので、ネットワークを効率良く運用することができると共に、ネットワークユーザに対するサービス品質を向上させることができる。
【図面の簡単な説明】
【００５４】
【図１】本実施例および従来例のノードにおけるルーティングプロトコルの実装位置を示す図。
【図２】本実施例のノードの機能ブロック構成図。
【図３】既存アルゴリズムを示すフローチャート。
【図４】本実施例の故障復旧方法の処理手順を示すフローチャート。
【図５】本実施例の処理♯１の手順を示すフローチャート。
【図６】本実施例の処理♯２の手順を示すフローチャート。
【図７】本実施例のツリー通知パケットの構成図。
【図８】本実施例の故障通知パケットの構成図。
【図９】本実施例の故障復旧方法を説明するためのネットワーク例を示す図。
【図１０】リンク共有ノードを説明するための図。
【図１１】本実施例の故障復旧方法を説明するための図。
【図１２】本実施例の故障復旧方法を説明するための図。
【図１３】テーブル♯１（各リンクの共有ノード）を示す図。
【図１４】テーブル♯２（リンク故障時の通知パケット送出先ノード）を示す図。
【符号の説明】
【００５５】
１ ルーティングプロトコル
２ ルーティングテーブル
３ フォワーディングテーブル
４ 制御部ソフトウェア
５ アプリケーションソフトウェア
６ ＯＳ
７ 制御部ハードウェア
８ 共通部
９ インタフェース部
１０ ツリー情報管理部
１１ リンク共有ノード抽出部
１２ 故障対応部
１３ 経路計算部
【技術分野】
【０００１】
本発明は、ネットワークの故障復旧に利用する。特に、インターネットなどの大規模ネットワークに利用するに適する。
【背景技術】
【０００２】
インターネットが社会インフラとして整備されつつある現在、その信頼性の向上、中でもネットワーク故障時の迅速な復旧は極めて重要な課題である。伝送路の故障（光ファイバの切断など）やノードの故障（ルータやスイッチの故障）に対しては様々な対処方法が提案されて実用化されている。
【０００３】
一般的には装置および伝送路の冗長化が簡便で迅速かつ確実な復旧方法として広く用いられる。伝送路冗長化の具体例としては世界標準となっているＳＤＨ／ＳＯＮＥＴ(Synchronous Digital Hierarchy/Synchronous Optical Network)のＡＰＳ切替(Automatic Protection Switching)やＥｔｈｅｒｎｅｔ（登録商標）のＬｉｎｋ Ａｇｇｒｅｇａｔｉｏｎ等が挙げられる（非特許文献１参照）。装置の冗長としては主信号部や制御部の二重化等が行われる。
【０００４】
しかし、冗長化は装置およびネットワークの規模とコストを増大させるため全てを冗長化することは現実的でない。しかも、もともとインターネットは多数のネットワークの集合体であり、メッシュ状のトポロジーを基本としているため、本来的にネットワークとしての冗長性を有している。したがって、故障発生時には多くの場合に、パケットの経路変更を行って故障箇所を迂回させることが可能であり、復旧方法としてはその方がコストメリットが大きい。しかし、それを行うためには関係するノードで故障情報に基づいた経路の再計算を行い、新しい経路を設定することが必要となる。
【０００５】
インターネットはいくつもの自律系システム(Autonomous System)が相互接続されて構成されており、各自律系システムは基本的に一つの組織によって管理、運営され内部では同一のルーティングプロトコルが使用される。自律系システム内部のルーティングプロトコル(IGP:Interior Routing Protocol)としては、ＯＳＰＦ(Open Shortest Path First)やＩＳ−ＩＳ(Intermediate System to Intermediate System)が代表的であり世界的に広く使用されている（ＯＳＰＦはＩＥＴＦのＲＦＣ２３２８で標準化されている）。
【０００６】
これらはリンクステート(Link State)型のルーティングプロトコルと呼ばれ、概略、以下のような方法で経路を設定する。まず、各ノードに出入りするリンクには予めコスト(Cost)と呼ばれる重みがマニュアルで設定される。一般的にはリンクの伝送容量に逆比例するようにコストが設定されることが多い。
【０００７】
次に、各ノードはそこに繋がるリンクの状態とコストとを定期的にネットワーク内にフラッディング（ブロードキャスト）する。この結果、全ノードがネットワークトポロジーの情報を共有することとなる。しかる後に各ノードは経路コストが最小になるように各ノードへの経路を決定する。この経路計算には主にＤｉｊｋｓｔｒａのアルゴリズムと呼ばれる計算方法が用いられる。
【０００８】
経路計算の結果はツリー(shortest path treeまたはspanning tree)と呼ばれるリンクの集合となる。ツリーは全ノードを連結する最小限のリンクの集合である。このツリーの情報に基づいてルーティングテーブルを更新し、さらにフォワーディングテーブルを更新する。装置構成上、ルーティングテーブルは制御部に格納され、フォワーディングテーブルは各インタフェース部に格納される場合が多い。
【０００９】
以上述べた情報の収集と通知、経路計算およびその設定は通常、全てソフトウェアで周期的に処理される。図１は本発明実施例および従来例のノードにおけるルーティングプロトコルの実装位置を示す図である。図１に示すように、ノードは、制御部と主信号部とから構成され、制御部は、制御部ソフトウェア４および制御部ハードウェア７を含み、主信号部は、共通部（スイッチ）８およびインタフェース部９を含む。さらに、制御部ソフトウェア４は、アプリケーションソフトウェア５およびＯＳ（通信プロトコルを含む）６を含む。また、アプリケーションソフトウェア５は、ルーティングプロトコル１およびルーティングテーブル２を含む。また、インタフェース部９は、フォワーディングテーブル３を含む。
【００１０】
ソフトウェアの実装位置は図１に太枠で囲った部分（ルーティングプロトコル１）である。既存ルーティングプロトコルの処理フローを図３に示す（Ｓ１〜Ｓ８）。なお、経路の更新に必要な時間は設定する周期によって変わるが、通常、数秒から場合によっては数百秒となる。
【００１１】
すなわち、図３に示すように、定周期タイマが起動されると（Ｓ１）、まず、自ノードのリンク状態を取得し（Ｓ２）、取得したリンク状態をフラッディングにより他ノードに通知する（Ｓ３）。また、他ノードから通知されたリンク状態を取得し（Ｓ４）、これによりツリー計算を行って（Ｓ５）、ネットワークのツリー構造を把握すると共に、ルーティングテーブル２およびフォワーディングテーブル３を更新する（Ｓ６、Ｓ７）。この処理Ｓ１〜Ｓ７は、定周期タイマがタイムアウトすると（Ｓ８）、再び繰り返し実行される。
【００１２】
なお、図３は処理を簡単化して示しており、実際には故障やトポロジーに変化があった場合にも通知と経路の再計算が行われる。しかし、制御情報が氾濫したネットワークに負荷をかけることを避けるため、フラッディングの最小間隔が定められており、その間は故障を検出しても通知できないようになっている。ＯＳＰＦではこの最小間隔は５秒である。図３ではフラッディングの最小間隔の意味も含めてタイマによる周期的な処理として表現している。
【００１３】
周期を短く設定すると故障時の復旧時間が短くなるが、制御情報のフラッディングが頻繁に行われることでネットワークに負荷がかかり、主信号パケットの転送が圧迫される。周期は両者のトレードオフを勘案して設定される。ある箇所に故障が発生した場合には、次回の経路更新まではそこを通過するパケットが廃棄され信号断が継続する。信号断の時間をできるだけ短くするため、いくつかの提案がなされている（非特許文献２参照）。
【００１４】
【非特許文献１】ＩＴＵ−Ｔ標準Ｇ．８４１、ＩＥＥＥ８０２．３ａｄ
【非特許文献２】Ｓ．Ｒａｉ ｅｔ ａｌ．“ＩＰ Ｒｅｓｉｌｉｅｎｃｅ ｗｉｔｈｉｎ ａｎ Ａｕｔｏｎｏｍｏｕｓ Ｓｙｓｔｅｍ：Ｃｕｒｒｅｎｔ Ａｐｐｒｏａｃｈｅｓ，Ｃｈａｌｌｅｎｇｅｓ，ａｎｄ Ｆｕｔｕｒｅ Ｄｉｒｅｃｔｉｏｎｓ”ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ Ｏｃｔｏｂｅｒ ２００５ ｐ１４２−１４９
【非特許文献３】Ｃ，Ａｌａｅｔｔｉｎｏｇｌｕ ｅｔ ａｌ．“Ｔｏｗａｒｄｓ Ｍｉｌｌｉｓｅｃｏｎｄ ＩＧＰ Ｃｏｎｖｅｒｇｅｎｃｅ”ＩＥＴＦ Ｉｎｔｅｒｎｅｔ Ｄｒａｆｔ ２０００
【非特許文献４】Ｓ．Ｌｅｅ ｅｔ ａｌ．“Ｐｒｏａｃｔｉｖｅ ｖｓ Ｒｅａｃｔｉｖｅ Ａｐｐｒｏａｃｈ ｔｏ Ｆａｉｌｕｒｅ Ｒｅｓｉｌｉｅｎｔ Ｒｏｕｔｉｎｇ”Ｐｒｏｃ．ＩＮＦＯＣＯＭ，Ｍａｒ．２００４
【非特許文献５】Ｓ．Ｖｅｌｌａｎｋｉ ｅｔ ａｌ．“Ｉｍｐｒｏｖｉｎｇ Ｓｅｒｖｉｃｅ Ａｖａｉｌａｂｉｌｉｔｙ Ｄｕｒｉｎｇ Ｌｉｎｋ Ｆａｉｌｕｒｅ Ｔｒａｎｓｉｅｎｔｓ ｔｈｒｏｕｇｈ Ａｌｔｅｒｎａｔｅ Ｒｏｕｔｉｎｇ”Ｔｅｘａｓ Ａ ＆ Ｍ Ｕｎｉｖ．，Ｔｅｃｈ．ｒｅｐ．ＴＡＭＵＥＣＥ−２００３−０２，Ｆｅｂ．２００３
【特許文献１】特開２００１−２３０７７６号公報
【特許文献２】特開２００３−２３４７７６号公報
【特許文献３】特表平５−５０２３４６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１５】
従来より提案されている方法の一つ（非特許文献３参照）は経路更新の周期を短縮し、迅速な経路再計算を行うものであるが、先に述べたように情報がネットワーク内に頻繁にフラッディングされるため、ネットワークに過度の負荷を与え、かつ局所的な故障に対しても全ノードで経路の再計算が行われるため、ノードのソフトウェアの負担も大きくなる。また、故障発生に備えて予め予備経路を計算しておく方法（非特許文献４または５参照）もあるが、全ての故障に対処するためには計算量が増大するため実現が難しい。
【００１６】
また、特許文献３には、故障発生を検出したノードが当該故障に関連するノードに限定して故障発生通知を行う方法が提案されている。当該提案によれば、故障発生通知がネットワーク全体に及ぼす影響を少なくすることができる。しかしながら、当該提案では、故障を検出したノードが、周辺ノードと連携して故障を効率良く迅速に復旧するための提案はなされていない。
【００１７】
本発明は、このような背景の下に行われたものであって、自律系パケット転送ネットワークにおいてリンクの故障が発生した場合にネットワークに負荷を与えることなく迅速に経路変更を実行しパケットに故障箇所を回避させることができる故障復旧方法およびノードならびにネットワークを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明は故障復旧方法であって、本発明の特徴とするところは、ネットワークに設置されたノードが、当該ネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握し、この把握したツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出し、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知し、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けとったときには、経路を再計算するところにある。
【００１９】
これによれば、故障の復旧に無関係のノードに対する故障通知を無くすことができるため、故障復旧に際し、ネットワークに負荷を与えることがない。さらに、自ノードの入出力リンクをツリーの一部とするノードの集合を予め抽出しておき、これらのノードと連携して故障復旧を行うことができるため、効率の良い故障復旧を迅速に行うことができる。なお、本発明を実現するためには、ネットワークのツリー構造を把握しておく必要があるが、ツリー情報の取得は、例えば、特許文献１または２による提案中にも記述されているように、フラッディング等により全ノード相互間でツリー情報を交換することにより実現することができる。
【００２０】
ここで、本発明の特徴を、前述した特許文献３による提案との比較によって説明する。特許文献３による提案では、既に説明したように、故障発生を検出したノードが当該故障に関連するノードに限定して故障発生通知を行うので、故障発生通知がネットワーク全体に及ぼす影響を少なくすることができるが、故障を検出したノードが、周辺ノードと連携して故障を効率良く復旧するための提案はなされていない。
【００２１】
すなわち、特許文献３の提案では、単に、伝送路における故障を検出し、その故障によって影響を受けているノードを通過する仮想回線に対して故障通知を送出しており、本発明のように、ツリー情報を各ノードで共有し、自ノードの入出力リンクをツリーの一部とするノードの集合に対して故障通知を行うものではない。
【００２２】
言い換えると、特許文献３による提案では、故障通知の送出先は、当該故障により直接影響を受けるノードのみである。これに対し、本発明による提案では、当該故障により直接影響を受けるノードでなくても、当該故障を復旧するために有用となるノード（迂回路を形成するために有用となるノード）に対しては故障通知が行われ、必要最小限のツリー構造の変更が行われる。よって、特許文献３の提案と比較して本発明の方が故障復旧をより効率良く行うことができる。
【００２３】
また、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行うことが望ましい。すなわち、自ノードの出力リンクの故障については、当該出力リンクを入力リンクとする他ノードからの通知を待たなければ実際の故障の有無はわからないが、自ノードで故障を検出した入力リンクと対になっている出力リンクについては、他ノードからの通知を待つこと無く、故障しているものとして扱うことにより、迅速かつ確実に故障復旧を行うことができる。
【００２４】
また、前記通知は、予め経路を指定して行うことが望ましい。これは途中のノードが現状（故障発生前）のフォワーディングテーブルを使用すると誤った転送が行われる可能性があるため、経路指定を行うことにより、確実に他ノードに情報を到達させることができる。
【００２５】
また、本発明をノードの観点からみることができる。すなわち、本発明は、ネットワークに設置されたノードであって、本発明の特徴とするところは、当該ネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握するツリー情報管理手段と、このツリー情報管理手段が把握するツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出するリンク共有ノード抽出手段と、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知する故障通知手段と、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けったときには、経路を再計算する経路計算手段とを備えたところにある。
【００２６】
また、前記経路計算手段は、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う手段を備えることが望ましい。さらに、前記故障通知手段は、予め経路を指定して前記通知を行う手段を備えることが望ましい。
【００２７】
また、本発明を、本発明のノードにより構成されたネットワークとしての観点からみることもできる。
【００２８】
さらに、本発明を、汎用の情報処理装置にインストールすることにより、その情報処理装置に、本発明のノードに相応する機能を実現させるプログラムとしての観点からみることもできる。本発明のプログラムは記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００２９】
これにより、汎用の情報処理装置を用いて、本発明のノードを実現することができる。
【発明の効果】
【００３０】
本発明によれば、自律系パケット転送ネットワークにおいてリンクの故障が発生した場合にネットワークに負荷を与えることなく迅速に経路変更を実行しパケットに故障箇所を回避させることができる。
【発明を実施するための最良の形態】
【００３１】
本発明実施例の故障復旧方法およびノードならびにネットワークを図１ないし図１４を参照して説明する。自律系システム内のルーティングプロトコルの一般的な説明は「背景技術」で述べたとおりである。本発明は、図１に示すように、ネットワークに設置されたノードのソフトウェアとして実装される。図１の太枠で囲ったルーティングプロトコル１の部分が実装位置を示す。
【００３２】
また、図２は本実施例のノードの機能ブロック構成図であるが、本実施例のルーティングプロトコル１を実装したノードを機能ブロックにより構成すると、図２に示すように、自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出するリンク共有ノード抽出部１１と、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知する故障対応部１２と、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けとったときには、経路を再計算する経路計算部１３とを備えたことを特徴とするノードである。
【００３３】
経路計算部１３は、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う。また、故障対応部１２は、予め経路を指定して前記通知を行う。
【００３４】
また、ツリー情報管理部１０は、他ノードからツリー情報を受信してネットワークのツリー構造を把握すると共に、他ノードに対してツリー情報を転送する。あるいは、自ノードに関係するリンクの状態を把握して自ノードを含むツリー情報を自ら計算して自ノードを含むツリー構造を把握すると共に、他ノードに対して計算した当該ツリー情報を転送する。また、経路計算部１３は、計算した経路に基づいてルーティングテーブル２またはフォワーディングテーブル３を生成または更新する。
【００３５】
さらに、本実施例は、汎用の情報処理装置にインストールすることにより、その情報処理装置に、本実施例のノードに相応する機能を実現させるプログラムとして実施することができる。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、本実施例のノードに相応する機能を実現させることができる。
【００３６】
本実施例の処理フローを図４に示す。図３に示す既存のリンクステート型ルーティングアルゴリズムＳ１〜Ｓ８（以下で既存アルゴリズムと記す）を基本とし、定周期のループの中に大きく２つの処理（処理♯１および処理♯２）を追加している。処理♯１はツリー情報の通知と受信および共有ノードの抽出である。処理♯２はリンク故障発生時のツリーの再計算と共有ノードへの通知である。
【００３７】
処理♯１（Ｓ２０〜Ｓ２５）および処理♯２（Ｓ３０〜Ｓ３４）の詳細をそれぞれ図５および図６に示す。すなわち、処理♯１は、図５に示すように、ツリー情報管理部１０により自ノードのツリー情報を他ノードに配信し（Ｓ２０）、他ノードからツリー情報を受信し（Ｓ２１）、受信したツリー情報の転送が必要ならば（Ｓ２２）、他ノードにもこのツリー情報を転送する（Ｓ２３）。これにより、全ノードのツリー情報が取得できたら（Ｓ２４）、リンク共有ノード抽出部１１によりリンク共有ノードの抽出を行う（Ｓ２５）。リンク共有ノードの定義は以下の説明の中で述べる。なお、ステップＳ２０の処理には、自ノードに関係するリンクの状態を把握して自ノードを含むツリー情報を自ら計算して自ノードを含むツリー構造を把握すると共に、他ノードに対して計算した当該ツリー情報を転送する処理を含む場合もある。
【００３８】
また、処理♯２は、図６に示すように、故障対応部１２によりリンク状態の変化を検出またはツリー情報管理部１０により通知パケットを受信したときには（Ｓ３０）、経路計算部１３は、自ノードに関係するツリーの再計算を行う（Ｓ３１）。これにより、ルーティングテーブル２を更新し（Ｓ３２）、フォワーディングテーブル３を更新する（Ｓ３３）。また、故障対応部１２は、自ノードが故障を検出したノードである場合には、故障検出を通知するパケットを作成してリンク共有ノードに対して送出する（Ｓ３４）。
【００３９】
本発明の基本的な考え方は、リンク故障の影響範囲（関係するノードの集合）を予め抽出しておき、故障検出時には直ちに経路を計算し影響範囲に通知すると共に通知先で経路の再計算を実行させるというものである。
【００４０】
故障の復旧に無関係のノードに対しては通知を行わないことで制御情報の転送を最小限に抑圧しネットワークに負荷をかけないようにする。ノードは、既存アルゴリズムで計算されるツリーの情報（リンクの集合）をこのツリーの経路に沿って全ノードに通知する。この通知パケットの構成を図７に示す。通知を受けたノードはこのツリー情報をメモリに格納すると共に他ノードへの転送の必要性を判断する。
【００４１】
通知を受けたノードがツリーの末端に位置していれば、さらなる転送は必要ない。ツリーの末端でなければ受け取った経路に沿って情報を転送する。ツリーの末端か否かは受け取ったリンクの集合の中に自ノードの出力リンクが含まれるか否かで判断する。この一種のマルチキャスト処理を全ノードが行うことにより全てのノードが互いのツリー情報を共有する。
【００４２】
次に、ノードは自装置の入出力リンクをツリーの一部とするノードの集合を抽出する。これらのノードをそれぞれのリンクの共有ノードと呼ぶ。共有ノードとはリンク故障時にもパケットの転送を継続するためにツリーを変更しなければならないノードの集合である。各ノードはリンクの故障に備えてそれぞれのリンクの共有ノードを予め抽出しておく。
【００４３】
今、ある入力リンクに故障が発生した場合を考える。検出したノードがそのリンクを自身のツリーの一部としていた場合は故障を加味してツリーの再計算を行わなければならない。また、故障リンクと対になる出力方向のリンクも同時に故障している可能性があるため、故障検出ノードはそのリンクへのパケットの転送を停止する。すなわち、故障検出ノードは双方向のリンクに故障が発生したとしてツリーを再計算する。また、この入出力リンクの共有ノードもツリーの再計算を行って故障リンクを回避する必要がある。
【００４４】
故障リンクおよびその対リンクがいずれのノードのツリーにも含まれていなければ再計算は必要でない。故障検出ノードは自身のツリーを再計算した後に故障リンクの共有ノードに故障発生を通知する。このとき、故障通知パケットはユニキャストとし、再計算された木（ツリー構造）に沿って転送を行う。この故障通知パケットの構成を図８に示す。故障通知パケットはルートオプションで経路を指定して送信する。これは途中のノードが現状（故障発生前）のフォワーディングテーブルを使用すると誤った転送が行われる可能性があるため、経路指定を行って確実に共有ノードに情報を到達させるためである。
【００４５】
通知を受け取ったノードは故障情報に基づいて経路すなわちツリーの再計算を行い、ルーティングテーブルとフォワーディングテーブルを更新する。これらの更新は既存アルゴリズムの次回の定周期動作までの暫定的なものであり、ネットワーク全体が最終的に正確なトポロジー情報を共有することは既存アルゴリズムの次回の定周期処理によって確保される。
【００４６】
以下、図９のネットワークを具体例として上記アルゴリズムを説明する。図９のＡ〜Ｆはノードを示し、それらを結ぶ直線はリンクを示している。リンクは双方向独立に存在する。例えば、ノードＣはＢ→Ｃ、Ｄ→Ｃ、Ｆ→Ｃの３つの入力リンクとＣ→Ｂ、Ｃ→Ｄ、Ｃ→Ｆの３つの出力リンクとを有する。リンクに付された数字はコストを示しており、経路計算を行う際に使用される。この例では双方向で同じ値のコストを使用する。
【００４７】
図１０は各ノードについて計算されたツリーを太線の矢印で示している。リンクＢ→ＣはノードＡとノードＢのツリーで共有されている。また、リンクＣ→ＢはノードＣとノードＦのツリーで共有されている。したがって、リンクＢ→Ｃのリンク共有ノードはＡ、Ｂ、Ｃ、Ｆとなる。
【００４８】
リンクＢ→Ｃに故障が発生した場合には、ノードＡ、Ｂ、Ｃ、Ｆがツリーの再計算を迫られることを意味している。そこで図１１（ａ）に示すように実際にリンクＢ→Ｃに故障が発生したとする。これはノードＣで検出され、Ｃはこの情報に基づいてツリーを再計算し、ルーティングテーブルとフォワーディングテーブルを更新する。再計算されたツリーを図１１（ｂ）に示す。
【００４９】
次に、ノードＣは新しく計算されたツリーに沿ってノードＡ、ノードＢ、ノードＦにユニキャストで個別に故障を通知する。このとき、通知パケットにはルートオプションを使用し経路指定を行う。通知を受けたノードＡ、Ｂ、ＦはリンクＢ→ＣとリンクＣ→Ｂとを回避するようにツリーを再計算する。それぞれのノードで再計算されたツリーを図１１（ｃ）、（ｄ）、（ｅ）に示す。ノードＤとノードＥとはリンクＢ→ＣとリンクＣ→Ｂのいずれもツリーには含んでおらず、再計算は必要でない。したがって、これらのノードに対する故障の通知も必要でない。図１２はリンクＣ→Ｄに故障が発生した場合の各ノードのツリー変更を示している。この場合はノードＤ、Ｃ、Ｆにツリー変更が必要となり、ノードＡ、Ｂ、Ｅはツリー変更は必要でない。
【００５０】
図１３に示すテーブル♯１は全ノードの入力リンクの共有ノードを示したものである。共有ノードは以上説明したように故障発生に備えて予め抽出しておくノードの情報である。図１４に示すテーブル♯２はリンクに故障が発生した場合の通知先および通知パケット送出リンクを示している。送出リンクは故障発生後に新しいツリーを計算した上で決定される。
【００５１】
以上述べたように本発明はリンク故障の影響範囲を予め特定しておき、故障情報を必要な箇所のみ転送することで新たな経路を迅速に計算させ故障箇所の迂回を実現する。必要最小限の情報を最短経路で配信するためネットワークへ負荷をかけることなく迅速な経路変更を行えるという効果がある。
【００５２】
また、本発明は、既存ルーティングプロトコルを新たなソフトウェアで置き換えることにより実現できるが、適切なソフトウェアインタフェースを設定することにより既存プロトコルと協働動作をする（追加処理）ソフトウェアとして実現することもできる。
【産業上の利用可能性】
【００５３】
本発明によれば、自律系パケット転送ネットワークにおいてリンクの故障が発生した場合にネットワークに負荷を与えることなく迅速に経路変更を実行しパケットに故障箇所を回避させることができるので、ネットワークを効率良く運用することができると共に、ネットワークユーザに対するサービス品質を向上させることができる。
【図面の簡単な説明】
【００５４】
【図１】本実施例および従来例のノードにおけるルーティングプロトコルの実装位置を示す図。
【図２】本実施例のノードの機能ブロック構成図。
【図３】既存アルゴリズムを示すフローチャート。
【図４】本実施例の故障復旧方法の処理手順を示すフローチャート。
【図５】本実施例の処理♯１の手順を示すフローチャート。
【図６】本実施例の処理♯２の手順を示すフローチャート。
【図７】本実施例のツリー通知パケットの構成図。
【図８】本実施例の故障通知パケットの構成図。
【図９】本実施例の故障復旧方法を説明するためのネットワーク例を示す図。
【図１０】リンク共有ノードを説明するための図。
【図１１】本実施例の故障復旧方法を説明するための図。
【図１２】本実施例の故障復旧方法を説明するための図。
【図１３】テーブル♯１（各リンクの共有ノード）を示す図。
【図１４】テーブル♯２（リンク故障時の通知パケット送出先ノード）を示す図。
【符号の説明】
【００５５】
１ ルーティングプロトコル
２ ルーティングテーブル
３ フォワーディングテーブル
４ 制御部ソフトウェア
５ アプリケーションソフトウェア
６ ＯＳ
７ 制御部ハードウェア
８ 共通部
９ インタフェース部
１０ ツリー情報管理部
１１ リンク共有ノード抽出部
１２ 故障対応部
１３ 経路計算部
【特許請求の範囲】
【請求項１】
ネットワークに設置されたノードが、当該ネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握し、この把握したツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出し、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知し、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けとったときには、経路を再計算する故障復旧方法。
【請求項２】
故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う請求項１記載の故障復旧方法。
【請求項３】
前記通知は、予め経路を指定して行う請求項１記載の故障復旧方法。
【請求項４】
ネットワークに設置されたノードにおいて、
当該ネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握するツリー情報管理手段と、
このツリー情報管理手段が把握するツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出するリンク共有ノード抽出手段と、
当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知する故障通知手段と、
自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けったときには、経路を再計算する経路計算手段と
を備えたことを特徴とするノード。
【請求項５】
前記経路計算手段は、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う手段を備えた請求項４記載のノード。
【請求項６】
前記故障通知手段は、予め経路を指定して前記通知を行う手段を備えた請求項４記載のノード。
【請求項７】
請求項４ないし６のいずれかに記載のノードにより構成されたネットワーク。
【請求項８】
汎用の情報処理装置にインストールすることにより、その情報処理装置に、請求項４ないし６のいずれかに記載のノードに相応する機能を実現させるプログラム。
【請求項１】
ネットワークに設置されたノードが、当該ネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握し、この把握したツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出し、当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知し、自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けとったときには、経路を再計算する故障復旧方法。
【請求項２】
故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う請求項１記載の故障復旧方法。
【請求項３】
前記通知は、予め経路を指定して行う請求項１記載の故障復旧方法。
【請求項４】
ネットワークに設置されたノードにおいて、
当該ネットワークのツリー情報を他ノードから取得あるいは自ら計算して把握するツリー情報管理手段と、
このツリー情報管理手段が把握するツリー情報に基づき自ノードの入出力リンクをツリーの一部とするノードの集合を当該リンク故障の影響範囲として予め抽出するリンク共有ノード抽出手段と、
当該リンクの故障検出時には故障を検出した旨を前記影響範囲に限定して通知する故障通知手段と、
自ノードが故障を検出したとき、あるいは、他ノードから前記通知を受けったときには、経路を再計算する経路計算手段と
を備えたことを特徴とするノード。
【請求項５】
前記経路計算手段は、故障が検出された入力リンクと対になる出力リンクについても同時に故障が発生していると仮定して経路の再計算を行う手段を備えた請求項４記載のノード。
【請求項６】
前記故障通知手段は、予め経路を指定して前記通知を行う手段を備えた請求項４記載のノード。
【請求項７】
請求項４ないし６のいずれかに記載のノードにより構成されたネットワーク。
【請求項８】
汎用の情報処理装置にインストールすることにより、その情報処理装置に、請求項４ないし６のいずれかに記載のノードに相応する機能を実現させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２００７−２５８９２６（Ｐ２００７−２５８９２６Ａ）
【公開日】平成１９年１０月４日（２００７．１０．４）
【国際特許分類】
【出願番号】特願２００６−７８９９０（Ｐ２００６−７８９９０）
【出願日】平成１８年３月２２日（２００６．３．２２）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成１９年１０月４日（２００７．１０．４）
【国際特許分類】
【出願日】平成１８年３月２２日（２００６．３．２２）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]