% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
%\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
\taikai{2010}

% ここに，使用するパッケージを列挙する．
\usepackage[dvips]{graphics}

% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{Meta Engine を用いた Federated Linda の実験}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{赤嶺 一樹　河野 真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Experiment of Federated Linda with Meta Engine}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Kazuki Akamine}{琉球大学理工学研究科情報工学専攻}%
{Information Engineering Course, Faculty of Engineering Graduate School
of Engineering and Science, University of the Ryukyus}
%
% 出典情報は \shutten とすれば出力される．
%\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
%\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
\Jabstract{%
本研究室では、分散型タプルスペースの実験用に Federated Linda を
提案し、実装してきた。従来の Federated Linda は各ノードの間に配置された
Protocol Engine によって互いに連携するが、プロセスが異なるため無駄な通信
が存在した。そこで Federated Linda と同一プロセス上で動作する Meta Engine
を提案し、実装してきた。本研究では、クラスター上で Meta Engine を用いた実
験用トポロジーを構築し、MetaEngine の使用例を示す。
}
%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle

\section{はじめに}

twitter をはじめとする大人数参加型 Web サービスや MMORPG などの大人数参
加型リアルタイムネットワークゲームが、これまで以上に大規模なものとなって
いくためには、分散ネットワークプログラムの発展が不可欠である。

しかし、分散ネットワークプログラムにおけるスケーラビリティーの確保は
難しい。ここで言うスケーラビリティーとは、サービスの大きさが増えたときに
サーバーなどのリソースを追加することのみでサービスの質をリニアに維持でき
ることを指す。

すなわち理想的なモデルは、複数のサーバーを接続することで負荷を分散し、ク
ライアントの数に従ってサービスが自然にスケールするものでなくてはならない。

例えば、現在の分散技術を助けている Key-Value Store などでは、すべてのデー
タのレプリケーションを複数台用意するという手法がとられている。
しかしながら、大人数が参加するサービスにおいて、全員が個人のとあるデータ
を持っている必要性はない。自分と関連のある人物の情報さえ取得できるように
なっていればよいのである。つまり、全データのレプリケーションを用意する必
要はなく、サーバーがクライアントの必要な情報とは何かを把握し、情報を取捨
しながら伝搬していく必要がある。

本研究室では、タプルスペースを制御する Linda プロトコルを採用した。さら
に、複数台の Linda サーバーを接続したモデルである分散型タプルスペース
Federated Linda を提案し、実装してきた。本研究では、Linda のプロトコルの
見直しと、 Federated Linda を用いたアプリケーションの実装を行い、現在の
システムの問題点を洗い出すことにする。

\section{ゲームの例題}

\subsection{水族館ゲーム}\label{subsection:aquarium}
本研究では、ネットワークゲームを例題として用いることにした。そのゲームは、
複数のクライアントのディスプレイを並べて使用する。各プレイヤーは1匹ずつ
魚のオブジェクトが与えられ、それを自由に操作することが出来る。また、魚は
画面の端まで移動すると、自分の画面上からは消え、隣のプレイヤーの画面の端
から魚が出てくる。(図\ref{fig:aqua})

\begin{figure}[htbp]
\begin{center}
%\scalebox{0.50}{\includegraphics{./pic/aqua.eps}} % TODO: 重いから最後
\scalebox{0.50}{\includegraphics{./pic/fedlinda.eps}}
\end{center}
\caption{A,B,C の順に接続すると左から順に画面が接続される。 B の魚は C
 の画面まで移動している。}
\label{fig:aqua}
\end{figure}

\section{Federated Linda}

\subsection{Linda とは}\label{subsection:linda}
Linda は、タプルスペースという ID で区画されたデータストアに、以下の API
(表\ref{tab:lindaapi})
を用いてデータを出し入れすることによって、外部との通信を行う分散プログラ
ミングモデルである。

\begin{table}[htbp]
\begin{center}
\caption{Linda API}
\label{tab:lindaapi}
\begin{tabular}[t]{|l|l|}
\hline
in(id)&タプル空間から取り出す。\\&タプル空間にタプルは残らない。\\
\hline
rd(id)&タプル空間から取り出す。\\&タプル空間にタプルが残る。\\
\hline
out(id,data)&タプル空間にタプルを入れる。 \\
\hline
\end{tabular}
\end{center}
\end{table}

\subsection{Federated Linda とは}\label{subsection:fedlinda}
Federated Linda は Linda サーバーを複数台、相互に接続することによって、
分散プログラミングを実現する。各サーバーは、接続した Linda サーバー内の
タプルスペースへデータのin/out を行うことによって、データを伝搬する。

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/fedlinda.eps}}
\end{center}
\caption{Federate Linda の接続モデル。組み込まれた Meta Engine がタプルスペースを操作し、外部のサーバーへデー
タを伝搬する}
\label{fig:fedlinda}
\end{figure}


\subsection{Meta Engine とは}\label{subsection:metaengine}

Federated Linda は、サーバー間に設置された、 Protocol Engine と呼ばれる
プログラムによって、タプルスペースの操作や、他サーバーへのタプルの伝搬などを行っており、
タプルスペースとは別のプロセスとして、サーバー上に存在していた。しかし、
別のプロセスであるため、タプルスペースへのアクセスには同一サーバー上であっ
ても、ソケット通信を用いていた。

そこで、本研究室では、 Meta Engine と呼ばれるプログラムを提案し実装して
きた。 Meta Engine は、 タプルスペースと同一プロセス上に組み込まれた
Protocol Engine である。(図\ref{fig:fedlinda})すなわち、タプルスペースと
同じメモリ空間にあるため、ソケット通信を用いることなく直接 Linda の API
を使用して、タプルスペースにアクセスすることが出来る。

\section{Linda API の見直し}
\subsection{update() API の追加}\label{subsection:update}
現状の Linda API では、タプル内のデータを更新するためには in() を実行し
てデータを取り出して削除したあとに、out() を実行してデータを書き込む必要
があった。(図\ref{fig:inout})今回考えている水族館の例題でも、操作があったときにはタプルスペー
スの座標情報を最新のデータに更新する必要がある。

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/inout.eps}}
\end{center}
\caption{in/out を用いたデータの更新}
\label{fig:inout}
\end{figure}


そこで、今回、新しく update() API を追加することにした。update() を実行
すると、現在存在するタプルは削除され、新しいデータで上書きされる。(図\ref{fig:update})

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/update.eps}}
\end{center}
\caption{update を用いたデータの更新}
\label{fig:update}
\end{figure}


update() の)引数は、 out() と同じく update(id,data) のように、 id と data を渡す。

\section{Meta Engine を用いたサーバーの設計}
\subsection{ツリー型トポロジーを用いた負荷分散}\label{subsection:treetopology}
今回の例題には、ツリー型トポロジー Federated Linda を用いることにした。
(図\ref{fig:treetopology})

\begin{figure}[htbp]
\begin{center}
\scalebox{0.40}{\includegraphics{./pic/treetopology.eps}}
\end{center}
\caption{ツリー型トポロジーで接続された Federated Linda。ツリーの末端に
 クライアントを接続する。}
\label{fig:treetopology}
\end{figure}

ツリー型トポロジーの各ノードは、親と2つの子への接続を持つ。また、末端のノードは
クライアントによる接続も受け付ける。

クライアントから座標情報を受け取った末端のノードは、その座標情報を他のク
ライアントが必要としているかを判断する。もしも必要ならば、その Linda サー
バーのみで通信は完結しているため、 Federated Linda 上でデータの伝搬は行
われない。

もし、必要としない場合は、親のノードにタプルデータの伝搬を行う。そのとき、親のノー
ドは、その子から送られてきた座標情報を元に、対になっている子がデータを必
要としているかを判断する。もし、必要ならば、対になっている子に対してタプ
ルデータを伝搬する。そうでなければ、さらにその親に対してタプルデータの伝
搬を行う。

このように、座標データを必要としているマシンのみに座標データをコピーする
ことで、負荷分散を実現するモデルである。このモデルを用いない場合は、各ク
ライアントは、すべての接続しているクライアントの所持しているオブジェクト
の座標情報を常に監視する必要があり、画面に表示されない(すなわち、必要のない)
データも操作がされるたびに通信する必要があった。



\section{評価}
\subsection{update() API の検証}\label{subsection:updateverification}
\subsection{ツリー型トポロジーによる負荷分散の検証}\label{subsection:treetopologyverification}


\section{まとめと今後の課題}

%
\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{LS86} test %Lanin, V. and Shasha, D.：A Symmetric Concurrent B-Tree
%Algorithm,
%Proc.\ 1986 Fall Joint Computer Conference, IEEE, 1986, pp.~380--389．
\end{thebibliography}
\end{adjustvboxheight} % needed only when Appendix follows

\end{document}