(57)【特許請求の範囲】
【請求項１】
物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムにおける前記設備提供者装置に備わる部分ネットワーク計算装置であって、
前記物理ネットワーク資源を構成する物理ノード及び物理リンクの中から、前記ユーザ装置より要求された仮想ネットワークの仮想部分領域を割り当てることのできる前記物理ネットワーク資源の物理ノード及び物理リンクを有する物理部分領域を、前記仮想ネットワークの各仮想ノードを起点仮想ノードとして検索し、前記仮想部分領域を割り当てることができる前記物理部分領域を列挙する部分ネットワーク列挙部と、
前記部分ネットワーク列挙部の列挙した前記物理部分領域のうち、共通する物理ノード又は物理リンクを有する前記物理部分領域を比較し、前記仮想部分領域の仮想ノード及び仮想リンクを最も多く割当てられる前記物理部分領域を、前記仮想部分領域を割当てるための物理部分領域として抽出する部分ネットワーク抽出部と
を備える部分ネットワーク計算装置。
【請求項２】
物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当における部分ネットワーク計算方法であって、
前記物理ネットワーク資源を構成する物理ノード及び物理リンクの中から、前記ユーザ装置より要求された仮想ネットワークの仮想部分領域を割り当てることのできる前記物理ネットワーク資源の物理ノード及び物理リンクを有する物理部分領域を、前記仮想ネットワークの各仮想ノードを起点仮想ノードとして検索し、前記仮想部分領域を割り当てることができる前記物理部分領域を列挙する部分ネットワーク列挙手順と、
前記部分ネットワーク列挙手順で列挙した前記物理部分領域のうち、共通する物理ノード又は物理リンクを有する前記物理部分領域を比較し、前記仮想部分領域の仮想ノード及び仮想リンクを最も多く割当てられる前記物理部分領域を、前記仮想部分領域を割当てるための物理部分領域として抽出する部分ネットワーク抽出手順と
を有する部分ネットワーク計算方法。
【請求項３】
コンピュータを、請求項１に記載の部分ネットワーク計算装置が備える前記部分ネットワーク列挙部及び前記部分ネットワーク抽出部として機能させるための部分ネットワーク計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部分ネットワーク計算装置、部分ネットワーク計算方法及び部分ネットワーク計算プログラムに関する。
【０００２】
また、本発明は複数の設備提供者がユーザの資源利用要求に対してその要求を満たす資源割当を情報秘匿のまま発見する方法に関する。ここで、設備提供者とはネットワーク資源やＩＣＴ資源を保有し、それらをユーザに提供するインターネットサービスプロバイダー（ＩＳＰ）などのことである。また、資源割当とは設備提供者がユーザからの仮想ネットワークなどの資源利用要求に応じて、保有する設備の中からどのネットワーク機器・ＩＣＴ機器を使用し、それらをどのように接続するかを決定することである。また、情報秘匿のまま発見するとは、各設備提供者が設備情報等を互いに開示することなく資源割当を発見することである。
【背景技術】
【０００３】
非特許文献１及び２には、本発明に関連する資源割当が開示されている。非特許文献１及び２の手法は、すべての設備提供者が保有設備の割当コスト（文献中では  ｎｏｄｅ  ｃｏｓｔ  や  ｌｉｎｋ  ｃｏｓｔ）を公開し、その情報を用いて資源割当てを行う。しかし、割当コストは競争力に直結する重要な情報であるため、設備提供者が公開することは難しい。そのため、非特許文献１及び２の手法は、現実性に課題がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｉｎｅｓ  Ｈｏｕｉｄｉ，  Ｗａｊｄｉ  Ｌｏｕａｔｉ，  Ｗａｌｉｄ  Ｂｅｎ  Ａｍｅｕｒ  ａｎｄ  Ｄｊａｍａｌ  Ｚｅｇｈｌａｃｈｅ，  “Ｖｉｒｔｕａｌ  ｎｅｔｗｏｒｋ  ｐｒｏｖｉｓｉｏｎｉｎｇ  ａｃｒｏｓｓ  ｍｕｌｔｉｐｌｅ  ｓｕｂｓｔｒａｔｅ  ｎｅｔｗｏｒｋｓ，”  Ｃｏｍｐｕｔｅｒ  Ｎｅｔｗｏｒｋｓ，  ｖｏｌ．５５，  ｎｏ．４，  ｐｐ．１０１１−１０２３，  ２０１１．
【非特許文献２】Ｓａｍｕｅｌ，  Ｆａｄｙ，  Ｃｈｏｗｄｈｕｒｙ，  Ｍｏｓｈａｒａｆ  ａｎｄ  Ｂｏｕｔａｂａ，  Ｒａｏｕｆ，  “ＰｏｌｙＶｉＮＥ：  ｐｏｌｉｃｙ−ｂａｓｅｄ  ｖｉｒｔｕａｌ  ｎｅｔｗｏｒｋ  ｅｍｂｅｄｄｉｎｇ  ａｃｒｏｓｓ  ｍｕｌｔｉｐｌｅ  ｄｏｍａｉｎｓ，”  Ｊｏｕｒｎａｌ  ｏｆ  Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，  ｖｏｌ．４，  ｎｏ．１，  ｐｐ．１−２３，  ２０１３．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
我々は、各設備提供者が割当可能な仮想ネットワークの部分領域について、割当コストを伏せたまま「順位」だけを明らかにし、順位の良い部分領域を組合せて仮想ネットワークを実現するネットワーク資源割当方法を提案した。このネットワーク資源割当方法の発明を適用するには以下の２つが課題となる。第１の課題は、各設備提供者が割当可能な部分領域を列挙することである。第２の課題は、不要な部分領域を削除することである。
【０００６】
第１の課題に関し、非特許文献１及び２の資源割当手法は、資源利用要求に対して、その要求を満たす資源割当を唯１つ発見する方法である。そのため、非特許文献１及び２の手法を用いて複数の部分領域を列挙することは困難である。また、一般に資源割当手法はＮＰ（Ｎｏｎ−ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｐｏｌｙｎｏｍｉａｌ）困難に分類される問題であるから、その列挙方法も自明ではない。
【０００７】
第２の課題に関し、ネットワーク資源割当方法は、各設備提供者が列挙した部分領域を組合せて最適な仮想ネットワークを実現するに際し、取り扱う部分領域の数が増えると計算に必要な時間が増加する可能性がある。一方で、部分領域のパターンの数は、一般に、資源利用要求のサイズに対して指数関数的に増加する。そこで、各設備提供者が膨大な数の部分領域を列挙しないような対策が必要となる。
【０００８】
そこで、本発明は、設備提供者が割当可能な部分領域のうち、複数の部分領域を短時間で列挙し、必要な部分領域の組合せを抽出する際の計算時間を削減することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本願発明の部分ネットワーク計算装置は、ユーザ装置から要求された仮想ネットワークが有する各仮想ノードを起点として、現在の仮想部分領域を物理部分領域に割当可能かどうかを判定し、仮想部分領域を割当てることができる複数の物理部分領域を列挙する。また、列挙した複数の物理部分領域を比較し、最も多くの仮想部分領域を割当てることのできる物理部分領域を抽出する。
【００１０】
具体的には、本願発明に係る部分ネットワーク計算装置は、物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムにおける前記設備提供者装置に備わる部分ネットワーク計算装置であって、前記物理ネットワーク資源を構成する物理ノード及び物理リンクの中から、前記ユーザ装置より要求された仮想ネットワークの仮想部分領域を割り当てることのできる前記物理ネットワーク資源の物理ノード及び物理リンクを有する物理部分領域を、前記仮想ネットワークの各仮想ノードを起点仮想ノードとして検索し、前記仮想部分領域を割り当てることができる前記物理部分領域を列挙する部分ネットワーク列挙部を、備える。
【００１１】
本願発明に係る部分ネットワーク計算装置は、部分ネットワーク列挙部を備えるため、ユーザ装置から要求された仮想ネットワークが有する各仮想ノードを起点として物理ネットワーク資源を検索し、仮想部分領域を割当てることのできる物理部分領域を列挙することができる。
【００１２】
本発明に係る部分ネットワーク計算装置は、前記部分ネットワーク列挙部の列挙した前記物理部分領域のうち、共通する物理ノード又は物理リンクを有する前記物理部分領域を比較し、前記仮想部分領域の仮想ノード及び仮想リンクを最も多く割当てられる前記物理部分領域を、前記仮想部分領域を割当てるための物理部分領域として抽出する部分ネットワーク抽出部を、さらに備えてもよい。
【００１３】
具体的には、本願発明に係る部分ネットワーク計算方法は、物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当における部分ネットワーク計算方法であって、前記物理ネットワーク資源を構成する物理ノード及び物理リンクの中から、前記ユーザ装置より要求された仮想ネットワークの仮想部分領域を割り当てることのできる前記物理ネットワーク資源の物理ノード及び物理リンクを有する物理部分領域を、前記仮想ネットワークの各仮想ノードを起点仮想ノードとして検索し、前記仮想部分領域を割り当てることができる前記物理部分領域を列挙する部分ネットワーク列挙手順を有する。
【００１４】
本発明に係る部分ネットワーク計算方法は、前記部分ネットワーク列挙手順で列挙した前記物理部分領域のうち、共通する物理ノード又は物理リンクを有する前記物理部分領域を比較し、前記仮想部分領域の仮想ノード及び仮想リンクを最も多く割当てられる前記物理部分領域を、前記仮想部分領域を割当てるための物理部分領域として抽出する部分ネットワーク抽出手順を、前記部分ネットワーク列挙手順の後にさらに有してもよい。
【００１５】
本発明に係る部分ネットワーク計算プログラムは、コンピュータを、本発明に係る部分ネットワーク計算装置が備える前記部分ネットワーク列挙部及び前記部分ネットワーク抽出部として機能させるための部分ネットワーク計算プログラムである。
【００１６】
なお、上記各発明は、可能な限り組み合わせることができる。
【発明の効果】
【００１７】
本発明によれば、設備提供者が割当可能な部分領域のうち、複数の部分領域を短時間で列挙し、必要な部分領域の組合せを抽出する際の計算時間を削減することができる。
【００１８】
複数の設備提供者にまたがるＶＮ（Ｖｉｒｔｕａｌ  Ｎｅｔｗｏｒｋ）の構成法として、ネットワーク資源割当方法があるが、まず各設備提供者が割当可能な部分領域を列挙する必要があった。また、多くの部分ネットワークが列挙されると最適化に必要な時間が増大するという性質があり、列挙される部分ネットワークの数は最悪の場合、非常に多くなる可能性（要求仮想ネットワークのサイズに対して指数個となる可能）があるという課題があった。本発明の列挙法では、各仮想ノードを起点として、割当を実行することで複数の部分ネットワークの列挙を可能にしている。また、割当の各ステップで現時点の割当が提供可能か判定を行うことができることも、複数の部分ネットワークの列挙を可能にしている。さらに、単純な貪欲法を用いているため、短時間で複数の部分ネットワークを列挙することができ、ネットワーク資源割当方法のボトルネックとなることはない。
【００１９】
本発明の部分ネットワーク削減法では、後処理であるネットワーク資源割当方法が値そのものではなく、その順序と部分ネットワークの領域のみを用いて組合せを探索すること利用して、パレート最適な部分ネットワークのみを抽出する。これにより、後処理であるネットワーク資源割当方法で扱う部分ネットワークの数が減るため、計算時間を削減することできる。
【００２０】
複数の設備提供者がユーザの仮想ネットワーク等の資源利用要求に対してその要求を満たすコストの小さい資源割当を発見する手法としてネットワーク資源割当方法がある。この手法の前提条件として、各設備提供者が割当可能な部分領域を列挙すること、また、計算時間を削減するため、不要な部分領域を削除する必要があった。そこで、本発明では、各仮想ノードを起点とし割当を実行し、仮想ノードを処理する度に現在の部分領域が割当可能かどうか判定する。これにより、複数の部分領域を列挙することができる。また、ネットワーク資源割当方法が、順位と部分領域の広さのみを用いて組合せを選択することに注目して、パレート最適な部分領域のみを抽出し、列挙された部分領域を削除する。これにより、部分領域の組合せを計算する際の計算時間を削減することができる。
【図面の簡単な説明】
【００２１】
【図１】本実施形態に係るネットワーク資源割当システムの一例を示す。
【図２】ユーザ装置から要求された仮想ネットワークの一例を示す。
【図３】複数の設備提供者装置が管理する物理ネットワーク資源の一例を示す。
【図４】仮想部分領域の第１例を示す。
【図５】仮想部分領域の第２例を示す。
【図６】仮想部分領域の第３例を示す。
【図７】仮想部分領域の第４例を示す。
【図８】仮想部分領域の第５例を示す。
【図９】仮想部分領域の第１例の物理ネットワーク資源への割当て例を示す。
【図１０】仮想部分領域の第２例の物理ネットワーク資源への割当て例を示す。
【図１１】仮想部分領域の第３例の物理ネットワーク資源への割当て例を示す。
【図１２】仮想部分領域の第４例の物理ネットワーク資源への割当て例を示す。
【図１３】本実施形態に係る設備提供者装置の一例を示す。
【図１４】本実施形態に係る部分ネットワーク列挙部の一例を示す。
【図１５】本実施形態に係る部分ネットワーク抽出部の一例を示す。
【図１６】部分ネットワーク列挙手順の一例を示す。
【図１７】本実施形態に係る部分ネットワーク計算方法を用いて、列挙した物理部分領域から抽出する仮想ネットワークの割当てに用いる物理部分領域の特性の一例を示す。
【図１８】部分ネットワーク抽出手順の一例を示す。
【図１９】本実施形態に係る部分ネットワーク計算方法を用いた場合の仮想ネットワークの物理ネットワーク資源への割当例を示す。
【図２０】部分ネットワーク列挙手順で割当てられる仮想ノード及び仮想リンクの一例を示す。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について、図面を参照しながら詳細に説明する。なお、本発明は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本発明は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２３】
図１に、本実施形態に係るネットワーク資源割当システムの構成例を示す。本実施形態に係るネットワーク資源割当システムは、設備提供者装置３０と、ユーザ装置６０と、ネットワーク７０とを備える。各設備提供者装置３０およびユーザ装置６０は、ネットワーク７０を介して接続されており、お互いに通信可能である。ユーザ装置６０は、設備提供者装置３０に対し、仮想ネットワークの割当要求を行う。設備提供者装置３０は、ユーザ装置６０の仮想ネットワークの割当要求に対して、仮想ネットワークを割り当てるための物理部分領域の提示を行う。
【００２４】
・仮想ネットワーク割当問題における割当可能な部分ネットワーク列挙問題
図２に示すような仮想ネットワークＮ０の仮想ネットワーク利用要求がユーザからあり、複数設備提供者が図３に示すような物理ネットワーク資源を保有している場合を想定する。図３では、図１に示す設備提供者装置３０（ＩＰ１）が図３に示すＩＰ１で囲まれた物理ネットワーク資源を保有し、図１に示す設備提供者装置３０（ＩＰ２）が図３に示すＩＰ２で囲まれた物理ネットワーク資源を保有し、図１に示す設備提供者装置３０（ＩＰ３）が図３に示すＩＰ３で囲まれた物理ネットワーク資源を保有し、図１に示す設備提供者装置３０（ＩＰ４）が図３に示すＩＰ４で囲まれた物理ネットワーク資源を保有する。
【００２５】
物理ネットワーク資源は、物理部分領域を備える。物理部分領域は、少なくとも１つの物理ノード又は物理リンクを備える。仮想ネットワークは、仮想部分領域を備える。仮想部分領域は、少なくとも１つの仮想ノード又は仮想リンクを備える。ここで、図２に示す仮想ネットワークＮ０は、仮想ノード１１、１２、１３及び１４と、仮想ノード間を接続する仮想リンクとを備える。
【００２６】
仮想リンクのそれぞれには、要求容量（ＣＰＵクロック数や通信帯域）が与えられる。仮想リンクの容量は、図２のように、仮想リンクの横に表記する。また、仮想ノードには要求タイプが与えられる。ここで、仮想ノードの要求タイプは、例えば、ノードが設置されている地域（アジア、アメリカ、ヨーロッパ、オーストラリアなど）やノードがもつ機能（汎用計算機、ストレージ、ファイアウォール、侵入検知システム、認証システムなど）の組合せである（アメリカに設置されたファイアウォール等）。ユーザが要求する仮想ノードの要求タイプを図示する際には、ノードの形状で表現する。図２では、仮想ノードの形状は○、△、□及び☆の４種類である。仮想ノードも、仮想リンクと同じように容量を有する（不図示）。
【００２７】
物理ネットワーク資源の物理部分領域は物理ノードと物理リンクで構成され、それぞれに空き容量と割当コストがある。ここで、設備提供者装置３０が管理するストレージサーバーや計算サーバーのようなネットワーク機器を物理ノードと呼び、それら物理ノードを結ぶ回線等を物理リンクと呼ぶ。物理ノードは、計算サーバー等の種別によって分類されるが、計算サーバー等が有する機能や、計算サーバー等が実行するプログラムによって分類されてもよい。
【００２８】
図３の物理ネットワーク資源ＩＰ１〜ＩＰ４は、物理ノード２１ａ、２１ｂ、２１ｃ、２１ｄ、２２ａ、２２ｂ、２３ａ、２３ｂ、２４ａと、物理ノード間を接続する物理リンクを備える。また、物理ノードは提供タイプをもつ。ここで、物理ノードの提供タイプは、例えば、ノードが設置されている地域（アジア、アメリカ、ヨーロッパ、オーストラリアなど）やノードがもつ機能（汎用計算機、ストレージ、ファイアウォール、侵入検知システム、認証システムなど）の組合せである（アメリカに設置されたファイアウォール等）。図３では、提供タイプを物理ノードの形状を○、△、□及び☆の４種類の形状で表現した。物理ノードの提供タイプ（○、△、□及び☆の形状）は、仮想ノードの要求タイプ（○、△、□及び☆の形状）と対応する。物理ノードも物理リンクと同じように容量を有する（不図示）。物理部分領域は、例えば、物理ノード２１ａ、物理ノード２１ｂ、物理ノード２１ａ及び物理ノード２１ｂを結ぶ物理リンクによって構成される。
【００２９】
物理ネットワーク資源ＩＰ１〜ＩＰ４は複数の設備提供者装置３０が提供する物理ノード及び物理リンクによって構成され、各ノードやリンクの情報はそれぞれの設備提供者装置３０しか知り得ない。ただし、設備提供者装置３０間を接続するリンクについては、両端となるふたつの設備提供者装置３０が情報を共有する。
【００３０】
仮想ネットワーク割当問題とは、仮想ノードとリンクを、それらの要求容量、タイプを満たす物理ノードとリンクにそれぞれ割当てることである。一つの仮想ノードは一つの物理ノードに割当てられる。仮想リンクは物理リンクから構成されるパスに割当てられる。物理リンクは、物理リンクの空き容量に応じて、複数の仮想リンクを割り当てることができる。また、物理ノードも、物理ノードの空き容量に応じて複数の仮想ノードを割当てることができる。
【００３１】
仮想ネットワークの割当てに要するコストとは、割当に用いたすべての物理ノードと物理リンクの合計コストである。コストは、ユーザに提供するために必要な価格である。この合計コストを最小にする割当を見つける。図４は、図２の仮想ネットワークが要求された場合に、割当可能な仮想ネットワークの仮想部分領域の例である。また、図９は、図４の割当可能な仮想部分領域の物理ネットワーク資源への割当例であり、太い破線で示した部分が物理ネットワーク資源に割当てられた仮想部分領域である。図４の仮想ノード１１は、図９の物理ノード２１ａに割当てられる。また、図４の仮想ノード１２は、図９の物理ノード２１ｂに割当てられる。図４の仮想ノード１１と仮想ノード１２の間の仮想リンクは、図９の物理ノード２１ａと物理ノード２１ｂの間の物理リンクに割当てられる。図４で仮想ノード１１のみに繋がる仮想リンクは、物理ノード２１ａと物理ノード２３ａの間の物理リンクに割当てられる。図４で仮想ノード１２のみに繋がる仮想リンクは、物理ノード２１ｂと物理ノード２４ａの間の物理ノードに割当てられる。この場合、割当可能な部分物理領域は、物理ノード２１ａ、物理ノード２１ｂ、物理ノード２１ａと物理ノード２１ｂの間の物理リンク、物理ノード２１ａと物理ノード２３ａの間の物理リンク、物理ノード２１ｂと物理ノード２４ａの間の物理ノードによって構成される。
【００３２】
図５及び図６は、図２の仮想ネットワークＮ０が要求された場合に、物理ネットワーク資源に割当て可能な仮想部分領域の例である。また、図１０は、図５及び図６の割当可能な仮想部分領域の物理ネットワーク資源への割当例である。図１０では、物理ネットワーク資源に割当てられた仮想部分領域を太い破線で示した。図５の仮想ノード１２は、物理ノード２１ｂに割当られる。また、仮想ノード１２に繋がる仮想リンクは、物理ノード２１ｂと物理ノード２４ａの間の物理リンクに割当てられる。図６の仮想ノード１４は、物理ノード２１ｄに割当てられる。また、仮想ノード１４に繋がる仮想リンクは、物理ノード２１ｄと物理ノード２２ａの間の物理リンクに割当てられる。この場合、割当可能な部分物理領域は、物理ノード２１ｂ、物理ノード２１ｂと物理ノード２４ａの間の物理リンク、物理ノード２１ｄ、物理ノード２１ｄと物理ノード２２ａの間の物理リンクによって構成される。
【００３３】
図７は、図２の仮想ネットワークが要求された場合に、物理ネットワーク資源に割当て可能な仮想部分領域の例である。図１１は、図７の割当可能な物理部分領域の物理ネットワーク資源への割当例である。図１１でも、物理ネットワーク資源に割当てられた仮想ネットワークを太い破線で示した。図７の仮想ノード１１は物理ノード２１ａに割当てられる。図７の仮想ノード１１に繋がる要求容量１０の仮想リンクは、物理ノード２１ａと物理ノード２３ａの間の物理リンクに割当てられる。図７の仮想ノード１１に繋がる要求容量５の仮想リンクは、物理ノード２１ａと物理ノード２１ｂの間の物理リンク及び物理ノード２１ｂと物理ノード２４ａの間の物理リンクに割当てられる。図１１に示すように、仮想リンクの物理リンクへの割当てにおいては、物理ノードを通過するように物理リンクを割り当ててもよい。この場合、割当可能な部分物領域は、物理ノード２１ａ、物理ノード２１ａと物理ノード２３ａの間の物理リンク、物理ノード２１ａと物理ノード２１ｂの間の物理リンク及び物理ノード２１ｂと物理ノード２４ａの間の物理リンクによって構成される。
【００３４】
図８は、図２の仮想ネットワークが要求された場合に、割当不可能な仮想部分領域の例である。図８の仮想ノード１１は、図１２の物理リンク２１ａに割当てられる。図８の仮想ノード１１にのみ繋がる要求容量５の仮想リンクは、物理ノード２１ａと物理ノード２１ｂの間の物理リンク及び物理ノード２１ｂと物理ノード２４ａの間の物理リンクに割当てられる。仮想ノード１１と仮想ノード１３の間の仮想リンクは、物理ノード２１ａと物理ノード２３ａの間の物理リンクに割当てられる。しかし、仮想ノード１３にのみ繋がる要求容量５及び要求容量１０の仮想リンクを、図１２の物理リンクに割当てることはできない。割当てることができない仮想リンクを図１２に一点波線で示す。この場合、割当可能な物理部分領域はない。
【００３５】
ある設備提供者装置３０における、仮想ネットワーク割当問題における割当可能な部分ネットワーク列挙問題とは、仮想ネットワークを割当可能なその設備提供者装置３０が有する物理部分領域を列挙することである。ここで、ある設備提供者装置３０での割当可能な物理部分領域とは、いくつかの仮想ノードとそれに接続する仮想リンクを備える仮想部分領域に対して、それらの要求容量、タイプを満たすように物理ノードとリンクにそれぞれ割当てることのできる物理部分領域である。
【００３６】
図１３に、本実施形態に係る設備提供者装置３０を示す。設備提供者装置３０は、本実施形態に係る部分ネットワーク計算方法を実行する部分ネットワーク計算装置として機能する。本実施形態に係る部分ネットワーク計算方法は、部分ネットワーク列挙手順と、部分ネットワーク抽出手順と、を順に有する。部分ネットワーク計算装置は、部分ネットワーク列挙部５０と、部分ネットワーク抽出部４０とを備える。
【００３７】
部分ネットワーク列挙手順では、部分ネットワーク列挙部５０が、物理ネットワーク資源を構成する物理ノード及び物理リンクの中から、ユーザ装置６０より要求された仮想ネットワークの仮想部分領域を割り当てることのできる物理ネットワーク資源の物理ノード及び物理リンクを有する物理部分領域を、仮想ネットワークの各仮想ノードを起点仮想ノードとして検索し、仮想部分領域を割り当てることができる物理部分領域を列挙する
【００３８】
・部分ネットワークの列挙
部分ネットワーク列挙部５０は、次のような順々に貪欲に仮想ノードを割当てる方法で、ユーザ装置より要求された仮想ネットワークの仮想部分領域を割当可能な物理ネットワーク資源を構成する物理部分領域の物理ノード及び物理リンクを列挙する。この際、仮想部分領域の各仮想ノードを起点として割当を開始することで複数の物理部分領域の物理ノード及び物理リンクを列挙する。また、各ステップで仮想ノード及び仮想リンクを処理する度に現在の仮想ノード及び仮想リンクが割当可能か判定することで複数の物理ノード及び物理リンクを列挙することができる。
【００３９】
本実施形態では、まず設備提供者装置３０は各物理ノード、仮想ノードの処理の順序Ａを決める。この順番は任意であるが、物理ノードであれば、例えば、ランダム、空き容量の順、コストの順、接続しているリンクの数の順、接続しているリンクの空き容量の合計の値の順、ノードの空き容量と接続しているリンクの空き容量の合計値の順、ノードの空き容量と接続しているリンクの空き容量から計算される値の順など考えられる。上記以外のものでも物理ノードを順番づけられるものなら良い。仮想ノードについても同様である。
【００４０】
図１６は割当列挙の概要図である。図１６に示した割当可能な部分ネットワークを列挙する処理である部分ネットワーク列挙手順を実行する部分ネットワーク列挙部５０の装置構成図を図１４に示す。部分ネットワーク列挙部５０は、部分ネットワーク列挙回路５１と、部分ネットワーク列挙制御回路５２と、部分ネットワーク記憶回路５３とを有する。
【００４１】
部分ネットワーク列挙回路５１では仮想ノード、リンクの割当可能判定や（図１６のＳ８−４，Ｓ８−６）、仮想ノード、リンクの割当を行う（図１６のＳ８−７〜Ｓ８−９）。部分ネットワーク列挙制御回路５２は、どの仮想ノードを割当てるかの決定（図１６のＳ８−１，Ｓ８−２，Ｓ８−４〜Ｓ８−１２）や割当の初期化（図１６のＳ８−３）の他、Ｓ８−１〜Ｓ８−１３間の遷移を制御する。部分ネットワーク記憶回路５３では現在の割当状態の記憶や、割当可能な部分ネットワークの記憶を行う（図１６のＳ８−８，Ｓ８−１１）。
【００４２】
具体的には、部分ネットワーク列挙手順は、ユーザ装置６０から設備提供者装置３０に仮想ネットワークの割当要求があると、部分ネットワーク列挙制御回路５２によって、Ｓ８−１で開始される。部分ネットワーク列挙制御回路５２は、起点となっていない仮想ノードを１つ選び、その仮想ノードを起点仮想ノードｖｖ０として処理を行う（Ｓ８−２）。起点仮想ノードｖｖ０は順序Ａに従って決める。部分ネットワーク列挙制御回路５２は、まず、仮想ネットワークの割当て状態のうち、処理を行う設備提供者装置３０における物理ネットワーク資源への割当状態を初期化する（Ｓ８−３）。なお、処理を行う設備提供者装置３０が提供する物理ネットワーク資源の範囲は、任意である。具体的には、１つの設備提供者装置３０が提供する物理ネットワーク資源に限らず、任意の設備提供者装置３０が提供する物理ネットワーク資源の範囲で処理を行ってもよい。
【００４３】
次に、部分ネットワーク列挙回路５１は、起点仮想ノードｖｖ０を割り当てた仮想ノードを割当てられる物理ノードを順序Ａで調べていき、初めて要求を満たす物理ノードにｖｒ０を割当てる（Ｓ８−４）。Ｓ８−４で要求を満たす物理ノードが存在しない場合は、Ｓ８−１１に移行した後、Ｓ８−１３に移行して処理を終了する。
【００４４】
Ｓ８−４において、部分ネットワーク列挙回路５１が要求を満たす物理ノードが存在すると判定する場合にはｖｒ０を割り当てた後、Ｓ８−５に移行する。Ｓ８−５では、部分ネットワーク列挙回路５１は、未処理の仮想ノードが存在するかを判定する。未処理の仮想ノードが存在しない場合には、Ｓ８−１１に移行する。Ｓ８−５で未処理の仮想ノードが存在する場合には、Ｓ８−６に移行する。
【００４５】
Ｓ８−６では、部分ネットワーク列挙回路５１は、順序Ａに従い割当済仮想ノードに接続する未処理の仮想ノードｖｖ１を選択する。Ｓ８−６において、部分ネットワーク列挙回路５１が未処理の仮想ノードが選択できた場合は、Ｓ８−７に移行する。Ｓ８−６で部分ネットワーク列挙回路５１が選択できる未処理の仮想ノードが存在しない場合は、Ｓ８−８に移行する。
【００４６】
Ｓ８−７において、部分ネットワーク列挙回路５１は、順序Ａに従いｖｖ１とそれに接続する内側向き仮想リンク（図４で仮想ノード１１を起点仮想ノードｖｖ０、仮想ノード１２をｖｖ１とした場合の仮想ノード１１と仮想ノード１２とを接続する仮想リンクに相当）が割当できる物理ノードを選択する。ここで内側向き仮想リンクとはｖｖ１と割当済仮想ノードとの間の仮想リンクのことである。内側向きでない仮想リンクを外側に接続している仮想リンクと呼ぶ。
【００４７】
Ｓ８−７で、部分ネットワーク列挙回路５１が内側向き仮想リンクを割当可能な場合、Ｓ８−８に移行する。Ｓ８−８では、部分ネットワーク列挙回路５１は、現時点で外側に接続している仮想リンク（図４で仮想ノード１１をｖｖ０、仮想ノード１２をｖｖ１とした場合の内側向き仮想リンクではない仮想ノード１１から外側に出るリンク及び仮想ノード１２から外側に出るリンクに相当）が割当可能か判定する。Ｓ８−８で外向き仮想リンクが割当可能な場合、現在の部分仮想ネットワークを提供可能として出力し（Ｓ８−８）、Ｓ８−１０に移行する。Ｓ８−８で外向き仮想リンクが割当不能な場合は何も出力せずにＳ８−１０に移行する。
【００４８】
Ｓ８−７で、部分ネットワーク列挙回路５１が内側向き仮想リンクを割当不可能である場合、Ｓ８−９に移行する。Ｓ８−９では、部分ネットワーク列挙回路５１がＳ８−７で内側向き仮想リンクが割当てられるかを判断したｖｖ１に繋がるリンクが外側に接続している仮想リンクとして割当てられるかを判定する。割当てられる場合は、当該仮想リンクを外側に接続される仮想リンクとして設定し、Ｓ８−１０に移行する。割当てられない場合は、そのままＳ８−１０に移行する。
【００４９】
また、Ｓ８−９では、ｖｖ１が現在処理を行っている設備提供者装置３０が提供する物理ネットワーク資源内に割当不能な場合は（Ｓ８−７で失敗）、割当済仮想ノードとｖ１の間の仮想リンクが、現在処理を行っている設備提供者装置３０が提供する物理ネットワーク資源の外側であって、他の設備提供者装置３０が有する物理ネットワーク資源の物理ノードとの間の物理リンクに割当可能か判定する（Ｓ８−９）。
【００５０】
Ｓ８−９で、仮想リンクが他の設備提供者装置３０が有する物理ネットワーク資源の物理ノードとの間の物理リンクに割当可能な場合、仮想リンクを当該物理リンクに割当て、未処理の仮想ノードが存在する間、処理を繰り返す（Ｓ８−１０）。Ｓ８−９で、仮想リンクが他の設備提供者装置３０が有する物理ネットワーク資源の物理ノードとの間の物理リンクに割当不可能な場合、Ｓ８−１２に移行する。全ての仮想ノードについて処理が終わるとＳ８−２で割当てた起点仮想ノードｖｖ０を起点とする処理を終了する。これらのＳ８−１〜Ｓ８−１２の処理を、順序Ａに従って全ての仮想ノードについて行う。Ｓ８−１２では、全ての仮想ノードを仮想起点ノードｖｖ０として処理を行ったかを判定し、全ての仮想ノードについて処理を行っていれば、Ｓ８−１３に移行して処理を終了する。また、Ｓ８−１２で、全ての仮想ノードを仮想起点ノードｖｖ０として処理を行っていないと判定されれば、Ｓ８−２に移行して処理を繰り返す。これらの処理により、起点仮想ノードｖｖ０と起点仮想ノードｖｖ０を割当てることができる物理ノードｖｒ０及び仮想ノードｖｖ１と仮想ノードｖｖ１を割当てることができる物理ノード物理ノードｖｒ１を列挙する。
【００５１】
以上説明したＳ８−１〜Ｓ８−１３の処理を用いて、図２の仮想ネットワークを図３の物理ネットワーク資源に割当てる場合について説明する。ここでは、順序Ａを、仮想ノードについては仮想ノード１１→仮想ノード１２→仮想ノード１３→仮想ノード１４（図２）、物理ノードについては物理ノード２１ａ→物理ノード２１ｂ→物理ノード２１ｃ→物理ノード２１ｄ（図３）とする。まずＳ８−２で仮想ノード１１が起点と設定される。仮想ノード１１の要求を満たす物理ノードのうち物理ノード２１ａが順序Ａに従い選ばれ、仮想ノード１１が物理ノード２１ａに割当てられる（Ｓ８−４）。割当済仮想ノード１１に接続する仮想ノード１２、１３のうち、順序Ａに従い１２が発見される（Ｓ８−６）。仮想ノード１２が物理ノード２１ｂに割当てられる（Ｓ８−７）。２つの外向き仮想リンク（１１，１３）と（１２，１３）は外側に割当て可能（図９）なので、部分仮想ネットワーク｛１１，１２｝が出力される（Ｓ８−８）。ここで、仮想リンク（１１，１３）とは、仮想ノード１１及び仮想ノード１３の間の仮想リンクであり、仮想リンク（１２，１３）とは、仮想ノード１２及び仮想ノード１３の間の仮想リンクである。また、部分仮想ネットワーク｛１１，１２｝とは、仮想ノード１１、仮想ノード１２及び仮想ノード１２及び仮想ノード１３の間の仮想リンクを有する部分仮想ネットワークである。割当済仮想ノード１１、１２に接続する仮想ノード１３が発見される（Ｓ８−６）。仮想ノード１３と内側向き仮想リンク（１１，１３）と（１２，１３）は割当不可（図１２）であり，失敗となる（Ｓ８−７）。仮想ノード１３と割当済仮想ノードの間の仮想リンク（１１，１３），（１２，１３）を図２０のように外側に割当てる（Ｓ８−９）。未処理の仮想ノード１４が存在する（Ｓ８−１０）。仮想ノード１３は割当済仮想ノード１１、１２とは接続しない（Ｓ８−６）ので外向き仮想リンクの割当可能判定を行う（Ｓ８−８）。このとき，外向き仮想リンクは存在しないので、現在の部分ネットワーク｛１１，１２｝を出力する。未処理の仮想ノードは存在しないので、再度部分仮想ネットワーク｛１１，１２｝を出力する（Ｓ８−１１）。仮想ノード１２、１３、１４は起点となっていないので、Ｓ８−２にていずれかが選ばれ、再度Ｓ８−３以降が実行される。
【００５２】
部分ネットワーク記憶回路５３は、部分ネットワーク列挙回路５１が部分ネットワーク列挙手順を実行して列挙した物理ノード及び物理リンクを記憶する。部分ネットワーク記憶回路５３が記憶する物理ノード及び物理リンクは、ユーザ装置６０が要求した仮想ノード及び仮想リンクと対応付けられる。
【００５３】
このような処理を実行することで、図４、図７の仮想ネットワークの仮想部分領域は仮想ノード１１及び物理ノード２１ａを起点とした際に、仮想ノードと物理ノードを対応付けて出力することができる。図７の仮想ネットワークの仮想部分領域は、仮想ノード１２及び物理ノード２１ｂを起点とした際に、仮想ノードと物理ノードを対応付けて出力することができる。
【００５４】
また、図８の部分ネットワークは□に対応する仮想ノード１３を物理ノード２１ｃに割当てた際に、仮想ノード１３に接続する外向きの仮想リンクを物理リンクに割当てることができないために割当可能部分ネットワークとして出力されることはない。図１２の太い一点波線で示したリンクが物理リンクに割当ることができない仮想リンクである。
【００５５】
なお、部分ネットワークの列挙を行う場合、各設備提供者装置３０が利用者に物理ネットワーク資源を提供する際の割当コストは秘密にしておかなければならない。そのため、割当コストの開示を各設備提供者装置３０から受ける場合には、任意の秘密計算法を用いる。用いることができる秘密計算法として、例えば、ＭＰＣ（ｍｕｌｔｉｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ）法のほか、Ｆａｉｒｐｌａｙ  ＭＰ、Ｓｈａｒｅｍｉｎｄ、ＳＥＰＩＡ及びＶＩＦＦが例示できる。
【００５６】
部分ネットワーク列挙部５０は、コンピュータを、部分ネットワーク列挙回路５１、部分ネットワーク列挙制御回路５２、部分ネットワーク記憶回路５３として機能させることで実現してもよい。この場合、部分ネットワーク列挙部５０が備えるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が記憶部（不図示）に記憶されたコンピュータプログラムを実行することで、各構成を実現する。
【００５７】
・部分ネットワーク数の削減方法
次に各設備提供者装置３０が備える部分ネットワーク列挙部５０が列挙した物理部分領域の数を削減する方法を述べる。列挙した物理部分領域の削減は、本実施形態に係る部分ネットワーク計算方法を用いて行う。本実施形態に係る部分ネットワーク計算方法は、部分ネットワーク抽出手順を有する。部分ネットワーク抽出手順は、部分ネットワーク抽出部４０が備える部分ネットワーク抽出回路４１を用いて行う。具体的には、部分ネットワーク抽出部４０は、ユーザ装置より要求された仮想ネットワークの仮想ノード及び仮想リンクを最も多く割当てられる物理ネットワーク資源の物理部分領域を抽出して、部分ネットワーク抽出手順を実行する。ここで、ネットワーク資源割当方法は正規化されたコストの順序のみを利用して組合せを探索する。正規化されたコストとは、例えば、列挙された部分ネットワークの単位容量あたりのコストである。このような場合、正規化された値が大きく、列挙された物理部分領域のうち、物理ノード数及び物リンク数が少ない物理部分領域は不要である。
【００５８】
図１７に、各物理部分領域の正規化コストと領域の包含関係の特性を示す。図１７の×印が各物理部分領域の特性である。例えば、仮想部分領域Ｎ１〜Ｎ４を割当てることができる物理部分領域それぞれを、図１７の×で示すことができる。ここで、領域の包含関係は、ユーザ装置６０から要求された仮想ネットワークと、割当可能な物理ネットワーク資源の物理部分領域によって決まる。具体的には、図２に示す仮想ネットワークＮ０が要求された場合には、仮想ネットワークＮ０のうち、物理ネットワーク資源に割当可能な仮想ノード及び仮想リンクが多いほど領域の包含関係では上位となる。また、包含関係が上位であるほど図１４のグラフで上側となる。例えば、図５及び図６に示した仮想部分領域Ｎ２及びＮ３を割当可能な物理部分領域は割当可能な仮想ノードと仮想リンクを１つ有する。また、図７に示した仮想部分領域Ｎ４を割当可能な物理部分領域は割当可能な仮想ノードを１つと仮想リンクを２つ有する。図４に示した仮想部分領域Ｎ１を割当可能な物理部分領域は割当可能な仮想ノードを２つと仮想リンクを３つ有する。そのため、仮想部分領域Ｎ１〜Ｎ４のそれぞれを割当てることができる物理部分領域での領域の包含関係は、上位からＮ１、Ｎ４、Ｎ２及びＮ３を割当てることのできる物理部分領域の順となる。
【００５９】
物理ネットワーク資源に割当てることのできる仮想ネットワークの仮想ノード及び仮想リンクの割合は大きいほど好ましい。そのため、列挙された物理部分領域の数を削減するためには、正規化コストと領域の包含関係において、図１４のようなパレート最適な物理部分領域又はパレート最適に近い物理部分領域のみを抽出し、その他の物理部分領域を削除すれば良い。ここで物理部分領域がパレート最適である場合とは、ユーザ装置６０から要求された仮想ネットワークを物理ネットワーク資源に全て割当てることができ、さらに、仮想ネットワークの仮想部分領域を物理ネットワーク資源の物理部分領域に割当てた際に物理部分領域の容量の余りがない場合である。具体的には、図２に示した仮想ネットワークＮ０がユーザ装置６０から要求された場合、仮想ネットワークＮ０と同じ構成の物理部分領域がパレート最適であり、仮想部分領域Ｎ１、Ｎ４、Ｎ２及びＮ３を割当てることができる物理部分領域順でパレート最適に近くなる。
【００６０】
また、領域の包含関係を計算する際には、物理ノードの提供タイプも考慮する。具体的には、Ｎ２が有する仮想ノードの提供タイプは、Ｎ１が有する仮想ノードの提供タイプのうち、仮想ノード１２で共通する。しかし、Ｎ１〜Ｎ４の範囲では、Ｎ３は他の仮想部分領域と仮想ノードが共通しない。また、仮想部分領域Ｎ１はＮ２、Ｎ４と仮想ノードが共通するが、Ｎ１、Ｎ２、Ｎ４の中ではＮ１が最もパレート最適に近い。そのため、Ｎ１、Ｎ２、Ｎ４を割当てることができる物理部分領域が列挙されている場合には、Ｎ１を割当てることができる物理部分領域のみ抽出される。そして、Ｎ２、Ｎ４を割当てることができる物理部分領域は抽出されない。また、Ｎ３を割当てることができる物理部分領域は、他の物理部分領域と物理ノードが共通しないので抽出される。
【００６１】
領域の包含関係が最も優れた物理部分領域を削除するために、具体的には、後述する式（１）での２項関係における極小元のみを抽出することで、領域の包含関係が最も優れた物理部分領域のみを抽出し、その他の物理部分領域を削除する。
【００６２】
領域の包含関係が最も優れた物理部分領域の集合を抽出する手順を図１８に示す。また、パレート最適な物理部分領域の集合を計算する処理を実行する部分ネットワーク抽出部４０の装置構成図を図１５に示す。部分ネットワーク抽出部４０は、部分ネットワーク抽出回路４１と、部分ネットワーク抽出制御回路４２と、抽出ネットワーク記憶回路４３と、を備える。
【００６３】
部分ネットワーク抽出制御回路４２は、どの物理部分領域についてパレート最適性の計算を行うかの制御を行う。部分ネットワーク抽出制御回路４２は処理開始（Ｓ７−１）の後、計算を行う部分ネットワークＮ１及びＮ２を選択する（Ｓ７−２）。部分ネットワークＮ１及びＮ２は、物理部分領域の集合Ｘに属する。物理部分領域の集合Ｘは、抽出ネットワーク記憶回路４３に記憶されている。
【００６４】
部分ネットワーク抽出回路４１では、部分ネットワーク抽出制御回路４２が選択した各部分ネットワークがパレート最適であるか否かを判定する二項関係の計算を行なう。具体的には、部分ネットワーク抽出回路４１は、以下の式（１）の計算を行う（Ｓ７−３）。
【００６５】
【数１】
0006291371.tif 000002
ここでＮ１及びＮ２はそれぞれ部分ネットワークであり、ｃ（Ｎ１）及びＣ（Ｎ２）はＮ１及びＮ２の正規化されたコストであり、⊆は集合の包含関係である。
【００６６】
部分ネットワーク抽出制御回路４２は、部分ネットワーク抽出回路４１の計算結果から計算対象となった物理部分領域がパレート最適であるかどうか判定する。具体的には、各物理部分領域について、部分ネットワーク抽出回路４１が式（１）の計算を行い、部分ネットワーク抽出制御回路４２が、当該物理部分領域についての計算結果が極小元であるかどうか判定する（Ｓ７−３）。極小元であれば（Ｓ７−３でＹＥＳ）、パレート最適な部分ネットワークである。物理部分領域についての計算結果が極小元でない場合には、部分ネットワーク集合からそれを取り除くことで領域の包含関係の値が一定以上の物理部分領域の集合が得られる。
【００６７】
Ｓ７−３の計算結果が極小元であれば、抽出ネットワーク記憶回路４３は、物理部分領域の集合の更新を行い（Ｓ７−４）、Ｓ７−５に遷移する。Ｓ７−５では、物理部分領域の集合Ｘのうち、全ての物理部分領域ペアについてＳ７−３の計算を行ったかを判定する。全ての物理部分領域についてＳ７−３の計算を行っている場合には、Ｓ７−６に遷移して処理を終了する。全ての物理部分領域についてＳ７−３の計算を行っていない場合には、Ｓ７−２に遷移して再度Ｓ７−３の計算を行う。
【００６８】
したがって、Ｓ７−１〜Ｓ７−６の処理が終了した後に抽出ネットワーク記憶回路４３に記憶されている物理部分領域は、領域の包含関係の値が一定以上の物理部分領域である。そのため、仮想ネットワークを物理ネットワーク資源に割当てる際に、仮想ノード及び仮想リンクの容量は割当てられる物理ノード及び物理リンクの容量と等しいか、仮想ノード及び仮想リンクを物理ノード及び物理リンクに割当てた後の物理ノード及び物理リンクの容量の余りは最少となる。
【００６９】
なお、物理部分領域の数の削減を行う場合にも、各設備提供者装置３０がユーザ装置６０に物理ネットワークを提供する際の割当コストは秘密にしておかなければならない。そのため、割当コストの開示を各設備提供者装置から受ける場合には、任意の秘密計算法を用いる。用いることができる秘密計算法として、例えば、ＭＰＣ（ｍｕｌｔｉｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ）法のほか、Ｆａｉｒｐｌａｙ  ＭＰ、Ｓｈａｒｅｍｉｎｄ、ＳＥＰＩＡ及びＶＩＦＦが例示できる。
【００７０】
部分ネットワーク抽出部４０は、コンピュータを、部分ネットワーク抽出回路４１、部分ネットワーク抽出制御回路４２、抽出ネットワーク記憶回路４３として機能させることで実現してもよい。この場合、部分ネットワーク抽出部４０が備えるＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が記憶部（不図示）に記憶されたコンピュータプログラムを実行することで、各構成を実現する。
【００７１】
また、本実施形態に係る部分ネットワークの列挙方法を用いて列挙した部分ネットワークを用いて、物理ネットワーク資源を仮想ネットワークへと割当てることができる。具体的には、本実施形態に係る抽出ネットワーク記憶回路４３に記憶されている列挙後に抽出した物理部分領域を検索して、仮想ネットワークを物理ネットワーク資源に割当てることができる。
【００７２】
例えば、先ず、抽出ネットワーク記憶回路４３に記憶されている物理部分領域を、割当コストに小さな順にソートする。次に、ソート後の各物理部分領域に割当コストの小さな順にＩＤを割当てる。次に、仮想ネットワークが有するすべての仮想ノードと仮想リンクをカバーすることを制約条件として、なるべく小さなＩＤの物理部分領域を用いる最適化問題を解く。この最適化問題を解くことにより、仮想ネットワークの物理ネットワーク資源への割当において、割当コストを小さくすることができる。この問題の解き方は任意であるが、例えば、動的計画法を用いることができる。
【００７３】
図１９に、図２に示された仮想ネットワークを物理ネットワーク資源が有する物理ノード及び物理リンクに割当てた例を示す。図１９では、図２の仮想ネットワークが完全に物理ネットワーク資源に割当てられている。図１９に示すように、複数の仮想リンクを１つ
の物理リンクに割当ててもよい。また、物理リンクの容量の許す限り、複数の仮想ノードを物理ノードに割当ててもよい（不図示）。
【００７４】
なお、本発明の部分ネットワーク計算装置及び部分ネットワーク計算方法はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。また、部分ネットワーク計算装置及び部分ネットワーク計算方法を実現する際のコンピュータは、コンピュータによって制御される任意の機器をさらに備えてもよい。
【産業上の利用可能性】
【００７５】
本発明の部分ネットワーク計算装置、部分ネットワーク計算方法及び部分ネットワーク計算プログラムは、情報通信産業に適用することができる。
【符号の説明】
【００７６】
１１，１２，１３，１４：仮想ノード
２１ａ，２１ｂ，２１ｃ，２１ｄ，２２ａ，２２ｂ，２３ａ，２３ｂ，２４ａ：物理ノード
３０：設備提供者装置
４０：部分ネットワーク抽出部
４１：部分ネットワーク抽出回路
４２：部分ネットワーク抽出制御回路
４３：抽出ネットワーク記憶回路
５０：部分ネットワーク列挙部
５１：部分ネットワーク列挙回路
５２：部分ネットワーク列挙制御回路
５３：列挙ネットワーク記憶回路
６０：ユーザ装置
７０：ネットワーク
【図１】
0006291371.tif 000003
【図２】
0006291371.tif 000004
【図３】
0006291371.tif 000005
【図４】
0006291371.tif 000006
【図５】
0006291371.tif 000007
【図６】
0006291371.tif 000008
【図７】
0006291371.tif 000009
【図８】
0006291371.tif 000010
【図９】
0006291371.tif 000011
【図１０】
0006291371.tif 000012
【図１１】
0006291371.tif 000013
【図１２】
0006291371.tif 000014
【図１３】
0006291371.tif 000015
【図１４】
0006291371.tif 000016
【図１５】
0006291371.tif 000017
【図１６】
0006291371.tif 000018
【図１７】
0006291371.tif 000019
【図１８】
0006291371.tif 000020
【図１９】
0006291371.tif 000021
【図２０】
0006291371.tif 000022