(57)【特許請求の範囲】
【請求項１】
コストが付与されたリンクによって複数のノードが互いに接続されて形成されるネットワーク上で、所望の始点ノードから所望の終端ノード（複数可）に至るまでの経路を複数本探索する複数経路探索方法であって、
経路候補作成手段が、前記始点ノードから接続可能な全てのリンクを選択して経路候補を作成し、記憶手段の、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第１の経路候補作成ステップと、
経路候補リスト制御手段が、前記記憶手段内のすべての経路候補リストの中で、経路コストが最小となる１本の経路候補を検索し、該経路候補リストから削除し、該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納する最小コスト経路削除ステップと、
前記経路候補リスト制御手段が、前記検索された経路候補の終端ノードから接続可能な全てのリンクを更に選択し、当該経路候補に選択された各リンクを加えた新たな経路候補を作成し、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第２の経路候補作成ステップと、
必要数判定手段が、所望のすべての終端ノードに対応する経路リストに必要数の経路候補が格納されるまで、前記第１の経路候補作成ステップから前記第２の経路候補作成ステップの処理を続ける繰り返しステップと、
を行う
ことを特徴とする複数経路探索方法。
【請求項２】
前記記憶手段に、各経路候補リストで、すでに最小経路として削除された経路候補数も含めた経路候補数上限を設定し、
前記第1の経路候補作成ステップ及び前記第２の経路候補作成ステップにおいて、
前記経路候補数上限を超えない範囲で、経路候補リスト内に経路候補を格納する経路候補格納判定ステップを含む
請求項１記載の複数経路探索方法。
【請求項３】
前記経路候補格納判定ステップにおいて、
新経路候補を、当該経路候補リストの終端ノード／リンク終端点に対応する経路候補リストに格納するかどうかを決定する際に、当該経路候補リスト内で最小経路として削除された経路候補数が当該経路候補リストの経路候補数上限値に達している場合は、当該新経路候補を当該経路候補リストに格納しない
請求項２記載の複数経路探索方法。
【請求項４】
前記経路候補格納判定ステップにおいて、
新経路候補を、当該経路候補リストの終端ノード／リンク終端点に対応する経路候補リストに格納するかどうかを決定する際に、（１）当該経路候補リスト内で最小経路として削除された経路候補数が当該経路候補リストの経路候補数上限値に達しておらず、且（２）当該経路候補リストで最小経路として削除された経路候補数と経路候補リスト内の経路候補数の合計が経路候補数上限と等しい場合は、当該新経路候補の経路コストが当該経路候補リスト中で最大経路コストを持つ経路候補と比較し、その最大経路コストより新経路候補の経路コストが小さい場合は、最大経路コストを持つ経路候補を当該経路候補リストから削除し、新たに新経路候補を当該経路候補リストに格納する
請求項３記載の複数経路探索方法。
【請求項５】
前記最小コスト経路削除ステップにおいて、
経路候補の経路コストを、経路を構成するリンクのコストの総計とするのではなく、前記始点ノードからの経由するリンク数が大きい経路は経路コストが大きくなるようにリンクコストに比重をつける第１の経路コスト調整ステップを含む
請求項１記載の複数経路探索方法。
【請求項６】
前記経路候補格納判定ステップにおいて、
経路候補の経路コストを、経路を構成するリンクのコストの総計とするのではなく、前記始点ノードからの経由するリンク数が大きい経路は経路コストが大きくなるようにリンクコストに比重をつける第２の経路コスト調整ステップを含む
請求項４記載の複数経路探索方法。
【請求項７】
前記第１の経路コスト調整ステップにおいて、
すべての経路候補リストの中で最小経路コストを持つ経路候補をpath(s,  u)とし、その終端ノードからのリンクをE(u,  v)とし、その経路候補とリンクを繋げて新しくできた経路候補をpath(s,v)とした場合、該path(s,v)の経路コスト|path(s,v)|を、
|path(s,  v)|  =  |path(s,  u)|+|E(u,  v)|  +  β|hop(path(s,  v))|
と定義する（ここで|E(u,  v)|はリンクコスト、|hop(path(s,  v))|はpath(s,  v)が経由するリンク数、βは正数）
請求項５記載の複数経路探索方法。
【請求項８】
前記第２の経路コスト調整ステップにおいて、
すべての経路候補リストの中で最小経路コストを持つ経路候補をpath(s,  u)とし、その終端ノードからのリンクをE(u,  v)とし、その経路候補とリンクを繋げて新しくできた経路候補をpath(s,v)とした場合、該path(s,v)の経路コスト|path(s,v)|を、
|path(s,  v)|  =  |path(s,  u)|+|E(u,  v)|  +  β|hop(path(s,  v))|
と定義する（ここで|E(u,  v)|はリンクコスト、|hop(path(s,  v))|はpath(s,  v)が経由するリンク数、βは正数）
請求項６記載の複数経路探索方法。
【請求項９】
コストが付与されたリンクによって複数のノードが互いに接続されて形成されるネットワーク上で、所望の始点ノードから所望の終端ノード（複数可）に至るまでの経路を複数本探索する複数経路探索装置であって、
経路候補リストを格納する記憶手段と、
前記始点ノードから接続可能な全てのリンクを選択して経路候補を作成し、前記記憶手段の各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第１の経路候補作成手段と、
前記記憶手段のすべての経路候補リストの中で、経路コストが最小となる１本の経路候補を検索し、該経路候補リストから削除し、該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納する最小コスト経路削除手段と、
前記検索された経路候補の終端ノードから接続可能な全てのリンクを更に選択し、当該経路候補に選択された各リンクを加えた新たな経路候補を作成し、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第２の経路候補作成手段と、
必要数判定手段が、所望のすべての終端ノードに対応する経路リストに必要数の経路候補が格納されるまで前記第1の経路候補作成手段、前記最小コスト経路削除手段、前記第2の経路候補作成手段の各処理を繰り返す必要数判定手段と、
を有する
ことを特徴とする複数経路探索装置。
【請求項１０】
コンピュータを、
請求項９に記載の複数経路探索装置の各手段として機能させるための複数経路探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数経路探索方法及び装置に係り、特に、ルータ／ルーティングサーバ等で起点と終点の間に複数のパスを設定し、負荷分散／故障回避をする、または、Video On Demand (VOD)サービス等で、ストリームサーバから複数のエッジルータまでの帯域を確保したマルチパスを設定するための複数経路探索方法及び装置に関する。
【背景技術】
【０００２】
既存の技術を図１を用いて説明する。既存の技術は、所望の１つの始点ノードと１つの終端ノードの間にk本の経路を経路コストが低いものから順に生成するk shortest pathアルゴリズムがある（例えば、非特許文献1参照）。ここでの経路コストとは、経路を構成するすべてのリンクコストの合計である。
【０００３】
ステップ１）ノードの選択を行う（アルゴリズムの最初では、始点ノード、その後は直前のステップ４で選択された経路候補の終端ノードとなる）。
【０００４】
ステップ２）ステップ１で選択されたノードからのリンクを選択する。このとき、複数のリンクを選択してもよい。
【０００５】
ステップ３）ステップ２で選択された各リンクを直前のステップ４で選択された経路候補の後尾につなげることにより、新たな経路候補を作成し、その経路候補の終端ノードに対応する経路候補リストに加える。その際に、同一経路上に同じノードが複数あるループ経路は経路候補とならない。
【０００６】
ステップ４）ネットワーク上のすべての経路候補の中で最も経路コストが小さいものを選択し、その経路候補を含む経路候補リストから削除する。
【０００７】
ステップ５）  選択された経路候補の終端ノードが所望の終端ノードかどうかを判断し、もし所望の終端ノードではない場合はステップ１の処理を行う。もし所望の終端ノードの場合はステップ6に移行する。
【０００８】
ステップ６）経路リストにその経路候補を追加する。
【０００９】
ステップ７）経路リストに経路がk本あるかどうか判断し、k本存在する場合はアルゴリズムの終了となる。k本未満の場合はステップ４の処理を行う。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】信学技報IN2010-107 松浦  洋"計算量最小化を実現するk shortest simple pathアルゴリズム提案" .
【発明の概要】
【発明が解決しようとする課題】
【００１１】
既存のk shortest path アルゴリズムは、始点ノード数、終端ノード数共に１であり、もし複数の終端ノードまでのk 本の経路を求める場合は、終端ノード数回のk shortest pathアルゴリズム走行が必要となる。この場合、処理時間が大きくなる課題がある。
また、k shortest pathアルゴリズムは経路コストが小さい経路から順番にk 本の経路を算出するが、これらの経路がトラフィック分散の観点で最適ではない場合がある。つまり、複数の経路が同一のリンクを使う可能性が高く、そのリンクの利用帯域が大きくなり、結果的にボトルネックとなるリンクを作成してしまう課題がある。
【００１２】
本発明は、上記の点に鑑みなされたもので、複数の経路探索処理時間を短縮でき、k shortest pathアルゴリズムの結果として多く見られる複数経路による始点ノードからの経由数が小さい少数の固定リンクの過剰利用を避けることが可能な複数経路探索方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の課題を解決するため、本発明（請求項１）は、コストが付与されたリンクによって複数のノードが互いに接続されて形成されるネットワーク上で、所望の始点ノードから所望の終端ノード（複数可）に至るまでの経路を複数本探索する複数経路探索方法であって、
経路候補作成手段が、前記始点ノードから接続可能な全てのリンクを選択して経路候補を作成し、記憶手段の、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第１の経路候補作成ステップと、
経路候補リスト制御手段が、前記記憶手段内のすべての経路候補リストの中で、経路コストが最小となる１本の経路候補を検索し、該経路候補リストから削除し、該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納する最小コスト経路削除ステップと、
前記経路候補リスト制御手段が、前記検索された経路候補の終端ノードから接続可能な全てのリンクを更に選択し、当該経路候補に選択された各リンクを加えた新たな経路候補を作成し、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第２の経路候補作成ステップと、
必要数判定手段が、所望のすべての終端ノードに対応する経路リストに必要数の経路候補が格納されるまで、前記第１の経路候補作成ステップから前記第２の経路候補作成ステップの処理を続ける繰り返しステップと、
を行う。
【００１４】
また、本発明（請求項２）は、請求項２において、前記記憶手段に、各経路候補リストで、すでに最小経路として削除された経路候補数も含めた経路候補数上限を設定し、
前記第1の経路候補作成ステップ及び前記第２の経路候補作成ステップにおいて、
前記経路候補数上限を超えない範囲で、経路候補リスト内に経路候補を格納する経路候補格納判定ステップを含む。
【００１５】
また、本発明（請求項３）は、請求項２の前記経路候補格納判定ステップにおいて、
新経路候補を、当該経路候補リストの終端ノード／リンク終端点に対応する経路候補リストに格納するかどうかを決定する際に、当該経路候補リスト内で最小経路として削除された経路候補数が当該経路候補リストの経路候補数上限値に達している場合は、当該新経路候補を当該経路候補リストに格納しない。
【００１６】
また、本発明（請求項４）は、請求項３の前記経路候補格納判定ステップにおいて、
新経路候補を、当該経路候補リストの終端ノード／リンク終端点に対応する経路候補リストに格納するかどうかを決定する際に、（１）当該経路候補リスト内で最小経路として削除された経路候補数が当該経路候補リストの経路候補数上限値に達しておらず、且（２）当該経路候補リストで最小経路として削除された経路候補数と経路候補リスト内の経路候補数の合計が経路候補数上限と等しい場合は、当該新経路候補の経路コストが当該経路候補リスト中で最大経路コストを持つ経路候補と比較し、その最大経路コストより新経路候補の経路コストが小さい場合は、最大経路コストを持つ経路候補を当該経路候補リストから削除し、新たに新経路候補を当該経路候補リストに格納する。
【００１７】
また、本発明（請求項５）は、請求項１の前記最小コスト経路削除ステップにおいて、
経路候補の経路コストを、経路を構成するリンクのコストの総計とするのではなく、前記始点ノードからの経由するリンク数が大きい経路は経路コストが大きくなるようにリンクコストに比重をつける第１の経路コスト調整ステップを含む。
また、本発明（請求項６）は、請求項４の前記経路候補格納判定ステップにおいて、
経路候補の経路コストを、経路を構成するリンクのコストの総計とするのではなく、前記始点ノードからの経由するリンク数が大きい経路は経路コストが大きくなるようにリンクコストに比重をつける第２の経路コスト調整ステップを含む。
【００１８】
また、本発明（請求項７）は、請求項５の前記第１の経路コスト調整ステップにおいて、
すべての経路候補リストの中で最小経路コストを持つ経路候補をpath(s,  u)とし、その終端ノードからのリンクをE(u,  v)とし、その経路候補とリンクを繋げて新しくできた経路候補をpath(s,v)とした場合、該path(s,v)の経路コスト|path(s,v)|を、
|path(s,  v)|  =  |path(s,  u)|+|E(u,  v)|  +  β|hop(path(s,  v))|
と定義する（ここで|E(u,  v)|はリンクコスト、|hop(path(s,  v))|はpath(s,  v)が経由するリンク数、βは正数）。
また、本発明(請求項８)は、請求項６の前記第２の経路コスト調整ステップにおいて、
すべての経路候補リストの中で最小経路コストを持つ経路候補をpath(s,  u)とし、その終端ノードからのリンクをE(u,  v)とし、その経路候補とリンクを繋げて新しくできた経路候補をpath(s,v)とした場合、該path(s,v)の経路コスト|path(s,v)|を、
|path(s,  v)|  =  |path(s,  u)|+|E(u,  v)|  +  β|hop(path(s,  v))|
と定義する（ここで|E(u,  v)|はリンクコスト、|hop(path(s,  v))|はpath(s,  v)が経由するリンク数、βは正数）。
【００１９】
本発明（請求項９）は、コストが付与されたリンクによって複数のノードが互いに接続されて形成されるネットワーク上で、所望の始点ノードから所望の終端ノード（複数可）に至るまでの経路を複数本探索する複数経路探索装置であって、
経路候補リストを格納する記憶手段と、
前記始点ノードから接続可能な全てのリンクを選択して経路候補を作成し、前記記憶手段の各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第１の経路候補作成手段と、
前記記憶手段のすべての経路候補リストの中で、経路コストが最小となる１本の経路候補を検索し、該経路候補リストから削除し、該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納する最小コスト経路削除手段と、
前記検索された経路候補の終端ノードから接続可能な全てのリンクを更に選択し、当該経路候補に選択された各リンクを加えた新たな経路候補を作成し、各リンクの終端ノードあるいは終端点に対応する経路候補リスト内に格納する第２の経路候補作成手段と、
必要数判定手段が、所望のすべての終端ノードに対応する経路リストに必要数の経路候補が格納されるまで前記第1の経路候補作成手段、前記最小コスト経路削除手段、前記第2の経路候補作成手段の各処理を繰り返す必要数判定手段と、
を有する。
【００２０】
本発明（請求項１０）は、コンピュータを、請求項９に記載の複数経路探索装置の各手段として機能させるための複数経路探索プログラムである。
【発明の効果】
【００２１】
上記のように、本発明は、ネットワーク上の全ての経路候補リストの中で、経路コストが最小となる1本の経路候補を検索し、当該経路候補の終端ノードが所望の終端ノードの場合は、当該終端ノードに対応する経路リスト内に当該経路候補を格納し、所望の終端ノードに対応する経路リストに必要数の経路候補が格納されるまで上記の処理を繰り返すことにより、k shortest pathアルゴリズムを終端ノード数回実行する必要がなく、処理時間を短縮することが可能となる。
【図面の簡単な説明】
【００２２】
【図１】従来の複数経路探索アルゴリズムフローである。
【図２】本発明で作成する始点ノードと終端ノードの複数経路探索方法である。
【図３】本発明の一実施の形態におけるPCE内のデータメモリ構造である。
【図４】本発明の一実施の形態における経路候補リストが各リンク終端点に対応する場合のデータメモリ構造である。
【図５】本発明の第1の実施の形態における複数経路探索装置の構成図である。
【図６】本発明の第1の実施の形態における複数経路探索のフローチャートである。
【図７】本発明の第２の実施の形態における経路候補リストのデータ構造と新規経路受付判断を説明するための図である。
【発明を実施するための形態】
【００２３】
以下図面と共に、本発明の実施の形態を説明する。
【００２４】
まず、本発明の概要を説明する。
【００２５】
図２は、本発明で作成する始点ノードと終端ノードの複数経路探索方法のネットワークへの適用例を示す。同図では、複数経路探索装置としてPCE(パスコンピューテーションエレメント）を用いる例である。
【００２６】
複数経路をＰＣＥ（パスコンピューテーションエレメント）１で作成する場合に、同図では、ノード２から７の間で、始点ノード２と終端ノード７の間に複数経路を作成することを想定しているが、終端ノード数は複数でもよい。この例では、ＰＣＥ１で始点ノード２と終端ノード７の間に４本の経路を決定した後で、その経路を各ネットワーク上ノードのスイッチングテーブルに設定することを想定している。
【００２７】
図３は、１０ノードを保持するネットワーク上で、ＰＣＥ１内で保持する始点ノード１１から３つの終端ノード１２、１５、１８に対して複数経路を求める際のＰＣＥ内のデータメモリの構造を示す。なお、ＰＣＥ内で保持するノード１１−２０、リンクＬ１−Ｌ１４は実ネットワークに存在するノード、リンクではないが、実ネットワークの構成／情報をそのまま保持しており、各リンクＬ１−Ｌ１４はその方向に応じて２つの異なるリンクコストを持つ。
【００２８】
始点ノード以外の各ノードに対応して保持されている経路候補リスト１２１−２０１は、始点ノードから当該ノードまでの経路候補を経路コスト順に２分探索木でソーティングして保持している。経路候補は２１に示されるように、始点ノードから経路候補の終端ノードまでのノード順列を保持する。また、各経路候補リスト中で最小の経路コストを持つ経路候補は、フィボナッチヒープ（文献「M.L. Fredman and R.E. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms," Journal of the ACM (JACM), vol. 34, no. 3, pp. 596-615, 1987」参照）の各ノード２２にリンクされ、このフィボナッチヒープでの最小ノードがすべての経路候補リスト内での最小経路コストを持つ経路候補となる。
【００２９】
ＰＣＥ１内で保持する３つのマルチパス終端ノード１２，１５，１８は、それぞれ経路リスト１２２、１５２、１８２を保持し、その経路リストの中に、対応する経路候補リスト１２１、１５１，１８１から選択された、すべての経路候補リストの中で最小経路コストを持つ経路候補が順番に格納されていく。
【００３０】
なお、図３では各ノードに対応させて経路候補リストを保持しているが、図４のように、経路候補リストをリンクの終端点毎に保持することも可能である。図４においては、図３におけるノード１４においてリンク終端点毎に経路候補リストを保持する例を示している。ノード１４には３つのリンク終端点が存在するので、各終端点に応じて１４２、１４３，１４４の３つの経路候補リストが対応している。
【００３１】
図５は、本発明の第1の実施の形態における装置構成を示す。
【００３２】
同図に示す複数経路探索装置は、ノード選択部１０、リンク選択部２０、経路候補作成部３０、経路リスト制御部４０から構成される。
【００３３】
以下に、上記の構成における動作を図６のフローに沿って説明する。
【００３４】
ステップ２０１）ノード選択部１０は、ノード情報が入力されると、ノードの選択を行う。このとき、最初は始点ノードが選択され、以降は、ステップ２０４で選択された経路候補の終端ノードとなる。
【００３５】
ステップ２０２）  リンク選択部２０は、ステップ２０１で選択されたノードから出ているすべてのリンクを選択する。
【００３６】
ステップ２０３）  経路候補作成部３０は、ステップ２０２で選択された各リンクを直前のステップ２０４で選択した経路候補の後尾につなげた新しい経路候補を作成し、経路リスト制御部４０に出力する。経路リスト制御部４０は、始点ノードから上記で選択されたリンクの終端を持つノードまでの経路（ノード順列）を、終端ノード／最終リンク終端点に対応する経路リスト記憶部５０の経路候補リストに追加する。この際、経路候補上に同じノードを２回通るような経路候補は対象から外す。なお、予め経路候補数上限が設定されている場合は、その上限数以下の経路候補数を維持する（当該処理については、図７にて詳述する）。
【００３７】
なお、新規経路候補の経路コストは、直前のステップ２０４で選択された経路候補の経路コストに追加されるリンクコストを追加した形になるが、経路が経由するリンク数が多い場合は経路コストが大きくなるように比重をつけることも可能であり、その一例として、新経路候補の経路コスト|path(s,  v)|を
|path(s,  v)|  =  |path(s,  u)|+|E(u,  v)|  +  β|hop(path(s,  v))|
と定義することも可能である。ここで、βを正数とするとリンク数に応じて比重が設定されるが、βを０に設定すると従来手法の経路コストと同じとなる。当該処理を行うことで、始点ノードからの経由数が小さいリンクのコストが、経由数が大きいリンクのコストに比較して小さくなり、結果として経由数が小さいリンクが均等に複数の経路を探索する際に選択されることになる。このため、k  shortest  pathアルゴリズムの結果として多く見られる複数経路による固定リンクの過剰利用が避けられる。
【００３８】
ステップ２０４）経路リスト制御部４０は、図３のフィボナッチヒープ２２を用いてすべての経路候補リストの中で最小の経路候補を選択し、その経路候補を取り出し、当該の経路候補リストから削除する。
【００３９】
ステップ２０５）ステップ２０４で選択した経路候補の終端ノードが所望の終端ノードであるかどうかを判断し、所望の終端ノードである場合は、ステップ２０６に移行し、そうでない場合はステップ２０１に移行する。
【００４０】
ステップ２０６）  経路リスト制御部４０は、当該経路候補を経路リスト記憶部５０の当該終端ノードに対応する経路リストに格納する。
【００４１】
ステップ２０７）  経路リスト制御部４０は、すべての所望の終端ノードに対応する経路リストに所望数の経路が格納されたかどうかを判断し、すべて格納された場合には処理を終了し、まだ格納されきれていない場合は、ステップ２０１に戻る。
【００４２】
［第２の実施の形態］
本実施の形態では、経路候補数の管理方法について説明する。
【００４３】
図７は、本発明の第２の実施の形態における経路候補リストのデータ構造と新規経路候補受付判断を説明するための図である。
【００４４】
本実施の形態では、経路候補リスト記憶部５０内に、経路候補条件管理メモリ４１、最小経路として削除された経路候補数管理メモリ４２、最小経路として削除された経路候補数を含めた経路候補数管理メモリ４３を有する。
【００４５】
経路候補数上限管理メモリ４１は、すでに削除された経路候補数を含めた当該経路候補リスト中の経路候補数の上限を管理する。ここではその上限値をＡとする。
【００４６】
最小経路として削除された経路候補数管理メモリ４２は、当該経路候補リストで最小経路として削除された経路数を管理する。ここではその値をＢとする。
【００４７】
最小経路として削除された経路候補数を含めた経路候補数管理メモリ４３は、すでに最小経路として削除された経路候補数を含めた当該経路候補リスト中の経路候補数を管理する。ここではその値をＣとする。
【００４８】
同図の経路候補リストに示す、経路候補リスト内で最小の経路コストを持つ経路候補４４は、フィボナッチヒープ２２のノードにリンクしている。経路候補４５は経路候補リスト内で最大の経路コストを持つ経路候補である。
【００４９】
上記の各管理メモリでそれぞれ保持される値、Ａ，Ｂ，Ｃについて、経路リスト制御部４０は、以下のような制御を行うものとする。
【００５０】
（１）Ｃ＜Ａの場合は、経路候補数上限まで経路候補が当該経路候補リストに格納されていないので、当該経路候補リストにステップ２０３で生成された新経路候補を格納する。
【００５１】
（２）Ｂ＝Ａの場合は経路候補リストに経路候補を格納しない。
【００５２】
（３）Ｃ＝Ａ∧Ｂ≠Ａの場合は、当該新規経路候補４６を経路候補４５の経路コストと比較し、当該新規経路候補の経路コストが経路候補４５の経路コストより小さいときのみ、経路候補４５を経路候補リストから削除した後に、新規経路候補４６を経路候補リストに格納する。
【００５３】
上記のような制御を行うことにより、図６に示す処理において、扱う経路候補数を制限することが可能になり、さらなる処理時間の短縮が可能になる。また、各ノード、リンクの終端点に対応する経路候補リストの経路候補数上限の設定ができるので、より容量の大きいノード、リンクには高い上限値を設ける等の調整が可能となる。
【００５４】
なお、上記の図5に示す複数経路探索装置の構成要素の動作をプログラムとして構築し、当該装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５５】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５６】
１  複数経路探索装置（PCE:パスコンピューテーションエレメント）
２  始点ノード
３〜６  ノード
７，１２，１５，１８  マルチパス終端ノード
１０  ノード選択部
１１  始点ノード
１３，１４，１６，１７，１９，２０  ネットワークノード
２０  リンク選択部
２１  経路候補
２２  フィボナッチヒープ
３０  経路候補作成部
４０  経路リスト制御部
４１  経路候補数上限管理メモリ
４２  最小経路として削除された経路候補数管理メモリ
４３  最小経路として削除された経路候補数を含めた経路候補数管理メモリ
５０  経路リスト記憶部
１２２，１５２，１８２  経路リスト
１２１，１３１，１４１，１５１，１６１，１７１，１８１，１９１，２０１  経路候補リスト
【図１】
0005595342.tif 000002
【図２】
0005595342.tif 000003
【図３】
0005595342.tif 000004
【図４】
0005595342.tif 000005
【図５】
0005595342.tif 000006
【図６】
0005595342.tif 000007
【図７】
0005595342.tif 000008