ネットワークにおける複数データベースの最適ロケーション問題
藤重研究室　　都築　祐哉

1.序論

ネットワークシステムの信頼性や能力の向上など,様々な目的で複製データベー スのロケーション問題は研究されている．本研究ではコミュニケーショ ンの費用に注目して,その最適な複製データベースの配置について研究を行う．
ネットワーク内のデータベースを利用する各ユーザについて，期間毎に要求され る情報量を,ユーザ固有の値として設定する．このネットワークをグラフで表し, 各ユーザをグラフ内の点とし，その情報量を各点の重みとして,1期間における,ネッ トワーク全体の情報伝達の費用が最小になるように,データベースを配置する．
しかし，一般のネットワークにおけるこの問題はNP-困難であることが分かってい るので,本研究では 木構造を持ったネットワークについて研究を行う．

2.問題の設定

ネットワークを重み付けされた無向グラフ G(V,E)で表し，点vをユーザ, 枝 eを,ユーザ間のリンクとする．各ユーザ vは，1期間の読み書きの情 報の要求量に応じて，それぞれr(v),w(v)の重みを持っているとする．また， ある2点x,y間の距離を,d(x,y)で表し,特に, ネットワーク内のある点集合をX={x1,x2,・・・,xp}と したとき，
d(x,X)を

d(x,X) = min{d(x,xi)|xi in X}

と定義する． ネットワーク上でデータベースの置かれた点の集合をXとし,Xの全ての点を 結ぶGの部分木をT(X)とする．あるユーザvがデータを読む際は，vから最も近いデータベースから読むとし,その 単位期間の費用は，r(v)d(v,X)であるとする．
また,書き込む際には,全てのデータベースに書き込まなければならない．そこで， T(X)の点で，vから最も近い点をv'とし，T(X)の全ての枝の長さの和を l(X)とすると, 点集合X cup{v}の全ての点を結ぶGの部分木T(X cup{v})の全長は l(X cup{v})=l(X)+d(v,v')と置ける．このとき，単位期間におけるユーザ vからの書き込みの費用は，w(v)l(X cup{v})であるとする．
以上より，全体の費用 Cost(X)は，次のように表される． Cost(X)=sum r(v)d(v,X)+sum w(v)l(X cup{v}) 3.新しいモデルとその解法 データベースの利用において,常に最新の情報を必要としない状況を考える．そ こで,各データベースへの,情報の書き込みについて,次のような設定を加える．
各ユーザが書き込んだ情報は,ある期間一定のデータベースに蓄えられ,期間毎に, 他の全てのデータベースを書き換えるようにする．つまり,ユーザが情報を書き 込めるデータベースは１つに決まっており,他のデータベースは全て読み出し専 用と考える．
このようなモデルについて,~1期間での費用を考えると,読む場合は,以前と同様で ある．次に,各ユーザが書き 込む場合の費用は,情報を蓄えるデータベースの置かれる点をx0とすると, sum{w(v)d(v,x_0)|v\in V}で求められる．そして，一定期間蓄えた情報を全て のレプリカにコピーする際は，1期間当り，蓄えられた情報の総量sum{w(v)|v in V} と木T(X)の全長l(X)の積より求められる．このモデルにおける 1期間当りの全体の費用評価の式は,次のように与えられる．

Cost(X,x_0)=sum r(v)d(v,X)+sum w(v)d(v,x_0) +l(X)sum w(v)

この問題を,任意のx0についての部分問題に分け,各x0についての最適解 X*(x_0)のうちで,最小のものが，原問題の最適解(X*,x0*)である．
この問題を解くために,ネットワークの1-メディアンを求める．1-メディアンと は,各点の重みをalpha(v)としたとき，H(u)=sum alpha(v)d(v,u)を最小にするuであるが,このモデルでは,データベースへ の書き込みはx0から行われるため,次のようにalpha(v)={r(v)|v !=x0},alpha(x0)=r(x0) +sum w(v)として求める．
この1-メディアンをu0(x0)として,部分問題を解くアルゴリズムを以下に示す．

＜部分問題の解 X*(x0)を求めるアルゴリズム＞}

[Step 0] X*(x0)={u0(x0)}とする．
[Step 1] T(X*(x0))の任意の葉u'に隣接する X*(x0)に含まれない点uで，
　　　　　sum w(v) - sum{r(v) | v in Tu} ＜ 0となる点uが存在すればStep 2へ．
　　　　　存在しなければ，
　　　　　X*(x0)は部分問題の解である．(停止)
[Step 2] X*(x0)←X*(x0) cup{u}としてStep 1へ戻る．
このアルゴリズムで，Tuは，Tをu0(x0)を根とする木としたときの，uを根とするTの部分木である．

4.今後の課題

今回提案したアルゴリズムでは，各x0毎に部分問題を解いているが,この形で はないより高速な解法の研究が望まれる．