(57)【特許請求の範囲】
【請求項１】
サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定部と、
前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する第１の選出部とを有し、
前記判定部は、前記物理ネットワークを構成する各リンクの残余帯域を重みとする無向グラフにおいて、前記割当要求に係る仮想ネットワークのトラヒック量に基づいて、当該仮想ネットワークに対する物理経路について、１以上の候補を抽出し、
前記第１の選出部は、前記無向グラフについて、局所辺連結度が零になるノード対の数を目的関数に設定し、前記目的関数に基づいて、前記１以上の候補の中から１つの物理経路を選出し、
前記判定部は、前記仮想ネットワークのトラヒック量が第１の所定値未満である場合には、当該トラヒック量が前記第１の所定値以上である場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定し
前記制約は、局所辺連結度が零になるノード対の数を第２の所定値以下にするという制約である、
ことを特徴とする物理経路割当装置。
【請求項２】
前記判定部は、更に、過去の仮想ネットワークの平均滞在時間と、前記過去の仮想ネットワークのトラヒック量とが所定の条件を満たす場合に、前記制約を課して、前記物理経路の割り当ての可否を判定する、
ことを特徴とする請求項１記載の物理経路割当装置。
【請求項３】
前記判定部によって、前記物理経路の割り当てが不可能であると判定された場合に、前記物理ネットワークに収容されている他の仮想ネットワークの中から任意の仮想ネットワークを取り出し、取り出された仮想ネットワークと、前記割当要求に係る仮想ネットワークとに基づいて新たな仮想ネットワークを生成し、当該新たな仮想ネットワークについて、数理計画問題を計算して物理経路を選出する第２の選出部、
を有し、
前記第２の選出部は、前記割当要求に係る仮想ネットワークのトラヒック量が前記第１の所定値未満であり、かつ、過去の仮想ネットワークの平均滞在時間と、前記過去の仮想ネットワークのトラヒック量とが所定の条件を満たす場合には、局所辺連結度が零になるノード対の数を前記第２の所定値以下にするという制約を課して、前記物理経路を選出する、
ことを特徴とする請求項１又は２記載の物理経路割当装置。
【請求項４】
コンピュータが、
サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定手順と、
前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する選出手順とを実行し、
前記判定手順は、前記物理ネットワークを構成する各リンクの残余帯域を重みとする無向グラフにおいて、前記割当要求に係る仮想ネットワークのトラヒック量に基づいて、当該仮想ネットワークに対する物理経路について、１以上の候補を抽出し、
前記選出手順は、前記無向グラフについて、局所辺連結度が零になるノード対の数を目的関数に設定し、前記目的関数に基づいて、前記１以上の候補の中から１つの物理経路を選出し、
前記判定手順は、前記仮想ネットワークのトラヒック量が第１の所定値未満である場合には、当該トラヒック量が前記第１の所定値以上である場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定し、
前記制約は、局所辺連結度が零になるノード対の数を第２の所定値以下にするという制約である、
ことを特徴とする物理経路割当方法。
【請求項５】
コンピュータに、
サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定手順と、
前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する選出手順とを実行させ、
前記判定手順は、前記物理ネットワークを構成する各リンクの残余帯域を重みとする無向グラフにおいて、前記割当要求に係る仮想ネットワークのトラヒック量に基づいて、当該仮想ネットワークに対する物理経路について、１以上の候補を抽出し、
前記選出手順は、前記無向グラフについて、局所辺連結度が零になるノード対の数を目的関数に設定し、前記目的関数に基づいて、前記１以上の候補の中から１つの物理経路を選出し、
前記判定手順は、前記仮想ネットワークのトラヒック量が第１の所定値未満である場合には、当該トラヒック量が前記第１の所定値以上である場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定し、
前記制約は、局所辺連結度が零になるノード対の数を第２の所定値以下にするという制約である、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物理経路割当装置、物理経路割当方法、及びプログラムに関する。
【背景技術】
【０００２】
仮想化技術の進展に伴い、ストレージやサーバのみならず、ネットワークにおいてＵプレーンとＣプレーンとを分離するネットワーク仮想化技術が進展している。当該技術を用いた世界においては、従来の様なネットワークサービスと設備との固定的な関係は解消し、より柔軟なつながりが実現されていく。すなわち、ネットワークを運営するネットワーク事業者が提供する物理的なネットワーク（以下「物理ネットワーク」という）上でサービスを展開する各事業者は、それぞれ独立なタイミング及び順番で当該サービスの提供を開始し、また、一般には、所定時間経過後にサービスを終了する。
【０００３】
物理ネットワークを運用管理するネットワーク事業者は、上記の様に一般には独立な到着時刻順で提供の開始を所望する各サービスに対し、当該物理ネットワークのリソース（ネットワーク帯域）を割り当て、仮想的なネットワークとして構成することで、ネットワーク上の各サービスを実現していく。従って、可能な限り多くのサービスを物理ネットワーク上に収容し、実現することが、ネットワーク事業者としても、サービス事業者としても望ましい。そのためには、高効率で各サービスへの物理リソースの割り当てを行い、サービスを実現することが肝要である。また、ネットワーク事業者としては、仮想ネットワークの構成に要するオペレーションの量、すなわち、リソースの再配置の実行頻度を抑制することも重要である。
【０００４】
したがって、このようなネットワーク仮想化技術を用いたネットワークサービスの提供形態において、提供の開始を所望する各サービスに対して物理ネットワークのリソースの割り当てを適切に実現することで、高効率で多くのサービスを収容することが求められている。
【０００５】
上記サービスへの物理リソースの割り当ては、Virtual Network Embedding（以下「ＶＮＥ」という。）と呼ばれる問題として定式化され、近年多くの研究が報告されている。これは、所与の物理ネットワーク及び時系列で到着するサービスを重み付き無向グラフとしてモデル化し、各サービスに対して、物理ネットワークのリソースを割り当てていく問題である。一般には、ノード、リンクとも物理的配置箇所は自由であり、多くの場合、受付成功率や要求トラヒック量の総和（受付ネットワークの価値の総和）を目的関数とする数理計画問題として定式化される。
【０００６】
非特許文献１においては、時系列で到着する仮想ネットワークに対して、ネットワークの各指標を勘案することで、ノードへの物理リソース（ＣＰＵ処理能力）及びネットワーク設備量を最適化することが検討されている。また、非特許文献２では、ノードの配置場所に若干の制約を設けた場合の問題が考察されている。
【０００７】
非特許文献３では、オンラインで仮想経路を割り当てていく問題において、各サービス要求に異なる要求トラヒック量の総和が付与されている場合において、要求トラヒック量の総和を最大化するために必要に応じて受け付けを拒否する方式が提案されている。当該問題では、線型計画問題の０−１整数計画問題においてその双対問題を考えることで、目的関数である要求トラヒック量の総和の累積値の向上を実現している。
【０００８】
この他、組み合わせ問題としてよく知られるナップザック問題のオンライン版として、時系列で到着する荷物をオンラインでナップザックに収容し、適切に収容の是非を判定することで、所定時間経過後におけるナップザック内の荷物の価値を最大化する問題も、オンラインナップザック問題として、近年、最適化アルゴリズムの研究が進められている（非特許文献４）。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Johannes Infuhr, Gunther R. Raidl, "Introducing the Virtual Network Mapping Problem with Delay, Routing and Location Constraints" Network Optimization Lecture Notes in Computer Science6701( 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", [online], [平成27年6月1日検索], インターネット(URL:http://research.microsoft.com/en-us/um/people/dechakr/pubs/czk-full.pdf)
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記非特許文献に示される技術においては、目的関数として現在までの収容数のみを採用していることから、将来的な収容数を向上する問題としては定式化されていない。
【００１１】
また非特許文献１、２等に示される従来技術においては、データセンタにおける適用を主な目的としており、ノードのリソース割り当てが中心であった。また、最適化される対象の性能指標としてオペレーションの実行回数などを勘案したものも報告されていない。また、従来のＶＮＥ検討においては、リンクの埋め込みは帯域を勘案せず、k-shortest path first方式により設備量を最小化するものが殆どであった。
【００１２】
本発明は、上記の点に鑑みてなされたものであって、物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすることを目的とする。
【課題を解決するための手段】
【００１３】
そこで上記課題を解決するため、物理経路割当装置は、サービスに利用される仮想ネットワークに対する、物理ネットワーク上の物理経路の割当要求に応じ、当該仮想ネットワークのトラヒック量と、当該物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、当仮想ネットワークに対する物理経路の割り当ての可否を判定する判定部と、前記物理経路の割り当てが可能であると判定された場合に、数理計画問題を計算して、前記割当要求に係る仮想ネットワークに対する物理経路を選出する第１の選出部とを有し、前記判定部は、前記物理ネットワークを構成する各リンクの残余帯域を重みとする無向グラフにおいて、前記割当要求に係る仮想ネットワークのトラヒック量に基づいて、当該仮想ネットワークに対する物理経路について、１以上の候補を抽出し、前記第１の選出部は、前記無向グラフについて、局所辺連結度が零になるノード対の数を目的関数に設定し、前記目的関数に基づいて、前記１以上の候補の中から１つの物理経路を選出し、前記判定部は、前記仮想ネットワークのトラヒック量が第１の所定値未満である場合には、当該トラヒック量が前記第１の所定値以上である場合には課せられない制約を課して、前記物理経路の割り当ての可否を判定し前記制約は、局所辺連結度が零になるノード対の数を第２の所定値以下にするという制約である。
【発明の効果】
【００１４】
物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態におけるネットワークリソース割当装置のハードウェア構成例を示す図である。
【図２】本発明の実施の形態におけるネットワークリソース割当装置の機能構成例を示す図である。
【図３】本発明の実施の形態におけるネットワークリソース割当装置が実行する処理手順の概要を説明するための図である。
【図４】サービス要求到着時の最適経路の決定処理を説明するための図である。
【図５】再配置処理を説明するための図である。
【図６】シミュレーションに利用された物理ネットワークを示す無向グラフの構成例を示す図である。
【図７】定常状態における既存方式と提案方式との比較結果を示す図である。
【図８】定常状態の時刻ｔ＝２５０における収容中の仮想ネットワークの要求トラヒック量の度数分布示す図である。
【図９】１００サンプルのサービス要求パターンに関する既存方式と提案方式との比較結果を示す図である。
【発明を実施するための形態】
【００１６】
以下、図面に基づいて本発明の実施の形態を説明する。本発明の実施の形態では、物理ネットワーク上での仮想ネットワークの展開を求める各種サービス（仮想ネットワークサービス）の要求がそれぞれ独立に到着し、ネットワーク事業者が、各サービスに対して物理ネットワークのリソース（物理的な経路。以下「物理経路」という。）を割り当てて、物理ネットワーク上でサービスを実現することを想定する。各サービスは所定時間経過後に終了し、割り当てられた物理経路を開放して退去する。また、通信事業者は、サービスの提供時間（サービスが提供されるタイミング）を知り得ないものとする。各サービスは仮想ネットワークとして物理ネットワーク上で展開されるが、仮想ネットワークは、１以上の仮想経路によって構成される。仮想ネットワークは、当該仮想ネットワークを構成する仮想経路ごとの仮想ノード対（送信元ノード、あて先ノード）、当該仮想経路ごとの仮想ノード対で仮想ノード間に流れるトラヒック量（要求トラヒック量）、並びに各仮想経路に共通の到着時刻及び退去時刻の組として定式化される。なお、各仮想経路は、仮想ネットワークに流れる各フローに対応する。
【００１７】
あるサービス要求が到着した時に、物理ネットワークの帯域リソースが当該サービスに係る仮想ネットワークの収容に不足している場合には、既に収容されている仮想ネットワークの配置変更を行うことで、既存の仮想ネットワーク及び新たに到着したサービスに係る仮想ネットワークを収容可能であるかを模索する。以下、当該プロセスを「再配置」と呼ぶ。本実施の形態では、適切な性能評価指標を採用することで、当該指標の意味においてネットワークリソースの割り当てを最適に行うプロセスと、それを実現するためのアルゴリズムとを記載する。
【００１８】
想定する物理リソース割当方式は、（ｉ）サービス要求到着時の経路割当方式に関する部分と、（ｉｉ）再配置実行時の再配置実行方式に関する部分とに大別される。
【００１９】
（ｉ）の経路割当方式は、サービス要求到着時に、当該サービス要求の要求トラヒック量の総和（仮想経路ごとの要求トラヒック量の総和）が所定値以下の場合においては、物理経路選択のための制約を新規に課し、物理ネットワークにおいて、別途指定される所定のリンクの残余使用率が所定値以下の場合には、当該サービス要求を受付不可と判断するものである。
【００２０】
（ｉｉ）の再配置実行方式は、到着したサービス要求の要求トラヒック量の総和に依存して、再配置における入れ替え経路数や実行回数の上限を課す方式である。
【００２１】
図１は、本発明の実施の形態におけるネットワークリソース割当装置のハードウェア構成例を示す図である。図１のネットワークリソース割当装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００２２】
ネットワークリソース割当装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２３】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従ってネットワークリソース割当装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２４】
図２は、本発明の実施の形態におけるネットワークリソース割当装置の機能構成例を示す図である。ネットワークリソース割当装置１０は、例えば、以下の（１）〜（３）の性能評価指標のいずれか１以上、又はそれらの加重和を向上させるために、図２に示されるような機能構成を有する。
（１）時間無限大における受付成功率；
（２）時間無限大における、サービス要求あたり再配置実行回数；
（３）時間無限大における、サービス要求あたり要求トラヒック量の総和
但し、これらの性能評価指標を最大化又は最小化する問題は、一般にはＮＰ困難な整数計画問題であり、実時間における確定的な理論解の算出は困難である。そこで、本実施の形態では、物理経路の選出過程において、所定のコスト関数を定め、それを最小化するヒューリスティックなアプローチを採用することにより、実時間での実現を図る。
【００２５】
図２において、ネットワークリソース割当装置１０は、物理ネットワーク情報入力部１１、サービス要求入力部１２、受付可否判定部１３、要求トラヒック量総和算出部１４、最適経路決定部１５、及び再配置実行部１６を有する。これら各部は、ネットワークリソース割当装置１０にインストールされる１以上のプログラムが、ＣＰＵ１０４に実行させる処理により実現される。ネットワークリソース割当装置１０は、また、選出経路対記憶部１７を利用する。選出経路対記憶部１７は、例えば、補助記憶装置１０２、又はネットワークリソース割当装置１０にネットワークを介して接続可能な記憶装置等を用いて実現可能である。
【００２６】
物理ネットワーク情報入力部１１は、物理ネットワーク￥情報を入力する。物理ネットワーク情報は、物理ネットワークのトポロジや、物理ネットワークを構成する各リンクの帯域等を示す情報である。物理ネットワーク情報の入力は、予め行われる。サービス要求が到着するたびに、他の各部は、図３に示される手順で、各部の機能を実行する。
【００２７】
図３は、本発明の実施の形態におけるネットワークリソース割当装置が実行する処理手順の概要を説明するための図である。
【００２８】
サービス要求が到着すると、サービス要求入力部１２は、当該サービス要求を入力する（ステップＳ１）。サービス要求は、仮想ネットワークを利用したサービスの提供要求であり、当該仮想ネットワークを構成する各仮想経路の仮想ノード対（送信元ノード、あて先ノード）、当該仮想経路ごとの仮想ノード対で仮想ノード間に流れるトラヒック量（要求トラヒック量）、並びに各仮想経路に共通の到着時刻及び退去時刻等を含む。なお、サービス要求は、仮想ネットワークに対する物理経路の割当要求であるともいえる。
【００２９】
続いて、受付可否判定部１３は、サービス要求入力部１２によって入力されたサービス要求について、当該サービス要求に係る仮想ネットワークに対する物理経路の割り当ての可否及び再配置の要否を判定する（ステップＳ２）。なお、当該判定において、受付可否判定部１３は、要求トラヒック量総和算出部１４を利用して、サービス要求の要求トラヒック量の総和を算出し、当該算出結果と、物理ネットワークにおける他の仮想ネットワークの収容状況とに基づいて、物理経路の割り当ての可否及び再配置の要否を判定する。要求トラヒック量の総和は、通信事業者としてのメリットを定量的に表す指標としての意味を有する。
【００３０】
受付可否判定部１３によって、物理経路の割り当てが可能であり、かつ、再配置が不要であると判定された場合、最適経路対決定部５は、当該サービス要求に係る仮想ネットワークに最適な物理経路（最適経路）を選出する（ステップＳ３）。最適経路は、仮想ネットワークを構成する仮想経路ごとに選出される。
【００３１】
一方、受付可否判定部１３によって、物理経路の割り当てが不可能であり、再配置処理が必要であると判定された場合、再配置実行部１６が、既に収容されている仮想ネットワークについて、再配置を実行する（ステップＳ４）。
【００３２】
なお、選出経路対記憶部１７は、選出経路対の情報を記憶する。選出経路対とは、仮想経路ごとに選出された最適経路の対（集合）を示す情報いう。
【００３３】
続いて、以下の説明において用いられる記号の用法及び前提事項を、以下にまとめて説明する。
【００３４】
【数１】
0006466789.tif 000002
続いて、図３のステップＳ２及びＳ３の詳細について説明する。
【００３５】
ｊ番目のサービス要求が到着すると、受付可否判定部１３は、k-shortest path firstアルゴリズムにより、物理ネットワーク情報が示す物理ネットワーク上において、サービス要求に係る仮想ネットワークＶＮｊ含まれる仮想経路ごとに、当該仮想経路の送信元ノード及びあて先ノード間について、ｋ本の物理経路を抽出する。ここでｋの値は、計算時間に対する要件のもとで可能な限り大きい値が望ましい。なお、抽出されたｋ本の物理経路を、以下「候補経路集合」という。
【００３６】
続いて、受付可否判定部１３は、仮想ネットワークＶＮｊを構成する仮想経路ごとに、当該仮想経路に関して抽出された候補経路集合に含まれる各物理経路について、容量制約の確認を行う。具体的には、仮想経路ごとに、当該仮想経路に関して抽出された候補経路集合に含まれる各物理経路について、当該物理経路を構成する物理リンクの最小残余帯域が、当該仮想経路の要求トラヒック量以上であることを確認する。受付可否判定部１３は、或る仮想経路について、最小残余帯域が要求トラヒック量を下回る物理経路が有る場合、当該物理経路を、当該仮想経路の候補経路集合から除外する。
【００３７】
容量制約の確認の結果、ｋ本の物理経路の全ての割り当てが不可能である仮想経路が１以上有る場合、受付可否判定部１３は、再配置が必要であると判定する。
【００３８】
容量制約の確認においては再配置が必要でないと判定された場合、要求トラヒック量総和算出部１４は、仮想ネットワークＶＮｊの仮想経路ごとの要求トラヒック量の総和ｒｊを、以下により計算する。
【００３９】
【数２】
0006466789.tif 000003
ｒｊ＜ε１である場合、受付可否判定部１３は、以下の条件付き制約を課して、物理経路の割り当ての可否を判定する。なお、ε１は、任意に設定可能なパラメータである。
【００４０】
【数３】
0006466789.tif 000004
なお、数３のＩＦ文が、「条件」付き「制約」における「条件」に該当し、ＩＦ文の条件が満たされた場合に実行される｛｝内が、「条件」付き「制約」における「制約」に該当する。また、ＩＦ文において、ｃ２と比較されている値は、ｊ番目のサービス要求の到着時刻において収容されている仮想ネットワークＶＮのトラヒック量の総和の上位α％の値である（数１の（１５）参照）。また、ｃ３と比較されている値は、ｊ番目のサービス要求の到着時刻において退去し終わった仮想ネットワークＶＮ（過去の仮想ネットワークＶＮ）のうち、トラヒック量の総和がｓ以下である仮想ネットワークＶＮの平均滞在時間である（数１の（１２）参照）。また、ｃ４と比較されている値は、ｊ番目のサービス要求の到着時刻において退去し終わった仮想ネットワークＶＮのうち、トラヒック量の総和がＳ以上である仮想ネットワークＶＮの平均滞在時間である（数１の（１４）参照）。なお、ｃ２、ｃ３、ｃ４、α、ｓ、Ｓは、任意に設定可能なパラメータである。ｃ２には、小さな値が設定されることが想定されている。ｃ３には、大きな値が設定されることが想定されている。ｃ４には、小さな値が設定されることが想定されている。したがって、ＩＦ文が示す条件は、「ｊ番目のサービス要求の到着時において収容されている仮想ネットワークＶＮの多くは、要求トラヒック量の総和が比較的小さく、かつ、要求トラヒック量の総和が比較的小さい仮想ネットワークＶＮの滞在時間が長い傾向にある」ことを示す。
【００４１】
また、当該条件が付与される制約（ＩＦ文の｛｝内）において、任意に設定可能なパラメータｃ５と比較される値は、ｊ番目のサービス要求に係る仮想ネットワークＶＮｊを収容した後の無向グラフの局所辺連結度が零になってしまうノード対の数である。ここで、局所辺連結度が零になってしまうノード対とは、当該ノード対の間の辺の残余帯域が零になってしまうノード対を意味する。また、ｃ５には、小さい値が設定されることが想定されている。したがって、当該制約は、残余帯域が零になってしまうノード対の数がし所定値より少なくなること（ｃ５以下になること）である。
【００４２】
ｒｊ＜ε１である場合において、受付可否判定部１３が、上記の条件付き制約を勘案した上で、各仮想経路について、当該仮想経路に対する候補経路集合に含まれる物理経路のうちのいずれの物理経路の割り当てが可能であると判定した場合には、最適経路決定部１５は、各仮想経路について、当該仮想経路に対する候補経路集合から、以下に述べる数理計画問題を計算して、１つの最適経路を選出する。一方、ｒｊ≧ε１である場合、上記の制約は勘案されずに、最適経路決定部１５は、各仮想経路について、当該仮想経路に対する候補経路集合から、以下に述べる数理計画問題を計算して最適経路を選出する。ここで、数理計画問題の計算とは、例えば、以下の目的関数を解くことをいう。
【００４３】
【数４】
0006466789.tif 000005
また、＃は、＃に続く（）内の集合の要素数を意味する。そして、Ｅｃ（ｖ１，ｖ２；Ｇ（Ｖ，Ｅ，ｕｅ））は、ノード集合Ｖ、エッジ集合Ｅ、重みベクトルｕｅの重み付き無向グラフにおける、ノードｖ１、ｖ２間の局所辺連結度を示す（数１の（６）参照）。したがって、＃に続く（）内は、局所辺連結度が零になるノード対の集合を示す。すなわち、当該目的関数は、仮想ネットワークＶＮｊに物理経路を割当てた場合において、接続性を失う（残余帯域が零になってしまう）ノード対の数量を最小化することを目的としている。
【００４４】
このようにすることで、要求トラヒック量の総和が小さいにも係らず、主要なリンクを占有するサービス要求を排除し、より高効率に要求トラヒック量の総和が大きい仮想ネットワークの収容を可能にしていくことができる。なお、上記制約により、ｊ番目のサービス要求に係る仮想ネットワークＶＮｊに対する物理経路の割り当てが不可能である場合には、受付可否判定部１３は、再配置が必要であると判定する。以上の判断フローは、サービス要求到着時に以下の様な最適化問題を解くことに相当する。
【００４５】
【数５】
0006466789.tif 000006
なお、図４に、ステップＳ２及びＳ３の処理手順を詳細化した図を示す。
【００４６】
なお、上記目的関数の他に、仮想ネットワークＶＮｊの各仮想経路のホップ数の総和を最小化することを目的とする目的関数を解くことで、各仮想経路の最適経路が選出されてもよい。
【００４７】
続いて、図３のステップＳ４の詳細について説明する。
【００４８】
受付可否判定部１３によって、再配置が必要であると判定されると、再配置実行部１６は、所定のプロセスに基づき、既存の仮想ネットワークＶＮへの物理経路の割り当てを見直し、到着サービス要求に係る仮想ネットワークＶＮｊと併せて収容の可否を模索する。
【００４９】
仮想ネットワークＶＮｊに係るサービス要求が、時刻tj(0)に到着したとし、その時点で収容されている仮想ネットワークＶＮの数を、N(tj(0))とする。この時、再配置実行部１６は、収容されている仮想ネットワークＶＮの中からランダムに、
【００５０】
【数６】
0006466789.tif 000007
個の仮想ネットワークＶＮを抽出し、メモリ上で一時的にリソース解放を行う。メモリ上でのリソース解放とは、実際に物理ネットワークから仮想ネットワークＶＮを退去させるわけではないことを意味する。ここで、Ｍ２は、任意に設定可能なパラメータである。また、「∧」は、「∧」の両側の値のうち小さいほうの値が選択されることを示す。したがって、時刻tj(0)において収容されている仮想ネットワークＶＮの数がＭ２以下であれば、時刻tj(0)において収容されている全ての仮想ネットワークＶＮが抽出され、時刻tj(0)において収容されている仮想ネットワークＶＮの数がＭ２を超える場合には、時刻tj(0)において収容されている仮想ネットワークＶＮの中から、Ｍ２個の仮想ネットワークＶＮが、ランダムに抽出される。
【００５１】
続いて、再配置実行部１６は、到着サービス要求に係る仮想ネットワークＶＮｊと、一時的にリソース解放が行われた仮想ネットワークＶＮとを併せて、新たな仮想ネットワーク
【００５２】
【数７】
0006466789.tif 000008
を生成する。これは、一時的にリソース解放が行われた各仮想ネットワークＶＮの仮想経路ごとの要求トラヒック量、送信元ノード及びあて先ノードと、仮想ネットワークＶＮｊの各仮想経路の要求トラヒック量、送信元ノード及びあて先ノードとを合成又は統合することで、新たな仮想ネットワークが生成されることを示す。
【００５３】
この時、一時的なリソース解放後の残余帯域を表すベクトルC'e(tj(0))は、
【００５４】
【数８】
0006466789.tif 000009
と表すことができる。これを用いて、当該時点におけるグラフＧは、
【００５５】
【数９】
0006466789.tif 000010
と表せる。また以下では、
【００５６】
【数１０】
0006466789.tif 000011
ただし、
【００５７】
【数１１】
0006466789.tif 000012
とする。
【００５８】
この時、再配置実行部１６は、新たな仮想ネットワークを、以下のオフライン最適化問題を解くことにより、グラフG(V、E、C'e(tj(0))に埋め込むことを試みる。
【００５９】
【数１２】
0006466789.tif 000013
新たな仮想ネットワークを埋め込めた場合（新たな仮想ネットワークの各仮想経路に物理経路を割り当てることができた場合）、当該各仮想経路の最適経路対は決定される。
【００６０】
一方、新たな仮想ネットワークを埋め込めなかった場合、再配置実行部１６は、収容されている仮想ネットワークＶＮの中からのランダムな仮想ネットワークＶＮの抽出以降を繰り返す。Ｎ∞回繰り返しても、新たな仮想ネットワークを埋め込めなかった場合、到着サービス要求は、受け付け不可であると判定される。
【００６１】
なお、図５に、ステップＳ４の処理手順を詳細化した図を示す。
【００６２】
次に、本実施の形態のネットワークリソース割当装置１０に関する数値実験について述べる。ここでは、時間は無次元の実数で表すこととする。数値実験による評価に際しては、サービス要求の到着パターンについて複数のパターンを用意し、同一の物理ネットワーク上でそれぞれのサービス要求に対する仮想ネットワークの収容の模様をシミュレーションした結果に基づき比較を行う。
【００６３】
図６は、シミュレーションに利用された物理ネットワークを示す無向グラフの構成例を示す図である。図６に示される無向グラフは、ノードＶ１〜Ｖ１５の１５個のノードから構成される、接続率が０．１のランダムグラフの一標本である。接続率が０．１であるとは、各ノードからの接続確率が０．１であることをいう。
【００６４】
サービス要求に係る仮想ネットワークは、それぞれＭ本の仮想経路から構成される。ただし、Ｍは確率変数で、
Ｍ＝ｍａｘ｛１、ｘ｝，  ｘ∈Ｎ（３、２）
である。ｍａｘ｛１、ｘ｝は、１とｘとのうちの大きい方が選択されることを示す。ｘ∈Ｎ（３、２）は、ｘが、平均３、標準偏差２の正規分布に従うことを示す。
【００６５】
また、サービス要求の到着パターンは、平均λ＝１のＰｏｉｓｓｏｎ到着、平均滞在時間μ＝２０の指数分布に従うとする。すなわち、各サービス要求は到着後、所定時間経過後に退去する。各仮想経路の送信元ノード及びあて先ノードは、いずれも物理ノードの集合Ｖからランダムに非復元抽出され、３００個のサービス要求が到着するまでシミュレーションが実行される。
【００６６】
比較するアルゴリズムは、最短経路方式（以下、「既存方式」という。）と本実施の形態における方式（以下、「提案方式」という。）とする。既存方式は、サービス要求到着時に、リンク容量の制約のもとに各仮想経路に対して割り当てられる物理経路の経路長の総和をコストとする方式である。提案方式では、前記各パラメータ値を以下の通り設定して評価を行う。
【００６７】
【表１】
0006466789.tif 000014
ここで、パラメータＭ２の値は、時刻tj(0)において収容されている仮想ネットワークから２本の仮想ネットワークを抽出する場合の組み合わせの数を示す。
【００６８】
図７は、定常状態における既存方式と提案方式との比較結果を示す図である。定常状態とは、シミュレーションが開始されてから、サービス要求の到着と、仮想ネットワークの退去とが安定している状態をいう。
【００６９】
図７には、上述した３つの性能評価指標について、既存方式と提案方式との比較結果が示されている。なお、受付成功率は、便宜上、図７において、収容サービス数（収容できたサービス要求の数）に置き換えられている。受付成功率＝収容サービス数／サービス要求の到着であり、サービス要求の到着数は、既存方式と提案方式とで共通である。したがって、収容サービス数の比較は、実質的に、受付成功率の比較に相当する。
【００７０】
図７によれば、提案方式の方が、既存方式よりも累積要求トラヒック量の総和が大きく、かつ再配置実行回数が少量であることが分かる。
【００７１】
また、図８は、定常状態の時刻ｔ＝２５０における収容中の仮想ネットワークの要求トラヒック量の度数分布示す図である。図８によれば、提案方式において、要求トラヒック量が高い仮想ネットワークが、既存方式に比べて高い割合で収容されていることが確認できる。
【００７２】
同様の試験を、サービス要求パターンをランダムに１００サンプル生成して実施した結果を図９に示す。図９より、統計的に見ても、再配置実施回数と要求トラヒック量との観点で、提案方式が既存方式よりも優れていることが確認できる。
【００７３】
上述したように、本実施の形態によれば、ネットワーク仮想化の技術を生かして、より少量のオペレーション稼動で、より要求トラヒック量の総和大きいサービスを収容することができる。かつ、ネットワーク内を流れるトラヒック量（carried traffic）については、既存方式と同程度の量を実現することができる。すなわち、本実施の形態によれば、物理ネットワークに対してより効率的に多くの仮想ネットワークを収容可能とすることができる。
【００７４】
なお、本実施の形態において、ネットワークリソース割当装置１０は、物理経路割当装置の一例である。受付可否判定部１３は、判定部の一例である。最適経路対決定部５は、第１の選出部の一例である。再配置実行部１６は、第２の選出部の一例である。ε１は、第１の所定値の一例である。ｃ５は、第２の所定値の一例である。
【００７５】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００７６】
１０          ネットワークリソース割当装置
１１          物理ネットワーク情報入力部
１２          サービス要求入力部
１３          受付可否判定部
１４          要求トラヒック量総和算出部
１５          最適経路決定部
１６          再配置実行部
１７          選出経路対記憶部
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
Ｂ            バス
【図１】
0006466789.tif 000015
【図２】
0006466789.tif 000016
【図３】
0006466789.tif 000017
【図４】
0006466789.tif 000018
【図５】
0006466789.tif 000019
【図６】
0006466789.tif 000020
【図７】
0006466789.tif 000021
【図８】
0006466789.tif 000022
【図９】
0006466789.tif 000023