(57)【要約】【課題】大規模なネットワークにおいて、より利用効率の高いネットワークリソースを割り当てる。【解決手段】制約条件取得部９１は、ネットワークにおけるトラヒック量の上限値および下限値を取得し、線形計画問題計算部９３は、取得された上限値および下限値の両方を含む制約条件を基に、ネットワークを表現するホースモデルについて、ネットワークにおける全リンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、ネットワークの各リンクに割り当てるべきリソース（帯域）を計算し、リソース割当部７２は、リソースの計算結果に基づいて、ネットワークの各リンクにリソースを割り当て、経路計算部７３は、割り当てられたリソースに基づいて、ネットワークにおけるノード間の経路計算を行う。本発明は、例えば、ネットワークの経路を計算する経路計算装置に適用することができる。【選択図】図２
2010171758.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得手段と、
前記取得手段によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算手段と、
前記帯域計算手段の計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当手段と、
前記割当手段によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算手段と
を備える経路計算装置。
【請求項２】
前記線形計画問題における前記制約条件を、双対定理を用いて他の制約条件に変換する変換手段をさらに備え、
前記帯域計算手段は、前記変換手段によって変換された前記他の制約条件を基に、前記線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する
請求項１に記載の経路計算装置。
【請求項３】
前記変換手段は、前記トラヒック量で規定される前記制約条件を、前記ネットワークの各リンクに対して一意的なパラメータで規定される前記他の制約条件に変換する
請求項２に記載の経路計算装置。
【請求項４】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、
前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、
前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、
前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップと
を含む経路計算方法。
【請求項５】
複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、
前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、
前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、
前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップと
を含む処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路計算装置および方法、並びにプログラムに関し、特に、大規模なネットワークにおいて、より利用効率の高いネットワークリソースを割り当てることができるようにする経路計算装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
VPN（Virtual Private Network）等の仮想ネットワークサービスを提供するネットワーク事業者が、仮想ネットワーク毎に割り当てる帯域（ネットワークリソース（以下、単に、リソースともいう））を計算する際に、所定のモデル（ネットワークモデル）を用いて、リソースを割り当てることが行われている（例えば、特許文献１参照）。
【０００３】
上述したモデルには、パイプモデルとホースモデルとがある。パイプモデルは、ネットワークにおいて、ノード間のトラヒック量の上限値を規定（制限）したモデルである。パイプモデルにおいては、ノード間のトラヒック量が規定された上限値以内となるように、リソースが割り当てられる。また、ホースモデルは、各ノードにおいて流入／流出するトラヒック量の上限値を規定（制限）したモデルである。ホースモデルにおいては、各ノードにおいて流入／流出するトラヒック量が規定された上限値以内となるように、リソースが割り当てられる。
【０００４】
ネットワークリソースの利用効率を向上させるための１つの手法として、ネットワークにおける全てのリンクの使用率の最大値（以下、ネットワーク輻輳率と称する）を最小化することが考えられる。ネットワーク輻輳率を最小化するということは、ネットワークにおいて受付可能なトラヒック量を最大にすることに等しい。すなわち、上述したパイプモデルまたはホースモデルにおいて、ネットワーク輻輳率が最小となるモデルを決定することで、より利用効率の高いネットワークリソースを割り当てることができる。
【０００５】
パイプモデルにおいては、始点ノードｐから終点ノードｑへのトラヒック量dpqについて、ネットワークにおける全ての始点ノード乃至終点ノード間のトラヒック量を表すトラヒック行列T={dpq}が、予め完全に与えられていることを前提としている。すなわち、ノード間のトラヒック量dpqが、所定の上限値以内で予め正確に与えられている場合には、ネットワーク輻輳率が最小となるパイプモデルを適切に決定することができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−５４７２２号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、大規模なネットワークにパイプモデルを適用しようとする場合、ノードの数が多くなり、全てのノード間のトラヒック量dpqを正確に測定することが困難なため、正確なトラヒック行列T={dpq}を得ることができず、ネットワーク輻輳率が最小となるパイプモデルを適切に決定することができなかった。
【０００８】
一方、ホースモデルにおいては、上述したように、所定のノードにおいて流入／流出するトラヒック量の上限値は制限される。すなわち、例えば、始点ノードｐからネットワークへ流出するトラヒック量の上限値をαpとすると、始点ノードｐからネットワークへ流出するトラヒック量の総量は、Σqdpq≦αpとなる。また、ネットワークから終点ノードｑへ流入するトラヒック量の上限値をβqとすると、ネットワークから終点ノードｑへ流入するトラヒック量の総量は、Σpdpq≦βqとなる。
【０００９】
ところで、ホースモデルにおいても、ネットワークにおける全てのノード間のトラヒック量を表すトラヒック行列T={dpq}は、始点ノードｐと終点ノードｑとの全ての組み合わせについて考慮される必要がある。
【００１０】
しかしながら、ホースモデルにおいても、やはり、始点ノードｐと終点ノードｑとの全ての組み合わせについてトラヒック行列T={dpq}を得ることは容易ではなく、また、トラヒック行列T={dpq}が予め完全に与えられていることを前提するパイプモデルと比較して、ホースモデルの正確性は劣っていた。
【００１１】
本発明は、このような状況に鑑みてなされたものであり、大規模なネットワークに対して、ネットワーク輻輳率が最小となるモデルを適切に決定し、より利用効率の高いネットワークリソースを割り当てるようにするものである。
【課題を解決するための手段】
【００１２】
本発明の一側面の経路計算装置は、複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得手段と、前記取得手段によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算手段と、前記帯域計算手段の計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当手段と、前記割当手段によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算手段とを備える。
【００１３】
前記経路計算装置においては、前記線形計画問題における前記制約条件を、双対定理を用いて他の制約条件に変換する変換手段をさらに設け、前記帯域計算手段には、前記変換手段によって変換された前記他の制約条件を基に、前記線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算させることができる。
【００１４】
前記変換手段には、前記トラヒック量で規定される前記制約条件を、前記ネットワークの各リンクに対して一意的なパラメータで規定される前記他の制約条件に変換させることができる。
【００１５】
本発明の一側面の経路計算方法は、複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップとを含む。
【００１６】
本発明の一側面のプログラムは、複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方を取得する取得ステップと、前記取得ステップの処理によって取得された前記上限値および前記下限値の両方またはいずれか一方を含む前記トラヒック量で規定される制約条件を基に、前記ネットワークを表現するホースモデルについて、前記ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、前記ネットワークの各リンクに割り当てるべき帯域を計算する帯域計算ステップと、前記帯域計算ステップにおける計算結果に基づいて、前記ネットワークの各リンクに帯域を割り当てる割当ステップと、前記割当ステップの処理によって割り当てられた帯域に基づいて、前記ネットワークにおけるノード間の経路計算を行う経路計算ステップとを含む処理をコンピュータに実行させる。
【００１７】
本発明の一側面においては、複数のノードから形成されるネットワークの始点ノードと終点ノードとの間のトラヒック量の上限値および下限値の両方またはいずれか一方が取得され、取得された上限値および下限値の両方またはいずれか一方を含むトラヒック量で規定される制約条件を基に、ネットワークを表現するホースモデルについて、ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、ネットワークの各リンクに割り当てるべき帯域が計算され、計算結果に基づいて、ネットワークの各リンクに帯域が割り当てられ、割り当てられた帯域に基づいて、ネットワークにおけるノード間の経路計算が行われる。
【発明の効果】
【００１８】
本発明の一側面によれば、大規模なネットワークに対して、ネットワーク輻輳率が最小となるモデルを適切に決定し、より利用効率の高いネットワークリソースを割り当てることが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施の形態としての経路計算装置を含むネットワークの構成例を示すブロック図である。
【図２】図１の経路計算装置の具体的な機能構成例を示すブロック図である。
【図３】トラヒック量のとり得る範囲を制限した経路計算処理について説明するフローチャートである。
【図４】制約条件変換処理について説明するフローチャートである。
【図５】上下限値追加ホースモデルにおけるネットワーク輻輳率の算出結果について説明する図である。
【図６】コンピュータのハードウェアの構成例を示すブロック図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態について図を参照して説明する。
【００２１】
［画像表示装置の構成例］
図１は、本発明の一実施の形態としての経路計算装置を含むネットワークの構成例を示している。
【００２２】
図１において、経路計算装置１１とノード１２−１乃至１２−４それぞれとは、通信可能に接続されている。また、図１において、ノード１２−１乃至１２−４によって形成されるネットワークは、例えば、TDM（Time Division Multiplexing）やWDM（Wavelet Division Multiplexing）等の回線交換ネットワーク、IP（Internet Protocol）やイーサネット（登録商標）、MPLS（Multi-Protocol Label Switching）等により実現される。
【００２３】
経路計算装置１１は、ノード１２−１乃至１２−４それぞれから、ネットワークについての各種の情報を取得する。また、経路計算装置１１は、取得した各種の情報に基づいて、ネットワーク全体のリソースの割り当てを行い、ノード１２−１乃至１２−４それぞれの間の経路計算を行い、経路計算の結果に応じた経路設定の指示を、ノード１２−１乃至１２−４それぞれに供給する。なお、経路計算装置１１の具体的な構成については後述する。
【００２４】
ノード１２−１乃至１２−４は、クロスコネクト装置やルータ等で構成される。ノード１２−１乃至１２−４はそれぞれ、経路制御装置１２ａ−１乃至１２ａ−４を備えており、経路制御装置１２ａ−１乃至１２ａ−４は、経路計算装置１１からの指示に基づいて、ネットワークにおける経路を設定する。
【００２５】
なお、図１のネットワークにおいては、便宜上、ノードの数を、ノード１２−１乃至１２−４の４個であるものとしたが、本実施の形態は、より多くのノードを含むネットワークに対して適用されるものとする。
【００２６】
［経路計算装置の機能構成例］
次に、図２を参照して、経路計算装置１１の具体的な機能構成例について説明する。
【００２７】
図２の経路計算装置１１は、入出力部３１、記憶部３２、制御部３３、および通信部３４から構成される。
【００２８】
入出力部３１は、経路計算装置１１に接続される、例えば、キーボードやマウス等の入力装置（図示せず）、および、液晶モニタ等の出力装置（図示せず）とのインタフェースである。入出力部３１は、ユーザの操作によって図示せぬ入力装置から入力された情報を、記憶部３２や制御部３３に供給したり、制御部３３において得られた情報（計算結果等）を図示せぬ出力装置に供給する。
【００２９】
記憶部３２は、RAM（Random Access Memory）、フラッシュメモリ、HD（Hard Disk）等の記憶装置で構成される。記憶部３２は、経路計算装置１１の機能を実現するプログラムを記憶する他、ノード１２−１乃至１２−４それぞれから取得した、ネットワークについての各種の情報を記憶する。記憶部３２は、トポロジ情報記憶部５１、経路情報記憶部５２、トラヒック情報記憶部５３、およびリソース情報記憶部５４を備えている。
【００３０】
トポロジ情報記憶部５１は、ネットワーク内のノード（図１のノード１２−１乃至１２−４）それぞれを識別する識別情報と、ノード同士がどのように接続されているかを示すトポロジ情報とを記憶する。トポロジ情報は、例えば、ネットワークの構成が変更される度に、通信部３４を介して取得される。
【００３１】
経路情報記憶部５２は、制御部３３において算出された、ネットワーク内のノード間の最短経路を示す経路情報を記憶する。
【００３２】
トラヒック量記憶部５３は、ネットワーク内の各ノード間（リンク）における、現在のトラヒック量を記憶する。トラヒック量は、例えば、所定の時間間隔で、通信部３４を介して取得されるようにしてもよいし、ユーザの操作に応じて図示せぬ入力装置が操作されたときに、通信部３４を介して取得されるようにしてもよい。
【００３３】
リソース情報記憶部５４は、ネットワーク内の各ノード間（リンク）における、現在のネットワーク内の各リンクに割り当てられているリソース（帯域）を示すリソース情報を記憶する。
【００３４】
制御部３３は、図示せぬCPU（Central Processing Unit）等が、記憶部３２に記憶されている所定のプログラムを実行することで実現され、経路計算装置１１の機能を実現する。制御部３３は、リソース計算部７１、リソース割当部７２、および経路計算部７３から構成される。
【００３５】
リソース計算部７１は、記憶部３２に記憶されている各種の情報に基づいて記述される、線形計画問題を解くことによって、ネットワーク内の各リンクに割り当てるべきリソースを計算する。
【００３６】
線形計画問題は、与えられた制約条件（等式または不等式）のもとで、線形な目的関数を最大化または最小化するように記述される。例えば、本実施の形態においては、リソース計算部７１は、パイプモデルまたはホースモデルにおける制限（制約条件）のもとで、ネットワーク輻輳率を最小化するように記述された線形計画問題を解く。本実施の形態における線形計画問題の具体的な説明については後述する。
【００３７】
リソース計算部７１は、制約条件取得部９１、制約条件変換部９２、および線形計画問題計算部９３を備えている。
【００３８】
制約条件取得部９１は、線形計画問題における制約条件を、記憶部３２に記憶されている各種の情報、および、ユーザが図示せぬ入力装置を操作することで入出力部３１から供給される情報から取得する。また、制約条件取得部９１は、取得した制約条件を基に線形計画問題を作成する。
【００３９】
制約条件変換部９２は、制約条件取得部９１によって取得された制約条件を、線形計画問題において最適な解（最適解）が得られるように、他の制約条件に変換する。制約条件変換部９２は、抽出部９２ａ、変換条件算出部９２ｂ、および変換部９２ｃを備えている。抽出部９２ａは、制約条件取得部９１によって取得された制約条件のうちの所定の制約条件を抽出する。変換条件算出部９２ｂは、抽出部９２ａによって抽出された制約条件を変換するための制約条件変換条件を求める。変換部９２ｃは、変換条件算出部９２ｂによって求められた制約条件変換条件に基づいて、制約条件取得部９１によって取得された制約条件を変換する。なお、制約条件変換部９２による制約条件の変換の処理の詳細は後述する。
【００４０】
線形計画問題計算部９３は、制約条件変換部９２によって変換された後の制約条件に基づいて、ネットワーク輻輳率を最小化するように記述された線形計画問題を解くことで、ネットワーク内の各リンクにおける最適なリソースを計算する。
【００４１】
リソース割当部７２は、リソース計算部７１によって計算されたネットワーク内の各リンクにおけるリソースと、リソース情報記憶部５４に記憶されているリソース情報によって示されるリソースとの差分を基に、ネットワーク内の各リンクに対して、リソースを割り当てる。
【００４２】
経路計算部７３は、リソース割当部７２によって割り当てられたリソースに基づいて、ネットワーク内のノード間の経路を計算し、その結果を経路情報として通信部３４や経路情報記憶部５２に供給する。
【００４３】
通信部３４は、経路計算装置１１と、ネットワーク内の各ノード（例えば、図１のノード１２−１乃至１２−４）とのインタフェースである。通信部３４は、ネットワーク内の各ノードから各種の情報を取得したり、ネットワーク内の各ノードに対して、経路計算部７３によって計算された経路情報に基づいた経路設定の指示を供給する。
【００４４】
［ネットワークモデルに対する線形計画問題の適用］
ここで、ネットワークモデル（パイプモデルまたはホースモデル）に対して、線形計画問題を適用することについて説明する。
【００４５】
一般的に、ネットワークは、いわゆるグラフ理論における有向グラフG(V,E)で表現することができる。Ｖはノードの集合を表し、Ｅはリンクの集合を表している。このようなネットワークにおいて、ノードｉ（ｉ∈Ｖ）からノードｊ（ｊ∈Ｖ）までのリンクをlink(i,j)（link(i,j)∈E）とし、リンクlink(i,j)のトラヒックの最大許容量（以下、単に、容量という）をcij、リンクlink(i,j)の使用率をLijとする。さらに、トラヒックをネットワーク内に流入／流出させるノード（エッジノード）の集合をＱ（Ｑ⊆Ｖ）として、所定のエッジノード（始点ノード）ｐ（ｐ∈Ｑ）から所定のエッジノード（終点ノード）ｑ（ｑ∈Ｑ）までのトラヒック量をdpqとする。また、始点ノードｐから終点ノードｑまで流れるトラヒックのうち、リンクlink(i,j)を通過するトラヒックの割合をxpqijとする。
【００４６】
ここで、ネットワークにおける全てのリンクの使用率の最大値であるネットワーク輻輳率をｒ（=Max(Lij)）とした場合、上述した有向グラフG(V,E)で定義されたパイプモデルまたはホースモデルにおいて、ネットワーク輻輳率ｒを最小化することで、ネットワークリソースの利用効率を向上させることができる。すなわち、ネットワーク輻輳率ｒを目的関数とした線形計画問題を解くことで、最小化されたネットワーク輻輳率ｒを求めればよい。
【００４７】
まず、パイプモデルにおいて、ネットワーク輻輳率ｒを最小化することを考える。式（１）乃至（６）は、パイプモデルについて記述された線形計画問題を示している。
【００４８】
目的関数：
【数１】
2010171758.tif 000003
【００４９】
制約条件：
【数２】
2010171758.tif 000004
【００５０】
【数３】
2010171758.tif 000005
【００５１】
【数４】
2010171758.tif 000006
【００５２】
【数５】
2010171758.tif 000007
【００５３】
【数６】
2010171758.tif 000008
【００５４】
式（１）は、ネットワーク輻輳率ｒを最小化することを示す目的関数である。式（２）乃至（６）は、この線形計画問題における制約条件を示している。式（２）は、ノードｉが始点ノードでも終点ノードでもない場合、ノードｉに流入するトラヒックとノードｉから流出するトラヒックとは等しいことを示している。式（３）は、ノードｉがエッジノード（例えば、始点ノードｐ）である場合、ノードｉから流出するトラヒックの総和は１であることを示している。このように、式（２），（３）は、有向グラフにおけるフロー保存則を表している。式（４）は、リンクlink(i,j)を通過するトラヒックの総和は、ネットワーク輻輳率ｒとリンクlink(i,j)の容量cijとの積以下であることを示している。式（５）は、始点ノードｐから終点ノードｑまで流れるトラヒックのうちのリンクlink(i,j)を通過するトラヒックの割合xpqijが、式（６）は、ネットワーク輻輳率ｒが、それぞれ０乃至１の範囲であることを示している。
【００５５】
しかしながら、上述した通り、大規模なネットワークにパイプモデルを適用しようとする場合、ノードの数が多くなり、全てのノード間のトラヒック量dpqを正確に測定することが困難なため、正確なトラヒック行列T={dpq}を得ることができず、ネットワーク輻輳率ｒが最小となるパイプモデルを適切に決定することができなかった。
【００５６】
一方、ホースモデルにおいて、ネットワーク輻輳率ｒを最小化することを考える。
【００５７】
式（７）乃至（１５）は、ホースモデルについて記述された線形計画問題を示している。
【００５８】
目的関数：
【数７】
2010171758.tif 000009
【００５９】
制約条件：
【数８】
2010171758.tif 000010
【００６０】
【数９】
2010171758.tif 000011
【００６１】
【数１０】
2010171758.tif 000012
【００６２】
【数１１】
2010171758.tif 000013
【００６３】
【数１２】
2010171758.tif 000014
【００６４】
【数１３】
2010171758.tif 000015
【００６５】
【数１４】
2010171758.tif 000016
【００６６】
【数１５】
2010171758.tif 000017
【００６７】
式（７）は、ネットワーク輻輳率ｒを最小化することを示す目的関数である。式（８）乃至（１５）は、この線形計画問題における制約条件を示している。式（８）は、ノードｉが始点ノードでも終点ノードでもない場合、ノードｉに流入するトラヒックとノードｉから流出するトラヒックとは等しいことを示している。式（９）は、ノードｉがエッジノード（例えば、始点ノードｐ）である場合、ノードｉから流出するトラヒックの総和は１であることを示している。すなわち、式（８），（９）は、有向グラフにおけるフロー保存則を表している。式（１０）は、リンクlink(i,j)を通過するトラヒックの総和は、ネットワーク輻輳率ｒとリンクlink(i,j)の容量cijとの積以下であることを示している。式（１１）は、所定の始点ノードｐからネットワークへ流出するトラヒック量の総量は、上限値αp以下であることを示しており、式（１２）は、ネットワークから所定の終点ノードｑへ流入するトラヒック量の総量は、上限値βq以下であることを示している。また、式（１３）は、始点ノードｐから終点ノードｑへのトラヒック量dpqは０以上であることを示している。そして、式（１４）は、始点ノードｐから終点ノードｑまで流れるトラヒックのうちのリンクlink(i,j)を通過するトラヒックの割合xpqijが、式（１５）は、ネットワーク輻輳率ｒが、それぞれ０乃至１の範囲であることを示している。
【００６８】
しかしながら、上述した通り、ホースモデルにおいて、始点ノードｐと終点ノードｑとの全ての組み合わせについてトラヒック行列T={dpq}を得ることは容易ではなかった。
【００６９】
ところで、J. Chu and C. Lee, “Optimal Link Weights for Maximizing QoS Traffic”, IEEE ICC 2007, pp.610-615, 2007.に基づいて、式（７）乃至（１５）で記述される線形計画問題を、式（１６）乃至（２３）で記述される線形計画問題に変換することにより、上述した点は解決されることが知られている。
【００７０】
目的関数：
【数１６】
2010171758.tif 000018
【００７１】
制約条件：
【数１７】
2010171758.tif 000019
【００７２】
【数１８】
2010171758.tif 000020
【００７３】
【数１９】
2010171758.tif 000021
【００７４】
【数２０】
2010171758.tif 000022
【００７５】
【数２１】
2010171758.tif 000023
【００７６】
【数２２】
2010171758.tif 000024
【００７７】
【数２３】
2010171758.tif 000025
【００７８】
以上においては、ホースモデルにおける制約条件を表す式（１０）乃至（１３）が、ノードの組(i,j)に対して一意的なパラメータπij(p)およびλij(p)を用いて、式（１９）乃至（２１）に変換されている。
【００７９】
具体的には、式（１９）は、式（１０）の左辺における、リンクlink(i,j)を通過するトラヒック量dpqxpqijが、式（１１），（１２）を基に、パラメータπij(p)およびλij(p)、並びに上限値αp，βpを用いた項に置き換えられていることを示している。また、式（２０），（２１）は、式（１９）の関係を成立させるための条件を示している。なお、式（１６）乃至（１８），（２２），（２３）は、それぞれ、式（７）乃至（９），（１４），（１５）に対応する。
【００８０】
このように、上述の式（１６）乃至（２３）においては、トラヒック量dpqを用いずに線形計画問題が記述されている。
【００８１】
しかしながら、そもそも、ホースモデルは、トラヒック行列T={dpq}が予め完全に与えられていることを前提するパイプモデルと比較して、その正確性は劣ってしまう。
【００８２】
これに対して、経路計算装置１１は、大規模なネットワークに適用したホースモデルにおいて、トラヒック行列T={dpq}を構成するトラヒック量dpqのとり得る範囲を適切に制限することで、そのモデルの正確性を高めるようにすることができる。
【００８３】
［経路計算装置による経路計算処理］
そこで、図３のフローチャートを参照して、経路計算装置１１による、トラヒック量dpqのとり得る範囲を制限した経路計算処理について説明する。
【００８４】
ネットワーク事業者において、オペレータは、運用上の経験や過去のデータに基づいて、始点ノードｐから終点ノードｑまでのトラヒック量dpqに対して、上限値γpqおよび下限値δpqの両方またはいずれか一方を推定し、与えることができる。
【００８５】
すなわち、ステップＳ１１において、制約条件取得部９１は、線形計画問題において制約条件となる情報（トラヒック量記憶部５３に記憶されている現在のトラヒック量等）を記憶部３２から取得するとともに、ユーザ（オペレータ）により図示せぬ入力装置が操作されることで入出力部３１から供給される、トラヒック量dpqの上限値γpqおよび下限値δpqの両方またはいずれか一方を取得する。
【００８６】
ステップＳ１２において、制約条件取得部９１は、上限値γpqおよび下限値δpqの両方またはいずれか一方を含むトラヒック量dpqで規定される制約条件を基に、ホースモデルについて記述された線形計画問題を作成する。
【００８７】
式（２４）乃至（３２）は、制約条件取得部９１によって作成される、ホースモデルについて記述された線形計画問題を示している。なお、上限値γpqおよび下限値δpqの両方を含むトラヒック量dpqで規定される制約条件に基づいた線形計画問題についてのホースモデルを、以下、上下限値追加ホースモデルと称する。
【００８８】
目的関数：
【数２４】
2010171758.tif 000026
【００８９】
制約条件：
【数２５】
2010171758.tif 000027
【００９０】
【数２６】
2010171758.tif 000028
【００９１】
【数２７】
2010171758.tif 000029
【００９２】
【数２８】
2010171758.tif 000030
【００９３】
【数２９】
2010171758.tif 000031
【００９４】
【数３０】
2010171758.tif 000032
【００９５】
【数３１】
2010171758.tif 000033
【００９６】
【数３２】
2010171758.tif 000034
【００９７】
式（２４）は、ネットワーク輻輳率ｒを最小化することを示す目的関数である。式（２５）乃至（３２）は、この線形計画問題における制約条件を示している。式（２５）は、ノードｉが始点ノードでも終点ノードでもない場合、ノードｉに流入するトラヒックとノードｉから流出するトラヒックとは等しいことを示している。式（２６）は、ノードｉがエッジノード（例えば、始点ノードｐ）である場合、ノードｉから流出するトラヒックの総和は１であることを示している。すなわち、式（２５），（２６）は、有向グラフにおけるフロー保存則を表している。式（２７）は、リンクlink(i,j)を通過するトラヒックの総和は、ネットワーク輻輳率ｒとリンクlink(i,j)の容量cijとの積以下であることを示している。式（２８）は、所定の始点ノードｐからネットワークへ流出するトラヒック量の総量は、上限値αp以下であることを示しており、式（２９）は、ネットワークから所定の終点ノードｑへ流入するトラヒック量の総量は、上限値βq以下であることを示している。また、式（３０）は、オペレータの入力操作等による上限値γpqおよび下限値δpqに基づいたトラヒック量dpqのとり得る範囲の制限を示している。そして、式（３１）は、始点ノードｐから終点ノードｑまで流れるトラヒックのうちのリンクlink(i,j)を通過するトラヒックの割合xpqijが、式（３２）は、ネットワーク輻輳率ｒが、それぞれ０乃至１の範囲であることを示している。
【００９８】
しかしながら、式（７）乃至（１５）を参照して説明した場合と同様、ホースモデルにおいて、始点ノードｐと終点ノードｑとの全ての組み合わせについてトラヒック行列T={dpq}を得ることは容易ではない。
【００９９】
そこで、ステップＳ１３において、制約条件変換部９２は、制約条件変換処理を実行することで、式（２７）乃至（３０）で示される制約条件を、双対定理を用いて、正確に得ることが容易でないトラヒック量dpqを用いない制約条件に変換する。
【０１００】
より具体的には、制約条件変換部９２は、上述したJ. Chu and C. Lee, “Optimal Link Weights for Maximizing QoS Traffic”, IEEE ICC 2007, pp.610-615, 2007.における、ホースモデルに対する解法を拡張し、以下に示される式（３３）および式（３４）の関係（以下、適宜、制約条件変換条件という）を得ることで、制約条件変換処理を実行する。
【０１０１】
【数３３】
2010171758.tif 000035
【０１０２】
【数３４】
2010171758.tif 000036
【０１０３】
式（３３）および式（３４）において、パラメータπij(p)，λij(p)，ηij(p,q)、およびθij(p,q)は、全てのノードの組(i,j)に対して一意に決まるパラメータである。式（３３）および式（３４）は、上述のJ. Chu and C. Lee, “Optimal Link Weights for Maximizing QoS Traffic”, IEEE ICC 2007, pp.610-615, 2007.に基づいた、以下に示す証明によって得られる。
【０１０４】
［制約条件変換条件導出の証明］
リンクlink(i,j)を通過するトラヒックの総和が最大となるトラヒック行列T={dpq}を得る問題は、以下の式（３５）乃至（３８）で示す線形計画問題によって表される。
【０１０５】
目的関数：
【数３５】
2010171758.tif 000037
【０１０６】
制約条件：
【数３６】
2010171758.tif 000038
【０１０７】
【数３７】
2010171758.tif 000039
【０１０８】
【数３８】
2010171758.tif 000040
【０１０９】
式（３５）は、リンクlink(i,j)を通過するトラヒックの総和を最大化することを示す目的関数である。式（３６）は、所定の始点ノードｐからネットワークへ流出するトラヒック量の総量は、上限値αp以下であることを示しており、式（３７）は、ネットワークから所定の終点ノードｑへ流入するトラヒック量の総量は、上限値βq以下であることを示している。また、式（３８）は、オペレータの入力操作等による上限値γpqおよび下限値δpqに基づいたトラヒック量dpqのとり得る範囲の制限を示している。
【０１１０】
次に、上述の式（３５）乃至（３８）で示されるリンクlink(i,j)についての線形計画問題に対して、双対定理を適用する。双対定理は、ある線形計画問題を主問題とし、これに双対する補問題を双対問題としたときに、主問題と双対問題のいずれか一方が最適解を持つならば、もう一方も最適解を持ち、主問題の最小値（または最大値）と双対問題の最大値（または最小値）とは一致する、と定義される。
【０１１１】
すなわち、式（３５）乃至（３８）で示される線形計画問題を主問題としたとき、その最適解として得られる最大値は、式（３５）乃至（３８）で示される線形計画問題の双対問題の最適解として得られる最小値と一致する。そこで、“Optimal Link Weights for Maximizing QoS Traffic”, IEEE ICC 2007, pp.610-615, 2007.における解法を拡張すれば、式（３５）乃至（３８）で示される線形計画問題の双対問題は、パラメータπij(p)，λij(p)，ηij(p,q)、およびθij(p,q)を用いて、以下の式（３９）乃至（４１）で表される。
【０１１２】
目的関数：
【数３９】
2010171758.tif 000041
【０１１３】
制約条件：
【数４０】
2010171758.tif 000042
【０１１４】
【数４１】
2010171758.tif 000043
【０１１５】
式（３９）は、式（３５）で示される目的関数に双対する目的関数を示している。式（４０），（４１）は、式（３９）で示される目的関数についての制約条件を示している。
【０１１６】
双対定理によれば、上述した２つの線形計画問題（主問題および双対問題）において、式（３５）乃至（３８）で示される主問題の最適解として得られる最大値は、式（３９）乃至（４１）で示される双対問題の最適解として得られる最小値と一致する。したがって、もともとの線形計画問題における制約条件である式（２７）より、式（３３）が成り立つ。また、上述の双対問題の制約条件である式（４０）は、式（３４）に等しい。
【０１１７】
次に、パラメータπij(p)，λij(p)，ηij(p,q)、およびθij(p,q)が、必要条件としての式（３３）および式（３４）を満たすことを説明する。
【０１１８】
式（３４）より、全てのエッジノードの組(p,q)について、以下の式（４２）が成り立つ。
【０１１９】
【数４２】
2010171758.tif 000044
【０１２０】
式（４２）において、最後の右辺は、最後から２番目の右辺で示されるモデルに対して、各項の上限値（または下限値）を考慮することで得られる。そして、上述の式（４２）および式（３３）より、以下の式（４３）が成り立つ。
【０１２１】
【数４３】
2010171758.tif 000045
【０１２２】
式（４３）は、その最初の右辺で示されるモデルにより制限された全ての組み合わせのトラヒック行列について、どのリンクにおけるトラヒック量（リンク使用率）も、多くとも、ネットワーク輻輳率ｒ以下であることを示しており、また、式（２７）も満たしている。以上のことより、パラメータπij(p)，λij(p)，ηij(p,q)、およびθij(p,q)は、式（３３）および式（３４）を満たしているといえる。
【０１２３】
［制約条件変換処理の詳細］
ここで、図４のフローチャートを参照して、ステップＳ１３の制約条件変換処理の詳細について説明する。
【０１２４】
ステップＳ３１において、抽出部９２ａは、制約条件取得部９１によって取得された制約条件のうちの所定の制約条件、具体的には、式（２７）乃至（３０）で示される制約条件を抽出する。
【０１２５】
ステップＳ３２において、変換条件算出部９２ｂは、抽出部９２ａによって抽出された制約条件に双対定理を適用することで、制約条件変換条件を求める。より具体的には、変換条件算出部９２ｂは、式（２７）の左辺における、リンクlink(i,j)を通過するトラヒック量dpqxpqijの総和を最大化する線形計画問題を、式（３９）乃至（４１）で示される双対問題に置き換えることで、式（３３），（３４）で示される制約条件変換条件を得る。
【０１２６】
ステップＳ３３において、変換部９２ｃは、変換条件算出部９２ｂによって求められた制約条件変換条件（式（３３），（３４））に基づいて、制約条件取得部９１によって取得された制約条件を変換する。すなわち、双対定理を適用して得られた式（３３）および式（３４）に基づいて、式（２４）乃至（３２）で示される線形計画問題において制約条件が変換された、式（４４）乃至（５１）で示される線形計画問題が得られる。
【０１２７】
目的関数：
【数４４】
2010171758.tif 000046
【０１２８】
制約条件：
【数４５】
2010171758.tif 000047
【０１２９】
【数４６】
2010171758.tif 000048
【０１３０】
【数４７】
2010171758.tif 000049
【０１３１】
【数４８】
2010171758.tif 000050
【０１３２】
【数４９】
2010171758.tif 000051
【０１３３】
【数５０】
2010171758.tif 000052
【０１３４】
【数５１】
2010171758.tif 000053
【０１３５】
以上の処理によれば、ホースモデルにおける制約条件を表す式（２７）乃至（３０）は、ノードの組(i,j)に対して一意的なパラメータπij(p)，λij(p)，ηij(p,q)、およびθij(p,q)を用いて、式（４７）乃至（４９）に変換される。
【０１３６】
具体的には、式（４７）は、式（２７）の左辺における、リンクlink(i,j)を通過するトラヒック量dpqxpqijが、制約条件変換条件である式（３３），（３４）を基に、パラメータπij(p)，λij(p)，ηij(p,q)、およびθij(p,q)、上限値αp，βp、並びにオペレータの入力操作等によるトラヒック量dpqの上限値γpqおよび下限値δpqを用いた項に置き換えられていることを示している。また、式（４８），（４９）は、式（４７）の関係を成立させるための条件を示している。なお、式（４４）乃至（４６），（５０），（５１）は、それぞれ、式（２４）乃至（２６），（３１），（３２）に対応する。
【０１３７】
図３のフローチャートの説明に戻り、ステップＳ１４において、線形計画問題計算部９３は、制約条件変換部９２によって変換された後の制約条件（式（４５）乃至（５１））に基づいて、線形計画問題を解くことで、ネットワーク輻輳率ｒの最小値を求め、ネットワーク内の各リンクにおける最適なリソースを計算する。
【０１３８】
ステップＳ１５において、リソース割当部７２は、リソース計算部７１の計算結果であるネットワーク内の各リンクにおけるリソースと、リソース情報記憶部５４に記憶されているリソース情報によって示されるリソースとの差分を基に、ネットワーク内の各リンクに対して、リソースを割り当てる。
【０１３９】
ステップＳ１６において、経路計算部７３は、リソース割当部７２によって割り当てられたリソースに基づいて、ネットワーク内のノード間の経路を計算し、その結果を経路情報として通信部３４や経路情報記憶部５２に供給する。
【０１４０】
以上の処理によれば、始点ノードｐから終点ノードｑまでのトラヒック量dpqに対して上限値γpqおよび下限値δpqを設けた上下限値追加ホースモデルについての線形計画問題において、双対定理を用いて制約条件を変換することにより、制約条件が、正確な値を得ることが容易でないとされたトラヒック量dpqを用いずに、ノードの組(i,j)に対して一意的なパラメータπij(p)，λij(p)，ηij(p,q)、およびθij(p,q)を用いて表現されるようになった。これにより、最適解としてのネットワーク輻輳率が最小となる上下限値追加ホースモデルを決定することができ、その上下限値追加ホースモデルについての線形計画問題を解くことが可能になった。また、上下限値追加ホースモデルにおいては、トラヒック量dpqのとり得る範囲が適切に制限されることで、そのモデルの正確性を高めることが可能となった。したがって、より利用効率の高いネットワークリソースを割り当てることが可能となった。
【０１４１】
なお、上述した説明においては、始点ノードｐから終点ノードｑまでのトラヒック量dpqに対して上限値γpqおよび下限値δpqの両方を設けた上下限値追加ホースモデルについての線形計画問題を解くようにしたが、トラヒック量dpqに対して上限値γpqのみを設けた上限値追加ホースモデルについての線形計画問題を解くようにしてもよい。すなわち、上限値追加ホースモデルについての線形計画問題において、双対定理を用いて制約条件を変換することにより、制約条件が、正確な値を得ることが容易でないとされたトラヒック量dpqを用いずに、ノードの組(i,j)に対して一意的なパラメータπij(p)，λij(p)、およびηij(p,q)を用いて表現されるようになり、最適解としてのネットワーク輻輳率が最小となる上限値追加ホースモデルが決定されることで、その上限値追加ホースモデルについての線形計画問題を解くことが可能となる。また、上限値追加ホースモデルにおいては、トラヒック量dpqのとり得る範囲が適切に制限されることで、そのモデルの正確性を高めることが可能となり、より利用効率の高いネットワークリソースを割り当てることが可能となる。
【０１４２】
また、同様にして、トラヒック量dpqに対して下限値δpqのみを設けた下限値追加ホースモデルについての線形計画問題を解くようにしてもよい。すなわち、下限値追加ホースモデルについての線形計画問題において、双対定理を用いて制約条件を変換することにより、制約条件が、正確な値を得ることが容易でないとされたトラヒック量dpqを用いずに、ノードの組(i,j)に対して一意的なパラメータπij(p)，λij(p)、およびθij(p,q)を用いて表現されるようになり、最適解としてのネットワーク輻輳率が最小となる下限値追加ホースモデルが決定されることで、その下限値追加ホースモデルについての線形計画問題を解くことが可能となる。また、下限値追加ホースモデルにおいても、トラヒック量dpqのとり得る範囲が適切に制限されることで、そのモデルの正確性を高めることが可能となり、より利用効率の高いネットワークリソースを割り当てることが可能となる。
【０１４３】
［シミュレーションとその結果］
次に、上述した上下限値追加ホースモデルを所定のネットワークに適用した場合のシミュレーションと、ネットワーク輻輳率のシミュレーション結果について説明する。
【０１４４】
Ｎ個のノードを有するネットワークに対して、全てのノードが接続されるようにネットワークトポロジを生成し、平均ノード次数（自ノードから隣接ノードへ接続しているリンクの数）Ｄを満足するという条件の下で、100パターンのネットワークトポロジをシミュレーションにより生成し、ネットワーク輻輳率ｒの平均値を算出する。
【０１４５】
なお、シミュレーションにおいては、リンクの容量cijを80乃至120の範囲で、トラヒック量dpqを０乃至100の範囲で、それぞれ一様分布となるようにした。また、一様分布となるトラヒック量dpqを用いて、上下限値追加ホースモデルの制約条件におけるパラメータを、αp=Σqdpq，βq=Σpdpq，γpq=(1/μ)dpq、およびδpq=νdpqとする。なお、パラメータμは０＜μ≦１の範囲の値をとり、パラメータνは０≦ν≦１の範囲の値をとるものとする。
【０１４６】
ここで、図５を参照して、上下限値追加ホースモデルにおいて、パラメータμ，νを変化させたときのネットワーク輻輳率ｒの算出結果について説明する。
【０１４７】
図５において、横軸はパラメータμを示しており、縦軸はネットワーク輻輳率ｒを示している。図５においては、ネットワーク輻輳率ｒは、ホースモデルのネットワーク輻輳率で正規化されている。すなわち、図５においては、ホースモデルのネットワーク輻輳率ｒHを１としたときの、上下限値追加ホースモデルのネットワーク輻輳率ｒA、および、パイプモデルのネットワーク輻輳率ｒPが示されている。また、図５において、上下限値追加ホースモデルのネットワーク輻輳率ｒAは、パラメータνが0.0のとき（黒塗りの丸印）、0.4のとき（白抜きの四角印）、および、0.8のとき（黒塗りの四角印）の３パターンで示されている。なお、図５の算出結果を得る際、ノード数N=8、平均ノード次数D=4としている。
【０１４８】
図５に示されるように、パラメータμ，νの全ての値において、ｒP≦ｒA≦ｒHとなっている。パラメータμ，νがそれぞれ１に近づくと、上下限値追加ホースモデルのネットワーク輻輳率ｒAは、パイプモデルのネットワーク輻輳率ｒPに近づき、パラメータμ，νがそれぞれ０に近づくと、上下限値追加ホースモデルのネットワーク輻輳率ｒAは、ホースモデルのネットワーク輻輳率ｒHに近づいている。また、パラメータμが十分小さい値のとき、上下限値追加ホースモデルのネットワーク輻輳率ｒAは、パラメータμに依存せず、ほとんど変化しない。これは、パラメータμが十分小さい値のときには、追加で設定される上限値γpq（=(1/μ)dpq）が十分大きな値となるので、トラヒック行列T={dpq}（トラヒック量dpq）は、上限値γpqでなく、ホースモデルにおける上限値αp，βqに制約されるためである。
【０１４９】
このように、上下限値追加ホースモデルにおいて、トラヒック行列T={dpq}を構成するトラヒック量dpqのとり得る範囲を制限する際に、ネットワーク事業者のオペレータが適切なパラメータμ，νを設定することで、上下限値追加ホースモデルのネットワーク輻輳率ｒAを、従来のホースモデルのネットワーク輻輳率ｒHより小さい値に調整することが可能となる。したがって、より利用効率の高いネットワークリソースを割り当てることができるようになる。
【０１５０】
上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウェアにより実行することもできる。一連の処理をソフトウェアにより実行する場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータ等に、プログラム記録媒体からインストールされる。
【０１５１】
図６は、上述した一連の処理をプログラムにより実行するコンピュータのハードウェアの構成例を示すブロック図である。
【０１５２】
コンピュータにおいて、CPU（Central Processing Unit）９０１，ROM（Read Only Memory）９０２，RAM（Random Access Memory）９０３は、バス９０４により相互に接続されている。
【０１５３】
バス９０４には、さらに、入出力インタフェース９０５が接続されている。入出力インタフェース９０５には、キーボード、マウス、マイクロホン等よりなる入力部９０６、ディスプレイ、スピーカ等よりなる出力部９０７、ハードディスクや不揮発性のメモリ等よりなる記憶部９０８、ネットワークインタフェース等よりなる通信部９０９、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリ等のリムーバブルメディア９１１を駆動するドライブ９１０が接続されている。
【０１５４】
以上のように構成されるコンピュータでは、CPU９０１が、例えば、記憶部９０８に記憶されているプログラムを、入出力インタフェース９０５およびバス９０４を介して、RAM９０３にロードして実行することにより、上述した一連の処理が行われる。
【０１５５】
コンピュータ（CPU９０１）が実行するプログラムは、例えば、磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disc-Read Only Memory),DVD(Digital Versatile Disc)等）、光磁気ディスク、もしくは半導体メモリ等よりなるパッケージメディアであるリムーバブルメディア９１１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供される。
【０１５６】
そして、プログラムは、リムーバブルメディア９１１をドライブ９１０に装着することにより、入出力インタフェース９０５を介して、記憶部９０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部９０９で受信し、記憶部９０８にインストールすることができる。その他、プログラムは、ROM９０２や記憶部９０８に、あらかじめインストールしておくことができる。
【０１５７】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１５８】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０１５９】
１１  経路計算装置，  １２−１乃至１２−４  ノード，  ３１  入出力部，  ３２  記憶部，  ３３  制御部，  ３４  通信部，  ５１  トポロジ情報記憶部，  ５２  経路情報記憶部，  ５３  トラヒック量記憶部，  ５４  リソース情報記憶部，  ７１  リソース計算部，  ７２  リソース割当部，  ７３  経路計算部，  ９１  制約条件取得部，  ９２  制約条件変換部，  ９２ａ  抽出部，  ９２ｂ  変換条件算出部，  ９２ｃ  変換部，  ９３  線形計画問題計算部
【図１】
2010171758.tif 000054
【図２】
2010171758.tif 000055
【図３】
2010171758.tif 000056
【図４】
2010171758.tif 000057
【図５】
2010171758.tif 000058
【図６】
2010171758.tif 000059