(57)【特許請求の範囲】
【請求項１】
受け付けた複数リソースの配備要求に関連したリソースであって、装置または該装置間の接続に関する複数のリソースに対するリソース条件を含むリソース条件情報を取得する条件取得部と、
管理対象の情報処理システムにおける、装置および該装置間の接続に関するリソースについての情報を含むシステム構成情報を参照し、前記リソース条件を満たすリソース各々の存在割合を含む存在割合情報を算出する算出部と、
前記存在割合情報、および、前記配備要求における装置間の接続関係に基づき、前記リソース条件を満たすリソースを順次選択することで、前記複数リソースの配信要求に対応した複数のリソースを検索する検索部と、
を備え、
前記検索部は、前記存在割合の最も低いリソースを最初に選択し、直近に選択した該リソースに複数の未選択のリソースが接続している場合には、該未選択のリソースのうち最も前記存在割合の小さいリソースを選択する
ことを特徴とするリソース検索装置。
【請求項２】
前記検索部は、前記装置間の接続関係に基づき、前記最初に選択したリソースからたどることにより前記リソース条件を満たすリソースを順次選択する、
ことを特徴とする請求項１に記載のリソース検索装置。
【請求項３】
前記算出部は、前記システム構成情報から取得した前記装置に対する、前記リソース条件を満たす該装置の存在割合を算出し、
前記検索部は、前記存在割合の最も低い装置を最初に選択し、該最初に選択した装置から前記接続を辿って未選択の前記装置を順次選択することで、前記複数リソースの配信要求に対応した複数のリソースを検索する
ことを特徴とする請求項１に記載のリソース検索装置。
【請求項４】
前記検索部は、直近に選択した該装置に複数の未選択の装置が接続している場合には、該未選択の装置のうち最も前記存在割合の小さい装置を選択する
ことを特徴とする請求項３に記載のリソース検索装置。
【請求項５】
コンピュータに、
受け付けた複数リソースの配備要求に関連した、装置または該装置間の接続に関するリソースに対するリソース条件を含むリソース条件情報を取得し、
管理対象の情報処理システムにおける、装置および該装置間の接続に関するリソースについての情報を含むシステム構成情報を参照し、前記リソース条件を満たすリソース各々の存在割合を含む存在割合情報を算出し、
前記存在割合情報、および、前記配備要求における装置間の接続関係に基づき、前記リソース条件を満たすリソースを順次選択することで、前記複数リソースの配信要求に対応した複数のリソースを検索する処理を実行させ、
前記順次選択する場合、前記存在割合の最も低いリソースを最初に選択し、直近に選択した該リソースに複数の未選択のリソースが接続している場合には、該未選択のリソースのうち最も前記存在割合の小さいリソースを選択する
ことを特徴とするリソース検索プログラム。
【請求項６】
前記順次選択では、前記装置間の接続関係に基づき、前記最初に選択したリソースからたどり前記リソース条件を満たすリソースを順次選択する、
処理を実行させる請求項５に記載のリソース検索プログラム。
【請求項７】
前記算出では、前記システム構成情報から取得した前記装置に対する、前記リソース条件を満たす該装置の存在割合を算出し、
前記検索では、前記存在割合の最も低い装置を最初に選択し、該最初に選択した装置から前記接続を辿って未選択の前記装置を順次選択することで、前記複数リソースの配信要求に対応した複数のリソースを検索する
処理を実行させる請求項５に記載のリソース検索プログラム。
【請求項８】
前記順次選択では、直近に選択した該装置に複数の未選択の装置が接続している場合には、該未選択の装置のうち最も前記存在割合の小さい装置を選択する
処理を実行させる請求項７に記載のリソース検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、情報処理システムのリソースを検索する技術に関する。
【背景技術】
【０００２】
クラウドに代表される大規模データセンターにおいて、利用者からのサービス配備要求に対してどの利用可能なリソースを割り当てるかが考慮される。このようなリソースの割り当ては、単体のデータセンターの場合であっても及び複数のデータセンターに跨る場合であっても考慮される。【０００３】
従来は、仮想マシン（VM：Virtual Machine）単位でのリソース配備が主流であった。つまり、「どのような性能、どのようなソフトウェアが搭載されたVMがX個必要」というリソース要求に対して、当該要求を満たすサーバ（群）を探し出してリソースを割り当てていた。【０００４】
しかし、近年では、サービス単位でのリソース配備の要求が高まっている。つまり、サービスを構成するサーバ、ストレージなどの（仮想的な）機器だけでなく、機器間を結ぶネットワークのトポロジも考慮して、リソースを割り当てる。このようなサービス単位の配備技術の１つとして、資源要求者による相関のある資源群の要求に対して、相互に作用して動作するための制約を満たした資源選択を可能にするシステムがある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−０９４８３４号公報
【特許文献２】特開２０１１−８１８２７号公報
【非特許文献】
【０００６】
【非特許文献１】Luigi P. Cordella, Pasquale Foggia, C.S., Vento, M.: “A (sub)graph isomorphism algorithm for matching large graphs”，IEEE Transactions on Pattern Analysis and Machine Intelligence 16(10) (October 2004) 1367-1372.
【非特許文献２】Roberto Battiti, Franco Mascia, “An Algorithm Portfolio for the Sub-graph Isomorphism Problem”, Lecture Notes in Computer Science, Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, Volume 4638/2007 Pages106-120, August 22, 2007.
【非特許文献３】YIN-TANG DAI, SHI-YONG ZHANG, “A FAST LABELED GRAPH MATCHING ALGORITHM BASED ON EDGE MATCHING AND GUIDED BY SEARCH ROUTE”, Proceedings of the 2009 International Conference on Wavelet Analysis and Pattern Recognition, Baoding, 12-15 July 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記技術の場合、資源群の要求に対して、相関関係を含めて要件を満たす資源群を広域に検索するシステムであり、検索に時間がかかるおそれがある。
１つの側面では、本発明は、情報処理システムからユーザの要求する条件を満たすリソースを有するサービスを効率的に検索するリソース検索技術を提供する。
【課題を解決するための手段】
【０００８】
本実施形態の一面にかかるリソース検索装置は、条件取得部、構成情報取得部、算出部、順次選択部、検索部を含む。条件取得部は、サービスの該リソースに関するリソース条件を含むサービスリソース条件情報を取得する。サービスは、装置に関するリソース及び装置間の接続に関するリソースを要素として含む情報によって定義される。構成情報取得部は、情報処理システムの構成情報であるシステム構成情報を取得する。システム構成情報は、複数の装置が接続されている情報処理システムにおける、装置に関するリソース及び装置間の接続に関するリソースを要素として含む情報によって定義される。算出部は、システム構成情報から取得した要素に対する、リソース条件を満たす要素の存在確率を算出する。順次選択部は、存在確率の最も低い要素を最初に選択する。順次選択部は、サービスを形成する装置間の接続関係により表されるサービスの接続形態を示すサービス接続形態情報において、最初に選択した要素から接続を辿って未選択の要素を順次選択する。検索部は、構成情報に含まれる装置間の接続関係により表される情報処理システムの接続形態を示すシステム接続形態情報から、要素の選択順に、リソース条件を満たすサービスの要素を検索する。検索部は、存在割合の最も低いリソースを最初に選択し、直近に選択したリソースに複数の未選択のリソースが接続している場合には、未選択のリソースのうち最も存在割合の小さいリソースを選択する。
【発明の効果】
【０００９】
本実施形態の一面によれば、情報処理システムからユーザの要求する条件を満たすリソースを有するサービスを効率的に検索することができる。
【図面の簡単な説明】
【００１０】
【図１】本実施形態におけるリソース管理装置の一例を示す。
【図２】本実施形態における全体のシステム構成例を示す。
【図３】本実施形態におけるリソース管理装置の構成の一実施例を示す。
【図４】本実施形態における端末から送られてくるリソース配備要求に含まれるサービス構成情報の記述例を示す。
【図５】本実施形態における構成管理DBにより管理される、管理対象ICTリソース（インフラ側）の利用可能なリソースについてのインフラ構成情報の記述例を示す。
【図６】本実施形態におけるユーザの要求するサービス接続形態情報の一例を示す。
【図７】図６の各ノードに付与されたリソース要件例を示す。
【図８】本実施形態における割り当て可能リソースのインフラ構成情報例を示す。
【図９】本実施形態におけるインフラを構成するノードの割り当て可能リソースがサービス接続形態情報を構成するノードのリソース要件に合致するかを説明するための図である。
【図１０】本実施形態における各ノードの稀少性を保持する稀少性テーブルの一例を示す。
【図１１】本実施形態における検索順リストの作成手順を説明する図である。
【図１２】本実施形態におけるリソース検索処理フローの一例を示す。
【図１３】検索順設定処理（Ｓ２）の詳細フローの一例を示す。
【図１４】検索処理（Ｓ４）の詳細フローの一例を示す。
【図１５】本実施形態（変形例）における各ノードの稀少性を保持する稀少性テーブルの一例を示す。
【図１６】本実施形態（変形例）における検索順リストの作成手順を説明する図である。
【図１７】本実施形態（変形例）における検索順設定処理（Ｓ２）の詳細フローの一例を示す。
【図１８】本実施形態を適用したコンピュータのハードウェア環境の構成ブロック図の一例を示す。
【発明を実施するための形態】
【００１１】
機器間を結ぶネットワークのトポロジを考慮したリソース配備を行うための技術の１つとしては、グラフマッチング技術（グラフ同形性判定問題）がある。このグラフマッチング技術は、各機器をノードと見立て、機器間を結ぶネットワークをエッジと見立て、データセンター側のリソース及び利用者が要求するサービスのリソースそれぞれをグラフに置き換えてマッチングする。その際、データセンター側の利用可能リソースがサービス側の要求を満たしているかどうかがチェックされる。これにより、サービス全体として要件を満たしたリソース配備が可能となる。
【００１２】
グラフマッチングアルゴリズムには様々なアルゴリズムが存在する。そのうちエッジベースのグラフマッチングアルゴリズムは、他アルゴリズムよりも省メモリかつ高速性に優れている。このエッジベースのグラフマッチングアルゴリズムでは、ユーザの要求するサービスのシステム構成を展開してエッジを連ねた線形リストが作成される。利用者が要求するサービスのリソースは、線形リストの先頭のエッジから順次、データセンター側の利用可能リソースとマッチングされる。グラフマッチングアルゴリズムを適用することで、サービス要件を確実に満たしつつ、ある程度高速なリソース配備が実現できる。
【００１３】
また、上記グラフマッチングアルゴリズムでは、線形リストを作成する際のノード・エッジ選択順序については深く考慮されていなかった。例えば、線形リストは、任意のノードから幅優先あるいは深さ優先で作成されていた。この方法を用いた場合、マッチするノードが見つからないと、線形リスト中の１つ以上前のノードに戻ってマッチング処理をやり直すバックトラックが高頻度に発生し、検索に時間がかかってしまう。
【００１４】
そこで、本実施形態の一面では、図１に示すように、情報処理システムからユーザの要求する条件を満たすリソースを有するサービスを効率的に検索するリソース検索装置を提供する。
【００１５】
図１は、本実施形態におけるリソース管理装置の一例を示す。リソース管理装置１は、条件取得部２、構成情報取得部３、算出部４、順次選択部５、検索部６を含む。
【００１６】
条件取得部２は、サービスのリソースに関するリソース条件を含むサービスリソース条件情報を取得する。サービスは、装置に関するリソース及び装置間の接続に関するリソースを要素として含む情報によって定義される。条件取得部２の一例として、要求取得部２１がある。
【００１７】
構成情報取得部３は、情報処理システムの構成情報であるシステム構成情報を取得する。システム構成情報は、複数の装置が接続されている情報処理システムにおける、装置に関するリソース及び装置間の接続に関するリソースを要素として含む情報によって定義される。構成情報取得部３の一例として、稀少性算出部２３、リソース管理部２４がある。
【００１８】
算出部４は、システム構成情報から取得した要素に対する、リソース条件を満たす要素の存在確率を算出する。算出部４の一例として、稀少性算出部２３がある。
【００１９】
順次選択部５は、存在確率の最も低い要素を最初に選択する。順次選択部５は、サービス接続形態情報において、最初に選択した要素から接続を辿って未選択の記要素を順次選択する。サービス接続形態情報は、サービスを形成する装置間の接続関係により表されるサービスの接続形態を示す情報である。ここで、順次選択部５は、最初に選択した要素から接続を辿って順次未選択の要素を選択する場合において、直近に選択した要素に複数の未選択の要素が接続している場合には、未選択の要素のうち最も存在確率の小さい要素を選択してもよい。順次選択部５の一例として、順序設定部２２がある。
【００２０】
検索部６は、システム接続形態情報から、要素の選択順に、リソース条件を満たす前記サービスの要素を検索する。システム接続形態情報は、構成情報に含まれる装置間の接続関係により表される情報処理システムの接続形態を示す情報である。検索部６の一例として、割当決定部２５がある。
【００２１】
より具体的には、算出部４は、システム構成情報から取得した装置に対する、リソース条件を満たす装置の存在確率を算出する。順次選択部５は、存在確率の最も低い装置を最初に選択し、サービス接続形態情報において、最初に選択した装置から接続を辿って未選択の前記装置を順次選択し、選択した順に該装置が現れるように接続を順次並べる。検索部６は、システム接続形態情報から、接続の並べ順に、リソース条件を満たすサービス接続形態を構成する装置及び接続を検索する。ここで、順次選択部５は、最初に選択した装置から接続を辿って順次未選択の装置を選択する場合において、直近に選択した装置に複数の未選択の装置が接続している場合には、順次選択部５は、次の処理を実行してもよい。すなわち、順次選択部５は、未選択の装置のうち最も存在確率の小さい装置を選択し、選択した順に装置が現れるように接続を順次並べるようにしてもよい。
【００２２】
このように構成することにより、情報処理システムからユーザの要求する条件を満たすリソースを有するサービスを効率的に検索することができる。
【００２３】
以下では、本実施形態の詳細を説明する。
【００２４】
図２は、本実施形態における全体のシステム構成例を示す。当該システムは、端末装置１０、リソース管理装置１１、サービス配備管理装置１２、構成管理データベース（DB）１３、管理対象ICT（Information and Communication Technology）リソース１５、ネットワーク２０を含む。端末装置１０、リソース管理装置１１、サービス配備管理装置１２、構成管理DB１３、管理対象ICTリソース１５は、ネットワーク２０により接続されている。
【００２５】
管理対象ICTリソース１５は、サーバ１６、ネットワーク１７、ストレージ１８、ソフトウェア１９等を含むインフラのICTリソースである。以下では、管理対象ICTリソース１５をインフラとも呼ぶ。管理対象ICTリソースを構成する各機器は、「ノード」と呼ばれる。これらの各機器（ノード）を結ぶネットワークは、「エッジ」と呼ばれる。ここで、サーバ１６には、アプリケーションサーバ（AP）、DBサーバ、WEBサーバ等の様々なサーバを含む。ネットワーク１７とは、ネットワーク機器、ネットワークの通信帯域幅等のネットワーク環境を含む。
【００２６】
端末装置（以下、「端末」という）１０は、ユーザにより操作されるコンピュータである。端末１０は、ユーザの操作により、管理対象ICTリソース１５からユーザが要求するリソースに関する要件（リソース要件）を満たすリソースを検索するための要求情報（サービス配備要求）を出力する。ここで、ユーザが要求するリソース要件を満たすリソース（サーバ１６、ネットワーク１７、ストレージ１８、ソフトウェア１９等の組み合わせ）をサービスという。
【００２７】
構成管理DB１３は、管理対象ICTリソース１５（インフラ）の構成についてのインフラ構成情報１４を含むデータベースである。
【００２８】
リソース管理装置１１は、端末装置１０から送信されたサービス配備要求を受信すると、構成管理DB１３を用いて管理対象ICTリソース１５のうちユーザが設定したリソース要件を満たすリソースを検索し、リソースの配備先を決定する。リソース管理装置１１は、その決定したリソースの配備先にリソースを配備（割り当てる）ように配備指示情報をサービス配備管理装置１２へ送信する。
【００２９】
サービス配備管理装置１２は、リソース管理装置１１からの配備指示情報を受信すると、その配備指示情報に基づいて管理対象ICTリソース１５にユーザの要求するリソースを割り当てる。
【００３０】
なお、リソース管理装置１１、サービス配備管理装置１２のいずれも、ネットワーク２０を介して管理対象のICTリソース１５を制御可能である。
【００３１】
図３は、本実施形態におけるリソース管理装置の構成の一実施例を示す。リソース管理装置１１は、要求取得部２１、順序設定部２２、稀少性算出部２３、リソース管理部２４、割当決定部２５、配備指示部２６を含む。
【００３２】
要求取得部２１は、端末装置１０から送信されたサービス配備要求を取得する。
【００３３】
稀少性算出部２３は、構成管理DB１３から利用可能なインフラ構成情報１４を取得する。稀少性算出部２３は、利用可能なインフラ構成情報１４とサービス配備要求に含まれるリソース要求とを用いて、ユーザの要求を満たすサービスを構成する各ノードの稀少性を算出する。
【００３４】
ノードの稀少性とは、管理対象ICTリソース（インフラ側のリソース）１５に含まれるノードのうち、ユーザの要求するリソース要件を満たすノードの存在確率の小ささをいう。ここで、稀少性を示す指標について説明する。稀少性を示す指標としては、例えば以下のようなものを採用することができる。
【００３５】
（第1の指標）システム全体における適合ノード数（割合）：稀少性算出部２３は、管理対象ICTリソース１５に含まれる全ノードからユーザの要求するリソース要件を満たすノード数を、サービスを構成するノード毎に算出する。稀少性算出部２３は、その算出された値（あるいは割合）が小さいものを稀少性が高いとすることができる。
【００３６】
（第２の指標）無作為抽出による適合ノード数概算値：稀少性算出部２３は、管理対象ICTリソース１５からノードを一定数無作為に抽出する。それから、稀少性算出部２３は、その抽出したノードのうちリソース要件を満たすノードがどれだけあるかを、サービスを構成するノード毎に算出する。稀少性算出部２３は、その算出された値（あるいは割合）が小さいものを稀少性が高いとすることができる。
【００３７】
（第３の指標）エントロピーに基づく計算：稀少性算出部２３は、管理対象ICTリソース１５からリソース要件を満たすノードの散らばり具合（エントロピー）を、サービスを構成するノード毎に算出する。稀少性算出部２３は、算出されたエントロピーが小さいほど稀少性が高いとすることができる。
【００３８】
このようにして、稀少性算出部２３は、ユーザから要求されたサービスを構成するICTリソースの各要素（ノード）の稀少性を算出することができる。
【００３９】
順序設定部２２は、割当決定部２５において検索する際に用いる検索順を、算出された稀少性に基づいて設定する。具体的には、順序設定部２２は、サービス配備要求から、ノードとエッジとの関係により表されるサービスの接続形態を示す情報（サービス接続形態情報）を展開する。順序設定部２２は、算出された稀少性を用いて、サービス接続形態情報内のノードを順に選択し、選択した順にノードが出現するようにエッジを並べ、その並べた順にエッジを検索順リストに登録する。このとき、順序設定部２２は、最も稀少と判断したノードを最初に選択する。順序設定部２２は、後続のノードの選択順については、任意に設定してもよいし、稀少性の高さに基づいて順に設定しても良い。
【００４０】
リソース管理部２４は、構成管理DB１３から管理対象ICTリソース１５のインフラ構成情報１４を取得する。リソース管理部２４は、取得したインフラ構成情報１４を用いて、ノードとエッジとの関係により表されるインフラの接続形態を示す情報（インフラ接続形態情報）を作成する。
【００４１】
割当決定部２５は、インフラ接続形態情報と、サービス接続形態情報の要素をＳ２で設定した検索順に照合することにより、インフラ接続形態情報からサービス接続形態情報を検索する。サービス接続形態情報が検索された場合、割当決定部２５は、その検索されたサービス接続形態情報をリソースの配備先（割り当て先）として決定する。すなわち、割当決定部２５は、検索順リストへのエッジの登録順に、インフラ側のエッジが、リソース要件を満たすか及び、リソース要件を満たすエッジの両端にあるノードが、検索順リストに登録したエッジの両端にあるノードのリソース条件を満たすかを照合する。これにより、割当決定部２５は、照合したインフラ側から、サービスを構成するノード及びエッジ配備先を検出する。
【００４２】
配備指示部２６は、サービス配備管理装置１２に対して、決定されたリソースの配備先にユーザより要求されたサービスの配備を指示する。
【００４３】
図４は、本実施形態における端末から送られてくるリソース配備要求に含まれるサービス構成情報の記述例を示す。図４は、XML（eXtensible Markup Language）書式を用いたサービス構成情報の記述例を示している。サービス構成情報の記述例では、ノードとエッジで対象サービスの構造を規定している。ノード、エッジの要件は、それぞれに付与した属性で表現される。
【００４４】
図４の記述例には、/graph/templates以下に出現するテンプレート３１、/graph/topology 以下に出現する要求リソース情報３２が含まれる。要求リソース情報３２内のnode定義３３、edge定義３４では、サービスに含まれるノード、エッジの要件が記述されている。node定義３３、edge定義３４それぞれは、id（識別子）、name（名前）、type（型名）、template（雛形）等の属性を含む。ここでtemplateとは対象ノード／エッジの雛形であり、template属性で示されたIDを持つテンプレート定義（/graph/templates/template 要素以下）に記述されたtype（型名）、attribute（要件）を引き継ぐことを意味する。また、attributeは対象ノード／エッジとして配備先リソースに要求される要件（条件）のことである。
【００４５】
図５は、本実施形態における構成管理DBにより管理される、管理対象ICTリソース（インフラ側）の利用可能なリソースについてのインフラ構成情報の記述例を示す。図５は、XML（eXtensible Markup Language）書式を用いたリソースのインフラ構成情報の記述例を示している。図５の記述例には、/graph/templates 以下に出現するテンプレート４１、/graph/topology 以下に出現する利用可能リソース情報４２が含まれる。
【００４６】
図５のデータ構造は、図４のサービス構成情報の記述例で説明したデータ構造と同様である。ただし、attributeの意味が異なる。図４のサービス接続形態情報の記述例では、attributeは要求するリソース要件を表したが、図５では、attributeは、利用可能なリソースのリソース要件を表す。
【００４７】
次に、本実施形態の内容を図６〜図１１を用いて説明する。
【００４８】
図６は、本実施形態におけるユーザの要求するサービス接続形態情報の一例を示す。サービス接続形態情報は、図４のサービス構成情報をメモリ上に展開したものである。図６では説明の便宜のため、サービス接続形態情報は、図示化されている。図６に示すサービス接続形態情報の構成要素（ノード）には、ファイヤーウォール装置（FW）、サーバロードバランサー装置（SLB）、アプリケーションサーバ１（AP1）、アプリケーションサーバ２（AP2）、データベース（DB）が含まれる。また、サービス接続形態情報のエッジには、エッジe1〜e5が含まれる。
【００４９】
エッジe1は、ノードFWとノードSLBを接続するネットワークである。エッジe2は、ノードSLBとAP1を接続するネットワークである。エッジe3は、ノードSLBとノードAP2を接続するネットワークである。エッジe4は、ノードAP1とノードDBを接続するネットワークである。エッジe5は、AP2とDBを接続するネットワークである。
【００５０】
図７は、図６の各ノードに付与されたリソース要件例を示す。リソース要件は、実際には図４の記述により与えられるが、図７では説明の便宜のため、図４の要求リソース情報３２のノード定義３３のattribute部分を抽出してテーブルに表す。
【００５１】
例えば、ノードFWのリソース要求は、CPU性能：１．０、メモリ容量：２ギガバイト（ＧＢ）、ディスク容量：４０ギガバイト（ＧＢ）である。例えば、ノードAP2のリソース要求は、CPU性能：２．５、メモリ容量：４ギガバイト（ＧＢ）、ディスク容量：４０ギガバイト（ＧＢ）、地域（設置場所）：関西である。
【００５２】
図８は、本実施形態における割り当て可能リソースのインフラ構成情報例を示す。割り当て可能リソースのインフラ構成情報１４は、実際には図５の記述により与えられるが、図８では説明の便宜のため、図５の利用可能リソース情報４２のノード定義のattribute部分を抽出してテーブルに表す。図８の表の項目「地域」は、ノードの設置場所を示す。図８の表の項目「割当可能リソース」は、ノードに対して割り当て可能なリソース（CPU性能、メモリ容量、ディスク容量）を示す。
【００５３】
図９は、本実施形態におけるインフラを構成するノードの割り当て可能リソースがサービス接続形態情報を構成するノードのリソース要件に合致するかを説明するための図である。図９では、図８に含まれる割り当て可能リソースの構成情報のうち、ノードe-sv1，e-sv3，m-sv1，w-sv1に着目して説明する。
【００５４】
ノードe-sv1，e-sv3，m-sv1（図８）とサービス接続形態情報上のノード（図７）とを比較すると、ノードe-sv1，e-sv3，m-sv1（地域：関東）は、地域情報についてサービス接続形態情報上のノードAP2の要件（場所：関西）を満たしていない。また、ノードe-sv1，e-sv3，m-sv1（図８）とサービス接続形態情報内のノード（図７）とを比較すると、ノードe-sv3，m-sv1は、サービス接続形態情報内のノードDBの要件（CPU性能：4.0、ディスク容量:300GB）を満たしていない。それ以外のノードFW，SLB，AP1については、ここで挙げたe-sv1，e-sv3，m-sv1，w-sv1がリソース要件を満たしている。このように全てのノードについて判定した結果、例えば、全ノード1,000台中、サービス接続形態情報上の各ノードは以下の台数だけ要件を満たしたとする。
【００５５】
FW:500台, LB:500台, AP1:350台, AP2:200台, DB:100台
【００５６】
なお、ここではすべてのノードについて調べた場合を示したが、一定数の標本を無作為に抽出して（ランダムサンプリング）、各ノードの要件を満たす台数の概算値を用いても良い。一例として、以下の式（１）による算出される標本数をランダムサンプリングしてもよい。
【００５７】
n = N / {(E / Z)2 {(N - 1) / P(1 - P)} + 1}      （１）
（n：必要な標本数、N：母集団の大きさ、E：最大誤差、Z：信頼率に対応する正規分布点、P：予測される母比率（予測困難な場合は、0.5）
式（１）によれば、信頼水準95%の場合には、100万ノードでも高々400程度の標本数でよい。
【００５８】
図１０は、本実施形態における各ノードの稀少性を保持する稀少性テーブルの一例を示す。ここでは、上記第１の指標として説明したように、サービス接続形態情報内のノード毎に、全ノード数のうちリソース要件を満たすノード数の割合（適合確率）を、稀少性を表す指標として用いている。稀少性テーブル５０から、適合確率の最も低いノードDBが最も稀少性が高いことがわかる。稀少性テーブル５０は、リソース管理装置１１が有するメモリに格納される。
【００５９】
なお、適合確率の最も低いノードが複数ある場合には、そのうちのいずれかのノードを選択してもよいし、それらのノードの後続のノードの適合確率の低さに応じて、いずれかのノードを選択してもよい。
【００６０】
図１１は、本実施形態における検索順リストの作成手順を説明する図である。図１１（Ａ）に示すように、図６のサービス接続形態情報を構成するノードのうち、図１０で算出した稀少性の最も高いノードDBを先頭ノードとして決定する。
【００６１】
次に、決定した先頭ノードからエッジを辿って後続ノードを選択する。次ノードとして選択可能な複数の未選択ノードがある場合には、任意のノードを選択する。選択したノードに後続の未選択ノードが存在しない場合には、１つ前のノードに戻って、未選択のノードを選択する。
【００６２】
このようにして、決定した先頭ノードからエッジを辿って後続ノードを選出していくと、図１１（Ｂ）に示すノードツリーのルートノードから末端ノードまでのノードの並びの並びで表される線形リストのうち、いずれかの線形リストが生成される。ここでは、例えば、DB→AP2→SLB→FW→AP1で示される線形リストが生成されたとする。本実施形態において用いるグラフマッチングアルゴリズムは、エッジをベースにした線形リストを用いるので、上記で生成したノードベースの線形リストをエッジベースに変更する。すると、図１１（Ｃ）に示す線形リスト（検索順リスト６０）：e5 → e3 → e1 → e2 → e4が得られる。
【００６３】
図１２は、本実施形態におけるリソース検索処理フローの一例を示す。要求取得部２１は、端末１０からサービス配備要求を取得する（Ｓ１）。
【００６４】
順序設定部２２は、後述する検索順の設定を行う。具体的には、順序設定部２２は、取得したサービス配備要求から、サービスを構成するノードと、ノード間を接続するエッジを読み出す。それから、順序設定部２２は、ノードとエッジとの関係により表されるサービスの接続形態を示す情報（サービス接続形態情報）をメモリ上に展開する。順序設定部２２は、稀少性算出部２３を用いて、サービス接続形態情報に含まれるエッジを所定の順で設定した検索順リスト６０を生成する（Ｓ２）。Ｓ２については、図１３で詳述する。
【００６５】
リソース管理部２４は、構成管理DB１３から管理対象ICTリソース１５のインフラ構成情報１４を取得する。リソース管理部２４は、取得したインフラ構成情報１４から、インフラを構成するノードと、ノード間を接続するエッジを読み出す。それからリソース管理部２４は、ノードとエッジとの関係により表されるインフラの接続形態を示す情報（インフラ接続形態情報）をメモリ上に展開する（Ｓ３）。
【００６６】
割当決定部２５は、インフラ接続形態情報と、サービス接続形態情報の要素をＳ２で設定した検索順に照合することにより、インフラ接続形態情報からサービス接続形態情報を検索する。サービス接続形態情報が検索された場合、割当決定部２５は、その検索されたサービス接続形態情報をリソースの配備先（割り当て先）として決定する（Ｓ４）。Ｓ４については、図１４で詳述する。
【００６７】
リソースの配備先が決定された場合（Ｓ５で「ＹＥＳ」）、配備指示部２６は、サービス配備管理装置１２に対して、決定したリソースの配備先にユーザより要求されたサービスの配備を指示する（Ｓ６）。サービス配備管理装置１２は、そのサービス配備指示に基づいて、その配備先にサービスを配備する。
【００６８】
Ｓ４において配備先が決定されなかった場合（Ｓ５で「ＮＯ」）、割当決定部２５は、サービス接続形態情報に含まれる各ノードの稀少性情報（図１０）を端末１０に通知する（Ｓ７）。なお、配備先が決定されなかった場合は、ユーザは、通知された稀少性情報を見ることで、各ノードの制限を緩めて再度配備リクエストを発行するなどの措置を取ることができる。
【００６９】
図１３は、検索順設定処理（Ｓ２）の詳細フローの一例を示す。稀少性算出部２３は、図６〜図１０を用いて説明したように、サービス接続形態情報を構成する各ノードについて稀少性を算出する（Ｓ２１）。稀少性算出部２３は、算出した各ノードの稀少性を、稀少性テーブル５０に格納する。
【００７０】
順序設定部２２は、図１１で説明したように、算出された稀少性の値から、稀少性の最も高いノードを選択する（Ｓ２２）。順序設定部２２は、選択したノードをメモリに先頭ノードとして格納する。
【００７１】
次に、順序設定部２２は、サービス接続形態情報に含まれる全てのノードの選択が完了したかどうかを判定する（Ｓ２３）。
【００７２】
未選択のノードがある場合（Ｓ２３で「ＮＯ」）、順序設定部２２は、次ノード候補（直近に選択したノードとエッジで繋がっていて未選択のノード）が存在するかどうかを判定する（Ｓ２４）。次ノード候補が１以上存在する場合（Ｓ２４で「ＹＥＳ」）、順序設定部２２は、任意のノードを次ノードとして選定し、選定したノードをメモリに格納する（Ｓ２５）。その後、Ｓ２３に処理が戻る。
【００７３】
次ノード候補が存在しない場合には、順序設定部２２は、さらにもう１つ前の選択済みノードに戻って（Ｓ２６）、Ｓ２４の処理を行う。
なお、Ｓ２２及びＳ２５においてノードを順次選定しているが、選定されたノードは、メモリ上に、先頭ノードから選択順に格納される。
【００７４】
すべてのノードの選択が完了した場合、順序設定部２２は、その選択したノードの選択順から、ノード間を接続するエッジについての線形リスト（検索順リスト６０）を作成する（Ｓ２７）。検索順リスト６０は、図１１（Ｃ）で説明したように、選択した順にノードが出現するようにエッジを並べることにより作成される。
【００７５】
図１４は、検索処理（Ｓ４）の詳細フローの一例を示す。割当決定部２５は、Ｓ２で作成した検索順リスト６０から先頭エッジを読み出す（Ｓ４１）。
割当決定部２５は、読み出したエッジと、インフラ接続形態情報内のエッジ（対象エッジ）とのマッチングを行う（Ｓ４２）。具体的には、割当決定部２５は、サービス配備要求から、読み出したエッジについてのリソース要件を取得する。割当決定部２５は、インフラ接続形態情報から、読み出したエッジのリソース要件を満たすエッジを抽出する。
【００７６】
Ｓ４２において、読み出したエッジと、対象エッジとがマッチしない場合（Ｓ４２で「ＮＯ」）、割当決定部２５は、インフラ接続形態情報内に他に候補となるエッジがあるかを判定する。インフラ接続形態情報内に他に候補となるエッジがあれば（Ｓ４４で「ＹＥＳ」）、割当決定部２５は、その候補となるエッジと、読み出したエッジとのマッチングを行う。Ｓ４４において候補となるエッジがなければ（Ｓ４４で「ＮＯ」）、本フローは終了する。
【００７７】
Ｓ４２において、読み出したエッジと、対象エッジとがマッチする場合（Ｓ４２で「ＹＥＳ」）、割当決定部２５は、次の処理を行う。すなわち、割当決定部２５は、インフラ接続形態情報内のマッチした対象エッジの両端のノードと、読み出したエッジの両端にあるサービス接続形態情報内のノードとのマッチングを行う（Ｓ４３）。具体的には、割当決定部２５は、サービス配備要求から、読み出したエッジの両端にあるサービス接続形態情報内のノードのリソース要件を取得する。割当決定部２５は、インフラ接続形態情報内の対象エッジの両端にある対象ノードが、そのリソース要件を満たすかを判定する。
【００７８】
Ｓ４３において、インフラ接続形態情報内の対象エッジの両端にある対象ノードがリソース要件を満たさない場合（Ｓ４３で「ＮＯ」）、割当決定部２５は、Ｓ４４の処理を行う。Ｓ４３において、インフラ接続形態情報内の対象エッジの両端にある対象ノードがリソース要件を満たす場合（Ｓ４３で「ＹＥＳ」）、割当決定部２５は、検索順リスト６０に次のエッジが存在するか判定する（Ｓ４５）。
【００７９】
検索順リスト６０に次のエッジが存在すれば（Ｓ４５で「ＹＥＳ」）、割当決定部２５は、検索順リスト６０からそのエッジを読み出し（Ｓ４６）、Ｓ４２の処理を行う。検索順リスト６０の末尾のエッジの処理が完了するまで、Ｓ４２〜Ｓ４５の処理が繰り返される。
【００８０】
検索順リスト６０の末尾のエッジの処理が完了すると（Ｓ４５で「ＮＯ」）、割当決定部２５は、マッチしたノードをサービスの配備先として決定する（Ｓ４７）。
【００８１】
本実施形態によれば、インフラ接続形態情報からサービス接続形態情報を検索する場合、サービス接続形態情報の稀少性の最も高いから検索することにより、バックトラックの可能性を下げることができる。すなわち、効率的な検索が可能になるのは次の理由による。バックトラックが発生しないに越したことはないが、バックトラックが発生するならば、検索の早い段階でかつバックトラック発生直前に検索した要素までしか戻らない方が効率がよい。また。遍在するノード群の中の任意のノードの近傍に、稀少なノードが存在する確率よりも、稀少なノード群の中の任意のノードの近傍に遍在するノードが存在する確率の方が高い。このことから、稀少なノードから順次検索していく方が、バックトラックが少なくて済む。その結果、ユーザによるサービス配備要求に対して、管理対象リソース（インフラ）から、リソース要求を満たすリソース（ノード及びエッジ）を検索する際の検索時間を短縮することができる。
【００８２】
次に本実施形態の変形例について説明する。上述した実施形態では、ノードベースの線形リストの作成に際して、最も稀少性の高いノードを先頭ノードとし、後続ノードを先頭ノードからエッジを辿ることができることを条件に任意に順次選出した。それに対して、変形例では、ノードベースの線形リストの作成に際して、最も稀少性の高いノードを先頭ノードとし、後続ノードを先頭ノードからエッジを辿ることができることを条件に、より希少性の高いノードを順次選出する。
【００８３】
図１５は、本実施形態（変形例）における各ノードの稀少性を保持する稀少性テーブルの一例を示す。図１５の稀少性テーブル５０ａは、図１０の稀少性テーブル５０に、「稀少性順位」の項目を追加したテーブルである。「稀少性順位」は、適応確率の小さい順（稀少性の高い順）に、番号を採番した順位である。
【００８４】
図１６は、本実施形態（変形例）における検索順リストの作成手順を説明する図である。図１６（Ａ）に示すように、図６のサービス接続形態情報内のノードに、稀少性テーブル５０ａの稀少性順位を当てはめる。稀少性順位が最も高いノードDBが線形リストの先頭ノードとなる。
【００８５】
ここで、ノードDBを基点とした場合の線形リストの全組み合わせをツリーで表現すると、図１６（Ｂ）のようになる。このツリーのルートノードから末端ノードに向かって、稀少性が高いノードを優先して選択する。ノードDBに接続しているノードAP1，AP2のうち稀少性が高いノードはAP2なので、AP2を選択する。AP2に接続しているノードはSLBなので、SLBを選択する。ノードSLBに接続しているノードAP1，FWのうち稀少性が高いノードはAP1なので、AP1を選択する。図１６（Ａ）において、ノードAP1 の先には未選択のノードは存在しないので、１つ前のノードSLBに戻って、ノードSLBに接続しているノードのうち未選択のノードFWを選択する。これにより、DB →AP2 → SLB →AP1 →FWという順が選択される。
【００８６】
このように、先頭ノードからエッジを辿って順次未選択のノードを選択する場合において、直近に選択したノードに複数の未選択のノードが接続している場合には、未選択のノードのうち最も稀少性の高いノードが選択される。未選択のノードのうち最も稀少性の高いノードが複数あれば、そのうちのいずれかのノードが選択されてもよいし、それらのノードの後続のノードの希少性の高さに応じて、いずれかのノードが選択されてもよい。
【００８７】
本実施形態において用いるグラフマッチングアルゴリズムは、エッジをベースにした線形リストを用いるので、上記で生成したノードベースの線形リストをエッジベースに変更する。すると、図１１（Ｃ） に示す線形リスト（検索順リスト６０ａ）：e5 → e3 → e2 → e4 → e1が求まる。
【００８８】
図１７は、本実施形態（変形例）における検索順設定処理（Ｓ２）の詳細フローの一例を示す。図１７のフローは、図１３のフローのＳ２５の処理をＳ２５ａの処理に置換したものである。
【００８９】
Ｓ２５ａでは、順序設定部２２は、次候補（直近に選択したノードとエッジで繋がっていて未選択のノード）の中で最も稀少性の高いものを次ノードとして選択し、選択したノードをメモリに格納する。その後、Ｓ２３に処理が戻る。Ｓ２５ａ以外の処理については、図１３と同様なので、その説明を省略する。
【００９０】
本実施形態（変形例）によれば、インフラ接続形態情報からサービス接続形態情報を検索する場合、サービス接続形態情報の稀少性の最も高いから、稀少性に基づいて設定した検索順で検索することにより、バックトラックの可能性をより下げることができる。これにより、上記実施形態よりも、バックトラックの可能性をより下げることができる。その結果、ユーザによるサービス配備要求に対して、管理対象リソース（インフラ）から、リソース要求を満たすリソース（ノード及びエッジ）を検索する際の検索時間をより短縮することができる。
【００９１】
図１８は、本実施形態を適用したコンピュータのハードウェア環境の構成ブロック図の一例を示す。コンピュータ７０は、本実施形態の処理を行うプログラムを読み込むことにより、リソース管理装置１１として機能する。
【００９２】
コンピュータ７０は、出力Ｉ／Ｆ７１、ＣＰＵ７２、ＲＯＭ７３、通信Ｉ／Ｆ７４、入力Ｉ／Ｆ７５、ＲＡＭ７６、記憶装置７７、読み取り装置７８、バス７９を含む。コンピュータ７０は、出力機器８１、及び入力機器８２と接続可能である。
【００９３】
ここで、ＣＰＵは、中央演算装置を示す。ＲＯＭは、リードオンリメモリを示す。ＲＡＭは、ランダムアクセスメモリを示す。Ｉ／Ｆは、インターフェースを示す。バス７９には、出力Ｉ／Ｆ７１、ＣＰＵ７２、ＲＯＭ７３、通信Ｉ／Ｆ７４、入力Ｉ／Ｆ７５、ＲＡＭ７６、記憶装置７７、読み取り装置７８が接続されている。読み取り装置７８は、可搬型記録媒体を読み出す装置である。出力機器８１は、出力Ｉ／Ｆ７１に接続されている。入力機器８２は、入力Ｉ／Ｆ７５に接続されている。
【００９４】
記憶装置７７としては、ハードディスクドライブ、フラッシュメモリ装置、磁気ディスク装置など様々な形式の記憶装置を使用することができる。
【００９５】
記憶装置７７またはＲＯＭ７３には、例えば、本実施形態で説明した処理を実現するプログラムが格納されている。ＲＡＭ７６には、ノードについての線形リスト、エッジについての線形リスト（検索順リスト）が格納される。
【００９６】
ＣＰＵ７２は、記憶装置７７等に格納した本実施形態で説明した処理を実現するプログラムを読み出し、当該プログラムを実行する。具体的には、ＣＰＵ７２は、当該プログラムを実行することにより、要求取得部２１、順序設定部２２、稀少性算出部２３、リソース管理部２４、割当決定部２５、配備指示部２６として機能する。
【００９７】
本実施形態で説明した処理を実現するプログラムは、プログラム提供者側から通信ネットワーク８０、および通信Ｉ／Ｆ７４を介して、例えば記憶装置７７に格納してもよい。また、本実施形態で説明した処理を実現するプログラムは、市販され、流通している可搬型記憶媒体に格納されていてもよい。この場合、この可搬型記憶媒体は読み取り装置７８にセットされて、ＣＰＵ７２によってそのプログラムが読み出されて、実行されてもよい。可搬型記憶媒体としてはＣＤ−ＲＯＭ、フレキシブルディスク、光ディスク、光磁気ディスク、ＩＣ（integrated circuit）カード、ＵＳＢ（Universal Serial Bus）メモリ装置など様々な形式の記憶媒体を使用することができる。このような記憶媒体に格納されたプログラムが読み取り装置７８によって読み取られる。
【００９８】
また、入力機器８２には、キーボード、マウス、電子カメラ、ウェブカメラ、マイク、スキャナ、センサ、タブレット、タッチパネルなどを用いることが可能である。また、出力機器８１には、ディスプレイ、プリンタ、スピーカなどを用いることが可能である。また、ネットワーク８０は、インターネット、ＬＡＮ、ＷＡＮ、専用線、有線、無線等の通信網であってよい。
【００９９】
なお、本実施形態は、以上に述べた実施の形態に限定されるものではなく、本実施形態の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。
【符号の説明】
【０１００】
１      リソース管理装置
２      条件取得部
３      構成情報取得部
４      算出部
５      順次選択部
６      検索部
１０    端末装置
１１    リソース管理装置
１２    サービス配備管理装置
１３    構成管理DB
１４    インフラ構成情報
１５    管理対象ICTリソース
１６    サーバ
１７    ネットワーク
１８    ストレージ
１９    ソフトウェア
２０    ネットワーク
２１    要求取得部
２２    順序設定部
２３    稀少性算出部
２４    リソース管理部
２５    割当決定部
２６    配備指示部
５０，５０ａ  稀少性テーブル
６０，６０ａ  検索順リスト
【図１】
0005880575.tif 000002
【図２】
0005880575.tif 000003
【図３】
0005880575.tif 000004
【図４】
0005880575.tif 000005
【図５】
0005880575.tif 000006
【図６】
0005880575.tif 000007
【図７】
0005880575.tif 000008
【図８】
0005880575.tif 000009
【図９】
0005880575.tif 000010
【図１０】
0005880575.tif 000011
【図１１】
0005880575.tif 000012
【図１２】
0005880575.tif 000013
【図１３】
0005880575.tif 000014
【図１４】
0005880575.tif 000015
【図１５】
0005880575.tif 000016
【図１６】
0005880575.tif 000017
【図１７】
0005880575.tif 000018
【図１８】
0005880575.tif 000019