(57)【要約】【課題】予め持つべきコスト最小経路の情報量を少なくし、経路の計算時間のばらつきを少なくする経路計算方法を提供する。【解決手段】コスト変化の原因が第１ノードの故障の場合、出力部１２ｄは、第１ノードに関する特定ネットワークのトポロジについて計算部１２ｂが計算したコスト最小経路のうち起点終点ノード間のコスト最小経路を出力する。コスト変化の原因が第２ノードに接続された所定リンクでのコスト変更である場合、出力部１２ｅは、コスト変更後の所定ネットワークについて第２ノードを経由する起点終点ノードの間のコスト最小経路を計算し、そのコスト最小経路と、第２ノードに関する特定ネットワークのトポロジについて計算部１２ｂにて計算された起点終点ノード間のコスト最小経路と、のうち、コストが小さい経路を、起点ノードと終点ノードの間のコスト最小経路として出力する。【選択図】図１
2012015837.tif 000002
【特許請求の範囲】
【請求項１】
ｎ（ｎは２以上の整数）個の所定ノードとｍ（ｍはｎよりも小さく１以上の整数）個の所定リンクとを有し前記所定リンクが前記所定ノード間を接続し前記所定リンクに優先度を示すコストが付与された所定ネットワークを表す第１情報を受け付け、その後、前記所定リンクのうちコストが変更された変更リンクと当該変更リンクの現況とを表す第２情報と、前記所定ノードのうち経路計算の対象となる起点ノードおよび終点ノードを表す第３情報と、を受け付ける受付手段と、
前記第１情報を参照して、前記所定ノードごとに、前記所定ネットワークから当該所定ノードと当該所定ノードに接続する所定リンクとを削除した特定ネットワークのトポロジを作成する作成手段と、
前記特定ネットワークのトポロジごとに、当該特定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、当該２つのノード間の経路のうち当該経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する計算手段と、
前記第２情報を解析して前記コストの変化の原因を判定する判定手段と、
前記コストの変化の原因が、前記所定ノードのいずれかである第１ノードの故障であると判定された場合、前記第１ノードについて作成された特定ネットワークのトポロジについて前記計算手段にて計算されたコスト最小経路のうち、前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路を出力する第１出力手段と、
前記コストの変化の原因が、前記所定リンクのうち前記所定ノードのいずれかである第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定された場合、前記第１情報と前記第２情報を参照して、前記コストの変更後の所定ネットワークについて、前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算し、当該コスト最小経路と、前記第２ノードについて作成された特定ネットワークのトポロジについて前記計算手段にて計算されたコスト最小経路のうち前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路と、のうち、コストが小さい経路を、前記起点ノードと前記終点ノードの間のコスト最小経路として出力する第２出力手段と、を含む経路計算装置。
【請求項２】
請求項１に記載の経路計算装置において、
前記第２出力手段は、前記コストの変更後の所定ネットワークでの前記第２ノードを起点とし前記所定ノードのうち前記第２ノード以外のノードの各々を終点とする各経路での第１コスト最小経路と、前記コストの変更後の所定ネットワークでの前記第２ノードを終点とし前記所定ノードのうち前記第２ノード以外のノードの各々を起点とする各経路での第２コスト最小経路と、を計算し、前記第１および第２コスト最小経路を参照して、前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算する、経路計算装置。
【請求項３】
請求項１または２に記載の経路計算装置において、
前記第３情報は、前記コストの変更後の所定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、当該２つのノードの一方を前記起点ノードとして表し、他方を前記終点ノードとして表すものであり、
前記第１出力手段は、前記起点ノードおよび前記終点ノードの組合せごとに、前記起点ノードおよび前記終点ノード間のコスト最小経路を出力し、
前記第２出力手段は、前記起点ノードおよび前記終点ノードの組合せごとに、前記起点ノードおよび前記終点ノード間のコスト最小経路を出力する、経路計算装置。
【請求項４】
請求項１または２に記載の経路計算装置において、
前記第３情報は、前記コストの変更後の所定ネットワーク内の前記起点ノードと前記終点ノードとの複数の組合せを表すものであり、
前記第２出力手段は、前記起点ノードおよび前記終点ノードの組合せごとに行われる、前記コストの変更後の所定ネットワークでの前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算し、当該コスト最小経路と、前記第２ノードについて作成された特定ネットワークのトポロジについて前記計算手段にて計算された前記起点ノードと前記終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、前記起点ノードと前記終点ノードの間のコスト最小経路として出力する、という一連の処理を、同時並列に実行する、経路計算装置。
【請求項５】
請求項１から４のいずれか１項に記載の経路計算装置において、
前記第２出力手段は、さらに、前記コストの変化によってコスト最小経路が変わる起点ノードと終点ノード間の経路を検索し、当該検索された経路についてのみ、前記コストの変更後の所定ネットワークでの前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算し、当該コスト最小経路と、前記第２ノードについて作成された特定ネットワークのトポロジについて前記計算手段にて計算された前記起点ノードと前記終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、前記起点ノードと前記終点ノードの間のコスト最小経路として出力する、経路計算装置。
【請求項６】
請求項１から５のいずれか１項に記載の経路計算装置において、
前記判定手段は、前記第２情報を解析し、前記第１ノードに接続された全ての所定リンクが前記変更リンクであり、かつ、当該変更リンクの現況が当該変更リンクが切断された旨を示す場合、前記コストの変化の原因が前記第１ノードの故障であると判定し、また、前記第２ノードに接続された１つ以上の所定リンクが変更リンクであり、かつ、前記第２ノードに接続された全ての所定リンクが前記変更リンクでなく、かつ、当該変更リンクの現況が当該変更リンクの変更後のコストを示す場合、前記コストの変化の原因が前記第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定する、経路計算装置。
【請求項７】
請求項１から６のいずれか１項に記載の経路計算装置と接続され、前記所定ネットワークから受け取ったデータを当該データの宛先に転送する、前記所定ノードであるデータ転送装置であって、
前記経路計算装置から経路計算結果を受け取り、当該経路計算結果に基づいて、前記データの転送先を設定する設定手段と、
前記設定された転送先に前記データを転送する転送手段と、を含むデータ転送装置。
【請求項８】
経路計算装置での経路計算方法であって、
ｎ（ｎは２以上の整数）個の所定ノードとｍ（ｍはｎよりも小さく１以上の整数）個の所定リンクとを有し前記所定リンクが前記所定ノード間を接続し前記所定リンクに優先度を示すコストが付与された所定ネットワークを表す第１情報を受け付け、その後、前記所定リンクのうちコストが変更された変更リンクと当該変更リンクの現況とを表す第２情報と、前記所定ノードのうち経路計算の対象となる起点ノードおよび終点ノードを表す第３情報と、を受け付ける受付ステップと、
前記第１情報を参照して、前記所定ノードごとに、前記所定ネットワークから当該所定ノードと当該所定ノードに接続する所定リンクとを削除した特定ネットワークのトポロジを作成する作成ステップと、
前記特定ネットワークのトポロジごとに、当該特定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、当該２つのノード間の経路のうち当該経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する計算ステップと、
前記第２情報を解析して前記コストの変化の原因を判定する判定ステップと、
前記コストの変化の原因が、前記所定ノードのいずれかである第１ノードの故障であると判定された場合、前記第１ノードについて作成された特定ネットワークのトポロジについて前記計算ステップにて計算されたコスト最小経路のうち、前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路を出力する第１出力ステップと、
前記コストの変化の原因が、前記所定リンクのうち前記所定ノードのいずれかである第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定された場合、前記第１情報と第２情報を参照して、前記コストの変更後の所定ネットワークについて、前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算し、当該コスト最小経路と、前記第２ノードについて作成された特定ネットワークのトポロジについて前記計算ステップにて計算されたコスト最小経路のうち前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路と、のうち、コストが小さい経路を、前記起点ノードと前記終点ノードの間のコスト最小経路として出力する第２出力ステップと、を含む経路計算方法。
【請求項９】
請求項１から６のいずれか１項に記載の経路計算装置と接続され、前記所定ネットワークから受け取ったデータを当該データの宛先に転送する、前記所定ノードであるデータ転送装置でのデータ転送方法であって、
前記経路計算装置から経路計算結果を受け取り、当該経路計算結果に基づいて、前記データの転送先を設定する設定ステップと、
前記設定された転送先に前記データを転送する転送ステップと、を含むデータ転送方法。
【請求項１０】
コンピュータに、
ｎ（ｎは２以上の整数）個の所定ノードとｍ（ｍはｎよりも小さく１以上の整数）個の所定リンクとを有し前記所定リンクが前記所定ノード間を接続し前記所定リンクに優先度を示すコストが付与された所定ネットワークを表す第１情報を受け付け、その後、前記所定リンクのうちコストが変更された変更リンクと当該変更リンクの現況とを表す第２情報と、前記所定ノードのうち経路計算の対象となる起点ノードおよび終点ノードを表す第３情報と、を受け付ける受付手順と、
前記第１情報を参照して、前記所定ノードごとに、前記所定ネットワークから当該所定ノードと当該所定ノードに接続する所定リンクとを削除した特定ネットワークのトポロジを作成する作成手順と、
前記特定ネットワークのトポロジごとに、当該特定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、当該２つのノード間の経路のうち当該経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する計算手順と、
前記第２情報を解析して前記コストの変化の原因を判定する判定手順と、
前記コストの変化の原因が、前記所定ノードのいずれかである第１ノードの故障であると判定された場合、前記第１ノードについて作成された特定ネットワークのトポロジについて前記計算手順にて計算されたコスト最小経路のうち、前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路を出力する第１出力手順と、
前記コストの変化の原因が、前記所定リンクのうち前記所定ノードのいずれかである第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定された場合、前記第１情報と第２情報を参照して、前記コストの変更後の所定ネットワークについて、前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算し、当該コスト最小経路と、前記第２ノードについて作成された特定ネットワークのトポロジについて前記計算手順にて計算されたコスト最小経路のうち前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路と、のうち、コストが小さい経路を、前記起点ノードと前記終点ノードの間のコスト最小経路として出力する第２出力手順と、を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノードと、ノード間を接続するリンクと、により構成されるネットワークにおいて、起点ノードから終点ノードまでたどるべき経路を計算する技術に関する。より詳細には、本発明は、ネットワーク内のリンクまたはノードの故障等によりリンクの優先度（コスト）が変化したときに、事前に計算しておいた起点終点間の経路を利用して、リンクの優先度が変化したネットワークでの起点ノードから終点ノードまでのコスト最小経路を再度計算する技術に関する。
【背景技術】
【０００２】
分岐の存在しない通路に相当するリンクと、分岐点に相当するノードと、から構成されるネットワークにおいて、新たにノードとリンクが追加され、それまで通れなかった箇所が通れるようになる場合が存在する。コンピュータネットワークにおいては、ルータやリンクの増設が前述の場合に相当する。
【０００３】
また、ネットワークにおいては、リンクに優先度（コスト）を持たせ、２ノード間の経路として、２ノード間の経路のうち経路内のリンクのコストの和が最も小さくなる経路を計算することが多々ある。通常、通したいリンクのコストは小さい値に設定される。そのようなネットワークで、経路内のリンクのコスト和が最小となる経路を計算することは重要な問題である。経路内のリンクのコスト和が最小となる経路をコスト最小経路という。
【０００４】
出発地（起点）から目的地（終点）までのコスト最小経路を常に維持する必要がある場合、ネットワークにおけるノードとリンクの敷設状況（トポロジ）やリンクのコストの変化に伴い、変化後のネットワークについて２ノード間を結ぶコスト最小経路を再計算する必要がある。
【０００５】
従来のコスト最小経路計算方法では、ネットワーク状況が変化した場合、２ノード間を結ぶコスト最小経路を、変化後のネットワークを示すネットワーク情報（トポロジの情報）のみを用いて、再計算する。
【０００６】
コスト最小経路計算方法の代表例は、非特許文献１に記載されている。なお、非特許文献１に記載された方法は、ダイクストラのアルゴリズムとして知られている。
【０００７】
リンクのコストが変化する等のネットワーク状況が変化するネットワークでの２ノード間の経路うち、ネットワーク状況の変化の前後でコスト最小経路に違いが生じない２ノード間の経路が存在することがある。このような状況を、コスト最小経路の再計算をする前に検知すると、ネットワーク状況の変化の前後でコスト最小経路に違いが生じない経路の計算を省くことが可能となる。これにより、計算時間の短縮が可能となる。
【０００８】
しかし、このような方法は、ネットワーク状況変化前のコスト最小経路を示す情報が必要となるため、変化後のネットワークを示すネットワーク情報のみを使用する従来の方法では実現が困難である。
【０００９】
ネットワーク状況変化後にすべてのコスト最短経路を再計算することにより計算時間が長くなるという問題を解決する１つめの方法が、非特許文献２に記載されている。非特許文献２に記載の方法は、あるリンクのコストに変化が生じた時に、ネットワーク状況の変化前の最短経路の情報を用いて、変化後の最短経路を計算する方法である。非特許文献２に記載の方法を用いることで、ネットワーク状況変化後にすべてのコスト最短経路を再計算することにより計算時間が長くなるという問題を解決することができる。
【００１０】
ネットワーク状況変化後にすべてのコスト最短経路を再計算することにより計算時間が長くなるという問題を解決する２つめの方法は、予め、すべての故障パターン（ノード故障とリンク故障）についてコスト最小経路を計算し、ノードやリンクが故障したときに、その故障に対応する故障パターンについてのコスト最小経路に従って経路情報を更新する方法である。この方法は、リンクやノードの故障時に経路計算を行う必要がないため、経路を復旧させるために必要な時間が短くなるという特徴を有する。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】E.W. Dijkstra: A note on two problems in connexion with graphs. In Numerische Mathematik, 1(1959), S. 269-271.
【非特許文献２】B. Xiao, et al. "Dynamic update of shortest path tree in OSPF," IEEE Parallel Architectures Algorithms and Network, pp. 18-23, May 2004.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
非特許文献２に記載の基本的なコスト最小経路の確定動作は、ダイクストラのアルゴリズムと同じである。このアルゴリズムでは、リンクのコストが変わった後のコスト最小経路を、ネットワーク状況変化前のコスト最小経路の情報を用いて計算する。非特許文献２に記載のコスト最小経路の計算方法を、図９を参照して説明する。
【００１３】
図９では、Ｂ→Ｃ、Ｄ→Ｃの経路が既に確定している、つまり、Ｂ→Ｃ、Ｄ→Ｃの経路では、ネットワーク状況変化によってコスト最小経路に変化がなかったとする。以下、この状況でＡ→Ｃのコスト最小経路を求める場合を説明する。
【００１４】
まず、ネットワーク状況変化の影響があった経路の計算を開始する。
【００１５】
この計算により、Ａ→Ｂへの経路が確定すると、Ｂ→Ｃの経路は既に確定しているため、Ａ→Ｂ→ＣをＡ→Ｃの経路（コスト最小経路）の候補とする。ここで、Ｂを通らず、よりコストが小さいＡ→Ｃの経路が存在する可能性があるため、Ａ→Ｂ→ＣをＡ→Ｃの経路の確定経路ではなく候補とする。
【００１６】
経路計算を続けていき、Ａ→Ｄの経路が確定すると、Ｄ→Ｃの経路は既に確定しているため、Ａ→Ｄ→ＣをＡ→Ｃの経路の候補とする。
【００１７】
続いて、Ａ→Ｂ→ＣとＡ→Ｄ→Ｃのコストを比較し、コストが小さい方をＡ→Ｃの経路の候補として残す。ここで、ＢまたはＤを通らず、よりコストが小さいＡ→Ｃの経路が存在する可能性があるため、コストが小さい方をＡ→Ｃの経路の確定経路ではなく候補とする。
【００１８】
同様に、他にＡ→Ｃの経路の候補が見つかるたびに、コストが小さい方をＡ→Ｃの経路の候補として残す。ネットワーク全体の経路計算が終了した時点で、残っているＡ→Ｃの経路の候補がＡ→Ｃの経路として確定する。
【００１９】
このアルゴリズムの場合、Ａ→Ｂ→Ｃ、Ａ→Ｄ→Ｃのように、Ａ→Ｃの経路の候補が何個見つかるか、経路計算を始める前にはわからないため、計算時間の予測が困難である。よって、安定した計算時間を予測することが重要な場合、使いづらいアルゴリズムとなっている。
【００２０】
また、２つめの方法については、次のような課題が存在する。想定される故障パターンについてのコスト最小経路を予め計算することで、実際に起こった故障に対応するコスト最小経路を得られるメリットは存在するが、故障するノードや故障するリンクを事前に予測することは不可能であるため、予め用意すべき故障パターンに対応するコスト最小経路が膨大になるというデメリットが存在する。
【００２１】
これは、ノード数やリンク数、ならびに、同時リンク故障数が増加するにつれて、予め用意すべき故障パターンおよびその故障パターンに対応するコスト最小経路が飛躍的に増大し、現状の計算機リソースで実現できるレベルを超えるほどになる。よって、２つめの方法を実現するために、非常に膨大なメモリと計算に必要な資源ならびに時間が必要になるという課題が存在する。
【００２２】
本発明は、予め持つべき故障パターンに対応するコスト最小経路の情報量を、全故障パターンに対応するコスト最小経路の情報量と比べて少なくし、かつ、経路の計算時間のばらつきを少なくすることを目的とする。
【課題を解決するための手段】
【００２３】
本発明の経路計算装置は、ｎ（ｎは２以上の整数）個の所定ノードとｍ（ｍはｎよりも小さく１以上の整数）個の所定リンクとを有し前記所定リンクが前記所定ノード間を接続し前記所定リンクに優先度を示すコストが付与された所定ネットワークを表す第１情報を受け付け、その後、前記所定リンクのうちコストが変更された変更リンクと当該変更リンクの現況とを表す第２情報と、前記所定ノードのうち経路計算の対象となる起点ノードおよび終点ノードを表す第３情報と、を受け付ける受付手段と、前記第１情報を参照して、前記所定ノードごとに、前記所定ネットワークから当該所定ノードと当該所定ノードに接続する所定リンクとを削除した特定ネットワークのトポロジを作成する作成手段と、前記特定ネットワークのトポロジごとに、当該特定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、当該２つのノード間の経路のうち当該経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する計算手段と、前記第２情報を解析して前記コストの変化の原因を判定する判定手段と、前記コストの変化の原因が、前記所定ノードのいずれかである第１ノードの故障であると判定された場合、前記第１ノードについて作成された特定ネットワークのトポロジについて前記計算手段にて計算されたコスト最小経路のうち、前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路を出力する第１出力手段と、前記コストの変化の原因が、前記所定リンクのうち前記所定ノードのいずれかである第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定された場合、前記第１情報と第２情報を参照して、前記コストの変更後の所定ネットワークについて、前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算し、当該コスト最小経路と、前記第２ノードについて作成された特定ネットワークのトポロジについて前記計算手段にて計算されたコスト最小経路のうち前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路と、のうち、コストが小さい経路を、前記起点ノードと前記終点ノードの間のコスト最小経路として出力する第２出力手段と、を含む。
【００２４】
本発明の経路計算方法は、経路計算装置での経路計算方法であって、ｎ（ｎは２以上の整数）個の所定ノードとｍ（ｍはｎよりも小さく１以上の整数）個の所定リンクとを有し前記所定リンクが前記所定ノード間を接続し前記所定リンクに優先度を示すコストが付与された所定ネットワークを表す第１情報を受け付け、その後、前記所定リンクのうちコストが変更された変更リンクと当該変更リンクの現況とを表す第２情報と、前記所定ノードのうち経路計算の対象となる起点ノードおよび終点ノードを表す第３情報と、を受け付ける受付ステップと、前記第１情報を参照して、前記所定ノードごとに、前記所定ネットワークから当該所定ノードと当該所定ノードに接続する所定リンクとを削除した特定ネットワークのトポロジを作成する作成ステップと、前記特定ネットワークのトポロジごとに、当該特定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、当該２つのノード間の経路のうち当該経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する計算ステップと、前記第２情報を解析して前記コストの変化の原因を判定する判定ステップと、前記コストの変化の原因が、前記所定ノードのいずれかである第１ノードの故障であると判定された場合、前記第１ノードについて作成された特定ネットワークのトポロジについて前記計算ステップにて計算されたコスト最小経路のうち、前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路を出力する第１出力ステップと、前記コストの変化の原因が、前記所定リンクのうち前記所定ノードのいずれかである第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定された場合、前記第１情報と第２情報を参照して、前記コストの変更後の所定ネットワークについて、前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算し、当該コスト最小経路と、前記第２ノードについて作成された特定ネットワークのトポロジについて前記計算ステップにて計算されたコスト最小経路のうち前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路と、のうち、コストが小さい経路を、前記起点ノードと前記終点ノードの間のコスト最小経路として出力する第２出力ステップと、を含む。
【００２５】
本発明のプログラムは、コンピュータに、ｎ（ｎは２以上の整数）個の所定ノードとｍ（ｍはｎよりも小さく１以上の整数）個の所定リンクとを有し前記所定リンクが前記所定ノード間を接続し前記所定リンクに優先度を示すコストが付与された所定ネットワークを表す第１情報を受け付け、その後、前記所定リンクのうちコストが変更された変更リンクと当該変更リンクの現況とを表す第２情報と、前記所定ノードのうち経路計算の対象となる起点ノードおよび終点ノードを表す第３情報と、を受け付ける受付手順と、前記第１情報を参照して、前記所定ノードごとに、前記所定ネットワークから当該所定ノードと当該所定ノードに接続する所定リンクとを削除した特定ネットワークのトポロジを作成する作成手順と、前記特定ネットワークのトポロジごとに、当該特定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、当該２つのノード間の経路のうち当該経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する計算手順と、前記第２情報を解析して前記コストの変化の原因を判定する判定手順と、前記コストの変化の原因が、前記所定ノードのいずれかである第１ノードの故障であると判定された場合、前記第１ノードについて作成された特定ネットワークのトポロジについて前記計算手順にて計算されたコスト最小経路のうち、前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路を出力する第１出力手順と、前記コストの変化の原因が、前記所定リンクのうち前記所定ノードのいずれかである第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定された場合、前記第１情報と第２情報を参照して、前記コストの変更後の所定ネットワークについて、前記第２ノードを経由する前記起点ノードと前記終点ノードの間のコスト最小経路を計算し、当該コスト最小経路と、前記第２ノードについて作成された特定ネットワークのトポロジについて前記計算手順にて計算されたコスト最小経路のうち前記第３情報が表す起点ノードおよび終点ノード間のコスト最小経路と、のうち、コストが小さい経路を、前記起点ノードと前記終点ノードの間のコスト最小経路として出力する第２出力手順と、を実行させる。
【発明の効果】
【００２６】
本発明によれば、コストの変化の原因が第１ノードの故障である場合、第１出力手段は、第１ノードについて作成された特定ネットワークのトポロジについて計算手段にて計算されたコスト最小経路のうち、起点ノードと終点ノード間のコスト最小経路を出力する。
【００２７】
また、コストの変化の原因が第２ノードに接続された１つ以上の所定リンクでのコスト変更である場合、第２出力手段は、コストの変更後の所定ネットワークについて、第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算し、そのコスト最小経路と、第２ノードについて作成された特定ネットワークのトポロジについて計算手段にて計算された起点ノードと終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、起点ノードと終点ノードの間のコスト最小経路として出力する。
【００２８】
このため、ノード故障を想定したときのコスト最小経路のみを予め計算することで、予め全故障パターンのコスト最小経路を持つ場合と比べて、持つべき情報量を削減しながら、単一ノード（第１ノード）故障、もしくは、端点となるノード（第２ノード）が同一である１つ以上のリンクの同時故障が生じた時の経路計算を行うことが可能になる。
【００２９】
また、コスト最小経路の再計算を行う際、既に計算済みのコスト最小経路の他に新たに計算されるコスト最小経路は、第２ノードを経由するコスト最小経路となるため、コスト最小経路の候補の最大数を予測でき、よって、コスト最小経路の計算時間の予測が容易となり、また、計算時間もほぼ一定の時間で高速に計算することが可能となる。
【図面の簡単な説明】
【００３０】
【図１】本発明の一実施形態の経路計算装置１の機能ブロック図である。
【図２】本実施形態の動作を説明するためのフローチャートである。
【図３】所定ネットワークおよび特定ネットワークのトポロジの一例を示した図である。
【図４】特定ネットワークのトポロジについて各ノード間のコスト最小経路の例を示した図である。
【図５】リンクが切断された所定ネットワークでのコスト最短経路の例を示した図である。
【図６】コスト最短経路の算出例を示した図である。
【図７】再計算が必要な経路の例を示した図である。
【図８】本発明の一実施形態のデータ転送装置２の機能ブロック図である。
【図９】非特許文献２に記載の技術を説明するための図である。
【発明を実施するための形態】
【００３１】
以下、本発明の実施形態について説明する。
【００３２】
図１は、本発明の一実施形態の経路計算装置１の機能ブロック図である。
【００３３】
経路計算装置１は、１本道に相当するリンクと、分岐点に相当するノードと、からなるネットワークを表すネットワーク情報が与えられたときに、ネットワーク内のノード間を結ぶ経路を計算する。リンクには、優先度に相当するコストが付与されている。本実施形態では、コストの値が小さいほど、優先度は高くなる。経路計算装置１は、ノード間を結ぶ経路のうち、経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する。
【００３４】
図１において、経路計算装置１は、トポロジ情報取得部１１と、経路計算部１２と、インタフェース１３と、を含む。経路計算部１２は、作成部１２ａと、計算部１２ｂと、判定部１２ｃと、出力部１２ｄおよび１２ｅと、を含む。
【００３５】
トポロジ情報取得部１１は、受付手段の一例である。
【００３６】
トポロジ情報取得部１１は、所定ネットワークを表す所定ネットワーク情報を受け付ける。所定ネットワークは、ｎ（ｎは２以上の整数）個の所定ノードと、ｍ（ｍはｎよりも小さく１以上の整数）個の所定リンクと、を有する。所定リンクは、所定ノード間を接続する。所定リンクには、優先度を示すコストが付与されている。所定ネットワーク情報は、第１情報の一例である。
【００３７】
トポロジ情報取得部１１は、所定ネットワーク情報を受け付けた後、コスト変更情報と、計算対象経路情報と、を受け付ける。
【００３８】
コスト変更情報は、第２情報の一例である。コスト変更情報は、所定リンクのうちコストが変更された変更リンクと、変更リンクの現況とを、少なくとも表す。
【００３９】
例えば、変更リンクが、削除（故障）された所定リンクである場合、変更リンクの現況は、変更リンクが削除された旨、または、変更リンクのコストが無限大「∞」である旨を表す。また、変更リンクのコストが、ある有限の値に変更された場合、変更リンクの現況は、変更後のコストの値（有限値）を表す。
【００４０】
計算対象経路情報は、第３情報の一例である。計算対象経路情報は、所定ノードのうち経路計算の対象となる起点ノードおよび終点ノードを表す。
【００４１】
本実施形態では、トポロジ情報取得部１１は、所定ネットワーク情報と、コスト変更情報と、計算対象経路情報とを、例えば、入力部（不図示）または外部装置（不図示）から取得することによって受け付ける。なお、トポロジ情報取得部１１は、例えば、外部装置（外部機能）から出力された所定ネットワーク情報、コスト変更情報、および、計算対象経路情報を、受け付けてもよい。
【００４２】
経路計算部１２は、トポロジ情報取得部１１が持っている所定ネットワーク情報、コスト変更情報、および、計算対象経路情報を利用して経路計算を行う。
【００４３】
作成部１２ａは、作成手段の一例である。
【００４４】
作成部１２ａは、所定ネットワーク情報を参照して、所定ノードごとに、所定ネットワークから所定ノードとその所定ノードに接続する所定リンクとを削除した特定ネットワークのトポロジを作成する。作成部１２ａは、所定ノードごとに作成された特定ネットワークのトポロジを計算部１２ｂに出力する。
【００４５】
計算部１２ｂは、計算手段の一例である。
【００４６】
計算部１２ｂは、特定ネットワークのトポロジごとに、特定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、２つのノード単位で、２つのノード間の経路のうち経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する。
【００４７】
例えば、特定ネットワーク内に所定ノードとしてノードａ１、ａ２およびａ３が存在する場合、所定ノードのうちの２つのノードの全ての組合せは、（ａ１、ａ２）と（ａ１、ａ３）と（ａ２、ａ３）の組合せとなる。
【００４８】
計算部１２ｂは、例えば、ダイクストラのアルゴリズム等の既存のコスト最小経路を計算するアルゴリズムを使用して、全ての組合せについてコスト最小経路を計算する。計算部１２ｂは、コスト最小経路の計算結果を保持する。
【００４９】
判定部１２ｃは、判定手段の一例である。
【００５０】
判定部１２ｃは、コスト変更情報を解析して、変更リンクでのコストの変化の原因を判定する。
【００５１】
本実施形態では、判定部１２ｃは、所定ノードのうちのある所定ノード（以下「第１ノード」と称する）に接続していた所定リンクの情報が全て削除された場合、または、第１ノードに接続する所定リンクのコストが無限大「∞」に変更された場合、コストの変化の原因が、第１ノードの故障であると判定する。
【００５２】
例えば、判定部１２ｃは、第１ノードに接続していた全ての所定リンクが変更リンクとしてコスト変更情報に表され、かつ、コスト変更情報に表された変更リンクの現況が、変更リンクが削除された旨、または、変更リンクのコストが無限大「∞」である旨を表す場合、コストの変化の原因が、第１ノードの故障であると判定する。
【００５３】
また、判定部１２ｃは、所定ノードのいずれかである第２ノードに接続された１つ以上の所定リンクが変更リンクとしてコスト変更情報に表され、かつ、第２ノードに接続された全ての所定リンクが変更リンクでなく、かつ、変更リンクの現況がその変更リンクの変更後のコストを示す場合、コストの変化の原因が、第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定する。
【００５４】
判定の実現手法としては、プログラムにより、コスト変更情報を解析して判定する方法などが例として存在する。
【００５５】
判定部１２ｃは、判定結果を出力部１２ｄおよび１２ｅに出力する。
【００５６】
出力部１２ｄは、第１出力手段の一例である。
【００５７】
出力部１２ｄは、コストの変化の原因が第１ノードの故障であると判定された場合、トポロジ情報取得部１１から計算対象経路情報を取得し、第１ノードについて作成された特定ネットワークのトポロジについて計算部１２ｂにて計算されたコスト最小経路のうち、計算対象経路情報が表す起点ノードおよび終点ノード間のコスト最小経路を出力する。
【００５８】
出力部１２ｅは、第２出力手段の一例である。
【００５９】
出力部１２ｅは、コストの変化の原因が第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定された場合、トポロジ情報取得部１１から、所定ネットワーク情報と、コスト変更情報と、計算対象経路情報と、を取得する。
【００６０】
出力部１２ｅは、所定ネットワーク情報とコスト変更情報と計算対象経路情報とを取得すると、所定ネットワーク情報とコスト変更情報を参照してコスト変化後の所定ネットワークを特定し、コスト変化後の所定ネットワークについて、第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算する。
【００６１】
出力部１２ｅは、第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算すると、そのコスト最小経路と、第２ノードについて作成部１２ａにて作成された特定ネットワークのトポロジについて計算部１２ｂにて計算された起点ノードと終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、起点ノードと終点ノードの間のコスト最小経路として出力する。
【００６２】
例えば、出力部１２ｅは、コスト変化後の所定ネットワークでの第２ノードを起点とし所定ノードのうち第２ノード以外のノードの各々を終点とする各経路での第１コスト最小経路と、コスト変化後の所定ネットワークでの第２ノードを終点とし所定ノードのうち第２ノード以外のノードの各々を起点とする各経路での第２コスト最小経路と、を計算し、第１および第２コスト最小経路を参照して、第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算する。
【００６３】
なお、計算対象経路情報は、コスト変化後の所定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、２つのノードの一方を起点ノードとして表し、他方を終点ノードとして表すものでもよい。この場合、出力部１２ｄは、起点ノードおよび終点ノードの組合せごとに、起点ノードおよび終点ノード間のコスト最小経路を出力し、出力部１２ｅは、起点ノードおよび終点ノードの組合せごとに、起点ノードおよび終点ノード間のコスト最小経路を出力する。
【００６４】
また、計算対象経路情報は、コスト変化後の所定ネットワーク内の起点ノードと終点ノードとの複数の組合せを表すものでもよい。この場合、出力部１２ｅは、起点ノードおよび終点ノードの組合せごとに行われる、第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算し、そのコスト最小経路と、第２ノードについて作成された特定ネットワークのトポロジについて計算部１２ｅにて計算された起点ノードと終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、起点ノードと終点ノードの間のコスト最小経路として出力する、という一連の処理を、同時並列に実行してもよい。
【００６５】
また、出力部１２ｅは、さらに、コストの変化によってコスト最小経路が変わる起点ノードと終点ノード間の経路を検索し、検索された経路についてのみ、第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算し、そのコスト最小経路と、第２ノードについて作成された特定ネットワークのトポロジについて計算部１２ｂにて計算された起点ノードと終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、起点ノードと終点ノードの間のコスト最小経路として出力してもよい。
【００６６】
ここで、経路計算装置１が有する処理機能を説明する。
【００６７】
経路計算装置１は、ノード間を結ぶリンクの接続状況であるトポロジと、リンクの優先度を示すコストと、にて構成されるネットワークを示すネットワーク情報（所定ネットワーク情報）が与えられ、かつ、ネットワークでのコストの値が変化したときに、コスト変化後のネットワークのトポロジにおけるコスト最小経路を計算する。
【００６８】
経路計算装置１は、処理Ｓ１〜Ｓ８を実行可能である。
【００６９】
処理Ｓ１では、作成部１２ａと計算部１２ｂは、トポロジ内の指定された１ノードと、そのノードに接続するリンクとを、元のトポロジ（所定ネットワークのトポロジ）から削除したトポロジ（特定ネットワークのトポロジ）を作成し、そのトポロジにおける全起点終点ノードペア間のコスト最小経路を計算する作業を、元のトポロジにおいて全ノードを個別に指定したときのそれぞれのトポロジ（特定ネットワークのトポロジ）パターンについて行う。
【００７０】
処理Ｓ２では、計算部１２ｂが、処理Ｓ１で計算された結果を記録し、出力部１２ｄおよび１２ｅは、経路の起点、終点、ならびに削除対象ノードが指定されると、処理Ｓ１での計算結果の中から、削除対象ノードが削除された特定ネットワークのトポロジにおける、指定された起点終点間のコスト最小経路を出力する。
【００７１】
処理Ｓ３では、判定部１２ｃは、リンクコストが変化したとき、その変化が、ネットワークからのノードの削除、もしくは、端点が同一の１本以上のリンクのコストが変化したことのいずれかに起因したことかを判断する。
【００７２】
処理Ｓ４では、出力部１２ｅは、トポロジと特定の点（ノード）が与えられると、与えられたトポロジにおける特定の点（ノード）を起点とする全コスト最小経路と、与えられたトポロジにおける特定の点（ノード）を終点とする全コスト最小経路と、を計算する。
【００７３】
処理Ｓ５では、出力部１２ｅは、処理Ｓ４で計算された経路のうち、指定された起点終点間のコスト最小経路を出力する。
【００７４】
処理Ｓ６では、トポロジ情報取得部１１およびインタフェース１３は、コスト最小経路の計算に必要なトポロジやコスト（所定ネットワーク情報、コスト変更情報）、起点終点の情報（計算対象経路情報）の入力、ならびに計算結果の出力を行う。
【００７５】
経路計算装置１は、処理Ｓ６に基づき入力されたリンクコスト変更前のトポロジとコストを表す所定ネットワーク情報をもとに、処理Ｓ１をリンクコストの変更前に実行する。
【００７６】
経路計算装置１は、処理Ｓ６により入力された変更後のリンクコストを表すコスト変更情報に基づき処理Ｓ３を実行してコストの変更原因を判定し、その結果、コストの変更原因が第１ノードの削除（故障）によるものであれば、処理Ｓ２に対し、計算したい経路の起点および終点と、削除対象ノードとして今回故障と判定された第１ノードと、を入力として与えた時の出力結果を、計算したい経路の計算結果として出力する。
【００７７】
経路計算装置１は、コストの変更原因が、端点（第２ノード）が同一の１本以上のリンクのコストが変化した場合であれば、所定ネットワーク情報とコスト変更情報とによって特定されるコスト変更後の所定ネットワークのトポロジと、特定の点（ノード）となる第２ノードと、を入力として処理Ｓ４を実行する。
【００７８】
経路計算装置１は、指定された起点終点ノードペア間のコスト最小経路として、処理Ｓ２に対し、起点、終点、ならびに、第２ノードを削除対象のノードとして入力した結果となる経路１と、処理Ｓ５を実行して得られる起点と第２ノード間のコスト最小経路および第２ノードと終点間のコスト最小経路の両者を合わせた経路２とを、比較し、コストの小さい方を、出力結果とする。
【００７９】
また、処理Ｓ７では、出力部１２ｅは、並列計算可能なプロセスを同時並列に計算する。
【００８０】
経路計算装置１は、端点（第２ノード）が同一の１本以上のリンクのコストが変化した場合、指定された複数の起点終点間のコスト最小経路を処理Ｓ４で計算した後の計算手順を、処理Ｓ７を用いて同時並列に計算を行う。
【００８１】
また、処理Ｓ８では、出力部１２ｅは、処理Ｓ３にてリンクコストの変更が判明したときに、リンクコストの変化によりコスト最小経路が変わる起点終点間の経路のみを検索する。出力部１２ｅは、処理Ｓ８で検索された経路についてのみ、処理Ｓ４実行後の計算手順を実行する。
【００８２】
経路計算装置１は、コンピュータにて実現されてもよい。この場合、コンピュータは、コンピュータにて読み取り可能なＣＤ−ＲＯＭ（Compact Disk Read Only Memory）のような記録媒体に記録されたプログラムを読込み実行することによって、トポロジ情報取得部１１および経路計算部１２として機能する。記録媒体は、ＣＤ−ＲＯＭに限らず適宜変更可能である。なお、トポロジ情報取得部１１および経路計算部１２は、ロジック回路にて構成されてもよい。
【００８３】
図２は、本実施形態の動作を説明するためのフローチャートである。以下、図２を参照して、本実施形態の動作を説明する。
【００８４】
作成部１２ａは、トポロジ情報取得部１１が所定ネットワーク情報を受け付けると、所定ネットワーク情報を参照して、ノード（所定ノード）とリンク（所定リンク）との接続状況を示す所定ネットワークのトポロジを調査する。
【００８５】
続いて、作成部１２ａは、所定ネットワークのトポロジ内のノードを個別に指定する。作成部１２ａは、ノードを個別に指定するごとに、所定ネットワーク情報が示す所定ネットワークから、その指定されたノードと、その指定されたノードに接続するリンクと、を削除したネットワーク（特定ネットワーク）のトポロジを作成する。
【００８６】
特定ネットワークのトポロジを作成する作業は、所定ネットワーク情報が表す所定ネットワークを構成するすべてのノードを個別に削除する形で実行される。この作業により、所定ネットワークから単一ノードが削除された特定ネットワークのトポロジとして、作成しうる全トポロジパターンが作成される。
【００８７】
次に、計算部１２ｂは、特定ネットワークのトポロジのそれぞれについて、起点終点ノード間を結ぶコスト最小経路を計算する。つまり、計算部１２ｂは、特定ネットワークのトポロジごとに、特定ネットワーク内のノードのうちの２つのノードの全ての組合せについて、２つのノード間の経路のうち経路内のリンクに付与されたコストの合計が最小となるコスト最小経路を計算する（ステップＡ１）。
【００８８】
経路計算装置１は、特定ネットワークのトポロジを作成し、各特定ネットワーク内の２ノード間のコスト最小経路を計算する処理を、所定ネットワーク情報の受け付けに応じて行うため、この処理は、将来起こるノード故障やリンクのコスト変更の前に行われることになる。
【００８９】
その後、ノード故障やリンクのコスト変更が発生すると、コスト変更情報がトポロジ情報取得部１１に入力される（ステップＡ２）。
【００９０】
判定部１２ｃは、トポロジ情報取得部１１からコスト変更情報を受け付けると、処理Ｓ３を実行して、コスト変更が、ノード故障（第１ノードの故障）によるものか、もしくは、端点となるノード（第２ノード）が同一である１つ以上のリンクのコストが変更したものかを判定する（ステップＡ３）。
【００９１】
コスト変更がノード故障によるものであれば、出力部１２ｄは、処理Ｓ２を実行して、所定ネットワークから第１ノードを抜いた特定ネットワークのトポロジにおける指定した起点終点間のコスト最小経路を得る（ステップＡ４）。計算対象経路情報が全経路の計算を意味する場合は、出力部１２ｄは、指定する起点終点として、所定ネットワークから第１ノードを抜いた特定ネットワーク内のすべてのノードペアを指定する。
【００９２】
コスト変更がリンクのコスト変更によるものであれば、判定部１２ｃは、コストが変更したリンク数が１であるか、２以上であるかをチェックする。コストが変更したリンク数が２以上の場合、判定部１２ｃは、コストが変更したリンクの端点のうちの１つがすべて共通していることをチェックする。そして、判定部１２ｃは、共通している端点ノード（第２ノード）を記録する。コスト変更が起こったリンク数が１の場合、判定部１２ｃは、予め設定されたポリシーに従い、コスト変更が起こったリンクの端点ノードのうちの１つ（第２ノード）を選び、それを記録する。
【００９３】
出力部１２ｅは、計算対象経路の起点と終点と、記録した端点ノード（第２ノード）を削除対象ノードとして、処理Ｓ２に入力したときに得られる経路を記録する。この経路は、図２における候補経路１とする。
【００９４】
次いで、出力部１２ｅは、所定ネットワーク情報とコスト変更情報にて特定される、コスト変更後の所定ネットワークのトポロジと、記録したノード（第２ノード）と、を入力として処理Ｓ４を用いて、コストが変化した後における、記録したノード（第２ノード）を起点とするコスト最小経路と、記録したノード（第２ノード）を終点とするコスト最小経路と、を計算する（ステップＡ５）。
【００９５】
その後、出力部１２ｅは、計算対象経路の起点と終点を入力することで、起点と記録したノード（第２ノード）とを結ぶコスト最小経路と、記録したノード（第２ノード）と終点とを結ぶコスト最小経路とを、処理Ｓ５を実行することによって出力する。そして、出力部１２ｅは、起点と記録したノード（第２ノード）とを結ぶコスト最小経路と、記録したノード（第２ノード）と終点とを結ぶコスト最小経路と、の両者の出力結果を合わせた経路を記録する。この経路は、図２における候補経路２とする。出力部１２ｅは、候補経路１、２を比較し、コストの小さいほうを計算対象経路として出力する（ステップＡ６）。
【００９６】
なお、複数の起点終点ノードペア間のコスト最小経路を計算する場合、処理Ｓ２、Ｓ４、Ｓ５による経路の出力処理と、コストの比較処理を、並列に行うことができる。そのような場合、出力部１２ｅは、処理Ｓ７を用いて、それぞれのノードペアのコスト最小経路に対する候補経路の比較処理を並列に行う。
【００９７】
次に、一例を挙げて、経路計算装置１の動作を説明する。
【００９８】
図３（ａ）は、コスト変更が起こる前の所定ネットワークのトポロジを示した図である。図３（ａ）に示した所定ネットワークのトポロジは、ノード（所定ノード）ａ〜ｆと、リンク（所定リンク）ａ−ｂと、リンク（所定リンク）ａ−ｄと、リンク（所定リンク）ｂ−ｃと、リンク（所定リンク）ｂ−ｄと、リンク（所定リンク）ｃ−ｅと、リンク（所定リンク）ｃ−ｆと、リンク（所定リンク）ｄ−ｅと、リンク（所定リンク）ｅ−ｆと、から構成される。リンクａ−ｂのコストは「１」である。リンクａ−ｄのコストは「１」である。リンクｂ−ｃのコストは「１」である。リンクｂ−ｄのコストは「１」である。リンクｃ−ｅのコストは「１」である。リンクｃ−ｆのコストは「１」である。リンクｄ−ｅのコストは「１」である。リンクｅ−ｆのコストは「３」である。
【００９９】
図３（ｂ）〜（ｇ）は、図３（ａ）に示した所定ネットワークのトポロジからノードを１つずつ削除した特定ネットワークのトポロジを示した図である。図３（ａ）に示したトポロジは６つのノードを有するので、図３（ａ）に示したトポロジからノードを１つ削除したトロポジの種類は、図３（ｂ）〜（ｇ）にそれぞれ示した６種類となる。図３（ｂ）〜（ｇ）に示した特定ネットワークのトポロジは、作成部１２ａにて作成される。
【０１００】
図４は、図３（ａ）に示したトポロジから１つのノードが削除されたトポロジ（特定ネットワークのトポロジ）におけるコスト最小経路の例を示した図である。
【０１０１】
なお、図４（Ａ）は、図３（ａ）に示したトポロジからノードｃが削除されたトポロジを示した図である。図４（ａ）〜（ｅ）は、ノードｃが削除されたトポロジにおいて、ノードｃ以外のノードを起点とするコスト最小経路を示した図である。図４（ａ）〜（ｅ）に示したようなコスト最小経路は、図３（ａ）に示したトポロジから１つのノードが削除された各トポロジ（図３（ｂ）〜（ｇ）参照）について、計算部１２ｂによって、それぞれ計算される。
【０１０２】
計算部１２ｂは、コスト最小経路の計算方法として、ダイクストラのアルゴリズムなどの既存のアルゴリズムを用いる。これらのコスト最小経路の計算は、ノード故障やリンクコストの変更が生じる前に行われる。
【０１０３】
本実施形態では、ノード故障が起きたときと、リンクコストが変化したときを、コスト最小経路の再計算のタイミングとして扱う。
【０１０４】
まず、ノード故障が起きた時の動作について説明する。
【０１０５】
本実施形態では、ノードｃが故障したときに、残ったノードペア間のコスト最小経路を再計算する場合について述べる。このとき、出力部１２ｄは、ノードｃを削除したトポロジに対して計算部１２ｂが計算した、ノードｃ以外のノードペア間を結ぶコスト最小経路（図４（ａ）〜（ｅ））を計算結果として出力する。よって、図４（ａ）〜（ｅ）に記載されたコスト最小経路が計算結果となる。
【０１０６】
次に、リンクのコストが変化したときにおける動作を説明する。
【０１０７】
図５（ａ）は、図３（ａ）に示したトポロジにおいて、リンクｂ−ｃが切断された場合のトポロジを示した図である。
【０１０８】
なお、リンクの切断は、コスト変更情報において、変更リンクの現況として、リンクのコストが無限大「∞」になった状態や、リンクの情報が消去された状態と捉える事が可能である。この時におけるトポロジ内の各ノードペア間のコスト最小経路の計算方法を以下に述べる。
【０１０９】
まず、判定部１２ｃは、切断されたリンクの端点のうち、予め決められたポリシーに従って、端点（第２ノード）を選ぶ。今回はランダムで選ばれた結果、ノードｃが前述の端点（第２ノード）に選ばれたとする。
【０１１０】
次に、出力部１２ｅは、コストが変化したトポロジにおける、選ばれた端点（第２ノード）を起点とするコスト最小経路群と、選ばれた端点（第２ノード）を終点とするコスト最小経路群とを、処理Ｓ４を実行して計算する。
【０１１１】
処理Ｓ４についても、ダイクストラのアルゴリズムなどの既存のコスト最小経路計算方法を利用することで実現が可能である。
【０１１２】
図５（ｂ）は、ノードｃを起点とするコスト最小経路群を示した図である。図５（ｃ）は、ノードｃを終点とするコスト最小経路群を示した図である。
【０１１３】
これらのコスト最小経路は、処理Ｓ５によりそれぞれ出力される。例として、処理Ｓ５でノードｃからノードａまでの経路を出力させると、経路ｃ→ｅ→ｄ→ａが出力される。
【０１１４】
ノードｃを起点とするコスト最小経路とノードｃを終点とするコスト最小経路との計算が終了すると、出力部１２ｅは、これらの経路と、事前に計算したノードｃを削除したトポロジにおける指定したノードペア間の経路と、を用いて、経路計算を行う。
【０１１５】
図６（ａ）〜（ｃ）は、ノードａとノードｆの間のコスト最小経路の再計算を説明するための図である。
【０１１６】
まず、出力部１２ｅは、処理Ｓ１で得られた、ノードｃを削除したトポロジにおいて計算されたノードａとノードｆとの間のコスト最小経路を、候補経路１とする（図６（ａ）参照）。
【０１１７】
そして、出力部１２ｅは、処理Ｓ４およびＳ５で得られた、ノードａからノードｃまでの経路と、処理Ｓ４およびＳ５で得られた、ノードｃからノードｆまでの経路と、を合わせた経路を、候補経路２とする（図６（ｂ）参照）。
【０１１８】
候補経路１のコストは「５」で、候補経路２のコストは「４」である。出力部１２ｅは、  これらの候補経路のうち、コストが小さい方の経路を計算結果として選択する。この場合、候補経路２のコストが小さいので、出力部１２ｅは、候補経路２を計算結果として選択する（図６（ｃ）参照）。
【０１１９】
図６（ｄ）〜（ｆ）は、ノードａとノードｂの間のコスト最小経路の再計算を説明するための図である。
【０１２０】
出力部１２ｅは、上記と同様の方法でノードａとノードｂとの間のコスト最小経路を計算する。
【０１２１】
この場合も、出力部１２ｅは、候補経路１として、ノードｃを削除したトポロジにおけるノードａとノードｂとの間のコスト最小経路を選び（図６（ｄ）参照）、候補経路２として、ノードａとノードｃとの間のコスト最小経路とノードｃとノードｂとの間のコスト最小経路とを合わせた経路（図６（ｅ）参照）を選択する。
【０１２２】
この場合、候補経路１のほうがコストが小さいので、出力部１２ｅは、候補経路１をコスト最小経路（図６（ｆ）参照）として出力する。他のノードペア間のコスト最小経路を計算する場合も同様の方法で計算することが可能である。
【０１２３】
以上がコスト最小経路を計算する方法である。
【０１２４】
なお、コスト最小経路の再計算であるが、前述のように再計算した結果が、所定ネットワークにおけるコストが変化する前の経路と全く同じ場合が存在する。
【０１２５】
全ノードペア間のコスト最小経路を計算する必要がある場合、そのような経路があらかじめ分かっている場合、そのような経路の再計算処理を行わず、コスト変化前の経路を計算結果として採用することで計算時間の短縮を実現することが可能となる。そのような場合の例として、図７に記載した状況について説明する。
【０１２６】
図７（ａ）は、コスト変化前の所定ネットワークのトポロジを示した図である。この場合におけるノードａ起点のコスト最小経路は、図７（ｂ）に記載される経路である。
【０１２７】
このとき、ノードｂとノードｃとの間のリンクが切断したとする（図７（ｃ）参照）。
【０１２８】
このとき、ノードａ起点のコスト最小経路のうち、ノードｂとノードｃとの間のリンクを使用する経路のみ再計算をする必要がある。
【０１２９】
このため、出力部１２ｅは、コストの変化によってコスト最小経路が変わる起点ノードと終点ノード間の経路（ノードｂとノードｃとの間のリンクを使用する経路）を検索し、前述のコスト最小経路計算処理を、ノードａとノードｃとの間のコスト最小経路の計算と、ノードａとノードｆとの間のコスト最小経路の計算に対して行い、残りのノードまでのコスト最小経路は、再計算せず、リンク切断前のコスト最小経路を再利用することで、計算時間を短縮することができる。
【０１３０】
出力部１２ｅは、その他のノードペア間のコスト最小経路についても同様にリンクｂ−ｃを経由するコスト最小経路のみ再計算を行うことによって、全ノードペア間のコスト最小経路の計算時間を短縮することが可能となる。
【０１３１】
本実施形態によれば、コストの変化の原因が第１ノードの故障である場合、出力部１２ｄは、第１ノードについて作成された特定ネットワークのトポロジについて計算部１２ｂにて計算されたコスト最小経路のうち、起点ノードおよび終点ノード間のコスト最小経路を出力する。
【０１３２】
また、コストの変化の原因が第２ノードに接続された１つ以上の所定リンクでのコスト変更である場合、出力部１２ｅは、コストの変更後の所定ネットワークについて、第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算し、そのコスト最小経路と、第２ノードについて作成された特定ネットワークのトポロジについて計算部１２ｂにて計算された起点ノードと終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、起点ノードと終点ノードの間のコスト最小経路として出力する。
【０１３３】
本実施形態では、ノード故障を想定したときのコスト最小経路のみを予め計算することで、予め全故障パターンのコスト最小経路を持つ場合と比べて、持つべき情報量を削減しながら、単一ノード（第１ノード）故障、もしくは、端点となるノード（第２ノード）が同一である１つ以上のリンクの同時故障が生じた時の経路計算を行うことが可能になる。
【０１３４】
また、コスト最小経路の再計算を行う際、既に計算済みのコスト最小経路の他に新たに計算されるコスト最小経路は、第２ノードを経由するコスト最小経路のみとなるため、コスト最小経路の候補の最大数を予測でき、よって、コスト最小経路の計算時間の予測が容易となり、また、計算時間もほぼ一定の時間で高速に計算することが可能となる。
【０１３５】
また、本実施形態では、出力部１２ｅは、コストの変更後の所定ネットワークでの第２ノードを起点とし所定ノードのうち第２ノード以外のノードの各々を終点とする各経路での第１コスト最小経路と、コストの変更後の所定ネットワークでの第２ノードを終点とし所定ノードのうち第２ノード以外のノードの各々を起点とする各経路での第２コスト最小経路と、を計算し、第１および第２コスト最小経路を参照して、第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算する。
【０１３６】
この場合、コストの変更後の所定ネットワークでの２ノードの全ての組合せでのコスト最小経路を算出する際、第１および第２コスト最小経路の算出を一度にまとめて行うことが可能になる。
【０１３７】
また、本実施形態では、計算対象経路情報が、コストの変更後の所定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、２つのノードの一方を起点ノードとして表し、他方を終点ノードとして表すものである場合、出力部１２ｄは、起点ノードおよび終点ノードの組合せごとに、起点ノードおよび終点ノード間のコスト最小経路を出力し、出力部１２ｅは、起点ノードおよび終点ノードの組合せごとに、起点ノードおよび終点ノード間のコスト最小経路を出力する。
【０１３８】
この場合、コストの変更後の所定ネットワーク内の所定ノードのうちの２つのノードの全ての組合せについて、コスト最小経路を算出することが可能になる。
【０１３９】
また、本実施形態では、計算対象経路情報が、コストの変更後の所定ネットワーク内の起点ノードと終点ノードとの複数の組合せを表すものである場合、出力部１２ｅは、起点ノードおよび終点ノードの組合せごとに行われる、コストの変更後の所定ネットワークでの第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算し、そのコスト最小経路と、第２ノードについての特定ネットワークのトポロジについて計算部１２ｂにて計算された起点ノードと終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、起点ノードと終点ノードの間のコスト最小経路として出力する、という一連の処理を、同時並列に実行する。
【０１４０】
この場合、さらなる計算時間の高速化を実現することが可能になる。
【０１４１】
また、本実施形態では、出力部１２ｅは、さらに、コストの変化によってコスト最小経路が変わる起点ノードと終点ノード間の経路を検索し、検索された経路についてのみ、コストの変更後の所定ネットワークでの第２ノードを経由する起点ノードと終点ノードの間のコスト最小経路を計算し、そのコスト最小経路と、第２ノードについての特定ネットワークのトポロジについて計算部１２ｂにて計算された起点ノードと終点ノードの間のコスト最小経路と、のうち、コストが小さい経路を、起点ノードと終点ノードの間のコスト最小経路として出力する。
【０１４２】
この場合、再計算の結果、再計算前の経路と同じ結果が計算されることが分かっている経路については、再計算前の経路を再利用することが可能になり、再計算すべき経路数が削減され、さらなる計算時間の短縮が可能となる。
【０１４３】
また、本実施形態では、判定部１２ｃは、コスト変更情報を解析し、第１ノードに接続された全ての所定リンクが変更リンクであり、かつ、その変更リンクの現況がその変更リンクが切断された旨を示す場合、コストの変化の原因が第１ノードの故障であると判定し、第２ノードに接続された１つ以上の所定リンクが変更リンクであり、かつ、第２ノードに接続された全ての所定リンクが変更リンクでなく、かつ、その変更リンクの現況がその変更リンクの変更後のコストを示す場合、コストの変化の原因が第２ノードに接続された１つ以上の所定リンクでのコスト変更であると判定する。
【０１４４】
この場合、コストの変化の原因を高い精度で判定することが可能になる。
【０１４５】
図８は、図１に示した経路計算装置１と通信するデータ転送装置２の機能ブロック図である。なお、図８において、図１に示したものと同一機能を有するものには同一符号を付してある。
【０１４６】
データ転送装置２は、例えば、新規追加ネットワーク内の追加ノードまたは既存ネットワーク内の所定ノードであり、図１に示した経路計算装置１から経路計算結果、もしくは、経路計算結果を加工した、データの転送先を表すデータを受け取り、経路計算装置１からの経路計算結果またはデータに従って、新規追加ネットワークまたは既存ネットワークから受け取ったデータを、適切な出力先に転送する。
【０１４７】
データ転送装置２は、経路情報制御部２１と、データ転送部２２と、インタフェース２３および２４と、を含む。
【０１４８】
経路情報制御部２１は、設定手段の一例である。
【０１４９】
経路情報制御部２１は、経路計算装置１内の経路計算部１２により出力された経路情報（経路計算結果）を受け取り、経路情報に基づいて、データの転送先を設定する。本実施形態では、経路情報制御部２１は、経路情報を、データの宛先に対応する次の転送先を示す転送先情報に変換する。経路情報制御部２１は、データ転送部２２が転送先情報を参照できるように、転送先情報を管理する。
【０１５０】
データ転送部２２は、転送手段の一例である。
【０１５１】
データ転送部２２は、経路情報制御部２１が設定した次のデータの転送先情報から、入力データの宛先に対応する次のデータの転送先を検索し、検索結果へとデータを転送する。
【０１５２】
インタフェース２３および２４は、外部の機能部ならびに外部装置とデータの入出力を行う。
【０１５３】
データ転送装置２は、コンピュータにて実現されてもよい。この場合、コンピュータは、コンピュータにて読み取り可能なＣＤ−ＲＯＭのような記録媒体に記録されたプログラムを読込み実行することによって、経路情報制御部２１およびデータ転送部２２として機能する。記録媒体は、ＣＤ−ＲＯＭに限らず適宜変更可能である。なお、経路情報制御部２１およびデータ転送部２２は、ロジック回路にて構成されてもよい。
【０１５４】
なお、経路計算装置１内の経路計算部１２は、データ転送装置２に含まれてもよいし、ネットワークやコネクタなどを介してデータ転送装置２とつながる外部装置に存在してもよい。
【０１５５】
本実施形態では、データ転送装置２は、経路計算装置１にて計算されたコスト最小経路を用いて、データの転送先を設定する。経路計算装置１でのコスト最小経路の計算時間が短いため、データ転送装置２は、的確な転送先を早期に設定することが可能になる。
【０１５６】
以上説明した実施形態において、図示した構成は単なる一例であって、本発明はその構成に限定されるものではない。
【符号の説明】
【０１５７】
１      経路計算装置
１１    トポロジ情報取得部
１２    経路計算部
１２ａ  作成部
１２ｂ  計算部
１２ｃ  判定部
１２ｄ  出力部
１２ｅ  出力部
１３    インタフェース
２      データ転送装置
２１    経路情報制御部
２２    データ転送部
２３〜２４  インタフェース
【図１】
2012015837.tif 000003
【図２】
2012015837.tif 000004
【図３】
2012015837.tif 000005
【図４】
2012015837.tif 000006
【図５】
2012015837.tif 000007
【図６】
2012015837.tif 000008
【図７】
2012015837.tif 000009
【図８】
2012015837.tif 000010
【図９】
2012015837.tif 000011