実験方法

EPSRの効果を評価するために，オーバレイ構築ツールキットOverlay Weaver [85, 86]上にEPSRを実装した．Overlay Weaverは構造化オーバレイネットワークの容 易な実装と評価を実現するフレームワークである．異なる需要変動をシミュレー トすることでEPSRの評価実験を行った．評価実験では以下の5つの指標につい て計測を行った．

• 経過時間．これはEPSRが需要の発生地域の特定と配置先の決定に要した時 間を示す．Flash Crowd による需要増加に対して短時間であれば，EPSRが 高速性を備えていることが示される．

• 複製サーバの配置先の数．これは需要の規模の変動に応じてEPSRが配置先 の数をどの程度調整できているかを示す．配置先の数が需要の変動に合わせ て増減していれば，EPSRが需要変動に応じて複製サーバの配置先の数を調 整できていることが示される．

• クライアントから複製サーバの配置先までのオーバレイネットワーク上の ホップ数．これはEPSRがオーバレイネットワーク上においてどの程度クラ イアントの近傍にあるホスティングマシンを複製サーバの配置先として選択 できているかを示す．ホップ数が少ないほど，EPSRがオーバレイネットワー

ク上においてクライアントの近傍にあるホスティングマシンを配置先として 選択できていることを示す．

• クライアントから複製サーバの配置先までのラウンドトリップタイム(RTT)．

これはEPSRがクライアントに対してどの程度通信遅延の小さいホスティン グマシンを複製サーバの配置先として選択できているかを示す．RTTが小さ いほど，EPSRがクライアントに対して通信遅延の小さいホスティングマシ ンを配置先として選択できていることを示す．

• 同時接続数．これは複製サーバおよびそれを稼働しているホスティングマシ ンの負荷を示す．同時接続数がホスティングマシンの性能制約以下であれば，

EPSRが性能制約に従って複製サーバの配置先を選択できているといえる．ま た，複製サーバを稼働しているホスティングマシンの同時接続数の集合にお ける最低値が大きく分散が小さいほど，無駄な複製サーバが少ないといえる．

より現実に即した条件下でEPSRの挙動を確認するために2種類のデータセッ トを用意した．用意したデータセットは，インターネットを模した仮想トポロジ から得たものとインターネットでの実測によるものである．インターネットの実 測データはKing計測手法[115]によって計測されたものである．実験ではこれら 2つのデータセットを用いて擬似的なインターネットのトポロジを構成し，そのト ポロジ上でEPSRを動作させた．

用意した2つのデータセットTSおよびMeridianの詳細は次の通りである．

1. TSデータセット: 2階層のルーティングドメインを持つTransit-Stubインター ネットモデルである[87]．Transit-StubモデルはTransitドメインが下位にある Stubドメインを接続する構造でインターネットをモデル化する．Transit-Stub モデルを生成するためにGT-ITMトポロジ生成器を利用した [116]．Transit-Stubモデルによるトポロジの生成パラメータは以下の通りである．Transitド メイン数は 228 とした．それぞれのTransit ドメインに5つのTransit ノー ドをおき，それぞれの Transit ノードに対して4 つのStub ドメインを割り 当てた．それぞれのStubドメインに2つのノードを割り当てた．実験では Transit-Stubモデルで生成した約10,000ノードのうち，GNPによって計算さ れたネットワーク座標を一意に割り当てることができた約3,000ノードをホ スティングマシンとして使用した．

図4.1: サービスAおよびサービスB のクライアント数の推移．

2. Meridianデータセット: Meridianプロジェクト[117]で使用されたインター ネットの実測データである．一意なIPアドレスをもつ2,500のDNSサーバ 間のRTTから成る．組み合わせの数は約625万である．このデータセット は2004年5月5日から13日の間に収集された．実験ではこのデータセット

が含む2,500台のうち，GNPによって計算されたネットワーク座標を一意に

割り当てることができた約2,200台をホスティングマシンとして使用した．

なお，本実験で使用するネットワーク座標の次元数は，文献[73]によるネットワー ク座標系の精度の評価に基づき6とした．

4.2 EPSR による複製サーバの配置先決定の評価

EPSRはFlash Crowdのように急激に需要が変動しても，需要の発生している地

域を特定し，ホスティングマシンの性能制約を満たすように複製サーバの配置先 を決定する．このEPSRの特徴を確認するために，EPSRの複製サーバ配置先決定 部の評価を行った．評価はシミュレーションによって行い，ネットワークのモデ

ルにはTransit-Stubモデルを，通信遅延のデータセットにはTSデータセットを使

用した．

EPSRの複製サーバ配置先決定部の特徴を確認するために，局所的に高い需要が 発生している地域をシミュレーション上で再現し実験を行った．クライアントは TSモデルで，互いのRTTが4000ミリ秒以下になるように設定した．クライアン

トは60秒ごとにサービスに対するリクエストメッセージを送信する．EPSRは複 数のサービスが同時に提供されている場合でも需要変動に応じて複製サーバの配 置先を決定できる．これを確認するために，本シミュレーションでは2つのサー ビスA，B が同時に提供されているように設定した．図4.2はシミュレーション 中のクライアント数を示す．図4.2が示すように，サービスAのクライアント数 は区間毎に増減するが，サービスB のクライアント数は一定とした．サービスA とサービスB のクライアントは同じ地域から選択した．

EPSRが性能制約を考慮して複製サーバの配置先を決定できていることを確認す るために，以下の方式との比較を行った．

• Root only:複製サーバを配置しない．

• Marker only: マーカとなったホスティングマシンのみを複製サーバの配置先

とする．

• Globule: Globule [49–51]で用いているHotSpotアルゴリズム[52, 53]に基づ いてマーカを選択する．HotSpotアルゴリズムは全複製サーバのアクセス記 録やホスティングマシンの位置情報のような大域情報に依存するため，長期 の需要変動のみに対応する．一方で大域情報に基づいて計算するためマー カ選択の精度は高く，最適解に最も近いとみなすことができる．これより，

EPSRの測定結果がGLOBULEのそれと近い場合，EPSRは各ホスティング マシンがもつ局所情報のみで最適解に近いマーカ配置が得られることを示す．

HotSpotアルゴリズムが本シミュレーションで発生させる短期の需要変動を

対象としていないため，HotSpotアルゴリズムによるマーカ選択はオフライ ンで行った．

なお，Globuleが複製サーバの配置先としたホスティングマシンの数は，サービス Aを90台，サービスBを10台とした．これはシミュレーション中でFlash Crowd が発生したと想定した第 2区間の後半において EPSRが決定した配置先の数に合 わせたものである．

本シミュレーションにおける設定値を表4.1に示す．APC degreeを管理するス ライディングウィンドウは 300秒分とし，各ホスティングマシンは 30秒間隔で

APC degreeを確認するように設定した．マーカとなる閾値upperは300，マーカ

から一般のホスティングマシンに戻る閾値 lowerは200とした．ホスティングマ シン1台当たりの性能制約は，クライアントの接続数を基準とし，同時接続数30

表4.1: EPSRによる複製サーバの配置先決定の評価で使用した各種パラメータ．

サービス数 2

クライアントのリクエスト間隔 60秒 スライディングウィンドウのサイズ 300秒分

APC degreeの確認間隔 30秒

マーカとなる閾値upper 300 マーカから戻る閾値lower 200

ホスティングマシンの性能制約 同時接続数30以下

図4.2: EPSRによる複製サーバの配置先候補点数の推移．

とした．すなわち，ホスティングマシンは最大で30クライアントまでを，マシン 上で稼働する複製サーバは許容できるものとした．また，複製サーバが与える負 荷はサービスAとサービスB で等しいとした．

4.2.1 複製サーバの配置先数の推移と決定に要した時間

図4.2はEPSRが決定した複製サーバの配置先数の変動を示す．x軸は経過時間 を，y軸は複製サーバの配置先数を示す．y軸は対数である．シミュレーション結 果はEPSRが需要変動に応じて複製サーバの配置先数を調整できていることを示 している．サービスAの需要が変動に応じて，サービスAの複製サーバの配置先

数が増減した．シミュレーションの第2区間では，図4.1が示すようにクライア ント数が第1区間の10倍となっている．この需要に対応するために，EPSRは複 製サーバの配置先数の増加を25秒後に開始した．これは文献 [10]で報告されて

いるFlash Crowdがピークに達するまでに要した時間40秒より高速である．その

後，EPSRはサービスAの複製サーバの配置先数を，166秒間で最初の7から299 まで増加した．さらに300秒経過後，EPSRは負荷の少ない複製サーバを終了し，

最終的に複製サーバの配置先数を90とした．第3区間では，サービスAの複製 サーバの配置先数はサービスB のものより少ない．これは第3区間ではサービス Aのクライアント数がサービスB のものよりも少ないからである．

さらに図4.2は，EPSRがサービスごとに独立して複製サーバの配置先数を調整 できていることを示す．第 1区間からFlash Crowdの発生した第2区間にかけて サービスAのクライアント数が60から600と10倍に増加したとき，サービスA の複製サーバの配置先数が7から299に増加した．これはEPSRがサービスAの 需要増加を検出したことを示す．ただし，同区間においてサービスB の複製サー バの配置先数も他区間と比較して若干増加している．これはサービスAのクライ アント数の増加によって，サービスBの複製サーバの配置先であるホスティング マシンの負荷が増加したためである．サービスAのクライアント数の増加に伴っ て，サービスAの複製サーバとサービスB の複製サーバの配置先へ同時になるホ スティングマシンが増加する．このときホスティングマシンの性能制約を超過す る場合，EPSRは高需要の複製サーバを優先する．これにより，低需要であるサー ビスB の複製サーバの配置先が増加する．

4.2.2 クライアントと複製サーバの配置先間の通信遅延

EPSRが需要の発生している地域にあるホスティングマシンから複製サーバの配 置先を選択できていることを確認するために，クライアントと複製サーバの配置 先間のRTTを EPSR，Root only，Globuleで比較した．図4.3 (a)，(b)および(c) はそれぞれ第1区間，第2区間，第3区間のRTTの分布を示す累積頻度グラフで ある．

図4.3は，EPSRが需要の発生した地域に複製サーバの配置先を設定しているこ とを示す．特にFlash Crowdが発生している第2区間においては，EPSRがGlobule よりも多くのクライアントのRTTを小さくした．EPSRではクライアントと複製 サーバの配置先とのRTTの90パーセンタイル値が1180ミリ秒であったのに対し