目的関数の組み合わせに関する考察

仮想ノードを物理ノードに配置するアルゴリズムを考える前に，メモリ，パケッ ト数とネットワークトラフィックの3点で設定した物理ノード数もしくは仮想ノー ド数を決定する目的関数と，仮想ノードの配置を決定する目的関数をそれぞれ列 挙する．

物理ノード数もしくは仮想ノード数を決定する目的関数

目的関数1 与えられた仮想ノードを配置するために必要な最小の物理ノード数

目的関数2 与えられた物理ノードに配置可能な最大の仮想ノード数

目的関数4 パケット破棄を起こさずに物理ノードに配置可能な仮想ノード数 目的関数7 オーバーフローを起こさずに物理ノードに配置可能な仮想ノード数

仮想ノードの配置を決定する目的関数

目的関数3 各物理ノードに配置された仮想ノードのメモリの合計値の平滑化 目的関数5 スイッチが処理するパケット数の最小化

目的関数6 スイッチの各イーサネットポートで処理するパケット数の平滑化 目的関数8 スイッチを通る通信量の最小化

目的関数9 スイッチの各イーサネットポートの通信量の平滑化

仮想ノードを物理ノードに割り当てる資源割り当てアルゴリズムは，物理ノー ド数もしくは仮想ノード数を決定する目的関数と仮想ノードの配置を決定するア ルゴリズムの組み合わせで決まる．

まず始めに物理ノード数と仮想ノード数を決定する．物理ノード数と仮想ノー ド数は，実験者が両方とも指定するか，どちらか一方が決まっている場合は，物 理ノード数もしくは仮想ノードを決定する目的関数を使って決まっていない方を 決定する．次に，最適化問題の近似解を求めるアルゴリズムで，配置の目的関数 を満たすような仮想ノードの物理ノードへの配置をおこなう．

物理ノード数または仮想ノード数を決定する目的関数の組み合わせは全部で9 種類存在する．1つ目は，実験者が物理ノード数と仮想ノード数の両方を設定す る場合である．2つ目は，仮想ノード数が決定されている場合である．このとき，

物理ノード数を求める目的関数は1のみである．3つ目は使用する物理ノード数 が決まっている場合である．この時，仮想ノード数を求める目的関数は2,4,7で ある．これらを組み合わせは全部で7種類存在する．それぞれの目的関数は

NP-表1 目的関数の組み合わせ(ノード数決定)

目的関数1 目的関数2 目的関数4 目的関数7 求めるノード数

仮想ノード配置に 物理ノード パケット破棄が トラフィックの 必要な最小の 配置可能な 起こらないで オーバーフローが起こらないで

物理ノード数 最大の仮想ノード数 配置可能な仮想ノード数 配置可能な仮想ノード数

未使用 未使用 未使用 未使用 なし

使用 未使用 未使用 未使用 物理ノード数

未使用 使用 未使用 未使用 仮想ノード数

未使用 未使用 使用 未使用 仮想ノード数

未使用 未使用 未使用 使用 仮想ノード数

未使用 使用 使用 未使用 仮想ノード数

未使用 使用 未使用 使用 仮想ノード数

未使用 未使用 使用 使用 仮想ノード数

未使用 使用 使用 使用 仮想ノード数

困難な問題である．物理ノード数もしくは仮想ノード数を決定する場合，NP-困 難な問題の組み合わせを解く多次元最適化問題となる．すべての組み合わせを表 1に表す．

配置決定の目的関数は5種類ある．それらの組み合わせは全部で32種類とな る．5つの目的関数は物理ノード数もしくは仮想ノードを求める時の目的関数同 様，すべてNP-困難な問題のため，その組み合わせは多次元最適化問題となるた め近似解やヒューリスティックを用いた解として出すことになる．よって，組み 合わせのうち，使用する目的関数が多くなれば，配置として最適化されて行くた め実験環境として安定しやすくなる．しかし，使用する目的関数が多くなれば，

条件を満たす組み合わせは少なくなりかつ条件判定をより多く行うため解が出る までの時間が長くなる．逆に配置に使用する目的関数の数を減らすと解が出るま での時間は短くなるが，スイッチが処理するパケットやトラフィック量の増加や

パケット破棄の可能性が発生してしまう．

以上より，仮想ノードを物理ノードに割り当てる資源割り当てアルゴリズムは 全部で288通りの組み合わせが考えられる．ここで，物理ノード数または仮想ノー ド数を決定する目的関数の組み合わせと配置決定の目的関数は多次元最適化問題 であるので，資源割り当てアルゴリズムも多次元最適化問題となる．そのため，

NP-困難問題となり近似解やヒューリスティックによる解をもとめないと現実時 間で解が求められない．しかし，メモリの割り当てであれば，OSが消費するメ モリ量とOS上で起動するアプリケーションが消費するメモリ量がわかればメモ リ割り当ての最適を出すことは可能であると考えられる．そこで，次章では，こ のメモリの割り当てに着目して最適なメモリ割り当て手法の提案を行う．