特許
J-GLOBAL ID:201003072742469740

最短経路計算装置、最短経路計算方法、およびプログラム

発明者:
出願人/特許権者:
代理人 (3件): 宮崎 昭夫 ,  石橋 亮一 ,  ▲高▼森 俊夫
公報種別:公開公報
出願番号(国際出願番号):特願2008-300973
公開番号(公開出願番号):特開2010-130173
出願日: 2008年11月26日
公開日(公表日): 2010年06月10日
要約:
【課題】ノードやリンクの追加または削除があったとき、最短経路の再計算を行うことが可能な最短経路計算装置を提供する。【解決手段】起点ノードから到達し得るノードとノード同士の接続関係との情報を含む計算対象ツリーが格納される記憶部と、ネットワークのトポロジに変化があると、上記計算対象ツリーを設定し、トポロジの変化がリンクの追加であると、追加されたリンクに接続される第1および第2のノードについて、追加されたリンクを経由する第1の経路の方がそのリンクを経由しない第2の経路よりも短ければ、第1の経路を最短経路の候補とし、トポロジの変化がリンクの削除であると、計算対象ツリー内の第3のノードと計算対象ツリーに属さない第4のノードとを結ぶリンクを見つけ、該リンクを含む経路を起点ノードから第4のノードまでの最短経路の候補とし、最短経路の候補が複数あれば、最短な候補を最短経路に決定するプロセッサとを有する。【選択図】図1
請求項(抜粋):
ネットワークにおけるノード間の最短経路を計算する最短経路計算装置であって、 起点となるノードである起点ノードからノード間の上流下流の関係をたどって到達し得るノードと該ノード同士における上流下流の接続関係との情報を含む計算対象ツリーが格納される記憶部と、 前記ネットワークのトポロジに変化があると、前記計算対象ツリーを設定し、前記トポロジの変化が新たな第1のリンクの追加である場合、前記計算対象ツリー内のノードであって該第1のリンクで接続される第1および第2のノードについて、前記起点ノードから前記計算対象ツリーに沿って前記第2のノードまで到達する経路および前記第1のリンクの経路を経由して前記第1のノードまで到達する経路からなる第1の経路と、前記起点ノードから前記計算対象ツリーに沿って前記第1のノードまで到達する第2の経路との距離を比較し、前記第2の経路よりも前記第1の経路の距離が短ければ、前記第1の経路を前記起点ノードから前記第1のノードまでの最短経路の候補とし、前記トポロジの変化がリンクの削除である場合、削除されたリンクの下流側の情報を前記計算対象ツリーから削除し、該計算対象ツリー内の第3のノードと該計算対象ツリーに属さない第4のノードとを結ぶ第2のリンクを見つけると、前記起点ノードから前記計算対象ツリーに沿って前記第3のノードまで到達する経路および前記第2のリンクからなる経路を前記起点ノードから第4のノードまでの最短経路の候補とし、前記起点ノードから前記第1または第4のノードに至る経路について、前記最短経路の候補が複数あれば、複数の候補から距離が最短な候補を特定し、特定した候補を最短経路に決定するプロセッサと、 を有する最短経路計算装置。
IPC (1件):
H04L 12/56
FI (1件):
H04L12/56 100Z
Fターム (2件):
5K030GA14 ,  5K030LB05
引用特許:
審査官引用 (5件)
全件表示
引用文献:
審査官引用 (2件)
  • ホストの接続次数を用いた深さ均一なALMツリー構築法
  • 高速なコスト削減マルチキャスト経路計算法の検討

前のページに戻る