株式会社キャンパスクリエイト

お客様の課題解決を
オープンイノベーションで実践する
広域TLO

(調布オフィス)
〒182-8585 東京都調布市調布ヶ丘1-5-1
国立大学法人電気通信大学産学官連携センター内

開放特許情報

特許情報

発明の名称 経路計算装置および方法、並びにプログラム
技術分野 IT
出願日 平成21年1月23日
出願番号 特願2009-12604
公開番号 特開2010-171758
登録番号
出願人 国立大学法人電気通信大学
発明者 大木 英司
特許公報 PDFのダウンロードはこちらから
概要 【要約】

【課題】
大規模なネットワークにおいて、より利用効率の高いネットワークリソースを割り当てる。

【解決手段】
制約条件取得部91は、ネットワークにおけるトラヒック量の上限値および下限値を取得し、線形計画問題計算部93は、取得された上限値および下限値の両方を含む制約条件を基に、ネットワークを表現するホースモデルについて、ネットワークにおける全リンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、ネットワークの各リンクに割り当てるべきリソース(帯域)を計算し、リソース割当部72は、リソースの計算結果に基づいて、ネットワークの各リンクにリソースを割り当て、経路計算部73は、割り当てられたリソースに基づいて、ネットワークにおけるノード間の経路計算を行う。本発明は、例えば、ネットワークの経路を計算する経路計算装置に適用することができる。

【特許請求の範囲】

【請求項1】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得手段と、
前記取得手段によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算手段と、
前記帯域計算手段の計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当手段と、
前記割当手段によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算手段と
を備える経路計算装置。

【請求項2】
前記線形計画問題における前記制約条件を、双対定理を用いて他の制約条件に変換する変換手段をさらに備え、
前記帯域計算手段は、前記変換手段によって変換された前記他の制約条件を基に、前記線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する
請求項1に記載の経路計算装置。

【請求項3】
前記変換手段は、前記トラヒック量で規定される前記制約条件を、前記ネットワークの各リンクに対して一意的なパラメータで規定される前記他の制約条件に変換する
請求項2に記載の経路計算装置。

【請求項4】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、
前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、
前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、
前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップと
を含む経路計算方法。

【請求項5】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、
前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、
前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、
前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップと
を含む処理をコンピュータに実行させるプログラム。

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