(57)【要約】【課題】マイグレーション中の障害に対する耐性を向上させるためのデータの移動順序を決定することができるデータ移動順序決定装置、データ移動順序決定方法及びプログラムを提供する。【解決手段】複数のサブデータから構成される複数のデータを移動させるときの移動順序を決定するデータ移動順序決定装置は、前記サブデータを、複数のデータで共通する共通データと、データ固有の固有データとに分類するデータ分類部と、共通データと固有データの移動順序を決定する移動順序決定部とを有する。【選択図】図２
2018073013.tif 000002
【特許請求の範囲】
【請求項１】
複数のサブデータから構成される複数のデータを移動させるときの移動順序を決定するデータ移動順序決定装置であって、
前記サブデータを、複数のデータで共通する共通データと、データ固有の固有データとに分類するデータ分類部と、
共通データと固有データの移動順序を決定する移動順序決定部と、
を有するデータ移動順序決定装置。
【請求項２】
前記移動順序決定部は、共通データ及び固有データのデータ量と、共通データを有するデータ数と、固有データの変更頻度とのうち少なくとも１つによって重み付けを行い、移動順序を決定する、請求項１に記載のデータ移動順序決定装置。
【請求項３】
前記データ分類部は、データ量に基づき共通データ及び固有データのコストを算出し、
前記移動順序決定部は、データの移動順序を複数仮定して、それぞれ仮定した移動順序に従ってあるデータを移動させるときの順序コストを、当該データ内の未移動のサブデータのコストと、当該データを含む未移動のデータ数とに基づいて算出し、当該仮定した移動順序でデータ移動を行うときの順序コストを算出し、算出した順序コストの中で最も順序コストが小さくなる移動順序を決定する、請求項１又は２に記載のデータ移動順序決定装置。
【請求項４】
前記データ分類部は、データ量に基づき共通データ及び固有データのコストを算出し、
前記移動順序決定部は、データの移動順序を複数仮定して、更に、それぞれ仮定した移動順序においてサブデータの移動順序を複数仮定して、それぞれ仮定したサブデータの移動順序に従ってあるサブデータを移動させるときの順序コストを、当該サブデータのコストと、当該データを含む未移動のデータ数とに基づいて算出し、当該仮定したサブデータの移動順序でデータ移動を行うときの順序コストを算出し、算出した順序コストの中で最も順序コストが小さくなる移動順序を決定する、請求項１又は２に記載のデータ移動順序決定装置。
【請求項５】
前記移動順序決定部は、順序コストを算出する過程において、途中まで算出した順序コストに基づいて、順序コストの算出を進める候補を選択して、選択された候補に対して順序コストの算出を進める、請求項３又は４に記載のデータ移動順序決定装置。
【請求項６】
前記移動順序決定部は、あるデータの移動順序若しくはサブデータの移動順序で順序コストを算出する過程において、別のデータの移動順序若しくはサブデータの移動順序に対して既に算出した順序コストを上回った場合、又は途中まで順序コストを算出したデータ若しくはサブデータと同一のデータ若しくはサブデータが別のデータの移動順序若しくはサブデータの移動順序において算出されており且つ途中まで算出した順序コストが当該別のデータの移動順序若しくはサブデータの移動順序において算出された順序コストを上回った場合、順序コストの算出を中断する、請求項３又は４に記載のデータ移動順序決定装置。
【請求項７】
複数のサブデータから構成される複数のデータを移動させるときの移動順序を決定するデータ移動順序決定装置におけるデータ移動順序決定方法であって、
前記サブデータを、複数のデータで共通する共通データと、データ固有の固有データとに分類するステップと、
共通データと固有データの移動順序を決定するステップと、
を有するデータ移動順序決定方法。
【請求項８】
複数のサブデータから構成される複数のデータを移動させるときの移動順序を決定するデータ移動順序決定装置として、コンピュータを機能させるためのプログラムであって、当該コンピュータを、
前記サブデータを、複数のデータで共通する共通データと、データ固有の固有データとに分類するデータ分類手段、及び
共通データと固有データの移動順序を決定する移動順序決定手段、
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ移動順序決定装置、データ移動順序決定方法及びプログラムに関し、特に、仮想マシンのマイグレーションにおいて複数の仮想マシンのデータを移動させるときの移動順序を決定するための技術に関する。
【背景技術】
【０００２】
これまで物理サーバを用いることでしか実現できなかったアプリケーションの稼働をソフトウェアプラットフォーム上で行う仮想マシン（VM：Virtual Machine）技術が発達している。VMはソフトウェアであり、VMを稼働させる環境が存在する物理プラットフォーム上で稼働する。そして、稼働環境を持つサーバが複数存在する場合、VM内のソフトを稼働させた状態で、VMを稼働するサーバを別のサーバに変更することができる、という特徴を持つ。このため、VM内で稼働するアプリケーションを止めることなく、それまでVMを稼働させていたサーバからバックアップ用のサーバにVMを移動させることができる。この動作はライブマイグレーションと呼ばれ、サーバの故障時やメンテナンス時にサービスを継続させる手段として用いられる。
【０００３】
サーバ内には複数のVMを収容することができる。これにより、1台のサーバを用いることで複数台のサーバと同等の処理を行うことが可能になる。このため、サーバのメンテナンスやデータセンタが災害に見舞われたとき、複数台のVMが一斉にバックアップ用のサーバやデータセンタに移動するという現象が発生する。
【０００４】
アプリケーションは高度化する傾向にある。それにともない、アプリケーションが利用するリソース量も増加する。そのようなアプリケーションを稼働させるため、VMのデータサイズは増加傾向にある。これに伴い、VMをマイグレーションするときに要する時間は増加する。この問題を解決すべくマイグレーション時間を短縮する様々な方法が検討されている。その中でもデデュプリケーション（dedupulication）と呼ばれる方法がマイグレーション時間を短縮する方法として有望視されている（非特許文献１参照）。
【０００５】
VMの中、もしくはVM間では、共通するデータが存在する。これは同じOS（Operating System）やアプリケーションを稼働させているVMが存在するためである。このようなVMのマイグレーションを行うとき、共通するデータにより重複して存在する部分については、共通するデータを1度だけ送信し、移行先で重複度合いにより複製する方法がデデュプリケーションである。この方法を用いることにより、重複するデータを個別に送信する必要がないため、送信しなければいけないデータ量が削減される。データ転送時間はマイグレーション時間に大きな影響を与えるため、この方法を用いることにより、マイグレーション時間を大幅に短縮することができる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】U. Deshpande, et al.,"Live gang migration of virtual machines," ACM High Performance Distributed Computing, pp. 135-146, 2011
【発明の概要】
【発明が解決しようとする課題】
【０００７】
VMのマイグレーションを必要とする状況として、災害や装置故障が発生し、それまで稼働していたサーバでVMを稼働できなくなる状況がある。マイグレーションは数秒から数十秒のオーダーの時間を必要とする。このため、災害等でデータセンタの施設の稼働状況が不安定になっている場合、マイグレーションを行っている最中にサーバやデータセンタ内のスイッチやケーブルに異常が発生し、マイグレーションを継続できない状況が生じうる。
【０００８】
この状況に対応する方法として、短い時間でできるだけ多くのVMのマイグレーションを完了するためにスケジューリングを行う方法を考える。
【０００９】
従来方式においてデデュプリケーションを行う際、データはシーケンシャルに送信される。すなわち、1つのデータが送信された後、別のデータを送信する。よって、すべてのデータを送信する時間は、データの送信順によらず一定である。
【００１０】
しかし、個別のVMのマイグレーション終了時間に注目した場合、事情は異なる。例として、2つのVM（VM1及びVM2）がマイグレーションを行う際に順番によって個別のVMのマイグレーション時間が異なる例を紹介する。VM1は別のVM2と共通するデータを100Mbyteもち、個別のデータを200Mbyte持つとする。別のVM2は先ほどのVM1と共通するデータを100Mbyte持ち、個別のデータを400Mbyte持つとする。
【００１１】
VM1を先にマイグレーションする場合、共通データと個別データを転送した後、VM2の個別データを送信する。よって、VM1のマイグレーションは300Mbyte送信した時点で終了し、VM2のマイグレーションは700Mbyte送信した時点で終了する。
【００１２】
送信順を逆にする。VM2を先にマイグレーションすると、このVM2のマイグレーションは500Mbyte送信した時点で終了し、VM1のマイグレーションは700Mbyte送信した時点で終了する。
【００１３】
ここで、400Mbyte送信した時点で移行元のサーバが稼働しなくなったとする。このとき、VM1,VM2の順番でマイグレーションを行った場合、VM1は移行先で稼働することができるが、VM2は故障に巻き込まれて停止してしまう。逆の順番でマイグレーションを行った場合、VM1,VM2ともに故障に巻き込まれて停止してしまう。
【００１４】
この例からも、マイグレーションを行う順番の決定方法を検討することにより、VMの生存数を向上させることができることがわかる。しかし、従来方式では、マイグレーションを行う順番が考慮されていないため、マイグレーション中の障害に対する耐性を向上させることができない。
【００１５】
本発明は、マイグレーション中の障害に対する耐性を向上させるためのデータの移動順序を決定することができるデータ移動順序決定装置、データ移動順序決定方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の一形態に係るデータ移動順序決定装置は、
複数のサブデータから構成される複数のデータを移動させるときの移動順序を決定するデータ移動順序決定装置であって、
前記サブデータを、複数のデータで共通する共通データと、データ固有の固有データとに分類するデータ分類部と、
共通データと固有データの移動順序を決定する移動順序決定部と、
を有することを特徴とする。
【００１７】
また、本発明の一形態に係るデータ移動順序決定方法は、
複数のサブデータから構成される複数のデータを移動させるときの移動順序を決定するデータ移動順序決定装置におけるデータ移動順序決定方法であって、
前記サブデータを、複数のデータで共通する共通データと、データ固有の固有データとに分類するステップと、
共通データと固有データの移動順序を決定するステップと、
を有することを特徴とする。
【００１８】
また、本発明の一形態に係るプログラムは、
複数のサブデータから構成される複数のデータを移動させるときの移動順序を決定するデータ移動順序決定装置として、コンピュータを機能させるためのプログラムであって、当該コンピュータを、
前記サブデータを、複数のデータで共通する共通データと、データ固有の固有データとに分類するデータ分類手段、及び
共通データと固有データの移動順序を決定する移動順序決定手段、
として機能させることを特徴とする。
【発明の効果】
【００１９】
本発明によれば、マイグレーション中の障害に対する耐性を向上させるためのデータの移動順序を決定することが可能になる。
【図面の簡単な説明】
【００２０】
【図１】マイグレーションのフェーズを示す図
【図２】本発明の実施例に係るデータ移動順序決定装置の機能ブロック図
【図３】VMのデータ構造例
【図４】ノード単位の順序コスト算出例
【図５】行毎にノード単位の順序コストを算出する方法のフロー例
【図６】ノード単位の順序コスト算出において計算量を削減する例（その１）
【図７】ノード単位の順序コスト算出において計算量を削減する例（その２）
【図８】ノード単位の順序コスト算出において計算量を削減する例（その３）
【図９】列毎にノード単位の順序コストを算出する方法のフロー例
【図１０】ノード単位の順序コスト算出において計算量を削減する例（その４）
【図１１】リンク単位の順序コスト算出例
【図１２】行毎にリンク単位の順序コストを算出する方法のフロー例
【図１３】列毎にリンク単位の順序コストを算出する方法のフロー例
【図１４】VMのデータ構造をツリーで表現する例
【図１５】VMのデータ構造をツリーで表現したときのリンクの順序及び順序コストを説明するための図
【図１６】ノード単位の順序コスト算出方法のフローチャート
【図１７】実施例１のステップＳ５０３−１におけるリンクの計算を示す図
【図１８】実施例１の計算過程におけるデータの例を示す図（その１）
【図１９】実施例１の計算過程におけるデータの例を示す図（その２）
【図２０】実施例１の計算過程におけるデータの例を示す図（その３）
【図２１】実施例１のフローチャートの計算過程におけるデータの例を示す図（その４）
【図２２】実施例１のフローチャートの計算過程におけるデータの例を示す図（その５）
【図２３】実施例１のフローチャートの計算過程におけるデータの例を示す図（その６）
【図２４】一般的なVMのデータ構造の例（その１）
【図２５】一般的なVMのデータ構造のときのリンクの順序及び順序コストを説明するための図
【図２６】一般的なVMのデータ構造の例（その２）
【図２７】実施例２のステップＳ５０３−１におけるリンクの計算を示す図
【図２８】実施例２の計算過程におけるデータの例を示す図（その１）
【図２９】実施例２の計算過程におけるデータの例を示す図（その２）
【図３０】実施例２の計算過程におけるデータの例を示す図（その３）
【図３１】実施例２のフローチャートの計算過程におけるデータの例を示す図（その４）
【図３２】実施例２のフローチャートの計算過程におけるデータの例を示す図（その５）
【図３３】リンク単位の順序コスト算出方法のフローチャート（その１）
【図３４】実施例３のステップＳ６０３−１における経路の計算を示す図
【図３５】実施例３（図３３）の計算過程におけるデータの例を示す図（その１）
【図３６】実施例３（図３３）の計算過程におけるデータの例を示す図（その２）
【図３７】実施例３（図３３）の計算過程におけるデータの例を示す図（その３）
【図３８】実施例３（図３３）のフローチャートの計算過程におけるデータの例を示す図（その４）
【図３９】実施例３（図３３）のフローチャートの計算過程におけるデータの例を示す図（その５）
【図４０】リンク単位の順序コスト算出方法のフローチャート（その２）
【図４１】実施例３のステップＳ７０３−１における経路の計算を示す図
【図４２】実施例３（図４０）の計算過程におけるデータの例を示す図（その１）
【図４３】実施例３（図４０）の計算過程におけるデータの例を示す図（その２）
【図４４】実施例３（図４０）の計算過程におけるデータの例を示す図（その３）
【図４５】実施例３（図４０）のフローチャートの計算過程におけるデータの例を示す図（その４）
【図４６】実施例３（図４０）のフローチャートの計算過程におけるデータの例を示す図（その５）
【図４７】計算量を削減するときの実施例３（図３３）の計算過程におけるデータの例を示す図
【図４８】実施例４のステップＳ６０３−１における経路の計算を示す図
【図４９】実施例４（図３３）の計算過程におけるデータの例を示す図（その１）
【図５０】実施例４（図３３）の計算過程におけるデータの例を示す図（その２）
【図５１】実施例４（図３３）の計算過程におけるデータの例を示す図（その３）
【図５２】実施例４（図３３）のフローチャートの計算過程におけるデータの例を示す図（その４）
【図５３】実施例４（図３３）のフローチャートの計算過程におけるデータの例を示す図（その５）
【図５４】実施例４のステップＳ７０３−１における経路の計算を示す図
【図５５】実施例４（図４０）の計算過程におけるデータの例を示す図（その１）
【図５６】実施例４（図４０）の計算過程におけるデータの例を示す図（その２）
【図５７】実施例４（図４０）の計算過程におけるデータの例を示す図（その３）
【図５８】実施例４（図４０）のフローチャートの計算過程におけるデータの例を示す図（その４）
【図５９】実施例４（図４０）のフローチャートの計算過程におけるデータの例を示す図（その５）
【図６０】計算量を削減するときの実施例４（図３３）の計算過程におけるデータの例を示す図
【図６１】一般的なVMのデータ構造の例（その３）
【図６２】本発明の実施例に係るデータ移動順序決定装置のハードウェア構成例を示す図
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施例について説明する。
【００２２】
本発明の実施例では、仮想マシン（VM）のマイグレーションにおいて複数のVMのデータを移動させるときの移動順序を決定するデータ移動順序決定装置について説明する。VMのマイグレーションとは、VMのメモリデータを移行先のサーバにコピーする作業のことを言う。VMのライブマイグレーションとは、VMのマイグレーションの一種であり、サーバ上で稼働しているVMを稼働させたまま別のサーバ（例えば、バックアップ用サーバ）に移動（コピー）させることを言う。
【００２３】
図１は、マイグレーションのフェーズを示す図である。マイグレーションには、初期コピー、更新コピー、及び最終更新コピーの３つのフェーズが存在する。マイグレーションを開始した後、初期コピーフェーズで開始時のデータを最初にコピーする。その間、VMは稼働しているため、データの書き換えが行われる。その書き換えられたデータを更新コピーフェーズで送信する。そして、あるタイミングでVMの稼働を停止し、最終更新コピーフェーズで残りの更新データを送信する。
【００２４】
例えば、サーバの故障時や障害時において、サーバ上で稼働しているVMを稼働させたまま一斉にバックアップ用サーバに移動させる場合、サーバの動作が不安定になっているため、途中で異常が発生し、ライブマイグレーションを継続できなくなってしまう場合がある。本発明の実施例に係るデータ移動順序決定装置は、短時間で移動が完了するVMを優先して移動させるように、データの移動をスケジューリングする。
【００２５】
図２は、本発明の実施例に係るデータ移動順序決定装置１００の機能ブロック図である。データ移動順序決定装置１００は、データ分類部１１０と、移動順序決定部１２０とを有する。
【００２６】
一般的に、VMのデータは、複数のサブデータから構成され、複数のサブデータは、VM間で共通する共通データ（OS等）と、VMに固有の固有データに分類される。固有データは、アプリケーションが処理を行う際に使用する一時データなどを含む。説明の便宜上、VMのデータをノードと呼ぶことがあり、サブデータをリンクと呼ぶことがある。また、共通データを中間リンクと呼ぶことがあり、固有データを葉リンクと呼ぶことがある。
【００２７】
データ分類部１１０は、マイグレーションの対象となるVMのサブデータに関する情報を取得し、VMのサブデータを、複数のVMで共通する共通データ（すなわち、中間リンク）と、VM固有の固有データ（すなわち、葉リンク）とに分類する。図３に、VMのデータ構造例を示す。例えば、VM間で共通するサブデータa〜iは中間リンクに分類され、VMに固有のサブデータ1〜4は葉リンクに分類される。VM固有の情報や一時データは葉リンクに分類される。また、マイグレーションの更新コピーフェーズ及び最終更新コピーフェーズで送信される更新データも葉リンクに分類される。更に、データ分類部１１０は、データ量に基づき中間リンク及び葉リンクのコストを算出する。例えば、コストはデータ量や転送時間に比例する値に設定される。
【００２８】
移動順序決定部１２０は、共通データと固有データの移動順序を決定する。このとき、短時間で移動が完了するVMを優先して移動させることができるようなスケジューリングを行う。移動順序の決定においては、中間リンクを葉リンクより優先する。葉リンクに含まれる一時データは処理に伴い頻繁に更新されるため、この部分をマイグレーションの中間部分で送信すると、大量に更新されたデータを送信することになり、マイグレーション時間の増加につながるため、葉リンクはノード内においては最後に送信する。また、葉リンクの中でも更新頻度が大きいデータほど最後に送信する。なお、以下の移動順序の計算においても、葉リンクの移動順序がノード内において最後になるようにする。
【００２９】
また、移動順序決定部１２０は、中間リンク及び葉リンクのデータ量（コスト）と、中間リンクを有するノード数と、固有データの変更頻度とのうち少なくとも１つによって重み付けを行い、移動順序を決定する。具体的には、移動順序決定部１２０は、ノードのデータ移動を完了するまでに要する順序コストを算出し、順序コストが小さくなるようデータの移動順序をスケジューリングするが、このスケジューリングのときに、上記のように中間リンクを葉リンクより優先する。順序コストは、優先して移動させるものほど順序コストが小さくなるよう、重み付けが行われる。
【００３０】
順序コストの算出方法には、以下に詳細に説明するように、ノード単位で順序コストを算出する方法と、リンク単位で順序コストを算出する方法がある。重み付けは、移動するノード／リンクのコスト算出時、自ノード／リンクを含む未移動のノード／リンク（残ノード／リンクと呼ぶ）の数を乗じた重み付けを行う。例えば、先にコストの大きいリンクを移動すると、そのリンク移動後の残ノード数は大きくなり、順序コストも大きくなることから、そのような移動は優先されなくなる。
【００３１】
＜ノード単位の順序コストの算出方法の概要＞
移動順序決定部１２０におけるノード単位の順序コスト算出について説明する。まず、移動順序決定部１２０は、データの移動順序、すなわち、データ移動を行うノード順序を複数仮定する。例えば、図３のデータ構造例の場合、複数のノード順序が考えられる。その中で、VM1、VM2、VM3、VM4の順でデータ移動を行う場合の順序コストについて説明する。
【００３２】
VM1のデータを移動させるときの順序コストは、VM1内の未移動のサブデータのコストと、VM1を含む未移動のノード数とに基づいて算出される。VM1のコスト（移動データ量）は、{a,b,c,d,1}のサブデータを移動するため、2+1+3+2+1=9である。この時、残ノード数4（自ノードも含め、未移動のノードはVM1、VM2、VM3、VM4の4ノード）を乗じて、順序コストは36とする。次に、VM2のコストを算出するが、VM2の中のa,dはVM1の移動で既に移動しているため、{f,g,2}=1+2+2=5である。この時、残ノード数3（VM2、VM3、VM4）を乗じて順序コストは15となる。同様にVM3の順序コストは({e,3}=4+3)*2=14となり、VM4の順序コスト{h,i,4}=3+2+2=7となる。従って、VM1、VM2、VM3、VM4でデータ移動する順序コストは、36+15+14+7=72である。
【００３３】
移動順序決定部１２０は、他のノード順序でデータ移動を行うときの順序コストも算出し、算出した順序コストの中で最も順序コストが小さくなる移動順序を決定する。順序コストは、全ての移動順序に対して算出してもよいが、以下に詳細に説明するように、順序コストの算出を進める候補を選択してもよく、順序コストの算出を途中で中断してもよい。
【００３４】
図４は、ノード単位の順序コスト算出例である。説明を簡単にするために、図４（Ａ）に示すデータ構造を仮定する。ノードn1、n2、n3、n4のリンクの中で、a、bは中間リンクであり、c、d、e、fは葉リンクである。それぞれのコストは中間リンク及び葉リンクに示されている。
【００３５】
このときの順序コストの算出過程を図４（Ｂ）に示す。図４（Ｂ）において、各ボックス内の{n1,n2,…}は移動するノードの順序であり、a,c,d,…は転送するリンクの順序である。また、図４（Ｂ）の最も下の行には、順序コストの算出の基礎となるコストの値を示す。
【００３６】
{n1}の順序コストは(リンクa,cのコスト)*(n1を含む残ノード数)=5*4=20として計算できる。{n1,n2}の順序コストは{n1}の順序コスト+(追加したリンクdのコスト)*(n2を含む残ノード数)=20+(1*3)=23として計算できる。{n1,n2,n3}の順序コストは{n1,n2}の順序コスト+(追加したリンクb,eのコスト)*(n3を含む残ノード数)=23+(6*2)=35として計算できる。{n1,n2,n3,n4}の順序コストは{n1,n2,n3}の順序コスト+(追加したリンクfのコスト)*(n4を含む残ノード数)=35+(3*1)=38として計算できる。同様に順序コストの算出を進めると、最も順序コストが小さくなる移動順序は、{n2,n1,n3,n4}であることが分かる。
【００３７】
順序コストの算出は、図４の行毎に行ってもよく、列毎に行ってもよい。言い換えると、行毎の算出とは、あるノード順序{n1,n2,n3,n4}の順序コストを算出する過程において、同じ階層（順序コストを算出したノード数）まで別のノード順序{n2,n1,n3,n4}の順序コストを算出する方法である。また、列毎の算出とは、あるノード順序{n1,n2,n3,n4}を計算し終えた後に、別のノード順序{n1,n2,n4,n3}を計算する方法である。
【００３８】
図５は、行毎にノード単位の順序コストを算出する方法のフロー例である。移動対象となるノードの数を階層数とする。例えば、4ノードの場合、階層数は4であり、階層L=4のときに最下層である。
【００３９】
まず、ステップＳ１０１において、階層L=1とする。ステップＳ１０２において、階層Lにおける各ノードの順序リストを更新する。例えば、階層L=1でn1を選定していたならば、階層L=2の未選定ノードはn2,n3,n4である。n2を次ノードと選定すると、階層L=1の順序リスト{n1}を{n1,n2}に更新する。ステップＳ１０３において、各順序リストにおける順序コストを算出する。順序コスト=(階層L-1の順序コスト)+(次ノードを移動完了するためのコスト)*（次ノードを含む未選定ノード数）である。例えば、順序リスト{n1,n2}ならば、順序コスト=({n1}の順序コスト)+(次ノードn2のコスト)*(未選定ノード数3(n2,n3,n4の3ノード))である。ステップＳ１０４において階層Lが最下層でない場合、ステップＳ１０５において階層L+1としてステップＳ１０２に戻る。ステップＳ１０４において階層Lが最下層である場合、ステップＳ１０６において最小順序コスト及びそのときの順序リストを出力する。
【００４０】
図５は、全ての順序コストを算出する例を示しているが、順序コストを算出する過程において順序コストの算出を中断して計算量を削減することも可能である。図６は、ノード単位の順序コスト算出において計算量を削減する例を示す。図６（Ａ）のデータ構造は図４（Ａ）のデータ構造と同じである。
【００４１】
あるノード順序{n1,n2,…}で順序コストを算出する過程{n1,n2}において、途中まで順序コストを算出したノードn1,n2と同一のノードが別のノード順序{n2,n1,…}において算出されており且つ途中まで算出した順序コスト23が別のノード順序において算出された順序コスト21を上回った場合、順序コストの算出を中断することができる。なお、順序コストが同じである場合には、どちらかの順序コストの算出を進める。これは、図５のステップＳ１０３において、階層Lにおいて順序コストを算出したノードの組み合わせが同一になった場合、最小コスト以外は順序リスト更新の対象から除外することで実現できる。
【００４２】
図７は、図６に従ってコスト算出を進めた結果である。例えば、{n1,n2}のノード順序で移動したときの順序コストは23であり、同じノードの組み合わせである{n2,n1}のノード順序で移動したときの順序コストは21である。そのため、コストが少ない{n2,n1}のノード順序に対して順序コストの算出を進める。図７において、ハッチングが同じ箇所は同じノードの組み合わせとなっており、このうち、順序コストが少ない順に次の階層の計算を行う。また、図７において、順序コストの算出を進めるものを、太線の枠で示す。最終的に、最適解である順序コスト36及び順序リスト{n2,n1,n3,n4}が出力される。
【００４３】
上記のように総当たりで順序コストを算出すると計算量が大きくなると想定される。従って、順序コストを算出する過程において、途中まで算出した順序コストに基づいて、順序コストの算出を進める候補を選択して、選択された候補に対して順序コストの算出を進めてもよい。図８は、ノード単位の順序コスト算出において計算量を削減する例を示す。図８においても図４（Ａ）のデータ構造の例が用いられる。
【００４４】
行毎にノード単位の順序コストを算出する過程において、ある階層において順序コストが少ない順に、順序コストの算出を進める候補を選択する。例えば、ある階層L=1において順序コストが少ない２つのノード順序{n1}、{n2}のみ次の階層L=2の順序コストを算出する。同様に、階層L=2において順序コストが少ない２つのノード順序{n1,n2}、{n1,n3}のみ次の階層L=3の順序コストを算出する。これは、図５のステップＳ１０３において、階層Lにおいて順序コストが少ない上位の２つ以外は順序リスト更新の対象から除外することで実現できる。この場合、最適解が得られない可能性があるが、準最適解が短時間で算出できる。
【００４５】
図９は、列毎にノード単位の順序コストを算出する方法のフロー例である。移動対象となるノードの数を階層数とする。例えば、4ノードの場合、階層数は4であり、階層L=4のときに最下層である。
【００４６】
まず、ステップＳ２０１において、階層L=1とする。ステップＳ２０２において、階層Lに未選定ノードがある場合、ステップＳ２０３において未選定ノードから次ノードを選択し、順序リストを更新する。例えば、階層L=1でn1を選定していたならば、階層L=2の未選定ノードはn2,n3,n4である。n2を次ノードと選定すると、階層L=1の順序リスト{n1}を{n1,n2}に更新する。ステップＳ２０４において、順序リストにおける順序コストを算出する。順序コスト=(階層L-1の順序コスト)+(次ノードを移動完了するためのコスト)*(次ノードを含む未選定ノード数)である。例えば、順序リスト{n1,n2}ならば、順序コスト=({n1}の順序コスト)+(次ノードn2のコスト)*(未選定ノード数3(n2,n3,n4の3ノード))である。ステップＳ２０５において階層Lが最下層でない場合、ステップＳ２０６において階層L+1としてステップＳ２０２に戻る。ステップＳ２０５において階層Lが最下層である場合、ステップＳ２０９において最小順序コスト及びそのときの順序リストを更新する。更に、ステップＳ２１０において階層L-1としてステップＳ２０２に戻る。
【００４７】
ステップＳ２０２において階層Lに未選定ノードがなく、階層L=1でない場合、１つ上の階層に戻って順序コストを計算するため、ステップＳ２１０において階層L-1としてステップＳ２０２に戻る。ステップＳ２０２において階層Lに未選定ノードがなく、階層L=1である場合、全ての順序コストの算出が完了したので、ステップＳ２０８において最小順序コスト及びそのときの順序リストを出力する。
【００４８】
図９は、全ての順序コストを算出する例を示しているが、順序コストを算出する過程において順序コストの算出を中断して計算量を削減することも可能である。図１０は、ノード単位の順序コスト算出において計算量を削減する例を示す。図１０においても図４（Ａ）のデータ構造の例が用いられる。
【００４９】
あるノード順序{n1,n2,n4,n3}で順序コストを算出する過程{n1,n2,n4}において、別のノード順序{n1,n2,n3,n4}に対して既に算出した順序コストを上回った場合、順序コストの算出を中断することができる。これは、図９のステップＳ２０４において、階層Lにおいて算出した順序コストが、別のノード順序に対してステップＳ２０９において既に算出した最小順序コスト以上であれば、ステップＳ２０５に進まずにステップＳ２０２に戻ることで実現できる。この例においても、最適解である順序コスト36及び順序リスト{n2,n1,n3,n4}が出力される。
【００５０】
＜リンク単位の順序コストの算出方法の概要＞
移動順序決定部１２０におけるリンク単位の順序コスト算出について説明する。まず、移動順序決定部１２０は、データの移動順序、すなわち、データ移動を行うノード順序を複数仮定する。例えば、図３のデータ構造例の場合、複数のノード順序が考えられる。その中で、VM1、VM2、VM3、VM4の順でデータ移動を行う場合の順序コストについて説明する。
【００５１】
VM1のデータを移動させるためには、リンク{a,b,c,d,1}を移動させる必要がある。更に、移動順序決定部１２０は、仮定したノード順序において、リンクの移動順序、すなわち、データ移動を行うリンク順序を仮定する。中間リンクからデータを移動させるため、a,b,c,d,1の順でリンクを移動させる場合を考える。
【００５２】
VM1のリンクaのデータを移動させるときの順序コストは、リンクaのコストと、VM1を含む未移動のノード数とに基づいて算出される。リンクaのコストは2である。この時、残ノード数4（自ノードも含め、未移動のノードはVM1、VM2、VM3、VM4の4ノード）を乗じて、順序コストは8とする。次に、リンクbのコストは1である。この時、残ノード数4を乗じて、順序コストは4とする。同様に計算し、VM1の順序コストは8+4+12+8+4=36（(2+1+3+2+1)*4=36）となる。同様にVM2のf,g,2（残ノード数3）、VM3のe,3（残ノード数2）、VM4のh,i,4（残ノード数1）の順序コストを算出し、その和をVM1、VM2、VM3、VM4の順でデータ移動する場合の順序コストとする。
【００５３】
移動順序決定部１２０は、他のリンク順序及び他のノード順序でデータ移動を行うときの順序コストも算出し、算出した順序コストの中で最も順序コストが小さくなる移動順序を決定する。順序コストは、全ての移動順序に対して算出してもよいが、ノード単位における順序コストの算出と同様に、順序コストの算出を進める候補を選択してもよく、順序コストの算出を途中で中断してもよい。
【００５４】
図１１は、リンク単位の順序コスト算出例である。説明を簡単にするために、図１１（Ａ）に示すデータ構造を仮定する。ノードn1、n2、n3、n4のリンクの中で、a、bは中間リンクであり、c、d、e、fは葉リンクである。それぞれのコストは中間リンク及び葉リンクに示されている。
【００５５】
このときの順序コストの算出過程を図１１（Ｂ）に示す。図１１（Ｂ）において、各ボックス内の{a,c,d,…}は転送するリンクの順序である。また、図５（Ｂ）の最も下の行には、順序コストの算出の基礎となるコストの値を示す。ノードの移動順序としては、{n1,n2,n3,n4}、{n1,n2,n4,n3}、{n1,n3,n2,n4}、｛n1,n3,n4,n2}、{n1,n4,n2,n3}、{n1,n4,n3,n2}、{n2,n1,n3,n4}、{n2,n1,n4,n3}、…が考えられるが、{n1,n2,n3,n4}のときの順序コストの算出について説明する。
【００５６】
{a}の順序コストは(リンクaのコスト)*(n1を含む残ノード数)=2*4=8として計算できる。{a,c}の順序コストは{a}の順序コスト+(追加したリンクcのコスト)*(n1を含む残ノード数)=8+(3*4)=20として計算できる。{a,c,d}の順序コストは{a,c}の順序コスト+(追加したリンクdのコスト)*(n2を含む残ノード数)=20+(1*3)=23として計算できる。全ての順序コストを算出してもよいが、図６と同様に、あるリンク順序{a,c,d,…}で順序コストを算出する過程{a,c,d}において、途中まで順序コストを算出したリンクa,c,dと同一のリンクが別のリンク順序{a,d,c}において算出されており且つ途中まで算出した順序コスト23が別のリンク順序において算出された順序コスト21を上回った場合、順序コストの算出を中断することができる。なお、順序コストが同じである場合には、どちらかの順序コストの算出を進める。順序コストの算出を進めると、最も順序コストが小さくなる移動順序は、{a,d,c,b,e,f}であることが分かる。
【００５７】
図１２は、行毎にリンク単位の順序コストを算出する方法のフロー例である。移動対象となるリンクの数を階層数とする。例えば、リンク数が4の場合、階層数は4であり、階層L=4のときに最下層である。
【００５８】
まず、ステップＳ３０１において、階層L=1とする。ステップＳ３０２において、階層Lにおける各リンクの順序リストを更新する。例えば、階層L=1でaを選定していたならば、階層L=2の未選定リンクはc,d,…である。cを次リンクと選定すると、階層L=1の順序リスト{a}を{a,c}に更新する。ステップＳ３０３において、各順序リストにおける順序コストを算出する。順序コスト=(階層L-1の順序コスト)+(次リンクを移動完了するためのコスト)*（次リンクのノードを含む未選定ノード数）である。例えば、順序リスト{a,c}ならば、順序コスト=({a}の順序コスト)+(次リンクcのコスト)*(未選定ノード数4(n1,n2,n3,n4の4ノード))である。ステップＳ３０４において階層Lが最下層でない場合、ステップＳ３０５において階層L+1としてステップＳ３０２に戻る。ステップＳ３０４において階層Lが最下層である場合、ステップＳ３０６において最小順序コスト及びそのときの順序リストを出力する。
【００５９】
図１２は、全ての順序コストを算出する例を示しているが、図１１で説明したように、順序コストを算出する過程において順序コストの算出を中断することも可能である。これは、図１２のステップＳ３０３において、階層Lにおいて順序コストを算出したリンクの組み合わせが同一になった場合、最小コスト以外は順序リスト更新の対象から除外することで実現できる。
【００６０】
また、上記のように総当たりで順序コストを算出すると計算量が大きくなると想定される。従って、図８と同様に、順序コストを算出する過程において、途中まで算出した順序コストに基づいて、順序コストの算出を進める候補を選択して、選択された候補に対して順序コストの算出を進めてもよい。これは、図１２のステップＳ３０３において、階層Lにおいて順序コストが少ない上位の２つ以外は順序リスト更新の対象から除外することで実現できる。この場合、最適解が得られない可能性があるが、準最適解が短時間で算出できる。
【００６１】
図１３は、列毎にリンク単位の順序コストを算出する方法のフロー例である。移動対象となるリンクの数を階層数とする。例えば、リンク数が4の場合、階層数は4であり、階層L=4のときに最下層である。
【００６２】
まず、ステップＳ４０１において、階層L=1とする。ステップＳ４０２において、階層Lに未選定リンクがある場合、ステップＳ４０３において未選定リンクから次リンクを選択し、順序リストを更新する。例えば、階層L=1でaを選定していたならば、階層L=2の未選定リンクはc,d,…である。cを次リンクと選定すると、階層L=1の順序リスト{a}を{a,c}に更新する。ステップＳ４０４において、順序リストにおける順序コストを算出する。順序コスト=(階層L-1の順序コスト)+(次リンクを移動完了するためのコスト)*(次リンクのノードを含む未選定ノード数)である。例えば、順序リスト{a,c}ならば、順序コスト=({a}の順序コスト)+(次リンクcのコスト)*(未選定ノード数4(n1,n2,n3,n4の4ノード))である。ステップＳ４０５において階層Lが最下層でない場合、ステップＳ４０６において階層L+1としてステップＳ４０２に戻る。ステップＳ４０５において階層Lが最下層である場合、ステップＳ４０９において最小順序コスト及びそのときの順序リストを更新する。更に、ステップＳ４１０において階層L-1としてステップＳ４０２に戻る。
【００６３】
ステップＳ４０２において階層Lに未選定リンクがなく、階層L=1でない場合、１つ上の階層に戻って順序コストを計算するため、ステップＳ４１０において階層L-1としてステップＳ４０２に戻る。ステップＳ４０２において階層Lに未選定ノードがなく、階層L=1である場合、全ての順序コストの算出が完了したので、ステップＳ４０８において最小順序コスト及びそのときの順序リストを出力する。
【００６４】
図１３は、全ての順序コストを算出する例を示しているが、順序コストを算出する過程において順序コストの算出を中断することも可能である。図１０と同様に、あるリンク順序{a,c,b,e,d,f}で順序コストを算出する過程{a,c,b,e}において、別のリンク順序{a,d,c,b,e,f}に対して既に算出した順序コストを上回った場合、順序コストの算出を中断することができる。これは、図１１のステップＳ４０４において、階層Lにおいて算出した順序コストが、別のリンク順序に対してステップＳ４０９において既に算出した最小順序コスト以上であれば、ステップＳ４０５に進まずにステップＳ４０２に戻ることで実現できる。
【００６５】
＜実施例１：ノード単位の順序コストの算出例（データ構造がツリーで表現できる場合）＞
図６で説明したノード単位の順序コストの算出において計算量を削減する例について更に詳細に説明する。実施例１では、VMのデータ構造がツリーで表現できることを仮定する。
【００６６】
図１４に、VMのデータ構造をツリーで表現する例を示す。VM1、VM2、VM3、VM4のサブデータを中間リンクa,b及び葉リンクc,d,e,fに分類する。ツリートポロジは、１つの根ノードと複数の葉ノードを含む。根ノード方向を上流とし、中間リンクを優先的に上流に接続し、葉リンクを下流に接続することで、VM1、VM2、VM3、VM4のデータ構造がツリートポロジで表現される。各リンクにはコストが存在する。
【００６７】
実施例１では、上記のように、共通データである中間リンクを優先して移動させ、固有データである葉リンクを後で送信する。葉リンクに含まれる一時データは処理に伴い頻繁に更新されるため、この部分をマイグレーションの中間部分で送信すると、大量に更新されたデータを送信することになり、マイグレーション時間の増加につながるため、葉リンクはノード内においては最後に送信する。リンクの順序の計算においても、葉リンクの移動順序がノード内において最後になるようにする。
【００６８】
以下の説明において使用するデータについて説明する。構造体データとは、確定済みのリンクの順序を管理するデータを示す。構造体データは、順序が確定したリンクを記録するデータ1と、リンクの順序を記録するデータ2と、確定済みの順序に従いデータを移動したときの順序コストを記録するデータ3を含む。また、集合データ1は、構造体データの集合であり、順序確定済みのリンクの組み合わせが同じリンク順序のうち、順序コストの最も小さい順序を管理するデータを示す。全てのリンクをデータ1に持つ構造体データのみになった場合、全てのリンクの順序が確定したため順序コストの算出が終了する。リンク集合データ1は、確定済みのリンクの集合を示し、リンク集合3の計算に使用する。リンク集合データ2は、リンクの順序を管理するデータを示す。リンク集合3は、未確定のリンクの集合を示す。
【００６９】
図１５は、VMのデータ構造をツリーで表現したときのリンクの順序及び順序コストを説明するための図である。図１５のデータ構造において、リンクのIDをa〜d、ノードのIDをn1〜n3と定義する。リンクのコストをCa〜Cdとする。リンクの順序がa->b->c->dである場合、構造体データのデータ1に{a,b,c,d}が、データ2に{a->b->c->d}が記録される。
【００７０】
リンクaを選ぼうとした時点で、葉リンクから根ノードまでの経路が確定していない葉リンク（aを含む）は3本存在する。よって、3*Caを順序コストに足す。次に、リンクb,cを選んだ時点で、葉リンクから根ノードまでの経路が確定していない葉リンクは2本存在する。よって、2*(Cb+Cc)を順序コストに足す。dを選んだ時点で順序が確定していない葉リンクは1本存在する。よって、1*Cdを順序コストに足す。この計算により、順序a->b->c->dの順序コストを3Ca+2Cb+2Cc+Cdとする。順序コストはVMのマイグレーション時間の総和を示す。よって、順序コストが小さければ、個別のVMのマイグレーション時間が短いものが多いことを示す。
【００７１】
図１６は、ノード単位の順序コスト算出方法のフローチャートである。図１６を説明するときの具体例として、図１４のデータ構造を用いる。
【００７２】
ステップＳ５０１において、変数を初期化する。リンク集合データ1とリンク集合データ2と構造体データ10と集合データ1を空にし、数値1を0にする。
【００７３】
ステップＳ５０２において、全リンクからリンク集合データ1に含まれるリンクを削除したリンクの集合であるリンク集合3を作成する。リンク集合データ1={}の場合、リンク集合3={a,b,c,d,e,f}である。
【００７４】
ステップＳ５０３−１において、リンク集合3に属するリンクから、指定した方法によって以降のステップで使用するリンクを計算する。
【００７５】
このときのリンクの計算について、図１７を参照して説明する。図１７は、ステップＳ５０３−１におけるリンクの計算を示す図である。ここでは、図１４のデータ構造にリンクgが追加されたデータ構造を例に挙げて説明する。ステップＳ５０３−１において、リンク集合3に含まれる、中間リンクのすべて、又は上流に存在する中間リンクがすべてリンク集合データ1に含まれる葉リンクのすべてを計算する。リンクa,cがリンク集合データ1に含まれる場合、リンクb,d,e,f,gがリンク集合3に含まれる。このとき、リンク集合3に含まれる中間リンクのすべては{b}であり、リンク集合3に含まれる、上流に存在する中間リンクがすべてリンク集合データ1に含まれる葉リンクのすべては{d,g}である。従って、(リンクID,コスト)={(b,5),(d,1),(g,3)}が出力される。
【００７６】
図１４のデータ構造に対してステップＳ５０３−１を実行すると、以降のステップで計算するリンクは{a,b}となる。
【００７７】
ステップＳ５０３−２において、ステップＳ５０３−１で計算されたリンクの中から選択したリンクをリンク10として、リンク10に対応する構造体データ1-1を作成する。リンクa->bの順で構造体データ1-1を作成することを仮定すると、リンクaが選択された場合、図１８（Ａ）に示すように、ステップＳ５０３−２終了時の構造体データ1-1のデータ1（data1）はNullであり、データ2（data2）はNullであり、データ3（data3）は0である。リンクbが選択された場合も、ステップＳ５０３−２終了時の構造体データ1-1のデータ1（data1）はNullであり、データ2（data2）はNullであり、データ3（data3）は0である。以下、リンクaの構造体データ1-1について説明する。
【００７８】
ステップＳ５０４−１において、構造体データ1-1のデータ1に、構造体データ1-1に対応するリンク10とリンク集合データ1に含まれるリンクを入力する。リンクaがリンク10として選択された場合、構造体データ1-1のデータ1（data1）に、リンク10（a）とリンク集合データ1（={}）の要素を代入する。
【００７９】
ステップＳ５０４−２において、構造体データ1-1のデータ2に、リンク集合データ2の最後尾にリンク10を追加したデータを入力する。リンク10が複数のリンクを結合したものである場合、結合したときの順序を保ちつつ、結合する前のリンクを先頭に追記する。リンクaがリンク10として選択された場合、構造体データ1-1のデータ2（data2）に、リンク集合データ2（={}）の最後尾にリンク10（a）を追加したデータを入力する。
【００８０】
ステップＳ５０４−３において、構造体データ1-1のデータ3に、葉リンクから根ノードまでの経路上のリンクがすべてリンク集合データ1に含まれている葉リンク数を全葉リンク数から引いた値とリンク10のコストをかけ、数値1を足した値を記録する。リンクaがリンク10として選択された場合、構造体データ1-1のデータ3（data3）に、葉リンクから根ノードまでの経路上のリンクがすべてリンク集合データ1に含まれている葉リンク数（=0）を全葉リンク数（=4）から引いた値（4-0=4）にリンク10（a）のコスト（=2）をかけ、数値1（=0）を足した値（=8）を記録する。その結果、図１８（Ｂ）に示す構造体データ1-1が生成される。
【００８１】
ステップＳ５０４−４において、構造体データ1-1のデータ1と同じデータ1を有する構造体データ1-2が集合データ1に存在しないとき、ステップＳ５０４−４−１において、構造体データ1-1を集合データ1に入力する。
【００８２】
ステップＳ５０４−４において、構造体データ1-1のデータ1と同じデータを有する構造体データ1-2が集合データ1に存在し、かつステップＳ５０４−５において構造体データ1-2のデータ3の値が構造体データ1-1のデータ3の値より大きい場合、ステップＳ５０４−５−１において、構造体データ1-1と構造体データ1-2を入れ替える。
【００８３】
ステップＳ５０３−３において、リンク集合3に属するリンクから計算したリンクすべてに対し、ステップＳ５０３−２からＳ５０４−５のステップを繰り返す。ステップＳ５０３−１で生成したリンク={a,b}に対し処理が終わったとき、図１９の集合データ1が生成される。
【００８４】
ステップＳ５０３−４において、構造体データ10が空でなければ、ステップＳ５０３−４−１において、集合データ1から構造体データ10を削除する。
【００８５】
ステップＳ５０３−４及びステップＳ５０３−４−１の後に、ステップＳ５０５−１において、集合データ1内に構造体データ1が1つだけ存在し、そのデータ1にすべてのリンクが含まれている場合、ステップＳ５０６において、構造体データ1のデータ2のリンクの順序を順序の計算結果として、データ3を順序に対する順序コストとして出力する。
【００８６】
ステップＳ５０５−１の条件が満たされない場合、ステップＳ５０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とし、そのデータ1をリンク集合データ1に、データ2をリンク集合データ2に、データ3を数値1に入力する。図１９の集合データ1の例では、集合データ1の要素数が最小値（=1）であるリンクa用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{a}となり、リンク集合データ2は構造体データ10のデータ2である{a}となり、数値1は、構造体データ10のデータ3である8となる。
【００８７】
その後、ステップＳ５０２に戻り計算を進めると、ステップＳ５０２において、リンク集合3=全リンク−リンク集合データ1（={a}）={b,c,d,e,f}となる。
【００８８】
ステップＳ５０３−１において、図１７を用いて説明した方法を用いて以降のステップで使用するリンクを計算すると、{b,c,d}となる。
【００８９】
ステップＳ５０３−２において、リンクb->c->dの順で、それぞれ構造体データ1-1を計算する。リンクbが選択された場合、ステップＳ５０４−１において、構造体データ1-1のデータ1（data1）に、リンク10（b）とリンク集合データ1（={a}）の要素を代入する。ステップＳ５０４−２において、構造体データ1-1のデータ2に、リンク集合データ2（={a}）の最後尾にリンク10（b）を追加したデータを入力する。ステップＳ５０４−３において、構造体データ1-1のデータ3に、葉リンクから根ノードまでの経路上のリンクがすべてリンク集合1に含まれている葉リンク数（=0）を全葉リンク数（=4）から引いた値（4-0=4）にリンク10（b）のコスト（=5）をかけ、数値1（=8）を足した値（=28）を記録する。その結果、図２０（Ａ）に示す構造体データ1-1が生成される。
【００９０】
リンクc及びdが選択されたときも同様に計算すると、図２０（Ｂ）及び（Ｃ）に示す構造体データ1-1が生成される。その結果、図２０（Ｄ）に示す集合データ1が生成される。
【００９１】
ステップＳ５０３−４において、構造体データ10が空でないため、ステップＳ５０３−４−１において、図２１（Ａ）に示すように、構造体データ10を集合データ1から削除する。
【００９２】
ステップＳ５０５−１の条件は満たされないため、ステップＳ５０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とする。ここでは、集合データ1の中でデータ1の要素数が最小値（=1）であるリンクb用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{b}となり、リンク集合データ2は構造体データ10のデータ2である{b}となり、数値1は、構造体データ10のデータ3である20となる。
【００９３】
その後、ステップＳ５０２からステップＳ５０３−３を同様に行うと、図２１（Ｂ）に示す構造体データ1-1、構造体データ1-2、構造体データ1-3が生成される。図２１（Ａ）の集合データ1を見ると、data1が{a,b}になっている構造体データ1が集合データ1内に存在する。このとき、構造体データ1-1作成中におけるステップＳ５０４−４の条件が満たされないため、ステップＳ５０４−５において両者のコストを比較し、ステップＳ５０４−５の条件を満たすかチェックする。この場合は両者とも同じコストであるため交換をしない。
【００９４】
更に計算を進めると、集合データ1は図２２（Ａ）に示すようになる。図２２（Ａ）の左下の構造体データを構造体データ10とすると、図２２（Ｂ）に示す構造体データが生成される。図２２（Ａ）の集合データ1を見ると、集合データ1内にdata1={a,b,c}であるデータが存在する。このとき、構造体データ作成中におけるステップＳ５０４−４の条件が満たされない。また、ステップＳ５０４−５において両者のコストを比較すると、集合データ1内の構造体データのコストが新たにできた構造体データより大きいためステップＳ５０４−５の条件に合致する。よって、ステップＳ５０４−５−１において、集合データ内の構造体データと新たにできた構造体データを入れ替える。
【００９５】
更に計算を進めると、集合データ1は図２３（Ａ）に示すようになる。ここで、図２３（Ａ）の構造体データ1-10、構造体データ1-11、構造体データ1-12、構造体データ1-13の順に計算を進める。
【００９６】
構造体データ1-10に対して計算を進めると、ステップＳ５０４−３終了時の構造体データ1-1は、図２３（Ｂ）に示すようになる。これを集合データ1に入力し、構造体データ1-10を集合データ1から削除する。
【００９７】
構造体データ1-11に対して計算を進めると、ステップＳ５０４−３終了時の構造体データ1-1は、図２３（Ｃ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図２３（Ｂ）の構造体データ）が存在するが、集合データ1の構造体データのほうのコストが小さいので置き換えない。その後、構造体データ1-11を集合データ1から削除する。
【００９８】
構造体データ1-12に対して計算を進めると、ステップＳ５０４−３終了時の構造体データ1-1は、図２３（Ｄ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図２３（Ｂ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-12を集合データ1から削除する。
【００９９】
構造体データ1-13に対して計算を進めると、ステップＳ５０４−３終了時の構造体データ1-1は、図２３（Ｅ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1のデータと置き換えられた図２３（Ｄ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-13を集合データ1から削除する。
【０１００】
最終的に、図２３（Ｆ）に示すように、集合データ1内に構造体データ1が１つだけ存在し、そのデータ1にすべてのリンクが含まれているため、データ2= a->d->c->b->e->fをリンクの順序として、データ3=36を順序コストとして出力する。
【０１０１】
このように、データの共通部分を1本のリンクとするツリー構造でVM間の関係を表せる場合に、個別のVMマイグレーション時間が短くなるよう、VMのデータの送信順をスケジューリングすることが可能になる。
【０１０２】
＜実施例２：ノード単位の順序コストの算出例（データ構造が一般的な場合）＞
図６で説明したノード単位の順序コストの算出において計算量を削減する例について更に詳細に説明する。実施例２では、VMのデータ構造が一般的な場合を仮定する。
【０１０３】
図２４に、一般的なVMのデータ構造の例を示す。VM1、VM2、VM3、VM4のサブデータを中間リンク及び葉リンクに分類する。説明の便宜上、中間リンクは、アルファベットでグループを表し、識別子を数字で表したリンクIDによって区別する。データ構造が一般的な場合、複数のリンクを直列につないだ経路が複数存在し、リンクはいずれか１つのグループに属する。経路の一番下に存在するリンクを葉リンクとし、その他を中間リンクとする。各リンクにはコストが存在する。
【０１０４】
実施例２では、上記のように、共通データである中間リンクのデータを優先して移動させ、固有データである葉リンクのデータを後で送信する。葉リンクに含まれる一時データは処理に伴い頻繁に更新されるため、この部分をマイグレーションの中間部分で送信すると、大量に更新されたデータを送信することになり、マイグレーション時間の増加につながるため、葉リンクはノード内においては最後に送信する。リンクの順序の計算においても、葉リンクの移動順序がノード内において最後になるようにする。
【０１０５】
以下の説明においても、既に定義した構造体データ、集合データ1、リンク集合データ1、リンク集合データ2、リンク集合3を用いる。
【０１０６】
図２５は、一般的なVMのデータ構造のときのリンクの順序及び順序コストを説明するための図である。図２５（Ａ）のデータ構造において、どのリンクの順序も確定していない状態からVM1に対応する経路上のリンクの順序を確定する場合、{a1,b1,c1,d1,1}が順序確定対象である。a1->b1->c1->d1->1の順でリンクの順序を確定する。a2,a3,b2,c2,d2についてはa1,b1,c1,d1と同じグループに属するので、順序確定済みとする。順序確定済みのものは太線の枠で示す。
【０１０７】
あるVMに対応する経路上のリンクを確定対象とする場合、順序のコストをそれまで確定した順序のコスト＋新たに確定対象とするリンクのコストの総和×未確定の経路の数として計算する。図２５（Ａ）に示すように、全リンクが順序未確定の状態で、VM1に対応する経路上のリンクを確定対象とするとき{a1,b1,c1,d1,1}が新たな確定対象なので、新たに確定対象とするリンクのコストの総和は2+1+3+2+1=9である。VM1の経路追加時の未確定の経路（VM1の経路を含む）の数は4なので、順序a1->b1->c1->d1->1の順序コストは9×4=36である。
【０１０８】
次に図２５（Ｂ）に示すように、VM2に対応する経路上のリンクの順序を確定する場合、順序未確定の{f1,g1,2}が順序確定対象である。f1->g1->2の順でリンクの順序を確定すると、先ほど確定したa1->b1->c1->d1->1の後ろにf1->g1->2を追加し、a1->b1->c1->d1->1->f1->g1->2とする。同時にf2,f3についてはf1と同じグループに属するので順序確定済みとする。
【０１０９】
図２５（Ｂ）に示すように、VM2に対応する経路上のリンクを確定対象とするとき、{f1,g1,2}が新たな確定対象なので、新たに確定対象とするリンクのコストの総和は1+2+2=5である。VM2の経路追加時の未確定の経路（VM2の経路を含む）の数は3なので、順序a1->b1->c1->d1->1->f1->g1->2のコストは36+5×3=51である。
【０１１０】
以降、VMを追加するとき、同じ方法でリンクの順序確定と同一グループに属するリンクの順序確定済みチェックを行い、順序コストを計算する。
【０１１１】
データ構造が一般的な場合のノード単位の順序コスト算出方法も、図１６と同じフローチャートで実現できる。説明を簡単にするために、図２６のデータ構造を用いて順序コストの計算について説明する。ここで、a1、a2、b1、b2は中間リンクであり、c、d、e、fは葉リンクである。
【０１１２】
ステップＳ５０１において、変数を初期化する。リンク集合データ1とリンク集合データ2と構造体データ10と集合データ1を空にし、数値1を0にする。
【０１１３】
ステップＳ５０２において、全リンクからリンク集合データ1に含まれるリンクを削除したリンクの集合であるリンク集合3を作成する。リンク集合データ1={}の場合、リンク集合3={a1,a2,b1,b2,c,d,e,f}である。
【０１１４】
ステップＳ５０３−１において、リンク集合3に属するリンクから、指定した方法によって以降のステップで使用するリンクを計算する。
【０１１５】
このときのリンクの計算について、図２７を参照して説明する。図２７は、ステップＳ６０３−１におけるリンクの計算を示す図である。ここでは、図２５のデータ構造を例に挙げて説明する。ステップＳ５０３−１において、リンク集合3に含まれる、中間リンクのすべて、又は上流に存在する中間リンクがすべてリンク集合データ1に含まれる葉リンクのすべてを計算する。リンクa1,a2,a3,b1,b2,c1,c2,d1,d2がリンク集合データ1に含まれる場合、リンク1,2,3,4,e1,f1,f2,f3,g1,h1,i1がリンク集合3に含まれる。このとき、リンク集合3に含まれる中間リンクのすべては{e1,f1,f2,f3,g1,h1,i1}であり、リンク集合3に含まれる、上流に存在する中間リンクがすべてリンク集合データ1に含まれる葉リンクのすべては{1}である。従って、(リンクID,コスト)={(e1,4),(f1,1),(f2,1),(f3,1),(g1,2),(h1,3),(i1,2),(1,1)}が出力される。
【０１１６】
図２６のデータ構造に対してステップＳ５０３−１を実行すると、以降のステップで計算するリンクは{a1,a2,b1,b2}となる。
【０１１７】
ステップＳ５０３−２において、ステップＳ５０３−１で計算されたリンクの中から選択したリンクをリンク10として、リンク10に対応する構造体データ1-1を作成する。リンクa1->a2->b1->b2の順で構造体データ1-1を作成することを仮定すると、リンクa1が選択された場合、図２８（Ａ）に示すように、ステップＳ５０３−２終了時の構造体データ1-1のデータ1（data1）はNullであり、データ2（data2）はNullであり、データ3（data3）は0である。以下、リンクa1の構造体データ1-1について説明する。
【０１１８】
ステップＳ５０４−１において、構造体データ1-1のデータ1に、構造体データ1-1に対応するリンク10とリンク集合データ1に含まれるリンクを入力する。更に、リンク10と同じグループに属するリンク集合を入力する。リンクa1がリンク10として選択された場合、構造体データ1-1のデータ1（data1）に、リンク10（a1）とリンク集合データ1（={}）の要素を代入する。更に、リンク10（a1）と同じグループに属するリンク集合（={a2}）を代入する。
【０１１９】
ステップＳ５０４−２において、構造体データ1-1のデータ2に、リンク集合データ2の最後尾にリンク10を追加したデータを入力する。リンク10が複数のリンクを結合したものである場合、結合したときの順序を保ちつつ、結合する前のリンクを先頭に追記する。リンクa1がリンク10として選択された場合、構造体データ1-1のデータ2（data2）に、リンク集合データ2（={}）の最後尾にリンク10（a1）を追加したデータを入力する。
【０１２０】
ステップＳ５０４−３において、構造体データ1-1のデータ3に、葉リンクから根ノードまでの経路上のリンクがすべてリンク集合データ1に含まれている葉リンク数を全葉リンク数から引いた値とリンク10のコストをかけ、数値1を足した値を記録する。リンクa1がリンク10として選択された場合、構造体データ1-1のデータ3（data3）に、葉リンクから根ノードまでの経路上のリンクがすべてリンク集合データ1に含まれている葉リンク数（=0）を全葉リンク数（=4）から引いた値（4-0=4）にリンク10（a1）のコスト（=2）をかけ、数値1（=0）を足した値（=8）を記録する。その結果、図２８（Ｂ）に示す構造体データ1-1が生成される。
【０１２１】
ステップＳ５０４−４において、構造体データ1-1のデータ1と同じデータ1を有する構造体データ1-2が集合データ1に存在しないとき、ステップＳ５０４−４−１において、構造体データ1-1を集合データ1に入力する。ステップＳ５０３−１で生成したリンク=a1に対し処理が終わったとき、図２９（Ａ）の集合データ1が生成される。
【０１２２】
ステップＳ５０４−４において、構造体データ1-1のデータ1と同じデータを有する構造体データ1-2が集合データ1に存在し、かつステップＳ５０４−５において構造体データ1-2のデータ3の値が構造体データ1-1のデータ3の値より大きい場合、ステップＳ５０４−５−１において、構造体データ1-1と構造体データ1-2を入れ替える。
【０１２３】
リンクa2に対する構造体データを生成する際、ステップＳ５０４−３終了時の構造体データ1-1は図２９（Ｂ）に示すようになる。構造体データ1-1のデータ1（data1）は、先に生成し、集合データ1内に存在する、リンクa1の構造体データのデータ1（data1）と同じa1,a2となる。このとき、ステップＳ５０４−５において、両者のコストを比較し、小さいほうを残す。同じ場合はどちらかを残す。この例では両者のコストは同じであるため、リンクa1に対する構造体データのほうを残す。
【０１２４】
ステップＳ５０３−３において、リンク集合3に属するリンクから計算したリンクすべてに対し、ステップＳ５０３−２からＳ５０４−５のステップを繰り返す。ステップＳ５０３−１で生成したリンク={a1,a2,b1,b2}に対し処理が終わったとき、図２９（Ｃ）の集合データ1が生成される。
【０１２５】
ステップＳ５０３−４において、構造体データ10が空でなければ、ステップＳ５０３−４−１において、集合データ1から構造体データ10を削除する。
【０１２６】
ステップＳ５０３−４及びステップＳ５０３−４−１の後に、ステップＳ５０５−１において、集合データ1内に構造体データ1が1つだけ存在し、そのデータ1にすべてのリンクが含まれている場合、ステップＳ５０６において、構造体データ1のデータ2のリンクの順序を順序の計算結果として、データ3を順序に対する順序コストとして出力する。
【０１２７】
ステップＳ５０５−１の条件が満たされない場合、ステップＳ５０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とし、そのデータ1をリンク集合データ1に、データ2をリンク集合データ2に、データ3を数値1に入力する。図２９（Ｃ）の集合データ1の例では、集合データ1の要素数が最小値（=2）であるリンクa1用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{a1,a2}となり、リンク集合データ2は構造体データ10のデータ2である{a1}となり、数値1は、構造体データ10のデータ3である8となる。
【０１２８】
その後、ステップＳ５０２に戻り計算を進めると、ステップＳ５０２において、リンク集合3=全リンク−リンク集合データ1（={a1,a2}）={b1,b2,c,d,e,f}となる。
【０１２９】
ステップＳ５０３−１において、図２７を用いて説明した方法を用いて以降のステップで使用するリンクを計算すると、{b1,b2,c,d}となる。
【０１３０】
ステップＳ５０３−２において、リンクb1->b2->c->dの順で、それぞれ構造体データ1-1を計算する。リンクb1が選択された場合、ステップＳ５０４−１において、構造体データ1-1のデータ1（data1）に、リンク10（b1）とリンク集合データ1（={a1,a2}）の要素を代入する。更に、リンク10（b1）と同じグループに属するリンク集合（={b2}）を代入する。
【０１３１】
ステップＳ５０４−２において、構造体データ1-1のデータ2に、リンク集合データ2（={a1}）の最後尾にリンク10（b1）を追加したデータを入力する。ステップＳ５０４−３において、構造体データ1-1のデータ3に、葉リンクから根ノードまでの経路上のリンクがすべてリンク集合1に含まれている葉リンク数（=0）を全葉リンク数（=4）から引いた値（4-0=4）にリンク10（b1）のコスト（=5）をかけ、数値1（=8）を足した値（=28）を記録する。その結果、図３０（Ａ）に示す構造体データ1-1が生成される。
【０１３２】
リンクb2、c及びdが選択されたときも同様に計算すると、図３０（Ｂ）、（Ｃ）及び（Ｄ）に示す構造体データ1-1が生成される。リンクb2が選択されたときの構造体データは、ステップＳ５０４−５においてコスト比較され、リンクb1に対する構造体データのほうを残す。その結果、図３０（Ｅ）に示す集合データ1が生成される。
【０１３３】
ステップＳ５０３−４において、構造体データ10が空でないため、ステップＳ５０３−４−１において、図３１に示すように、構造体データ10を集合データ1から削除する。
【０１３４】
ステップＳ５０５−１の条件は満たされないため、ステップＳ５０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とする。ここでは、集合データ1の中でデータ1の要素数が最小値（=2）であるリンクb1用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{b1,b2}となり、リンク集合データ2は構造体データ10のデータ2である{b1}となり、数値1は、構造体データ10のデータ3である20となる。
【０１３５】
更に計算を進めると、集合データ1は図３２（Ａ）に示すようになる。ここで、図３２（Ａ）の構造体データ1-10、構造体データ1-11、構造体データ1-12、構造体データ1-13の順に計算を進める。
【０１３６】
構造体データ1-10に対して計算を進めると、ステップＳ５０４−３終了時の構造体データ1-1は、図３２（Ｂ）に示すようになる。これを集合データ1に入力し、構造体データ1-10を集合データ1から削除する。
【０１３７】
構造体データ1-11に対して計算を進めると、ステップＳ５０４−３終了時の構造体データ1-1は、図３２（Ｃ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図２３（Ｂ）の構造体データ）が存在するが、集合データ1の構造体データのほうのコストが小さいので置き換えない。その後、構造体データ1-11を集合データ1から削除する。
【０１３８】
構造体データ1-12に対して計算を進めると、ステップＳ５０４−３終了時の構造体データ1-1は、図３２（Ｄ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図３２（Ｂ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-12を集合データ1から削除する。
【０１３９】
構造体データ1-13に対して計算を進めると、ステップＳ５０４−３終了時の構造体データ1-1は、図３２（Ｅ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1のデータと置き換えられた図３２（Ｄ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-13を集合データ1から削除する。
【０１４０】
最終的に、図３２（Ｆ）に示すように、集合データ1内に構造体データ1が１つだけ存在し、そのデータ1にすべてのリンクが含まれているため、データ2= a1->d->c->b1->e->fをリンクの順序として、データ3=36を順序コストとして出力する。
【０１４１】
このように、VMのデータ構造が一般的な場合に、個別のVMマイグレーション時間が短くなるよう、VMのデータの送信順をスケジューリングすることが可能になる。
【０１４２】
＜実施例３：リンク単位の順序コストの算出例（データ構造がツリーで表現できる場合）＞
図１１で説明したリンク単位の順序コストの算出において計算量を削減する例について更に詳細に説明する。実施例３では、VMのデータ構造がツリーで表現できることを仮定する。VMのデータ構造は、図１４と同様に表現される。VMのデータ構造をツリーで表現したときのリンクの順序及び順序コストは、図１５と同様に計算される。
【０１４３】
実施例３では、上記のように、共通データである中間リンクのデータを優先して移動させ、固有データである葉リンクのデータを後で送信する。葉リンクに含まれる一時データは処理に伴い頻繁に更新されるため、この部分をマイグレーションの中間部分で送信すると、大量に更新されたデータを送信することになり、マイグレーション時間の増加につながるため、葉リンクはノード内においては最後に送信する。リンクの順序の計算においても、葉リンクの移動順序がノード内において最後になるようにする。
【０１４４】
以下の説明においても、既に定義した構造体データ、集合データ1、リンク集合データ1、リンク集合データ2、リンク集合3を用いる。
【０１４５】
図３３は、リンク単位の順序コスト算出方法のフローチャートである。図３３を説明するときの具体例として、図１４のデータ構造を用いる。
【０１４６】
ステップＳ６０１において、変数を初期化する。リンク集合データ1とリンク集合データ2と構造体データ10と集合データ1を空にし、数値1を0にする。
【０１４７】
ステップＳ６０２において、全リンクからリンク集合データ1に含まれるリンクを削除したリンクの集合であるリンク集合3を作成する。リンク集合データ1={}の場合、リンク集合3={a,b,c,d,e,f}である。
【０１４８】
ステップＳ６０３−１において、リンク集合3に属するリンクから、指定した方法によって以降のステップで使用する経路を計算する。
【０１４９】
このときの経路の計算について、図３４を参照して説明する。図３４は、ステップＳ６０３−１における経路の計算を示す図である。ここでは、図１４のデータ構造にリンクgが追加されたデータ構造を例に挙げて説明する。ステップＳ６０３−１において、リンク集合3に含まれるリンクのうち、リンク集合3に含まれる葉リンクごとに計算した経路を選び出すときに、計算対象とする経路に含む葉リンクと、その上流に存在しリンク集合3に含まれるリンクとを葉リンクが最後に来るように結合した経路を選び出す。リンクa,b,c,d,e,f,gがリンク集合3に含まれる場合、計算対象の葉リンクは{d,e,f,g}である。計算対象の葉リンクがdの場合の経路は、{a->d}であり、計算対象の葉リンクがeの場合の経路は、{b->e}であり、計算対象の葉リンクがfの場合の経路は、{b->f}であり、計算対象の葉リンクがgの場合の経路は、{a->c->g}である。従って、(経路,コスト)={(a->d,3),(b->e,6),(b->f,8),(a->c->g,8)}が出力される。
【０１５０】
図１４のデータ構造に対してステップＳ６０３−１を実行すると、以降のステップで計算する(経路,コスト)は{(a->c,5),(a->d,3),(b->e,6),(b->f,8)}となる。
【０１５１】
ステップＳ６０３−２において、ステップＳ６０３−１で計算された経路の中から選択した経路を経路10として、経路10に対応する構造体データ1-1を作成する。経路(a->c)->(a->d)->(b->e)->(b->f)の順で構造体データ1-1を作成することを仮定すると、経路a->cが選択された場合、図３５（Ａ）に示すように、ステップＳ６０３−２終了時の構造体データ1-1のデータ1（data1）はNullであり、データ2（data2）はNullであり、データ3（data3）は0である。
【０１５２】
ステップＳ６０４−１において、構造体データ1-1のデータ1に、構造体データ1-1に経路10上のリンクとリンク集合データ1に含まれるリンクを入力する。経路a->cが経路10として選択された場合、構造体データ1-1のデータ1（data1）に、経路10上のリンク（a,c）とリンク集合データ1（={}）の要素を代入する。
【０１５３】
ステップＳ６０４−２において、構造体データ1-1のデータ2に、経路10を構成するリンクを、葉リンクが最後に来るように並び替えたものをリンク集合データ2の最後尾に追加したデータを入力する。経路a->cが経路10として選択された場合、構造体データ1-1のデータ2（data2）に、リンク集合データ2（={}）の最後尾に経路10（a->c）を追加したデータを入力する。
【０１５４】
ステップＳ６０４−３において、構造体データ1-1のデータ3に、リンク集合3に含まれる葉リンクの数と経路10のコストをかけ、数値1を足した値を記録する。経路a->cが経路10として選択された場合、構造体データ1-1のデータ3（data3）に、リンク集合3に含まれる葉リンクの数（=4）と経路10のコスト（=5）をかけ、数値1（=0）を足した値（=20）を記録する。その結果、図３５（Ｂ）に示す構造体データ1-1が生成される。
【０１５５】
ステップＳ６０４−４において、構造体データ1-1のデータ1と同じデータ1を有する構造体データ1-2が集合データ1に存在しないとき、ステップＳ６０４−４−１において、構造体データ1-1を集合データ1に入力する。
【０１５６】
ステップＳ６０４−４において、構造体データ1-1のデータ1と同じデータを有する構造体データ1-2が集合データ1に存在し、かつステップＳ６０４−５において構造体データ1-2のデータ3の値が構造体データ1-1のデータ3の値より大きい場合、ステップＳ６０４−５−１において、構造体データ1-1と構造体データ1-2を入れ替える。
【０１５７】
ステップＳ６０３−３において、リンク集合3に属するリンクから計算した経路すべてに対し、ステップＳ６０３−２からＳ６０４−５のステップを繰り返す。ステップＳ６０３−１で生成した経路={(a->c,5),(a->d,3),(b->e,6),(b->f,8)}に対し処理が終わったとき、図３６の集合データ1が生成される。
【０１５８】
ステップＳ６０３−４において、構造体データ10が空でなければ、ステップＳ６０３−４−１において、集合データ1から構造体データ10を削除する。
【０１５９】
ステップＳ６０３−４及びステップＳ６０３−４−１の後に、ステップＳ６０５−１において、集合データ1内に構造体データ1が1つだけ存在し、そのデータ1にすべてのリンクが含まれている場合、ステップＳ６０６において、構造体データ1のデータ2のリンクの順序を順序の計算結果として、データ3を順序に対する順序コストとして出力する。
【０１６０】
ステップＳ６０５−１の条件が満たされない場合、ステップＳ６０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とし、そのデータ1をリンク集合データ1に、データ2をリンク集合データ2に、データ3を数値1に入力する。図３６の集合データ1の例では、集合データ1の要素数が最小値（=2）である経路a->c用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{a,c}となり、リンク集合データ2は構造体データ10のデータ2である{a->c}となり、数値1は、構造体データ10のデータ3である20となる。
【０１６１】
その後、ステップＳ６０２に戻り計算を進めると、ステップＳ６０２において、リンク集合3=全リンク−リンク集合データ1（={a,c}）={b,d,e,f}となる。
【０１６２】
ステップＳ６０３−１において、図３４を用いて説明した方法を用いて以降のステップで使用する経路を計算すると、{(d,1),(b->e,6),(b->f,8)}となる。
【０１６３】
ステップＳ６０３−２において、経路(b->e)->(d)->(b->f)の順で、それぞれ構造体データ1-1を計算する。経路b->eが選択された場合、ステップＳ６０４−１において、構造体データ1-1のデータ1（data1）に、経路10上のリンク（b,e）とリンク集合データ1（={a,c}）の要素を代入する。ステップＳ６０４−２において、構造体データ1-1のデータ2に、リンク集合データ2（={a->c}）の最後尾に経路10を追加したデータ（a->c->b->e）を入力する。ステップＳ６０４−３において、構造体データ1-1のデータ3に、リンク集合3に含まれている葉リンク数（=3）に経路10のコスト（=6）をかけ、数値1（=20）を足した値（=38）を記録する。その結果、図３７（Ａ）に示す構造体データ1-1が生成される。
【０１６４】
経路d及び経路b->fが選択されたときも同様に計算すると、図３７（Ｂ）及び（Ｃ）に示す構造体データ1-1が生成される。その結果、図３７（Ｄ）に示す集合データ1が生成される。
【０１６５】
ステップＳ６０３−４において、構造体データ10が空でないため、ステップＳ６０３−４−１において、図３８（Ａ）に示すように、構造体データ10を集合データ1から削除する。
【０１６６】
ステップＳ６０５−１の条件は満たされないため、ステップＳ６０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とする。ここでは、集合データ1の中でデータ1の要素数が最小値（=2）である経路a->d用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{a,d}となり、リンク集合データ2は構造体データ10のデータ2である{a->d}となり、数値1は、構造体データ10のデータ3である12となる。
【０１６７】
その後、ステップＳ６０２からステップＳ６０３−３を同様に行うと、図３８（Ｂ）に示す構造体データ1-1、構造体データ1-2、構造体データ1-3が生成される。図３８（Ａ）の集合データ1を見ると、data1が{a,c,d}になっている構造体データ1が集合データ1内に存在する。このとき、構造体データ1-1作成中におけるステップＳ６０４−４の条件が満たされないため、ステップＳ６０４−５において両者のコストを比較し、ステップＳ６０４−５の条件を満たすかチェックする。この場合は図３８（Ｂ）の構造体データ1-1のコストの方が小さいため、入れ替える。その結果、集合データ1は図３８（Ｃ）になる。
【０１６８】
更に計算を進めると、集合データ1は図３９（Ａ）に示すようになる。ここで、図３９（Ａ）の構造体データ1-10、構造体データ1-11、構造体データ1-12、構造体データ1-13の順に計算を進める。
【０１６９】
構造体データ1-10に対して計算を進めると、ステップＳ６０４−３終了時の構造体データ1-1は、図３９（Ｂ）に示すようになる。これを集合データ1に入力し、構造体データ1-10を集合データ1から削除する。
【０１７０】
構造体データ1-11に対して計算を進めると、ステップＳ６０４−３終了時の構造体データ1-1は、図３９（Ｃ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図３９（Ｂ）の構造体データ）が存在するが、集合データ1の構造体データのほうのコストが小さいので置き換えない。その後、構造体データ1-11を集合データ1から削除する。
【０１７１】
構造体データ1-12に対して計算を進めると、ステップＳ６０４−３終了時の構造体データ1-1は、図３９（Ｄ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図３９（Ｂ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-12を集合データ1から削除する。
【０１７２】
構造体データ1-13に対して計算を進めると、ステップＳ６０４−３終了時の構造体データ1-1は、図３９（Ｅ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1のデータと置き換えられた図３９（Ｄ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-13を集合データ1から削除する。
【０１７３】
最終的に、図３９（Ｆ）に示すように、集合データ1内に構造体データ1が１つだけ存在し、そのデータ1にすべてのリンクが含まれているため、データ2= a->d->c->b->e->fをリンクの順序として、データ3=36を順序コストとして出力する。
【０１７４】
次に、別の順序コスト算出方法について説明する。
【０１７５】
図４０は、リンク単位の順序コスト算出方法のフローチャートである。図４０を説明するときの具体例として、図１４のデータ構造を用いる。図４０のフローチャートは、ステップＳ７０３−１、Ｓ７０４−２、Ｓ７０４−３を除き、図３３のフローチャートと同じである。
【０１７６】
ステップＳ７０１において、変数を初期化する。リンク集合データ1とリンク集合データ2と構造体データ10と集合データ1を空にし、数値1を0にする。
【０１７７】
ステップＳ７０２において、全リンクからリンク集合データ1に含まれるリンクを削除したリンクの集合であるリンク集合3を作成する。リンク集合データ1={}の場合、リンク集合3={a,b,c,d,e,f}である。
【０１７８】
ステップＳ７０３−１において、リンク集合3に属するリンクから、指定した方法によって以降のステップで使用する経路を計算する。
【０１７９】
このときの経路の計算について、図４１を参照して説明する。図４１は、ステップＳ７０３−１における経路の計算を示す図である。ここでは、図１４のデータ構造にリンクgが追加されたデータ構造を例に挙げて説明する。ステップＳ７０３−１において、リンク集合3に含まれるリンクのうち、リンク集合3に含まれる葉リンクごとに計算した経路を選び出すときに、計算対象とする経路に含む葉リンクと、その上流に位置する中間リンクのうち、下流側の端点である分岐ノードにおいて、下流側リンクのうち該葉リンク方向のリンク以外のすべてのリンクが、その下流にリンク集合データ1に含まれる葉リンクが存在するような中間リンクとを葉リンクが最後に来るように結合した経路を選び出す。リンクdがリンク集合データ1に含まれる場合、リンクa,b,c,e,f,gがリンク集合3に含まれる。このとき、計算対象の葉リンクは{e,f,g}である。計算対象の葉リンクがeの場合の経路は、{e}である。この経路を選び出すときに、リンクbの下流側分岐ノードにリンク集合3に属する葉リンク（=f）が存在するため、bは含めない。計算対象の葉リンクがfの場合の経路は、{f}である。この経路を選び出すときに、リンクbの下流側分岐ノードにリンク集合3に属する葉リンク（=e）が存在するため、bは含めない。計算対象の葉リンクがgの場合の経路は、{a->c->g}である。この経路を選び出すときに、リンクa,cの下流側分岐ノードに、リンクg方向以外の下流側リンクすべてに、リンク集合１に属する葉リンクが下流方向に存在する、もしくはg方向にのみ下流側リンクが存在するため、a,cを含める。従って、(経路,コスト)={(e,1),(f,3),(a->c->g,8)}が出力される。
【０１８０】
図１４のデータ構造に対してステップＳ７０３−１を実行すると、以降のステップで計算する(経路,コスト)は{(c,3),(d,1),(e,1),(f,3)}となる。
【０１８１】
ステップＳ７０３−２において、ステップＳ７０３−１で計算された経路の中から選択した経路を経路10として、経路10に対応する構造体データ1-1を作成する。経路(c)->(d)->(e)->(f)の順で構造体データ1-1を作成することを仮定すると、経路cが選択された場合、図４２（Ａ）に示すように、ステップＳ７０３−２終了時の構造体データ1-1のデータ1（data1）はNullであり、データ2（data2）はNullであり、データ3（data3）は0である。
【０１８２】
ステップＳ７０４−１において、構造体データ1-1のデータ1に、構造体データ1-1に経路10上のリンクとリンク集合データ1に含まれるリンクを入力する。経路cが経路10として選択された場合、構造体データ1-1のデータ1（data1）に、経路10上のリンク（c）とリンク集合データ1（={}）の要素を代入する。
【０１８３】
ステップＳ７０４−２において、構造体データ1-1のデータ2に、経路10を構成するリンクを、葉リンクが最後に来るように並び替えたものをリンク集合データ2の先頭に追加したデータを入力する。経路cが経路10として選択された場合、構造体データ1-1のデータ2（data2）に、リンク集合データ2（={}）の先頭に経路10（c）を追加したデータを入力する。
【０１８４】
ステップＳ７０４−３において、構造体データ1-1のデータ3に、リンク集合データ1に含まれる葉リンクの数に1を足した値に経路10のコストをかけ、数値1を足した値を記録する。経路cが経路10として選択された場合、構造体データ1-1のデータ3（data3）に、リンク集合データ1に含まれる葉リンクの数に1を足した値（0+1=1）と経路10のコスト（=3）をかけ、数値1（=0）を足した値（=3）を記録する。その結果、図４２（Ｂ）に示す構造体データ1-1が生成される。
【０１８５】
ステップＳ７０４−４において、構造体データ1-1のデータ1と同じデータ1を有する構造体データ1-2が集合データ1に存在しないとき、ステップＳ７０４−４−１において、構造体データ1-1を集合データ1に入力する。
【０１８６】
ステップＳ７０４−４において、構造体データ1-1のデータ1と同じデータを有する構造体データ1-2が集合データ1に存在し、かつステップＳ７０４−５において構造体データ1-2のデータ3の値が構造体データ1-1のデータ3の値より大きい場合、ステップＳ７０４−５−１において、構造体データ1-1と構造体データ1-2を入れ替える。
【０１８７】
ステップＳ７０３−３において、リンク集合3に属するリンクから計算した経路すべてに対し、ステップＳ７０３−２からＳ７０４−５のステップを繰り返す。ステップＳ７０３−１で生成した経路={(c,3),(d,1),(e,1),(f,3)}に対し処理が終わったとき、図４３の集合データ1が生成される。
【０１８８】
ステップＳ７０３−４において、構造体データ10が空でなければ、ステップＳ７０３−４−１において、集合データ1から構造体データ10を削除する。
【０１８９】
ステップＳ７０３−４及びステップＳ７０３−４−１の後に、ステップＳ７０５−１において、集合データ1内に構造体データ1が1つだけ存在し、そのデータ1にすべてのリンクが含まれている場合、ステップＳ７０６において、構造体データ1のデータ2のリンクの順序を順序の計算結果として、データ3を順序に対する順序コストとして出力する。
【０１９０】
ステップＳ７０５−１の条件が満たされない場合、ステップＳ７０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とし、そのデータ1をリンク集合データ1に、データ2をリンク集合データ2に、データ3を数値1に入力する。図４３の集合データ1の例では、集合データ1の要素数が最小値（=1）である経路c用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{c}となり、リンク集合データ2は構造体データ10のデータ2である{c}となり、数値1は、構造体データ10のデータ3である3となる。
【０１９１】
その後、ステップＳ７０２に戻り計算を進めると、ステップＳ７０２において、リンク集合3=全リンク−リンク集合データ1（={c}）={a,b,d,e,f}となる。
【０１９２】
ステップＳ７０３−１において、図４１を用いて説明した方法を用いて以降のステップで使用する経路を計算すると、{(a->d,3),(e,1),(f,3)}となる。
【０１９３】
ステップＳ７０３−２において、経路(a->d)->(e)->(f)の順で、それぞれ構造体データ1-1を計算する。経路a->dが選択された場合、ステップＳ７０４−１において、構造体データ1-1のデータ1（data1）に、経路10上のリンク（a,d）とリンク集合データ1（={c}）の要素を代入する。ステップＳ７０４−２において、構造体データ1-1のデータ2に、リンク集合データ2（={c}）の先頭に経路10を追加したデータ（a->d->c）を入力する。ステップＳ７０４−３において、構造体データ1-1のデータ3に、リンク集合データ1に含まれる葉リンクの数に1を足した値（1+1=2）に経路10のコスト（=3）をかけ、数値1（=3）を足した値（=9）を記録する。その結果、図４４（Ａ）に示す構造体データ1-1が生成される。
【０１９４】
経路e及び経路fが選択されたときも同様に計算すると、図４４（Ｂ）及び（Ｃ）に示す構造体データ1-1が生成される。その結果、図４４（Ｄ）に示す集合データ1が生成される。
【０１９５】
ステップＳ７０３−４において、構造体データ10が空でないため、ステップＳ７０３−４−１において、図４５（Ａ）に示すように、構造体データ10を集合データ1から削除する。
【０１９６】
ステップＳ７０５−１の条件は満たされないため、ステップＳ７０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とする。ここでは、集合データ1の中でデータ1の要素数が最小値（=1）である経路d用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{d}となり、リンク集合データ2は構造体データ10のデータ2である{d}となり、数値1は、構造体データ10のデータ3である1となる。
【０１９７】
その後、ステップＳ７０２からステップＳ７０３−３を同様に行うと、図４５（Ｂ）に示す構造体データ1-1、構造体データ1-2、構造体データ1-3が生成される。図４５（Ａ）の集合データ1を見ると、data1が{a,c,d}になっている構造体データ1が集合データ1内に存在する。このとき、構造体データ1-1作成中におけるステップＳ７０４−４の条件が満たされないため、ステップＳ７０４−５において両者のコストを比較し、ステップＳ７０４−５の条件を満たすかチェックする。この場合は図４５（Ｂ）の構造体データ1-1のコストの方が小さいため、入れ替える。その結果、集合データ1は図４５（Ｃ）になる。
【０１９８】
更に計算を進めると、集合データ1は図４６（Ａ）に示すようになる。ここで、図４６（Ａ）の構造体データ1-10、構造体データ1-11、構造体データ1-12、構造体データ1-13の順に計算を進める。
【０１９９】
構造体データ1-10に対して計算を進めると、ステップＳ７０４−３終了時の構造体データ1-1は、図４６（Ｂ）に示すようになる。これを集合データ1に入力し、構造体データ1-10を集合データ1から削除する。
【０２００】
構造体データ1-11に対して計算を進めると、ステップＳ７０４−３終了時の構造体データ1-1は、図４６（Ｃ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図４６（Ｂ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-11を集合データ1から削除する。
【０２０１】
構造体データ1-12に対して計算を進めると、ステップＳ７０４−３終了時の構造体データ1-1は、図４６（Ｄ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図４６（Ｃ）の構造体データ）が存在するが、集合データ1の構造体データのほうのコストが小さいので置き換えない。その後、構造体データ1-12を集合データ1から削除する。
【０２０２】
構造体データ1-13に対して計算を進めると、ステップＳ７０４−３終了時の構造体データ1-1は、図４６（Ｅ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1のデータと置き換えられた図４６（Ｃ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが小さいので置き換えない。その後、構造体データ1-13を集合データ1から削除する。
【０２０３】
最終的に、図４６（Ｆ）に示すように、集合データ1内に構造体データ1が１つだけ存在し、そのデータ1にすべてのリンクが含まれているため、データ2= a->d->c->b->e->fをリンクの順序として、データ3=36を順序コストとして出力する。
【０２０４】
次に、図３３のフローチャートにおいて計算量を削減するための方法について説明する。以下の説明では図３３のフローチャートを参照して説明するが、図４０のフローチャートにも適用可能である。
【０２０５】
図３３では、ステップＳ６０３−１において計算されたすべての経路に対して順序コストの計算を進めるが、順序コストの計算を進める経路を、コストが小さい順に予め与えられた数に制限してもよい。すなわち、ステップＳ６０３−１において、例えば候補経路の選択方法の変更指示（計算量の削減指示）を受信した場合に、リンク集合3に属するリンクから指定した方法によって計算された経路のうち、コストが最小の経路からk番目までの経路を選ぶ。
【０２０６】
図３６の集合データ1から経路a->c用の構造体データ1を取り出し、構造体データ10とした場合について説明する。このとき、リンク集合データ1は構造体データ10のデータ1である{a,c}となり、リンク集合データ2は構造体データ10のデータ2である{a->c}となり、数値1は、構造体データ10のデータ3である20となる。
【０２０７】
その後、ステップＳ６０２に戻り計算を進めると、ステップＳ６０２において、リンク集合3=全リンク−リンク集合データ1（={a,c}）={b,d,e,f}となる。
【０２０８】
ステップＳ６０３−１において、図３４を用いて説明した方法を用いて以降のステップで使用する経路を計算すると、{(d,1),(b->e,6),(b->f,8)}となる。ここで、計算量の削減指示を受信したことを想定する。
【０２０９】
計算量の削減指示がなければ、経路(b->e)->(d)->(b->f)の順で、それぞれ構造体データ1-1を計算するが、計算量の削減指示に従い、ステップＳ６０３−２において、コストの小さい順に２つ目までの経路に対する構造体データ1-1を計算する。経路dのコストは1*3=3であり、経路b->eのコストは6*3=18であり、経路b->fのコストは8*3=24である。従って、経路d及びb->eに対する構造体データを生成する。経路dが選択された場合、図４７（Ａ）に示す構造体データ1-1が生成される。経路b->eが選択された場合、図４７（Ｂ）に示す構造体データ1-1が生成される。その結果、図４７（Ｃ）に示す集合データ1が生成される。図４７（Ｃ）の集合データ1と図３７（Ｄ）の集合データ1を比べると、集合データ1の要素数が少なくなっていることが分かる。
【０２１０】
上記の例では、候補経路の選択方法の変更指示が計算途中で受信された場合を示しているが、候補経路の選択方法の変更指示は用いられなくてもよい。すなわち、ステップＳ６０３−１において、リンク集合3に属するリンクから指定した方法によって計算された経路のうち、コストが最小の経路からk番目までの経路を選んでもよい。
【０２１１】
このように、データの共通部分を1本のリンクとするツリー構造でVM間の関係を表せる場合に、個別のVMマイグレーション時間が短くなるよう、VMのデータの送信順をスケジューリングすることが可能になる。
【０２１２】
＜実施例４：リンク単位の順序コストの算出例（データ構造が一般的な場合）＞
図１１で説明したリンク単位の順序コストの算出において計算量を削減する例について更に詳細に説明する。実施例４では、VMのデータ構造が一般的な場合を仮定する。VMのデータ構造は、図２４と同様に表現される。VMのデータ構造をツリーで表現したときのリンクの順序及び順序コストは、図２５と同様に計算される。
【０２１３】
実施例４では、上記のように、共通データである中間リンクのデータを優先して移動させ、固有データである葉リンクのデータを後で送信する。葉リンクに含まれる一時データは処理に伴い頻繁に更新されるため、この部分をマイグレーションの中間部分で送信すると、大量に更新されたデータを送信することになり、マイグレーション時間の増加につながるため、葉リンクはノード内においては最後に送信する。リンクの順序の計算においても、葉リンクの移動順序がノード内において最後になるようにする。
【０２１４】
以下の説明においても、既に定義した構造体データ、集合データ1、リンク集合データ1、リンク集合データ2、リンク集合3を用いる。
【０２１５】
データ構造が一般的な場合のノード単位の順序コスト算出方法も、図３３と同じフローチャートで実現できる。説明を簡単にするために、図２６のデータ構造を用いて順序コストの計算について説明する。ここで、a1、a2、b1、b2は中間リンクであり、c、d、e、fは葉リンクである。
【０２１６】
ステップＳ６０１において、変数を初期化する。リンク集合データ1とリンク集合データ2と構造体データ10と集合データ1を空にし、数値1を0にする。
【０２１７】
ステップＳ６０２において、全リンクからリンク集合データ1に含まれるリンクを削除したリンクの集合であるリンク集合3を作成する。リンク集合データ1={}の場合、リンク集合3={a1,a2,b1,b2,c,d,e,f}である。
【０２１８】
ステップＳ６０３−１において、リンク集合3に属するリンクから、指定した方法によって以降のステップで使用する経路を計算する。
【０２１９】
このときの経路の計算について、図４８を参照して説明する。図４８は、ステップＳ６０３−１における経路の計算を示す図である。ここでは、図２５のデータ構造を例に挙げて説明する。ステップＳ６０３−１において、リンク集合3に含まれるリンクのうち、リンク集合3に含まれる葉リンクごとに計算した経路を選び出すときに、計算対象とする経路に含む葉リンクと、その上流に存在しリンク集合3に含まれるリンクとを葉リンクが最後に来るように結合した経路を選び出す。リンクe1,f1,f2,f3,g1,h1,i1,2,3,4がリンク集合3に含まれる場合、計算対象の葉リンクは{2,3,4}である。計算対象の葉リンクが2の場合の経路は、{f1->g1->2}であり、計算対象の葉リンクが3の場合の経路は、{e1->f2->3}であり、計算対象の葉リンクが4の場合の経路は、{f3->h1->i1->4}である。従って、(経路,コスト)={(f1->g1->2,5),(e1->f2->3,13),(f3->h1->i1->4,8)}が出力される。
【０２２０】
図２６のデータ構造に対してステップＳ６０３−１を実行すると、以降のステップで計算する(経路,コスト)は{(a1->c,5),(a2->d,3),(b1->e,6),(b2->f,8)}となる。
【０２２１】
ステップＳ６０３−２において、ステップＳ６０３−１で計算された経路の中から選択した経路を経路10として、経路10に対応する構造体データ1-1を作成する。経路(a1->c)->(a2->d)->(b1->e)->(b2->f)の順で構造体データ1-1を作成することを仮定すると、経路a1->cが選択された場合、図４９（Ａ）に示すように、ステップＳ６０３−２終了時の構造体データ1-1のデータ1（data1）はNullであり、データ2（data2）はNullであり、データ3（data3）は0である。
【０２２２】
ステップＳ６０４−１において、構造体データ1-1のデータ1に、構造体データ1-1に経路10上のリンクとリンク集合データ1に含まれるリンクを入力する。更に、経路10と同じグループに属するリンク集合を入力する。経路a1->cが経路10として選択された場合、構造体データ1-1のデータ1（data1）に、経路10上のリンク（a1,c）とリンク集合データ1（={}）の要素を代入する。更に、経路10と同じグループに属するリンク集合（={a2}）を代入する。
【０２２３】
ステップＳ６０４−２において、構造体データ1-1のデータ2に、経路10を構成するリンクを、葉リンクが最後に来るように並び替えたものをリンク集合データ2の最後尾に追加したデータを入力する。経路a1->cが経路10として選択された場合、構造体データ1-1のデータ2（data2）に、リンク集合データ2（={}）の最後尾に経路10（a1->c）を追加したデータを入力する。
【０２２４】
ステップＳ６０４−３において、構造体データ1-1のデータ3に、リンク集合3に含まれる葉リンクの数と経路10のコストをかけ、数値1を足した値を記録する。経路a1->cが経路10として選択された場合、構造体データ1-1のデータ3（data3）に、リンク集合3に含まれる葉リンクの数（=4）と経路10のコスト（=5）をかけ、数値1（=0）を足した値（=20）を記録する。その結果、図４９（Ｂ）に示す構造体データ1-1が生成される。
【０２２５】
ステップＳ６０４−４において、構造体データ1-1のデータ1と同じデータ1を有する構造体データ1-2が集合データ1に存在しないとき、ステップＳ６０４−４−１において、構造体データ1-1を集合データ1に入力する。
【０２２６】
ステップＳ６０４−４において、構造体データ1-1のデータ1と同じデータを有する構造体データ1-2が集合データ1に存在し、かつステップＳ６０４−５において構造体データ1-2のデータ3の値が構造体データ1-1のデータ3の値より大きい場合、ステップＳ６０４−５−１において、構造体データ1-1と構造体データ1-2を入れ替える。
【０２２７】
ステップＳ６０３−３において、リンク集合3に属するリンクから計算した経路すべてに対し、ステップＳ６０３−２からＳ６０４−５のステップを繰り返す。ステップＳ６０３−１で生成した経路={(a1->c,5),(a2->d,3),(b1->e,6),(b2->f,8)}に対し処理が終わったとき、図５０の集合データ1が生成される。
【０２２８】
ステップＳ６０３−４において、構造体データ10が空でなければ、ステップＳ６０３−４−１において、集合データ1から構造体データ10を削除する。
【０２２９】
ステップＳ６０３−４及びステップＳ６０３−４−１の後に、ステップＳ６０５−１において、集合データ1内に構造体データ1が1つだけ存在し、そのデータ1にすべてのリンクが含まれている場合、ステップＳ６０６において、構造体データ1のデータ2のリンクの順序を順序の計算結果として、データ3を順序に対する順序コストとして出力する。
【０２３０】
ステップＳ６０５−１の条件が満たされない場合、ステップＳ６０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とし、そのデータ1をリンク集合データ1に、データ2をリンク集合データ2に、データ3を数値1に入力する。図５０の集合データ1の例では、集合データ1の要素数が最小値（=3）である経路a1->c用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{a1,a2,c}となり、リンク集合データ2は構造体データ10のデータ2である{a1->c}となり、数値1は、構造体データ10のデータ3である20となる。
【０２３１】
その後、ステップＳ６０２に戻り計算を進めると、ステップＳ６０２において、リンク集合3=全リンク−リンク集合データ1（={a1,a2,c}）={b1,b2,d,e,f}となる。
【０２３２】
ステップＳ６０３−１において、図４８に示す方法で以降のステップで使用する経路を計算すると、{(d,1),(b1->e,6),(b2->f,8)}となる。
【０２３３】
ステップＳ６０３−２において、経路(b1->e)->(d)->(b2->f)の順で、それぞれ構造体データ1-1を計算する。経路b1->eが選択された場合、ステップＳ６０４−１において、構造体データ1-1のデータ1（data1）に、経路10上のリンク（b1,e）とリンク集合データ1（={a1,a2,c}）の要素を代入する。更に、経路10と同じグループに属するリンク集合（={b2}）を代入する。ステップＳ６０４−２において、構造体データ1-1のデータ2に、リンク集合データ2（={a1->c}）の最後尾に経路10を追加したデータ（a1->c->b1->e）を入力する。ステップＳ６０４−３において、構造体データ1-1のデータ3に、リンク集合3に含まれている葉リンク数（=3）に経路10のコスト（=6）をかけ、数値1（=20）を足した値（=38）を記録する。その結果、図５１（Ａ）に示す構造体データ1-1が生成される。
【０２３４】
経路d及び経路b2->fが選択されたときも同様に計算すると、図５１（Ｂ）及び（Ｃ）に示す構造体データ1-1が生成される。その結果、図５１（Ｄ）に示す集合データ1が生成される。
【０２３５】
ステップＳ６０３−４において、構造体データ10が空でないため、ステップＳ６０３−４−１において、図５２（Ａ）に示すように、構造体データ10を集合データ1から削除する。
【０２３６】
ステップＳ６０５−１の条件は満たされないため、ステップＳ６０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とする。ここでは、集合データ1の中でデータ1の要素数が最小値（=3）である経路a2->d用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{a1,a2,d}となり、リンク集合データ2は構造体データ10のデータ2である{a2->d}となり、数値1は、構造体データ10のデータ3である12となる。
【０２３７】
その後、ステップＳ６０２からステップＳ６０３−３を同様に行うと、図５２（Ｂ）に示す構造体データ1-1、構造体データ1-2、構造体データ1-3が生成される。図５２（Ａ）の集合データ1を見ると、data1が{a1,a2,c,d}になっている構造体データ1が集合データ1内に存在する。このとき、構造体データ1-1作成中におけるステップＳ６０４−４の条件が満たされないため、ステップＳ６０４−５において両者のコストを比較し、ステップＳ６０４−５の条件を満たすかチェックする。この場合は図５２（Ｂ）の構造体データ1-1のコストの方が小さいため、入れ替える。その結果、集合データ1は図５２（Ｃ）になる。
【０２３８】
更に計算を進めると、集合データ1は図５３（Ａ）に示すようになる。ここで、図５３（Ａ）の構造体データ1-10、構造体データ1-11、構造体データ1-12、構造体データ1-13の順に計算を進める。
【０２３９】
構造体データ1-10に対して計算を進めると、ステップＳ６０４−３終了時の構造体データ1-1は、図５３（Ｂ）に示すようになる。これを集合データ1に入力し、構造体データ1-10を集合データ1から削除する。
【０２４０】
構造体データ1-11に対して計算を進めると、ステップＳ６０４−３終了時の構造体データ1-1は、図５３（Ｃ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図５３（Ｂ）の構造体データ）が存在するが、集合データ1の構造体データのほうのコストが小さいので置き換えない。その後、構造体データ1-11を集合データ1から削除する。
【０２４１】
構造体データ1-12に対して計算を進めると、ステップＳ６０４−３終了時の構造体データ1-1は、図５３（Ｄ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図５３（Ｂ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-12を集合データ1から削除する。
【０２４２】
構造体データ1-13に対して計算を進めると、ステップＳ６０４−３終了時の構造体データ1-1は、図５３（Ｅ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1のデータと置き換えられた図５３（Ｄ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-13を集合データ1から削除する。
【０２４３】
最終的に、図５３（Ｆ）に示すように、集合データ1内に構造体データ1が１つだけ存在し、そのデータ1にすべてのリンクが含まれているため、データ2= a2->d->c->b1->e->fをリンクの順序として、データ3=36を順序コストとして出力する。
【０２４４】
次に、図４０を参照して別の順序コスト算出方法について説明する。図４０を説明するときの具体例として、図２６のデータ構造を用いる。
【０２４５】
ステップＳ７０１において、変数を初期化する。リンク集合データ1とリンク集合データ2と構造体データ10と集合データ1を空にし、数値1を0にする。
【０２４６】
ステップＳ７０２において、全リンクからリンク集合データ1に含まれるリンクを削除したリンクの集合であるリンク集合3を作成する。リンク集合データ1={}の場合、リンク集合3={a1,a2,b1,b2,c,d,e,f}である。
【０２４７】
ステップＳ７０３−１において、リンク集合3に属するリンクから、指定した方法によって以降のステップで使用する経路を計算する。
【０２４８】
このときの経路の計算について、図５４を参照して説明する。図５４は、ステップＳ７０３−１における経路の計算を示す図である。ここでは、図２５のデータ構造を例に挙げて説明する。ステップＳ７０３−１において、リンク集合3に含まれるリンクのうち、リンク集合3に含まれる葉リンクごとに計算した経路を選び出すときに、計算対象とする経路に含む葉リンクと、該葉リンクの上流に位置するリンク集合3に含まれる中間リンクのうち、該中間リンクと同じグループに属し下流側にリンク集合データ1に含まれる葉リンクが存在する中間リンクの数が、グループに属するリンク数から1を引いた値である中間リンクとを葉リンクが最後に来るように結合した経路を選び出す。リンクg1,2がリンク集合データ1に含まれる場合、リンクa1,a2,a3,b1,b2,c1,c2,d1,d2,e1,f1,f2,f3,h1,i1,1,3,4がリンク集合3に含まれる。このとき、計算対象の葉リンクは{1,3,4}である。計算対象の葉リンクが1の場合の経路は、{d1->1}である。この経路を選び出すときに、リンクd1は同じグループのリンクd2が経路VM2に存在し、その葉リンクはリンク集合データ1に属する。リンクd1と同じグループに属するリンク数は2であるため、d1は経路を選び出す条件に合致する。リンクa1は同じグループのリンクa2が経路VM2に存在し、リンクd3が経路VM3に存在し、各経路の葉リンクでリンク集合データ1に属するのはVMの葉リンクの2のみである。よって、リンクa1と同じグループに属し下流側にリンク集合データ1に含まれる葉リンクが存在する中間リンクの数は1である。グループに属するリンク数は3であるため、a1は経路を選び出す条件に合致しない。よって、a1は上記の経路に含まれない。同様の理由でb1、c1も上記の経路に含まれない。同様に計算すると、計算対象の葉リンクが3の場合の経路は、{e1->3}であり、計算対象の葉リンクが4の場合の経路は、{h1->i1->4}である。従って、(経路,コスト)={(d1->1,3),(e1->3,7),(h1->i1->4,7)}が出力される。
【０２４９】
図２６のデータ構造に対してステップＳ７０３−１を実行すると、以降のステップで計算する(経路,コスト)は{(c,3),(d,1),(e,1),(f,3)}となる。
【０２５０】
ステップＳ７０３−２において、ステップＳ７０３−１で計算された経路の中から選択した経路を経路10として、経路10に対応する構造体データ1-1を作成する。経路(c)->(d)->(e)->(f)の順で構造体データ1-1を作成することを仮定すると、経路cが選択された場合、図５５（Ａ）に示すように、ステップＳ７０３−２終了時の構造体データ1-1のデータ1（data1）はNullであり、データ2（data2）はNullであり、データ3（data3）は0である。
【０２５１】
ステップＳ７０４−１において、構造体データ1-1のデータ1に、構造体データ1-1に経路10上のリンクとリンク集合データ1に含まれるリンクを入力する。更に、経路10と同じグループに属するリンク集合を入力する。経路cが経路10として選択された場合、構造体データ1-1のデータ1（data1）に、経路10上のリンク（c）とリンク集合データ1（={}）の要素を代入する。更に、経路10と同じグループに属するリンク集合（={}）を代入する。
【０２５２】
ステップＳ７０４−２において、構造体データ1-1のデータ2に、経路10を構成するリンクを、葉リンクが最後に来るように並び替えたものをリンク集合データ2の先頭に追加したデータを入力する。経路cが経路10として選択された場合、構造体データ1-1のデータ2（data2）に、リンク集合データ2（={}）の先頭に経路10（c）を追加したデータを入力する。
【０２５３】
ステップＳ７０４−３において、構造体データ1-1のデータ3に、リンク集合データ1に含まれる葉リンクの数に1を足した値に経路10のコストをかけ、数値1を足した値を記録する。経路cが経路10として選択された場合、構造体データ1-1のデータ3（data3）に、リンク集合データ1に含まれる葉リンクの数に1を足した値（0+1=1）と経路10のコスト（=3）をかけ、数値1（=0）を足した値（=3）を記録する。その結果、図５５（Ｂ）に示す構造体データ1-1が生成される。
【０２５４】
ステップＳ７０４−４において、構造体データ1-1のデータ1と同じデータ1を有する構造体データ1-2が集合データ1に存在しないとき、ステップＳ７０４−４−１において、構造体データ1-1を集合データ1に入力する。
【０２５５】
ステップＳ７０４−４において、構造体データ1-1のデータ1と同じデータを有する構造体データ1-2が集合データ1に存在し、かつステップＳ７０４−５において構造体データ1-2のデータ3の値が構造体データ1-1のデータ3の値より大きい場合、ステップＳ７０４−５−１において、構造体データ1-1と構造体データ1-2を入れ替える。
【０２５６】
ステップＳ７０３−３において、リンク集合3に属するリンクから計算した経路すべてに対し、ステップＳ７０３−２からＳ７０４−５のステップを繰り返す。ステップＳ７０３−１で生成した経路={(c,3),(d,1),(e,1),(f,3)}に対し処理が終わったとき、図５６の集合データ1が生成される。
【０２５７】
ステップＳ７０３−４において、構造体データ10が空でなければ、ステップＳ７０３−４−１において、集合データ1から構造体データ10を削除する。
【０２５８】
ステップＳ７０３−４及びステップＳ７０３−４−１の後に、ステップＳ７０５−１において、集合データ1内に構造体データ1が1つだけ存在し、そのデータ1にすべてのリンクが含まれている場合、ステップＳ７０６において、構造体データ1のデータ2のリンクの順序を順序の計算結果として、データ3を順序に対する順序コストとして出力する。
【０２５９】
ステップＳ７０５−１の条件が満たされない場合、ステップＳ７０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とし、そのデータ1をリンク集合データ1に、データ2をリンク集合データ2に、データ3を数値1に入力する。図５６の集合データ1の例では、集合データ1の要素数が最小値（=1）である経路c用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{c}となり、リンク集合データ2は構造体データ10のデータ2である{c}となり、数値1は、構造体データ10のデータ3である3となる。
【０２６０】
その後、ステップＳ７０２に戻り計算を進めると、ステップＳ７０２において、リンク集合3=全リンク−リンク集合データ1（={c}）={a1,a2,b1,b2,d,e,f}となる。
【０２６１】
ステップＳ７０３−１において、図５４に示す方法で以降のステップで使用する経路を計算すると、{(a2->d,3),(e,1),(f,3)}となる。
【０２６２】
ステップＳ７０３−２において、経路(a2->d)->(e)->(f)の順で、それぞれ構造体データ1-1を計算する。経路a2->dが選択された場合、ステップＳ７０４−１において、構造体データ1-1のデータ1（data1）に、経路10上のリンク（a2,d）とリンク集合データ1（={c}）の要素を代入する。更に、経路10と同じグループに属するリンク集合（={a1}）を代入する。ステップＳ７０４−２において、構造体データ1-1のデータ2に、リンク集合データ2（={c}）の先頭に経路10を追加したデータ（a2->d->c）を入力する。ステップＳ７０４−３において、構造体データ1-1のデータ3に、リンク集合データ1に含まれる葉リンクの数に1を足した値（1+1=2）に経路10のコスト（=3）をかけ、数値1（=3）を足した値（=9）を記録する。その結果、図５７（Ａ）に示す構造体データ1-1が生成される。
【０２６３】
経路e及び経路fが選択されたときも同様に計算すると、図５７（Ｂ）及び（Ｃ）に示す構造体データ1-1が生成される。その結果、図５７（Ｄ）に示す集合データ1が生成される。
【０２６４】
ステップＳ７０３−４において、構造体データ10が空でないため、ステップＳ７０３−４−１において、図５８（Ａ）に示すように、構造体データ10を集合データ1から削除する。
【０２６５】
ステップＳ７０５−１の条件は満たされないため、ステップＳ７０５−２において、集合データ1内の構造体データ1のうち、データ1の要素数が最も少ない構造体データ1を取り出して構造体データ10とする。ここでは、集合データ1の中でデータ1の要素数が最小値（=1）である経路d用の構造体データ1を取り出し、構造体データ10とする。リンク集合データ1は構造体データ10のデータ1である{d}となり、リンク集合データ2は構造体データ10のデータ2である{d}となり、数値1は、構造体データ10のデータ3である1となる。
【０２６６】
その後、ステップＳ７０２からステップＳ７０３−３を同様に行うと、図５８（Ｂ）に示す構造体データ1-1、構造体データ1-2、構造体データ1-3が生成される。図５８（Ａ）の集合データ1を見ると、data1が{a1,a2,c,d}になっている構造体データ1が集合データ1内に存在する。このとき、構造体データ1-1作成中におけるステップＳ７０４−４の条件が満たされないため、ステップＳ７０４−５において両者のコストを比較し、ステップＳ７０４−５の条件を満たすかチェックする。この場合は図５８（Ｂ）の構造体データ1-1のコストの方が小さいため、入れ替える。その結果、集合データ1は図５８（Ｃ）になる。
【０２６７】
更に計算を進めると、集合データ1は図５９（Ａ）に示すようになる。ここで、図５９（Ａ）の構造体データ1-10、構造体データ1-11、構造体データ1-12、構造体データ1-13の順に計算を進める。
【０２６８】
構造体データ1-10に対して計算を進めると、ステップＳ７０４−３終了時の構造体データ1-1は、図５９（Ｂ）に示すようになる。これを集合データ1に入力し、構造体データ1-10を集合データ1から削除する。
【０２６９】
構造体データ1-11に対して計算を進めると、ステップＳ７０４−３終了時の構造体データ1-1は、図５９（Ｃ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図５９（Ｂ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが大きいので置き換える。その後、構造体データ1-11を集合データ1から削除する。
【０２７０】
構造体データ1-12に対して計算を進めると、ステップＳ７０４−３終了時の構造体データ1-1は、図５９（Ｄ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1に入力された図５９（Ｃ）の構造体データ）が存在するが、集合データ1の構造体データのほうのコストが小さいので置き換えない。その後、構造体データ1-12を集合データ1から削除する。
【０２７１】
構造体データ1-13に対して計算を進めると、ステップＳ７０４−３終了時の構造体データ1-1は、図５９（Ｅ）に示すようになる。集合データ1にデータ1が同じ構造体データ（集合データ1のデータと置き換えられた図５９（Ｃ）の構造体データ）が存在し、集合データ1の構造体データのほうのコストが小さいので置き換えない。その後、構造体データ1-13を集合データ1から削除する。
【０２７２】
最終的に、図５９（Ｆ）に示すように、集合データ1内に構造体データ1が１つだけ存在し、そのデータ1にすべてのリンクが含まれているため、データ2= a2->d->c->b1->e->fをリンクの順序として、データ3=36を順序コストとして出力する。
【０２７３】
次に、図３３のフローチャートにおいて計算量を削減するための方法について説明する。以下の説明では図３３のフローチャートを参照して説明するが、図４０のフローチャートにも適用可能である。
【０２７４】
図３３では、ステップＳ６０３−１において計算されたすべての経路に対して順序コストの計算を進めるが、順序コストの計算を進める経路を、コストが小さい順に予め与えられた数に制限してもよい。すなわち、ステップＳ６０３−１において、例えば候補経路の選択方法の変更指示（計算量の削減指示）を受信した場合に、リンク集合3に属するリンクから指定した方法によって計算された経路のうち、コストが最小の経路からk番目までの経路を選ぶ。
【０２７５】
図５０の集合データ1から経路a1->c用の構造体データ1を取り出し、構造体データ10とした場合について説明する。このとき、リンク集合データ1は構造体データ10のデータ1である{a1,a2,c}となり、リンク集合データ2は構造体データ10のデータ2である{a1->c}となり、数値1は、構造体データ10のデータ3である20となる。
【０２７６】
その後、ステップＳ６０２に戻り計算を進めると、ステップＳ６０２において、リンク集合3=全リンク−リンク集合データ1（={a1,a2,c}）={b1,b2,d,e,f}となる。
【０２７７】
ステップＳ６０３−１において、図４８に示す方法で以降のステップで使用する経路を計算すると、{(d,1),(b1->e,6),(b2->f,8)}となる。ここで、計算量の削減指示を受信したことを想定する。
【０２７８】
計算量の削減指示がなければ、経路(b1->e)->(d)->(b2->f)の順で、それぞれ構造体データ1-1を計算するが、計算量の削減指示に従い、ステップＳ６０３−２において、コストの小さい順に２つ目までの経路に対する構造体データ1-1を計算する。経路dのコストは1*3=3であり、経路b1->eのコストは6*3=18であり、経路b2->fのコストは8*3=24である。従って、経路d及びb1->eに対する構造体データを生成する。経路dが選択された場合、図６０（Ａ）に示す構造体データ1-1が生成される。経路b1->eが選択された場合、図６０（Ｂ）に示す構造体データ1-1が生成される。その結果、図６０（Ｃ）に示す集合データ1が生成される。図６０（Ｃ）の集合データ1と図５１（Ｄ）の集合データ1を比べると、集合データ1の要素数が少なくなっていることが分かる。
【０２７９】
上記の例では、候補経路の選択方法の変更指示が計算途中で受信された場合を示しているが、候補経路の選択方法の変更指示は用いられなくてもよい。すなわち、ステップＳ６０３−１において、リンク集合3に属するリンクから指定した方法によって計算された経路のうち、コストが最小の経路からk番目までの経路を選んでもよい。
【０２８０】
このように、VMのデータ構造が一般的な場合に、個別のVMマイグレーション時間が短くなるよう、VMのデータの送信順をスケジューリングすることが可能になる。
【０２８１】
なお、実施例２及び実施例４の順序コストの算出例において、共通データを有するリンクを同じグループに属するリンクとして扱っているが、数字で表したリンクIDを用いずに同じリンクとして扱ってもよい。すなわち、図２６に示すように識別子を用いず、VMのデータ構造は図６１のように表現されてもよい。その場合においても、上記の計算は適用可能である。
【０２８２】
図２６のデータ構造の例では、ステップＳ５０４−１において、リンクa1がリンク10として選択された場合、構造体データ1-1のデータ1（data1）に、リンク10（a1）とリンク集合データ1（={}）の要素を代入し、更に、リンク10（a1）と同じグループに属するリンク集合（={a2}）を代入している。図６１のデータ構造の例では、ステップＳ５０４−１において、リンクaがリンク10として選択された場合、構造体データ1-1のデータ1（data1）に、リンク10（a）とリンク集合データ1（={}）の要素を代入すればよい。リンク10と同じグループに属するリンク（a）は既にデータ1に代入されているため、再度代入する必要はない
また、図２６のデータ構造の例では、ステップＳ６０４−１において、経路a1->cが経路10として選択された場合、構造体データ1-1のデータ1（data1）に、経路10上のリンク（a1,c）とリンク集合データ1（={}）の要素を代入し、更に、経路10と同じグループに属するリンク集合（={a2}）を代入している。図６１のデータ構造の例では、ステップＳ５０４−１において、経路a->cが経路10として選択された場合、構造体データ1-1のデータ1（data1）に、経路10（a->c）とリンク集合データ1（={}）の要素を代入すればよい。経路10上のリンクと同じグループに属するリンク（a）は既にデータ1に代入されているため、再度代入する必要はない。以降のステップも、リンクをグループ化することなく実施することができる。
【０２８３】
＜ハードウェア構成例＞
図６２に、本発明の実施例に係るデータ移動順序決定装置１００のハードウェア構成例を示す。データ移動順序決定装置１００は、ＣＰＵ（Central Processing Unit）１５１等のプロセッサ、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）等のメモリ装置１５２、ハードディスク等の記憶装置１５３等から構成されたコンピュータでもよい。例えば、上記のデータ移動順序決定方法の実行手順は、記憶装置１５３又はメモリ装置１５２に記録される。VMのデータ構造や計算中に発生するデータも、記憶装置１５３又はメモリ装置１５２に記録される。データ移動順序決定装置１００の機能及び処理は、記憶装置１５３又はメモリ装置１５２に格納されているデータやプログラムをＣＰＵ１５１が実行することによって実現される。また、データ移動順序決定装置１００に必要な情報は、入出力インタフェース装置１５４から入力され、データ移動順序決定装置１００において求められた結果は、入出力インタフェース装置１５４から出力されてもよい。
【０２８４】
＜補足＞
説明の便宜上、本発明の実施例に係るデータ移動順序決定装置は機能的なブロック図を用いて説明しているが、本発明の実施例に係るデータ移動順序決定装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、本発明の実施例は、コンピュータに対して本発明の実施例に係るデータ移動順序決定装置の機能を実現させるプログラム、コンピュータに対して本発明の実施例に係る方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。また、本発明の実施例に係る方法は、実施例に示す順序と異なる順序で実施されてもよい。
【０２８５】
以上、マイグレーション中の障害に対する耐性を向上させるための手法について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【０２８６】
１００  データ移動順序決定装置
１１０  データ分類部
１２０  移動順序決定部
１５１  ＣＰＵ
１５２  メモリ装置
１５３  記憶装置
１５４  入出力インタフェース装置
【図１】
2018073013.tif 000003
【図２】
2018073013.tif 000004
【図３】
2018073013.tif 000005
【図４】
2018073013.tif 000006
【図５】
2018073013.tif 000007
【図６】
2018073013.tif 000008
【図７】
2018073013.tif 000009
【図８】
2018073013.tif 000010
【図９】
2018073013.tif 000011
【図１０】
2018073013.tif 000012
【図１１】
2018073013.tif 000013
【図１２】
2018073013.tif 000014
【図１３】
2018073013.tif 000015
【図１４】
2018073013.tif 000016
【図１５】
2018073013.tif 000017
【図１６】
2018073013.tif 000018
【図１７】
2018073013.tif 000019
【図１８】
2018073013.tif 000020
【図１９】
2018073013.tif 000021
【図２０】
2018073013.tif 000022
【図２１】
2018073013.tif 000023
【図２２】
2018073013.tif 000024
【図２３】
2018073013.tif 000025
【図２４】
2018073013.tif 000026
【図２５】
2018073013.tif 000027
【図２６】
2018073013.tif 000028
【図２７】
2018073013.tif 000029
【図２８】
2018073013.tif 000030
【図２９】
2018073013.tif 000031
【図３０】
2018073013.tif 000032
【図３１】
2018073013.tif 000033
【図３２】
2018073013.tif 000034
【図３３】
2018073013.tif 000035
【図３４】
2018073013.tif 000036
【図３５】
2018073013.tif 000037
【図３６】
2018073013.tif 000038
【図３７】
2018073013.tif 000039
【図３８】
2018073013.tif 000040
【図３９】
2018073013.tif 000041
【図４０】
2018073013.tif 000042
【図４１】
2018073013.tif 000043
【図４２】
2018073013.tif 000044
【図４３】
2018073013.tif 000045
【図４４】
2018073013.tif 000046
【図４５】
2018073013.tif 000047
【図４６】
2018073013.tif 000048
【図４７】
2018073013.tif 000049
【図４８】
2018073013.tif 000050
【図４９】
2018073013.tif 000051
【図５０】
2018073013.tif 000052
【図５１】
2018073013.tif 000053
【図５２】
2018073013.tif 000054
【図５３】
2018073013.tif 000055
【図５４】
2018073013.tif 000056
【図５５】
2018073013.tif 000057
【図５６】
2018073013.tif 000058
【図５７】
2018073013.tif 000059
【図５８】
2018073013.tif 000060
【図５９】
2018073013.tif 000061
【図６０】
2018073013.tif 000062
【図６１】
2018073013.tif 000063
【図６２】
2018073013.tif 000064