(57)【特許請求の範囲】
【請求項１】
物理ネットワークに割り当てる仮想ネットワークを取得する入力部と、
前記入力部の取得した入力仮想ネットワークを、前記入力仮想ネットワークに含まれる仮想リンクよりも仮想リンク数を減らした疎な仮想ネットワークに変換する仮想ネットワーク変換部と、
得られた疎な仮想ネットワークを前記物理ネットワークに割り当てる仮想ネットワーク割当計算部と、
前記入力仮想ネットワークと前記疎な仮想ネットワークとの差分を用いて、前記仮想ネットワーク割当計算部の割り当てた前記疎な仮想ネットワークへの割当を、前記入力仮想ネットワークへの割当に変換する割当変換部と、
を備える仮想ネットワーク割当装置。
【請求項２】
前記割当変換部は、前記疎な仮想ネットワークに割り当てられている前記物理ネットワークに含まれる物理パスを、前記入力仮想ネットワークに含まれる仮想リンクのうちの前記疎な仮想ネットワークに含まれていない仮想リンクに割り当てることで、前記疎な仮想ネットワークへの割当を前記入力仮想ネットワークへの割当に変換する、
請求項１に記載の仮想ネットワーク割当装置。
【請求項３】
前記仮想ネットワーク変換部における前記変換は、三角形をなす３つの仮想リンクの１つを削除するリンク縮約処理を複数回行うことで行う、
請求項１又は２に記載の仮想ネットワーク割当装置。
【請求項４】
前記仮想ネットワーク変換部における前記変換は、
前記入力仮想ネットワークに含まれる仮想ノードを複数の分割ノード群に分割し、
前記分割ノード群に含まれる各仮想ノードと仮想リンクで接続されたコアノードを前記分割ノード群ごとに生成し、前記コアノードと各仮想ノードが接続された仮想リンクをアクセスリンクとし、前記コアノード同士を接続する仮想リンクをコアリンクとし、
前記アクセスリンク及び前記コアリンクを残し、前記入力仮想ネットワークに含まれる各仮想リンクを削除することで行う、
請求項１又は２に記載の仮想ネットワーク割当装置。
【請求項５】
物理ネットワークに割り当てる仮想ネットワークを取得すると、取得した入力仮想ネットワークを、前記入力仮想ネットワークに含まれる仮想リンクよりも仮想リンク数を減らした疎な仮想ネットワークに変換する仮想ネットワーク変換手順と、
得られた疎な仮想ネットワークを前記物理ネットワークに割り当てる仮想ネットワーク割当計算手順と、
前記入力仮想ネットワークと前記疎な仮想ネットワークとの差分を用いて、前記仮想ネットワーク割当計算手順で割り当てた前記疎な仮想ネットワークへの割当を、前記入力仮想ネットワークへの割当に変換する割当変換手順と、
を仮想ネットワーク割当装置が順に実行する仮想ネットワーク割当方法。
【請求項６】
請求項５に記載の各手順をコンピュータに実行させるための仮想ネットワーク割当プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物理ネットワークを仮想ネットワークに割り当てるための装置、方法及びプログラムに関する。
【背景技術】
【０００２】
仮想ネットワークの割当手法が提案されている（例えば、非特許文献１参照。）。非特許文献１の手法は、物理ネットワークを、ユーザが要求する仮想ネットワークに割り当てる。このとき、ユーザが要求する仮想ネットワークのトポロジはユーザが適切にデザインする必要がある。一方で、ユーザは、需要予測の交流トラフィック（Ｔｒａｆｆｉｃ  Ｍａｔｒｉｘ）に基づいた全てのノード間にリンクが存在する密なネットワーク（トポロジが完全グラフなネットワーク）を要求することが自然である。
【０００３】
しかしながら、要求されたネットワークのリンク数が多くなると、仮想ネットワーク割当の発見に必要な計算時間が増加してしまう。例えば、仮想ネットワーク割当典型的手法である線形計画緩和（非特許文献１参照。）を用いた場合、計算時間は要求仮想ネットワークのリンク数｜Ｅ｜の約３乗｜Ｅ｜３に比例する。要求仮想ネットワークのノード数｜Ｖ｜が１００のとき、リンクが疎な仮想ネットワークＯ（｜Ｅ｜）＝Ｏ（｜Ｖ｜）とリンクが密な仮想ネットワークＯ（｜Ｅ｜）＝Ｏ（｜Ｖ｜２）を比べると計算時間は１００３＝１０６の差となる。
【０００４】
密な仮想ネットワークを疎な仮想ネットワークに変換する方法は考えられていない。一般的なグラフ操作として頂点・枝の削除や縮約は考えられているが、仮想ネットワーク割当のためではない。そのため、変換された仮想ネットワークの仮想ネットワーク割当（変換後割当）から変換前の仮想ネットワークの仮想ネットワーク割当（変換前割当）を求める方法も考えられていない。
【０００５】
まず仮想ネットワーク割当問題を説明する。図１に示すユーザからの仮想ネットワーク利用要求と、図２に示すネットワーク設備提供者の物理ネットワークがあるとする。仮想ネットワークは、仮想ノードが仮想リンクで接続された通信ネットワークである。物理ネットワークは、物理ノードが物理リンクで接続された通信ネットワークである。図１において、枠内のアルファベットは仮想ノード名を示し、枠内の数字は仮想ノードの利用要求量を示し、仮想ノード間を結ぶ各仮想リンクに付随する数値は仮想リンクの利用要求量を示す。図２において、枠内のアルファベットは物理ノード名を示し、枠内の数字は物理ノードにおける空き容量を示し、物理ノード間を結ぶ各物理リンクに付随する数値は物理リンクの空き容量を示す。
【０００６】
仮想ネットワークは仮想ノードと仮想リンクで構成され、それぞれ利用要求（ＣＰＵクロック数や通信帯域）が与えられる。仮想ネットワークのトポロジは完全グラフ、すなわち全ての仮想ノードペアが仮想リンクで接続されているとする。ただし、仮想ネットワークのトポロジが完全グラフでない場合も、要求通信帯域が０である仮想リンクを追加することで完全グラフとして扱うことができる。
【０００７】
物理ネットワークは物理ノードと物理リンクで構成され、それぞれに空き容量と割当コストがある。図２においては、ノード及びリンクの割当コストは省略した。
【０００８】
仮想ネットワーク割当問題とは、仮想ノード及び仮想リンクを、それらの要求容量を満たす物理ノード及び物理リンクに割り当てることである。仮想ノードはひとつの物理ノードに割り当てられる。仮想リンクは１つもしくは複数の物理パスに割り当てられる。ここで、「物理パス」とは、物理リンクの列のうち、隣接している物理リンクが端点を共有しているような物理リンクの列である。複数の物理パスに割り当てるとは、例えば、ある仮想リンクの要求通信帯域の３０％を物理パスＰ１に、２０％を物理パスＰ２に、５０％を物理パスＰ３にそれぞれ割り当てるなどである。
【０００９】
図３に、物理ネットワークへの仮想ネットワークの割当の一例を示す。仮想ノードａ、ｂ、ｃが物理ノードＡ、Ｂ、Ｅにそれぞれ割り当てられている。仮想リンク（ａ，ｂ）が物理パス｛（Ａ，Ｂ）｝に割り当てられている。仮想リンク（ａ，ｃ）が物理パス｛（Ａ，Ｄ），（Ｄ，Ｅ）｝に割り当てられている。仮想リンク（ｂ，ｃ）が２つの物理パス｛（Ｂ，Ｄ），（Ｄ，Ｅ）｝及び｛（Ｂ，Ｃ），（Ｃ，Ｅ）｝に割り当てられている。
【００１０】
仮想ネットワーク割当のコストとは、割り当てに用いたすべての物理ノードと物理リンクの合計コストである。仮想ネットワークを割り当てる際には、この合計コストを最小にする割当を求める。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Ｍ．  Ｃｈｏｗｄｈｕｒｙ，  Ｍ．  Ｒａｈｍａｎ，  ａｎｄ  Ｒ．  Ｂｏｕｔａｂａ，  “ＶｉＮＥＹａｒｄ：  Ｖｉｒｔｕａｌ  Ｎｅｔｗｏｒｋ  Ｅｍｂｅｄｄｉｎｇ  Ａｌｇｏｒｉｔｈｍｓ  Ｗｉｔｈ  Ｃｏｏｒｄｉｎａｔｅｄ  Ｎｏｄｅ  ａｎｄ  Ｌｉｎｋ  Ｍａｐｐｉｎｇ，”  ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓ．  Ｎｅｔｗ．，  Ｖｏｌ．  ２０，  Ｎｏ．  １，  ｐｐ．  ２０６−２１９，  ２０１２．
【発明の概要】
【発明が解決しようとする課題】
【００１２】
ユーザが密な仮想ネットワークを要求すると、合計コストを最小にする割当を求める際に、計算時間が大きくなってしまうという課題があった。密な仮想ネットワークを疎な仮想ネットワークに変換するか、変換後の割当から変換前の割当をどのように求めるか、について分からなかった。
【００１３】
そこで、本発明は、ユーザから要求された仮想ネットワークの割当を行うに当たり、要求された密な仮想ネットワークを疎な仮想ネットワークに変換することを目的とする。
【課題を解決するための手段】
【００１４】
本発明に係る仮想ネットワーク割当装置は、
物理ネットワークに割り当てる仮想ネットワークを取得する入力部と、
前記入力部の取得した入力仮想ネットワークを、前記入力仮想ネットワークに含まれる仮想リンクよりも仮想リンク数を減らした疎な仮想ネットワークに変換する仮想ネットワーク変換部と、
得られた疎な仮想ネットワークを前記物理ネットワークに割り当てる仮想ネットワーク割当計算部と、
前記入力仮想ネットワークと前記疎な仮想ネットワークとの差分を用いて、前記仮想ネットワーク割当計算部の割り当てた前記疎な仮想ネットワークへの割当を、前記入力仮想ネットワークへの割当に変換する割当変換部と、
を備える。
【００１５】
前記割当変換部は、前記疎な仮想ネットワークに割り当てられている前記物理ネットワークに含まれる物理パスを、前記入力仮想ネットワークに含まれる仮想リンクのうちの前記疎な仮想ネットワークに含まれていない仮想リンクに割り当てることで、前記疎な仮想ネットワークへの割当を前記入力仮想ネットワークへの割当に変換してもよい。
【００１６】
前記仮想ネットワーク変換部における前記変換は、三角形をなす３つの仮想リンクの１つを削除するリンク縮約処理を複数回行うことで行ってもよい。
【００１７】
前記仮想ネットワーク変換部における前記変換は、
前記入力仮想ネットワークに含まれる仮想ノードを複数の分割ノード群に分割し、
前記分割ノード群に含まれる各仮想ノードと仮想リンクで接続されたコアノードを前記分割ノード群ごとに生成し、前記コアノードと各仮想ノードが接続された仮想リンクをアクセスリンクとし、前記コアノード同士を接続する仮想リンクをコアリンクとし、
前記アクセスリンク及び前記コアリンクを残し、前記入力仮想ネットワークに含まれる各仮想リンクを削除することで行ってもよい。
【００１８】
本発明に係る仮想ネットワーク割当方法は、
物理ネットワークに割り当てる仮想ネットワークを取得すると、取得した入力仮想ネットワークを、前記入力仮想ネットワークに含まれる仮想リンクよりも仮想リンク数を減らした疎な仮想ネットワークに変換する仮想ネットワーク変換手順と、
得られた疎な仮想ネットワークを前記物理ネットワークに割り当てる仮想ネットワーク割当計算手順と、
前記入力仮想ネットワークと前記疎な仮想ネットワークとの差分を用いて、前記仮想ネットワーク割当計算手順で割り当てた前記疎な仮想ネットワークへの割当を、前記入力仮想ネットワークへの割当に変換する割当変換手順と、
を仮想ネットワーク割当装置が順に実行する。
【００１９】
本発明に係る仮想ネットワーク割当プログラムは、本発明に係る仮想ネットワーク割当方法に含まれる各手順をコンピュータに実行させるためのプログラムである。
【００２０】
なお、上記各発明は、可能な限り組み合わせることができる。
【発明の効果】
【００２１】
本発明によれば、ユーザから要求された仮想ネットワークの割当を行うに当たり、要求された密な仮想ネットワークを疎な仮想ネットワークに変換することができ、割当の計算を高速に行うことが可能となる。
【図面の簡単な説明】
【００２２】
【図１】仮想ネットワークの一例を示す。
【図２】物理ネットワークの一例を示す。
【図３】物理ネットワークへの仮想ネットワークの割当の一例を示す。
【図４】仮想ネットワーク割当装置の一例を示す構成図である。
【図５】実施形態１及び２に係る仮想ネットワーク変換の一例を示す。
【図６】実施形態３及び４における利用要求のあった入力仮想ネットワークの一例を示す。
【図７】実施形態３に係る疎な仮想ネットワークの一例を示す。
【図８】実施形態４に係る疎な仮想ネットワークの一例を示す。
【発明を実施するための形態】
【００２３】
以下、本発明の実施形態について、図面を参照しながら詳細に説明する。なお、本発明は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本発明は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２４】
本実施形態に係る仮想ネットワーク割当方法は、本実施形態に係る仮想ネットワーク割当装置が実行する方法であって、ネットワーク設備提供者の保有する物理ネットワークを、ユーザが要求する仮想ネットワークに割り当てる。これにより、ネットワーク設備提供者は、ユーザからの仮想ネットワーク利用要求に対し、その要求を満たす仮想ネットワーク割当を求めることができる。
【００２５】
ここで、ネットワーク設備提供者とは、ネットワーク資源やＩＣＴ資源を保有し、それらをユーザに提供するインターネットサービスプロバイダ（ＩＳＰ）などのことである。また、仮想ネットワーク割当は、仮想ネットワーク利用要求に応じて、保有するネットワーク設備の中からどのネットワーク機器・ＩＣＴ（Ｉｎｆｏｒｍａｔｉｏｎ  ＆  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｔｅｃｈｎｏｌｏｇｙ）資源を使用し、それらをどのように接続するかを決定することである。
【００２６】
本実施形態は、仮想ネットワーク割当の探索前に要求仮想ネットワークのリンク数を減らすことで、高速に割当を発見する。本実施形態は、利用要求のあった仮想ネットワークのリンク数を減らすために、仮想ネットワーク変換及び割当変換を行う。なお、割当の発見（計算）は既存の手法を用いることができる。
【００２７】
仮想ネットワークのリンク数を減らす仮想ネットワーク変換の手法として、４種類の変換手法を説明する。それぞれ、実施形態１ではリンク縮約を、実施形態２では複数リンク縮約を、実施形態３ではｋ−ノード挿入リンク縮約を、実施形態４では擬ｋ−ノード挿入リンク縮約を、説明する。
【００２８】
図４に、本実施形態に係る仮想ネットワーク割当装置の構成例を示す。本実施形態に係る仮想ネットワーク割当装置は、入力部１１、仮想ネットワーク変換部１２、仮想ネットワーク割当計算部１３及び割当変換部１４を備える。
【００２９】
本実施形態に係る仮想ネットワーク割当装置は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）及び記憶部を備えるコンピュータを用いて構成することができる。この場合、仮想ネットワーク割当装置内のＣＰＵが、記憶部に記憶されたコンピュータプログラムを実行することで、仮想ネットワーク割当装置に備わる各機能部を実現する。このように、本実施形態に係る仮想ネットワーク割当装置は、コンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【００３０】
入力部１１は、問題の入力である物理ネットワークと仮想ネットワークを受取る。
仮想ネットワーク変換部１２は、仮想ネットワーク変換を実行し、利用要求のあった仮想ネットワークのリンク数が減るように変換する。これにより、入力仮想ネットワークを疎な仮想ネットワークに変換する。
次に、仮想ネットワーク割当計算部１３は、仮想ネットワーク変換部１２で変換された疎な仮想ネットワークについて、仮想ネットワーク割当を計算する。仮想ネットワーク割当は、既存の仮想ネットワーク割当手法を用いて行うことができる。
次に、割当変換部１４は、仮想ネットワーク割当計算部１３の割当に割当変換を実行し、仮想ネットワーク変換前の入力仮想ネットワークの割当を計算する。これを結果として出力する。割当変換は、入力仮想ネットワークと疎な仮想ネットワークとの差分を用いる。
【００３１】
後述する実施形態１〜４では、仮想ネットワーク変換部１２がリンク縮約を実行する仮想ネットワーク変換の具体例を述べる。実施形態１〜４で説明するいずれの仮想ネットワーク変換手法も、適用する仮想ネットワーク及び物理ネットワークに制限はない。そのため、いずれの手法も仮想ネットワーク変換部１２にて使用することができる。
【００３２】
実施形態１の「リンク縮約」では仮想リンクの数が１つ減る。実施形態２の「複数リンク縮約」、実施形態３の「ノード挿入リンク縮約」及び実施形態４の「擬ノード挿入リンク縮約」では、複数の仮想リンクを減らすことができる。このため、仮想ネットワーク変換部１２で使用する変換手法は、実施形態２の「複数リンク縮約」、実施形態３の「ノード挿入リンク縮約」又は実施形態４の「擬ノード挿入リンク縮約」であることが好ましい。
【００３３】
また、実施形態３の「ノード挿入リンク縮約」は実施形態４の「擬ノード挿入リンク縮約」で得られる仮想ネットワークに適切な要求通信帯域をもつ仮想リンクを付加したものである。例えば、図７の変換後の仮想ネットワークは図８の擬コアノードｕ１、ｕ２、ｕ３に枝を付加したものになっている。そのため、擬ノード挿入リンク縮約はノード挿入リンク縮約よりも疎な仮想ネットワークになっている。
【００３４】
実施形態４の「擬ノード挿入リンク縮約」は、実施形態２の「複数リンク縮約」に比べて高速に変換が完了する。これは複数リンク縮約では仮想リンクを１つずつ処理するが、擬ノード挿入リンク縮約では一括でリンクを処理することができるからである。
【００３５】
（実施形態１）
本実施形態では、仮想ネットワーク変換の第１例として、「リンク縮約」について説明する。リンク縮約は仮想ネットワークから仮想リンクをひとつ削除する操作である。
【００３６】
（仮想ネットワーク変換）
図５に、本実施形態に係る仮想ネットワーク変換の一例を示す。リンク縮約処理は、仮想ネットワークが三角形をなす３つの仮想リンクｅ、ｘ、ｙである場合、任意の一辺である仮想リンクｅを削除し、その仮想リンクの要求通信帯域ｒ（ｅ）を残りの２本の仮想リンクｘ及びｙに足す処理である。これは、仮想リンクｅが仮想ノードｘとｙの共有端点である仮想ノードＮ２を経由するように制約を加えたことと等価である。このリンク縮約処理により、仮想リンクの数が１少なくなる。
【００３７】
（割当変換）
仮想ネットワーク割当計算部１３の計算した仮想ネットワーク割当は、削除された仮想リンクｅに対応する割当がない。そこで、割当変換部１４は、仮想リンクｅに対応する割当を行う。なお、入力仮想ネットワークと疎な仮想ネットワークとでは仮想ノードＮ１、Ｎ２、Ｎ３には変わりがないため、仮想ノード割当は変換する必要がない。
【００３８】
仮想ネットワーク割当後の仮想リンクｘ、ｙには、帯域が過剰に割り当てられている。余剰分の帯域はちょうどｒ（ｅ）である。これを仮想リンクｅに割当てる。具体的には、仮想リンクｘ、ｙが割当られている各物理リンクが、それぞれ１つの物理パスＰｘ｛（Ｎ１，Ｎ２）｝、Ｐｙ｛（Ｎ２，Ｎ３）｝であると仮定する。このとき、仮想リンクｅを、物理パスＰｘ｛（Ｎ１，Ｎ２）｝と物理パスＰｙ｛（Ｎ２，Ｎ３）｝を連結したパス｛（Ｎ１，Ｎ２），（Ｎ２，Ｎ３）｝に割り当てる。
【００３９】
ここで、物理リンクｅ１、ｅ２、ｅ３、ｅ４がある場合、物理パス｛ｅ１，ｅ２｝と物理パス｛ｅ３，ｅ４｝の連結は、例えば、次式で表される。
【数１】
0006473406.tif 000002
【００４０】
仮想リンクｘ、ｙが複数の物理パスに割り当てられている場合は、それぞれの物理パスから余剰帯域をもつ物理パスを１つずつ選んで連結し、これに仮想リンクｅを割り当てる。仮想リンクｅに必要な帯域が割り当てられるまで、これを繰り返す。これにより、疎な仮想ネットワークへの割当を、入力仮想ネットワークへの割当に変換することができる。
【００４１】
（実施形態２）
本実施形態では、仮想ネットワーク変換の第２例として、「複数リンク縮約」について説明する。複数リンク縮約は実施形態１のリンク縮約を複数回実行する操作である。
【００４２】
（仮想ネットワーク変換）
実施形態１で説明したリンク縮約の操作を複数回実行する。実行回数をｓとすると、仮想リンクの数はｓ少なくなる。
【００４３】
（割当変換）
仮想ネットワーク変換において、ｉ番目に削除した仮想リンクをｅｉ、三角形をｅｉ、ｘｉ、ｙｉとする。ただし、ｉ＝１、２、…、ｓである。仮想ネットワーク割当計算部１３の計算した仮想ネットワーク割当は、削除された仮想リンクｅ１，ｅ２，…ｅｓに対応する割当がない。そこで、割当変換部１４は、仮想リンクｅｉに対応する割当を作成する。なお、リンク縮約では仮想ノードに変化はないため、仮想ノード割当は変換する必要がない。
【００４４】
仮想リンクｅｓ，ｅｓ−１，…ｅ２，ｅ１の順に、各仮想リンク毎に割当を行う。仮想リンクｅｉの割当を作成する際は、実施形態１と同様に、仮想リンクｘｉ、ｙｉが割り当てられた物理パスＰｘｉ、Ｐｙｉを組合せて仮想リンクｅｉを割り当てる物理パスを作成する。仮想ネットワーク変換時とは逆順で物理パスの割当を構築していくことで、削除した仮想リンクｅｉの割当を作成する際に、三角形の残りの仮想リンクｘｉ、ｙｉの割当が作成済であることが保証できる。
【００４５】
（実施形態３）
本実施形態では、仮想ネットワーク変換の第３例として、「ノード挿入リンク縮約」について説明する。ｋ−ノード挿入リンク縮約は新たに仮想ノードをｋ個追加し、リンク数を減らす操作である。図６は変換前の密な入力仮想ネットワークを示し、図７は変換後の疎な仮想ネットワークを示す。
【００４６】
（仮想ネットワーク変換）
本実施形態の「ノード挿入リンク縮約」は、仮想ノードの変換及び仮想リンクの変換を行う。
【００４７】
仮想ノードの変換を説明する。仮想ノードの集合Ｖをｋ分割し、ｋ個の分割ノード群を生成する。この分割後の分割ノード群の集合を｛Ｖ１，Ｖ２，Ｖ３，…，Ｖｋ｝とする。ｋ個の仮想ノード｛ｕ１，ｕ２，…，ｕｋ｝を分割ノード群ごとに追加する。図７は、ｋ＝３の場合の疎な仮想ネットワークの一例を示す。追加した仮想ノードｕ１、ｕ２、ｕ３をコアノード、元からある仮想ノードｖ１〜ｖ９をアクセスノードと呼ぶ。追加したコアノードの要求容量は０に設定する。
【００４８】
仮想リンクの変換を説明する。仮想リンクを次の３種類に分けて説明する。コアノード間のリンク（ｕｉ，ｕｊ）を「コアリンク」と呼ぶ。コアノードｕｉとアクセスノードｖ∈Ｖｉの間のリンク（ｕｉ，ｖ）を「アクセスリンク」と呼ぶ。アクセスノード間のリンク（元からあるリンクｅ∈Ｅ）を「オリジナルリンク」と呼ぶ。
【００４９】
本実施形態では、図７に示すように、コアリンクとアクセスリンクを追加し、オリジナルリンクは削除する。太い実線がコアリンクを示し、細い実線がアクセスリンクを示す。コアリンクとアクセスリンクの要求通信帯域は、次のようにオリジナルリンクの要求通信帯域が含まれるように設定する。
【００５０】
コアリンク（ｕｉ，ｕｊ）の要求通信帯域ｒ（（ｕｉ，ｕｊ））を
【数２】
0006473406.tif 000003
と設定する（ただし、ｉ≠ｊ）。
【００５１】
ここで、Ｅ（Ｖｉ，Ｖｊ）は分割ノード群Ｖｉと分割ノード群Ｖｊの間のオリジナルリンクの集合である。つまり、オリジナルリンクの端点の片方の仮想ノードが分割ノード群Ｖｉに含まれ、もう片方の仮想ノードが分割ノード群Ｖｊに含まれるようなオリジナルリンクの集合である。例えば、仮想ノードｖ１、ｖ２、ｖ３が分割ノード群Ｖ１に含まれ、仮想ノードｖ４、ｖ５、ｖ６が分割ノード群Ｖ２に含まれている場合、仮想ノードｖ２と仮想ノードｖ４に含まれるオリジナルリンクは集合Ｅ（Ｖ１，Ｖ２）に含まれる。
【００５２】
アクセスリンク（ｕｉ，ｖ）の要求通信帯域ｒ（（ｕｉ，ｖ））を
【数３】
0006473406.tif 000004
と設定する（ただしｖ∈Ｖｉ）。ここで「／」は差集合を表す集合演算子である。
【００５３】
この操作で仮想ノード数は｜Ｖ｜＋ｋとなり、仮想リンクの数は
【数４】
0006473406.tif 000005
となる。２＜｜Ｖ｜のときｋ＜｜Ｖ｜−１となるｋを選ぶことで仮想リンクの数を減らすことができる。
【００５４】
（割当変換）
本実施形態では、コアリンク及びアクセスリンクに対応する割当があるが、オリジナルリンクに対応する割当がない。そこで、割当変換部１４は、オリジナルリンクに対応する割当を作成する必要がある。なお、仮想ノードｖ１〜ｖ９には変わりがないため、仮想ノード割当は変換する必要がない。コアノードｕ１〜ｕ３は変換前の入力仮想ネットワークに対応するノードがいないので割当を削除する。
【００５５】
オリジナルリンクの割当は、コアリンクの割当とアクセスリンクの割当から作成する。このとき、オリジナルリンクの端点の仮想ノードが同じ分割ノード群Ｖｉに含まれる場合（割当変換例Ｉ）、オリジナルリンクの端点の仮想ノードが異なる分割ノード群Ｖｉと分割ノード群Ｖｊに含まる場合（割当変換例ＩＩ）の２つの場合に分けて考える。
【００５６】
（割当変換例Ｉ）
端点ｖ及びｗがオリジナルリンクの端点でありかつ同じ分割ノード群Ｖｉに含まれる場合について説明する。例えば、端点ｖ及びｗは、分割ノード群Ｖ１に含まれる仮想ノードｖ１及びｖ３である。
【００５７】
２つのアクセスリンク（ｕｉ，ｖ）及び（ｕｉ，ｗ）が割り当てられている物理パスを、実施形態１と同様に連結することで、オリジナルリンク（ｖ，ｗ）に対応する物理パスが得られる。これらの物理パスにアクセスリンク（ｖ，ｗ）を割り当てる。
【００５８】
ここで、仮想ネットワーク変換後の仮想ネットワークに含まれるアクセスリンク（ｕｉ，ｖ）及び（ｕｉ，ｗ）は変換前の入力仮想ネットワークには存在しないため、要求通信帯域を確保する必要がない。そのため、これらのアクセスリンクに割り当てていた通信帯域を変換前の入力仮想ネットワークのオリジナルリンク（ｖ，ｗ）に割り当てることができる。また、コアリンクとアクセスリンクの要求通信帯域にオリジナルリンクの要求通信帯域が含まれているため、オリジナルリンクに必要十分な帯域がアクセスリンク及びコアリンクに割り当てられている。
【００５９】
（割当変換例ＩＩ）
端点ｖ及びｗがオリジナルリンクの端点でありかつ異なる分割ノード群Ｖｉ及び分割ノード群Ｖｊに含まれる場合について説明する。ｖ∈Ｖｉ、ｗ∈Ｖｊとする。例えば、端点ｖは分割ノード群Ｖ１に含まれる仮想ノードｖ２であり、端点ｗは分割ノード群Ｖ２に含まれる仮想ノードｖ４である。
【００６０】
アクセスリンク（ｕｉ，ｖ）が割り当てられている物理パスと、アクセスリンク（ｕｊ，ｗ）が割り当てられている物理パスと、コアリンク（ｕｉ，ｕｊ）が割り当てられている物理パスと、を連結することで、オリジナルリンク（ｖ，ｗ）に対応する物理パスが得られる。後は（割当変換例Ｉ）の場合と同様であり、これらの物理パスにオリジナルリンク（ｖ，ｗ）を割り当てる。
【００６１】
（実施形態４）
本実施形態では、仮想ネットワーク変換の第４例として、「擬ノード挿入リンク縮約」について説明する。擬ｋ−ノード挿入リンク縮約は、実施形態３で説明したｋ−ノード挿入リンク縮約のような仮想ネットワーク変換を行う操作であるが、入力仮想ネットワークの仮想ノードをコアノードの追加は行わず、入力仮想ネットワークの仮想ノードをコアノードに用いる変換である。
【００６２】
（仮想ネットワーク変換）
本実施形態の「擬ノード挿入リンク縮約」は、実施形態３のｋ−ノード挿入リンク縮約と同様に、仮想ノードの変換及び仮想リンクの変換を行う。
【００６３】
実施形態３のｋ−ノード挿入リンク縮約と同様にノード集合Ｖをｋ分割し、分割後の分割ノード群｛Ｖ１，Ｖ２，…，Ｖｋ｝とする。図８は、ｋ＝３の場合の疎な仮想ネットワークの一例を示す。各分割ノード群Ｖｉから任意に仮想ノードをひとつ選び、それをｕｉと表わし、「擬コアノード」と呼ぶ。例えば、図８では、分割ノード群Ｖ１に含まれる仮想ノードｖ２を擬コアノードｕ１とし、分割ノード群Ｖ２に含まれる仮想ノードｖ５を擬コアノードｕ２とし、分割ノード群Ｖ３に含まれる仮想ノードｖ８を擬コアノードｕ３とした。擬コアノードではない仮想ノードｖ１、ｖ３、ｖ４、ｖ６、ｖ７、ｖ９を「擬アクセスノード」と呼ぶ。
【００６４】
次に変換後の仮想リンクについて説明する。ｋ−ノード挿入リンク縮約と同様に、３種類に分けて説明する。擬コアノード間のリンク（ｕｉ，ｕｊ）を「擬コアリンク」と呼ぶ。擬コアノードｕｉと擬アクセスノードｖ∈Ｖｉの間のリンク（ｕｉ，ｖ）を「擬アクセスリンク」と呼ぶ。上記２種類以外のリンクを「擬オリジナルリンク」と呼ぶ。
【００６５】
本実施形態では、図８に示すように、擬オリジナルリンクを全て削除し、擬コアリンクと擬アクセスリンクを全て残す。太い実線が擬コアリンクを示し、細い実線が擬アクセスリンクを示す。
【００６６】
次に要求通信帯域について説明する。仮想ネットワーク変換前の要求通信帯域ｒと区別するため、仮想ネットワーク変換後の要求通信帯域をｒ’と書く。擬コアリンク（ｕｉ，ｕｊ）の要求通信帯域ｒ’（（ｕｉ，ｕｊ））を
【数５】
0006473406.tif 000006
と設定する（ただし、ｉ≠ｊ）。
【００６７】
また、擬アクセスリンク（ｕｉ，ｖ）の要求通信帯域ｒ’（（ｕｉ，ｖ））を
【数６】
0006473406.tif 000007
と設定する（ただし、ｖ∈Ｖｉ）。
【００６８】
この操作で仮想リンクの数は
【数７】
0006473406.tif 000008
となる。ｋ＜｜Ｖ｜となるｋを選ぶことで、仮想リンクの数を減らすことができる。
【００６９】
（割当変換）
本実施形態では、擬コアリンク及び擬アクセスリンクに対応する割当があるが、擬オリジナルリンクの割当がない。そこで、割当変換部１４は、擬オリジナルリンクに対応する割当を作成する必要がある。なお、仮想ノードｖ１〜ｖ９には変わりがないため、仮想ノード割当は変換する必要がない。
【００７０】
擬オリジナルリンクの割当は実施形態３で説明した割当変換と同様に、擬コアリンクの割当と擬アクセスリンクの割当から作成する。このとき、擬オリジナルリンクの端点の仮想ノードが同じ分割ノード群Ｖｉに含まれる場合（割当変換例ＩＩＩ）、擬オリジナルリンクの端点の仮想ノードが異なる分割ノード群Ｖｉと分割ノード群Ｖｊに含まれる場合（割当変換例ＩＶ）、に分けて考える。
【００７１】
（割当変換例ＩＩＩ）
端点ｖ及びｗが擬オリジナルリンクの端点でありかつ同じ分割ノード群Ｖｉに含まれる場合について説明する。例えば、端点ｖ及びｗは、分割ノード群Ｖ１に含まれる仮想ノードｖ１及びｖ３である。
【００７２】
２つの擬アクセスリンク（ｕｉ，ｖ）と（ｕｉ，ｗ）が割り当てられている物理パスを、実施形態１と同様に連結することで、擬オリジナルリンク（ｖ，ｗ）に対応する物理パスが得られる。これらの物理パスに擬オリジナルリンク（ｖ，ｗ）を割り当てる。
【００７３】
ここで、擬アクセスリンクは通信帯域が過剰に割り当てられているので、それら余剰分を擬オリジナルリンクに割り当てる。また、擬コアリンクと擬アクセスリンクの要求通信帯域に擬オリジナルリンクの要求通信帯域が含まれているため、擬オリジナルリンクに必要十分な帯域が擬コアリンク及び擬アクセスリンクに割り当てられている。
【００７４】
（割当変換例ＩＶ）
端点ｖ及びｗが擬オリジナルリンクの端点でありかつ異なる分割ノード群Ｖｉ及分割ノード群Ｖｊに含まれている場合について説明する。ｖ∈Ｖｉ、ｗ∈Ｖｊとする。例えば、端点ｖは分割ノード群Ｖ１に含まれる仮想ノードｖ１であり、端点ｗは分割ノード群Ｖ２に含まれる仮想ノードｖ４である。
【００７５】
アクセスリンク（ｕｉ，ｖ）が割り当てられている物理パスと、アクセスリンク（ｕｊ，ｖ）が割り当てられている物理パスと、コアリンク（ｕｉ，ｕｊ）が割り当てられている物理パスと、を連結することで擬オリジナルリンク（ｖ，ｗ）に対応する物理パスが得られる。後は（割当変換例ＩＩＩ）と同様であり、これらの物理パスに擬オリジナルリンク（ｖ，ｗ）を割り当てる。
【産業上の利用可能性】
【００７６】
本発明は情報通信産業に適用することができる。
【符号の説明】
【００７７】
１１：入力部
１２：仮想ネットワーク変換部
１３：仮想ネットワーク割当計算部
１４：仮想ネットワーク割当計算部
【図１】
0006473406.tif 000009
【図２】
0006473406.tif 000010
【図３】
0006473406.tif 000011
【図４】
0006473406.tif 000012
【図５】
0006473406.tif 000013
【図６】
0006473406.tif 000014
【図７】
0006473406.tif 000015
【図８】
0006473406.tif 000016