【要約】
【課題】
大規模なネットワークにおいて、より利用効率の高いネットワークリソースを割り当てる。
【解決手段】
制約条件取得部91は、ネットワークにおけるトラヒック量の上限値および下限値を取得し、線形計画問題計算部93は、取得された上限値および下限値の両方を含む制約条件を基に、ネットワークを表現するホースモデルについて、ネットワークにおける全リンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、ネットワークの各リンクに割り当てるべきリソース(帯域)を計算し、リソース割当部72は、リソースの計算結果に基づいて、ネットワークの各リンクにリソースを割り当て、経路計算部73は、割り当てられたリソースに基づいて、ネットワークにおけるノード間の経路計算を行う。本発明は、例えば、ネットワークの経路を計算する経路計算装置に適用することができる。
【特許請求の範囲】
【請求項1】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得手段と、
前記取得手段によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算手段と、
前記帯域計算手段の計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当手段と、
前記割当手段によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算手段と
を備える経路計算装置。
【請求項2】
前記線形計画問題における前記制約条件を、双対定理を用いて他の制約条件に変換する変換手段をさらに備え、
前記帯域計算手段は、前記変換手段によって変換された前記他の制約条件を基に、前記線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する
請求項1に記載の経路計算装置。
【請求項3】
前記変換手段は、前記トラヒック量で規定される前記制約条件を、前記ネットワークの各リンクに対して一意的なパラメータで規定される前記他の制約条件に変換する
請求項2に記載の経路計算装置。
【請求項4】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、
前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、
前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、
前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップと
を含む経路計算方法。
【請求項5】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、
前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、
前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、
前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップと
を含む処理をコンピュータに実行させるプログラム。
|