経路計算方法及び装置及びプログラム

発明者： , ,
出願人/特許権者：
代理人 (2件)：伊東忠彦 , 石原隆治
公報種別：公開公報
出願番号（国際出願番号）：特願2006-230814
公開番号（公開出願番号）：特開2008-054211
出願日： 2006年08月28日
公開日（公表日）： 2008年03月06日
要約：

【課題】LSPを構成するリンクの数を最小限に抑えたLSP経路計算を可能にする。【解決手段】本発明は、ホップ数・合計コストが最小のノードを次の探索ノードとし、その隣接ノードについて、探索ノード経由の経路における第1のホップ数と第1の合計コストを計算し、隣接ノードについて、記憶手段にホップ数が格納されていない場合、または、他のノード経由の経路の第2のホップ数>第1のホップ数の場合は、第1のホップ数、第1の合計コスト、探索ノード経由の経路を記憶手段に格納し、第2のホップ数=第1のホップ数、かつ、他のノード経由の経路の第2の合計コスト>第1の合計コストの場合は、該第1のホップ数、該第1の合計コスト、探索ノード経由の経路を記憶手段に格納し、終点ノード全てが訪問済みとなるまで、探索ノード決定処理以降の処理を繰り返し、経路を出力する。【選択図】図1

請求項（抜粋）：

ネットワークトポロジにおいて、1つの始点ノードから1つの終点ノード、または、1つの始点ノードから複数の終点ノードまでの経路を計算する経路計算方法であって、要求取得手段が、各ノードの接続関係を表したトポロジ情報及び、始点ノードと1つまたは複数の終点ノードを受け付ける要求取得ステップと、探索ノード決定手段が、既に探索ノードとなったノードを保存する訪問済みノード記憶手段を参照して、訪問済みノードが1つもない場合は、前記始点ノードを探索ノードとして決定し、訪問済みノードがある場合は、まだ訪問済みとなっていないノードの中から、ノード毎のホップ数、合計コスト、経路を格納するノード情報記憶手段を参照して、ホップ数が最小のノードを探索ノードとして決定し、ホップ数が最小のノードが複数ある場合は、その中から合計コストが最小のノードを次の探索ノードとして決定し、該探索ノードを訪問済みノード記憶手段に記録する探索ノード決定ステップと、経路パラメータ計算手段が、前記トポロジ情報を参照し、前記探索ノードの隣接ノードについて、前記探索ノード経由の経路における第1のホップ数と第1の合計コストを計算する経路パラメータ計算ステップと、経路パラメータ判定手段が、前記隣接ノードについて、前記ノード情報記憶手段を参照し、ホップ数が格納されていない場合、または、他のノード経由の経路における第2のホップ数が既に計算されているが、前記第1のホップ数の方が小さい場合は、該第1のホップ数、前記第1の合計コスト、前記探索ノード経由の経路を該ノード情報記憶手段に格納し、該第2のホップ数が該第1のホップ数と等しく、かつ、他のノード経由の経路における第2の合計コストが既に計算されているが、該第1の合計コストの方が小さい場合は、該第1のホップ数、該第1の合計コスト、前記探索ノード経由の経路を該ノード情報記憶手段に格納する経路パラメータ判定ステップと、前記終点ノード全てが前記訪問済みノード記憶手段に記録されるまで、探索ノード決定ステップ以降の処理を繰り返し、経路出力手段が、前記ノード情報記憶手段を参照し、経路を出力する経路出力ステップと、を行うことを特徴とする経路計算方法。

IPC (1件)：

H04L 12/56

FI (1件)：

H04L12/56 100Z

Fターム (8件)：

5K030GA04 , 5K030HA08 , 5K030HD03 , 5K030JA10 , 5K030KA05 , 5K030LB05 , 5K030MB07 , 5K030MD07

引用文献：

審査官引用 (1件)

MPLSトラヒックエンジニアリングにおけるアルゴリズム/トポロジ評価

前のページに戻る