(57)【要約】【課題】第三者機関の助けを利用することなく、かつ互いの設備情報等を開示せず、さらに計算時間が現実的な複数設備提供者間でのネットワーク資源割当てを行う。【解決手段】複数の設備提供者の資源割当装置間で協調して割当てを行うネットワーク資源割当方法において、資源利用要求における要求ノードの各設備提供者への割振りを選択する割振選択ステップと、各設備提供者の資源割当装置が、選択された要求ノードの割振りに従って、内部資源割当てを独立に決定する内部資源割当ステップと、前記内部資源割当ステップにおいて決定された各設備提供者の内部資源割当ての結果を、各資源割当装置が協調計算を行うことにより統合するし、統合により得られた資源割当て後の所定の評価値を求める統合ステップとを備え、これらステップを要求ノードの各設備提供者への割振り毎に実行する。【選択図】図７
2014171063.tif 000002
【特許請求の範囲】
【請求項１】
それぞれがネットワーク資源を保有する複数の設備提供者の資源割当装置間で協調して、ネットワーク利用者からの資源利用要求を満たすようにネットワーク資源の割当てを行うネットワーク資源割当システムにおけるネットワーク資源割当方法であって、
ある資源割当装置がネットワーク利用者からの資源利用要求を受信すると、当該資源利用要求を他の資源割当装置に共有させるステップと、
前記ネットワーク資源割当システムにおいて、前記資源利用要求における要求ノードの各設備提供者への割振りを選択する割振選択ステップと、
各設備提供者の資源割当装置が、前記割振選択ステップにおいて選択された要求ノードの割振りに従って、内部資源割当てを独立に決定する内部資源割当ステップと、
前記内部資源割当ステップにおいて決定された各設備提供者の内部資源割当ての結果を、各資源割当装置が協調計算を行うことにより統合し、統合により得られた資源割当て後の所定の評価値を求める統合ステップと、
前記所定の評価値を良い値になるように更新しながら、前記内部資源割当ステップ、及び前記統合ステップを、前記割振選択ステップにより選択される要求ノードの各設備提供者への割振り毎に実行し、得られた評価値を出力するステップと
を備えることを特徴とするネットワーク資源割当方法。
【請求項２】
前記統合ステップは、
前記ネットワーク資源割当システムが、所定の境界条件を満たすように内部資源割当ての修正が終了した設備提供者の集合の近傍にある設備提供者のうち、所定の条件を満たす設備提供者を協調計算により探索して、探索された設備提供者の資源割当装置が、前記境界条件を満たすように内部資源割当ての修正を行う処理を、全ての設備提供者における内部資源割当ての修正が終了するまで実行する修正ステップ
を含むことを特徴とする請求項１に記載のネットワーク資源割当方法。
【請求項３】
前記統合ステップにおいて、
前記修正ステップと、
前記修正ステップが終了した後、資源割当て後の評価値を協調計算により算出し、当該評価値を良い値に更新する評価値更新ステップと、
を前記集合に加える最初の設備提供者を変えながら実行する
ことを特徴とする請求項２に記載のネットワーク資源割当方法。
【請求項４】
前記評価値は、資源割当て後のネットワークの使用料金、資源割当て後のネットワークの平均遅延、又は資源割当て後のネットワークの設備の使用率
であることを特徴とする請求項１ないし３のうちいずれか１項に記載のネットワーク資源割当方法。
【請求項５】
それぞれがネットワーク資源を保有する複数の設備提供者の資源割当装置を含むネットワーク資源割当システムであり、当該資源割当装置間で協調して、ネットワーク利用者からの資源利用要求を満たすようにネットワーク資源の割当てを行うネットワーク資源割当システムであって、
ある資源割当装置がネットワーク利用者からの資源利用要求を受信すると、当該資源利用要求を他の資源割当装置に共有させるステップと、
前記資源利用要求における要求ノードの各設備提供者への割振りを選択する割振選択ステップと、
各設備提供者の資源割当装置において、前記割振選択ステップにおいて選択された要求ノードの割振りに従って、内部資源割当てを独立に決定する内部資源割当ステップと、
前記内部資源割当ステップにおいて決定された各設備提供者の内部資源割当ての結果を、各資源割当装置が協調計算を行うことにより統合し、統合により得られた資源割当て後の所定の評価値を求める統合ステップと、
前記所定の評価値を良い値になるように更新しながら、前記内部資源割当ステップ、及び前記統合ステップを、前記割振選択ステップにより選択される要求ノードの各設備提供者への割振り毎に実行し、得られた評価値を出力するステップと
を実行することを特徴とするネットワーク資源割当システム。
【請求項６】
前記統合ステップは、
前記ネットワーク資源割当システムが、所定の境界条件を満たすように内部資源割当ての修正が終了した設備提供者の集合の近傍にある設備提供者のうち、所定の条件を満たす設備提供者を協調計算により探索して、探索された設備提供者の資源割当装置が、前記境界条件を満たすように内部資源割当ての修正を行う処理を、全ての設備提供者における内部資源割当ての修正が終了するまで実行する修正ステップ
を含むことを特徴とする請求項５に記載のネットワーク資源割当システム。
【請求項７】
前記統合ステップにおいて、
前記修正ステップと、
前記修正ステップが終了した後、資源割当て後の評価値を協調計算により算出し、当該評価値を良い値に更新する評価値更新ステップと、
を前記集合に加える最初の設備提供者を変えながら実行する
ことを特徴とする請求項６に記載のネットワーク資源割当システム。
【請求項８】
前記評価値は、資源割当て後のネットワークの使用料金、資源割当て後のネットワークの平均遅延、又は資源割当て後のネットワークの設備の使用率
であることを特徴とする請求項５ないし７のうちいずれか１項に記載のネットワーク資源割当システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の設備提供者がユーザの資源利用要求に対してその要求を満たす資源割当てを情報秘匿のまま発見する技術に関する。ここで、設備提供者とはネットワーク資源やICT資源を保有し、それらをユーザに提供するインターネットサービスプロバイダー(ISP)などのことである。また、資源割当てとは設備提供者がユーザからの仮想ネットワークなどの資源利用要求に応じて、保有する設備の中からどのネットワーク機器・ICT機器を使用し、それらをどのように接続するかを決定することである。また、情報秘匿のまま発見するとは、各設備提供者が設備情報等を互いに開示することなく資源割当てを発見することである。
【背景技術】
【０００２】
例えば非特許文献１、２、３に従来の資源割当てを行う技術が開示されている。しかし、これら従来の技術は、単一の設備保有者の管理する設備から資源割当てを発見する手法であって、複数の設備保有者の設備から資源割当てを発見することは考慮されていない。
【０００３】
また、例えば非特許文献４、５に開示されているように、異なる設備提供者が管理するネットワーク機器を接続するための技術は存在する。しかしながら、資源割当ての決定においては、まず、複数の設備提供者が管理するネットワーク機器からどれを使うべきかを決定する必要があり、上記の従来技術では不十分である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】M. Yu, Y. Yi, J. Rexford, and M. Chiang, "Rethinking virtual network embedding: substrate support for path splitting and migration," Comput. Commun. Rev., vol. 38, no. 2, pp. 17-29, Mar. 2008.
【非特許文献２】M. Chowdhury, M. Rahman, and R. Boutaba, "ViNEYard: Virtual network embedding algorithms with coordinated node and link mapping," IEEE/ACM Trans. Netw., vol. 20, no. 1, pp. 206 -219, feb. 2012.
【非特許文献３】X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, "Virtual network embedding through topology-aware node ranking," Comput. Commun. Rev., vol. 41, no. 2, pp. 38-47, Apr. 2011.
【非特許文献４】S. Dasgupta, J. de Oliveira, and J.-P. Vasseur, "Path-computationelement-based architecture for interdomain MPLS/GMPLS traffic engineering:Overview and performance," Network, IEEE, vol. 21, no. 4,pp. 38 -45, july-august 2007.
【非特許文献５】J. Vasseur, A. Ayyangar, and A. Farrel, "Inter-domain MPLS and GMPLS traffic engineering-resource reservation protocol-traffic engineering (RSVP-TE) extensions," RFC 5151, Feb. 2008.
【非特許文献６】O. Goldreich, Foundations of Cryptography, volume II, Basic Applications. Cambridge University Press, 2004.
【非特許文献７】R. Cramer, I. Damgard, "Multiparty Computation, an Introduction", in Contemporary Cryptology, Advanced courses in Mathematics CRM Barcelona 2005, pp. 41--87.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来の単一設備保有者用の資源割当て手法を用いて、複数のISPなどの設備保有者が管理する設備から資源割当てを発見することは困難である。なぜならば、従来の手法を適用するには複数の設備保有者の設備情報等(設備地理的な位置、利用可能な資源量、利用料金等)が必要であるが、通常ISPなどの設備保有者は競合関係にあり互いの設備情報等は開示しないからである。このため、従来手法をそのまま用いることは難しい。
【０００６】
また、信頼できる第三者機関に各設備保有者が各自の情報を渡し、第三者機関に従来技術を用いて資源割当てを発見してもらうという方法も困難である。なぜならば、第三者機関は設備保有者の情報を漏洩しないという信頼性の他に、資源割当ての発見に関してある特定の設備保有者に便宜をはかってはいけないという設備保有者に関する中立性を有する必要がある。このような信頼できかつ中立でありかつ資源割当てに協力する第三者機関を発見するもしくは設立することは困難である。
【０００７】
また、Multi Party Computation (MPC)（非特許文献６、７）を利用して従来の資源割当て手法を複数の設備提供者間で実行する方法も計算時間が膨大になり困難である。ここで、MPCは複数の参加者が参加して計算を行う手法のひとつで、各参加者の入力に基づく計算を各参加者の入力を開示することなく実行する手法である。一般的なMPCでは、乗算、比較等の基本的な演算ごとに参加者間での通信が発生する。このため、MPCを用いて従来手法を実行することは、上記の通信遅延が大量に発生し計算終了までに必要な時間が膨大になるため困難である。
【０００８】
本発明は上記の点に鑑みてなされたものであり、第三者機関の助けを利用することなく、かつ互いの設備情報等を開示せず、さらに計算時間が現実的な複数設備提供者間での資源割当てを行うための技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、本発明は、それぞれがネットワーク資源を保有する複数の設備提供者の資源割当装置間で協調して、ネットワーク利用者からの資源利用要求を満たすようにネットワーク資源の割当てを行うネットワーク資源割当システムにおけるネットワーク資源割当方法であって、
ある資源割当装置がネットワーク利用者からの資源利用要求を受信すると、当該資源利用要求を他の資源割当装置に共有させるステップと、
前記ネットワーク資源割当システムにおいて、前記資源利用要求における要求ノードの各設備提供者への割振りを選択する割振選択ステップと、
各設備提供者の資源割当装置が、前記割振選択ステップにおいて選択された要求ノードの割振りに従って、内部資源割当てを独立に決定する内部資源割当ステップと、
前記内部資源割当ステップにおいて決定された各設備提供者の内部資源割当ての結果を、各資源割当装置が協調計算を行うことにより統合し、統合により得られた資源割当て後の所定の評価値を求める統合ステップと、
前記所定の評価値を良い値になるように更新しながら、前記内部資源割当ステップ、及び前記統合ステップを、前記割振選択ステップにより選択される要求ノードの各設備提供者への割振り毎に実行し、得られた評価値を出力するステップとを備えることを特徴とするネットワーク資源割当方法として構成される。
【００１０】
また、前記統合ステップは、
前記ネットワーク資源割当システムが、所定の境界条件を満たすように内部資源割当ての修正が終了した設備提供者の集合の近傍にある設備提供者のうち、所定の条件を満たす設備提供者を協調計算により探索して、探索された設備提供者の資源割当装置が、前記境界条件を満たすように内部資源割当ての修正を行う処理を、全ての設備提供者における内部資源割当ての修正が終了するまで実行する修正ステップを含むようにしてもよい。
【００１１】
前記統合ステップにおいて、前記修正ステップと、前記修正ステップが終了した後、資源割当て後の評価値を協調計算により算出し、当該評価値を良い値に更新する評価値更新ステップと、を前記集合に加える最初の設備提供者を変えながら実行するようにしてもよい。
【００１２】
前記評価値は、例えば、資源割当て後のネットワークの使用料金、資源割当て後のネットワークの平均遅延、又は資源割当て後のネットワークの設備の使用率である。
【００１３】
また、本発明は、それぞれがネットワーク資源を保有する複数の設備提供者の資源割当装置を含むネットワーク資源割当システムであり、前述した各ステップを実行するネットワーク資源割当システムとして構成してもよい。
【発明の効果】
【００１４】
本発明によれば、第三者機関の助けを利用することなく、かつ互いの設備情報等を開示せず、さらに計算時間が現実的な複数設備提供者間での資源割当てを行うための技術を提供することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】ネットワーク利用要求の１例を示す図である。
【図２】設備提供者のネットワーク及びネットワーク利用要求に対応する資源割当て例を示す図である。
【図３】本発明の実施の形態の概要を示す図である。に係るシステム構成例である。
【図４】本発明の実施の形態に係るシステム構成例である。
【図５】本発明の実施の形態に係る資源割当装置の機能構成図である。
【図６】協調計算の処理を示す図である。
【図７】協調計算の処理を示すフローチャートである。
【図８】境界ノードの例１を示す図である。
【図９】境界ノードの例２を示す図である。
【図１０】補助ノード追加の例（１／４）を示す図である。
【図１１】補助ノード追加の例（２／４）を示す図である。
【図１２】補助ノード追加の例（３／４）を示す図である。
【図１３】補助ノード追加の例（４／４）を示す図である。
【図１４】境界条件の例（１／３）を示す図である。
【図１５】境界条件の例（２／３）を示す図である。
【図１６】境界条件の例（３／３）を示す図である。
【図１７】内部資源割当ての統合手順を示す図である。
【図１８】内部資源割当ての統合手順を示すフローチャートである。
【図１９】内部資源割当ての統合手順を示すフローチャートの他の例である。
【図２０】計算時間の削減の効果を示す図である。
【図２１】既存手法と同程度の使用料金の達成を実現していることを示す図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１７】
（本実施の形態において対象とする問題例）
まず、本実施の形態において対象とする問題例を説明する。
【００１８】
本実施の形態では設備提供者が管理するストレージサーバーや計算サーバーのようなネットワーク機器をノード、それらノードを結ぶ回線等をリンクと呼ぶ。また、ネットワーク利用者等の資源利用要求の要素も同様にノード、リンクと呼ぶ。また、設備提供者の数をn（nは1以上の整数）とする。
【００１９】
本実施の形態は、例えば以下のように記述される資源割当て問題へ適用可能である。入力として設備提供者らのネットワークトポロジーである無向グラフG=(V,E)、と設備提供者の各ノードの余剰CPU資源量cV・使用料金 fV・地理的位置 lV、各リンクの余剰帯域cV、とネットワーク利用要求のトポロジーである無向グラフ H=(W,F)、と利用要求ノードの必要CPU資源量dW・許容可能な設置範囲AW、各リンクの必要帯域 dFを受け取る。そして、出力は利用要求を満たす資源割当てのなかで使用料金が最小のものとする。ここで、資源割当てとはノード割当てMNとリンク割当て MLの組でMN はWからVへの単射な写像で、 ML は E×F から区間 [0,1] への写像とする。また、要求を満たす資源割当て(MN, ML)とは次の４つの条件を満たす資源割当てのことである。
●∀w∈W,  lV (MN(w))∈AW(w)
●∀w∈W, dW(w)≦cV(MN(w))
●∀e∈E,Σf∈FdF(f) ML(e,f)≦cE(e)
●任意の(s,t)=f∈F についてML(e,f) がMN(s) とMN(t) を結ぶパスになっている。
また、資源割当て(MN, ML)の使用料金とは
【００２０】
【数１】
2014171063.tif 000003
(式1)
である。ただし、各設備提供者が管理するノードの余剰CPU資源量cV、地理的位置lV、使用料金uV、リンクの余剰帯域cE、使用料金uEは他の設備提供者には非開示のまま処理を進めるとする。
【００２１】
図１はネットワーク利用要求の１例を示す図である。図１では、利用要求のトポロジー（無向グラフ）と各ノード、リンクの必要CPU資源量、帯域が図示されている。
【００２２】
図２の実線は設備提供者のネットワークの1例である。図２の実線ではネットワークのトポロジーと各ノード、リンクの余剰CPU資源量、余剰帯域が図示されている。図２において、図１のネットワーク利用要求に対応する資源割当て例が点線で示されている。図２の資源割当てでは要求ノードaが設備提供者のノードCに、要求ノードbが設備提供者のノードIに、要求ノードcが設備提供者のノードEに、要求ノードdが設備提供者のノードGに割当てられている。また、要求リンク(a,b)は設備提供者のリンク{(C,A), (A,B), (B,I)} に、要求リンク (a,c) が設備提供者のリンク{(C,E)}に、要求リンク (c,d)が設備提供者のリンク {(E,G)}に割当てられている。
【００２３】
この問題を情報非開示のまま実行するには、従来の単一の資源割当て手法、例えば線型計画緩和法（非特許文献２）や貪欲法（非特許文献１）の各演算（加算、乗算、比較等）をMPCを用いて実行すればよい。ここで線形計画法は、入力として設備提供者のネットワークを表わす無向グラフ、各ノードの余剰CPU資源量・使用料金・地理的位置、各リンクの余剰帯域・使用料金とネットワーク利用要求を表わす無向グラフ、各ノードの必要CPU資源量・許容可能な設置場所、各リンクの必要資帯域を受け取り、利用要求を満たす資源割当てを出力する。線型計画緩和法は、まず資源割当て問題を(1)対象とする問題例で述べたように混合整数計画問題として定式化し、次に離散変数を連続変数へと緩和することで線型計画問題ととらえ線型計画法によって解く。そして、線型計画問題の解を確率的に離散化することでノードの割当を得る。リンクの割当ては先と同様に問題を線型計画問題として定式化し、線形計画法を用いて解くことによって得る。
【００２４】
また貪欲法は、入力として設備提供者のネットワークを表わす無向グラフ、各ノードの余剰CPU資源量・使用料金・地理的位置、各リンクの余剰帯域・使用料金とネットワーク利用要求を表わす無向グラフ、各ノードの必要CPU資源量・許容可能な設置場所、各リンクの必要資帯域を受け取り、利用要求を満たす資源割当てを出力する。貪欲法はまず設備提供者が保有する各ノードをそのノードの余剰CPU量やそのノードに接続するリンクの余剰帯域によって順序付けを行う。そして、同様の手順でネットワーク利用要求の各ノードをそのノード必要CPU資源量やそのノードに接続するリンクの必要帯域によって順序付けを行う。その後、ネットワーク利用要求のノードを必要CPU資源量・帯域が大きいものから、設備提供者のノードの余剰CPU量・帯域が大きいものへ割当ることでノードの割当を得る。リンクの割当は上と同様に線型計画法を用いて得る。
【００２５】
しかしながら、この従来手法とMPCの単純な組合せはMPCの通信遅延により計算コストが大きいという問題を抱える。以下で説明する本実施の形態の手法では、この問題が解決される。
【００２６】
（本実施の形態の概要）
図３を参照して、本発明の実施の形態における処理の流れの概要を説明する。まず、ネットワーク利用者が資源利用要求をある設備提供者に提示する（ステップ１）。次に、利用要求を受け取った設備提供者（図３では、設備提供者１）は資源利用要求を他の設備提供者に送信し、共有する（ステップ２）。そして、利用要求を共有した設備提供者らは協調して資源割当ての計算を開始する（ステップ３）。この協調計算の一部は設備提供者らの間でMPCを通して実行され、残りは各設備提供者内でその設備提供者が独立に実行する。この協調計算の詳細は後述する。最後に、協調計算終了後にその結果、すなわち、利用要求に沿った設備を提供可能かどうかと提供可能な場合は資源割当ての使用料金を、利用要求を受け取った設備提供者がネットワーク利用者に提示する（ステップ４）。
【００２７】
（システム構成例）
図４に、図３で示したような処理を実現するネットワーク資源割当システムの構成例を示す。図４に示すように、本実施の形態では、各設備提供者の資源割当装置（図４の例では、３つの資源割当装置１０、２０、３０）が備えられ、ネットワークを介して互いに通信可能である。例えば、図３の設備提供者１が資源割当装置１０を保有し、設備提供者２が資源割当装置２０を保有し、設備提供者３が資源割当装置３０を保有する。また、ネットワーク利用者は、ネットワーク利用者端末１００から資源利用要求を資源割当装置１０に送信し、資源割当装置１０から提供可能可否、使用料金の出力をネットワーク利用者端末１００を介して受けるものとする。また、各資源割当装置は、自身の設備提供者の資源割当てに必要なネットワークに関する情報（トポロジ、余剰CPU量・帯域、料金等）はデータベース等に保持するが、他の設備提供者のネットワークに関する情報は知ることができないものとする。
【００２８】
図５は、各資源割当装置の機能構成例を示す図である。各資源割当装置は同じ構成を有するものとする。図５に示すように、資源割当装置は、独立に資源割当ての計算を行う資源割当計算部１１と、MPCによる協調計算を行うための協調計算部１２と、後述する要求ノードの設備提供者への割振りの選択や、資源割当ての統合等の制御を、協調計算部１２を利用して行う資源割当制御部１３とを備える。
【００２９】
各資源割当装置は、１つの装置（つまり、コンピュータ）から構成されてもよいし、複数のコンピュータから構成されてもよい。本実施の形態における資源割当装置は、１つ又は複数のコンピュータに、本実施の形態の処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、資源割当装置の各部が有する機能は、当該資源割当装置を構成するコンピュータに内蔵されるＣＰＵやメモリ、ハードディスクなどのハードウェア資源を用いて、各部で実施される処理に対応するプログラムを実行することによって実現することが可能である。上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【００３０】
（システムの動作概要）
図６は、本実施の形態において設備提供者らの資源割当装置が行う協調計算の処理内容を示している。図６に示すように、この協調計算において、設備提供者らの資源割当装置は資源割当ての決定を以下の3つの手順(a)、(b)、(c)を順に繰り返すことによって行う。(a) 要求ノードの設備提供者への割振りの選択、(b) 各設備提供者が行う手順(a)で選択された割振りに対応する資源割当ての決定、(c) 手順(b)で決定した設備提供者内部での資源割当ての統合。
【００３１】
図６に示した処理をフローチャートで表現した図７に沿って本実施の形態における協調計算の全体の手順を説明する。
【００３２】
前述したように、資源利用要求を受信した資源割当装置は、各設備提供者の資源割当装置に利用要求を共有させる。
【００３３】
その後、設備提供者らの各資源割当装置の資源割当制御部１３はメモリ等の記憶手段に格納される一時変数t, x, y をそれぞれ、0, 0, Mに初期化する（ステップ１１）。ここで、Mは十分大きな正の整数であるとする。また、これらの変数は資源割当ての計算中にMPC（つまり、各資源割当装置の協調計算部１２の機能）を通して更新されるとする。後述するように、xは内部資源割当ての番号（設備提供者の番号）が入り、yには、資源割当て後の評価値（以下で説明する例では使用料金）が入る。
【００３４】
次に、設備提供者らの資源割当装置の資源割当制御部１３はある要求ノードの設備提供者への割振りを選択する(上記手順(a))。割振りは、ある設備提供者の資源割当装置が行ってもよいし、予め定めたルールで（同じ結果になるように）、各設備提供者（各資源割当装置）が行ってもよい。
【００３５】
本実施の形態では、複数ある割振り候補は順序付けされていて、資源割当制御部１３の記憶手段に格納されており、その中から i 番目の割振りを選択したとする（ステップ１２）。そして、各設備提供者の資源割当装置は要求ノードの割振りに従い資源割当てを決定する（ステップ１３）(上記手順(b))。
【００３６】
次に、設備提供者らの各資源割当装置は先程の各自の資源割当て結果、すなわち、設備が提供可能かどうかという真偽値と可能な場合はその使用料金を共有する。この共有は各協調計算部１２によりMPCを用いて行なう。そして、MPCにより、設備提供者ら（各資源割当制御部１３）は各自の資源割当てをひとつの資源割当てに統合し、その結果を一時変数x', y'に保存する（ステップ１４）(上記手順(c))。次に、一時変数t, x, yを以下のように更新する（ステップ１５、１６）。つまり、より小さい使用料金（＝良い評価値）に更新されるようにする。
【００３７】
【数２】
2014171063.tif 000004
その後、設備提供者らの資源割当装置は別の要求ノードの設備提供者への割振りに対して上記と同様の手順を繰り返す（ステップ１７）。
【００３８】
全てのノード割振り候補に対する操作が終了した場合、設備提供者らは一時変数t,x,yの内容を開示し、資源割当てを再度計算する（ステップ１８）。つまり、最後に得られたt,x,yを用いて、同様の手順にてMCPを使用して資源割当てを計算する。その後、利用要求を受け取った設備提供者が結果をユーザに提示する。以下、順次、上記３つの手順(a), (b), (c)についてより詳しく説明する。
【００３９】
（（ａ）要求ノードの設備提供者への割振りの選択）
まず、手順（ａ）の要求ノードの設備提供者への割振りの選択について詳細に説明する。
要求ノードの設備提供者への割振りとは、要求された各ノードに対してどの設備提供者が設備を提供するかを指定することである。ここで、設備提供者の数はnであるから、ある要求ノードはn 通りの割振り先が存在する。よって、要求ノードの数をW とすると、可能な要求ノードの割振りの数は nW通りである。このnWの中から資源割当ての発見に用いる候補Aを選択し、下記の(b), (c) の操作を行う。この候補は複数の設備提供者間で事前に選出の方法を決定しておく。例えば、nW通りの全ての割振りを候補とするなどである。
【００４０】
候補または、各設備提供者から希望のノード割振り候補を集めそこから構成するという方法もある。候補Aの選び方は資源割当ての性能、すなわち、使用料金の低さに関係する。つまり、より多くの候補を選択すれば、より低い使用料金の資源割当てを得られる可能性がある。
【００４１】
（(b) 各設備提供者内での資源割当ての決定）
次に、手順(b)である各設備提供者内での資源割当ての決定について説明する。指定されたノード割振りに対して、各設備提供者の資源割当装置は、資源割当計算部１１において、独立に資源割当てを計算する。以降、この資源割当てを内部資源割当てと呼ぶ。
【００４２】
各設備提供者の資源割当装置における資源割当計算部１１は内部資源割当て計算のために補助ノードを追加し、単一の設備提供者用の資源割当て手法を用いて内部資源割当てを計算する。その後、協調計算部１２により、MPCを用いて内部資源割当て計算の結果を他の設備提供者らの資源割当装置と共有する（設備が提供可能かどうかの真偽値と、可能な場合はその使用料金）。
【００４３】
上記の補助ノードについて説明する。各設備提供者の資源割当装置は、割振られた要求ノードとそれらを含む要求リンクに対して、各自で内部資源割当てを、単一の設備提供者用の資源割当て手法を用いて計算する。しかしながら、要求リンクの端点である2つの要求ノードが必ずしも同一設備提供者に割り振られているとは限らないので、そのまま単一設備提供者用の資源割当て手法を用いることはできない。そこで、各設備提供者はこの不具合を解消するために、補助ノードを要求ノードと提供者側ノードに追加する。具体的には、要求ノードには、要求ノードの境界ノードらを加え、提供者側ノードにも同様に、提供者側ノードの境界ノードを加える。
【００４４】
ここで、あるノード集合Vに対する境界ノードとは、例えば図８、図９に示すように、ノード集合V に属するノードとあるリンクで接続されているノードであり、かつそのノード集合 V には属さないノードのことである。また、要求ノードの境界ノードは設備提供者側ノードの境界ノードにのみ割当て可能となるような制約条件を追加する。このように、要求ノードと設備提供者側ノードの両方にそれぞれの境界ノードを追加し、対応する制約条件を追加することで、要求リンクの両端点がこの設備提供者に属すようになる。
【００４５】
ここで、補助ノード追加の一例を図１０〜図１３に示す。ここでは、図１０(a)に示すようにユーザ要求ネットワークがあり、図１０(b)に示すように設備提供者ネットワークがあり、図１１に示すように、１番目の設備提供者に要求ノードが割振られたものとする。このとき、図１２に示すとおりに、要求ノードと設備提供者側ノードの両方にそれぞれの境界ノードを追加する。そして、要求ノードの境界ノードは設備提供者側ノードの境界ノードにのみ割当て可能となるような制約条件により、図１３に示すようにノードの割当てが行われる。
【００４６】
各設備提供者は補助ノード追加後、単一の設備提供者用の資源割当て手法を用いて資源割当てを計算する。単一の資源割当て手法には線形計画緩和法（非特許文献２）や貪欲法（非特許文献１）等がある。
【００４７】
この資源割当ては各設備提供者の資源割当装置が各々、独立して実行するので各設備提供者が用いる手法が異なってもよい。また、各設備提供者の資源割当装置が独立して資源割当てを計算しているので、各設備提供者の資源割当ては他の設備提供者の資源割当てと適合しない、すなわち、両端点が異なる設備提供者に割り振られた要求リンクに対応する設備提供者側のリンク割当てが適切な資源割当てになっていない可能性がある。この不一致は手順(c)で解決される。また、各設備提供者の資源割当装置が割り振られた要求ノードに対応する資源割当てを計算する際に、資源割当てを発見することができない可能性もある。そのような場合、設備提供者らはその要求ノードの設備提供者への割振りに対する以降の計算を中止し、次の要求ノードの設備提供者への割振りに対して計算を開始する。
【００４８】
（（ｃ）各設備提供者での資源割当ての統合）
次に、手順(c)である各設備提供者での資源割当ての統合について説明する。設備提供者らの資源割当装置は手順(b)終了後に、MPCにより、各設備提供者の資源割当装置が計算したn個の内部資源割当てをひとつの資源割当てに統合する。その際に、統合された資源割当てが境界条件に合致し、かつ低い使用料金になるように資源割当てを統合する。ここで、境界条件に合致するとは、その両端点が異なる設備提供者に割り振られた要求リンクに対応する設備提供者ら側のリンク割当てが、その要求リンクの両端点の要求ノードに割当てられた設備提供者側の2つのノードを結ぶパスもしくは複数のパスになっている状態と定義する。
【００４９】
境界条件の例を図１４〜図１６に示す。図１４(a)、(b)に示すように、ユーザ要求ネットワークと設備提供者ネットワークがあり、図示のとおりに各設備提供者に要求ノードが割振られているとする。このとき、境界条件に合致しない資源割当てが行われる例を図１５に示す。図１５(b)(c)に示すように、１番目の設備提供者と２番目の設備提供者において資源割当てが行われた場合、(d)に示すように、要求リンク(a，d)への設備提供者側のリンク割当てがDとIを結ぶパスになっていないため、境界条件に合致しない。
【００５０】
境界条件に合致する資源割当てが行われる例を図１６に示す。図１６(b)(c)に示すように、１番目の設備提供者と２番目の設備提供者において資源割当てが行われた場合、(d)に示すように、要求リンク(a，d)への設備提供者側のリンク割当てがDとHを結ぶパスになっているため、境界条件に合致する。
【００５１】
手順(c)は上記2つの目的を達成、すなわち境界条件に合致し、かつ低い使用料金であるような資源割当てに統合することが目的である。
【００５２】
前者の目的は内部資源割当てをひとつずつ修正しながら統合していくことで達成する。後者の目的は異なる統合の仕方で内部資源割当てを統合することで複数の資源割当てを生成し、その中から最小の使用料金をもつ資源割当てを選択することで達成する。
【００５３】
図１７に、手順(c)の内部資源割当ての統合手順を示す。図１７に示す手順をフローチャートで表した図１８を参照して内部資源割当ての統合手順について説明する。
【００５４】
この手順では、まず、設備提供者らの資源割当装置の資源割当制御部１３において、一時変数x', y'をそれぞれ0, Mに初期化する（ステップ２１）。ここで、Mは十分大きな正の整数であるとする。また、これらの変数は資源割当ての計算中にMPC（協調計算部１２）を通して更新されるとする。
【００５５】
次に、設備提供者らの資源割当装置はひとつの設備提供者（資源割当装置）を選ぶ、ここではi 番目の設備提供者を選んだとする（ステップ２２）。そして、一時変数Tを{i} とする（ステップ２３）。ここで、T は内部の資源割当ての修正が終了した設備提供者の集合を表す。
【００５６】
次に、i 番目の設備提供者の資源割当装置はその近傍 N({i}) に境界条件を伝える。ここで、設備提供者の集合の近傍とは、それらの設備提供者にリンクで接続している設備提供者と定義する。つまり、当該設備提供者のネットワークのノードにリンクで接続しているノードを有する設備提供者である。次に設備提供者らは次段落の操作を T={1,…,n} となるまで繰り返す（ステップ２５〜ステップ２９）。
【００５７】
設備提供者らの資源割当装置は、MPCを用いて、Tの近傍 N(T)に含まれる設備提供者の中からその内部資源割当ての使用料金が最大の設備提供者をひとつ選ぶ（ステップ２６）。ここでは、その設備提供者は j 番目の設備提供者であるとする。j 番目の設備提供者の資源割当装置は境界条件に合致するように内部資源割当てを修正する（ステップ２７）。この修正は境界条件にそった制約条件を追加し、再度内部資源割当てを計算することで達成される。再計算後、j 番目の設備提供者の資源割当装置はその近傍N({j})に境界条件を伝える（ステップ２８）。そして、設備提供者らの各資源割当装置は T←T∪{j} とT を更新する（ステップ２９）。つまり、Tにjが存在しなければ、jを加える。
【００５８】
T={1,…,n}となると（ステップ２５のYes）、設備提供者らはn 個全ての内部資源割当てをひとつの資源割当てに統合した状態になっている。そこで、設備提供者らの資源割当装置はMPCを用いて資源割当てに必要な使用料金を計算しそれを一時変数 y'' に保存する（ステップ３０）。なお、使用料金は、前述した式１を用いて算出できる。そして、一時変数x',y'を以下のように更新する（ステップ３１、３２）。
【００５９】
【数３】
2014171063.tif 000005
すなわち、前回の使用料金y'よりも今回の使用料金y''が小さければ、今回の使用料金y''をy'とする。
【００６０】
次に設備提供者らは別の設備提供者、ここでは i' 番目の設備提供者を選び、T={i'} として上記の手順を繰り返す。この操作を全ての設備提供者に対して実行する。すなわち、 i'=1,…,n に対して繰り返す。その結果、y'にはこの手順の間に見つかった最小の資源割当て使用料金（最良の評価値）が含まれ、x' にはその資源割当てを統合した際に基となった内部資源割当ての番号（ステップ２２で選択された設備提供者の番号）が含まれている。これら2つの変数は図６、図７にあるように、別の一時変数t,x,y の更新に使用される。
【００６１】
＜別の統合手順＞
上記の図１７、図１８に示した手順のほか、図１７の６行目、すなわち、図１８のステップ２６を以下のいずれかに変更する手順でも統合が可能である。
【００６２】
●  j <- N(T) から内部資源割当ての使用料金が最小の設備提供者を探索
●  j <- N(T) からTとN(T)の間の要求リンクのうち最大の必要帯域をもつ要求リンクで接続された設備提供者を探索
●  j <- N(T) からTとN(T)の間の要求リンクのうち最小の必要帯域をもつ要求リンクで接続された設備提供者を探索
もしくは、あらかじめ m 種類の{1,..,n}に対する置換｛σ1,…,σm｝、すなわち、{1,..,n} から {1,..,n}の写像のうち全単射を決定しておき、図１９のような手順で統合することもできる。図１９の処理では、ステップ４２に示されるループの処理の部分で、k毎に各i（1,..,n）についての前述したループ処理がなされ、y'には当該手順の間に見つかった最小の資源割当て使用料金が含まれることになる。各ステップでの処理は、図１８に示した処理と同様である。
【００６３】
＜使用料金以外の基準＞
資源割当ての使用料金を表現する式1を別の式に変更することで、資源割当ての探索に使用料金以外の基準を使用することが可能である。
【００６４】
各ノード、各リンクで発生する平均遅延を最小にするような資源割当てを探索するには式１を
【００６５】
【数４】
2014171063.tif 000006
とする。ここでtVは各設備提供者ノードでの遅延、tEは各設備提供者リンクで遅延である。また、ネットワーク利用者の希望上限額Uを新たな入力として加え、さらに次の制約を加える。
【００６６】
【数５】
2014171063.tif 000007
（式２）
また、資源割当て後の設備の使用率（使用資源量 / 資源容量）を最小化するには、各設備提供者のノードCPU資源容量をpV、リンクの帯域容量をpEとする。さらに、ノード割当てMNに対応する新たな変数xv,w∈{0,1}をMN(w)=v ⇔xv,w=0と定義して（式２）に加え、次の制約条件を加える
【００６７】
【数６】
2014171063.tif 000008
ここで、R は新たに導入した補助変数である。そして、式1を R におきかえ、Rを最小化するような資源割当てを探せば良い。
【００６８】
なお、基準（評価値）として、上記のように使用料金、平均遅延、設備利用率を例示したが、基準がこれらに限られず、他の基準を用いてもよい。例えば最大遅延、遅延揺らぎ幅、電力消費、冗長度等の基準及び、基準の内の複数の基準にそれぞれ優先順位や重み付けを乗じて合成した基準を用いてもよい。いずれの場合でも、処理としては、図６〜図１９を参照して説明した処理において、「使用料金」が、当該基準に置き換わるだけで、探索の処理内容は、どのような基準においても基本的に同様である。
【００６９】
（実施の形態のまとめ、効果）
冒頭で説明したように、複数設備提供者間で資源割当てを求める際に、従来の技術は、複数の設備提供者間に対して適用することを想定しておらず、必要な情報を利用することができない。また、MPCは通常の計算に比べ膨大な計算コストを必要とするので、MPCを用いて従来技術を実行することは計算時間が膨大になるので困難である。また、第三者機関を利用することも信頼できかつ全ての設備提供者に対して中立であるという第三者機関が必要となり困難である。
【００７０】
そこで、本実施の形態では部分的にMPCを利用しつつ、各設備提供者でも独立に計算を実行することとした。その結果、本実施の形態によって、設備提供者の非開示情報を秘匿にしたまま、必要な計算時間を大幅に削減するとともに、全情報が開示された状態での従来手法と少なくとも同程度の使用料金の資源割当てを得ることが可能になった。
【００７１】
より詳細には、本実施の形態によれば、少なくとも以下の３つの効果を奏する。
【００７２】
(d) 各設備提供者の情報の秘匿性。
【００７３】
(e) 資源割当てを計算する際の計算時間の削減。
【００７４】
(f) 全情報が開示されている状態での既存手法と少なくとも同程度の使用料金の資源割当て達成。
【００７５】
以下、それぞれの効果について説明する。
【００７６】
(d) 情報の秘匿性
本実施の形態に係る技術では各要求ノードの設備提供者への割振りについて、内部資源割当ての使用料金の順序のみ、が設備提供者らに開示され、その他の設備提供者の情報、ノード・リンクの使用料金や、ノード・リンクの物理的な位置、余剰資源量といった情報を開示することなく資源割当ての計算を複数の設備提供者間で実行することができる。実際、本実施の形態に係る技術では各設備提供者が内部資源割当てを計算する際(手順(b))には、各設備提供者が独立に計算を実行するので、情報開示の必要はない。また、内部の資源割当てを統合する際も、開示する必要がある情報は内部資源割当ての使用料金の順序だけである。したがって、本発明手法によって、各設備提供者らの情報の秘匿性を保ったまま、複数の設備提供者間で資源割当てを計算することが可能になる。
【００７７】
(e) 計算時間の削減
本実施の形態の技術によって、複数設備提供者間で情報の秘匿性を保ったまま資源割当てを計算する際の計算コストを従来技術に比べ削減するができる。これは本実施の形態の技術が手順(b)のようなMPCが不要な手順を導入し、必要なMPC回数を削減しているためである。
【００７８】
ここでは計算時間を比較する従来技術として、MPCを用いて全探索を実行する手法(Full search)、MPCを用いて貪欲法を実行する方法(Greedy)、MPCを用いて線形計画緩和法を実行する方法(LP relax)を考える。また、ここでは、設備提供者のノードには使用料金、余剰CPU資源量、地理的位置が設定されているとする。また、設備提供者のリンクにも使用料金、余剰帯域が設定されているとする。同様に資源要求のノードにも必要CPU資源量、地理的位置が設定され、リンクにも必要帯域が設定されているとする。さらに手順(a)では要求ノードの設備提供者への割振りの候補としてnW 通りの全ての割振りを用いる。また、手順(b)において、各設備提供者は内部資源割当ての計算に従来技術である線形緩和法を用いる。このとき、設備提供者のひとつあたりのノード数を20、リンク数を40、要求ノード数を10、リンク数を20とした。また、加算・乗算・比較等の基礎的MPC演算1回に10ms、通常の加算・乗算・比較等の基礎的計算1回に1ns必要として、それぞれ手法の必要な計算時間を算出すると図２０のようになる。
【００７９】
図２０から分かるように、本実施の形態の技術は従来の技術に比べ計算時間が大幅に削減されている。特に、設備提供者の数が8以下の場合必要な計算時間が少なくとも1/100以下になっている。このように、本実施の形態の技術によって複数管理者間の資源割当てに必要な計算時間を大幅に削減することが可能となる。
【００８０】
(f) 既存手法と同程度の使用料金の達成
本実施の形態の技術によって、全情報が開示された状態での従来技術と同程度の使用料金の資源割当てを得ることが可能になる。(e)と同じ状況で資源割当て問題を無作為に生成し、各手法で資源割当てを求めその正規化使用料金の平均値を算出した。ここで、資源割当ての正規化使用料金とは資源割当ての使用料金を最小使用料金で割ったものである。したがって全探索を行い、常に最小資料料金の資源割当てを出力する手法であるFull  search の正規化使用料金は常に1である。また、実験に際して、以下のようにパラメータを設定した。各設備提供者のノード数は20、リンク数は20から60までの一様分布から抽出、設備提供者の数nを2とした。要求ノード数をWとして、要求リンクの数はW から3W までの一様分布から抽出した。要求ノードの数Wは3から9に変化させ、各W について資源割当て問題を100 個生成し正規化使用料金の計算をした。
【００８１】
図２１にその結果を示す。図２１から本実施の形態の技術が少なくとも全情報が開示されている状態での従来技術と少なくとも同程度の使用料金の資源割当てを達成していることが確認できる。これはMPCを通して従来手法を実行して得られた資源割当ては、全情報が開示されている状態で従来法を実行して得た資源割当てと同一だからである。
【００８２】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００８３】
１０〜３０  資源割当装置
１００  ネットワーク利用者端末
１１  資源割当計算部
１２  資源割当制御部
１３  協調計算部
【図１】
2014171063.tif 000009
【図２】
2014171063.tif 000010
【図３】
2014171063.tif 000011
【図４】
2014171063.tif 000012
【図５】
2014171063.tif 000013
【図６】
2014171063.tif 000014
【図７】
2014171063.tif 000015
【図８】
2014171063.tif 000016
【図９】
2014171063.tif 000017
【図１０】
2014171063.tif 000018
【図１１】
2014171063.tif 000019
【図１２】
2014171063.tif 000020
【図１３】
2014171063.tif 000021
【図１４】
2014171063.tif 000022
【図１５】
2014171063.tif 000023
【図１６】
2014171063.tif 000024
【図１７】
2014171063.tif 000025
【図１８】
2014171063.tif 000026
【図１９】
2014171063.tif 000027
【図２０】
2014171063.tif 000028
【図２１】
2014171063.tif 000029