経路決定方法および経路決定装置
【課題】最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避する。
【解決手段】通信ネットワークを構成する複数のノードのそれぞれから、複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定方法であって、複数のノードのうち、当該ノードからの最短経路が決定していない未決定終点ノードが存在するノードの１つを始点ノードとして選択する選択処理と、始点ノードから未決定終点ノードまでの最短経路を決定する処理と、決定された最短経路上の始点ノード以外のノードから、当該最短経路を介して当該最短経路の終点ノードまで至る通信経路を、当該ノードから当該終点ノードまでの最短経路として決定する処理と、を有する。
【解決手段】通信ネットワークを構成する複数のノードのそれぞれから、複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定方法であって、複数のノードのうち、当該ノードからの最短経路が決定していない未決定終点ノードが存在するノードの１つを始点ノードとして選択する選択処理と、始点ノードから未決定終点ノードまでの最短経路を決定する処理と、決定された最短経路上の始点ノード以外のノードから、当該最短経路を介して当該最短経路の終点ノードまで至る通信経路を、当該ノードから当該終点ノードまでの最短経路として決定する処理と、を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードから構成される通信ネットワークにおける２つのノード間の最短経路を決定する経路決定方法および経路決定装置に関する。
【背景技術】
【０００２】
複数のノードから構成される通信ネットワークにおいては、その複数のノードのいずれかである始点ノードから、その複数のノードのうちの始点ノード以外のノードである終点ノードまでの通信経路が複数ある。そのため、その複数の通信経路のうち、最も効率的な通信経路である最短経路を決定する必要がある。
【０００３】
そこで、複数のノードのそれぞれを接続するリンクにコスト値と呼ばれる重み値を設定する。そして、始点ノードから終点ノードまでの複数の通信経路のそれぞれのコスト値を計算することにより、コスト値が最小となる通信経路を最短経路として決定するのが一般的である。
【０００４】
上述したような計算によって最短経路を決定するためのアルゴリズムの１つであるダイクストラ法が例えば、非特許文献１に開示されている。
【０００５】
図９は、ダイクストラ法を用いて最短経路を決定する動作を説明するためのフローチャートである。
【０００６】
まず、通信ネットワークを構成する複数のノードのうち始点ノードとして選択されていないノードがあるかどうかが判定される（ステップＳ１０１）。
【０００７】
ステップＳ１０１における判定の結果、始点ノードとして選択されていないノードがない場合、処理が終了する。
【０００８】
一方、ステップＳ１０１における判定の結果、始点ノードとして選択されていないノードがある場合には、始点ノードとして選択されていないノードの１つが始点ノードとして選択される（ステップＳ１０２）。なお、始点ノードとして選択されたノードは、決定済みの最短経路の終点ノードとして認識される。
【０００９】
次に、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードがあるかどうかが判定される（ステップＳ１０３）。なお、「終点ノードに隣接するノード」とは終点ノードとリンクによって直接接続されたノードのことであり、終点ノードとそのノードとの間には他のノードが存在しない。これは、以降の説明においていも同様である。
【００１０】
ステップＳ１０３における判定の結果、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードがある場合、始点ノードからそのノードまでの通信経路が最短経路候補とされる。
【００１１】
そして、最短経路候補のコスト値を算出する計算が行われ、算出されたコスト値が最小となる最短経路候補が最短経路として決定される（ステップＳ１０４）。そして、ステップＳ１０３の動作へ遷移する。
【００１２】
一方、ステップＳ１０３における判定の結果、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードがない場合には、ステップＳ１０１の動作へ遷移する。
【００１３】
図１０は、図９に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図、（ｂ）は最短経路が決定していく推移の一例を示す図である。なお、図１０（ａ）においては、ノードａ〜ｇが黒丸で表されている。また、以降、通信経路を＜ノードａ→ノードｂ＞のように＜ ＞を用いて表記する。
【００１４】
まず、上述したステップＳ１０１の動作に従い、図１０（ａ）に示す通信ネットワークを構成するノードａ〜ｇのうち始点ノードとして選択されていないノードがあるかどうかが判定される。ここでは、ノードａ〜ｇが始点ノードとして選択されていないものとする。
【００１５】
従って、上述したステップＳ１０２の動作に従い、ノードａ〜ｇのうちの１つを始点ノードとして選択する。ここでは、ノードａが始点ノードとして選択されるものとする。これにより、ノードａは決定済みの最短経路の終点ノードとして認識される。
【００１６】
次に、上述したステップＳ１０３の動作に従い、決定済みの最短経路の終点ノードに隣接し、始点ノードからの最短経路が未決定のノードがあるかどうかが判定される。ここでは、決定済みの最短経路の終点ノードはノードａである。また、始点ノードはノードａである。図１０（ａ）に示した通信ネットワークにおいてノードａに隣接するノードは、ノードｂおよびノードｅである。また、ここでは、ノードａからの最短経路が決定しているノードはない。従って、＜ノードａ→ノードｂ＞および＜ノードａ→ノードｅ＞の２つが最短経路候補となる。
【００１７】
次に、＜ノードａ→ノードｂ＞および＜ノードａ→ノードｅ＞のコスト値を算出する計算が行われる。ここでは、＜ノードａ→ノードｂ＞のコスト値の方が＜ノードａ→ノードｅ＞のコスト値よりも小さいものとする。そのため、上述したステップＳ１０４の動作に従い、＜ノードａ→ノードｂ＞がノードａからノードｂまでの最短経路として決定される。ここまでに決定した最短経路が図１０（ｂ）の上段に示されている。
【００１８】
次に、上述したステップＳ１０３の動作へ遷移し、決定済みの最短経路の終点ノードに隣接し、始点ノードからの最短経路が未決定のノードがあるかどうかが判定される。ここでは、決定済みの最短経路の終点ノードはノードａおよびノードｂである。また、始点ノードはノードａである。図１０（ａ）に示した通信ネットワークにおいて、ノードａに隣接するノードはノードｂおよびノードｅであり、ノードｂに隣接するノードはノードｃおよびノードｇである。ここで、＜ノードａ→ノードｂ＞は最短経路として決定済みである。従って、＜ノードａ→ノードｂ→ノードｃ＞と、＜ノードａ→ノードｂ→ノードｇ＞と、＜ノードａ→ノードｅ＞との３つの通信経路が最短経路候補となる。
【００１９】
次に、＜ノードａ→ノードｂ→ノードｃ＞と、＜ノードａ→ノードｂ→ノードｇ＞と、＜ノードａ→ノードｅ＞とのコスト値を算出する計算が行われる。ここでは、＜ノードａ→ノードｂ→ノードｃ＞のコスト値が＜ノードａ→ノードｂ→ノードｇ＞および＜ノードａ→ノードｅ＞のコスト値よりも小さいものとする。そのため、上述したステップＳ１０４の動作に従い、＜ノードａ→ノードｂ→ノードｃ＞がノードａからノードｃまでの最短経路として決定される。ここまでに決定した最短経路が図１０（ｂ）の中段に示されている。
【００２０】
以降、同様の動作を繰り返すことにより、上述したステップＳ１０４の動作に従い、＜ノードａ→ノードｂ→ノードｃ→ノードｄ＞がノードａからノードｄまでの最短経路として決定されたものとする。ここまでに決定された最短経路が図１０（ｂ）の下段に示されている。
【００２１】
このように、通信ネットワークを構成する複数のノードのうちの１つを始点ノードとして選択し、始点ノードとして選択されたノードからの最短経路が順次決定していく。その始点ノードからの最短経路が全て決定した後、始点ノードとして選択されていないノードの１つが始点ノードとして選択され、始点ノードとして選択されたノードからの最短経路が順次決定していくことになる。つまり、ダイクストラ法を用いた場合、図１０（ｂ）に示したような表の行毎に最短経路が順次決定していくことになる。
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs".Numerische Mathematik 1:269-271(http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf. )
【発明の概要】
【発明が解決しようとする課題】
【００２３】
上述したダイクストラ法のようなアルゴリズムは、ある１つのノードから他のノードへの最短経路を決定するためのアルゴリズムである。そのため、最短経路を決定するためのコスト値の計算を複数のノード毎に行うことになる。
【００２４】
この場合、同じ通信経路についてコスト値の計算が複数回行われることになる。つまり、不必要な計算を行うことによって最短経路を決定するまでの時間が必要以上に長くなってしまうという問題点がある。
【００２５】
本発明は、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避することができる経路決定方法および経路決定装置を提供することを目的とする。
【課題を解決するための手段】
【００２６】
上記目的を達成するために本発明の経路決定方法は、通信ネットワークを構成する複数のノードのそれぞれから、前記複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定方法であって、
前記複数のノードのうち、当該ノードからの最短経路が決定していない未決定終点ノードが存在するノードの１つを始点ノードとして選択する選択処理と、
前記始点ノードから前記未決定終点ノードまでの最短経路を決定する処理と、
前記決定された最短経路上の始点ノード以外のノードから、当該最短経路を介して当該最短経路の終点ノードまで至る通信経路を、当該ノードから当該終点ノードまでの最短経路として決定する処理と、を有する。
【００２７】
また、上記目的を達成するために本発明の経路決定装置は、通信ネットワークを構成する複数のノードのそれぞれから、前記複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置であって、上記の経路決定方法における処理を実行する。
【発明の効果】
【００２８】
本発明は以上説明したように構成されているので、２番目以降に始点ノードとして選択されるノードからの最短経路の一部は、それ以前に始点ノードとして選択されたノードからの最短経路が決定するとともに決定していることになる。
【００２９】
そのため、同じ通信経路について複数回のコスト値の計算が行われることがなくなり、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避することができる。
【図面の簡単な説明】
【００３０】
【図１】通信ネットワークの一例を示す図である。
【図２】本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【図３】図２に示した記憶部が備える最短経路決定表の一例を示す図である。
【図４】図２および図３に示した経路決定装置が最短経路を決定する動作を説明するためのフローチャートである。
【図５】図２および図３に示した経路決定装置が最短経路を決定する動作の具体例を説明するための図であり、（ａ）はトポロジ情報部に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は最短経路決定表の状態の推移の一例を示す図である。
【図６】図２および図３に示した経路決定装置が最短経路を決定する動作の他の具体例を説明するための図であり、（ａ）はトポロジ情報部に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は最短経路決定表の状態の推移の一例を示す図である。
【図７】図２に示した選択部が始点ノードを選択する際の動作の一例を説明するための図である。
【図８】図２に示した選択部が始点ノードを選択する際の動作の他の例を説明するための図であり、（ａ）はトポロジ情報部に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は複数のノード毎のメトリック値を示す図である。
【図９】ダイクストラ法を用いて最短経路を決定する動作を説明するためのフローチャートである。
【図１０】図９に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図、（ｂ）は最短経路が決定していく推移の一例を示す図である。
【発明を実施するための形態】
【００３１】
以下に、本発明の実施の形態について図面を参照して説明する。
【００３２】
本発明では、ある２つのノード間の最短経路の一部が、その最短経路上の２つのノード間の最短経路となることを用いて最短経路を決定していく。
【００３３】
図１は、通信ネットワークの一例を示す図である。なお、図１においては、ノードａ〜ｆが黒丸で表されている。
【００３４】
ここでは、図１に示す通信ネットワークにおいて、ノードａからノードｄまでの最短経路が＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞であるならば、ノードｂからノードｃへの最短経路は、＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞の一部である＜ノードｂ→ノードｅ→ノードｃ＞であることを証明する。
【００３５】
まず、以下に示す（１）（２）を仮定する。
（１）ノードａからノードｄまでの最短経路は＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞である
（２）ノードｂからノードｃまでの最短経路は＜ノードｂ→ノードｆ→ノードｃ＞である
ここで、上記の（２）が正しいとすると、ノードａからノードｄまでの最短経路は＜ノードａ→ノードｂ→ノードｆ→ノードｃ→ノードｄとなり、上記の（１）と（２）とは矛盾する。従って、ノードａからノードｄまでの最短経路が＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞であれば、ノードｂからノードｃまでの最短経路は＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞の一部である＜ノードｂ→ノードｅ→ノードｃ＞となる。
【００３６】
このように、ある２つのノード間の最短経路の一部は、その最短経路上の２つのノード間の最短経路となる。本発明においては、ある２つのノード間の最短経路が決定したとき、その最短経路上の始点ノード以外のノードから、その最短経路を介してその最短経路の終点ノードへ至る通信経路も最短経路として決定する。
【００３７】
図２は、本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【００３８】
図２に示す経路決定装置１０は、トポロジ情報部１１と、記憶部１２、選択部１３と、決定部１４とを備えている。
【００３９】
トポロジ情報部１１は、通信ネットワークを示すトポロジ情報を記憶する。なお、トポロジ情報には、通信ネットワークを構成する複数のノードと、その複数のノードのそれぞれの接続状態とが含まれている。
【００４０】
記憶部１２は、トポロジ情報部１１が記憶するトポロジ情報が示す通信ネットワークを構成する複数のノードのそれぞれを始点ノードとし、その始点ノードから終点ノードまでの最短経路が決定されているかどうかを示す最短経路決定表を備えている。
【００４１】
図３は、図２に示した記憶部１２が備える最短経路決定表の一例を示す図である。
【００４２】
最短経路決定表は図３に示すように、列方向を始点ノードとし、行方向を終点ノードとしている。図３に示す例では、ノードａを始点ノードとした場合の最短経路の全てが決定されている状態を示している。
【００４３】
再度図２を参照すると、選択部１３は、記憶部１２に記憶された最短経路決定表を参照する。そして、選択部１３は、トポロジ情報が示す通信ネットワークを構成する複数のノードのうち、そのノードを始点ノードとした場合の最短経路が決定していない終点ノードである未決定終点ノードが存在するノードがあるかどうかを判定する。その判定の結果、未決定終点ノードが存在するノードがある場合、選択部１３は、未決定終点ノードが存在するノードの１つを始点ノードとして選択する。例えば、最短経路決定表が図３に示した状態である場合、選択部１３は、ノードｂ〜ｄうちの１つを始点ノードとして選択することになる。そして、選択部１３は、始点ノードとして選択したノードを示す選択ノード情報を決定部１４へ出力する。
【００４４】
決定部１４は、トポロジ情報部１１に記憶されたトポロジ情報を取得する。また、決定部１４は、選択部１３から出力された選択ノード情報を受け付ける。そして、決定部１４は、受け付けた選択ノード情報が示すノードを始点ノードとし、取得したトポロジ情報を参照して、その始点ノードから未決定終点ノードまでの最短経路を決定する。具体的には、決定部１４は、例えば上述したダイクストラ法を用いてコスト値を計算することによって最短経路を決定する。また、決定部１４は、決定した最短経路上の始点ノード以外のノードから、その最短経路を介してその最短経路の終点ノードまで至る経路を、そのノードからその終点ノードまでの最短経路として決定する。そして、決定部１４は、決定した最短経路に基づき、記憶部１２に記憶された最短経路決定表を更新する。
【００４５】
以下に、上記のように構成された経路決定装置が最短経路を決定する動作について説明する。
【００４６】
図４は、図２および図３に示した経路決定装置１０が最短経路を決定する動作を説明するためのフローチャートである。
【００４７】
まず、選択部１３は、記憶部１２に記憶された最短経路決定表を参照する。
【００４８】
そして、選択部１３は、トポロジ情報が示す通信ネットワークを構成する複数のノードのうち、未決定終点ノードが存在するノードがあるかどうかを判定する（ステップＳ１）。
【００４９】
ステップＳ１における判定の結果、未決定終点ノードが存在するノードがない場合、処理を終了する。
【００５０】
一方、ステップＳ１における判定の結果、未決定終点ノードが存在するノードがある場合には、選択部１３は、未決定終点ノードが存在するノードの１つを始点ノードとして選択する（ステップＳ２）。なお、始点ノードとして選択されたノードは決定部１４において、決定済みの最短経路の終点ノードとして認識される。
【００５１】
そして、選択部１３は、始点ノードとして選択したノードを示す選択ノード情報を決定部１４へ出力する。
【００５２】
選択部１３から出力された選択ノード情報を受け付けた決定部１４は、トポロジ情報を参照して、決定済みの最短経路の終点ノードに隣接し、かつ、受け付けた選択ノード情報が示す始点ノードからの最短経路が未決定のノードがあるかどうかを判定する（ステップＳ３）。
【００５３】
ステップＳ３における判定の結果、決定済みの最短経路の終点ノードに隣接し、かつ、受け付けた選択ノード情報が示す始点ノードからの最短経路が未決定のノードがある場合、決定部１４は、始点ノードからそのノードまでの通信経路を最短経路候補とする。
【００５４】
そして、決定部１４は、最短経路候補のコスト値を算出する計算を行い、算出されたコスト値が最小の最短経路候補を最短経路として決定する（ステップＳ４）。
【００５５】
次に、決定部１４は、ステップＳ４において決定した最短経路上の始点ノード以外のノードから、その最短経路を介してその最短経路の終点ノードまで至る通信経路を、そのノードからその終点ノードまでの最短経路として決定する（ステップＳ５）。
【００５６】
そして、決定部１４は、ステップＳ４およびステップＳ５において決定した最短経路に基づき、記憶部１２に記憶された最短経路決定表を更新し（ステップＳ６）、ステップＳ３の動作へ遷移する。
【００５７】
一方、ステップＳ３における判定の結果、決定済みの最短経路の終点ノードに隣接し、かつ、受け付けた選択ノード情報が示す始点ノードからの最短経路が未決定のノードがない場合には、ステップＳ１の動作へ遷移する。
【００５８】
図５は、図２および図３に示した経路決定装置１０が最短経路を決定する動作の具体例を説明するための図であり、（ａ）はトポロジ情報部１１に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は最短経路決定表の状態の推移の一例を示す図である。なお、図５（ａ）においては、ノードａ〜ｇが黒丸で表されている。
【００５９】
まず、上述したステップＳ１の動作に従い、選択部１３は、図５（ａ）に示す通信ネットワークを構成するノードａ〜ｇのうち、未決定終点ノードが存在するノードがあるかどうかを判定する。ここでは、ノードａ〜ｇを始点ノードとした場合の未決定終点ノードが存在するものとする。
【００６０】
従って、上述したステップＳ２の動作に従い、選択部１３は、ノードａ〜ｇのうちの１つを始点ノードとして選択する。ここでは、選択部１３は、ノードａを始点ノードとして選択するものとする。これにより、ノードａは決定部１４において、決定済みの最短経路の終点ノードとして認識される。
【００６１】
次に、上述したステップＳ３の動作に従い、決定部１４は、決定済みの最短経路の終点ノードに隣接し、始点ノードからの最短経路が未決定のノードがあるかどうかを判定する。ここでは、決定済みの最短経路の終点ノードはノードａである。また、始点ノードはノードａである。図５（ａ）に示した通信ネットワークにおいてノードａに隣接するノードは、ノードｂおよびノードｅである。また、ここでは、ノードａからの最短経路が決定しているノードはないものとする。従って、＜ノードａ→ノードｂ＞および＜ノードａ→ノードｅ＞の２つが最短経路候補となる。
【００６２】
次に、決定部１４は、＜ノードａ→ノードｂ＞および＜ノードａ→ノードｅ＞のコスト値を算出する計算を行う。ここでは、＜ノードａ→ノードｂ＞のコスト値の方が＜ノードａ→ノードｅ＞のコスト値よりも小さいものとする。そのため、決定部１４は、上述したステップＳ４の動作に従い、＜ノードａ→ノードｂ＞をノードａからノードｂまでの最短経路として決定する。
【００６３】
次に、決定部１４は、上述したステップＳ５に従って動作するが、ここでは、ステップＳ４において決定された最短経路上の始点ノード以外のノードと、その最短経路の終点ノードとがともにノードｂである。そのため、ここでは上述したステップＳ５の動作は実行されない。
【００６４】
そして、決定部１４は、上述したステップＳ６の動作に従い、決定された最短経路に基づいて最短経路決定表を更新する。この更新後の最短経路決定表が図５（ｂ）の上段に示されている。
【００６５】
次に、上述したステップＳ３の動作へ遷移し、決定部１４は、決定済みの最短経路の終点ノードに隣接し、始点ノードからの最短経路が未決定のノードがあるかどうかを判定する。ここでは、決定済みの最短経路の終点ノードはノードａおよびノードｂである。また、始点ノードはノードａである。図５（ａ）に示した通信ネットワークにおいて、ノードａに隣接するノードはノードｂおよびノードｅであり、ノードｂに隣接するノードはノードｃおよびノードｇである。ここで、＜ノードａ→ノードｂ＞は最短経路として決定済みである。従って、＜ノードａ→ノードｂ→ノードｃ＞と、＜ノードａ→ノードｂ→ノードｇ＞と、＜ノードａ→ノードｅ＞との３つの通信経路が最短経路候補となる。
【００６６】
次に、決定部１４は、＜ノードａ→ノードｂ→ノードｃ＞と、＜ノードａ→ノードｂ→ノードｇ＞と、＜ノードａ→ノードｅ＞とのコスト値を算出する計算を行う。ここでは、＜ノードａ→ノードｂ→ノードｃ＞のコスト値が＜ノードａ→ノードｂ→ノードｇ＞および＜ノードａ→ノードｅ＞のコスト値よりも小さいものとする。そのため、決定部１４は、上述したステップＳ４の動作に従い、＜ノードａ→ノードｂ→ノードｃ＞をノードａからノードｃまでの最短経路として決定する。
【００６７】
また、決定部１４は、上述したステップＳ５の動作に従い、ステップＳ４において決定した最短経路上の始点ノード以外のノードから、その最短経路を介してその最短経路の終点ノードまで至る通信経路を、そのノードからその終点ノードまでの最短経路として決定する。ここでは、上述したステップＳ４において決定された最短経路は、＜ノードａ→ノードｂ→ノードｃ＞である。従って、始点ノード（ノードａ）以外のノードは、ノードｂであり、終点ノードはノードｃである。従って、決定部１４は、＜ノードｂ→ノードｃ＞をノードｂからノードｃまでの最短経路として決定する。
【００６８】
そして、決定部１４は、上述したステップＳ６の動作に従い、決定された最短経路に基づいて最短経路決定表を更新する。この更新後の最短経路決定表が図５（ｂ）の中段に示されている。
【００６９】
以降、同様の動作を繰り返すことにより、決定部１４が、上述したステップＳ４の動作に従い、＜ノードａ→ノードｂ→ノードｃ→ノードｄ＞をノードａからノードｄまでの最短経路として決定したとする。
【００７０】
この場合、決定された最短経路上の始点ノード（ノードａ）以外のノードは、ノードｂおよびノードｃであり、終点ノードはノードｄである。従って、決定部１４は、上述したステップＳ５の動作に従い、＜ノードｂ→ノードｃ→ノードｄ＞をノードｂからノードｄまでの最短経路として決定し、＜ノードｃ→ノードｄ＞をノードｃからノードｄまでの最短経路として決定する。
【００７１】
そして、決定部１４は、上述したステップＳ６の動作に従い、決定された最短経路に基づいて最短経路決定表を更新する。この更新後の最短経路決定表が図５（ｂ）の下段に示されている。
【００７２】
このように本実施形態において経路決定装置１０は、通信ネットワークを構成する複数のノードのうち、当該ノードからの最短経路が決定していない未決定終点ノードが存在するノードの１つを始点ノードとして選択する。そして、経路決定装置１０は、始点ノードから未決定終点ノードまでの最短経路を決定する。
【００７３】
また、経路決定装置１０は、決定された最短経路上の始点ノード以外のノードから、当該最短経路を介して当該最短経路の終点ノードまで至る通信経路を、当該ノードから当該終点ノードまでの最短経路として決定する。
【００７４】
これにより、２番目以降に始点ノードとして選択されるノードからの最短経路の一部は、それ以前に始点ノードとして選択されたノードからの最短経路が決定するとともに決定していることになる。
【００７５】
そのため、同じ経路について複数回のコスト値の計算が行われることがなくなり、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避することができる。
【００７６】
ここで、上述した方法では、複数のノードのそれぞれを始点ノードとして選択する順番によっては、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避できるという効果が十分に得られない場合があり得る。
【００７７】
図６は、図２および図３に示した経路決定装置１０が最短経路を決定する動作の他の具体例を説明するための図であり、（ａ）はトポロジ情報部１１に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は最短経路決定表の状態の推移の一例を示す図である。なお、図６（ａ）においては、ノードａ〜ｇおよびノードｘ〜ｚが黒丸で表されている。
【００７８】
ここでは、ノードａ〜ｇおよびノードｘ〜ｚを始点ノードとした場合の未決定終点ノードが存在するものとする。そして、ノードｘが始点ノードとして最初に選択された場合を考えてみる。
【００７９】
この場合、＜ノードｘ→ノードｂ→ノードｃ＞がノードｘからノードｃまでの最短経路として決定したとすると、これに伴って、＜ノードｂ→ノードｃ＞がノードｂからノードｃまでの最短経路として決定することになる。また、＜ノードｘ→ノードｂ→ノードｃ→ノードｄ＞がノードｘからノードｄまでの最短経路として決定したとすると、これに伴って、＜ノードｂ→ノードｃ→ノードｄ＞がノードｂからノードｄまでの最短経路として決定することになる。また、＜ノードｃ→ノードｄ＞がノードｃからノードｄまでの最短経路として決定することになる。ここまでに決定した最短経路に基づいて更新された最短経路決定表が図６（ｂ）の上段に示されている。
【００８０】
この後にノードａが始点ノードとして選択され、＜ノードａ→ノードｂ→ノードｃ＞がノードａからノードｃまでの最短経路として決定したとする。これに伴って、＜ノードｂ→ノードｃ＞がノードｂからノードｃまでの最短経路として決定されるはずである。しかし、ノードｂからノードｃまでの最短経路は図６（ｂ）の上段に示すように、ノードｘを始点ノードとして最短経路を決定したときに既に決定済みとなっている。
【００８１】
同様に、＜ノードａ→ノードｂ→ノードｃ→ノードｄ＞がノードａからノードｄまでの最短経路として決定したとする。これに伴って、＜ノードｂ→ノードｃ→ノードｄ＞がノードｂからノードｄまでの最短経路として決定され、＜ノードｃ→ノードｄ＞がノードｃからノードｄまでの最短経路として決定されるはずである。しかし、ノードｂからノードｄまでの最短経路およびノードｃからノードｄまでの最短経路は図６（ｂ）の上段に示すように、やはり、ノードｘを始点ノードとして最短経路を決定したときに既に決定済みとなっている。
【００８２】
このように、複数のノードのそれぞれを始点ノードとして選択する順番によっては、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避できるという効果が十分に得られない場合があり得る。
【００８３】
従って、全体の計算量ができるだけ少なくなるように、複数のノードのそれぞれを始点ノードとして選択する順番を決定する必要がある。
【００８４】
この順番は、通信ネットワークの構成や、直前に行った計算結果等、始点ノードを選択する時点で知りえる情報、またはその情報を基に算出される情報に基づいて行うようにすればよい。
【００８５】
図７は、図２に示した選択部１３が始点ノードを選択する際の動作の一例を説明するための図であり、最短経路決定表を示している。
【００８６】
図７に示す最短経路決定表は、ノードａを始点ノードとして選択して最短経路を決定した結果、ノードｂおよびノードｃを始点ノードとした場合の最短経路の一部も決定済みとなった状態を示している。
【００８７】
この状態から、次に始点ノードとして選択するノードを決定する際、選択部１３は、未決定終点ノードが存在するノードｂ〜ｄのうち、未決定終点ノードの数が最も多いノードを始点ノードとして選択する。図７に示す例において未決定終点ノードの数は、ノードｂが１個、ノードｃが２個、ノードｄが３個である。そのため、選択部１３は、ノードｄを始点ノードとして選択する。
【００８８】
あるノードについて未決定終点ノードの数が多いということは、最短経路を決定するためにコスト値の計算が行われた通信経路のうち、そのノードを通過する通信経路の数が少ないということである。そのため、未決定終点ノードの数がより多いノードを優先的に始点ノードとして選択すれば、そのノードからの最短経路を決定するために行われた計算が、他のノードからの最短経路を決定する際に既に行われている確率が低くなる。従って、未決定終点ノードの数がより多いノードを優先的に始点ノードとして選択すれば、そのノードからの最短経路を、より多くの他のノードからの最短経路として利用することができる。
【００８９】
また、複数のノードのそれぞれを始点ノードとして選択する順番を決定する他の方法として、複数のノードのそれぞれを接続するリンクのメトリック値を利用する方法がある。なお、メトリック値とは、２つのノード間の仮想的な距離を表すパラメータである。
【００９０】
この場合、選択部１３は、未決定終点ノードが存在するノードのうち、そのノードと接続されているリンクのメトリック値の平均値が最も大きなノードを、始点ノードとして選択する。
【００９１】
最短経路を決定する際には、リンクのメトリック値がより小さいほど、そのリンクを介した通信経路の距離がより短いものとして認識され、あるノードに接続されているリンクのメトリック値の平均値が大きいと、そのノードを通過する最短経路の数は少なくなる。そのため、接続されているリンクのメトリック値の平均値がより大きなノードを優先的に始点ノードとして選択すれば、そのノードからの最短経路を決定するために行われた計算が、他のノードからの最短経路を決定する際に既に行われている確率が低くなる。つまり、接続されているリンクのメトリック値の平均値がより大きなノードを優先的に始点ノードとして選択すれば、そのノードからの最短経路を、より多くの他のノードからの最短経路として利用することができる。
【００９２】
図８は、図２に示した選択部１３が始点ノードを選択する際の動作の他の例を説明するための図であり、（ａ）はトポロジ情報部１１に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は複数のノード毎のメトリック値を示す図である。
【００９３】
図８（ａ）においては、ノードＡ〜Ｆのそれぞれが四角形で表され、リンクが直線で表されている。そして、各リンクの近傍の数値が各リンクのメトリック値を示している。なお、ここでは、各リンクの上り下りの方向に関わらずメトリック値は同じものとする。
【００９４】
図８に示す例の場合、選択部１３は、ノードＡ〜Ｆのそれぞれに接続されたリンクのメトリック値の平均値をノードＡ〜Ｆ毎に算出する。これが図８（ｂ）に示されている。
【００９５】
そして、選択部１３は、メトリック値の平均値がより大きなノードから順番に始点ノードとして選択していく。従って、図８に示した例において、始点ノードとして最初に選択されるのは、メトリック値の平均値が最も大きなノードＤとなる。そして、ノードＤの次に始点ノードとして選択されるのは、メトリック値の平均値がノードＤの次に大きなノードＦとなる。
【００９６】
このように、経路決定装置１０は、未決定終点ノードの数に応じた順番や、複数のノードのそれぞれが接続されているリンクのメトリック値に応じた順番で、始点ノードとして選択するノードを決定する。これにより、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避できるという効果を十分に得ることができる。
【符号の説明】
【００９７】
１０ 経路決定装置
１１ トポロジ情報部
１２ 記憶部
１３ 選択部
１４ 決定部
【技術分野】
【０００１】
本発明は、複数のノードから構成される通信ネットワークにおける２つのノード間の最短経路を決定する経路決定方法および経路決定装置に関する。
【背景技術】
【０００２】
複数のノードから構成される通信ネットワークにおいては、その複数のノードのいずれかである始点ノードから、その複数のノードのうちの始点ノード以外のノードである終点ノードまでの通信経路が複数ある。そのため、その複数の通信経路のうち、最も効率的な通信経路である最短経路を決定する必要がある。
【０００３】
そこで、複数のノードのそれぞれを接続するリンクにコスト値と呼ばれる重み値を設定する。そして、始点ノードから終点ノードまでの複数の通信経路のそれぞれのコスト値を計算することにより、コスト値が最小となる通信経路を最短経路として決定するのが一般的である。
【０００４】
上述したような計算によって最短経路を決定するためのアルゴリズムの１つであるダイクストラ法が例えば、非特許文献１に開示されている。
【０００５】
図９は、ダイクストラ法を用いて最短経路を決定する動作を説明するためのフローチャートである。
【０００６】
まず、通信ネットワークを構成する複数のノードのうち始点ノードとして選択されていないノードがあるかどうかが判定される（ステップＳ１０１）。
【０００７】
ステップＳ１０１における判定の結果、始点ノードとして選択されていないノードがない場合、処理が終了する。
【０００８】
一方、ステップＳ１０１における判定の結果、始点ノードとして選択されていないノードがある場合には、始点ノードとして選択されていないノードの１つが始点ノードとして選択される（ステップＳ１０２）。なお、始点ノードとして選択されたノードは、決定済みの最短経路の終点ノードとして認識される。
【０００９】
次に、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードがあるかどうかが判定される（ステップＳ１０３）。なお、「終点ノードに隣接するノード」とは終点ノードとリンクによって直接接続されたノードのことであり、終点ノードとそのノードとの間には他のノードが存在しない。これは、以降の説明においていも同様である。
【００１０】
ステップＳ１０３における判定の結果、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードがある場合、始点ノードからそのノードまでの通信経路が最短経路候補とされる。
【００１１】
そして、最短経路候補のコスト値を算出する計算が行われ、算出されたコスト値が最小となる最短経路候補が最短経路として決定される（ステップＳ１０４）。そして、ステップＳ１０３の動作へ遷移する。
【００１２】
一方、ステップＳ１０３における判定の結果、決定済みの最短経路の終点ノードに隣接し、かつ、始点ノードからの最短経路が未決定のノードがない場合には、ステップＳ１０１の動作へ遷移する。
【００１３】
図１０は、図９に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図、（ｂ）は最短経路が決定していく推移の一例を示す図である。なお、図１０（ａ）においては、ノードａ〜ｇが黒丸で表されている。また、以降、通信経路を＜ノードａ→ノードｂ＞のように＜ ＞を用いて表記する。
【００１４】
まず、上述したステップＳ１０１の動作に従い、図１０（ａ）に示す通信ネットワークを構成するノードａ〜ｇのうち始点ノードとして選択されていないノードがあるかどうかが判定される。ここでは、ノードａ〜ｇが始点ノードとして選択されていないものとする。
【００１５】
従って、上述したステップＳ１０２の動作に従い、ノードａ〜ｇのうちの１つを始点ノードとして選択する。ここでは、ノードａが始点ノードとして選択されるものとする。これにより、ノードａは決定済みの最短経路の終点ノードとして認識される。
【００１６】
次に、上述したステップＳ１０３の動作に従い、決定済みの最短経路の終点ノードに隣接し、始点ノードからの最短経路が未決定のノードがあるかどうかが判定される。ここでは、決定済みの最短経路の終点ノードはノードａである。また、始点ノードはノードａである。図１０（ａ）に示した通信ネットワークにおいてノードａに隣接するノードは、ノードｂおよびノードｅである。また、ここでは、ノードａからの最短経路が決定しているノードはない。従って、＜ノードａ→ノードｂ＞および＜ノードａ→ノードｅ＞の２つが最短経路候補となる。
【００１７】
次に、＜ノードａ→ノードｂ＞および＜ノードａ→ノードｅ＞のコスト値を算出する計算が行われる。ここでは、＜ノードａ→ノードｂ＞のコスト値の方が＜ノードａ→ノードｅ＞のコスト値よりも小さいものとする。そのため、上述したステップＳ１０４の動作に従い、＜ノードａ→ノードｂ＞がノードａからノードｂまでの最短経路として決定される。ここまでに決定した最短経路が図１０（ｂ）の上段に示されている。
【００１８】
次に、上述したステップＳ１０３の動作へ遷移し、決定済みの最短経路の終点ノードに隣接し、始点ノードからの最短経路が未決定のノードがあるかどうかが判定される。ここでは、決定済みの最短経路の終点ノードはノードａおよびノードｂである。また、始点ノードはノードａである。図１０（ａ）に示した通信ネットワークにおいて、ノードａに隣接するノードはノードｂおよびノードｅであり、ノードｂに隣接するノードはノードｃおよびノードｇである。ここで、＜ノードａ→ノードｂ＞は最短経路として決定済みである。従って、＜ノードａ→ノードｂ→ノードｃ＞と、＜ノードａ→ノードｂ→ノードｇ＞と、＜ノードａ→ノードｅ＞との３つの通信経路が最短経路候補となる。
【００１９】
次に、＜ノードａ→ノードｂ→ノードｃ＞と、＜ノードａ→ノードｂ→ノードｇ＞と、＜ノードａ→ノードｅ＞とのコスト値を算出する計算が行われる。ここでは、＜ノードａ→ノードｂ→ノードｃ＞のコスト値が＜ノードａ→ノードｂ→ノードｇ＞および＜ノードａ→ノードｅ＞のコスト値よりも小さいものとする。そのため、上述したステップＳ１０４の動作に従い、＜ノードａ→ノードｂ→ノードｃ＞がノードａからノードｃまでの最短経路として決定される。ここまでに決定した最短経路が図１０（ｂ）の中段に示されている。
【００２０】
以降、同様の動作を繰り返すことにより、上述したステップＳ１０４の動作に従い、＜ノードａ→ノードｂ→ノードｃ→ノードｄ＞がノードａからノードｄまでの最短経路として決定されたものとする。ここまでに決定された最短経路が図１０（ｂ）の下段に示されている。
【００２１】
このように、通信ネットワークを構成する複数のノードのうちの１つを始点ノードとして選択し、始点ノードとして選択されたノードからの最短経路が順次決定していく。その始点ノードからの最短経路が全て決定した後、始点ノードとして選択されていないノードの１つが始点ノードとして選択され、始点ノードとして選択されたノードからの最短経路が順次決定していくことになる。つまり、ダイクストラ法を用いた場合、図１０（ｂ）に示したような表の行毎に最短経路が順次決定していくことになる。
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs".Numerische Mathematik 1:269-271(http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf. )
【発明の概要】
【発明が解決しようとする課題】
【００２３】
上述したダイクストラ法のようなアルゴリズムは、ある１つのノードから他のノードへの最短経路を決定するためのアルゴリズムである。そのため、最短経路を決定するためのコスト値の計算を複数のノード毎に行うことになる。
【００２４】
この場合、同じ通信経路についてコスト値の計算が複数回行われることになる。つまり、不必要な計算を行うことによって最短経路を決定するまでの時間が必要以上に長くなってしまうという問題点がある。
【００２５】
本発明は、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避することができる経路決定方法および経路決定装置を提供することを目的とする。
【課題を解決するための手段】
【００２６】
上記目的を達成するために本発明の経路決定方法は、通信ネットワークを構成する複数のノードのそれぞれから、前記複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定方法であって、
前記複数のノードのうち、当該ノードからの最短経路が決定していない未決定終点ノードが存在するノードの１つを始点ノードとして選択する選択処理と、
前記始点ノードから前記未決定終点ノードまでの最短経路を決定する処理と、
前記決定された最短経路上の始点ノード以外のノードから、当該最短経路を介して当該最短経路の終点ノードまで至る通信経路を、当該ノードから当該終点ノードまでの最短経路として決定する処理と、を有する。
【００２７】
また、上記目的を達成するために本発明の経路決定装置は、通信ネットワークを構成する複数のノードのそれぞれから、前記複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置であって、上記の経路決定方法における処理を実行する。
【発明の効果】
【００２８】
本発明は以上説明したように構成されているので、２番目以降に始点ノードとして選択されるノードからの最短経路の一部は、それ以前に始点ノードとして選択されたノードからの最短経路が決定するとともに決定していることになる。
【００２９】
そのため、同じ通信経路について複数回のコスト値の計算が行われることがなくなり、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避することができる。
【図面の簡単な説明】
【００３０】
【図１】通信ネットワークの一例を示す図である。
【図２】本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【図３】図２に示した記憶部が備える最短経路決定表の一例を示す図である。
【図４】図２および図３に示した経路決定装置が最短経路を決定する動作を説明するためのフローチャートである。
【図５】図２および図３に示した経路決定装置が最短経路を決定する動作の具体例を説明するための図であり、（ａ）はトポロジ情報部に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は最短経路決定表の状態の推移の一例を示す図である。
【図６】図２および図３に示した経路決定装置が最短経路を決定する動作の他の具体例を説明するための図であり、（ａ）はトポロジ情報部に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は最短経路決定表の状態の推移の一例を示す図である。
【図７】図２に示した選択部が始点ノードを選択する際の動作の一例を説明するための図である。
【図８】図２に示した選択部が始点ノードを選択する際の動作の他の例を説明するための図であり、（ａ）はトポロジ情報部に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は複数のノード毎のメトリック値を示す図である。
【図９】ダイクストラ法を用いて最短経路を決定する動作を説明するためのフローチャートである。
【図１０】図９に示したフローチャートに従って最短経路を決定する動作の具体例を説明するための図であり、（ａ）は通信ネットワークの一例を示す図、（ｂ）は最短経路が決定していく推移の一例を示す図である。
【発明を実施するための形態】
【００３１】
以下に、本発明の実施の形態について図面を参照して説明する。
【００３２】
本発明では、ある２つのノード間の最短経路の一部が、その最短経路上の２つのノード間の最短経路となることを用いて最短経路を決定していく。
【００３３】
図１は、通信ネットワークの一例を示す図である。なお、図１においては、ノードａ〜ｆが黒丸で表されている。
【００３４】
ここでは、図１に示す通信ネットワークにおいて、ノードａからノードｄまでの最短経路が＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞であるならば、ノードｂからノードｃへの最短経路は、＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞の一部である＜ノードｂ→ノードｅ→ノードｃ＞であることを証明する。
【００３５】
まず、以下に示す（１）（２）を仮定する。
（１）ノードａからノードｄまでの最短経路は＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞である
（２）ノードｂからノードｃまでの最短経路は＜ノードｂ→ノードｆ→ノードｃ＞である
ここで、上記の（２）が正しいとすると、ノードａからノードｄまでの最短経路は＜ノードａ→ノードｂ→ノードｆ→ノードｃ→ノードｄとなり、上記の（１）と（２）とは矛盾する。従って、ノードａからノードｄまでの最短経路が＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞であれば、ノードｂからノードｃまでの最短経路は＜ノードａ→ノードｂ→ノードｅ→ノードｃ→ノードｄ＞の一部である＜ノードｂ→ノードｅ→ノードｃ＞となる。
【００３６】
このように、ある２つのノード間の最短経路の一部は、その最短経路上の２つのノード間の最短経路となる。本発明においては、ある２つのノード間の最短経路が決定したとき、その最短経路上の始点ノード以外のノードから、その最短経路を介してその最短経路の終点ノードへ至る通信経路も最短経路として決定する。
【００３７】
図２は、本発明の経路決定装置の実施の一形態の構成を示すブロック図である。
【００３８】
図２に示す経路決定装置１０は、トポロジ情報部１１と、記憶部１２、選択部１３と、決定部１４とを備えている。
【００３９】
トポロジ情報部１１は、通信ネットワークを示すトポロジ情報を記憶する。なお、トポロジ情報には、通信ネットワークを構成する複数のノードと、その複数のノードのそれぞれの接続状態とが含まれている。
【００４０】
記憶部１２は、トポロジ情報部１１が記憶するトポロジ情報が示す通信ネットワークを構成する複数のノードのそれぞれを始点ノードとし、その始点ノードから終点ノードまでの最短経路が決定されているかどうかを示す最短経路決定表を備えている。
【００４１】
図３は、図２に示した記憶部１２が備える最短経路決定表の一例を示す図である。
【００４２】
最短経路決定表は図３に示すように、列方向を始点ノードとし、行方向を終点ノードとしている。図３に示す例では、ノードａを始点ノードとした場合の最短経路の全てが決定されている状態を示している。
【００４３】
再度図２を参照すると、選択部１３は、記憶部１２に記憶された最短経路決定表を参照する。そして、選択部１３は、トポロジ情報が示す通信ネットワークを構成する複数のノードのうち、そのノードを始点ノードとした場合の最短経路が決定していない終点ノードである未決定終点ノードが存在するノードがあるかどうかを判定する。その判定の結果、未決定終点ノードが存在するノードがある場合、選択部１３は、未決定終点ノードが存在するノードの１つを始点ノードとして選択する。例えば、最短経路決定表が図３に示した状態である場合、選択部１３は、ノードｂ〜ｄうちの１つを始点ノードとして選択することになる。そして、選択部１３は、始点ノードとして選択したノードを示す選択ノード情報を決定部１４へ出力する。
【００４４】
決定部１４は、トポロジ情報部１１に記憶されたトポロジ情報を取得する。また、決定部１４は、選択部１３から出力された選択ノード情報を受け付ける。そして、決定部１４は、受け付けた選択ノード情報が示すノードを始点ノードとし、取得したトポロジ情報を参照して、その始点ノードから未決定終点ノードまでの最短経路を決定する。具体的には、決定部１４は、例えば上述したダイクストラ法を用いてコスト値を計算することによって最短経路を決定する。また、決定部１４は、決定した最短経路上の始点ノード以外のノードから、その最短経路を介してその最短経路の終点ノードまで至る経路を、そのノードからその終点ノードまでの最短経路として決定する。そして、決定部１４は、決定した最短経路に基づき、記憶部１２に記憶された最短経路決定表を更新する。
【００４５】
以下に、上記のように構成された経路決定装置が最短経路を決定する動作について説明する。
【００４６】
図４は、図２および図３に示した経路決定装置１０が最短経路を決定する動作を説明するためのフローチャートである。
【００４７】
まず、選択部１３は、記憶部１２に記憶された最短経路決定表を参照する。
【００４８】
そして、選択部１３は、トポロジ情報が示す通信ネットワークを構成する複数のノードのうち、未決定終点ノードが存在するノードがあるかどうかを判定する（ステップＳ１）。
【００４９】
ステップＳ１における判定の結果、未決定終点ノードが存在するノードがない場合、処理を終了する。
【００５０】
一方、ステップＳ１における判定の結果、未決定終点ノードが存在するノードがある場合には、選択部１３は、未決定終点ノードが存在するノードの１つを始点ノードとして選択する（ステップＳ２）。なお、始点ノードとして選択されたノードは決定部１４において、決定済みの最短経路の終点ノードとして認識される。
【００５１】
そして、選択部１３は、始点ノードとして選択したノードを示す選択ノード情報を決定部１４へ出力する。
【００５２】
選択部１３から出力された選択ノード情報を受け付けた決定部１４は、トポロジ情報を参照して、決定済みの最短経路の終点ノードに隣接し、かつ、受け付けた選択ノード情報が示す始点ノードからの最短経路が未決定のノードがあるかどうかを判定する（ステップＳ３）。
【００５３】
ステップＳ３における判定の結果、決定済みの最短経路の終点ノードに隣接し、かつ、受け付けた選択ノード情報が示す始点ノードからの最短経路が未決定のノードがある場合、決定部１４は、始点ノードからそのノードまでの通信経路を最短経路候補とする。
【００５４】
そして、決定部１４は、最短経路候補のコスト値を算出する計算を行い、算出されたコスト値が最小の最短経路候補を最短経路として決定する（ステップＳ４）。
【００５５】
次に、決定部１４は、ステップＳ４において決定した最短経路上の始点ノード以外のノードから、その最短経路を介してその最短経路の終点ノードまで至る通信経路を、そのノードからその終点ノードまでの最短経路として決定する（ステップＳ５）。
【００５６】
そして、決定部１４は、ステップＳ４およびステップＳ５において決定した最短経路に基づき、記憶部１２に記憶された最短経路決定表を更新し（ステップＳ６）、ステップＳ３の動作へ遷移する。
【００５７】
一方、ステップＳ３における判定の結果、決定済みの最短経路の終点ノードに隣接し、かつ、受け付けた選択ノード情報が示す始点ノードからの最短経路が未決定のノードがない場合には、ステップＳ１の動作へ遷移する。
【００５８】
図５は、図２および図３に示した経路決定装置１０が最短経路を決定する動作の具体例を説明するための図であり、（ａ）はトポロジ情報部１１に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は最短経路決定表の状態の推移の一例を示す図である。なお、図５（ａ）においては、ノードａ〜ｇが黒丸で表されている。
【００５９】
まず、上述したステップＳ１の動作に従い、選択部１３は、図５（ａ）に示す通信ネットワークを構成するノードａ〜ｇのうち、未決定終点ノードが存在するノードがあるかどうかを判定する。ここでは、ノードａ〜ｇを始点ノードとした場合の未決定終点ノードが存在するものとする。
【００６０】
従って、上述したステップＳ２の動作に従い、選択部１３は、ノードａ〜ｇのうちの１つを始点ノードとして選択する。ここでは、選択部１３は、ノードａを始点ノードとして選択するものとする。これにより、ノードａは決定部１４において、決定済みの最短経路の終点ノードとして認識される。
【００６１】
次に、上述したステップＳ３の動作に従い、決定部１４は、決定済みの最短経路の終点ノードに隣接し、始点ノードからの最短経路が未決定のノードがあるかどうかを判定する。ここでは、決定済みの最短経路の終点ノードはノードａである。また、始点ノードはノードａである。図５（ａ）に示した通信ネットワークにおいてノードａに隣接するノードは、ノードｂおよびノードｅである。また、ここでは、ノードａからの最短経路が決定しているノードはないものとする。従って、＜ノードａ→ノードｂ＞および＜ノードａ→ノードｅ＞の２つが最短経路候補となる。
【００６２】
次に、決定部１４は、＜ノードａ→ノードｂ＞および＜ノードａ→ノードｅ＞のコスト値を算出する計算を行う。ここでは、＜ノードａ→ノードｂ＞のコスト値の方が＜ノードａ→ノードｅ＞のコスト値よりも小さいものとする。そのため、決定部１４は、上述したステップＳ４の動作に従い、＜ノードａ→ノードｂ＞をノードａからノードｂまでの最短経路として決定する。
【００６３】
次に、決定部１４は、上述したステップＳ５に従って動作するが、ここでは、ステップＳ４において決定された最短経路上の始点ノード以外のノードと、その最短経路の終点ノードとがともにノードｂである。そのため、ここでは上述したステップＳ５の動作は実行されない。
【００６４】
そして、決定部１４は、上述したステップＳ６の動作に従い、決定された最短経路に基づいて最短経路決定表を更新する。この更新後の最短経路決定表が図５（ｂ）の上段に示されている。
【００６５】
次に、上述したステップＳ３の動作へ遷移し、決定部１４は、決定済みの最短経路の終点ノードに隣接し、始点ノードからの最短経路が未決定のノードがあるかどうかを判定する。ここでは、決定済みの最短経路の終点ノードはノードａおよびノードｂである。また、始点ノードはノードａである。図５（ａ）に示した通信ネットワークにおいて、ノードａに隣接するノードはノードｂおよびノードｅであり、ノードｂに隣接するノードはノードｃおよびノードｇである。ここで、＜ノードａ→ノードｂ＞は最短経路として決定済みである。従って、＜ノードａ→ノードｂ→ノードｃ＞と、＜ノードａ→ノードｂ→ノードｇ＞と、＜ノードａ→ノードｅ＞との３つの通信経路が最短経路候補となる。
【００６６】
次に、決定部１４は、＜ノードａ→ノードｂ→ノードｃ＞と、＜ノードａ→ノードｂ→ノードｇ＞と、＜ノードａ→ノードｅ＞とのコスト値を算出する計算を行う。ここでは、＜ノードａ→ノードｂ→ノードｃ＞のコスト値が＜ノードａ→ノードｂ→ノードｇ＞および＜ノードａ→ノードｅ＞のコスト値よりも小さいものとする。そのため、決定部１４は、上述したステップＳ４の動作に従い、＜ノードａ→ノードｂ→ノードｃ＞をノードａからノードｃまでの最短経路として決定する。
【００６７】
また、決定部１４は、上述したステップＳ５の動作に従い、ステップＳ４において決定した最短経路上の始点ノード以外のノードから、その最短経路を介してその最短経路の終点ノードまで至る通信経路を、そのノードからその終点ノードまでの最短経路として決定する。ここでは、上述したステップＳ４において決定された最短経路は、＜ノードａ→ノードｂ→ノードｃ＞である。従って、始点ノード（ノードａ）以外のノードは、ノードｂであり、終点ノードはノードｃである。従って、決定部１４は、＜ノードｂ→ノードｃ＞をノードｂからノードｃまでの最短経路として決定する。
【００６８】
そして、決定部１４は、上述したステップＳ６の動作に従い、決定された最短経路に基づいて最短経路決定表を更新する。この更新後の最短経路決定表が図５（ｂ）の中段に示されている。
【００６９】
以降、同様の動作を繰り返すことにより、決定部１４が、上述したステップＳ４の動作に従い、＜ノードａ→ノードｂ→ノードｃ→ノードｄ＞をノードａからノードｄまでの最短経路として決定したとする。
【００７０】
この場合、決定された最短経路上の始点ノード（ノードａ）以外のノードは、ノードｂおよびノードｃであり、終点ノードはノードｄである。従って、決定部１４は、上述したステップＳ５の動作に従い、＜ノードｂ→ノードｃ→ノードｄ＞をノードｂからノードｄまでの最短経路として決定し、＜ノードｃ→ノードｄ＞をノードｃからノードｄまでの最短経路として決定する。
【００７１】
そして、決定部１４は、上述したステップＳ６の動作に従い、決定された最短経路に基づいて最短経路決定表を更新する。この更新後の最短経路決定表が図５（ｂ）の下段に示されている。
【００７２】
このように本実施形態において経路決定装置１０は、通信ネットワークを構成する複数のノードのうち、当該ノードからの最短経路が決定していない未決定終点ノードが存在するノードの１つを始点ノードとして選択する。そして、経路決定装置１０は、始点ノードから未決定終点ノードまでの最短経路を決定する。
【００７３】
また、経路決定装置１０は、決定された最短経路上の始点ノード以外のノードから、当該最短経路を介して当該最短経路の終点ノードまで至る通信経路を、当該ノードから当該終点ノードまでの最短経路として決定する。
【００７４】
これにより、２番目以降に始点ノードとして選択されるノードからの最短経路の一部は、それ以前に始点ノードとして選択されたノードからの最短経路が決定するとともに決定していることになる。
【００７５】
そのため、同じ経路について複数回のコスト値の計算が行われることがなくなり、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避することができる。
【００７６】
ここで、上述した方法では、複数のノードのそれぞれを始点ノードとして選択する順番によっては、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避できるという効果が十分に得られない場合があり得る。
【００７７】
図６は、図２および図３に示した経路決定装置１０が最短経路を決定する動作の他の具体例を説明するための図であり、（ａ）はトポロジ情報部１１に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は最短経路決定表の状態の推移の一例を示す図である。なお、図６（ａ）においては、ノードａ〜ｇおよびノードｘ〜ｚが黒丸で表されている。
【００７８】
ここでは、ノードａ〜ｇおよびノードｘ〜ｚを始点ノードとした場合の未決定終点ノードが存在するものとする。そして、ノードｘが始点ノードとして最初に選択された場合を考えてみる。
【００７９】
この場合、＜ノードｘ→ノードｂ→ノードｃ＞がノードｘからノードｃまでの最短経路として決定したとすると、これに伴って、＜ノードｂ→ノードｃ＞がノードｂからノードｃまでの最短経路として決定することになる。また、＜ノードｘ→ノードｂ→ノードｃ→ノードｄ＞がノードｘからノードｄまでの最短経路として決定したとすると、これに伴って、＜ノードｂ→ノードｃ→ノードｄ＞がノードｂからノードｄまでの最短経路として決定することになる。また、＜ノードｃ→ノードｄ＞がノードｃからノードｄまでの最短経路として決定することになる。ここまでに決定した最短経路に基づいて更新された最短経路決定表が図６（ｂ）の上段に示されている。
【００８０】
この後にノードａが始点ノードとして選択され、＜ノードａ→ノードｂ→ノードｃ＞がノードａからノードｃまでの最短経路として決定したとする。これに伴って、＜ノードｂ→ノードｃ＞がノードｂからノードｃまでの最短経路として決定されるはずである。しかし、ノードｂからノードｃまでの最短経路は図６（ｂ）の上段に示すように、ノードｘを始点ノードとして最短経路を決定したときに既に決定済みとなっている。
【００８１】
同様に、＜ノードａ→ノードｂ→ノードｃ→ノードｄ＞がノードａからノードｄまでの最短経路として決定したとする。これに伴って、＜ノードｂ→ノードｃ→ノードｄ＞がノードｂからノードｄまでの最短経路として決定され、＜ノードｃ→ノードｄ＞がノードｃからノードｄまでの最短経路として決定されるはずである。しかし、ノードｂからノードｄまでの最短経路およびノードｃからノードｄまでの最短経路は図６（ｂ）の上段に示すように、やはり、ノードｘを始点ノードとして最短経路を決定したときに既に決定済みとなっている。
【００８２】
このように、複数のノードのそれぞれを始点ノードとして選択する順番によっては、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避できるという効果が十分に得られない場合があり得る。
【００８３】
従って、全体の計算量ができるだけ少なくなるように、複数のノードのそれぞれを始点ノードとして選択する順番を決定する必要がある。
【００８４】
この順番は、通信ネットワークの構成や、直前に行った計算結果等、始点ノードを選択する時点で知りえる情報、またはその情報を基に算出される情報に基づいて行うようにすればよい。
【００８５】
図７は、図２に示した選択部１３が始点ノードを選択する際の動作の一例を説明するための図であり、最短経路決定表を示している。
【００８６】
図７に示す最短経路決定表は、ノードａを始点ノードとして選択して最短経路を決定した結果、ノードｂおよびノードｃを始点ノードとした場合の最短経路の一部も決定済みとなった状態を示している。
【００８７】
この状態から、次に始点ノードとして選択するノードを決定する際、選択部１３は、未決定終点ノードが存在するノードｂ〜ｄのうち、未決定終点ノードの数が最も多いノードを始点ノードとして選択する。図７に示す例において未決定終点ノードの数は、ノードｂが１個、ノードｃが２個、ノードｄが３個である。そのため、選択部１３は、ノードｄを始点ノードとして選択する。
【００８８】
あるノードについて未決定終点ノードの数が多いということは、最短経路を決定するためにコスト値の計算が行われた通信経路のうち、そのノードを通過する通信経路の数が少ないということである。そのため、未決定終点ノードの数がより多いノードを優先的に始点ノードとして選択すれば、そのノードからの最短経路を決定するために行われた計算が、他のノードからの最短経路を決定する際に既に行われている確率が低くなる。従って、未決定終点ノードの数がより多いノードを優先的に始点ノードとして選択すれば、そのノードからの最短経路を、より多くの他のノードからの最短経路として利用することができる。
【００８９】
また、複数のノードのそれぞれを始点ノードとして選択する順番を決定する他の方法として、複数のノードのそれぞれを接続するリンクのメトリック値を利用する方法がある。なお、メトリック値とは、２つのノード間の仮想的な距離を表すパラメータである。
【００９０】
この場合、選択部１３は、未決定終点ノードが存在するノードのうち、そのノードと接続されているリンクのメトリック値の平均値が最も大きなノードを、始点ノードとして選択する。
【００９１】
最短経路を決定する際には、リンクのメトリック値がより小さいほど、そのリンクを介した通信経路の距離がより短いものとして認識され、あるノードに接続されているリンクのメトリック値の平均値が大きいと、そのノードを通過する最短経路の数は少なくなる。そのため、接続されているリンクのメトリック値の平均値がより大きなノードを優先的に始点ノードとして選択すれば、そのノードからの最短経路を決定するために行われた計算が、他のノードからの最短経路を決定する際に既に行われている確率が低くなる。つまり、接続されているリンクのメトリック値の平均値がより大きなノードを優先的に始点ノードとして選択すれば、そのノードからの最短経路を、より多くの他のノードからの最短経路として利用することができる。
【００９２】
図８は、図２に示した選択部１３が始点ノードを選択する際の動作の他の例を説明するための図であり、（ａ）はトポロジ情報部１１に記憶されたトポロジ情報が示す通信ネットワークの一例を示す図、（ｂ）は複数のノード毎のメトリック値を示す図である。
【００９３】
図８（ａ）においては、ノードＡ〜Ｆのそれぞれが四角形で表され、リンクが直線で表されている。そして、各リンクの近傍の数値が各リンクのメトリック値を示している。なお、ここでは、各リンクの上り下りの方向に関わらずメトリック値は同じものとする。
【００９４】
図８に示す例の場合、選択部１３は、ノードＡ〜Ｆのそれぞれに接続されたリンクのメトリック値の平均値をノードＡ〜Ｆ毎に算出する。これが図８（ｂ）に示されている。
【００９５】
そして、選択部１３は、メトリック値の平均値がより大きなノードから順番に始点ノードとして選択していく。従って、図８に示した例において、始点ノードとして最初に選択されるのは、メトリック値の平均値が最も大きなノードＤとなる。そして、ノードＤの次に始点ノードとして選択されるのは、メトリック値の平均値がノードＤの次に大きなノードＦとなる。
【００９６】
このように、経路決定装置１０は、未決定終点ノードの数に応じた順番や、複数のノードのそれぞれが接続されているリンクのメトリック値に応じた順番で、始点ノードとして選択するノードを決定する。これにより、最短経路を決定するまでの時間が必要以上に長くなってしまうのを回避できるという効果を十分に得ることができる。
【符号の説明】
【００９７】
１０ 経路決定装置
１１ トポロジ情報部
１２ 記憶部
１３ 選択部
１４ 決定部
【特許請求の範囲】
【請求項１】
通信ネットワークを構成する複数のノードのそれぞれから、前記複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定方法であって、
前記複数のノードのうち、当該ノードからの最短経路が決定していない未決定終点ノードが存在するノードの１つを始点ノードとして選択する選択処理と、
前記始点ノードから前記未決定終点ノードまでの最短経路を決定する処理と、
前記決定された最短経路上の始点ノード以外のノードから、当該最短経路を介して当該最短経路の終点ノードまで至る通信経路を、当該ノードから当該終点ノードまでの最短経路として決定する処理と、を有する経路決定方法。
【請求項２】
請求項１に記載の経路決定方法において、
前記選択処理においては、前記複数のノードのうち前記始点ノードとして選択するノードを、前記未決定終点ノードの数に応じて決定する経路決定方法。
【請求項３】
請求項１に記載の経路決定方法において、
前記複数のノードのそれぞれは、リンクによって接続され、
前記選択処理においては、前記複数のノードのうち前記始点ノードとして選択するノードを、前記複数のノードのそれぞれが接続されているリンクのメトリック値に応じて決定する経路決定方法。
【請求項４】
通信ネットワークを構成する複数のノードのそれぞれから、前記複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置であって、
請求項１乃至３のいずれか１項に記載の経路決定方法における処理を実行する経路決定装置。
【請求項１】
通信ネットワークを構成する複数のノードのそれぞれから、前記複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定方法であって、
前記複数のノードのうち、当該ノードからの最短経路が決定していない未決定終点ノードが存在するノードの１つを始点ノードとして選択する選択処理と、
前記始点ノードから前記未決定終点ノードまでの最短経路を決定する処理と、
前記決定された最短経路上の始点ノード以外のノードから、当該最短経路を介して当該最短経路の終点ノードまで至る通信経路を、当該ノードから当該終点ノードまでの最短経路として決定する処理と、を有する経路決定方法。
【請求項２】
請求項１に記載の経路決定方法において、
前記選択処理においては、前記複数のノードのうち前記始点ノードとして選択するノードを、前記未決定終点ノードの数に応じて決定する経路決定方法。
【請求項３】
請求項１に記載の経路決定方法において、
前記複数のノードのそれぞれは、リンクによって接続され、
前記選択処理においては、前記複数のノードのうち前記始点ノードとして選択するノードを、前記複数のノードのそれぞれが接続されているリンクのメトリック値に応じて決定する経路決定方法。
【請求項４】
通信ネットワークを構成する複数のノードのそれぞれから、前記複数のノードのうち当該ノード以外のノードである終点ノードまでの最短経路を決定する経路決定装置であって、
請求項１乃至３のいずれか１項に記載の経路決定方法における処理を実行する経路決定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１２−１７５２４６（Ｐ２０１２−１７５２４６Ａ）
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１１−３３１９１（Ｐ２０１１−３３１９１）
【出願日】平成２３年２月１８日（２０１１．２．１８）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、独立行政法人情報通信研究機構「次世代ネットワーク（ＮＧＮ）基盤技術の研究開発」委託事業、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２３年２月１８日（２０１１．２．１８）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、独立行政法人情報通信研究機構「次世代ネットワーク（ＮＧＮ）基盤技術の研究開発」委託事業、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]