(57)【要約】【課題】  網リソースの利用効率を高めるようなネットワークのリソース割り当てを計算すること。【解決手段】  プロバイダエッジ装置ＰＥ間のトラヒック量上限、ならびに、各プロバイダエッジ装置ＰＥに流入および流出するトラヒック量上限によって規定される契約の対象となる所定のネットワークにおいて、ネットワークに割り当てるリソースを計算するリソース算出装置であって、所定のネットワークのネットワークトポロジおよび契約を示すプロファイルを記憶する記憶手段と、ネットワークトポロジからプロバイダエッジ装置ＰＥ間の経路を計算する経路計算手段１２と、契約から定義される制約条件を満たすように、経路上のリンクに割り当てるリソースを計算するリンクリソース計算手段１４と、を含めて構成されることを特徴とする。【選択図】      図２
2006054722.tif 000002
【特許請求の範囲】
【請求項１】
プロバイダエッジ装置間のトラヒック量上限、ならびに、各プロバイダエッジ装置に流入および流出するトラヒック量上限によって規定される契約の対象となる所定のネットワークにおいて、ネットワークに割り当てるリソースを計算するリソース算出装置であって、
前記所定のネットワークのネットワークトポロジおよび前記契約を示すプロファイルを記憶する記憶手段と、
前記ネットワークトポロジから前記プロバイダエッジ装置間の経路を計算する経路計算手段と、
前記契約から定義される制約条件を満たすように、前記経路上のリンクに割り当てるリソースを計算するリンクリソース計算手段と、を含めて構成されることを特徴とするリソース算出装置。
【請求項２】
前記経路計算手段は、前回の評価値となる経路から、今回の評価値となる経路の候補を生成し、その候補の評価値が前回の評価値を上回る時に、その候補を今回の評価値となる経路として採用する処理を繰り返し、前回の評価値と今回の評価値とを比較して評価値が上昇しなくなると繰り返しを終了することを特徴とする請求項１に記載のリソース算出装置。
【請求項３】
前記経路計算手段は、前回の評価値となる経路から、今回の評価値となる経路の候補を生成し、その候補の評価値が、前回の評価値より上回るのであれば、その候補を今回の評価値となる経路として採用し、一方、その候補の評価値が、前回の評価値より上回らないのであれば、その候補を今回の評価値となる経路として採用するかどうかは、所定の確率によって決定される処理を繰り返し、評価値となる経路が所定の回数だけ連続して変更されない場合には、これ以上評価値を改良する余地がないとして、繰り返しを終了することを特徴とする請求項１に記載のリソース算出装置。
【請求項４】
前記リンクリソース計算手段は、前記ネットワークトポロジから後記の（ａ）（ｂ）（ｃ）の作成手順によって作成される所定のグラフにおいて、後記の（ｄ）の最大フロー問題を解くことによって得られる解をリソースとして算出することを特徴とする請求項１ないし請求項３のいずれか１項に記載のリソース算出装置。
（ａ）Ｎをプロバイダエッジ装置数とすると、始点ノード→入側のプロバイダエッジ装置群→出側のプロバイダエッジ装置群→終点ノード、の順に接続するノード数２Ｎ＋２のグラフを構成する
（ｂ）始点ノード→入側のプロバイダエッジ装置群の間の帯域を、前記契約として指定された流入トラヒック量上限とし、出側のプロバイダエッジ装置群→終点ノードの間の帯域を、前記契約として指定された流出トラヒック量上限とする
（ｃ）入側のプロバイダエッジ装置群→出側のプロバイダエッジ装置群の帯域を、前記契約として指定されたプロバイダエッジ装置間のトラヒック量上限とする
（ｄ）始点ノード→終点ノードの最大フロー問題
【請求項５】
前記リンクリソース計算手段は、前記プロファイルを元に生成される条件式を満たしつつ、割り当てるリソースを示す所定の目的関数を最適化するような線形計画問題を解くアルゴリズムを実行し、
リンクｉ→ｊで仮想網に割り当てるべきリソース量として、プロバイダエッジ装置数をＮ、Ｆ（ｘ、ｙ）を変数とすると、前記所定の目的関数の最適化は、プロバイダエッジ装置ｘ→ｙ間経路がリンクｉ→ｊを通っている（ｘ、ｙ）について、Ｆ（ｘ、ｙ）の合計を最大化することとし、前記条件式は、後記（１）〜（３）とすることを特徴とする請求項１ないし請求項３のいずれか１項に記載のリソース算出装置。
（１）０≦Ｆ（ｘ、ｙ）≦（該仮想網の契約として指定されたプロバイダエッジ装置ｘ→プロバイダエッジ装置ｙ間のトラヒック量上限）
（２）任意のプロバイダエッジ装置ａについて、Ｆ（ａ、ｚ）（０≦ｚ≦Ｎ）のｚに関する和が、該仮想網の契約として指定されたプロバイダエッジ装置ａへの流入トラヒック量上限以下になること
（３）任意のプロバイダエッジ装置ａについて、Ｆ（ｚ、ａ）のｚに関する和が、該仮想網の契約として指定されたプロバイダエッジ装置ａからの流出トラヒック量上限以下になること
【請求項６】
前記リソース算出装置は、前記リンクリソース計算手段によって算出されたリソースを、所定のネットワークに割り当てるように制御するリソース割り当て手段を、さらに含めて構成されることを特徴とする請求項１ないし請求項５のいずれか１項に記載のリソース算出装置。
【請求項７】
前記リソース算出装置は、前記契約対象者に関するトラヒックが、前記契約によるトラヒック量上限を守っているかどうかを判断し、トラヒック量上限を超えるトラヒックが通信されることを抑制するように前記所定のネットワークを制御する受付制御手段を、さらに含めて構成されることを特徴とする請求項１ないし請求項６のいずれか１項に記載のリソース算出装置。
【請求項８】
プロバイダエッジ装置間のトラヒック量上限、ならびに、各プロバイダエッジ装置に流入および流出するトラヒック量上限によって規定される契約の対象となる所定のネットワークにおいて、ネットワークに割り当てるリソースを計算するリソース算出方法であって、
コンピュータが、前記所定のネットワークのネットワークトポロジおよび前記契約を示すプロファイルを記憶手段に記憶する手順と、前記ネットワークトポロジから前記プロバイダエッジ装置間の経路を計算する手順と、前記契約から定義される制約条件を満たすように、前記経路上のリンクに割り当てるリソースを計算する手順と、を実行することを特徴とするリソース算出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リソース算出装置およびリソース算出方法に関する。
【背景技術】
【０００２】
ＶＰＮ（Virtual Private Network）などの仮想網サービスを提供するネットワーク事業者において、ユーザとの契約内容に応じて、仮想網ごとに割り当てるネットワークリソース（帯域）の計算方法には、前提となる契約のモデルとしてホースモデルとパイプモデルがあり、それぞれのモデルに対して、リソース割り当て方法がある（非特許文献１、非特許文献２）。
【０００３】
まず、ホースモデルは、プロバイダエッジ装置への流入／流出トラヒック上限のみをカスタマと契約するモデルである。ホースモデルに対するリソース割り当て方法は、ユーザ側の装置（カスタマエッジ装置）を収容する事業者側のエッジ装置（プロバイダエッジ装置）への流入／流出トラヒックの上限値のみを契約で規定して帯域を割り当てる計算方法である。具体的には、ツリー構成のトポロジーを作り、ツリー上の各リンクで割り当てるべきリソースを計算する方法である。そして、流入／流出上限以内であれば、どのプロバイダエッジ装置間のトラヒックであっても許容する。
【０００４】
一方、パイプモデルとは、プロバイダエッジ装置間のトラヒック上限のみをカスタマと契約するモデルである。このモデルに対するリソース割り当て計算方法としては、プロバイダエッジ装置間トラヒックの上限のみを契約で規定して帯域を割り当てる計算方法がある。つまり、プロバイダエッジ装置間の最短経路を計算し、最短経路上にリソースを割り当てる方法である。
【非特許文献１】A.Juttner at al.,"On bandwidth efficiency of the hose resource management model in virtual private networks",IEEE INFOCOM 2003.
【非特許文献２】A.Kumar et al.,"Algorithms of provisioning virtual private networks in the hose model",IEEE Trans.Networking,Aug.2002.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、トラヒックパターンが数パターン（例えば昼夜）想定できる場合には、プロバイダエッジ装置への流入／流出トラヒック上限、および、プロバイダエッジ装置間トラヒック上限、という２種類の上限を組み合わせて表されるトラヒック契約を結ぶことが想定される。
【０００６】
しかしながら、従来のモデルでは、プロバイダエッジ装置間のトラヒックパターンが固定的か（パイプモデル）、全くの任意か（ホースモデル）、という極端な前提をとっている。つまり、従来のモデルおよびそのためのリソース割り当て方法は、いずれも１種類の上限により表させることを前提としているため、２種類の上限により表される契約を結ぶ際には、適さない。
【０００７】
具体的には、ホースモデルのためのリソース割り当て方法では、前記で表される契約に対して、プロバイダエッジ装置間のトラヒック上限を考慮しない。そのため、ホースモデルではプロバイダエッジ装置間のトラヒックは上限値を規定せず、プロバイダエッジ装置から流入する可能性のある最大のトラヒックを想定して網のリソースを確保する。そのため、その最大値が実際の契約値よりも上回った場合、上回った分の網のリソースが、本来確保する必要のない余分なリソースとなってしまう。その上、従来のホースモデルに対するリソース割り当て方法は、ツリー構成を前提としており、必ずしも最適解（契約を守りつつ最小となるリソース）を得ることができない。
【０００８】
パイプモデルでは逆にプロバイダエッジ装置への流入／流出トラヒックを考慮しないため、その流入／流出トラヒックを、プロバイダエッジ装置間の最大値と想定して、網のリソースを確保している。その場合にも、やはり最大値と契約値との差分が、余分に確保されたリソースとなっていた。そのため、契約で使用されないリソースが無駄に確保されてしまうことで、網リソースの利用効率が低いという問題点があった。
【０００９】
そこで、本発明は、前記した問題を解決し、網リソースの利用効率を高めるようなネットワークのリソース割り当てを計算することを主な目的とする。
【課題を解決するための手段】
【００１０】
前記課題を解決するため、本発明は、プロバイダエッジ装置間のトラヒック量上限、ならびに、各プロバイダエッジ装置に流入および流出するトラヒック量上限によって規定される契約の対象となる所定のネットワークにおいて、ネットワークに割り当てるリソースを計算するリソース算出装置であって、前記所定のネットワークのネットワークトポロジおよび前記契約を示すプロファイルを記憶する記憶手段と、前記ネットワークトポロジから前記プロバイダエッジ装置間の経路を計算する経路計算手段と、前記契約から定義される制約条件を満たすように、前記経路上のリンクに割り当てるリソースを計算するリンクリソース計算手段と、を含めて構成されることを特徴とする。
【００１１】
これにより、プロバイダエッジ装置間のトラヒック上限およびプロバイダエッジ装置への流入／流出トラヒック上限の両方を考慮した上で、なるべく、網全体の消費リソースが少なくなるように、リソースを計算することで、ネットワークに割り当てるリソースを削減することができる。
【００１２】
本発明は、前記経路計算手段が、前回の評価値となる経路から、今回の評価値となる経路の候補を生成し、その候補の評価値が前回の評価値を上回る時に、その候補を今回の評価値となる経路として採用する処理を繰り返し、前回の評価値と今回の評価値とを比較して評価値が上昇しなくなると繰り返しを終了することを特徴とする。
【００１３】
これにより、評価値は計算の度に徐々に上昇することはあっても、下降することはない。それにより、計算が早く収束するので、計算が終了するまでに計算を繰り返す回数が少なくて済み、早く計算結果を得ることが出来る。
【００１４】
本発明は、前記経路計算手段が、前回の評価値となる経路から、今回の評価値となる経路の候補を生成し、その候補の評価値が、前回の評価値より上回るのであれば、その候補を今回の評価値となる経路として採用し、一方、その候補の評価値が、前回の評価値より上回らないのであれば、その候補を今回の評価値となる経路として採用するかどうかが、所定の確率によって決定される処理を繰り返し、評価値となる経路が所定の回数だけ連続して変更されない場合には、これ以上評価値を改良する余地がないとして、繰り返しを終了することを特徴とする。
【００１５】
これにより、評価値は計算の度に上昇することもあるし、下降することもある。それにより、狭い範囲での最適解（局所最適解）を発見しても計算が続けられることで、全体最適となる解を発見する可能性があり、評価値の高い計算結果を得ることが出来る。
【００１６】
本発明は、前記リンクリソース計算手段が、前記ネットワークトポロジから後記の（ａ）（ｂ）（ｃ）の作成手順によって作成される所定のグラフにおいて、後記の（ｄ）の最大フロー問題を解くことによって得られる解をリソースとして算出することを特徴とする。（ａ）Ｎをプロバイダエッジ装置数とすると、始点ノード→入側のプロバイダエッジ装置群→出側のプロバイダエッジ装置群→終点ノード、の順に接続するノード数２Ｎ＋２のグラフを構成する（ｂ）始点ノード→入側のプロバイダエッジ装置群の間の帯域を、前記契約として指定された流入トラヒック量上限とし、出側のプロバイダエッジ装置群→終点ノードの間の帯域を、前記契約として指定された流出トラヒック量上限とする（ｃ）入側のプロバイダエッジ装置群→出側のプロバイダエッジ装置群の帯域を、前記契約として指定されたプロバイダエッジ装置間のトラヒック量上限とする（ｄ）始点ノード→終点ノードの最大フロー問題
【００１７】
これにより、ネットワークの経路がツリー構成ではない場合においても、各リンクのリソースを計算することができる。また、プロバイダエッジ装置間のトラヒック上限およびプロバイダエッジ装置への流入／流出量上限の両方を考慮して各リンクのリソースを計算することができる。
【００１８】
本発明は、前記リンクリソース計算手段が、前記プロファイルを元に生成される条件式を満たしつつ、割り当てるリソースを示す所定の目的関数を最適化するような線形計画問題を解くアルゴリズムを実行し、リンクｉ→ｊで仮想網に割り当てるべきリソース量として、プロバイダエッジ装置数をＮ、Ｆ（ｘ、ｙ）を変数とすると、前記所定の目的関数の最適化が、プロバイダエッジ装置ｘ→ｙ間経路がリンクｉ→ｊを通っている（ｘ、ｙ）について、Ｆ（ｘ、ｙ）の合計を最大化することとし、前記条件式が、後記（１）〜（３）とすることを特徴とする。（１）０≦Ｆ（ｘ、ｙ）≦（該仮想網の契約として指定されたプロバイダエッジ装置ｘ→プロバイダエッジ装置ｙ間のトラヒック量上限）（２）任意のプロバイダエッジ装置ａについて、Ｆ（ａ、ｚ）（０≦ｚ≦Ｎ）のｚに関する和が、該仮想網の契約として指定されたプロバイダエッジ装置ａへの流入トラヒック量上限以下になること（３）任意のプロバイダエッジ装置ａについて、Ｆ（ｚ、ａ）のｚに関する和が、該仮想網の契約として指定されたプロバイダエッジ装置ａからの流出トラヒック量上限以下になること
【００１９】
これにより、ネットワークの経路がツリー構成ではない場合においても、各リンクのリソースを計算することができる。また、プロバイダエッジ装置間のトラヒック上限およびプロバイダエッジ装置への流入／流出量上限の両方を考慮して各リンクのリソースを計算することができる。
【００２０】
本発明は、前記リソース算出装置が、前記リンクリソース計算手段によって算出されたリソースを、所定のネットワークに割り当てるように制御するリソース割り当て手段を、さらに含めて構成されることを特徴とする。
【００２１】
これにより、契約を元に計算した効率的なリソースを、ネットワークの運用に反映させることができる。
【００２２】
本発明は、前記リソース算出装置が、前記契約対象者に関するトラヒックが、前記契約によるトラヒック量上限を守っているかどうかを判断し、トラヒック量上限を超えるトラヒックが通信されることを抑制するように前記所定のネットワークを制御する受付制御手段を、さらに含めて構成されることを特徴とする。
【００２３】
これにより、契約違反となるトラヒックをネットワークから除外出来るので、円滑なネットワークの運用が可能となる。
【００２４】
本発明は、プロバイダエッジ装置間のトラヒック量上限、ならびに、各プロバイダエッジ装置に流入および流出するトラヒック量上限によって規定される契約の対象となる所定のネットワークにおいて、ネットワークに割り当てるリソースを計算するリソース算出方法であって、コンピュータが、前記所定のネットワークのネットワークトポロジおよび前記契約を示すプロファイルを記憶手段に記憶する手順と、前記ネットワークトポロジから前記プロバイダエッジ装置間の経路を計算する手順と、前記契約から定義される制約条件を満たすように、前記経路上のリンクに割り当てるリソースを計算する手順と、を実行することを特徴とする。
【００２５】
これにより、プロバイダエッジ装置間のトラヒック上限およびプロバイダエッジ装置への流入／流出トラヒック上限の両方を考慮した上で、なるべく、網全体の消費リソースが少なくなるように、リソースを計算することで、ネットワークに割り当てるリソースを削減することができる。
【発明の効果】
【００２６】
本発明は、２種類の契約から生成される制約を同時に満たすようにリソースを計算することを特徴とする。これにより、プロバイダエッジ装置間のトラヒック上限およびプロバイダエッジ装置への流入／流出トラヒック上限の両方を考慮した上で、なるべく、網全体の消費リソースが少なくなるように、リソースを計算することで、ネットワークに割り当てるリソースを最低必要な分は確保しつつ、無駄な分を削減することができる。よって、網リソースの利用効率を高めるようなネットワークのリソース割り当てを計算することが、可能となる。
【発明を実施するための最良の形態】
【００２７】
次に、本発明の実施の形態について図面を参照して説明する。
【００２８】
図１は、本発明の一実施形態が適用されるネットワーク構成を示している。このネットワークは、一つ以上のカスタマを同一の網に収容しながら、同一カスタマのカスタマエッジ装置ＣＥ間にのみの通信を可能とするものである。ここで、カスタマとは、網の管理者と異なる管理者であっても、同じ管理者であっても構わない。
【００２９】
よって、図１に示すネットワークは、１つのプロバイダ網と、２つの仮想網（＃１，＃２）とが接続されているものである。そして、ある仮想網に属する装置は、同じ仮想網に属する装置と通信することができるが、別の仮想網に属する装置とは、通信することは、出来ない。これは、仮想網が、ＶＰＮであることを意味する。そして、同じ仮想網に属する装置が、互いに物理的に離れた位置に存在する場合、それらの装置間の通信は、プロバイダ網を中継して行われる。そして、仮想網ごとの契約を守りつつ、かつ、ネットワーク全体で確保すべきリソースをなるべく少なくするような、仮想網リソース割り当ての方式を提案することが、本実施形態の主な特徴である。
【００３０】
図１のＣＥ（Customer Edge）とは、カスタマエッジ装置ＣＥを意味する。カスタマエッジ装置ＣＥは、カスタマが所有し、一つ以上のＰＥ（Provider Edge）と接続されている。このＰＥとは、プロバイダエッジ装置ＰＥを意味する。プロバイダエッジ装置ＰＥは、プロバイダが所有し、一つ以上のカスタマエッジ装置ＣＥと接続されている。Ｐ（Provider）とは、プロバイダ装置Ｐを意味する。プロバイダ装置Ｐは、プロバイダが所有し、プロバイダエッジ装置ＰＥもしくは他のプロバイダ装置Ｐと接続されている。リンクとは、カスタマエッジ装置ＣＥ−プロバイダエッジ装置ＰＥ、プロバイダエッジ装置ＰＥ−プロバイダ装置Ｐ、プロバイダエッジ装置ＰＥ−プロバイダエッジ装置ＰＥ間に存在し、情報転送の媒体となる。プロバイダエッジ装置ＰＥ、プロバイダ装置Ｐ、リンクにより構成されるプロバイダ網は、同一仮想網内のカスタマエッジ装置ＣＥ間にのみ、通信を可能とする。
【００３１】
カスタマエッジ装置ＣＥ、プロバイダエッジ装置ＰＥ、プロバイダ装置Ｐとしては、例えば、ルータやＬ２ＳＷ（Layer 2 Switch）、ＴＤＭ（Time Division Multiplexing）クロスコネクト、波長クロスコネクト、ＭＰＬＳ（MultiProtocol Label Switching）のＬＳＲ（Label Switch Router）、などが相当する。
【００３２】
図２は、リソース算出装置の構成を示している。なお、リソース算出装置は、演算処理を行う際に用いられる記憶手段としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータとして構成される。なお、メモリは、ＲＡＭ（Random Access Memory）などにより構成される。演算処理は、ＣＰＵ（Central Processing Unit）によって構成される演算処理装置が、メモリ上のプログラムを実行することで、実現される。
【００３３】
仮想網ごとの契約の一例として、流入トラヒック量上限とは、該プロバイダエッジ装置ＰＥへの流入トラヒック量の上限を示す。流出トラヒック量上限とは、該プロバイダエッジ装置ＰＥからの流出トラヒック量の上限を示す。流入トラヒック量とは、該プロバイダエッジ装置ＰＥへの現在の流入トラヒック量を示す。
【００３４】
仮想網ごとの契約の別の一例として、ＰＥ間トラヒック量上限とは、該プロバイダエッジ装置ＰＥ間のトラヒック量の上限を示す。なお、ＰＥ−ＩＤ→ＰＥ−ＩＤとは、その間にリソースを確保すべきプロバイダエッジ装置ＰＥのペアを示し、→はトラヒックの流れる方向を示す。例えば、Ａ→Ｂとなっている場合、ＡからＢにトラヒックが流れる。
【００３５】
さらに、現在のトラヒック量として、流出トラヒック量とは、該プロバイダエッジ装置ＰＥからの現在の流出トラヒック量を示す。ＰＥ間トラヒック量とは、該プロバイダエッジ装置ＰＥ間の現在のトラヒック量を示す。
【００３６】
網トポロジーＤＢ２２は、プロバイダ網のトポロジー情報を格納するものである。リンクＩＤとは、リンクを一意に識別する情報である。上流装置ＩＤとは、リンクの上流側の装置（ある装置から見て、トラヒックが流入される相手となる装置）を一意に示す情報である。下流装置ＩＤとは、リンクの下流側の装置（ある装置から見て、トラヒックを流出する相手となる装置）を一意に示す情報である。この網トポロジーＤＢ２２では、ネットワークを構成する全ての装置およびそれらの装置間の全てのリンクを定義しているので、これらの定義された情報をもとに、図１などに示すネットワークトポロジを図示することができる。
【００３７】
経路ＤＢ２４は、各仮想網に対する、プロバイダエッジ装置ＰＥ間の経路を格納するものである。ＶＰＮ−ＩＤは、仮想網を一意に識別する情報である。ＰＥ−ＩＤ→ＰＥ−ＩＤとは、プロファイルＤＢ２６同様、その間にリソースを確保すべきプロバイダエッジ装置ＰＥのペアを示し、→はトラヒックの流れる方向を示す。リンクＩＤリストとは、リンクＩＤのリストであり、経路を示す。図１の例で、ＰＥ１→ＰＥ２の経路が、ＰＥ１→Ｐ１→ＰＥ２である場合、リンクＩＤリスとは、〈ＰＥ１、Ｐ１、ＰＥ２〉となる。
【００３８】
プロファイルＤＢ２６は、仮想網ごとの契約と、現在のトラヒック量を格納するものである。ＶＰＮ−ＩＤは、仮想網を一意に識別する情報である。ＰＥ−ＩＤとは、プロバイダエッジ装置ＰＥを一意に識別する情報であり、例えば、ＩＰアドレスが相当する。
【００３９】
リンクリソースＤＢ２８は、各仮想網に対する、各リンクでの割り当てリソース量を格納するものである。ＶＰＮ−ＩＤは、仮想網を一意に識別する情報である。リンクＩＤとは、リンクを一意に識別する情報である。リソース量とは、該仮想網の該リンクにおける割り当てリソース量を示す。
【００４０】
経路計算手段１２は、計算すべき仮想網を示すＶＰＮ−ＩＤを与えられると、該仮想網におけるプロバイダエッジ装置ＰＥ間の経路を計算するものである。リソース割り当て手段１６は、計算すべき仮想網を示すＶＰＮ−ＩＤを与えられると、該仮想網におけるプロバイダエッジ装置ＰＥ間の経路を計算するように指示し、経路ＤＢ２４に値を格納し、また、各リンクにおける割り当てリソース量を計算するように指示し、リンクリソースＤＢ２８に値を格納するものである。
【００４１】
受付制御手段１８は、ある仮想網に対して、プロバイダエッジ装置ＰＥ間にリソース増加要求があった場合、プロバイダエッジ装置ＰＥへの流入／流出トラヒック量上限以内であり、かつ該プロバイダエッジ装置ＰＥ間のトラヒック量上限以内である場合は、リソースの増加を許可するとともに、プロファイルＤＢ２６のトラヒック量を更新し、また、プロバイダエッジ装置ＰＥ間にリソース減少要求があった場合、プロファイルＤＢ２６のトラヒック量を更新することで、契約に従った受付制御を行うものである。なお、トラヒック量の更新は，プロファイルＤＢ２６のデータベースの中身（トラヒック量）を書き換える処理である。そして、受付処理手段１８の具体的な処理として、契約違反のトラヒックを除外する処理は、例えば、契約が１０Ｍｂｐｓのユーザが、１５Ｍｂｐｓのトラヒックを流した場合、契約違反となる５Ｍｂｐｓ分のトラヒックをネットワークの通信対象から除外するように、ネットワークの転送装置に指示するような処理である。
【００４２】
リソース割り当て手段１６は、リンクリソース計算手段１４によって計算されたリンクリソースをネットワークに割り当てる手段であり、例えば、ＳＮＭＰ（Simple Network Management Protocol）により実現される。
【００４３】
リンクリソース計算手段１４は、計算すべき仮想網を示すＶＰＮ−ＩＤと、計算すべきリンクを示すリンクＩＤを与えられると、該仮想網の該リンクにおける割り当てリソース量を計算するものである。このリンクリソース計算手段１４の構成については、後記において詳細に説明する。
【００４４】
以下、リンクリソース計算手段１４が行うリソース量計算方法について、２つ例示する。説明のため、図１の仮想網＃１の契約を図７（ａ）および図７（ｂ）に示す。
【００４５】
図３は、第１のリソース量計算方法を示す。つまり、図７（ａ）および図７（ｂ）であらわされる契約に対して、リンクリソース計算手段１４により、得られるノード数２Ｎ＋２のネットワークの構成を示している。なお、リンクの記号（Ｉ１，Ｉ２，Ｉ３，Ｏ１，Ｏ２，Ｏ３）は、図７に示したリソース量に対応する。ノード２−６、ノード２−７、ノード３−６、ノード３−７、ノード４−５、ノード４−６間については、プロバイダエッジ装置ＰＥ間の経路が注目リンクを通っている場合は、リンクが存在するが、通っていない場合は存在しない。例えば、注目リンクを図１のＰＥ１−Ｐ１とすると、ＰＥ１→ＰＥ２の経路は注目リンクを通っている場合、図３のノード２−６間にはリンクが存在する。なお、図３のノードと、図１のノードとの対応は、図３（ｂ）のようになっている。例えば、図３のノード２−３間は、図１でＰＥ１→ＰＥ２に対応することとなる。
【００４６】
第１のリソース量計算方法では、このようにして得られたネットワークにおいて、最大フロー問題を解くことで、該リンクにおけるリソース量を計算する。最大フロー問題を解く方法としては、ラベリング法やＰｒｅｆｌｏｗ−Ｐｕｓｈ法がある。
【００４７】
図８は、第２のリソース量計算方法を示す。第２の方法では、図８に示す線形計画問題を解くことで、該リンクにおけるリソース量を計算する。なお、線形計画問題は、例えば、シンプレックス法（単体法）によって、解を求めることができる。そして、算出するリソース量（例えば、帯域）は、図８の目的関数の値である。
【００４８】
次に、経路計算手段１２が行う経路計算方法について、図４ならびに図５および図６に示すフローチャートを参照しつつ、説明する。これらのフローチャートは、ヒューリスティック法の一例を示すものである。
【００４９】
図４は、プロバイダエッジ装置ＰＥ間の経路を計算する手順を、グリーディアルゴリズム（Greedy algorithm）により行うフローチャートを示している。このグリーディアルゴリズムは、初めから最高の評価値となるデータを算出するのではなく、初回の評価値となるデータから、徐々に評価値を上げるように計算を繰り返す、改良型のアルゴリズムである。そして、前回の評価値となるデータから、今回の評価値となるデータの候補を生成し、その候補の評価値が前回の評価値を上回る時に、その候補を今回の評価値となるデータとして採用する。さらに、前回の評価値と今回の評価値とを比較して評価値が上昇しなくなると、これ以上評価値を改良する余地がないとして、計算を終了することを特徴とする。
【００５０】
そのため、評価値は計算の度に徐々に上昇することはあっても、下降することはない。それにより、計算が早く収束するので、計算が終了するまでに計算を繰り返す回数が少なくて済み、早く計算結果を得ることができる。
【００５１】
リンクリソース計算手段１４は、各リンクについて、必要なリンクリソースを計算する。この値をＲ（１）とする（Ｓ１０１）。リンクリソース計算手段１４は、Ｓ１０１で求めたリンクリソースの全リンクでの合計を求める。この値をＲとする（Ｓ１０２）。経路計算手段１２は、変数ＭＩＮに大きな値を入力する（Ｓ１０３）。
【００５２】
リンクリソース計算手段１４は、プロバイダエッジ装置ＰＥ間のトラヒック上限が０より大きいプロバイダエッジ装置ＰＥｓｒｃ→ｄｓｔ間経路の一つに注目する（Ｓ１０４）。リンクリソース計算手段１４は、各リンクについて、このプロバイダエッジ装置ＰＥ間のトラヒック量上限を０にした場合の必要なリンクリソースを計算する。この値を、Ｒ'（ｌ）とする（Ｓ１０５）。経路計算手段１２は、各リンクについて、[Ｒ（ｌ）−Ｒ'（ｌ）]×Ｘ＋１（Ｘ：定数）をリンクコストとする（Ｓ１０６）。経路計算手段１２は、前記リンクコストに基づき、プロバイダエッジ装置ＰＥｓｒｃ→ｄｓｔ間について、最短経路を計算する（Ｓ１０７）。リンクリソース計算手段１４は、プロバイダエッジ装置ＰＥｓｒｃ→ｄｓｔ間経路を、Ｓ１０７で求めた経路に置き換えたことを想定し、各リンクについて、必要なリソースを計算する（Ｓ１０８）。リンクリソース計算手段１４は、前記得られたリンクリソースの全リンクでの合計を求める。この値をＲ'とする（Ｓ１０９）。
【００５３】
経路計算手段１２は、Ｒ'−Ｒ＜０かつ、Ｒ'＜ＭＩＮであるか確認する（Ｓ１１０）。経路計算手段１２は、Ｓ１１０がＹＥＳの場合、ＭＩＮ＝Ｒ'とする（Ｓ１１１）。経路計算手段１２は、全プロバイダエッジ装置ＰＥ間について計算が終了しているか確認する（Ｓ１２０）。経路計算手段１２は、Ｓ１２０でＮＯの場合、Ｓ１０４に戻る。経路計算手段１２は、ＭＩＮがＳ１０３で設定した大きい値のままであるかどうか確認する（Ｓ１３０）。経路計算手段１２は、Ｓ１３０がＮＯである場合（Ｓ１３０、Ｎ）、ＭＩＮとなるプロバイダエッジ装置ＰＥ間について経路を置き換え、Ｓ１０１に戻る（Ｓ１３１）。経路計算手段１２は、Ｓ１３０がＹＥＳである場合（Ｓ１３０、Ｙ）、経路の計算処理を終了する。
【００５４】
図５および図６は、プロバイダエッジ装置ＰＥ間の経路を計算する手順を、シミュレーティッドアニーリング（simulated annealing）により行うフローチャートを示している。この手法は、初めから最高の評価値となるデータを算出するのではなく、初回の評価値となるデータから、徐々に評価値を上げるように計算を繰り返す、改良型のアルゴリズムである。そして、前回の評価値となるデータから、今回の評価値となるデータの候補を生成する。そして、その候補の評価値が、前回の評価値より上回るのであれば、その候補を今回の評価値となるデータとして採用する（Ｓ２２０、Ｓ２２１参照）。一方、その候補の評価値が、前回の評価値より上回らないのであれば、その候補を今回の評価値となるデータとして採用するかどうかは、所定の確率によって決定される（Ｓ２２４、Ｓ２２５参照）。さらに、評価値となるデータが所定の回数だけ連続して変更されない場合には、これ以上評価値を改良する余地がないとして、計算を終了する（Ｓ２４０参照）ことを特徴とする。
【００５５】
そのため、評価値は計算の度に上昇することもあるし、下降することもある。それにより、狭い範囲での最適解（局所最適解）を発見しても計算が続けられることで、全体最適となる解を発見する可能性があり、評価値の高い計算結果を得ることができる。
【００５６】
経路計算手段１２は、ｃ＿ａ＝０、ｃ＿ｒ＝０、ｃ＿ｃ＝０、ｃ＿ｓ＝０、Ｔ＝Ｔ０（Ｔ０：定数）とする（Ｓ２０１）。リンクリソース計算手段１４は、各リンクについて、必要なリンクリソースを計算し、この値を、Ｒ（１）とする（Ｓ２０２）。リンクリソース計算手段１４は、Ｓ２０２で求めたリンクリソースの全リンクでの合計を求める、この値を、Ｒとする（Ｓ２０３）。
【００５７】
経路計算手段１２は、ランダムにリンクｉ→ｊを選択する（Ｓ２０４）。経路計算手段１２は、経路がリンクｉ→ｊを通るプロバイダエッジ装置ＰＥｓｒｃ→ｄｓｔ間をランダムに選択する（Ｓ２０５）。リンクリソース計算手段１４は、プロバイダエッジ装置ＰＥｓｒｃ→ｄｓｔ間のトラヒック上限を０とした場合の必要な各リンクのリンクリソースを計算する。この値を、Ｒ'（ｌ）とする（Ｓ２０６）。経路計算手段１２は、各リンクについて、リンクコストを、[Ｒ（ｌ）−Ｒ'（ｌ）]×Ｘ＋１とする。ただし、Ｓ２０４で選択したリンクｉ→ｊのリンクコストを大きい値にする（Ｓ２０７）。経路計算手段１２は、Ｓ２０７で求めたリンクコストに基づき、Ｓ２０５で選択したプロバイダエッジ装置ＰＥｓｒｃ→ｄｓｔ間について、最短経路を計算する（Ｓ２０８）。リンクリソース計算手段１４は、プロバイダエッジ装置ＰＥｓｒｃ→ｄｓｔ間経路を、Ｓ２０８で求めた経路に置き換えたことを想定し、各リンクについて、必要なリソースを計算する（Ｓ２０９）。
【００５８】
経路計算手段１２は、ｃ＿ｃの値を１増やすとともに、Ｓ２０９で得られたリンクリソースの全リンクでの合計を求める。この値を、Ｒ'とする（Ｓ２１０）。経路計算手段１２は、Ｒ'−Ｒの値が負である場合（Ｓ２２０、Ｙ）、経路を置き換えるとともに、ｃ＿ａの値を１増やし、ｃ＿ｓ、ｃ＿ｒの値を０にする（Ｓ２２１）。経路計算手段１２は、Ｒ'−Ｒの値が０である場合（Ｓ２２２、Ｙ）、経路を置き換えるとともに、ｃ＿ａの値とｃ＿ｓの値を１増やし、ｃ＿ｒの値を０にする（Ｓ２２３）。経路計算手段１２は、Ｒ'−Ｒの値が正である場合、確率ｅ（＝（−Ｒ'＋Ｒ）／Ｔ）で経路を置き換えるかどうか判断する（Ｓ２２４）。経路計算手段１２は、経路を置き換える場合は（Ｓ２２４，Ｙ）、ｃ＿ａの値を１増やし、ｃ＿ｓ、ｃ＿ｒの値を０にし、（Ｓ２２５）。経路計算手段１２は、経路を置き換えない場合は（Ｓ２２４，Ｎ）、ｃ＿ｒの値を１増やす（Ｓ２２６）。経路計算手段１２は、ｃ＿ａ＝Ｃ＿Ａ（Ｃ＿Ａ：定数）もしくは、ｃ＿ｃ＝Ｃ＿Ｃ（Ｃ＿Ｃ：定数）の場合（Ｓ２３０、Ｙ）、Ｔ＝α×Ｔ（α：定数）とすると同時に、ｃ＿ａ＝０、ｃ＿ｃ＝０とする（Ｓ２３１）。経路計算手段１２は、ｃ＿ｒ＝Ｃ＿Ｒ（Ｃ＿Ｒ：定数）もしくは、ｃ＿ｓ＝Ｃ＿Ｓ（Ｃ＿Ｓ：定数）でない場合（Ｓ２４０、Ｎ）、Ｓ２０２に戻るが、そうである場合（Ｓ２４０、Ｙ）は終了する。この結果、算出された経路は、全体最適となる可能性がある。
【００５９】
以上説明した本発明は、以下のようにその趣旨を逸脱しない範囲で広く変形実施することができる。
【００６０】
例えば、図２に示されるリソース算出装置は、独立した１つの装置として構成されてもよいし、ＰＥ、Ｐ内に収納されてもよい。さらに、リソース算出装置は、計算対象となるネットワーク内において、トラヒックを転送する機能（ルータ機能）を有していてもよいし、リソース計算を行い、その結果をもとにネットワークを製御する制御装置として構成されてもよい。
【００６１】
さらに、図１に示す一実施形態では、プロバイダ網と仮想網との２つに分けて、ネットワークを構成することとしたが、これはあくまで一例である。つまり、本発明は、ＶＰＮに限定されず、トラヒック量上限を契約で規定するようなネットワークであれば、適用が可能である。
【図面の簡単な説明】
【００６２】
【図１】本発明の一実施形態に関するネットワーク構成を示している。
【図２】本発明の一実施形態に関するリソース算出装置の構成を示している。
【図３】本発明の一実施形態に関するリンクリソース計算手段がリンクリソースを計算する際に用いられるノード数２Ｎ＋２のネットワークの構成を示している。
【図４】本発明の一実施形態に関するプロバイダエッジ装置間の経路を計算する手順を、グリーディアルゴリズムにより行うフローチャートを示している。
【図５】本発明の一実施形態に関するプロバイダエッジ装置間の経路を計算する手順を、シミュレーティッドアニーリングにより行うフローチャートを示している。
【図６】本発明の一実施形態に関するプロバイダエッジ装置間の経路を計算する手順を、シミュレーティッドアニーリングにより行うフローチャートを示している。
【図７】本発明の一実施形態に関する最大フロー問題を説明する図である。
【図８】本発明の一実施形態に関する線形計画問題を示す図である。
【符号の説明】
【００６３】
ＰＥ    プロバイダエッジ装置
１２    経路計算手段
１４    リンクリソース計算手段
１６    リソース割り当て手段
１８    受付制御手段
２２    網トポロジーＤＢ
２４    経路ＤＢ
２６    プロファイルＤＢ
２８    リンクリソースＤＢ
【図１】
2006054722.tif 000003
【図２】
2006054722.tif 000004
【図３】
2006054722.tif 000005
【図４】
2006054722.tif 000006
【図５】
2006054722.tif 000007
【図６】
2006054722.tif 000008
【図７】
2006054722.tif 000009
【図８】
2006054722.tif 000010