|
1
|
1 % Sample file for the use of compsoft style file.
|
|
|
2 %
|
|
|
3 \documentclass[T]{compsoft}
|
|
|
4
|
|
|
5 % Preamble
|
|
|
6 %
|
|
7
|
7 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
|
|
|
8 % 巻数，号数，開始ページ，終了ページを指定する．
|
|
1
|
9 %\volNoPp{16}{5}{78}{83}
|
|
|
10
|
|
7
|
11 % ワークショップによる推薦論文の場合，ワークショップ名を指定する．
|
|
|
12 % \suisen{ワークショップ名}
|
|
1
|
13
|
|
7
|
14 % 特集の場合，特集のタイトルを与える．
|
|
|
15 % \tokushu{特集のタイトル}
|
|
1
|
16
|
|
7
|
17 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
|
|
|
18 % 大会の回数は計算される．
|
|
1
|
19 \taikai{2010}
|
|
|
20
|
|
7
|
21 % ここに，使用するパッケージを列挙する．
|
|
1
|
22 \usepackage[dvips]{graphics}
|
|
|
23
|
|
7
|
24 % ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
|
|
|
25 % 再定義は原則として避けること．
|
|
1
|
26
|
|
|
27 \begin{document}
|
|
|
28
|
|
7
|
29 % 論文のタイトル
|
|
|
30 \title{Meta Engine を用いた Federated Linda の実験}
|
|
1
|
31
|
|
7
|
32 % 著者
|
|
|
33 % 和文論文の場合，姓と名の間には半角スペースを入れ，
|
|
|
34 % 複数の著者の間は全角スペースで区切る
|
|
1
|
35 %
|
|
7
|
36 \author{赤嶺 一樹 河野 真治
|
|
1
|
37 %
|
|
7
|
38 % ここにタイトル英訳 (英文の場合は和訳) を書く．
|
|
1
|
39 %
|
|
|
40 \ejtitle{Experiment of Federated Linda with Meta Engine}
|
|
|
41 %
|
|
7
|
42 % ここに著者英文表記 (英文の場合は和文表記) および
|
|
|
43 % 所属 (和文および英文) を書く．
|
|
|
44 % 複数著者の所属はまとめてよい．
|
|
1
|
45 %
|
|
7
|
46 \shozoku{Kazuki Akamine}{琉球大学理工学研究科情報工学専攻}%
|
|
6
|
47 {Information Engineering Course, Faculty of Engineering Graduate School
|
|
|
48 of Engineering and Science, University of the Ryukyus}
|
|
1
|
49 %
|
|
7
|
50 % 出典情報は \shutten とすれば出力される．
|
|
1
|
51 %\shutten
|
|
|
52 %
|
|
7
|
53 % 受付年月日，記事カテゴリなどは自動的に生成される．
|
|
1
|
54 %\uketsuke{1999}{8}{3}
|
|
|
55 %
|
|
7
|
56 % その他，脚注に入れるものがあれば，\note に記述する．
|
|
|
57 %\note{脚注に入れる内容}
|
|
1
|
58 }
|
|
|
59
|
|
|
60 %
|
|
7
|
61 % 和文アブストラクト
|
|
1
|
62 \Jabstract{%
|
|
7
|
63 本研究室では、分散型タプルスペースの実験用に Federated Linda を
|
|
|
64 提案し、実装してきた。従来の Federated Linda は各ノードの間に配置された
|
|
|
65 Protocol Engine によって互いに連携するが、プロセスが異なるため無駄な通信
|
|
|
66 が存在した。そこで Federated Linda と同一プロセス上で動作する Meta Engine
|
|
|
67 を提案し、実装してきた。本研究では、クラスター上で Meta Engine を用いた実
|
|
|
68 験用トポロジーを構築し、MetaEngine の使用例を示す。
|
|
1
|
69 }
|
|
|
70 %
|
|
7
|
71 % 英文アブストラクト（大会論文には必要なし)
|
|
1
|
72 % \Eabstract{}
|
|
|
73 %
|
|
|
74 \maketitle
|
|
|
75
|
|
7
|
76 \section{はじめに}
|
|
3
|
77
|
|
7
|
78 twitter をはじめとする大人数参加型 Web サービスや MMORPG などの大人数参
|
|
|
79 加型リアルタイムネットワークゲームが、これまで以上に大規模なものとなって
|
|
|
80 いくためには、分散ネットワークプログラムの発展が不可欠である。
|
|
3
|
81
|
|
7
|
82 しかし、分散ネットワークプログラムにおけるスケーラビリティーの確保は
|
|
|
83 難しい。ここで言うスケーラビリティーとは、サービスの大きさが増えたときに
|
|
|
84 サーバーなどのリソースを追加することのみでサービスの質をリニアに維持でき
|
|
|
85 ることを指す。
|
|
3
|
86
|
|
7
|
87 すなわち理想的なモデルは、複数のサーバーを接続することで負荷を分散し、ク
|
|
|
88 ライアントの数に従ってサービスが自然にスケールするものでなくてはならない。
|
|
1
|
89
|
|
7
|
90 例えば、現在の分散技術を助けている Key-Value Store などでは、すべてのデー
|
|
|
91 タのレプリケーションを複数台用意するという手法がとられている。
|
|
|
92 しかしながら、大人数が参加するサービスにおいて、全員が個人のとあるデータ
|
|
|
93 を持っている必要性はない。自分と関連のある人物の情報さえ取得できるように
|
|
|
94 なっていればよいのである。つまり、全データのレプリケーションを用意する必
|
|
|
95 要はなく、サーバーがクライアントの必要な情報とは何かを把握し、情報を取捨
|
|
|
96 しながら伝搬していく必要がある。
|
|
3
|
97
|
|
12
|
98 本研究室では、分散プログラムモデルとして、タプルスペースを制御する Linda
|
|
|
99 を採用してきた。さらに、複数台の Linda サーバーを接続したモデルである分
|
|
|
100 散型タプルスペースFederated Linda を提案し、実装してきた。本研究では、
|
|
|
101 Linda の API の見直しと、 Federated Linda を用いたアプリケーションの実装
|
|
|
102 を行い、現在のシステムの問題点を洗い出すことにする。
|
|
3
|
103
|
|
7
|
104 \section{ゲームの例題}
|
|
1
|
105
|
|
7
|
106 \subsection{水族館ゲーム}\label{subsection:aquarium}
|
|
|
107 本研究では、ネットワークゲームを例題として用いることにした。そのゲームは、
|
|
|
108 複数のクライアントのディスプレイを並べて使用する。各プレイヤーは1匹ずつ
|
|
|
109 魚のオブジェクトが与えられ、それを自由に操作することが出来る。また、魚は
|
|
|
110 画面の端まで移動すると、自分の画面上からは消え、隣のプレイヤーの画面の端
|
|
9
|
111 から魚が出てくる。(図\ref{fig:aqua})
|
|
4
|
112
|
|
8
|
113 \begin{figure}[htbp]
|
|
|
114 \begin{center}
|
|
12
|
115 \scalebox{0.50}{\includegraphics{./pic/aqua.eps}} % TODO: 重いから最後
|
|
|
116 %\scalebox{0.50}{\includegraphics{./pic/fedlinda.eps}}
|
|
8
|
117 \end{center}
|
|
|
118 \caption{A,B,C の順に接続すると左から順に画面が接続される。 B の魚は C
|
|
|
119 の画面まで移動している。}
|
|
|
120 \label{fig:aqua}
|
|
|
121 \end{figure}
|
|
1
|
122
|
|
4
|
123 \section{Federated Linda}
|
|
|
124
|
|
7
|
125 \subsection{Linda とは}\label{subsection:linda}
|
|
|
126 Linda は、タプルスペースという ID で区画されたデータストアに、以下の API
|
|
|
127 (表\ref{tab:lindaapi})
|
|
|
128 を用いてデータを出し入れすることによって、外部との通信を行う分散プログラ
|
|
|
129 ミングモデルである。
|
|
4
|
130
|
|
|
131 \begin{table}[htbp]
|
|
|
132 \begin{center}
|
|
|
133 \caption{Linda API}
|
|
|
134 \label{tab:lindaapi}
|
|
|
135 \begin{tabular}[t]{|l|l|}
|
|
|
136 \hline
|
|
7
|
137 in(id)&タプル空間から取り出す。\\&タプル空間にタプルは残らない。\\
|
|
4
|
138 \hline
|
|
7
|
139 rd(id)&タプル空間から取り出す。\\&タプル空間にタプルが残る。\\
|
|
4
|
140 \hline
|
|
7
|
141 out(id,data)&タプル空間にタプルを入れる。 \\
|
|
4
|
142 \hline
|
|
|
143 \end{tabular}
|
|
|
144 \end{center}
|
|
|
145 \end{table}
|
|
|
146
|
|
7
|
147 \subsection{Federated Linda とは}\label{subsection:fedlinda}
|
|
|
148 Federated Linda は Linda サーバーを複数台、相互に接続することによって、
|
|
|
149 分散プログラミングを実現する。各サーバーは、接続した Linda サーバー内の
|
|
|
150 タプルスペースへデータのin/out を行うことによって、データを伝搬する。
|
|
5
|
151
|
|
|
152 \begin{figure}[htbp]
|
|
|
153 \begin{center}
|
|
|
154 \scalebox{0.50}{\includegraphics{./pic/fedlinda.eps}}
|
|
|
155 \end{center}
|
|
9
|
156 \caption{Federate Linda の接続モデル。組み込まれた Meta Engine がタプルスペースを操作し、外部のサーバーへデー
|
|
|
157 タを伝搬する}
|
|
6
|
158 \label{fig:fedlinda}
|
|
5
|
159 \end{figure}
|
|
4
|
160
|
|
|
161
|
|
7
|
162 \subsection{Meta Engine とは}\label{subsection:metaengine}
|
|
6
|
163
|
|
7
|
164 Federated Linda は、サーバー間に設置された、 Protocol Engine と呼ばれる
|
|
|
165 プログラムによって、タプルスペースの操作や、他サーバーへのタプルの伝搬などを行っており、
|
|
|
166 タプルスペースとは別のプロセスとして、サーバー上に存在していた。しかし、
|
|
|
167 別のプロセスであるため、タプルスペースへのアクセスには同一サーバー上であっ
|
|
|
168 ても、ソケット通信を用いていた。
|
|
6
|
169
|
|
7
|
170 そこで、本研究室では、 Meta Engine と呼ばれるプログラムを提案し実装して
|
|
|
171 きた。 Meta Engine は、 タプルスペースと同一プロセス上に組み込まれた
|
|
9
|
172 Protocol Engine である。(図\ref{fig:fedlinda})すなわち、タプルスペースと
|
|
7
|
173 同じメモリ空間にあるため、ソケット通信を用いることなく直接 Linda の API
|
|
|
174 を使用して、タプルスペースにアクセスすることが出来る。
|
|
4
|
175
|
|
7
|
176 \section{Linda API の見直し}
|
|
|
177 \subsection{update() API の追加}\label{subsection:update}
|
|
|
178 現状の Linda API では、タプル内のデータを更新するためには in() を実行し
|
|
|
179 てデータを取り出して削除したあとに、out() を実行してデータを書き込む必要
|
|
11
|
180 があった。(図\ref{fig:inout})今回考えている水族館の例題でも、操作があったときにはタプルスペー
|
|
7
|
181 スの座標情報を最新のデータに更新する必要がある。
|
|
6
|
182
|
|
11
|
183 \begin{figure}[htbp]
|
|
|
184 \begin{center}
|
|
|
185 \scalebox{0.50}{\includegraphics{./pic/inout.eps}}
|
|
|
186 \end{center}
|
|
|
187 \caption{in/out を用いたデータの更新}
|
|
|
188 \label{fig:inout}
|
|
|
189 \end{figure}
|
|
|
190
|
|
|
191
|
|
7
|
192 そこで、今回、新しく update() API を追加することにした。update() を実行
|
|
11
|
193 すると、現在存在するタプルは削除され、新しいデータで上書きされる。(図\ref{fig:update})
|
|
|
194
|
|
|
195 \begin{figure}[htbp]
|
|
|
196 \begin{center}
|
|
|
197 \scalebox{0.50}{\includegraphics{./pic/update.eps}}
|
|
|
198 \end{center}
|
|
|
199 \caption{update を用いたデータの更新}
|
|
|
200 \label{fig:update}
|
|
|
201 \end{figure}
|
|
|
202
|
|
12
|
203 update() の引数は、 out() と同じく update(id,data) のように、 id と data を渡す。
|
|
4
|
204
|
|
9
|
205 \section{Meta Engine を用いたサーバーの設計}
|
|
7
|
206 \subsection{ツリー型トポロジーを用いた負荷分散}\label{subsection:treetopology}
|
|
10
|
207 今回の例題には、ツリー型トポロジー Federated Linda を用いることにした。
|
|
11
|
208 (図\ref{fig:treetopology})
|
|
9
|
209
|
|
|
210 \begin{figure}[htbp]
|
|
|
211 \begin{center}
|
|
|
212 \scalebox{0.40}{\includegraphics{./pic/treetopology.eps}}
|
|
|
213 \end{center}
|
|
|
214 \caption{ツリー型トポロジーで接続された Federated Linda。ツリーの末端に
|
|
|
215 クライアントを接続する。}
|
|
11
|
216 \label{fig:treetopology}
|
|
9
|
217 \end{figure}
|
|
|
218
|
|
12
|
219 ツリー型トポロジーの各ノードは、親と2つの子への接続を持つ。また、末端の
|
|
|
220 ノードはクライアントによる接続も受け付ける。
|
|
10
|
221
|
|
|
222 クライアントから座標情報を受け取った末端のノードは、その座標情報を他のク
|
|
|
223 ライアントが必要としているかを判断する。もしも必要ならば、その Linda サー
|
|
|
224 バーのみで通信は完結しているため、 Federated Linda 上でデータの伝搬は行
|
|
|
225 われない。
|
|
|
226
|
|
12
|
227 もし必要としない場合は、親のノードにタプルデータの伝搬を行う。そのとき
|
|
|
228 親のノードは、その子から送られてきた座標情報を元に、対になっている子がデー
|
|
|
229 タを必要としているかを判断する。もし必要ならば、対になっている子に対し
|
|
|
230 てタプルデータを伝搬する。そうでなければ、さらにその親に対してタプルデー
|
|
|
231 タの伝搬を行う。
|
|
10
|
232
|
|
|
233 このように、座標データを必要としているマシンのみに座標データをコピーする
|
|
12
|
234 ことで、負荷分散を実現するモデルである。 このモデルを用いない場合、つま
|
|
|
235 り Linda サーバーを単体で用いる場合は、各クライアントは、すべての接続し
|
|
|
236 ているクライアントの所持しているオブジェクトの座標情報を常に監視する必要
|
|
|
237 があり、画面に表示されない(すなわち、必要のない)データも操作がされるたび
|
|
|
238 に通信する必要があった。
|
|
8
|
239
|
|
7
|
240 \section{評価}
|
|
|
241 \subsection{update() API の検証}\label{subsection:updateverification}
|
|
|
242 \subsection{ツリー型トポロジーによる負荷分散の検証}\label{subsection:treetopologyverification}
|
|
4
|
243
|
|
|
244
|
|
7
|
245 \section{まとめと今後の課題}
|
|
1
|
246
|
|
|
247 %
|
|
|
248 \begin{adjustvboxheight} % needed only when Appendix follows
|
|
|
249 \begin{thebibliography}{99}
|
|
7
|
250 \bibitem{LS86} test %Lanin, V. and Shasha, D.：A Symmetric Concurrent B-Tree
|
|
5
|
251 %Algorithm,
|
|
7
|
252 %Proc.\ 1986 Fall Joint Computer Conference, IEEE, 1986, pp.~380--389．
|
|
1
|
253 \end{thebibliography}
|
|
|
254 \end{adjustvboxheight} % needed only when Appendix follows
|
|
|
255
|
|
|
256 \end{document}
|
