(57)【特許請求の範囲】
【請求項１】
物理ネットワーク上で仮想ネットワークのサービスを収容するために、当該物理ネットワークのリソースを割り当てるためのネットワークリソース割当装置であって、
前記仮想ネットワークのサービスの要求トラヒック量の総和を算出する要求トラヒック量総和算出部と、
前記仮想ネットワークのサービスに割り当て可能な物理ネットワーク上の候補経路を決定する受付可否判定部と、
前記決定された候補経路の中から、前記仮想ネットワークのサービスに経路を割り当てた場合、接続性を失うノード対の量を最小化する経路を決定する最適経路決定部と、
を有し、
前記受付可否判定部は、前記算出された要求トラヒック量の総和が所定の第１の閾値以下であり、媒介中心性の値が一定値以上である主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第２の閾値以下である場合、前記仮想ネットワークのサービスに経路を割り当てた場合の主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第３の閾値以上であることを要求する制約条件を設け、
前記最適経路決定部は、前記設けられた制約条件を勘案して、前記仮想ネットワークのサービスの経路を決定する、ネットワークリソース割当装置。
【請求項２】
前記受付可否判定部は、候補経路に含まれる物理リンクの最小残余帯域が前記仮想ネットワークのサービスの要求トラヒック量以上であることを確認し、最小残余帯域が前記要求トラヒック量を下回る物理リンクを、候補経路から除外する、請求項１に記載のネットワークリソース割当装置。
【請求項３】
前記受付可否判定部は、前記仮想ネットワークのサービスに割り当て可能な候補経路が存在しない場合、既存サービスのリソースの再配置が必要であると判定する、請求項２に記載のネットワークリソース割当装置。
【請求項４】
既存サービスのリソースの再配置が必要であると判定された場合、前記仮想ネットワークのサービスに加えて再配置の対象となる既存サービスの要求トラヒック量の総和を算出し、前記算出された要求トラヒック量の総和が所定の第１の閾値以下であり、媒介中心性の値が一定値以上である主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第２の閾値以下である場合、前記仮想ネットワークのサービスに加えて前記再配置の対象となる既存サービスに経路を割り当てた場合の主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第３の閾値以上であることを要求する制約条件を設け、前記設けられた制約条件を勘案して、前記仮想ネットワークのサービスの経路と、前記再配置の対象となる既存サービスの経路とを決定する再配置実行部を更に有する、請求項３に記載のネットワークリソース割当装置。
【請求項５】
前記再配置実行部は、再配置実行回数に対して、前記仮想ネットワークのサービスの要求トラヒック量の総和に依存した上限値を設け、前記設けられた上限値を勘案して、前記再配置の対象となる既存サービスの経路を決定する、請求項４に記載のネットワークリソース割当装置。
【請求項６】
前記再配置実行部は、再配置を行う対象となる既存サービスの数量に対して、前記仮想ネットワークのサービスの要求トラヒック量の総和に依存した上限値を設け、前記設けられた上限値を勘案して、前記再配置の対象となる既存サービスの経路を決定する、請求項４に記載のネットワークリソース割当装置。
【請求項７】
物理ネットワーク上で仮想ネットワークのサービスを収容するために、当該物理ネットワークのリソースを割り当てるためのネットワークリソース割当装置におけるネットワークリソース割当方法であって、
前記仮想ネットワークのサービスに割り当て可能な物理ネットワーク上の候補経路を決定するステップと、
前記仮想ネットワークのサービスの要求トラヒック量の総和を算出するステップと、
前記算出された要求トラヒック量の総和が所定の第１の閾値以下であり、媒介中心性の値が一定値以上である主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第２の閾値以下である場合、前記仮想ネットワークのサービスに経路を割り当てた場合の主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第３の閾値以上であることを要求する制約条件を設けるステップと、
前記設けられた制約条件を勘案して、前記決定された候補経路の中から、前記仮想ネットワークのサービスに経路を割り当てた場合、接続性を失うノード対の量を最小化する経路を決定するステップと、
を有するネットワークリソース割当方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークリソース割当装置及びネットワークリソース割当方法に関する。特に、本発明は、ネットワーク仮想化技術を用いたネットワークの提供形態において、サービス提供開始を所望するサービスに対して物理ネットワークのリソースを割り当てるためのネットワークリソース割当装置及びネットワークリソース割当方法に関する。
【背景技術】
【０００２】
仮想化技術の進展に伴い、ストレージやサーバのみならず、ネットワークにおいてＵプレーン（User Plane）とＣプレーン（Control Plane）を分離するネットワーク仮想化技術が進展している。当該技術を用いた世界においては、従来の様なネットワークサービスと設備の固定的な関係は解消し、より柔軟なつながりが実現されていく。即ち、ネットワークを運営するネットワーク事業者が提供する物理的なネットワーク（以下物理ネットワークと呼ぶ）上でサービスを展開する各事業者は、それぞれ独立なタイミング及び順番で当該サービスの提供を開始し、また一般には所定時間経過後にサービスを終了する。
【０００３】
物理ネットワークを運用管理するネットワーク事業者は、一般には独立な到着時刻順で提供開始を所望する各サービスに対し、当該物理ネットワークのリソース（ネットワーク帯域）を割り当て、仮想的なネットワークとして構成することで、ネットワーク上の各サービスを実現する。
【０００４】
上記サービスへの物理リソース割り当ては、Virtual Network Embedding（以下ＶＮＥ）と呼ばれる問題として定式化され、近年多くの研究が報告されている。これは、所与の物理ネットワーク及び時系列で到着するサービスを重み付き無向グラフとしてモデル化し、各サービスに対して、物理ネットワークのリソースを割り当てていく問題である。一般にはノード、リンクとも物理的配置箇所は自由であり、多くの場合、受付成功率や要求トラヒック量の総和（受付ネットワークの価値の総和）を目的関数とする数理計画問題として定式化される。
【０００５】
非特許文献１においては、時系列で到着する仮想ネットワークに対して、ネットワークの各指標を勘案することで、ノードへの物理リソース（ＣＰＵ処理能力）及びネットワーク設備量を最適化する検討がされている。また、非特許文献２では、ノードの配置場所に若干の制約を設けた場合の問題が考察されている。
【０００６】
非特許文献３では、オンラインで仮想経路を割当てていく問題において、各サービス要求に異なる要求トラヒック量の総和が付与されている場合に、要求トラヒック量の総和を最大化するために必要に応じて受付を拒否する方式が提案されている。当該問題では、線型計画問題の0-1整数計画問題においてその双対問題を考えることで、目的関数である要求トラヒック量の総和の累積値の向上を実現している。
【０００７】
この他、組み合わせ問題としてよく知られるナップザック問題のオンライン版として、時系列で到着する荷物をオンラインでナップザックに収容し、適切に収容是非を判定することで、所定時間経過後におけるナップザック内の荷物の価値を最大化する問題も、オンラインナップザック問題として近年最適化アルゴリズムの研究が進められている（非特許文献４参照）。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Johannes Infuhr, Gunther R. Raidl, "Introducing the Virtual Network Mapping Problem with Delay, Routing and Location Constraints", Network Optimization Lecture Notes in Computer Science 6701 (2011), 105-117.
【非特許文献２】Chowdhury, N.M.M.K. Cheriton, Rahman, M.R. ; Boutaba, R., "Virtual Network Embedding with Coordinated Node and Link Mapping", Proc. INFOCOM2009.
【非特許文献３】G.Even, et. al., "Competitive and deterministic embeddings of virtual networks", Theory of Computer Science 496 (2013), 184--194.
【非特許文献４】D. Chakrabarty, et.al.., "Online Knapsack Problems", http://research.microsoft.com/en-us/um/people/dechakr/pubs/czk-full.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記の様に、物理ネットワークを運用管理するネットワーク事業者は、一般には独立な到着時刻順で提供開始を所望する各サービスに対し、当該物理ネットワークのリソース（ネットワーク帯域）を割り当て、仮想的なネットワークとして構成することで、ネットワーク上の各サービスを実現する。従って、可能な限り多くのサービスを物理ネットワーク上に収容し、実現することが、ネットワーク事業者としても、サービス事業者としても望ましい。そのためには、高効率で各サービスへの物理リソース割り当てを行い、サービスを実現することが肝要である。また、ネットワーク事業者としては、仮想ネットワーク構成に要するオペレーションの量、即ちリソースの再配置の実行頻度を抑制することも要求される。
【００１０】
このようなネットワーク仮想化技術を用いたネットワークサービスの提供形態において、提供開始を所望する各サービスに対して物理ネットワークのリソース割り当てを適切に実現することで、高効率で多くのサービスを収容することが求められている。
【００１１】
しかしながら、上記非特許文献に示される技術においては、目的関数として現在までの収容数のみを採用していることから、将来的な収容数を向上する問題としては定式化されていなかった。
【００１２】
また非特許文献１、２等に示される従来技術においては、データセンタにおける適用を主な目的としており、ノードのリソース割り当てが中心であった。また最適化される対象の性能指標としてオペレーションの実行回数などを勘案したものも報告されていない。また従来のＶＮＥ検討においては、リンクの埋め込みは帯域を勘案せず、k-shortest path first方式により設備量を最小化するものが殆どであった。
【００１３】
本発明は上記の点に鑑みてなされたものであり、物理ネットワーク上での仮想ネットワークのサービス提供の要求に対し、当該サービスを収容する物理ネットワークのリソースを割り当てる技術において、例えば、より少量の設備量とオペレーション稼働で、より多くのサービスを収容することを可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の一形態に係るネットワークリソース割当装置は、
物理ネットワーク上で仮想ネットワークのサービスを収容するために、当該物理ネットワークのリソースを割り当てるためのネットワークリソース割当装置であって、
前記仮想ネットワークのサービスの要求トラヒック量の総和を算出する要求トラヒック量総和算出部と、
前記仮想ネットワークのサービスに割り当て可能な物理ネットワーク上の候補経路を決定する受付可否判定部と、
前記決定された候補経路の中から、前記仮想ネットワークのサービスに経路を割り当てた場合、接続性を失うノード対の量を最小化する経路を決定する最適経路決定部と、
を有し、
前記受付可否判定部は、前記算出された要求トラヒック量の総和が所定の第１の閾値以下であり、媒介中心性の値が一定値以上である主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第２の閾値以下である場合、前記仮想ネットワークのサービスに経路を割り当てた場合の主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第３の閾値以上であることを要求する制約条件を設け、
前記最適経路決定部は、前記設けられた制約条件を勘案して、前記仮想ネットワークのサービスの経路を決定することを特徴とする。
【００１５】
また、本発明の一形態に係るネットワークリソース割当方法は、
物理ネットワーク上で仮想ネットワークのサービスを収容するために、当該物理ネットワークのリソースを割り当てるためのネットワークリソース割当装置におけるネットワークリソース割当方法であって、
前記仮想ネットワークのサービスに割り当て可能な物理ネットワーク上の候補経路を決定するステップと、
前記仮想ネットワークのサービスの要求トラヒック量の総和を算出するステップと、
前記算出された要求トラヒック量の総和が所定の第１の閾値以下であり、媒介中心性の値が一定値以上である主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第２の閾値以下である場合、前記仮想ネットワークのサービスに経路を割り当てた場合の主要な物理リンクの集合に含まれる物理リンクの残余帯域の最小値が第３の閾値以上であることを要求する制約条件を設けるステップと、
前記設けられた制約条件を勘案して、前記決定された候補経路の中から、前記仮想ネットワークのサービスに経路を割り当てた場合、接続性を失うノード対の量を最小化する経路を決定するステップと、
を有することを特徴とする。
【発明の効果】
【００１６】
本発明によれば、物理ネットワーク上での仮想ネットワークのサービス提供の要求に対し、当該サービスを収容する物理ネットワークのリソースを割り当てる技術において、より多くのサービスを収容することが可能になる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施形態に係るネットワークリソース割当装置の構成図
【図２】本発明の実施形態に係るネットワークリソース割当方法の概略フローチャート
【図３】本発明の第１実施形態に係るネットワークリソース割当方法のフローチャート
【図４】本発明の第２実施形態に係るネットワークリソース割当方法のフローチャート
【図５】本発明の第３実施形態に係るネットワークリソース割当方法のフローチャート
【図６】本発明の第４実施形態に係るネットワークリソース割当方法のフローチャート
【図７】本発明の実施形態のシミュレーションに用いた物理ネットワーク構成を示す図
【図８】本発明の第１及び第２実施形態による累積仮想ネットワーク帯域和と、最短経路方式による累積仮想ネットワーク帯域和との比較を示す図
【図９】本発明の第１及び第２実施形態による要求トラヒック量と、最短経路方式による要求トラヒック量との同数分布の比較を示す図
【図１０】本発明の第１及び第２実施形態による再配置実行回数累積値と、最短経路方式による再配置実行回数累積値の比較を示す図
【図１１】本発明の第１及び第３実施形態による累積仮想ネットワーク帯域和と、最短経路方式による累積仮想ネットワーク帯域和との比較を示す図
【図１２】本発明の第１及び第３実施形態による要求トラヒック量と、最短経路方式による要求トラヒック量との同数分布の比較を示す図
【図１３】本発明の第１及び第３実施形態による再配置実行回数累積値と、最短経路方式による再配置実行回数累積値の比較を示す図
【図１４】本発明の第１及び第４実施形態による累積仮想ネットワーク帯域和と、最短経路方式による累積仮想ネットワーク帯域和との比較を示す図
【図１５】本発明の第１及び第４実施形態による要求トラヒック量と、最短経路方式による要求トラヒック量との同数分布の比較を示す図
【図１６】本発明の第１及び第４実施形態による再配置実行回数累積値と、最短経路方式による再配置実行回数累積値の比較を示す図
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施形態について説明する。
【００１９】
本発明の実施形態では、一例として、物理ネットワーク上で仮想ネットワークのサービスを収容するために、当該物理ネットワークのリソースを割り当てるためのネットワークリソース割当装置について説明する。また、当該ネットワークリソース割当装置におけるネットワークリソース割当方法についても説明する。なお、以下で説明する実施形態は一例に過ぎず、本発明が適用される実施形態は、以下の実施形態に限られるわけではない。
【００２０】
本発明の実施形態では、既に示したように、物理ネットワーク上での展開を求める各種サービス（仮想ネットワークサービス）の要求がそれぞれ独立に到着し、ネットワーク事業者は各サービスに対して物理ネットワークのリソースを割り当て、物理ネットワーク上でサービスを実現することを想定している。各サービスは所定時間経過後に終了し、割り当てられた物理ネットワークのリソースを開放して退去する。また、通信事業者は当該サービスの提供時間を知り得ないものとする。各サービスは仮想ネットワークとしてネットワーク上で展開されるが、これは複数の仮想ノード対と、各ノード対でノード間に流れるトラヒック量、各サービスの到着および退去時刻の組として定式化される。
【００２１】
いま、あるサービス要求が到着した時に、物理ネットワークの帯域リソースが当該サービスの収容に不足している場合には、既に収容されているサービスの配置変更を行うことで、既存の収容サービスおよび前記到着サービスを収容可能であるか模索する。以下、当該プロセスを再配置と呼ぶ。本実施形態では、適切な性能評価指標を採用することで、当該指標の意味においてネットワークリソースの割当を最適に行うプロセスと、それを実現するためのアルゴリズムを記載する。
【００２２】
想定する物理リソース割当方式は、(i)サービス要求到着時の経路割当方式に関する部分と、(ii)再配置実行時に関するものに大別される。
【００２３】
(i)の経路割当方式は、サービス要求到着時に、物理ネットワークにおいて、リンクの残余帯域が要求トラヒック量を下回る場合には当該サービス要求を受付不可と判断する。更に、当該サービス要求の要求トラヒック量の総和とサービス収容状況とに応じて、物理経路選択のための制約条件を新規に課す。制約条件によりサービス要求の受付ができない場合には、再配置を行わなければサービス要求を受付不可と判断するものである。
【００２４】
(ii)の再配置実行方式は、到着サービス要求の要求トラヒック量の総和に依存して再配置における入れ替え経路数（再配置を行う対象となる既存サービスの数量）や実行回数（再配置実行回数）の上限を課す方式である。
【００２５】
＜ネットワークリソース割当装置の構成＞
図１は、本発明の実施形態に係るネットワークリソース割当装置１００の構成図である。
【００２６】
ネットワークリソース割当装置１００は、単一もしくは複数のコンピュータ上で、本実施形態で説明する処理内容を実装したプログラムを動作させることで実現される。上記プログラムはネットワーク上で提供されるなど、物理的に他の媒体に保存されていることも可能である。また、ネットワークリソース割当装置１００は、サービス提供を行う物理ネットワークに接続されても良いし、単独で動作する装置であっても良い。
【００２７】
ネットワークリソース割当装置１００は、物理ネットワーク上で仮想ネットワークとしてのサービス提供を要求する各要求に対して物理ネットワークのリソース割当を行う装置である。サービス要求の到着時に、当該サービスに割り当てる経路（物理経路対）を決定する過程において、当該サービスの要求トラヒック量の総和を算出する。そして、算出された要求トラヒック量の総和とサービス収容状況とに応じて、新たに制約条件を設けて数理計画問題を計算することで、(i)サービス要求受付成功率、(ii)収容した仮想ネットワークのトラヒック量の総和の累積値、(iii)サービス要求あたり再配置実行回数の逆数のいずれか又はそれらの加重和を向上する。その結果、より少量の設備量とオペレーション稼働で、より多くのサービスを収容することを可能とする。
【００２８】
すなわち、ネットワークリソース割当装置１００は、以下のいずれかの性能評価指標を最適化する。
【００２９】
1.時間無限大における受付成功率
2.時間無限大における、サービス要求あたり再配置実行回数
3.時間無限大における、サービス要求あたり要求トラヒック量の総和
これらの性能評価指標を最大化もしくは最小化する問題は、一般にはNP困難な整数計画問題であり、実時間における確定的な理論解の算出は困難である。そこで、物理経路選出過程において、所定のコスト関数を定め、それを最小化するヒューリスティックなアプローチを採用することにより、実時間での実現を図る。
【００３０】
具体的には、図１に示すように、ネットワークリソース割当装置１００は、性能評価指標入力部１０１と、物理ネットワーク情報入力部１０２と、サービス要求入力部１０３と、要求トラヒック量総和算出部１０４と、受付可否判定部１０５と、最適経路決定部１０６と、再配置実行部１０７と、リソース割当部１０８と、選出経路対蓄積部１０９とを含む。
【００３１】
性能評価指標入力部１０１は、上記の３つの性能評価指標のいずれかを入力する。入力された性能評価指標は、例えば、受付可否判定部１０５におけるサービスの受付可否の判定のため、最適経路決定部１０６における経路の選出のため、また、再配置実行部１０７における再配置の実行のために用いられる。
【００３２】
物理ネットワーク情報入力部１０２は、物理ネットワーク情報を入力する。例えば、物理ネットワークの物理リンクの媒介中心性（主要なリンクの指標）、物理リンクの残余帯域等の情報が入力される。
【００３３】
サービス要求入力部１０３は、各サービス要求の情報を入力する。例えば、サービス要求の仮想経路の要求トラヒック量等の情報が入力される。サービス要求入力部１０３にて入力されたサービス要求の情報に基づき、図２に示すように、ネットワークリソース割当装置１００において順次リソース割当処理が実施される。
【００３４】
図２は、本発明の実施形態に係るネットワークリソース割当方法の概略フローチャートである。図２を参照して、要求トラヒック量総和算出部１０４、受付可否判定部１０５、最適経路決定部１０６、再配置実行部１０７、リソース割当部１０８及び選出経路対蓄積部１０９について更に説明する。
【００３５】
要求トラヒック量総和算出部１０４は、サービスの要求トラヒック量の総和を算出する。
【００３６】
受付可否判定部１０５は、サービス要求の到着時に当該到着サービスに対して割り当て可能な物理ネットワーク上の候補経路の存在有無を判定することにより、サービスの受付可否を判定する（Ｓ１０１）。受付可否判定部１０５は、仮想ネットワークのサービスに割り当て可能な物理ネットワーク上の候補経路を決定し、候補経路に含まれる物理リンクの最小残余帯域がサービスの要求トラヒック量以上であることを確認し、いずれかの物理リンクの最小残余帯域が要求トラヒック量を下回る場合、候補経路から除外する。そして、受付可否判定部１０５は、候補経路が存在しない場合、既存サービスのリソースの再配置が必要であると判定する。
【００３７】
また、受付可否判定部１０５は、要求トラヒック量総和算出部１０４において算出された要求トラヒック量の総和とサービス収容状況とに応じて、新たに制約条件を設けてもよい。制約条件によりサービス要求の受付ができない場合には、再配置が必要であると判定する。
【００３８】
最適経路決定部１０６は、候補経路が存在する場合に、当該候補経路の中から所定のコストを最小化する最適経路を決定する（Ｓ１０３）。ここでは、時間無限大における受付成功率を最大化するため、最適経路決定部１０６は、候補経路の中から、前記仮想ネットワークのサービスに経路を割り当てた場合、接続性を失うノード対の量を最小化する経路を決定する。
【００３９】
再配置実行部１０７は、受付可否判定部１０５において仮想ネットワークのサービスに割り当て可能な候補経路が存在しないと判定された場合、既存サービスのリソースの再配置を実施する（Ｓ１０５）。再配置実行部１０７は、既存サービスを物理ネットワークから一旦取り出して、当該既存サービスと前記到着サービスとを併せて物理ネットワークに収容させることで再配置を行う。
【００４０】
リソース割当部１０８は、サービスに対する物理リソース割り当てを決定し出力する。
【００４１】
選出経路対蓄積部１０９は、最適経路決定部１０６又は再配置実行部１０７において決定された仮想ネットワークのサービスに割り当てられる経路（選出経路対）の情報、再配置の対象となる既存サービスの経路（選出経路対）の情報等を蓄積する。
【００４２】
＜第１実施形態＞
次に、図３を参照して本発明の第１実施形態について説明する。本発明の第１実施形態は、サービス要求到着時の物理リソース選出に関するものである。サービス要求VNj到着時、受付可否判定部１０５が、以下に記載する処理を行うことで、当該サービス要求VNjの受付可否もしくは再配置処理の要否を判定する。
【００４３】
まず、受付可否判定部１０５は、前記物理ネットワークの主要なリンクの集合
【００４４】
【数１】
0006374825.tif 000002
を以下により定義する：
【００４５】
【数２】
0006374825.tif 000003
ここでLは物理ネットワークの物理リンク集合、b(l)は物理リンクlの媒介中心性、B(L,α)は物理ノードの全物理リンクの媒介中心性の値のα%値である。例えばα=0.9の場合、主要なリンクの集合
【００４６】
【数３】
0006374825.tif 000004
は、媒介中心性の値が90%以上である物理リンクの集合を示す。媒介中心性は、当該リンクが他のノード間の通信の最短経路として用いられる割合を示す指標であるから、当該集合は、その意味において、重要なリンクの集合であるということができる。
【００４７】
続いてk-shortest path firstアルゴリズムにより、物理ネットワークの情報から、当該サービス要求に含まれる各仮想経路について、その送信元ノードと宛先ノード間のk本の候補経路Rj（j=1,...,k）を抽出する（Ｓ２０１）。さらに、前記抽出したk本の候補経路について、それに含まれる物理リンクの最小残余帯域が要求トラヒック量以上であることを確認する。当該候補経路に含まれるいずれかの物理リンクにおいて、残余帯域が要求トラヒック量を下回る場合には、当該候補経路を割り当てることはできないため、候補経路から除外する。
【００４８】
こうして、受付可否判定部１０５は、仮に前記k本の候補経路全てが割当不可である場合には、再配置が必要であると判定する（Ｓ２０３）。ここで前記kの値は計算時間に対する要件のもとで可能な限り大きい値とする。
【００４９】
更に、受付可否判定部１０５は、要求トラヒック量総和算出部１０４において当該サービス要求VNjの要求トラヒック量の総和rjを以下により計算する（Ｓ２０５）：
【００５０】
【数４】
0006374825.tif 000005
ここでe'は仮想経路、Ejはサービス要求に含まれる仮想経路の集合、
【００５１】
【数５】
0006374825.tif 000006
はサービス要求の仮想経路e'に含まれる仮想経路の要求トラヒック量を示す。そして、rj≦ε1でありかつ
【００５２】
【数６】
0006374825.tif 000007
に含まれるリンクの残余帯域の最小値がε0以下である場合には、当該経路を使用した場合における
【００５３】
【数７】
0006374825.tif 000008
に含まれるリンクの残余帯域の最小値がε2以上であることを要求する（Ｓ２０７）。
【００５４】
上記の制約を勘案した上で、前記k本の候補経路中、いずれの経路が割当可能である場合には、最適経路決定部１０６において、当該候補経路の集合から、以下に述べる目的関数の観点で最適な経路を選出する（Ｓ２０９）。
【００５５】
【数８】
0006374825.tif 000009
ここでEc(v1,v2;G(V,E,ue))は、ノード集合V、エッジ集合E、重みベクトルueの重み付き無向グラフにおけるノードv1、v2間の局所辺連結度を示す。ベクトルcは各物理リンクの残余帯域から所定値を差し引いた値を示すベクトルであり、ベクトルyiは、既存サービスに関して仮想ネットワークiが各物理リンクを使用するときに1を示し、使用しないときに0を示すベクトルであり、ベクトルAiは既存サービスに関して仮想ネットワークiに使われている各物理リンクのトラヒック量を示すベクトルである。ベクトルyjは、到着サービスに関して仮想ネットワークjが各物理リンクを使用するときに1を示し、使用しないときに0を示すベクトルであり、ベクトルAjは到着サービスに関して仮想ネットワークjに使われる各物理リンクのトラヒック量を示すベクトルである。即ち、上記目的関数は、サービス要求VNjに当該経路を割当てた場合において、接続性を失うノード対の数量を最小化することを目的としている。上記目的関数を計算することで、接続性を失うノード対の数量を最小化する到着サービスの候補経路yj=Rj'(j'=1,...,k')を求める（Ｓ２１１）。
【００５６】
求められた候補経路Rj'が複数の場合（j'≧2）、候補経路Rj'の中からランダムに経路が抽出されてもよい（Ｓ２１３）。また、求められた候補経路Rj'が単一の場合（j'=1）、その経路を最適経路と決定する（Ｓ２１５）。
【００５７】
次のサービス要求が到着した場合、j=ji+1として、上記の手順が繰り返される（Ｓ２１７）。
【００５８】
このように、最適経路決定部１０６は、到着サービスに経路を割り当てるときに、ネットワークを、その各物理リンクの残余帯域から所定値を差し引いた値と０の最大値を重みとする無向グラフと看做し、その各ノード間の局所辺連結度が零になるノード対の数を目的関数に設定する。この目的関数によって経路を計算するときに、上記のように、当該サービス要求の要求トラヒック量の総和が所定値以下であり、かつ、主要な物理リンクの集合（媒介中心性が所定値以上の物理リンク）に含まれる物理リンクの残余帯域の最小値が所定値以下である場合には、到着サービスに経路を割り当てたときに主要な物理リンクにおける残余帯域が所定値以上であることを制約条件として課す。
【００５９】
このようにすることで、要求トラヒック量の総和が小さいにも拘わらず主要なリンクを占有するサービス要求を排除し、より高効率に高い要求トラヒック量の総和のサービス要求収容を可能にしていくことができる。上記制約条件によりサービス要求VNjの受付ができない場合には、再配置が必要であると判定する。
【００６０】
＜第２実施形態＞
次に、図４を参照して本発明の第２実施形態について説明する。本発明の第２実施形態は、再配置の実行プロセスに係る。到着サービスに対するリソース不足等により再配置実施を決定すると、再配置実行部１０７は所定のプロセスに基づき既存サービスへのリソース割当を見直し、到着サービス要求と併せて収容可否を模索する。
【００６１】
具体的には、再配置実行部１０７は、既存サービスを物理ネットワークから一旦取り出して、当該既存サービスと到着サービスとを併せて物理ネットワークに収容させることで再配置を行う。ここで、再配置実行部１０７は、受付可否判定部１０５が課したのと同じ制約条件の下で、候補となる物理経路対を探索する。即ち、到着サービスVNjに加えて再配置の対象となる既存サービスの要求トラヒック量の総和rjを算出し（Ｓ３０１）、rj≦ε1かつ
【００６２】
【数９】
0006374825.tif 000010
に含まれるリンクの残余帯域の最小値がε0以下である場合には、再配置を実施した場合における
【００６３】
【数１０】
0006374825.tif 000011
に含まれるリンクの残余帯域の最小値がε2以上であることを要求する（Ｓ３０３）。
【００６４】
再配置実行部１０７は、上記の制約を勘案した上で、再配置を試みる（Ｓ３０５）。いずれかの経路が割当可能である場合には、第１実施形態と同様にして最適な経路を選出し（Ｓ３０７）、リソース割当部１０８が物理リソースを割り当てる（Ｓ３０９）。
【００６５】
一方、割当可能な経路が存在しない場合、再配置実行部１０７は、再配置の対象となる既存サービスを変更して再配置を試みる（Ｓ３１１）。再配置実行回数の上限N∞に達しても制約条件を満たすリソース配分が実現できない場合には、受付可否判定部１０５において、当該到着サービス要求の受付を不可と判定する（Ｓ３１３）。
【００６６】
＜第３実施形態＞
次に、図５を参照して本発明の第３実施形態について説明する。本発明の第３実施形態においても、第２実施形態と同様に、既存サービスを物理ネットワークから一旦取り出して、当該既存サービスと到着サービスとを併せて物理ネットワークに収容させることで再配置を行う。ここで、再配置実行部１０７は、受付可否判定部１０５が課したのと同じ制約条件の下で、候補となる物理経路対を探索する。即ち、到着サービスVNjに加えて再配置の対象となる既存サービスの要求トラヒック量の総和rjを算出し、再配置を試みる（Ｓ４０１）。
【００６７】
ただし、本発明の第３実施形態においては、前記再配置実行部１０７が再配置を行う場合において、再配置実行回数に対して、到着サービスの要求トラヒック量の総和に依存した上限値を設ける（Ｓ４０３）。即ち、その再配置実行回数の上限N∞は、例えば、以下のように、当該時点における到着サービス要求の要求トラヒック量の総和rjに関する広義単調増加関数とする。
【００６８】
【数１１】
0006374825.tif 000012
再配置実行部１０７は、第２実施形態と同様にして設定された制約を勘案した上で、再配置を試みる（Ｓ４０５）。いずれかの経路が割当可能である場合には、第１実施形態と同様にして最適な経路を選出し（Ｓ４０７）、リソース割当部１０８が物理リソースを割り当てる（Ｓ４０９）。
【００６９】
一方、割当可能な経路が存在しない場合、再配置実行部１０７は、再配置の対象となる既存サービスを変更して再配置を試みる（Ｓ４１１）。再配置実行回数の上限N∞に達しても制約条件を満たすリソース配分が実現できない場合には、受付可否判定部１０５において、当該到着サービス要求の受付を不可と判定する（Ｓ４１３）。
【００７０】
これによって、要求トラヒック量の総和が小さいサービス要求に対しては再配置の探索空間を狭めることで探索時間を効率化することができる。
【００７１】
＜第４実施形態＞
次に、図６を参照して本発明の第４実施形態について説明する。本発明の第４実施形態においても、第２実施形態と同様に、既存サービスを物理ネットワークから一旦取り出して、当該既存サービスと到着サービスとを併せて物理ネットワークに収容させることで再配置を行う。ここで、再配置実行部１０７は、受付可否判定部１０５が課したのと同じ制約条件の下で、候補となる物理経路対を探索する。即ち、到着サービスVNjに加えて再配置の対象となる既存サービスの要求トラヒック量の総和rjを算出し、再配置を試みる（Ｓ５０１）。
【００７２】
本発明の第４実施形態においては、再配置実行部１０７が再配置を行う場合において、再配置を行う対象となる既存サービスの数量に対して、到着サービスの要求トラヒック量の総和に依存した上限値を設ける（Ｓ５０３）。すなわち、再配置のときに、見直しを行う既存サービスの数量pに対して、当該時点におけるサービス要求の要求トラヒック量の総和rjに関する広義単調増加関数であることを要求する。
【００７３】
再配置実行部１０７は、第２実施形態と同様にして設定された制約を勘案した上で、再配置を試みる（Ｓ５０５）。いずれかの経路が割当可能である場合には、第１実施形態と同様にして最適な経路を選出し（Ｓ５０７）、リソース割当部１０８が物理リソースを割り当てる（Ｓ５０９）。
【００７４】
一方、割当可能な経路が存在しない場合、再配置実行部１０７は、再配置の対象となる既存サービスを変更して再配置を試みる（Ｓ５１１）。再配置実行回数の上限N∞に達しても制約条件を満たすリソース配分が実現できない場合には、受付可否判定部１０５において、当該到着サービス要求の受付を不可と判定する（Ｓ５１３）。
【００７５】
これによって、要求トラヒック量の総和が小さいサービス要求に対しては再配置の探索空間を狭めることで探索時間を効率化することができる。
【００７６】
＜第１及び第２実施形態の評価結果＞
次に、本発明の実施形態を数値実験により評価する。本実施形態では、時間は無次元の実数で表すこととする。数値実験による評価に際しては、複数のサービス要求到着パターンを用意し、同一の物理ネットワーク上でそれぞれに対する収容の模様をシミュレーションした結果に基づき比較を行う。
【００７７】
以下のシミュレーションにおいて、図７に示すように、物理ネットワークは１５ノードから構成される接続率0.1のランダムグラフの一標本とする。サービス要求はそれぞれM本の仮想経路から構成される。ただしMは確率変数で、
M=max{0,x},  x∈N(3,2)
またサービス要求到着パターンは平均λ=1のPoisson到着、平均滞在時間μ=20の指数分布に従うとする。即ち、各サービス要求は到着後、所定時間経過後に退去する。仮想パスの送信元、あて先はいずれも物理ノードの集合Vからランダムに非復元抽出され、300サービス要求到着までシミュレーションを実行する。
【００７８】
比較するアルゴリズムは最短経路方式と本発明の実施形態における提案方式とする。前者はサービス要求到着時に、リンク容量の制約のもとで各仮想パスに対する割当物理経路の経路長総和をコストとする方式である。
【００７９】
提案方式では、前記各パラメータ値を以下の通り設定して評価を行う：
ε1=30、ε0=20、ε2=10
上記の条件において、図８〜１０に定常状態における両方式の比較結果を示す。
【００８０】
図８は、本発明の第１及び第２実施形態による累積仮想ネットワーク帯域和と、最短経路方式による累積仮想ネットワーク帯域和との比較を示す図であり、図９は、本発明の第１及び第２実施形態による要求トラヒック量と、最短経路方式による要求トラヒック量との同数分布の比較を示す図であり、図１０は、本発明の第１及び第２実施形態による再配置実行回数累積値と、最短経路方式による再配置実行回数累積値の比較を示す図である。
【００８１】
図８から、本発明の第１及び第２実施形態の方が、最短経路方式に比べて累積要求トラヒック量の総和が大きいことが分かる。また、図９から、本発明の第１及び第２実施形態の方が、最短経路方式に比べて帯域の大きい仮想ネットワークを収容できることが分かる。更に、図１０から、本発明の第１及び第２実施形態の方が、最短経路方式に比べて再配置実行回数が少量であることが分かる。
【００８２】
＜第１及び第３実施形態の評価結果＞
次に、本発明の第１及び第３実施形態を数値実験により評価する。ここでは、再配置実施時における試行回数の上限N∞は、要求トラヒック量の総和の関数として、
【００８３】
【数１２】
0006374825.tif 000013
としている。ここで[x]は実数xの整数部分である。結果を図１１〜図１３に示す。
【００８４】
図１１は、本発明の第１及び第３実施形態による累積仮想ネットワーク帯域和と、最短経路方式による累積仮想ネットワーク帯域和との比較を示す図であり、図１２は、本発明の第１及び第３実施形態による要求トラヒック量と、最短経路方式による要求トラヒック量との同数分布の比較を示す図であり、図１３は、本発明の第１及び第３実施形態による再配置実行回数累積値と、最短経路方式による再配置実行回数累積値の比較を示す図である。
【００８５】
第１及び第２実施形態の評価結果と同様に、図１１から、本発明の第１及び第３実施形態の方が、最短経路方式に比べて累積要求トラヒック量の総和が大きいことが分かる。また、図１２から、本発明の第１及び第３実施形態の方が、最短経路方式に比べて帯域の大きい仮想ネットワークを収容できることが分かる。更に、図１３から、本発明の第１及び第３実施形態の方が、最短経路方式に比べて再配置実行回数が少量であることが分かる。
【００８６】
＜第１及び第４実施形態の評価結果＞
次に、本発明の第１及び第４実施形態を数値実験により評価する。ここでは、再配置実施時における見直し対象の既存サービス数の上限pは、要求トラヒック量の総和の関数として、
【００８７】
【数１３】
0006374825.tif 000014
としている。結果を図１４〜図１６に示す。
【００８８】
図１４は、本発明の第１及び第４実施形態による累積仮想ネットワーク帯域和と、最短経路方式による累積仮想ネットワーク帯域和との比較を示す図であり、図１５は、本発明の第１及び第４実施形態による要求トラヒック量と、最短経路方式による要求トラヒック量との同数分布の比較を示す図であり、図１６は、本発明の第１及び第４実施形態による再配置実行回数累積値と、最短経路方式による再配置実行回数累積値の比較を示す図である。
【００８９】
第１及び第２実施形態の評価結果と同様に、図１４から、本発明の第１及び第４実施形態の方が、最短経路方式に比べて累積要求トラヒック量の総和が大きいことが分かる。また、図１５から、本発明の第１及び第４実施形態の方が、最短経路方式に比べて帯域の大きい仮想ネットワークを収容できることが分かる。更に、図１６から、本発明の第１及び第４実施形態の方が、最短経路方式に比べて再配置実行回数が少量であることが分かる。
【００９０】
＜本発明の実施形態の効果＞
本発明の実施形態によれば、ネットワーク仮想化の技術を生かして、より少量のオペレーション稼動で、より要求トラヒック量の総和の高いサービスを収容することができる。
【００９１】
説明の便宜上、本発明の実施形態に係るネットワークリソース割当装置は機能的なブロック図を用いて説明しているが、本発明の実施形態に係るネットワークリソース割当装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、本発明の実施形態は、コンピュータに対して本発明の実施形態に係るネットワークリソース割当装置の各機能を実現させるプログラム、コンピュータに対して本発明の実施形態に係る方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。また、本発明の実施形態に係る方法は、実施形態に示す順序と異なる順序で実施されてもよい。
【００９２】
以上、物理ネットワーク上での仮想ネットワークのサービス提供の要求に対し、当該サービスを収容する物理ネットワークのリソースを割り当てる技術において、より多くのサービスを収容するための手法について説明したが、本発明は、上記の実施形態に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【００９３】
１００  ネットワークリソース割当装置
１０１  性能評価指標入力部
１０２  物理ネットワーク情報入力部
１０３  サービス要求入力部
１０４  要求トラヒック量総和算出部
１０５  受付可否判定部
１０６  最適経路決定部
１０７  再配置実行部
１０８  リソース割当部
１０９  選出経路対蓄積部
【図１】
0006374825.tif 000015
【図２】
0006374825.tif 000016
【図３】
0006374825.tif 000017
【図４】
0006374825.tif 000018
【図５】
0006374825.tif 000019
【図６】
0006374825.tif 000020
【図７】
0006374825.tif 000021
【図８】
0006374825.tif 000022
【図９】
0006374825.tif 000023
【図１０】
0006374825.tif 000024
【図１１】
0006374825.tif 000025
【図１２】
0006374825.tif 000026
【図１３】
0006374825.tif 000027
【図１４】
0006374825.tif 000028
【図１５】
0006374825.tif 000029
【図１６】
0006374825.tif 000030