(57)【特許請求の範囲】
【請求項１】
物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムであって、
前記設備提供者装置は、
前記ユーザ装置から要求された仮想ネットワークの部分である仮想部分領域を構築可能な物理ネットワーク資源の物理部分領域を、前記仮想部分領域ごとに抽出し、抽出した各物理部分領域に識別子を付し、各物理部分領域の割当コストと識別子を関連付けた一覧表を作成する部分ネットワーク資源抽出部と、
他の前記設備提供者装置と協調して前記複数の設備提供者装置が作成した前記一覧表を統合し、統合後の前記一覧表に含まれる識別子を割当コストの順に並べる識別子配列部と、
前記ユーザ装置から前記識別子を含む問い合わせを受けると、問い合わせのあった識別子に対応する物理部分領域の情報を前記ユーザ装置に通知する物理領域情報通知部と、
を備え、
前記ユーザ装置は、
前記設備提供者装置に前記仮想ネットワークの資源利用要求を送信する資源利用要求部と、
前記複数の設備提供者装置が協調して割当コストの順に並べた前記一覧表を取得すると、前記一覧表に含まれる識別子に対応する物理部分領域の情報を前記複数の設備提供者装置から受信する物理領域情報受信部と、
前記仮想ネットワークの前記仮想部分領域を、前記物理領域情報受信部の受信した物理部分領域の情報に割り当てる資源割当計算部と、
を備える、
ネットワーク資源割当システム。
【請求項２】
物理ネットワーク資源を保有する設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムにおけるネットワーク資源割当方法であって、
前記ユーザ装置が、前記設備提供者装置に前記仮想ネットワークの資源利用要求を送信する資源利用要求手順と、
前記複数の設備提供者装置が、前記ユーザ装置から要求された仮想ネットワークの部分である仮想部分領域を構築可能な物理ネットワーク資源の物理部分領域を、前記仮想部分領域ごとに抽出し、抽出した各物理部分領域に識別子を付し、各物理部分領域の割当コストと識別子を関連付けた一覧表を作成する部分ネットワーク資源抽出手順と、
前記複数の設備提供者装置が、他の前記設備提供者装置と協調して前記複数の設備提供者装置が作成した前記一覧表を統合し、統合後の前記一覧表に含まれる識別子を割当コストの順に並べる識別子配列手順と、
前記ユーザ装置が、前記複数の設備提供者装置が協調して割当コストの順に並べた前記一覧表を取得すると、前記一覧表に含まれる識別子に対応する物理部分領域の情報を前記複数の設備提供者装置に問い合わせ、前記複数の設備提供者装置が、問い合わせのあった識別子に対応する物理部分領域の情報を前記ユーザ装置に通知する物理領域情報通知手順と、
前記ユーザ装置が、前記仮想ネットワークの前記仮想部分領域を、前記物理領域情報通知手順で通知された物理部分領域の情報に割り当てる資源割当計算手順と、
を順に有するネットワーク資源割当方法。
【請求項３】
物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムにおける前記ユーザ装置であって、
前記設備提供者装置に前記仮想ネットワークの資源利用要求を送信する資源利用要求部と、
前記仮想ネットワークの部分である仮想部分領域を構築可能な前記設備提供者装置のそれぞれが保有する物理ネットワーク資源の物理部分領域の割当コストと当該物理部分領域の識別子を関連付けた一覧表を取得すると、前記一覧表に含まれる識別子に対応する物理部分領域の情報を前記複数の設備提供者装置から受信する物理領域情報受信部と、
前記仮想ネットワークの前記仮想部分領域を、前記物理領域情報受信部の受信した物理部分領域の情報に割り当てる資源割当計算部と、
を備えるユーザ装置。
【請求項４】
物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムおける前記設備提供者装置であって、
前記ユーザ装置から要求された仮想ネットワークの部分である仮想部分領域を構築可能な物理ネットワーク資源の物理部分領域を、前記仮想部分領域ごとに抽出し、抽出した各物理部分領域に識別子を付し、各物理部分領域の割当コストと識別子を関連付けた一覧表を作成する部分ネットワーク資源抽出部と、
他の前記設備提供者装置と協調して前記複数の設備提供者装置が作成した前記一覧表を統合し、統合後の前記一覧表に含まれる識別子を割当コストの順に並べる識別子配列部と、
前記ユーザ装置から前記識別子を含む問い合わせを受けると、問い合わせのあった識別子に対応する物理部分領域の情報を前記ユーザ装置に通知する物理領域情報通知部と、
を備える設備提供者装置。
【請求項５】
コンピュータを、請求項３に記載の資源利用要求部及び資源割当計算部として機能させるためのユーザ装置プログラム。
【請求項６】
コンピュータを、請求項４に記載の部分ネットワーク資源抽出部及び識別子配列部として機能させるための設備提供者装置プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の設備提供者がユーザの資源利用要求に対してその要求を満たす資源割当を情報秘匿のまま発見する方法に関する。ここで、設備提供者とはネットワーク資源やＩＣＴ資源を保有し、それらをユーザに提供するインターネットサービスプロバイダー（ＩＳＰ）などのことである。また、資源割当とは設備提供者がユーザからの仮想ネットワークなどの資源利用要求に応じて、保有する設備の中からどのネットワーク機器・ＩＣＴ機器を使用し、それらをどのように接続するかを決定することである。また、情報秘匿のまま発見するとは、各設備提供者が設備情報等を互いに開示することなく資源割当を発見することである。
【背景技術】
【０００２】
非特許文献１及び２に関連する資源割当てを行う方法が開示されている。非特許文献１及び２の手法は、すべての設備提供者がノードコストやリンクコストなどの保有設備の割当コストを公開し、その情報を用いて資源割り当てを行う。しかし、非特許文献１及び２の手法では、割当コストは競争力に直結する重要な情報であるため、設備提供者が公開することは難しく、現実性に課題がある。
【０００３】
そこで、可能なすべての割当について各設備提供者が割当コストを計算し、非特許文献３で開示されているＭＰＣ（Ｍｕｌｔｉ  Ｐａｒｔｙ  Ｃｏｍｐｕｔａｔｉｏｎ）などの秘密計算を用いて、割当コストを公開することなく合計し比較することが考えられる。ここで、ＭＰＣは複数の参加者が参加して計算を行う手法のひとつで、各参加者の入力に基づく計算を各参加者の入力を開示することなく実行する手法である。一般的なＭＰＣでは、乗算、比較等の基本的な演算ごとに参加者間での通信が発生する。しかし、ＭＰＣを用いて可能なすべての割当についてコストを計算し、比較すると、割当の数は仮想ネットワークの大きさに対して指数的に増加する。このため、ＭＰＣを用いて従来手法を実行すると、通信遅延が大量に発生し計算終了までに必要な時間が膨大になるという課題がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｉｎｅｓ  Ｈｏｕｉｄｉ，  Ｗａｊｄｉ  Ｌｏｕａｔｉ，  Ｗａｌｉｄ  Ｂｅｎ  Ａｍｅｕｒ  ａｎｄ  Ｄｊａｍａｌ  Ｚｅｇｈｌａｃｈｅ，  “Ｖｉｒｔｕａｌ  ｎｅｔｗｏｒｋ  ｐｒｏｖｉｓｉｏｎｉｎｇ  ａｃｒｏｓｓ  ｍｕｌｔｉｐｌｅ  ｓｕｂｓｔｒａｔｅ  ｎｅｔｗｏｒｋｓ，”  Ｃｏｍｐｕｔｅｒ  Ｎｅｔｗｏｒｋｓ，  ｖｏｌ．５５，  ｎｏ．４，  ｐｐ．１０１１−１０２３，  ２０１１．
【非特許文献２】Ｓａｍｕｅｌ，  Ｆａｄｙ，  Ｃｈｏｗｄｈｕｒｙ，  Ｍｏｓｈａｒａｆ，  Ｂｏｕｔａｂａ，  ａｎｄ  Ｒａｏｕｆ，  “ＰｏｌｙＶｉＮＥ：  ｐｏｌｉｃｙ−ｂａｓｅｄ  ｖｉｒｔｕａｌ  ｎｅｔｗｏｒｋ  ｅｍｂｅｄｄｉｎｇ  ａｃｒｏｓｓ  ｍｕｌｔｉｐｌｅ  ｄｏｍａｉｎｓ”，  Ｊｏｕｒｎａｌ  ｏｆ  Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，  ｖｏｌ．４，  ｎｏ．１，  ｐｐ．１−２３，  ２０１３．
【非特許文献３】Ｊｏｎｓｓｏｎ，  Ｋｒｉｓｔｊａｎ  Ｖａｌｕｒ，  Ｋｒｅｉｔｚ，  Ｇｕｎｎａｒ，  Ｕｄｄｉｎ  ａｎｄ  Ｍｉｓｂａｈ，  “Ｓｅｃｕｒｅ  Ｍｕｌｔｉ−Ｐａｒｔｙ  Ｓｏｒｔｉｎｇ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ”，  ＩＡＣＲ  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ，  Ｒｅｐｏｒｔ  ２０１１／１２２，  ２０１１．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
そこで、本発明は上記の点に鑑みてなされたものであり、設備提供者が割当コストを公開することなく、ユーザが所望する低コストな仮想ネットワークを実現することを目的とする。
【課題を解決するための手段】
【０００６】
本発明では、各設備提供者が割当可能な仮想ネットワークの部分領域について、割当コストを伏せたまま「順位」だけを明らかにし、順位のよい部分領域を組み合わせて仮想ネットワークを実現する。本発明では、すべての割当を調べることなく、「順位」を用いて最適な割当を効率的に探索可能にする。
【０００７】
具体的には、本発明に係るネットワーク資源割当システムは、
物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムであって、
前記設備提供者装置は、
前記ユーザ装置から要求された仮想ネットワークの部分である仮想部分領域を構築可能な物理ネットワーク資源の物理部分領域を、前記仮想部分領域ごとに抽出し、抽出した各物理部分領域に識別子を付し、各物理部分領域の割当コストと識別子を関連付けた一覧表を作成する部分ネットワーク資源抽出部と、
他の前記設備提供者装置と協調して前記複数の設備提供者装置が作成した前記一覧表を統合し、統合後の前記一覧表に含まれる識別子を割当コストの順に並べる識別子配列部と、
前記ユーザ装置から前記識別子を含む問い合わせを受けると、問い合わせのあった識別子に対応する物理部分領域の情報を前記ユーザ装置に通知する物理領域情報通知部と、
を備え、
前記ユーザ装置は、
前記設備提供者装置に前記仮想ネットワークの資源利用要求を送信する資源利用要求部と、
前記複数の設備提供者装置が協調して割当コストの順に並べた前記一覧表を取得すると、前記一覧表に含まれる識別子に対応する物理部分領域の情報を前記複数の設備提供者装置から受信する物理領域情報受信部と、
前記仮想ネットワークの前記仮想部分領域を、前記物理領域情報受信部の受信した物理部分領域の情報に割り当てる資源割当計算部と、
を備える。
【０００８】
具体的には、本発明に係るネットワーク資源割当方法は、
物理ネットワーク資源を保有する設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムにおけるネットワーク資源割当方法であって、
前記ユーザ装置が、前記設備提供者装置に前記仮想ネットワークの資源利用要求を送信する資源利用要求手順と、
前記複数の設備提供者装置が、前記ユーザ装置から要求された仮想ネットワークの部分である仮想部分領域を構築可能な物理ネットワーク資源の物理部分領域を、前記仮想部分領域ごとに抽出し、抽出した各物理部分領域に識別子を付し、各物理部分領域の割当コストと識別子を関連付けた一覧表を作成する部分ネットワーク資源抽出手順と、
前記複数の設備提供者装置が、他の前記設備提供者装置と協調して前記複数の設備提供者装置が作成した前記一覧表を統合し、統合後の前記一覧表に含まれる識別子を割当コストの順に並べる識別子配列手順と、
前記ユーザ装置が、前記複数の設備提供者装置が協調して割当コストの順に並べた前記一覧表を取得すると、前記一覧表に含まれる識別子に対応する物理部分領域の情報を前記複数の設備提供者装置に問い合わせ、前記複数の設備提供者装置が、問い合わせのあった識別子に対応する物理部分領域の情報を前記ユーザ装置に通知する物理領域情報通知手順と、
前記ユーザ装置が、前記仮想ネットワークの前記仮想部分領域を、前記物理領域情報通知手順で通知された物理部分領域の情報に割り当てる資源割当計算手順と、
を順に有する。
【０００９】
具体的には、本発明に係るユーザ装置は、
物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムにおける前記ユーザ装置であって、
前記設備提供者装置に前記仮想ネットワークの資源利用要求を送信する資源利用要求部と、
前記仮想ネットワークの部分である仮想部分領域を構築可能な前記設備提供者装置のそれぞれが保有する物理ネットワーク資源の物理部分領域の割当コストと当該物理部分領域の識別子を関連付けた一覧表を取得すると、前記一覧表に含まれる識別子に対応する物理部分領域の情報を前記複数の設備提供者装置から受信する物理領域情報受信部と、
前記仮想ネットワークの前記仮想部分領域を、前記物理領域情報受信部の受信した物理部分領域の情報に割り当てる資源割当計算部と、
を備える。
【００１０】
具体的には、本発明に係る設備提供者装置は、
物理ネットワーク資源を保有する複数の設備提供者装置と前記物理ネットワーク資源を利用するユーザ装置がネットワークで接続されたネットワーク資源割当システムおける前記設備提供者装置であって、
前記ユーザ装置から要求された仮想ネットワークの部分である仮想部分領域を構築可能な物理ネットワーク資源の物理部分領域を、前記仮想部分領域ごとに抽出し、抽出した各物理部分領域に識別子を付し、各物理部分領域の割当コストと識別子を関連付けた一覧表を作成する部分ネットワーク資源抽出部と、
他の前記設備提供者装置と協調して前記複数の設備提供者装置が作成した前記一覧表を統合し、統合後の前記一覧表に含まれる識別子を割当コストの順に並べる識別子配列部と、
前記ユーザ装置から前記識別子を含む問い合わせを受けると、問い合わせのあった識別子に対応する物理部分領域の情報を前記ユーザ装置に通知する物理領域情報通知部と、
を備える。
【００１１】
具体的には、本発明に係るユーザ装置プログラムは、コンピュータを、本発明に係るユーザ装置に備わる資源利用要求部、物理領域情報受信部及び資源割当計算部として機能させるためのプログラムである。
【００１２】
具体的には、本発明に係る設備提供者装置プログラムは、コンピュータを、本発明に係る設備提供者装置に備わる部分ネットワーク資源抽出部、協調計算部及び物理領域情報通知部として機能させるためのプログラムである。
【発明の効果】
【００１３】
本発明によれば、設備提供者が割当コストを公開することなく、ユーザが所望する低コストな仮想ネットワークを実現することができる。
【図面の簡単な説明】
【００１４】
【図１】ユーザ装置の要求する仮想ネットワークの一例を示す。
【図２】複数の設備提供者装置の保有する物理ネットワークの一例を示す。
【図３】本実施形態に係るネットワーク資源割当システムの構成例である。
【図４】設備提供者装置の機能構成例を示す。
【図５】ユーザ装置の機能構成例を示す。
【図６】本実施形態に係るネットワーク資源割当システムのシーケンス図を示す。
【図７】設備提供者が収容可能な部分ネットと価格の一例を示す。
【図８】ＩＤと価格の表の作成例を示す。
【図９】秘密計算によってコスト順にソートされた部分ネットとピアリンクの一例を示す。
【図１０】動的計画法に基づく仮想ネットワークの構成例を示す。
【図１１】共通の設備提供者の保有する二つ以上の部分ネットが現れた場合の動作例を説明するための仮想ネットワークの一例を示す。
【図１２】共通の設備提供者の保有する二つ以上の部分ネットが現れた場合の動作例を説明するための物理ネットワークの一例を示す。
【図１３】共通の設備提供者の保有する二つ以上の部分ネットが現れた場合の動作例を説明するための部分ネットの第１の選択例を示す。
【図１４】共通の設備提供者の保有する二つ以上の部分ネットが現れた場合の動作例を説明するための部分ネットの第２の選択例を示す。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について、図面を参照しながら詳細に説明する。なお、本発明は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本発明は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００１６】
（本実施の形態において対象とする問題例）
まず、本実施の形態における問題例を述べる。本実施の形態では設備提供者が管理するストレージサーバーや計算サーバーのようなネットワーク機器をノード、それらノードを結ぶ回線等をリンクと呼ぶ。
【００１７】
図１にユーザ装置の要求する仮想ネットワークの一例を示す。図２に、複数の設備提供者装置の保有する物理ネットワークの一例を示す。図１に示す仮想ネットワークは、仮想ノード９２ａ，９２ｂ，９２ｃと、仮想ノード９２ａ及び９２ｂをつなぐ仮想リンクと、仮想ノード９２ａ及び９２ｃをつなぐ仮想リンクで構成される。各仮想ノード９２ａ，９２ｂ，９２ｃ及び各仮想リンクには要求容量（ＣＰＵクロック数や通信帯域）が与えられる。
【００１８】
仮想ノードの中の数字が仮想ノードの要求容量を示し、仮想リンクの傍の数字が仮想リンクへの要求容量を示す。図１では、仮想ノード９２ａの要求容量は３、仮想ノード９２ｂの要求容量は３、仮想ノード９２ｃの要求容量は１である。また、仮想ノード９２ａと仮想ノード９２ｂを連結する仮想ノードの要求容量は１、仮想ノード９２ａと仮想ノード９２ｃを連結する仮想ノードの要求容量は２である。
【００１９】
設備提供者の提供する物理ネットワークは、物理ノードと物理リンクで構成され、それぞれに空き容量と割当コストがある。物理ノード内の数字が物理ノードの空き容量を示し、物理リンクの数字が物理リンクの空き容量を示す。設備提供者Ａは、実線で示された物理ネットワークを保有し、物理ノード９１ａ−１及び９１ａ−２並びにそれらをつなぐ物理リンクを提供する。設備提供者Ａの割当コストは、容量あたりの価格が２である。設備提供者Ｂは、破線で示された物理ネットワークを保有し、物理ノード９１ｂ−１及び９１ｂ−２並びにそれらをつなぐ物理リンクを提供する。設備提供者Ｂの割当コストは、容量あたりの価格が１である。設備提供者Ｃは、一点鎖線で示された物理ネットワークを保有し、物理ノード９１ｃ−１及び９１ｃ−２並びにそれらをつなぐ物理リンクを提供する。設備提供者Ｃの割当コストは、容量あたりの価格が３である。
【００２０】
物理ネットワークは複数の設備提供者Ａ，Ｂ，Ｃによって構成され、各物理ノードや物理リンクの情報はそれぞれの設備提供者しか知り得ない。ただし、設備提供者間を接続するリンク（以降、単にピアリンク）については、両端となるふたつの設備提供者が情報を共有する。例えば、物理ノード９１ａ−１と物理ノード９１ｂ−１を接続するピアリンクは、容量当たりの価格が１０であるという情報を設備提供者Ａ及びＢが共有する。物理ノード９１ａ−２と物理ノード９１ｃ−１を接続するピアリンクは、容量当たりの価格が３０であるという情報を設備提供者Ａ及びＣが共有する。物理ノード９１ｂ−２と物理ノード９１ｃ−２を接続するピアリンクは、容量当たりの価格が２０であるという情報を設備提供者Ａ及びＣが共有する。
【００２１】
仮想ネットワーク割当問題とは、仮想ノードとリンクを、それらの要求容量を満たす物理ノードあるいは物理リンクに割り当てることである。仮想ノードはひとつの物理ノードに割り当てられる。仮想リンクは、複数の物理リンクによって構成されることがあり（一般にｐａｔｈと呼ばれる）、その場合には、仮想リンクを構成するすべての物理リンクに要求容量以上の空き容量がなければならない。
【００２２】
仮想ネットワークのコストとは、割当に用いたすべての物理ノードと物理リンクの合計コストである。本実施形態に係る発明では、この合計コストを最小にする割当を見つける。
【００２３】
（本実施の形態の概要）
図３を参照して発明手法を述べる。図３は本実施形態に係るネットワーク資源割当システムの構成例である。本実施形態に係るネットワーク資源割当システムは、各設備提供者装置２０およびユーザ装置１０がネットワーク９０を介して接続されており、通信可能である。
【００２４】
図４に、各設備提供者装置の機能構成例を示す。設備提供者装置２０は、部分ネット及びピアリンク列挙部２１、部分ネット及びピアリンクＤＢ２２、ソート用協調計算部２３、復号用協調計算部２４、及び資源割当計算部２５を備える。部分ネット及びピアリンクＤＢ２２は記憶部（不図示）に記憶される。設備提供者装置２０は、コンピュータを、部分ネット及びピアリンク列挙部２１、部分ネット及びピアリンクＤＢ２２、ソート用協調計算部２３、復号用協調計算部２４、及び資源割当計算部２５として機能させることで実現してもよい。この場合、設備提供者装２０内のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）（不図示）が、記憶部（不図示）に記憶されたコンピュータプログラムを実行することで、各構成を実現する。
【００２５】
部分ネット及びピアリンク列挙部２１は、部分ネットワーク資源抽出部として機能し、ユーザ装置１０に提示する部分ネット及びピアリンクの列挙を行う。部分ネット及びピアリンクＤＢ２２は、ユーザ装置１０に提示する部分ネット及びピアリンクのデータを保存する。ソート用協調計算部２３は、識別子配列部として機能し、秘密計算によるソートを他の設備提供者装置２０と協調して行う。復号用協調計算部２４は、識別子配列部として機能し、秘密計算による結果の復号を他の設備提供者装置２０と協調して行う。資源割当計算部２５は、部分ネットワーク資源抽出部として機能し、部分ネットの価格計算を行うとともに、仮想ネットワーク要求を受信する。資源割当計算部２５は、物理領域情報通知部として機能し、ユーザ装置１０からＩＤを含む問い合わせを受けると、問い合わせのあったＩＤに対応する部分ネットの情報をユーザ装置１０に通知する。
【００２６】
図５は、ユーザ装置の機能構成例を示す図である。ユーザ装置１０は、部分ネット及びピアリンクＤＢ１１、部分ネット及びピアリンク探索部１２、復号用協調計算部１３及び資源割当計算部１４を備える。ユーザ装置１０は、コンピュータを、部分ネット及びピアリンクＤＢ１１、部分ネット及びピアリンク探索部１２、復号用協調計算部１３及び資源割当計算部１４として機能させることで実現してもよい。この場合、ユーザ装置１０内のＣＰＵ（不図示）が、記憶部（不図示）に記憶されたコンピュータプログラムを実行することで、各構成を実現する。
【００２７】
資源割当計算部１４は、仮想ネットワーク要求の送信や、仮想ネットワーク分割後にそれぞれの設備提供者装置２０に資源割当要求を送信する。復号用協調計算部１３は、秘密計算によりソートされた部分ネット及びピアリンク列の復号を設備提供者装置２０と協調して行う。部分ネット及びピアリンクＤＢ１１は、復号用協調計算部１３の計算結果を保持する。部分ネット及びピアリンク探索部１２は、物理領域情報受信部として機能し、仮想ネットワークの構築に用いる物理ネットワークの部分ネット及びピアリンクを割当コストの低い順に探索する。
【００２８】
図６に、本実施形態に係るネットワーク資源割当システムのシーケンス図を示す。本実施形態に係るネットワーク資源割当システムは、本実施形態に係るネットワーク資源割当方法を実行する。本実施形態に係るネットワーク資源割当方法は、資源利用要求手順（Ｓ１０１）と、部分ネットワーク資源抽出手順（Ｓ１０２及びＳ１０３）と、識別子配列手順（Ｓ１０４）と、物理領域情報通知手順（Ｓ１０５）と、資源割当計算手順（Ｓ１０６）と、を順に有する。識別子配列手順（Ｓ１０４）では、秘密計算法によるソート処理を行う。このソート処理は、設備提供者側装置２０Ａ，２０Ｂ及び２０Ｃにおいて実行する。識別子配列手順（Ｓ１０４）における復号処理は、ユーザ装置１０と設備提供者側装置２０において実行する。
【００２９】
資源利用要求手順（Ｓ１０１）では、ユーザ装置１０に備わる送受信部（不図示）が、資源利用要求をすべての設備提供者装置２０Ａ，２０Ｂ及び２０Ｃへ送信する。
部分ネットワーク資源抽出手順（Ｓ１０２及びＳ１０３）では、各設備提供者装置２０Ａ，２０Ｂ及び２０Ｃが、仮想ネットワークの部分である仮想部分領域を構築可能な物理ネットワーク資源の物理部分領域を、仮想部分領域ごとに抽出する。そして、各物理部分領域を各物理部分領域の識別子であるＩＤと関連付け、ＩＤと割当コストを紐付した表を作成する。
識別子配列手順（Ｓ１０４）では、設備提供者装置２０Ａ，２０Ｂ及び２０Ｃが、互いに協調し、設備提供者装置２０Ａ，２０Ｂ及び２０Ｃが作成した表のＩＤを割当コストに従って並べ替える。
物理領域情報通知手順（Ｓ１０５）では、割当コストの順に並んだＩＤ列から任意のＩＤを選択し、各設備提供者２０に選択したＩＤを伝え、対応する部分ネットあるいはピアリンクを取得する。
資源割当計算手順（Ｓ１０６）では、ユーザ装置１０が、設備提供者装置２０Ａ，２０Ｂ及び２０Ｃが割当コスト順に並べ替えた物理部分領域を取得し、割当コスト順に、仮想ネットワークの仮想部分領域を物理部分領域に割り当てる。
以下、各手順の詳細について説明する。
【００３０】
資源利用要求手順（Ｓ１０１）では、ユーザ装置１０から要求された仮想ネットワークを、すべての設備提供者装置２０で共有する。資源利用要求には、図１に示すような、ユーザ装置１０の利用しようとする仮想ネットワークを構成する仮想ノード及び仮想リンクの情報が含まれる。
【００３１】
部分ネットワーク資源抽出手順では、各設備提供者装置２０Ａ，２０Ｂ，２０Ｃの部分ネット及びピアリンク列挙部２１は、与えられた仮想ネットワークから、仮想部分領域を収容可能な物理部分領域（以降、部分ネット）を列挙する。そして、資源割当計算部２５が価格を計算する（Ｓ１０２）。例えば、設備提供者装置２０Ａは、仮想ノード９２及び９２ｃとこれらを接続する仮想リンクを収容可能な物理ノード及び物理リンクからなる部分ネットを有するか否かを判定し、有する場合は当該部分ネットの価格＝１２を計算する。設備提供者装置２０Ｂ及び２０Ｃにおいても同様に、図７に示すような、仮想部分領域を収容可能な部分ネットとその価格を計算する。ここで、ひとつの設備提供者装置２０が複数の部分ネットを挙げてもよい。また、各設備提供者装置２０の資源割当計算部２５は、ピアリンクについても価格を計算する。
【００３２】
そして、資源割当計算部２５は、部分ネットとピアリンクに適当なＩＤを与え、図８に示すようなＩＤと価格の表を作成する（Ｓ１０３）。ＩＤと部分ネットとの対応付けは、各設備提供者装置２０Ａ，２０Ｂ，２０Ｃが個別に管理し、表には含まない。ピアリンクは、両端のいずれか一方の設備提供者装置２０が処理すればよい。この例では簡単のために価格をそのまま用いるが、「単位容量あたりの価格」のような補正値を用いてもよい。その場合、全設備提供者装置２０Ａ，２０Ｂ，２０Ｃで同じ補正方法を用いる。
【００３３】
ここまでは、各設備提供者装置２０Ａ，２０Ｂ，２０Ｃが独立に行う。ＩＤと価格の表は公開しない。また、部分ネットの列挙方法は任意であり、各設備提供者装置２０Ａ，２０Ｂ，２０Ｃが自由に決めてよい。
【００３４】
次に、設備提供者装置２０Ａ，２０Ｂ，２０Ｃのソート用協調計算部２３が識別子配列手順を実行する（Ｓ１０４）。識別子配列手順では、設備提供者装置２０はＩＤと価格の表を秘密分散法を用いて暗号化して、全設備提供者装置２０と共有する。秘密分散法は、秘密にしたい情報を複数の分散情報に分けることによって保護する手法であり、分散情報は一定数集めなければ元の情報を復元できない。設備提供者装置２０のソート用協調計算部２３は協調して、秘密計算法を用い、分散したままの秘匿データである全設備提供者装置２０の表をマージして、価格の小さい順に表をソートする。そして、識別子配列手順の後に、全設備提供者装置２０は、ソート後の秘匿データをユーザ装置１０に送る。ユーザ装置１０の復号用協調計算部１３は、全設備提供者装置２０から送られたソート後の秘匿データを集める。ユーザ装置１０の復号用協調計算部１３のみにソートされた表のＩＤ列を復元させる（図８右）。
【００３５】
ここで、本実施形態では、部分ネットの価格順にソートするのみであるため、計算が容易である。このため、任意の秘密計算法を用いることができる。例えば、ＭＰＣ法（非特許文献３）のほか、Ｆａｉｒｐｌａｙ  ＭＰ、Ｓｈａｒｅｍｉｎｄ、ＳＥＰＩＡ及びＶＩＦＦが例示できる。
【００３６】
このように、全設備提供者装置２０が秘密計算法を用いて部分ネットを価格の小さい順に並べるため、ユーザ装置１０は、価格情報を得ることなく、価格の小さい順にソートされたＩＤ列を入手する。また、この過程で、設備提供者装置２０が、他の設備提供者装置２０の情報を入手することはない。
【００３７】
次に、物理領域情報通知手順（Ｓ１０５）を行う。ユーザ装置１０の部分ネット及びピアリンク探索部１２は、価格の小さい順にソートされたＩＤ列から任意のＩＤを選択し、各設備提供者装置２０に選択したＩＤを伝え、対応する部分ネットあるいはピアリンクを取得する。この時点で、ユーザ装置１０は、図９に示すような、価格の小さい順にソートされた部分ネットおよびピアリンクの列を得る。
【００３８】
最後に、ユーザ装置１０の資源割当計算部１４が資源割当計算手順（Ｓ１０６）を行う。ユーザ装置１０は、なるべく若い順位の部分ネットとピアリンクを組み合わせて、仮想ネットワークを構成する。若い順位を用いることで、安い価格を期待できる。仮想ネットワークを構成するためには、選択した部分ネットとピアリンクの組合せによって、すべての仮想ノードと仮想リンクをカバーできなければならない。つまり、組合せによるカバーを制約条件とし、なるべく順位を若くすることを目的とする最適化問題を解けばよい。この問題の解き方は任意であるが、ここでは図１０を用いて動的計画法に基づく一例を説明する。
【００３９】
図１０に示すように、資源割当計算部１４は、部分ネットとピアリンクを横に並べ、要求仮想ネットワークの構成要素数（仮想ノードと仮想リンクの合計数）を縦とする表を作成する。資源割当計算部１４は、まず最左列の部分ネットあるいはピアリンクをみて、それによってカバーできる仮想ネットワークの構成要素数を求める。本実施形態では、最も若い順位の部分ネットは、ノードのみであるため、構成要素数が１である。次に、２列目の部分ネットあるいはピアリンクを追加してできる仮想ネットワークの構成要素数を求める。
【００４０】
ここで、図１０の２列目では、構成要素数１と構成要素数３のいずれかを選択することができる。しかし、図１０の２列目で選択できるのは、いずれも設備提供者Ａの保有する部分ネットである。このような場合、図１１〜図１４に示すように、ひとつの設備提供者装置２０はひとつの部分ネットしか提供できない。例えば、図１１に示す仮想ネットワークが資源利用要求であり、設備提供者が図１２に示す部分ネットを有していたとする。この場合に、図１２に示す部分ネットを用いて図１１に示す仮想ネットワークを構築しようとしても、図１３に示す仮想ノード９２ｅと９２ｄ及びその仮想リンクか、或いは図１４に示す仮想ノード９２ｄと９２ｆ及びその仮想リンクしか構成することができない。このように、仮想ノード９２ｅと９２ｄ及びその仮想リンクと、仮想ノード９２ｄと９２ｆ及びその仮想リンクと、を同時に収容することは不可能である。
【００４１】
そこで、資源割当計算部１４は、共通の設備提供者の保有する二つ以上の部分ネットが現れた場合、いずれかひとつを選択する。例えば、２列目の構成要素数３を選択する。この選択によって、複数の矢印に分岐する。
【００４２】
このようにして最初に最下行に到達したら、仮想ネットワークの構成要素のすべてがそろっているため、最下行に到達した部分ネットの組合せを用いることで、そのセルにある構成要素が資源利用要求の解となる。その構成要素を用いて仮想ネットワークを構成すれば、もっとも若い順位の部分ネットとピアリンクによって、要求された仮想ネットワークを実現できる。解に含まれる部分ネットに重複がある場合（同じ仮想ノードや仮想リンクを含む場合）、いずれかひとつの部分ネットを選ぶ。
【００４３】
以上説明したように、本発明によれば、設備提供者装置２０の割当コストの代わりに、秘密計算を用いて得られた割当コストの「順位」のみを用いて仮想ネットワーク割当を行う。このため、設備提供者装置２０は割当コストの公開を避けられ、ユーザ装置１０は割当コストをみることなくコストの小さな仮想ネットワークを実現できる。
【００４４】
副次的な効果として、設備提供者装置２０は収容可能な仮想ネットワークの領域を提示するため、収容したくない領域が割り当てられることはない。このため、非特許文献１で生じていた収容したくない領域が割り当てられることがあるという問題を解決することができる。
【００４５】
なお、本発明の装置はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【産業上の利用可能性】
【００４６】
本発明は情報通信産業に適用することができる。
【符号の説明】
【００４７】
１０：ユーザ装置
１１：部分ネット及びピアリンクＤＢ
１２：部分ネット及びピアリンク探索部
１３：復号用協調計算部
１４：資源割当計算部
２０：設備提供者装置
２０Ａ、２０Ｂ、２０Ｃ：設備提供者装置
２１：部分ネット及びピアリンク列挙部
２２：部分ネット及びピアリンクＤＢ
２３：ソート用協調計算部
２４：復号用協調計算部
２５：資源割当計算部
９０：ネットワーク
９１ａ−１、９１ａ−２、９１ｂ−１、９１ｂ−２、９１ｃ−１、９１ｃ−２、９１ｄ−１、９１ｄ−２、９１ｆ−１、９１ｆ−２、９１ｇ−１、９１ｇ−２、９１ｇ−３、９１ｈ−１、９１ｈ−２、９１ｈ−３、９１ｈ−４：物理ノード
９２ａ、９２ｂ、９２ｃ、９２ｄ、９２ｅ、９２ｆ：仮想ノード
【図１】
0006034815.tif 000002
【図２】
0006034815.tif 000003
【図３】
0006034815.tif 000004
【図４】
0006034815.tif 000005
【図５】
0006034815.tif 000006
【図６】
0006034815.tif 000007
【図７】
0006034815.tif 000008
【図８】
0006034815.tif 000009
【図９】
0006034815.tif 000010
【図１０】
0006034815.tif 000011
【図１１】
0006034815.tif 000012
【図１２】
0006034815.tif 000013
【図１３】
0006034815.tif 000014
【図１４】
0006034815.tif 000015