\chapter{Federated Linda の提案}

\section{LindaとFedarated Linda}
本研究室では、自然に分散プログラミングが書けるようなプログラミングモデル
として大域 ID を持たない連邦型タプルスペース[2][3](以下Federated Lindaと記す)
を提案してきた。

\subsection{Linda}
Linda は、タプルというid で番号づけられたデータの塊を
以下のAPI (表\ref{lindaapi}) で、共有されたタプル空間に出し入れする
ことにより外部との通信を行う分散プログラミングモデルである。(図\ref{fig:lindacom})

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


\begin{figure}[htbp]
\begin{center}
 \includegraphics[width=7.6cm]{fig/lindacom.pdf}
\end{center}
 \caption{LindaServer}
 \label{fig:lindacom}
\end{figure}


\subsection{Federated Linda}
Federated Linda は、複数のタプル空間(Linda)を相互に接続することにより分散プログ
ラムを実現する。一つのタプル空間には少数の接続があることが期待されており、
多数のタプル空間が接続により分散アプリケーションを実現する(図
\ref{connection-of-tspace}参照)。smtp/nntp デーモンが行単位でプロトコル
を作るのと似た形で、タプル空間への in/out でプロトコルを作ることになる。

通信モデルはタプルの出し入れによる、リレー転送のようになる。インターネッ
トのパケット転送のように、タプルスペースからタプルスペースへとタプルを転
送していく。

クライアントのアクセス数が増えても、タプルスペース等の数を増やし、ネットワーク処理を
分散することにより、スケーラビリティを保つ。

\begin{figure}[htc]
\begin{center}
\includegraphics[width=14cm]{fig/connection-of-tspace.pdf}
\end{center}
\caption{タプルスペースの相互接続}
\label{connection-of-tspace}
\end{figure}

\newpage
\section{Federated Linda の分散プログラミング}
Fedetated Linda の分散プログラムには``Local Access Protocol'', ``Protocol Engine'',
``Link Configuration'' の３つの要素がある。Federated Linda はこの３つの
要素に基づいてプログラミングモデルを提供する。

\subsubsection{Local Access Protocol}
プロトコルへのアクセスは Linda の API を用いる。つまり、タプルスペースへ
の ``in'', ``read'', ``out'' などである。これらのコマンドは単純で、理解し
やすいものである。タプルの出し入れというモデルで通信を行うことができる。
また、通信は非同期に行う。このAPIを用いるプログラムはポーリングベースのプ
ログラミングスタイルを取る。

\subsubsection{Protocol Engine}
プロトコルを規定する Protocol Engine は、分散アルゴリズムを内包し、他の
プロトコルへのアクセスもタプルスペース経由で行う。通信はタプルをタプルス
ペースからタプルスペースへと、バケツリレーの様に転送する。クライアントと
はタプルスペースを介した通信を行うので、クライアントからはプロトコルの細
かい挙動は見えない。しかし、クライアントプログラムのプロトコルへの依存を
低く抑えることが可能である。

\subsubsection{Link Configuration}
タプルスペースやProtocol Engineの接続を規定する。接続の状況をXMLとして表
し、各ノードがそれにしたがって論理ネットワークを構築する。論理ネットワー
クを構築するために、接続などを扱うモジュールを提供する。

\section{実装の段階分け}

Federated Linda の実装には次の3つの段階がある。

\begin{description}
\item    [type 1]  オリジナルの非同期型 Linda
\item    [type 2]  複数のLindaServer をエージェントが橋渡しする
\item    [type 3]  タプル空間自体が直接接続される
\end{description}

この段階分けは実装の容易さで決められている。type1はすでに実装されている
非同期型Lindaである。type2,type3からはその前のタイプのプログラミングの経
験よりその詳細な仕様を決定する。以下でその説明を行う。

\subsection{type 1}

type 1 は本研究室で開発した非同期型Lindaプログラムである(図\ref{type1}参照)。
タプルスペースを持つLindaサーバに、Clientプログラムがタプルを出し入れすること
により、分散プログラムを実現している。
非同期型Lindaはpolling base の実装であり、また、複数のcommandをqueueに登録して、
同期処理部分で複数同時に送信する、という実装が可能である。これにより、
細かいタプル操作毎に通信せず、送信するパケットをまとめることを実現する。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=6cm]{fig/flinda_type1.pdf}
\end{center}
\vspace{-8mm}
\caption{type 1}
\label{type1}
\end{figure}


\subsection{type 2}
type 2 は、複数のLindaに同時にアクセスすることができる。type 2 は type 1 
の実装から容易に作ることができる。

type 2 のタプル空間(Linda)は、Protocol Engine と呼ばれるエージェントで接
続される。Protocol Engine から Linda へのアクセスは通常の Linda API で行
われる。(図\ref{fig:type2}参照)。エージェントは状態を持たないように作る
ことが望ましい。そのようにすれば、状態はLinda上に維持される。Lindaとの接
続が切れても、状態がLindaに維持されていれば、状態を持たないProtocol
Engine を接続することにより自動的に再接続される。現在の実装では、
Protocol Engine は Perl, Python 上の非同期タプル通信であり、シングルスレッドで動
作する。

Protocol Engine は、タプル空間のタプルを見張り、タプルの状態の変化により、
接続されたタプル空間へアクセスする。必要なら計算処理を行う。どのような処
理を行うかは、Protocol Engine のプログラムによって決まる。type 2 では、
これらは前もって決まっており変更することは想定していない。type 3 では、
なんらかのプログラムのロード機構が必要となると考えられる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=10cm]{fig/flinda_type2.pdf}
\end{center}
\vspace{-8mm}
\caption{type 2}
\label{fig:type2}
\end{figure}


\subsection{type 3}

type 3 では、Protocol Engine は Linda と一体化して抽象化される。(図
\ref{fig:type3}参照)。Linda 間は、Inter-Linda プロトコルで接続される。そ
のAPIは、タプル空間にアクセスする時に、そのプロトコルを指定するような手法を用いる。
この段階で、ネットワーク資源の管理、例えば、複数ユーザや複数のアプリケーションの分離を実装する。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=10cm]{fig/flinda_type3.pdf}
\end{center}
\vspace{-8mm}
\caption{type 3}
\label{fig:type3}
\end{figure}

これらの詳細は、type 2 でのプログラミング経験に基づいて決定する必要がある。
特に Protocol Engine は、必要となる分散プロトコルが十分に有限なら
API として提供し、APIとして提供できないぐらい多様性を持つならプログラム
のロード機構を用いる事になる。よって、type 2 で様々な Protocol Engine を実装
し、その経験から最終的な仕様(type3)を決定する。

Linda と Protocol Engine の接続は、ネットワークで接続される。type 2 では、
それらは手動で設定される。これらの設定の自動化は、やはりtype 3 で行われ
る。

%Federated Lindaは複雑なネットワーク状での接続を想定しており、クリアすべき
%接続のトポロジーは例えば図\ref{fig:Tree}, 図\ref{fig:mesh} のような
%TreeやMeshが考えられる。

%\begin{figure}[htbp]
%\begin{center}
%\includegraphics[width=10cm]{fig/tree.pdf}
%\caption{Tree型トポロジ}
%\label{fig:Tree}
%\end{center}
%\end{figure}

%\begin{figure}[htbp]
%\begin{center}
%\includegraphics[width=10cm]{fig/mesh.pdf}
%\caption{Mesh型トポロジ}
%\label{fig:mesh}
%\end{center}
%\end{figure}

\newpage

\section{現段階における実装}

先行研究[2][3]において前述したtype2の Federated Lindaの開発が行われた、
ここでは先行研究におけるFederated Lindaの実装について説明する。

\subsection{type2の実装}

Federated Linda は本研究室で開発された非同期型Linda\cite{linda}をベー
スに開発された。type 2 では Linda Server と Protocol Engine は別プロセスと
して実装し、Protocol Engine では Linda Server との通信を クライアントに
提供されている Linda API を用いて行う。

タプルのIDは、{\tt 16bit}の整数値を用い、タプルのデータは任意の文字列であ
る。Linda Server は C で記述されており、クライアントは C, Perl, Python,
Ruby にて記述可能である。以下、Linda Server と クライアントへ提供している
Linda API の説明をし、分散プログラムの主要素である Local Access,
Protocol Engine, Link Configuration の実装について説明する。

\subsubsection{Linda Server}

Linda Server においてタプルスペースはメモリ上のキューとして
実装されている。タプルスペースには1から65535までのIDが割り当てられており、
タプルは指定されたIDへのキューへ格納される。

非同期型 Linda Server の特徴として、タプルを要求するコマンド (in, read,
wait\_read) などを実行する際のコマンド実行の保留が挙げられる。クライアン
トからタプルを要求するコマンドを受け取ると、Linda Server は指定されたID 
にタプルがあるかどうかを調べる。ある場合にはそのコマンドを即実行するが、
無い 場合には、コマンド実行の保留を行う。その後、そのIDへタプルが書き込
まれた( out された) 時に 保留されたコマンドを実行する。(図\ref{async-in} 
参照)。このコマンド実行の保留により、コマンド実行の待ちやクライアントが 
Linda Server へタプルの有無を問い合わせたりすることなく、非同期通信を行
うことができる。

\begin{figure}[htp]
\begin{center}
\includegraphics[width=13cm]{fig/pdf/async-in.pdf}
\caption{タプルがない場合の in コマンドの実行}
\label{async-in}
\end{center}
\end{figure}

プログラムは {\tt ldserv} という名前で提供されている。
起動方法は以下の通りである。``-p''オプションでポート番号を指定している。

% ldserv の起動方法
\begin{verbatim}
    $ ldserv -p 10000
\end{verbatim}

\newpage

\subsubsection{Federated Linda API} 

Federated Linda の通信は非同期に行われる。in, read, out などのコマンドの関数
を呼び出した時点では通信は行われず、それらのコマンドを一時的にキュー
({\tt COMMAND}キュー)へ蓄える。蓄えたコマンドは、タプルやコマンドの送受信を行
う関数({\tt sync()})が呼ばれた時点で一斉に各 Linda Server へ送信される。このと
き、Linda Server から送信されたタプルの受信も行う。受信されたタプルは
{\tt REPLY}キューへ蓄えられ、データを取りだす関数({\tt reply()})で取り出される。
{\tt COMMAND} キューと {\tt REPLY} キューは API により隠蔽されており、直接は見えない。

Federated Linda ではクライアントプログラムへの API として C, Perl,
Python, Ruby で実装したインターフェースを提供している。クライアントプロ
グラムはこれらの中から好きな言語を選んで記述することになる。提供している 
API は、C言語とその他のスクリプト言語との間で若干の違いがある。スクリプ
ト言語ではオブジェクト指向を意識して実装したため、このような違いが出てい
る。

C言語とスクリプト言語に分けて API の説明を行う。

\subsubsection{C言語のAPI}

C言語で提供している主な関数群は以下の通りである。

% CのAPIの説明
\begin{itemize}
\item {\tt open\_linda(hostname,port)}\\
	  Linda Server へ接続する。引数としてホスト名({\tt hostname})とポート番号
	  ({\tt port})をとる。返り値はタプルスペースの番号
\item {\tt psx\_in(ts\_id,tuple\_id)}\\
	  指定したIDのタプルの受け取り要求をするコマンド {\tt in} を {\tt COMMAND}キュー
	  へ入れる。引数としてコマンドを送るタプルスペースの番号({\tt ts\_id})と受け
	  取るタプルのID({\tt tuple\_id})をとる。返り値として{\tt psx\_reply()}でタプル
	  を取り出すときに用いるユニークな番号が返る。受け取ったタプルは、タ
	  プルスペース上からは削除される。
\item {\tt psx\_rd(ts\_id,tuple\_id)}\\
	  指定したIDのタプルの受け取り要求をするコマンド {\tt read} を{\tt COMMAND}キュー
	  へ入れる。引数としてコマンドを送るタプルスペースの番号({\tt ts\_id})と受け
	  取るタプルのID({\tt tuple\_id})をとる。返り値として{\tt psx\_reply()}でタプル
	  を取り出すときに用いるユニークな番号が返る。受け取ったタプルは、タ
	  プルスペース上に残る。
\item {\tt psx\_wait\_rd(ts\_id,tuple\_id)}\\
	  {\tt psx\_rd()}と似ているが、タプルスペース上での挙動に違いがある。タプル
	  スペースにタプルがあった場合、現在あるタプルではなく、新規に{\tt out}され
	  たタプルに対して{\tt read}を行う。それ以外は同じ挙動である。
\item {\tt psx\_out(ts\_id, tuple\_id, data)}\\
	  指定したIDのタプルの書き込み要求をするコマンド {\tt out} を{\tt COMMAND}キュー
	  へ入れる。引数としてコマンドを送るタプルスペースの番号({\tt ts\_id})と書き
	  込むタプルのID({\tt tuple\_id})をとる。
\item {\tt psx\_ck(ts\_id,tuple\_id)}\\
	  指定したIDのタプルの有無の確認をするコマンド {\tt check} を{\tt COMMAND}キュー
	  へ入れる。引数としてコマンドを送るタプルスペースの番号({\tt ts\_id})と受け
	  取るタプルのID({\tt tuple\_id})をとる。返り値として{\tt psx\_reply()}でタプル
	  を取り出すときに用いるユニークな番号が返る。タプルのデータ部分には
	  タプルスペース上にあるタプルのサイズが入る。指定したIDのタプルが無
	  ければ {\tt 0} となる。
\item {\tt psx\_sync\_n()}\\
	  接続している全Linda Server とタプルの送受信を行う。{\tt COMMAND}キューに
	  溜まったコマンドを送信し、Linda Server からのタプルを {\tt REPLY} キュー
	  へ入れる
\item {\tt psx\_reply(uid)}\\
	  {\tt REPLY}キューにあるタプルを取りだす。取り出す際に、{\tt in},
	  {\tt read}コマンドが返した番号を引数としてとる。返り値はタプル。取り出したタプルからデー
	  タやタプル情報(IDやデータサイズ)を取り出す関数群も用意している。
\end{itemize}

まず {\tt open\_linda} を用いて Linda Server へ接続する。この時返る値が Linda
Server の ID になる(Tuple Space ID)。この値とタプルのIDを用いて{\tt psx\_in,
psx\_rd, psx\_out}などのコマンドを発行する。{\tt psx\_in} や {\tt psx\_rd, psx\_ck}
はユニークな番号を返す。この番号は {\tt psx\_reply} の引数として使用し、どの
{\tt psx\_in, psx\_rd}の返答を取り出すかを指定するためのものである。通信は
{\tt psx\_sync\_n}でのみ発生する。

%これらのAPIを用いた通信はポーリング型の形を取る。具体的なポーリングベー
%スのプログラミング例は Local Access の説明で述べる。

\subsubsection{Perl, Python, Ruby の API}

% Perl, Python, Ruby で提供したクラスなどの説明

Perl, Python, Ruby は C の API を拡張して実装している。提供しているモジュー
ルは{\tt FederatedLinda, Linda, Reply}というクラスで構成されている(図
\ref{LWLClass}参照)。各スクリプト言語で同じ名前を用いて実装している。


% FederatedLinda クラスや Reply クラスを、図を入れて説明

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=11.2cm]{fig/pdf/flinda-class-dig.pdf}
\caption{Perl, Python, Ruby で拡張したLinda API のクラス図}
\label{LWLClass}
\end{center}
\end{figure}

\newpage

\begin{itemize}
\item {\tt FederatedLinda} - {\tt open} や {\tt sync} など、通信やその接
	  続切断を行うクラス。１プロセスに１インスタンスのみ生成される。
\begin{description}
\item[~{\tt open(hostname, port)}]{\tt Linda} インスタンスを返す。引数としてホスト名
		   ポート番号を取る。
\item[~{\tt sync()}] 接続している全Linda Serverと通信を行う。
\end{description}
\item {\tt Linda} - 
	  インスタンスを生成する際に Linda Server と接続する。メンバとしてタ
	  プルスペースのIDを保持する({\tt tsid})
\begin{description}
\item[~{\tt In(tid)}]{\tt in} コマンドを発行する。引数としてタプルID({\tt
	  tid})を取る。返
	  り値は、その応答となる{\tt Reply}のインスタンス。
\item[~{\tt Rd(tid)}]{\tt read }コマンドを発行する。引数としてタプル
	  ID({\tt tid})を取る。返り値は、その応答となる{\tt Reply}のインスタンス。
\item[~{\tt WaitRd(tid)}]{\tt wait\_rd} コマンドを発行する。引数としてタプ
		   ルID({\tt tid})を取る。返り値は、その応答となる{\tt Reply}のインスタンス。
\item[~{\tt Out(tid, data)}]{\tt out}コマンドを発行する。引数としてタプル
	  {\tt ID(tid)}と送信するデータを取る。
\item[~{\tt Ck(tid)}]{\tt check} コマンドを発行する。引数としてタプル
	  ID({\tt tid})を取る。返り値は、その応答となる{\tt Reply}のインスタンス。
\item[~{\tt getid()}]タプルID 65535 の値を取得する。この値はLinda Server内部で
      クライアント数をカウントした値である。
\item[~{\tt close()}]Linda Server との接続を閉じる。
\end{description}
\item {\tt Reply} - 
	  Linda Server から受け取ったタプルを取得するためのクラス。
\begin{description}
\item[~{\tt reply()}]受け取ったタプルを取得する。タプルをまだ受け取っていなかっ
	  たら{\tt null(None)}を返す。
\end{description}
\end{itemize}

Linda Server への接続は {\tt FederatedLinda} インスタンスの {\tt open} メソッドを使
う。引数として接続したいLinda Serverのホスト名とポート番号を取る。{\tt open}は
{\tt Linda}インスタンスが返す。また、Linda Serverとの通信は{\tt sync}メソッドで行う。
{\tt in, read, out}などのコマンドは、{\tt Linda}インスタンスのメンバ関数から行う。
{\tt in, read}などのタプルを受け取るコマンドは、{\tt Reply}インスタンスを返す。Linda
Serverからのタプルを取り出したいときは、{\tt Reply}の{\tt reply}メソッドを用いる。

\newpage
\subsection{Local Access Protocol}

``Local Access''はプロトコルへアクセスするAPIである。APIの内容は先に説明
したので、ここではクライアントプログラムにおける Linda API を用いたプロ
グラミングについて説明する。まず最初に、Linda API を使ったクライアントの
ポーリング型のプログラミングについて説明する。次に、タプルスペースを
介した Protocol Engine へのアクセスについて、その利便性について説明する。

\subsubsection{ポーリング型のプログラミングスタイル}

Federated Linda の通信は非同期に行われる。これはポーリング型のプログ
ラミングスタイルで記述されることが期待されているということでもある。
Linda API を用いるプログラムではメインループが一度回ると、{\tt sync()}が一回呼
ばれるようなプログラミングスタイルになる。これは、通信が起こる回数を減ら
すことと、通信箇所を明確にすることを目的としている。

以下にPerlで記述したプログラミング例を挙げる。

\begin{center}
\begin{itembox}[l]{ポーリング型のプログラミング例}
\begin{verbatim}
# Linda Server と接続する
$linda  = FederatedLinda->open($hostname, $portnumber);
# タプルスペースの TUPLE_ID へタプルの取得を要求する
$rep = $linda->in($TUPLE_ID);
# メインループ
while (1) {
    #
    # 通信以外の処理
    #
    if (($data = $rep->reply()) > 0) {  # 応答が来ていたら
        # 繰り返しIDに対してタプルの取得要求を出す
        $rep = $linda->in($TUPLE_ID);

        #
        # 受け取ったデータの処理を記述
        #
        print $data;
    }
    # コマンドやタプルの一斉送受信
    FederatedLinda->sync();
}
\end{verbatim}
\end{itembox}
\end{center}

この例は {\tt \$TUPLE\_ID} で指定されたタプルスペースのタプルを取得し、標準出
力へ書き出すプログラムである。基本的な流れは以下のようになっている。まず
Linda Server へ接続する。次に、使用するタプルスペースへ {\tt in} する。
この {\tt in }
はその後の {\tt sync()} が実行されるまで Linda Server へは送信されない。メイン
ループ内は３つのパートに分かれる。まずは``通信以外の処理''では、クライア
ントの処理を行う。ここでデータのin, read, out 等を実行してもよい。次に 
{\tt reply()} で in/read した時の応答が受け取ったかを確認。受け取っていたなら
({\tt if} 内が実行され)受け取ったデータの処理を行う。そして最後に{\tt sync()}を呼
んで通信を行う。

この例は基本的なプログラミングである。しかし、メインループ内で {\tt sync()} は
一度だけ呼ぶ事、{\tt reply()} でデータの受信を確認する事など、ポーリングを意識
したプログラミングの特徴を表している。

また、{\tt reply()} のデータ取り出し時や {\tt sync()} の通信時で``待ち''に入る事はな
い。よって、通信以外の処理が待たされることはないが、逆に通信以外の処理で
``待ち''が入ると、通信が滞る。通信以外の処理においても``待ち''が入らない
ようなスタイルを取る必要がある。

\subsubsection{Protocol Engine へのアクセス}

クライアントプログラムは使用する Protocol Engine とはタプルスペースを介
してデータをやり取りする。データのやり取りは Linda をベースにした in,
read, out という分かりやすいモデルになっている。

Protocol Engine への依存は低い。実際、タプルIDを各プロトコル毎に割り当て
ることにより、使用するプロトコルを切替えるということもできる。この場合、
in, read, out などのコマンドで指定する タプルID を変更するだけでいい。

以下に例を挙げる(図\ref{select_protocol}参照)。

\begin{figure}[htp]
\begin{center}
\includegraphics[width=8cm]{fig/pdf/select_protocol.pdf}
\caption{使用するプロトコルの切替え}
\label{select_protocol}
\end{center}
\end{figure}

この図の場合、タプルIDの 10000 番を Distance Vector 型 Routing Protocol
に、タプルID 10001 番を Broad Cast Protocol に割り当てている。クライアン
トプログラム(Client Application)は、in, read, out するときの引数として渡す
タプルIDを 10000 すると Distance Vector 型 Routing Protocol を用いたデー
タ転送を行い、 10001 すると全タプルスペースへ Broad Cast することになる。

プロトコルへのアクセスは in, read, out などの単純なコマンドで行われるの
で分かりやすい。また、プロトコル切替えが容易であるので、多数のプロトコル
を用いたプログラムを記述しやすい。

\subsection{Protocol Engine}
type 2 では Protocol Engine は Linda API を用いて実装する。よって実装の
スタイル自体は Local Access Protocol にて説明した通りである。そしてそ
の API を用いて分散アルゴリズムを実装する。分散アルゴリズムは多種多様あ
り、またその実装方法も多い。しかし、タプルのやり取りの部分はやタプルIDの
使いかたなどは共通しているので、その部分を説明する。

以下にマルチキャストを行うプロトコルのメインループの例を挙げる。

この例では、{\tt \$TUPLE\_ID\_CONNECT, \$TUPLE\_ID\_SEND,
\$TUPLE\_ID\_RECV} の３つのタプルIDを使用している。また、接続先の Linda
Server を配列を用いて管理している。

{\tt \$TUPLE\_ID\_CONNECT}に投入されたタプルは新しく接続する Linda Server の
ホスト名とポート番号が入っており、{\tt getTuplespace()} 内 で
{\tt FederatedLinda->open()} している。

{\tt \$TUPLE\_ID\_SEND}に投入されたタプルは、マルチキャストしたいデータを含
んでいる。よって、自分が接続している全Linda Server の{\tt \$TUPLE\_ID\_RECV}
へタプルを投入する。クライアントは、データを送りたいときは
{\tt \$TUPLE\_ID\_SEND}へタプルを{\tt out}し、受け取りたいときは、
{\tt \$TUPLE\_ID\_RECV}へ{\tt in}する。

\begin{center}
\begin{itembox}[l]{マルチキャストのプロトコルの例}
\begin{verbatim}
@tuplespaces # マルチキャストする相手の Linda インスタンス
$linda       # 自分が担当する Linda 
# メインループ
while (1) {
    # 接続に変更があった場合の処理
    if (($data = $ConnectRep->reply()) > 0) {
        $ConnectRep = $linda->in($TUPLE_ID_CONNECT);
        # $dataから接続相手を得て、@tuplespaces へ加える
        @tuplespaces = (@tuplespaces, getTuplespace($data));
    }
    # マルチキャスト
    if (($data = $MultiCastRep->reply()) > 0) {
        # 繰り返しIDに対してタプルの取得要求を出す
        $MultiCastRep = $linda->in($TUPLE_ID_MULTICAST);
        # 全タプルスペースへデータを送信
        foreach $t (@tuplespaces) {
            $t->out($TUPLE_ID_RECV, $data);
        }
    }
    FederatedLinda->sync();
}
\end{verbatim}
\end{itembox}
\end{center}

この例では 自分が担当する Linda Server の二つのタプルID(
{\tt \$TUPLE\_ID\_CONNECT, \$TUPLE\_ID\_SEND})に {\tt in} をしており、それぞれの
タプルIDで取り扱われるデータを分けている。また、クライアントのデータ送信・
受信をそれぞれ {\tt \$TUPLE\_ID\_SEND, \$TUPLE\_ID\_RECV} へ割り当てている。
このようにタプルID毎に取り扱うデータを決めておき、そのIDからのデータを受
け取ったら、対応する処理を行うということができる。当然タプルのデータ部に
プロトコル独自のヘッダなどを入れて、それで行う処理を選択することもできる。
しかしその場合はデータ自身がその Protocol Engine に依存するので、他の
Protocol Engine では使えなくなる。

よって、様々な Protocol Engine で使われるデータなどは、その処理の選択は
タプルID毎に行うと良い。そうでない場合は同一タプルIDを使うという手段
もある。

\newpage
\subsection{Link Configuration}

Linda Server 間は Protocol Engine で接続される。その接続の形を規定するの
が Link Configuration である。Link Configuration ではタプルスペース間を
どのように接続するかを XML で記述しており、それを基にネットワークを構築
する。

図\ref{linkconfig_xml}では Configurator というプロセスが 接続状態を表し
た XML を Linda Server へ投入し、そのXMLを元にトポロジを構築している。
このXMLを投入するプロセスはクライアントプログラムでも Protocol Engine で
もよい。

\begin{figure}[htp]
\begin{center}
\includegraphics[width=13cm]{fig/pdf/lc.pdf}
\caption{Configuratorによるトポロジ形成}
\label{linkconfig_xml}
\end{center}
\end{figure}

Link Configuration では、取り扱う XML のパーサとトポロジの接続の状態を
表したデータ構造、接続を行う関数などをプロトコルとして Protocol Engine
へ組み込めるように、モジュールとして提供している。以下ではその説明を行う。


\subsubsection{トポロジを表すXML}

まず、トポロジを規定するXMLについて説明する。このXMLの形式は独自に定めた
ものである。

以下に挙げる例は、ノード数 ４ で、Ring トポロジを表した XML である。この
例を用いて XML の形式を説明する。

\begin{center}
\begin{itembox}[l]{Ring トポロジを表す XML例}
\begin{verbatim}
<graph name = "Ring">
    <node label = "lindaA" tsid = "localhost:10000">
        <destination label = "lindaC"/>
        <destination label = "lindaB"/>
    </node>
    <node label = "lindaB" tsid = "localhost:10002">
        <destination label = "lindaD"/>
        <destination label = "lindaA"/>
    </node>
    <node label = "lindaC" tsid = "localhost:10003">
        <destination label = "lindaD"/>
        <destination label = "lindaA"/>
    </node>
    <node label = "lindaD" tsid = "localhost:10004">
        <destination label = "lindaB"/>
        <destination label = "lindaC"/>
    </node>
</graph>
\end{verbatim}
\end{itembox}
\end{center}

各タグの説明をする。

\begin{itemize}
\item {\tt graph} - トポロジを表すルートタグ
\begin{description}
\item [~{\tt name}] - トポロジの名前などを表す。任意
\end{description}
\item {\tt node} - Linda Server を表すタグ。子要素として、接続先を表した 
	  {\tt desitination} タグを持つ。
\begin{description}
\item [~{\tt label}] - ノードに付けられたラベル。この属性を元に接続状況を調べる。
\item [~{\tt tsid}] - Linda Server のタプルスペースID。どのタプルスペースがこのノー
			ドを担当するかを表す。
\end{description}
\item {\tt destination} - 接続先を表すタグ。
\begin{description}
\item [~{\tt label}] - 接続先のラベル。XML内のどの {\tt node} タグに対応するかを表す。
\end{description}
\end{itemize}

このXMLは非常に単純な構造をしている。まずルートタグの下には各 Linda
Server を表す {\tt node} タグがある。この {\tt node} タグには各々個別の名
前({\tt lable}属性)が付けられている。また、そのノードを担当する Linda
Server のタプルスペースID({\tt tsid}属性)が付いている。接続状況などは
{\tt lable} を用いて表される。{\tt node} タグは子として {\tt
destination} タグを持つ。{\tt destination} タグは、{\tt node} がどのノー
ドと接続するかを表している。あて先は {\tt lable}属性を用いて表される。
{\tt node} タグで定義されていない {\tt lable} や、親の {\tt lable} を指定
することはできない。{\tt destination} はあて先を表しており、単方向グラフ
になっている。

このXMLは Protocol Engine が解析することになる。Protocol Engine に組み込
むパーサと自身が接続する相手先を取得するモジュールを提供している。次では
その説明を行う。

\subsubsection{接続を行うモジュール}

Link Configuration では Link Configuration の XML を変換するパーサと、変
換されたデータ構造を表すクラスを提供している。図\ref{LinkConfig-class}に
そのクラス図を示す。

\begin{figure}[htb]
\begin{center}
\includegraphics[width=13cm]{fig/pdf/LinkConfig-class-dig.pdf}
\end{center}
\caption{LinkConfiguration のクラス図}
\label{LinkConfig-class}
\end{figure}

提供するクラスは、{\tt LinkConfigParser, LinkConfiguration, NodeInfo} の３つで
ある。これらのメンバとメソッドの説明を以下に示す。

\begin{itemize}
\item {\tt LinkConfigParser} - XMLを解析し、その結果である {\tt
 LinkConfiguration} インスタンスを返す
\begin{description}
\item [~{\tt parseLinkConfig(tsid, xmltext)}] - XMLを解析する。引数として自分のタ
			プルスペース ID({\tt tsid})、解析するXML({\tt xmltext})を取る。解析結果
			の {\tt LinkConfiguration} インスタンスを返す。
\end{description}
\item {\tt LinkConfiguration} - 各ノードの接続を表すクラス。
\begin{description}
\item [~{\tt tsid}] - タプルスペースID
\item [~{\tt lable}] - 自分が担当するタプルスペースのラベル
\item [~{\tt linklist}] - XMLで示された全ノードの接続をハッシュとして保持。キーと
			してラベルを使用。値は {\tt NodeInfo} インスタンス。
\item [~{\tt getDstlist(label)}] - 引数で渡したラベルのノードが接続する相
			手のラベルの配列を取得
\end{description}
\item {\tt NodeInfo} - ノードを表すクラス
\begin{description}
\item [~{\tt tsid}] - ノードを担当するタプルスペースのID
\item [~{\tt lable}] - ノードのラベル
\item [~{\tt dstlist}] - ノードが接続するノードのラベルのリスト
\end{description}
\end{itemize}

これらのクラスを使い、XMLより自分が接続する相手先のタプルスペースIDの一
覧を取得し、{\tt FederatedLinda.open} を行うことになる。{\tt Linda} クラスの管理は各
プログラムに任せる。また、{\tt LinkConfiguration} インスタンスを複数持つことに
より、一つの Protocol Engine で別々のトポロジに参加することも可能である。