経路計算装置および方法

開放特許情報

特許情報

発明の名称	経路計算装置および方法、並びにプログラム
技術分野	IT
出願日	平成２１年１月２３日
出願番号	特願２００９－１２６０４
公開番号	特開２０１０－１７１７５８
登録番号
出願人	国立大学法人電気通信大学
発明者	大木英司
特許公報	PDFのダウンロードはこちらから
概要	【要約】【課題】大規模なネットワークにおいて、より利用効率の高いネットワークリソースを割り当てる。【解決手段】制約条件取得部９１は、ネットワークにおけるトラヒック量の上限値および下限値を取得し、線形計画問題計算部９３は、取得された上限値および下限値の両方を含む制約条件を基に、ネットワークを表現するホースモデルについて、ネットワークにおける全リンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、ネットワークの各リンクに割り当てるべきリソース（帯域）を計算し、リソース割当部７２は、リソースの計算結果に基づいて、ネットワークの各リンクにリソースを割り当て、経路計算部７３は、割り当てられたリソースに基づいて、ネットワークにおけるノード間の経路計算を行う。本発明は、例えば、ネットワークの経路を計算する経路計算装置に適用することができる。【特許請求の範囲】【請求項１】複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得手段と、前記取得手段によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算手段と、前記帯域計算手段の計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当手段と、前記割当手段によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算手段とを備える経路計算装置。【請求項２】前記線形計画問題における前記制約条件を、双対定理を用いて他の制約条件に変換する変換手段をさらに備え、前記帯域計算手段は、前記変換手段によって変換された前記他の制約条件を基に、前記線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する請求項１に記載の経路計算装置。【請求項３】前記変換手段は、前記トラヒック量で規定される前記制約条件を、前記ネットワークの各リンクに対して一意的なパラメータで規定される前記他の制約条件に変換する請求項２に記載の経路計算装置。【請求項４】複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップとを含む経路計算方法。【請求項５】複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップとを含む処理をコンピュータに実行させるプログラム。

本特許の活用に関心がある方はコチラよりお問合せください。