第 3 章 ExaPeer Server Reposition
3.3 ネットワーク座標
本節では，EPSRの要素技術であるネットワーク座標について説明する．ネット ワーク座標はネットワークにおけるホスト間の RTTをユークリッド距離で近似す
(a)物理ネットワークのトポロジ を考慮したオーバレイネットワー クを構築する．
(b)ホスティングマシンはクライ アントが送信したサーバ解決要求 メッセージを複製サーバまで転送 する．
(c)メッセージが多く転送されてい るホスティングマシンを複製サー バの配置先とする．
(d)以降に送信されたサーバ解決 要求メッセージは，より近い複製 サーバに到達する．
(e)ホスティングマシンの負荷が 性能制約に達すると，さらにクラ イアントに近いホスティングマシ ンに複製サーバを配置する．
図3.1: EPSRの動作概念図．
るように計算されたユークリッド座標である．ネットワーク座標によって，イン ターネット上のホストは互いの座標から通信遅延を推測することができる．
ネットワーク座標を生成するシステムはネットワーク座標系と呼ばれ，様々な ものが提案されている[69–77]．ネットワーク座標系は各ホストに割り当てるネッ トワーク座標を，座標から計算されるユークリッド距離がホスト間のRTTになる ように発見的アルゴリズムを用いて決定する．ネットワーク座標系は2種類に大 別される．ひとつは，あらかじめ用意したランドマークホストから d次元の座標 空間を構築しておき，一般ホストの座標をランドマークとのRTTとユークリッド 距離の誤差を最小化する最適化問題から求める中央処理型の方法[69–71]である．
もうひとつは，ランドマークホストを用意せずに個々のホスト間のRTTとユーク リッド距離の誤差を最小化する最適化問題で求める完全分散型の方法[72–77]で ある．適切な次元数dはネットワーク座標系によって異なるが，通常は6から8 次元を用いる．これはRTTを距離としたインターネット空間は複雑な位置関係と なっており，低次元では三角不等式を満たさない座標になり精度が低下するから である．ネットワーク座標系の精度は相対誤差が 0.2程度と文献[77]で報告され ている．
ここではGlobal Network Positioning (GNP) [69]を例に挙げて，ネットワーク座 標の計算手続きを説明する．GNPはランドマークのネットワーク座標を求める手 続きと，一般ホストのネットワーク座標を求める手続きの2段階を経る．まず，N 台のランドマークのネットワーク座標cSL1, . . . , cSL
N は次の目的関数fobj1(·)を最小 化する最適化問題を解くことで求める．
fobj1(cSL1, . . . , cSL
N) =
Li,Lj∈{L1,...,LN}|i>j
ε(dLiLj,dˆSL
iLj) (3.1) ここでcSL
iはネットワーク座標空間SにおけるランドマークLi のネットワーク座 標，dLiLj はランドマークLi とLj のRTT，dˆLiLj はネットワーク座標から求めた ランドマークLi とLj のユークリッド距離，ε(·)は誤差関数である．誤差関数ε(·) は例えば次のような単純な二乗誤差を用いることで定義できる．
ε(dH1H2,dˆSH1H2) = (dH1H2 −dˆSH1H2)2 (3.2) この最適化問題は発見的アルゴリズムで近似解を求めることができる．GNPによ るネットワーク座標は，例えば滑降シンプレックス法[111]で求められることが知 られている．
次に一般ホストのネットワーク座標を求める．ホストHのネットワーク座標cSH は次の目的関数fobj2(·)を最小化する最適化問題を解くことで求める．
fobj2(cSH) =
Li∈{L1,...,LN}
ε(dHLi,dˆSHLi) (3.3)
ここでε(·)はランドマークのネットワーク座標を求める際と同様の誤差関数であ る．一般ホストのネットワーク座標の場合もランドマークのネットワーク座標の 場合と同様に，発見的アルゴリズムを用いて近似解を求められる．
3.4 EPSR オーバレイネットワーク
需要が発生している地域の方角を特定するために，EPSRはオーバレイネット ワークをGNPとContent-Addressable Network (CAN) [79]を組み合わせることで 構築する．GNP は第3.3節で述べた通り，ネットワーク座標系のひとつである．
CANはDHTのひとつである．CANは個々のホスティングマシンに仮想的なd次 元の座標を与え，またd次元空間をゾーンと呼ばれる単位に分割する．各ゾーン はホスティングマシンが 1台ずつ割り当てられるように分割される．ホスティン グマシンは自身が管理するゾーンが座標 (h0(K), . . . , hd−1(K)) を含む場合，(key
K, valueV)の組を自身に保存する．ここでhi はホスティングマシン間で共有す
るハッシュ関数である．もしkeyKが存在するとき，CANはK を管理するホス ティングマシンまでの到達ホップ数の平均を d4N1d とすることを保証する．ここで N はCANに参加しているホスティングマシンの数である．
GNPとCANを用いることで，EPSRは物理ネットワークのトポロジを考慮した オーバレイネットワークを構築する．EPSRでは，d次元のCANで割り当てる座 標をGNPによって生成したd次元のネットワーク座標とする．これにより，EPSR オーバレイネットワーク上で隣接するホスティングマシンは物理ネットワーク上 でも近傍にあることが保証される．ExaPeerにサービスが登録されると，EPSRは ルートマシンと呼ばれるホスティングマシンを選び出す．ルートマシンはサービ スの識別子1をkeyとして，CANのプロトコルに従って決定する．なお，EPSRは GNP と CAN に依存するものではない．例えば，EPSR は GNP の代わりに他の ネットワーク座標系であるSCoLE [73]やVivaldi [75]を用いることができる．ま た，CANの代わりにeCAN [112]を用いて構築することも可能である．
1サービス名などの一意に定められるものを使用する．
図3.2: APC degreeに基づいたマーカの設定．
クライアントは自身が接続すべき複製サーバを特定するために，サーバ解決要 求メッセージをクライアント自身が含まれるゾーンを管理するホスティングマシ ンに送信する．サーバ解決要求メッセージは，メッセージの種類を示す4ビット 値，クライアントのIPアドレス，サービス名から変換して求めたd次元の宛先座 標およびクライアントからのメッセージを最初に受信したホスティングマシンの IPアドレスを含む．サーバ解決要求メッセージはCANのプロトコルに従い，複 製サーバかルートマシンに到達するまでホスティングマシンによって転送される．
クライアントがサーバ解決要求メッセージの送信先とするホスティングマシン を特定する手順は以下の通りである．まず，クライアントXはDNSラウンドロビ ンなどの手段でExaPeerに参加している任意のホスティングマシンM を特定し，
ゾーン特定用メッセージを送信する．ゾーン特定用メッセージは，メッセージの 種類を示す4ビット値，クライアントのIPアドレスとGNP座標，およびクライ アントが最初に送信したホスティングマシンのIPアドレスを含む．ホスティング マシンはクライアントのGNP座標を宛先としてゾーン特定用メッセージを転送す る．宛先座標を含むゾーンを管理するホスティングマシンN は，ホスティングマ シンM を経由して自身のIPアドレスをクライアントXに通知する．
図3.2はEPSRが2次元のCANを用いて構築したオーバレイネットワークを示 す2．それぞれのゾーンにはひとつずつホスティングマシンがある．この図では登 録したサービスのルートマシンがホスティングマシンAとなっている．クライア ントXは登録されているサービスを受けるために，自身が含まれるゾーンを管理 するホスティングマシンにサーバ解決要求メッセージを送信する．送信されたメッ セージは CANのプロトコルに従ってルートマシン Aまで転送される．クライア ントY およびZ に関しても同様である．