\chapter{Federated Lindaを用いたプログラミング}

ここでは Federated Linda のモジュールを使ったプロトコルエンジンやクライ
アントプログラムの説明をする。最初に Treeトポロジを用いたタプルのブロー
ドキャストを説明し、次に Distance Vector 型 Routing Protocol を説明する。

\section{Treeトポロジを用いたタプルのブロードキャスト}

例題として、IRC のような一つのノードへの入力を木構造を通して、配布する例
を考える。この場合のトポロジーは、図\ref{TreeBCast}の木構造を用いる。

Engine は
{\tt Leaf Engine, Node Engine, Root Engine}
の三種類がある。


\begin{figure}[htp]
\begin{center}
\includegraphics[width=13cm]{fig/TreeBCast.eps}
\caption{木構造を通したタプルのブロードキャスト}
\label{TreeBCast}
\end{center}
\end{figure}

{\tt Root Engine}は 木構造の一番上に配置する。{\tt Leaf Engine} は木構造の末端。Node
Engine はその間に配置される。この Protocol Engine の違いは、受け取ったタ
プルをどのように次のタプルスペースへ送信するか、という点である。

以下にその説明をソースコードを示しながら説明する。

\subsection{{\tt Leaf Engine}}
{\tt Leaf Engine} は、末端のタプルスペースへタプルを投入する。また、投入された
タプルが返って来るのを待ち、返って来たら標準出力に書き出す。

\begin{center}
\begin{itembox}[l]{{\tt Leaf Engine}}
\begin{verbatim}
# タプルスペースへ接続する
my $linda = 
  FederatedLinda->open($hostname, $port);
# タプルスペースへ $data を送信する
$linda->out($TUPLE_ID_UP, $data);
# 答を待つ
$rep = $linda->in($TUPLE_ID_DN);
while (1) {
  if ((my $reply = $rep->reply()) > 0) {
    print "Got : $reply, \n";
  }
  FederatedLinda->sync();
}
\end{verbatim}
\end{itembox}
\end{center}

\subsection{{\tt Node Engine}}
{\tt Node Engine} は、子供から来たタプルを親に転送する。
親から来たタプルは、自分の全ての子供に複製する。

親から来たタプルと子供から来たタプルは、別のタプルIDを使っている。タプル
ID {\tt \$TUPLE\_ID\_UP} は子供から来たタプルで、タプルID {\tt \$TUPLE\_ID\_DN}
は親から来たタプル、という風に使い分けている。

\begin{center}
\begin{itembox}[l]{{\tt Node Engine}}
\begin{verbatim}
# タプルスペースへ接続する
my $linda=
   FederatedLinda->open($hostname,$port);
# タプル監視用の in
for (my $i=0; $i < $children_num; $i++) {
 $children_rep[$i]=
   $children[$i]->in($TUPLE_ID_UP);
}
$parent_rep = $parent->in($TUPLE_ID_DN);
while (1) {
  my $reply;
  # 子からタプルを受け取り、親へ送信。
  # 下から上へ
  for (my $i=0; $i < $children_num; $i++) {
    $reply = $children_rep[$i]->reply();
    if ($reply) {
      $children_rep[$i] = 
        $children[$i]->in($TUPLE_ID_UP);
print "UP:$reply $children[$i]->{'tsid'}\n";
      $parent->out($TUPLE_ID_UP, $reply);
      last;
      }
    }
    # 親からタプルを受け取り、子へ送信。
    # 上から下へ
    if ($reply = $parent_rep->reply()) {
      $parent_rep = $parent->in($TUPLE_ID_DN);
print "Down:$reply from $parent->{'tsid'}\n";
      foreach my $c (@children) {
        $c->out($TUPLE_ID_DN, $reply);
      }
    }
    FederatedLinda->sync();
  }
}
\end{verbatim}
\end{itembox}
\end{center}


\subsection{{\tt Root Engine}}
{\tt Root Engine} は、子供から来たタプルをすべての子供に複製する。

\begin{center}
\begin{itembox}[l]{{\tt Root Engine}}
\begin{verbatim}
my $linda=FederatedLinda->open($hostname,$port);
# 子からのデータを待つ
$rep = $linda->in($TUPLE_ID_UP);
# 子からのデータを受け取ると、
# 下り用のデータ送信をする
while (1) {
  if ((my $reply = $rep->reply()) > 0) {
    print "Got $reply\n";
    $rep = $linda->in($TUPLE_ID_UP);
    $linda->out($TUPLE_ID_DN, $reply+1);
  }
  FederatedLinda->sync();
}
\end{verbatim}
\end{itembox}
\end{center}

\subsection{実装について}

この例では、{\tt Leaf Engine} がクライアント、{\tt Node Engine}, {\tt
Root Engine} がProtocol Engine の役割を果たしている。各 Engine のソース
コードの行数とその合計は以下のようになる。

\begin{verbatim}
[yasumura@karateka Tree]$ wc -l *.pl
  36 Leaf.pl
  81 Node.pl
  39 Root.pl
 156 合計
[yasumura@karateka Tree]$
\end{verbatim}

多くても80行程度と、どの Engine も簡潔に短い行で書けていることが分かる。
これは、in や out など、単純なコマンドでタプルを出し入れするという通信モ
デルに依るものだといえる。また、ポーリング型のプログラミングでは、要求を
出して、その答えが返って来たらアクションを起こすという形になっており、ア
クションの要因が明確である。


\section{Distance Vector型ルーティングプロトコル}

type2 において分散システムを構築するため、基本的なプロトコルである、ルー
ティングプロトコルをPythonで実装した。ルーティングはRIP(Routing
Information Protocol)などのディスタンスベクタ型を参考にし、各タプルスペー
スごとに経路テーブル情報を用意した。タプルスペース自体はルーティングを行
わず、代わりにルーティングなどを行うエージェントを作成した。また、論理ネット
ワーク構築してからルーティングテーブルが収束するまでの時間を計測した。

ルーティングに用いるテーブルには

\begin{itemize}
\item タプルを送る宛先(タプルスペースのID)
\item 次ホップ
\item ホップ数
\end{itemize}

の情報が含まれている。タプルスペースのIDは、``ホスト名:ポート番号''として
いる。これは、タプルスペースに一意なIDを割り振る目的でこの型式を取った。
次ホップは、宛先のタプルスペースに送るために、隣り合ったどのタプルスペー
スにタプルを送るべきかを表わす。ホップ数は、宛先へ送り届けるために通るタ
プルスペースの数を表わす。

タプルを送る場合、宛先と送りたいタプルを指定する。ルーティングエージェ
ントは、その指定された宛先を、自分が保持しているルーティングテーブルか
ら引き、次にどのタプルスペースへタプルを渡せばいいかを判断する。テーブ
ルを表すデータ構造は、以下のクラスを値とした{\tt hash} を用いて実装した。

\begin{center}
\begin{itembox}[l]{他のタプルスペースの情報を表すクラス}
\begin{verbatim}
class TSInfo:
    def __init__(self, tsid, hopnum, nexthop):
        self.tsid = tsid        # tuple space id, like 'host:port'
        self.hopnum = hopnum    # hop number
        self.nexthop = nexthop  # next hop (tuple space id)
\end{verbatim}
\end{itembox}
\end{center}

ルーティングプロセスは、起動すると、まず、自分が担当するタプルスペースへ
接続し、そのIDをルーティングテーブルへ登録する。次に、Link Configuration
などにより、他のタプルスペースへの接続を行う。この場合も各タプルスペース
のID をテーブルへ登録する。このとき、次のホップ、ホップ数も一緒に登録され
る。{\tt hash} へは宛先をキーとして、次のホップとホップ数が引けるように実
装した。

以下にルーティングテーブルへノード情報を登録する関数を載せる。引数として、
宛先のタプルスペースID、次ホップ、ホップ数を取る。ルーティングテーブルは
{\tt tslist}という{\tt hash} である。
{\tt hash} で作成されたテーブルは、XML形式に変換して他のタプルスペースへ送信する。

\begin{center}
\begin{itembox}[l]{ルーティングテーブルへノード情報を登録する}
\begin{verbatim}
def register(self, tsid, hopnum, nexthop):
    if (self.tslist.has_key(tsid)):
        del self.tslist[tsid]
        self.tslist[tsid] = TSInfo(tsid, hopnum, nexthop)
\end{verbatim}
\end{itembox}
\end{center}

ルーティングテーブルの作成が終わると、メインループへと入る。メインループ
は大きく三つの処理に分かれる。ルーティングテーブルの更新処理、ルーティン
グテーブルを使ったタプル転送、そして他のタプルスペースと接続を行うLink
Configurationである。

下記にそのソースコードを載せる。

\begin{center}
\begin{itembox}[l]{ルーティングプロトコルのメインループ}
\begin{verbatim}
while (1):
    rep = self.updateReply.reply()
    if (rep):    # ルーティングテーブルの更新処理
        self.updateRply = self.linda.In(TUPLE_ID_TABLE_UPDATE)
        srcname = self.rt.getdstname(rep)
        if ( self.rt.update(rep, srcname) ): # ルーティングテーブルを更新
            # 更新したテーブルを他のタプルスペースへ送信
            upedxml = self.rt.getxml()
            for n in self.neighbors.values():
                n.Out(TUPLE_ID_TABLE_UPDATE,upedxml)
    rep = self.sendReply.reply()
    if (rep):    # タプル転送
        self.sendReply = self.linda.In(TUPLE_ID_ROUTING_SEND)
        dsttsid, tid, rest = string.split(rep,',',2)
        # 転送相手先が自分なら、指定されたタプルIDへoutする
        if (dsttsid == self.rt.name):
            dsttid = int(tid)
            dstts = self.linda
        # 次ホップへ転送する
        else:  
            dsttid = TUPLE_ID_ROUTING_SEND
            dstts = self.neighbors[self.rt.tslist[dsttsid].nexthop]
        dstts.Out(dsttid, rep)
    rep = linkConfigReply.reply()
    if (rep):    # Link Configuration
        linkConfigReply = self.linda.In(TUPLE_ID_LINKCONFIG)
        # XMLをパース
        linkConfig = lcparser.parseLinkConfig(self.tsid, rep)
        # 自分と接続する相手のリストを取得
        mydstlist = linkConfig.getDstlist(linkConfig.label)
        for n in mydstlist:
            tsid = linkConfig.linklist[n].tsid
            # 知らない相手に対して接続し、LinkConfigurationXMLを送信
            if ( tsid and not self.neighbors.has_key(tsid) ):
                ts = self.connect(tsid)
                ts.Out(TUPLE_ID_LINKCONFIG, rep)
                ts.Out(TUPLE_ID_ROUTING,self.pack(self.tsid,
                       ROUTING_COMMAND_CONNECT))
    self.flinda.sync()
\end{verbatim}
\end{itembox}
\end{center}

ルーティングテーブルの更新情報を受け取ったタプルスペースでは、ルーティン
グプロトコルがその情報を受け取り、自身のルーティングテーブルを更新する。更
新は受け取ったテーブルと自身のテーブルの統合をする。統合は、受け取ったテー
ブルにおいて

\begin{enumerate}
\item 知らない宛先
\item 既知の宛先だが、ホップ数が小さい
\end{enumerate}
場合のみ、自身のテーブルに統合する。ホップ数は登録するときに 1 増やし
ている。

\begin{center}
\begin{itembox}[l]{テーブル情報の更新}
\begin{verbatim}
def update(self, xmldoc, tsport):
    rt = xml.dom.minidom.parseString(xmldoc).childNodes[0]
    tslist = rt.childNodes
    updateflag = False
    # append tuplespace
    for ts in tslist:
        if ts.nodeType==ts.ELEMENT_NODE and ts.localName=='ts':
            tsattr  = ts.attributes
            tsid    = tsattr['tsid'].nodeValue
            hopnum  = int( tsattr['hopnum'].nodeValue )
            nexthop = tsport
            # 既に登録されていないもしくは
            #ホップ数が小さいものをものは登録する
            if ((not self.tslist.has_key(tsid)) or
                (self.tslist[tsid].hopnum > hopnum+1)):
                self.register(tsid, hopnum+1, nexthop)
                updateflag = True
\end{verbatim}
\end{itembox}
\end{center}

次にタプル転送について説明する。ルーティングエージェントは自分が担当する
タプルスペースのタプル転送用のタプルIDへタプルが投入されると、それを取得
する。取得したタプルのデータ部は、転送するためのヘッダと送信したいデータ
が以下の形で格納されている。

\begin{verbatim}
"宛先タプルスペースID,タプルID,発信元タプルスペースID,データ"
\end{verbatim}

各情報はコンマで区切られた文字列である。まず宛先タプルスペースIDは送り先
のタプルスペースID({\tt ``hostname:portnumber''}の形式)。次のタプルIDは、宛先
のタプルスペースで投入するタプルID。発信元タプルスペースIDは最初にタプル
を投入したタプルスペースIDである。これらの情報とルーティングテーブルを元
に、宛先タプルスペースまでルーティングを行う。

まず転送するタプルを受け取ると、その宛先タプルスペースIDが自分が担当して
いるタプルスペースかどうかを調べる。もし自分が担当するタプルスペースなら
ば、指定されたタプルIDへタプルを投入する。そうでない場合はルーティングテー
ブルから次ホップを調べ、そのタプルスペースのタプル転送用のタプルIDへタプ
ルを投入する。

以上の手順でルーティングテーブルを使ってタプルを宛先まで転送する。


\subsection{論理ネットワークの構築}

タプルスペースとProtocol Engineの論理ネットワークはLink Configurationの
トポロジ構築用XMLにて構築される。このXMLは単純な構造をしており、自動で生
成・変換することが容易である。今回、ルーティングテーブルの収束時間を計測
するにあたり、ドローイングツールからの変換スクリプトを記述した。それを用
いてより直感的に論理ネットワークを記述することを可能にした。

使用したツールはOmni社が提供しているOmniGraffle 3.2.4である。その標準の
保存形式graffleから論理ネットワークを構築するまでの手順は図
\ref{configurator}の通りである。この変換スクリプトにより、より容易にトポ
ロジを切り替えての実験が行えた。

  \begin{figure}[htb]
   \begin{center}
\includegraphics[width=14cm]{fig/configurator.eps}
   \end{center}
   \caption{OmniGraffleから論理ネットワークを構築}
   \label{configurator}
  \end{figure}


\subsection{計測}
実装した Distance Vector型ルーティングを用いて、ルーティングテーブルが生
成されるまでの時間
%% と、ホップ数毎のタプル転送時間
について計測を行った。

ルーティングテーブルについては、LinkConfigurationからの他タプルスペース
への接続要求を受け取ってから、ルーティングテーブルが最短経路を構築するま
での時間を各ノードで計り、その平均を出した。

以下にバイナリーツリートポロジのと格子状のメッシュトポロジのルーティング
テーブルを構築したときの結果を載せる(図\ref{routingtable})。

  \begin{figure}[htb]
   \begin{center}
\includegraphics[width=10cm]{fig/exetime.eps}
   \end{center}
   \caption{ノード数に対してルーティングテーブルを構築するのにかかる時間}
   \label{routingtable}
  \end{figure}

ルーティングテーブルが構築されるまでにかかる時間は、ノード数に対して２乗
オーダ的に増加する。これは、ルーティングテーブルの更新情報をノードが受け取
ると、自身のルーティングテーブルを更新し、接続している他のノードへ更新情
報を配信するため、メッセージ数が２乗オーダに増えるためである。しかし、テー
ブル情報のホップ数が最短経路でないときは更新をしないため、更新のトラフィッ
クは徐々に収束へ向かう。

またツリートポロジとメッシュトポロジを比較すると、メッシュの方がツリーよ
りルーティングテーブルが収束する時間が非常に大きい。これは、ルーティング
テーブルを全ノードへ送信する際に、メッシュトポロジの方がメッセージ数が多
くなることが原因と考えられる。

\subsection{実装について}

分散システムを構築するための基本的なプロトコルであるルーティングプロトコ
ルを Protocol Engine に実装した。Pythonで実装できたので、ハッシュや XML
のパーサなどの実装手間が掛からなかったので、素早く実装できた。ただ、実装
した Distance Vector 型ルーティングプロトコルは、ネットワークが頻繁に変化
すると、テーブル情報の更新作業によるトラフィックが起こってしまう。これは、
分散システムにはあまり適したルーティングとはいえない。

しかし、分散システムを作る上で必要となるルーティングプロトコルを作ること
ができたので、これを用いてアプリケーションの開発も可能となった。

以下に実装した Distance Vector 型 ルーティングプロトコルの行数を示す。
ルーティングプロトコル{\tt Routing.py} 以外に、ルーティングを用いたタプ
ル転送を行うための、タプルを送受信するクライアントプログラム({\tt
RoutingClient.py}) とLinkConfigurationのモジュール({\tt
LinkConfiguration.py})の行数も挙げておく。

\begin{verbatim}
[yasumura@karateka Routing]$ wc -l *.py
     267 Routing.py
     104 RoutingClient.py
      74 LinkConfiguration.py
     445 total
[yasumura@karateka Routing]$ 
\end{verbatim}

ルーティングプロトコルも250行程で記述できることが分かる。