(57)【要約】【課題】通信ネットワークにおける最短経路を短時間で決定する。【解決手段】始点ノードに隣接するノードを識別するノード情報と当該ノードまでのコスト値とが付与された経路情報を生成してデータ構造を利用して記憶し、当該経路情報に付与されたノード情報及びコスト値とデータ構造における位置を示す位置情報とを対応付けてテーブルに記憶させる。生成された経路情報に付与されたノード情報と同じノード情報に対応するコスト値がテーブルに記憶されている場合、コスト値が小さな経路情報だけを記憶し、それに応じてテーブルのコスト値を変更する。そして、データ構造上の位置の入れ替えを行った結果に基づきテーブルの位置情報を更新し、最上位の位置情報に対応するノード情報が付与された経路情報を選択して削除する。選択された経路情報が示す通信経路を最短経路とし、当該通信経路の最後のノードに隣接するノードまでの通信経路を示す経路情報を生成する。【選択図】図１
2012054756.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードで構成される通信ネットワークにおける始点ノードから、前記複数のノードのうち前記始点ノード以外のそれぞれのノードまでの最短経路を決定する経路決定装置であって、
記憶部と、
前記複数のノードのそれぞれを識別する複数のノード情報のうち、前記始点ノードに隣接するノードを識別するノード情報と、前記始点ノードから当該ノードまでの間のコスト値とが付与され、前記始点ノードから当該ノードまでの通信経路を示す情報を経路情報として生成する経路決定部と、
前記生成された経路情報をデータ構造を利用して前記記憶部に記憶させるとともに、当該経路情報に付与されたノード情報及びコスト値と、当該経路情報の前記データ構造における位置を示す位置情報とを対応付けてテーブルに記憶させ、より小さなコスト値を付与された経路情報が前記データ構造においてより上位の位置になるように、前記記憶された経路情報の前記データ構造上の位置の入れ替えを行い、該入れ替えの結果に基づいて前記テーブルの位置情報を更新し、前記記憶された経路情報のうち前記テーブルにおいて最上位を示す位置情報に対応するノード情報が付与された経路情報を選択した後、該選択した経路情報を削除する制御部と、を有し、
前記経路決定部は、前記選択された経路情報が示す通信経路を、前記始点ノードから当該経路情報が示す通信経路における最後のノードまでの最短経路として決定し、当該通信経路における最後のノードに隣接するノードを識別するノード情報と、前記始点ノードから当該ノードまでの間のコスト値とが付与され、前記始点ノードから当該ノードまでの通信経路を示す情報を前記経路情報として生成し、
前記制御部は、前記生成された経路情報に付与されたノード情報と同じノード情報に対応するコスト値が前記テーブルに記憶されている場合、当該生成された経路情報に付与されたコスト値が、当該記憶されたコスト値よりも小さければ、前記記憶部に記憶された経路情報のうち当該ノード情報が付与された経路情報を、当該生成された経路情報で置換するとともに、当該記憶されたコスト値を当該生成された経路情報に付与されたコスト値に変更する経路決定装置。
【請求項２】
複数のノードで構成される通信ネットワークにおける始点ノードから、前記複数のノードのうち前記始点ノード以外のそれぞれのノードまでの最短経路を決定する経路決定装置における経路決定方法であって、
前記複数のノードのそれぞれを識別する複数のノード情報のうち、前記始点ノードに隣接するノードを識別するノード情報と、前記始点ノードから当該ノードまでの間のコスト値とが付与され、前記始点ノードから当該ノードまでの通信経路を示す情報を経路情報として生成する処理と、
前記生成された経路情報をデータ構造を利用して記憶するとともに、当該経路情報に付与されたノード情報及びコスト値と、当該経路情報の前記データ構造における位置を示す位置情報とを対応付けてテーブルに記憶させる記憶処理と、
より小さなコスト値を付与された経路情報が前記データ構造においてより上位の位置になるように、前記記憶された経路情報の前記データ構造上の位置の入れ替えを行い、該入れ替えの結果に基づいて前記テーブルの位置情報を更新する処理と、
前記記憶された経路情報のうち前記テーブルにおいて最上位を示す位置情報に対応するノード情報が付与された経路情報を選択した後、該選択した経路情報を削除する処理と、
前記選択された経路情報が示す通信経路を、前記始点ノードから当該経路情報が示す通信経路における最後のノードまでの最短経路として決定し、当該通信経路における最後のノードに隣接するノードを識別するノード情報と、前記始点ノードから当該ノードまでの間のコスト値とが付与され、前記始点ノードから当該ノードまでの通信経路を示す情報を前記経路情報として生成する処理と、を有し、
前記記憶処理は、前記生成された経路情報に付与されたノード情報と同じノード情報に対応するコスト値が前記テーブルに記憶されている場合、当該生成された経路情報に付与されたコスト値が、当該記憶されたコスト値よりも小さければ、前記記憶された経路情報のうち当該ノード情報が付与された経路情報を、当該生成された経路情報で置換するとともに、当該記憶されたコスト値を当該生成された経路情報に付与されたコスト値に変更する処理である経路決定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードで構成される通信ネットワークにおいて、始点ノードからの最短経路を決定する経路決定装置及び経路決定方法に関する。
【背景技術】
【０００２】
通信ネットワークでは、通信ネットワーク内のノードやリンクが故障した場合、故障した箇所で転送データが破棄されてしまう。これを回避するために、通信ネットワーク上のノードやリンクが故障した場合には、故障していないノードやリンクのみを転送データが通るように、新たな通信経路を決定する必要がある。
【０００３】
この場合、ノードやリンクにコスト値と呼ばれる重み値を設定し、ノードやリンクのコスト値が最小となる通信経路を新たな通信経路とするのが一般的である。このためには、コスト値が最小となる通信経路を決定するためのアルゴリズムが必要となる。このようなアルゴリズムとしては、例えばダイクストラアルゴリズムやベルマンフォードアルゴリズム等がある。以降、コスト値が最小となる通信経路のことを最短経路という。
【０００４】
複数のノードから構成される通信ネットワークにおいて最短経路を決定する場合、まず、複数のノードのうちの始点となる始点ノードから、始点ノードに隣接するノードまでの通信経路が検索される。検索された通信経路は、始点ノードから、検索された通信経路における最後のノードまでの最短経路の候補となる。そして、最短経路の候補のうちコスト値が最も小さな通信経路が、始点ノードから、その通信経路における最後のノードまでの最短経路として決定される。
【０００５】
次に、始点ノードから、決定した最短経路における最後のノードに隣接するノードまでの通信経路が検索される。そして、検索された通信経路は、始点ノードから、検索された通信経路の最後のノードまでの最短経路の候補となる。そして、最短経路の候補のうちコスト値が最も小さな通信経路が、始点ノードから、その通信経路における最後のノードまでの最短経路として決定される。これを繰り返すことにより、始点ノードから、複数のノードのうち始点ノード以外のノードのそれぞれまでの最短経路が順次決定される。
【０００６】
最短経路の候補の中から最短経路を決定する場合、ヒープやマージソート等のデータ構造を利用すると高速に行うことができる。なお、最短経路を決定するために利用できるデータ構造の１つであるヒープ構造が、例えば非特許文献１に記載されている。
【０００７】
ここで、データ構造として二分木ヒープを利用して最短経路を決定する方法について説明する。二分木ヒープのデータ構造は、１つの親に対して子の数が最大で２つの木構造である。
【０００８】
コンピュータ等において二分木ヒープを利用する場合、二分木ヒープをテーブルとして表したソート用テーブルを用意する。
【０００９】
図７は、ソート用テーブルの一例を説明するための図であり、（ａ）は二分木ヒープの一例を示す図、（ｂ）は二分木ヒープを表したソート用テーブルの一例を示す図である。
【００１０】
図７（ａ）に示す二分木ヒープにおいて親及び子は四角形で表されており、親または子のそれぞれは、最短経路の候補となる通信経路を示す経路情報である。経路情報には、複数のノードのそれぞれを識別するノード情報のうち、その経路情報が示す通信経路における最後のノードを識別するノード情報と、その通信経路のコスト値とが付与されている。なお、四角形内のアルファベットはノード情報を示している。
【００１１】
また、図７（ａ）に示す二分木ヒープにおいて、四角形の図中左の添字は、二分木ヒープにおける位置を示している。二分木ヒープを利用して最短経路を決定する場合、経路情報のそれぞれは、位置１から順番に追加されていく。例えば位置１〜３まで経路情報が入れられている場合、新たに最短経路の候補となった通信経路を示す経路情報は位置４に追加される。
【００１２】
また、図７（ａ）に示す二分木ヒープには、ルールが設定されている。このルールによれば、二分木ヒープにおいて親となる経路情報に付与されたコスト値と、その親の子となる経路情報に付与されたコスト値とが比較される。そして、子となる経路情報に付与されたコスト値が親となる経路情報に付与されたコスト値よりも小さければ、親となる経路情報と子となる経路情報との位置が入れ替えられる。これにより、付与されたコスト値の最も小さな経路情報が、位置１に置かれることになる。
【００１３】
図７（ｂ）に示すソート用テーブルは、図７（ａ）に示した二分木ヒープにおける位置を示す位置情報と、その位置の経路情報に付与されたノード情報及びコスト値とを対応付けて記憶している。
【００１４】
図７（ｂ）に示すソート用テーブルにおいて、親の位置を示す位置情報をＮとすると、その親の子の位置を示す位置情報は２Ｎ及び（２Ｎ＋１）となる。このようにして、ソート用テーブルにおいて親と子との関係が認識できるようになっている。
【００１５】
そして、上述した二分木ヒープに設定されたルールに従って親と子との入れ替えを行った結果、ソート用テーブルにおいて位置情報１に対応するノード情報を付与された経路情報が示す通信経路が最短経路として決定される。
【００１６】
次に、上述したようなソート用テーブルを用いて最短経路を決定する方法について具体的に説明する。ここでは、一例として、図８に示すようなトポロジの通信ネットワークにおいて最短経路を決定する場合について説明する。
【００１７】
図８に示したトポロジでは、複数のノードのそれぞれが円で表されている。円内のアルファベットはノード情報である。以降、例えば、ノード情報がＡのノードのことをノードＡという。また、円で表された２つのノード間の直線のそれぞれはリンクを示しており、それぞれの直線の近傍の数字はその２つのノード間のコスト値である。例えば、ノードＳとノードＡとの間のコスト値は４であり、ノードＳとノードＢとの間のコスト値は５である。なお、ここでは、ノードＳを始点ノードとした場合について説明する。
【００１８】
図９は、図８に示したトポロジの通信ネットワークにおいて最短経路を決定する動作の一例を説明するための図である。図９（ａ）〜（ｆ）のそれぞれはソート用テーブルに記憶された情報の推移の一例を示している。
【００１９】
まず、ノードＳからノードＳに隣接するノードまでの通信経路を示す経路情報、すなわち、＜ノードＳ→ノードＡ＞、＜ノードＳ→ノードＢ＞、＜ノードＳ→ノードＣ＞の通信経路を示す経路情報に付与されたノード情報及びコスト値がソート用テーブルに記憶される。なお、それぞれの経路情報に付与されたコスト値は、４、５、２である。
【００２０】
次に、二分木ヒープに設定されたルールに従って位置の入れ替えが行われる。すなわち、ソート用テーブルにおいてノード情報の入れ替えが行われる。これにより、ソート用テーブルは、図９（ａ）に示す状態になり、ソート用テーブルにおいて位置情報１に対応するのはノード情報Ｃ及びコスト値２が付与された経路情報となる。
【００２１】
従って、ノード情報Ｃが付与された経路情報が示す＜ノードＳ→ノードＣ＞の通信経路がノードＳからノードＣまでの最短経路として決定される。そして、この通信経路を示す経路情報が削除される。これにより、ソート用テーブルは、図９（ｂ）に示す状態になる。
【００２２】
そして、二分木ヒープに設定されたルールに従い、ソート用テーブルにおいてノード情報の入れ替えが行われる。これにより、ソート用テーブルは、図９（ｃ）に示す状態になる。
【００２３】
次に、ノードＳから、最短経路として決定した通信経路の最後のノードであるノードＣに隣接するノードＢまでの通信経路、すなわち、＜ノードＳ→ノードＣ→ノードＢ＞の通信経路を示す経路情報に付与されたノード情報及びコスト値がソート用テーブルに記憶される。なお、この経路情報に付与されたコスト値は、＜ノードＳ→ノードＣ＞の通信経路のコスト値である２と、＜ノードＣ→ノードＢ＞の通信経路のコスト値である１との合計の３である。これにより、ソート用テーブルは、図９（ｄ）に示す状態になる。なお、この場合、ソート用テーブルに２つのノード情報Ｂが記憶されていることになる。
【００２４】
そして、二分木ヒープに設定されたルールに従い、ソート用テーブルにおいてノード情報の入れ替えが行われる。これにより、ソート用テーブルは、図９（ｅ）に示す状態になる。
【００２５】
また、ノードＳから、最短経路として決定した通信経路の最後のノードであるノードＣに隣接するノードＥまでの通信経路、すなわち＜ノードＳ→ノードＣ→ノードＥ＞の通信経路を示す経路情報に付与されたノード情報及びコスト値がソート用テーブルに記憶される。なお、この経路情報に付与されたコスト値は、＜ノードＳ→ノードＣ＞の通信経路のコスト値である２と、＜ノードＣ→ノードＥ＞の通信経路のコスト値である５との合計の８である。
【００２６】
そして、二分木ヒープに設定されたルールに従い、ソート用テーブルにおいてノード情報の入れ替えが行われる。これにより、ソート用テーブルは、図９（ｆ）に示す状態になり、位置情報１に対応するのはノード情報Ｂ及びコスト値３が付与された経路情報となる。
【００２７】
従って、＜ノードＳ→ノードＣ→ノードＢ＞の通信経路がノードＳからノードＢまでの最短経路として決定され、この通信経路を示す経路情報が削除される。
【００２８】
上述した動作が繰り返されることにより、始点ノードからの最短経路が順次決定されていく。
【先行技術文献】
【非特許文献】
【００２９】
【非特許文献１】浅野孝夫著  日本評論社「情報の構造  上」４５頁〜５３頁
【発明の概要】
【発明が解決しようとする課題】
【００３０】
上述した方法においては、ノードＳからノードＢまでの最短経路が決定した後も、＜ノードＳ→ノードＢ＞の通信経路を示す経路情報に付与されたノード情報及びコスト値がソート用テーブルに記憶されている。
【００３１】
しかし、ノードＳからノードＢまでの最短経路が既に決定しているため、＜ノードＳ→ノードＢ＞の通信経路はノードＳからノードＢまでの最短経路とはなり得ない。そして、この通信経路を示す経路情報に付与されたノード情報及びコスト値は、コスト値が最小となるまでソート用テーブルに記憶され続けることになる。
【００３２】
つまり、不必要なノード情報及びコスト値がソート用テーブルに記憶されていることになり、二分木ヒープに設定されたルールに従ってソート用テーブルにおいてノード情報の入れ替えが行われる際に、コスト値を比較する回数が増えてしまう。その結果、最短経路を決定するまでの時間が長くなってしまうという問題点がある。
【００３３】
ここで、ソート用テーブルに記憶されるノード情報及びコスト値の数を最小限に抑制する方法について説明する。
【００３４】
図１０は、図８に示したトポロジの通信ネットワークにおいて最短経路を決定する動作の他の例を説明するための図である。図１０（ａ）〜（ｆ）のそれぞれはソート用テーブルに記憶された情報の推移を示している。
【００３５】
ソート用テーブルが図１０（ｃ）に示す状態になるまでの動作は、上述した図９（ｃ）に示した状態になるまでの動作と同様なので、説明を省略する。
【００３６】
図１０（ｃ）に示す状態の後、＜ノードＳ→ノードＣ→ノードＢ＞の通信経路を示す経路情報に付与されたノード情報Ｂ及びコスト値３をソート用テーブルに記憶させる場合を考える。
【００３７】
このとき、＜ノードＳ→ノードＢ＞の通信経路を示す経路情報に付与されたノード情報Ｂ及びコスト値５がソート用テーブルに既に記憶されている。
【００３８】
この場合、記憶させようとしているコスト値と、既に記憶されているコスト値とが比較される。そして、比較の結果、コスト値が小さな方だけをソート用テーブルに記憶させる。
【００３９】
ここでは、記憶させようとしているコスト値が３であり、既に記憶されたコスト値が５であるため、既に記憶されたコスト値が上書きされる。これにより、ソート用テーブルは、図１０（ｄ）に示す状態になる。
【００４０】
図９（ｄ）と図１０（ｄ）とを比較すると、図１０（ｄ）では、ノード情報Ｂ及びコスト値５がソート用テーブルに記憶されていないことがわかる。
【００４１】
ソート用テーブルが図１０（ｅ）及び図１０（ｆ）の状態になるまでの動作は、上述した図９（ｅ）及び図９（ｆ）に示した状態になるまでの動作と同様なので、説明を省略する。
【００４２】
このように、図１０を参照しながら説明した方法の場合、最短経路になり得ない通信経路を示す経路情報に付与されたノード情報及びコスト値がソート用テーブルに記憶されるのを回避することができる。つまり、図１０を参照しながら説明した方法を用いれば、二分木ヒープに設定されたルールに従ってソート用テーブルにおいてノード情報の入れ替えが行われる際に、コスト値を比較する回数を最小限に抑制することができる。
【００４３】
しかし、図１０を参照しながら説明した方法の場合でも、二分木ヒープに設定されたルールに従ってソート用テーブルにおいてノード情報の入れ替えが行われることには変わりはない。そのため、記憶させようとしているノード情報と同じノード情報が存在しているかどうかを確認するためには、ソート用テーブルを全検索する必要がある。
【００４４】
つまり、通信ネットワークにおける最短経路を決定する際に、データ構造を利用して管理されている経路情報の全てを検索する必要がある。
【００４５】
従って、図１０を参照しながら説明した方法を用いても、最短経路を決定するまでの時間が長くなってしまうという問題点を解決できるとは言えない。
【００４６】
本発明は、通信ネットワークにおける最短経路を短時間で決定できる経路決定装置及び経路決定方法を提供することを目的とする。
【課題を解決するための手段】
【００４７】
上記目的を達成するために本発明の経路決定装置は、複数のノードで構成される通信ネットワークにおける始点ノードから、前記複数のノードのうち前記始点ノード以外のそれぞれのノードまでの最短経路を決定する経路決定装置であって、
記憶部と、
前記複数のノードのそれぞれを識別する複数のノード情報のうち、前記始点ノードに隣接するノードを識別するノード情報と、前記始点ノードから当該ノードまでの間のコスト値とが付与され、前記始点ノードから当該ノードまでの通信経路を示す情報を経路情報として生成する経路決定部と、
前記生成された経路情報をデータ構造を利用して前記記憶部に記憶させるとともに、当該経路情報に付与されたノード情報及びコスト値と、当該経路情報の前記データ構造における位置を示す位置情報とを対応付けてテーブルに記憶させ、より小さなコスト値を付与された経路情報が前記データ構造においてより上位の位置になるように、前記記憶された経路情報の前記データ構造上の位置の入れ替えを行い、該入れ替えの結果に基づいて前記テーブルの位置情報を更新し、前記記憶された経路情報のうち前記テーブルにおいて最上位を示す位置情報に対応するノード情報が付与された経路情報を選択した後、該選択した経路情報を削除する制御部と、を有し、
前記経路決定部は、前記選択された経路情報が示す通信経路を、前記始点ノードから当該経路情報が示す通信経路における最後のノードまでの最短経路として決定し、当該通信経路における最後のノードに隣接するノードを識別するノード情報と、前記始点ノードから当該ノードまでの間のコスト値とが付与され、前記始点ノードから当該ノードまでの通信経路を示す情報を前記経路情報として生成し、
前記制御部は、前記生成された経路情報に付与されたノード情報と同じノード情報に対応するコスト値が前記テーブルに記憶されている場合、当該生成された経路情報に付与されたコスト値が、当該記憶されたコスト値よりも小さければ、前記記憶部に記憶された経路情報のうち当該ノード情報が付与された経路情報を、当該生成された経路情報で置換するとともに、当該記憶されたコスト値を当該生成された経路情報に付与されたコスト値に変更する。
【００４８】
また、上記目的を達成するために本発明の経路決定方法は、複数のノードで構成される通信ネットワークにおける始点ノードから、前記複数のノードのうち前記始点ノード以外のそれぞれのノードまでの最短経路を決定する経路決定装置における経路決定方法であって、
前記複数のノードのそれぞれを識別する複数のノード情報のうち、前記始点ノードに隣接するノードを識別するノード情報と、前記始点ノードから当該ノードまでの間のコスト値とが付与され、前記始点ノードから当該ノードまでの通信経路を示す情報を経路情報として生成する処理と、
前記生成された経路情報をデータ構造を利用して記憶するとともに、当該経路情報に付与されたノード情報及びコスト値と、当該経路情報の前記データ構造における位置を示す位置情報とを対応付けてテーブルに記憶させる記憶処理と、
より小さなコスト値を付与された経路情報が前記データ構造においてより上位の位置になるように、前記記憶された経路情報の前記データ構造上の位置の入れ替えを行い、該入れ替えの結果に基づいて前記テーブルの位置情報を更新する処理と、
前記記憶された経路情報のうち前記テーブルにおいて最上位を示す位置情報に対応するノード情報が付与された経路情報を選択した後、該選択した経路情報を削除する処理と、
前記選択された経路情報が示す通信経路を、前記始点ノードから当該経路情報が示す通信経路における最後のノードまでの最短経路として決定し、当該通信経路における最後のノードに隣接するノードを識別するノード情報と、前記始点ノードから当該ノードまでの間のコスト値とが付与され、前記始点ノードから当該ノードまでの通信経路を示す情報を前記経路情報として生成する処理と、を有し、
前記記憶処理は、前記生成された経路情報に付与されたノード情報と同じノード情報に対応するコスト値が前記テーブルに記憶されている場合、当該生成された経路情報に付与されたコスト値が、当該記憶されたコスト値よりも小さければ、前記記憶された経路情報のうち当該ノード情報が付与された経路情報を、当該生成された経路情報で置換するとともに、当該記憶されたコスト値を当該生成された経路情報に付与されたコスト値に変更する処理である。
【発明の効果】
【００４９】
本発明は以上説明したように構成されているので、ノード情報の入れ替えを行う際に、コスト値を比較する回数を最小限に抑制することができる。また、データ構造に設定されたルールに従ってデータ構造上の位置の入れ替えが行われてもノード情報の入れ替えが行われないテーブルを用いているため、データ構造を利用して管理されている経路情報の全てを検索する必要がない。
【００５０】
従って、通信ネットワークにおける最短経路を短時間で決定できる。
【図面の簡単な説明】
【００５１】
【図１】本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【図２】図１に示したテーブル記憶部に記憶されたテーブルの構成の一例を説明するための図であり（ａ）は二分木ヒープの一例を示す図、（ｂ）は二分木ヒープに対応するソート用テーブルの構成の一例を示す図、（ｃ）は優先度管理テーブルの構成の一例を示す図である。
【図３】図１に示したトポロジ情報部が管理するトポロジ情報が示すトポロジの一例を示す図である。
【図４】図１に示した経路決定装置が、図３に示したトポロジの通信ネットワークにおいて最短経路を決定する動作の一例を説明するための図である。
【図５】図１に示した経路決定装置が、図３に示したトポロジの通信ネットワークにおいて最短経路を決定する動作の一例を説明するための図である。
【図６】図１に示した経路決定装置の機能を実装したパケット転送装置の一構成例を示すブロック図である。
【図７】ソート用テーブルの一例を説明するための図であり、（ａ）は二分木ヒープの一例を示す図、（ｂ）は二分木ヒープに対応するソート用テーブルの一例を示す図である。
【図８】通信ネットワークのトポロジの一例を示す図である。
【図９】図８に示したトポロジの通信ネットワークにおいて最短経路を決定する動作の一例を説明するための図である。
【図１０】図８に示したトポロジの通信ネットワークにおいて最短経路を決定する動作の他の例を説明するための図である。
【発明を実施するための形態】
【００５２】
以下に、本発明の実施の形態について図面を参照して説明する。
【００５３】
図１は、本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【００５４】
図１に示す経路決定装置１０は、制御部１１と、記憶部１２と、テーブル記憶部１３と、経路決定部１４と、トポロジ情報部１５とを備えている。
【００５５】
トポロジ情報部１５は、通信ネットワークのトポロジを示すトポロジ情報を管理する。
【００５６】
経路決定部１４は、トポロジ情報部１５からトポロジ情報を取得する。そして、経路決定部１４は、取得したトポロジ情報が示すトポロジの通信ネットワークを構成する複数のノードのうち最短経路を決定する通信経路の始点となる始点ノードから、始点ノードに隣接するノードまでの通信経路を示す情報を経路情報として生成する。そして、経路決定部１４は、生成した経路情報を制御部１１へ出力する。その後、経路決定部１４は、制御部１１から出力された経路情報を受け付け、受け付けた経路情報が示す通信経路を、始点ノードからその通信経路における最後のノードまでの最短経路として決定する。次に、経路決定部１４は、始点ノードから、最短経路として決定した通信経路における最後のノードに隣接するノードまでの通信経路を示す情報を経路情報として生成して制御部１１へ出力する。このように、経路決定部１４は、経路情報の生成と最短経路の決定とを繰り返して行う。これにより、始点ノードから、複数のノードのうちの始点ノード以外のノードのそれぞれまでの最短経路が順次決定していく。なお、経路情報には、複数のノードのそれぞれを識別する複数のノード情報のうち、その経路情報が示す通信経路における最後のノードを示すノード情報と、その通信経路のコスト値とが付与されている。
【００５７】
記憶部１２は、経路決定部１４にて生成された経路情報を記憶する。
【００５８】
テーブル記憶部１３は、ソート用テーブルと優先度管理テーブルとを記憶している。
【００５９】
図２は、図１に示したテーブル記憶部１３に記憶されたテーブルの構成の一例を説明するための図であり（ａ）は二分木ヒープの一例を示す図、（ｂ）は二分木ヒープに対応するソート用テーブルの構成の一例を示す図、（ｃ）は優先度管理テーブルの構成の一例を示す図である。
【００６０】
図２（ａ）に示す二分木ヒープにおいて親及び子は四角形で表されており、親または子のそれぞれは、記憶部１２に記憶された経路情報である。また、四角形内のアルファベットはノード情報を示している。
【００６１】
図２（ｂ）に示すソート用テーブルは、図２（ａ）に示した二分木ヒープにおける位置を示す位置情報と、その位置の経路情報に付与されたノード情報とを対応付けて記憶する。
【００６２】
図２（ｃ）に示す優先度管理テーブルは、ノード情報とコスト値と二分木ヒープにおける位置を示す位置情報とを対応付けて記憶する。
【００６３】
再度、図１を参照すると、制御部１１は、経路決定部１４から出力された経路情報を受け付け、受け付けた経路情報を二分木ヒープのデータ構造を利用して記憶部１２に記憶させる。それとともに、制御部１１は、受け付けた経路情報に付与されたノード情報及びコスト値と、その経路情報の二分木ヒープにおける位置を示す位置情報とを対応付けて優先度管理テーブルに記憶させる。これらの情報を優先度管理テーブルに記憶させる際、制御部１１は、優先度管理テーブルに記憶された情報を確認する。確認の結果、受け付けた経路情報に付与されたノード情報と同じノード情報に対応するコスト値が優先度管理テーブルに記憶されている場合、制御部１１は、受け付けた経路情報に付与されたコスト値と、優先度管理テーブルに記憶されたコスト値とを比較する。比較の結果、受け付けた経路情報に付与されたコスト値が、優先度管理テーブルに記憶されたコスト値よりも小さければ、制御部１１は、記憶部１２に記憶された経路情報のうちそのノード情報が付与された経路情報を、受け付けた経路情報で置換する。それとともに、制御部１１は、優先度管理テーブルに記憶されたコスト値を、受け付けた経路情報に付与されたコスト値に変更する。次に、制御部１１は、二分木ヒープに設定されたルールに従い、記憶部１２に記憶された経路情報の二分木ヒープにおける位置の入れ替えを行う。すなわち、制御部１１は、ソート用テーブルにおいてノード情報の入れ替えを行う。そして、制御部１１は、この入れ替えの結果に基づいて優先度管理テーブルの位置情報を更新する。次に、制御部１１は、優先度管理テーブルにおいて最上位の位置を示す位置情報１に対応するノード情報が付与された経路情報を選択して経路決定部１４へ出力する。その後、制御部１１は、選択した経路情報を記憶部１２から削除し、二分木ヒープに設定されたルールに従い、ソート用テーブルにおいてノード情報の入れ替えを行う。
【００６４】
なお、二分木ヒープに設定されたルールとは、より小さなコスト値を付与された経路情報が二分木ヒープにおいてより上位の位置になるように、記憶部１２に記憶された経路情報の二分木ヒープ上の位置を入れ替えるルールである。具体的には、二分木ヒープにおいて親となる経路情報に付与されたコスト値と、その親の子となる経路情報に付与されたコスト値とが比較される。そして、子となる経路情報に付与されたコスト値が親となる経路情報に付与されたコスト値よりも小さければ、親となる経路情報と子となる経路情報との位置が入れ替えられる。これにより、記憶部１２に記憶された経路情報のうち、付与されたコスト値の最も小さな経路情報が、二分木ヒープにおける最上位の位置になる。
【００６５】
以下に、上記のように構成された経路決定装置１０において最短経路を決定する動作について説明する。
【００６６】
まず、図１に示したトポロジ情報部１５が管理するトポロジ情報が示すトポロジの一例について説明する。
【００６７】
図３は、図１に示したトポロジ情報部１５が管理するトポロジ情報が示すトポロジの一例を示す図である。
【００６８】
図３に示したトポロジでは、複数のノードのそれぞれが円で表されている。円内のアルファベットはノード情報である。以降、例えば、ノード情報がＡのノードのことをノードＡという。また、円で表された２つのノード間の直線のそれぞれはリンクを示しており、それぞれの直線の近傍の数字はその２つのノード間のコスト値である。例えば、ノードＳとノードＡとの間のコスト値は１であり、ノードＳとノードＢとの間のコスト値は３である。
【００６９】
図４及び図５は、図１に示した経路決定装置１０が、図３に示したトポロジの通信ネットワークにおいて最短経路を決定する動作の一例を説明するための図である。図４（ａ）〜（ｄ）は、ソート用テーブルに記憶された情報の推移の一例を示す図であり、図５（ａ）〜（ｄ）は、優先度管理テーブルに記憶された情報の推移の一例を示す図である。
【００７０】
なお、ここでは、図３に示したトポロジにおいて、ノードＳを始点ノードとした場合について説明する。
【００７１】
まず、経路決定部１４は、ノードＳからノードＳに隣接するノードまでの通信経路を示す経路情報を生成する。図３を参照すると、ノードＳに隣接するノードはノードＡ及びノードＢである。また、＜ノードＳ→ノードＡ＞の通信経路のコスト値は１であり、＜ノードＳ→ノードＢ＞の通信経路のコスト値は３である。
【００７２】
従って、経路決定部１４は、＜ノードＳ→ノードＡ＞の通信経路を示し、ノード情報Ａ及びコスト値１が付与された経路情報を生成して制御部１１へ出力する。また、経路決定部１４は、＜ノードＳ→ノードＢ＞の通信経路を示し、ノード情報Ｂ及びコスト値３が付与された経路情報を生成して制御部１１へ出力する。
【００７３】
経路決定部１４から出力された経路情報を受け付けた制御部１１は、優先度管理テーブルに記憶された情報を確認する。この時点では、記憶部１２に経路情報が記憶されていない。そのため、ノード情報Ａ及びノード情報Ｂに対応するコスト値が優先度管理テーブルに記憶されていない。
【００７４】
従って、制御部１１は、受け付けた経路情報を記憶部１２に記憶させるとともに、受け付けた経路情報に付与されたノード情報及びコスト値と、受け付けた経路情報の二分木ヒープにおける位置を示す位置情報とを対応付けて優先度管理テーブルに記憶させる。
【００７５】
次に、制御部１１は、二分木ヒープに設定されたルールに従い、ソート用テーブルにおいてノード情報の入れ替えを行う。これにより、ソート用テーブルは、図４（ａ）に示す状態になる。
【００７６】
そして、制御部１１は、ソート用テーブルにおいてノード情報の入れ替えを行った結果に基づき、優先度管理テーブルの位置情報を更新する。これにより、優先度管理テーブルは、図５（ａ）に示す状態になる。
【００７７】
次に、制御部１１は、優先度管理テーブルにおいて位置情報１に対応するノード情報が付与された経路情報を選択して経路決定部１４へ出力する。ここでは、優先度管理テーブルにおいて位置情報１に対応するノード情報はノード情報Ａであり、ノード情報Ａが付与された経路情報は、＜ノードＳ→ノードＡ＞の通信経路を示す経路情報である。
【００７８】
次に、制御部１１は、出力した経路情報を記憶部１２から削除する。
【００７９】
そして、制御部１１は、二分木ヒープに設定されたルールに従い、ソート用テーブルにおいてノード情報の入れ替えを行う。これにより、ソート用テーブルは、図４（ｂ）に示す状態になる。
【００８０】
また、制御部１１は、ソート用テーブルにおいてノード情報の入れ替えを行った結果に基づき、優先度管理テーブルの位置情報を更新する。これにより、優先度管理テーブルは、図５（ｂ）に示す状態になる。
【００８１】
制御部１１から出力された経路情報を受け付けた経路決定部１４は、受け付けた経路情報が示す＜ノードＳ→ノードＡ＞の通信経路を、ノードＳからノードＡまでの最短経路として決定する。
【００８２】
次に、経路決定部１４は、ノードＳから、最短経路として決定した通信経路における最後のノード（ここではノードＡ）に隣接するノードまでの通信経路を示す経路情報を生成する。図３を参照すると、ノードＡに隣接するノードはノードＢ及びノードＣである。また、＜ノードＳ→ノードＡ→ノードＢ＞の通信経路のコスト値は２であり、＜ノードＳ→ノードＡ→ノードＣ＞の通信経路のコスト値は４である。
【００８３】
従って、経路決定部１４は、＜ノードＳ→ノードＡ→ノードＢ＞の通信経路を示し、ノード情報Ｂ及びコスト値２が付与された経路情報を生成して制御部１１へ出力する。それとともに、経路決定部１４は、＜ノードＳ→ノードＡ→ノードＣ＞の通信経路を示し、ノード情報Ｃ及びコスト値４が付与された経路情報を生成して制御部１１へ出力する。
【００８４】
経路決定部１４から出力された経路情報を受け付けた制御部１１は、優先度管理テーブルを確認する。ここでは、図５（ｂ）に示すように、ノード情報Ｂに対応するコスト値は優先度管理テーブルに記憶されている。一方、ノード情報Ｃに対応するコスト値は優先度管理テーブルに記憶されていない。
【００８５】
そのため、制御部１１は、受け付けた経路情報のうちノード情報Ｂが付与された経路情報に付与されたコスト値（２）と、優先度管理テーブルにおいてノード情報Ｂに対応するコスト値（３）とを比較する。ここでは、受け付けた経路情報のうちノード情報Ｂが付与された経路情報に付与されたコスト値の方が小さい。
【００８６】
従って、制御部１１は、記憶部１２に記憶された経路情報のうちノード情報Ｂが付与された経路情報を、受け付けた経路情報のうちノード情報Ｂが付与された経路情報で置換する。それとともに、制御部１１は、優先度管理テーブルにおいてノード情報Ｂに対応するコスト値を３から２に変更する。
【００８７】
また、制御部１１は、受け付けた経路情報のうちノード情報Ｃが付与された経路情報を記憶部１２に記憶させる。それとともに、制御部１１は、この経路情報に付与されたノード情報及びコスト値と、この経路情報の二分木ヒープにおける位置を示す位置情報とを対応付けて優先度管理テーブルに記憶させる。
【００８８】
次に、制御部１１は、二分木ヒープに設定されたルールに従い、ソート用テーブルにおいてノード情報の入れ替えを行う。これにより、ソート用テーブルは、図４（ｃ）に示す状態になる。
【００８９】
そして、制御部１１は、ソート用テーブルにおいてノード情報の入れ替えを行った結果に基づき、優先度管理テーブルの位置情報を更新する。これにより、優先度管理テーブルは、図５（ｃ）に示す状態になる。
【００９０】
次に、制御部１１は、優先度管理テーブルにおいて位置情報１に対応するノード情報が付与された経路情報を選択して経路決定部１４へ出力する。ここでは、優先度管理テーブルにおいて位置情報１に対応するノード情報はノード情報Ｂであり、ノード情報Ｂが付与された経路情報は、＜ノードＳ→ノードＡ→ノードＢ＞の通信経路を示す経路情報である。
【００９１】
次に、制御部１１は、出力した経路情報を記憶部１２から削除する。
【００９２】
そして、制御部１１は、二分木ヒープに設定されたルールに従い、ソート用テーブルにおいてノード情報の入れ替えを行う。これにより、ソート用テーブルは、図４（ｄ）に示す状態になる。
【００９３】
また、制御部１１は、ソート用テーブルにおいてノード情報の入れ替えを行った結果に基づいて優先度管理テーブルの位置情報を更新する。これにより、優先度管理テーブルは、図５（ｄ）に示す状態になる。
【００９４】
制御部１１から出力された経路情報を受け付けた経路決定部１４は、受け付けた経路情報が示す＜ノードＳ→ノードＡ→ノードＢ＞の通信経路を、ノードＳからノードＢまでの最短経路として決定する。
【００９５】
次に、経路決定部１４は、ノードＳから、最短経路として決定した通信経路における最後のノード（ここではノードＢ）に隣接するノードまでの通信経路を示す経路情報を生成する。図３を参照すると、ノードＢに隣接するノードはノードＣである。なお、ここでは、既に最短経路が決定したノードＡは除外される。また、＜ノードＳ→ノードＡ→ノードＢ→ノードＣ＞の通信経路のコスト値は４である。
【００９６】
従って、経路決定部１４は、＜ノードＳ→ノードＡ→ノードＢ→ノードＣ＞の通信経路を示し、ノード情報Ｃ及びコスト値４が付与された経路情報を生成して制御部１１へ出力する。
【００９７】
経路決定部１４から出力された経路情報を受け付けた制御部１１は、優先度管理テーブルを確認する。ここでは、図５（ｄ）に示すように、優先度管理テーブルにノード情報Ｃに対応するコスト値が記憶されている。
【００９８】
そのため、制御部１１は、受け付けた経路情報に付与されたコスト値（４）と、優先度管理テーブルに記憶されているノード情報Ｃに対応するコスト値（４）とを比較する。ここでは、両方のコスト値が同じである。
【００９９】
この場合、制御部１１は、受け付けた経路情報を破棄する。なお、記憶部１２に記憶された経路情報のうちノード情報Ｃが付与された経路情報を、受け付けた経路情報で置換してもよい。
【０１００】
次に、制御部１１は、優先度管理テーブルにおいて位置情報１に対応するノード情報が付与された経路情報を選択して経路決定部１４へ出力する。なお、受け付けた経路情報を破棄した場合、制御部１１は、＜ノードＳ→ノードＡ→ノードＣ＞の通信経路を示す経路情報を経路決定部１４へ出力することとなる。一方、経路情報を置換した場合には、制御部１１は、＜ノードＳ→ノードＡ→ノードＢ→ノードＣ＞の通信経路を示す経路情報を出力することとなる。
【０１０１】
制御部１１から出力されたノードＳからノードＣまでの間の通信経路を示す経路情報を受け付けた経路決定部１４は、受け付けた経路情報が示す通信経路を、ノードＳからノードＣまでの間の最短経路として決定する。
【０１０２】
このように本実施形態において経路決定装置１０は、複数のノードのそれぞれを識別する複数のノード情報のうち、始点ノードに隣接するノードを識別するノード情報と、始点ノードから当該ノードまでの間のコスト値とが付与され、始点ノードから当該ノードまでの通信経路を示す情報を経路情報として生成する。
【０１０３】
次に、経路決定装置１０は、生成された経路情報をデータ構造を利用して記憶する。それとともに、経路決定装置１０は、当該経路情報に付与されたノード情報及びコスト値と、当該経路情報のデータ構造における位置を示す位置情報とを対応付けて優先度管理テーブルに記憶させる。
【０１０４】
このとき、経路決定装置１０は、生成された経路情報に付与されたノード情報と同じノード情報に対応するコスト値が優先度管理テーブルに記憶されている場合、当該生成された経路情報に付与されたコスト値が、当該記憶されたコスト値よりも小さければ、記憶された経路情報のうち当該ノード情報が付与された経路情報を、当該生成された経路情報で置換する。それとともに、経路決定装置１０は、当該記憶されたコスト値を当該生成された経路情報に付与されたコスト値に変更する。
【０１０５】
次に、経路決定装置１０は、より小さなコスト値を付与された経路情報がデータ構造においてより上位の位置になるように、記憶された経路情報のデータ構造上の位置の入れ替えを行い、入れ替えの結果に基づいて優先度管理テーブルの位置情報を更新する。
【０１０６】
次に、経路決定装置１０は、記憶された経路情報のうち優先度管理テーブルにおいて位置情報１に対応するノード情報が付与された経路情報を選択した後、選択した経路情報を削除する。
【０１０７】
そして、経路決定装置１０は、選択された経路情報が示す通信経路を、始点ノードから当該経路情報が示す通信経路における最後のノードまでの最短経路として決定し、当該通信経路における最後のノードに隣接するノードを識別するノード情報と、始点ノードから当該ノードまでの間のコスト値とが付与され、始点ノードから当該ノードまでの通信経路を示す情報を経路情報として生成する。
【０１０８】
経路決定装置１０は上記のように構成されているため、ノード情報の入れ替えを行う際に、コスト値を比較する回数を最小限に抑制することができる。また、データ構造に設定されたルールに従ってデータ構造上の位置の入れ替えが行われてもノード情報の入れ替えが行われない優先度管理テーブルを用いているため、データ構造を利用して管理されている経路情報の全てを検索する必要がない。
【０１０９】
従って、通信ネットワークにおける最短経路を短時間で決定できる。
【０１１０】
なお、上述した経路決定装置１０の機能を、ルータ等のパケット転送装置に実装してもよい。これにより、パケット転送装置において最短経路の決定にかかる負荷を軽減することができる。
【０１１１】
図６は、図１に示した経路決定装置１０の機能を実装したパケット転送装置の一構成例を示すブロック図である。
【０１１２】
図１０に示すパケット転送装置２０は、制御部１１と、記憶部１２と、テーブル記憶部１３と、送受信部２１と、経路情報制御部２２と、パケット転送部２３と、ネクストホップ検索部２４とを備えている。
【０１１３】
制御部１１、記憶部１２及びテーブル記憶部１３については、既に説明しているので、ここでは説明を省略する。
【０１１４】
送受信部２１は、通信ネットワークに関する情報やパケットの送受信を外部装置と行う。
【０１１５】
経路情報制御部２２は、上述した経路決定部１４の機能を有し、送受信部２１にて受信した通信ネットワークに関する情報に基づいてパケットの転送先等を設定する。
【０１１６】
パケット転送部２３は、送受信部２１にて受信したパケットの宛先アドレスに基づき、経路情報制御部２２が設定した転送先へ受信したパケットを転送するために、受信したパケットのヘッダ情報の書き換え等を行う。そして、送受信部２１を介してパケットを転送する。
【０１１７】
なお、ここでは、経路決定装置１０の機能を実装したパケット転送装置について説明したが、経路決定装置１０と、経路決定装置１０の機能が実装されていないパケット転送装置とをインタフェース等を介して接続してもパケット転送装置２０と同等の機能を実現できる。
【符号の説明】
【０１１８】
１０    経路決定装置
１１    制御部
１２    記憶部
１３    テーブル記憶部
１４    経路決定部
１５    トポロジ情報部
２０    パケット転送装置
２１    送受信部
２２    経路情報制御部
２３    パケット転送部
２４    ネクストホップ検索部
【図１】
2012054756.tif 000003
【図２】
2012054756.tif 000004
【図３】
2012054756.tif 000005
【図４】
2012054756.tif 000006
【図５】
2012054756.tif 000007
【図６】
2012054756.tif 000008
【図７】
2012054756.tif 000009
【図８】
2012054756.tif 000010
【図９】
2012054756.tif 000011
【図１０】
2012054756.tif 000012