\chapter{Compact Routing の実装によるtype 2 Federated Linda の評価}
type2によるFederated Lindaの実装には、Protocol Engineによるタプル空間の
ルーティングアルゴリズムが必要になることを述べたが、
先行研究[2][3]によって既に、Distance Vector型ルーティングプロトコルを行うtype2の
Federated Lindaが実装されている。その基本アイデアは全対全の最短路を求めるもので、
各ノードが他の全ノードへの最短路に沿った次ホップを蓄えた表（ルーティングテーブル）を
保持するルーティング方式である。
この方式は実装が容易でルーティング経路が最適であるという長所がある半面、
ルーティング情報の伝播が遅いほか、ルーティングテーブルの記憶領域が膨大となる点やあるルートがダウン
した際に起こるルーティングループなどといった様々な分散プログラムに適さない欠点がある。

そこで、より高度なProtocol Engineの実装の検証とtype2による実装の経験を積む為に、
今回新たにNプロセスに対して、各プロセスが$Sublinear$で$O(N)$とみれるルーティングテーブルの
記憶領域(入力に対して２乗など比例より大きな変化をする場合を$Superlinear$、
比例より小さい変化を$Sublinear$と呼ぶ)を用い、
ルーティングテーブルの収束速度やネットワークのスケーラビリティに対して優位な
ルーティングアルゴリズムである、
``コンパクトルーティング''(Cowen,[7])を行うProtocol Engineを実装した。



コンパクトルーティングのアルゴリズム的改良としては参考資料[8][9]のような改良が試みられているが、
実際にコンパクトルーティングを実装し、テストを行った例は報告されていない。これは新規性の分散
アルゴリズムを実装し評価するフレームワークが少数しか存在せず、また存在する分散フレームワークに
おいてもその複雑性や機能特化によってテストに適さない為である。
今回の様にコンパクトルーティングのような新規アルゴリズムを比較的容易にテストとして実装出来る点は
Federated Lindaの利点であると言える。

\section{Compact Routingのアルゴリズム}
コンパクトルーティングでは、各ノードがある一定の範囲の近傍ノードに対しては完全な
ルーティング情報を持ち、遠くのノードに対してはLandmarkと呼ばれるいくつかの選ばれた
ノードに対してのルーティング情報のみを持つようにすることでルーティングテーブルのサイズ
と更新量を抑える事が出来る。次表にコンパクトルーティングによるルーティングアルゴリズム
の全体構造を示す。

\begin{center}
\begin{itembox}[l]{アルゴリズムの全体構造}
{\small
\begin{center}
\begin{verbatim}
[準備]
・XMLによりタプル空間同士のネットワークとProtocol EngineのLink Configuration
　を行う。

[ルーティングテーブル構築]
・全ノードは自身に近いノード、つまりローカルネットワークのルーティングテーブル
　を構築する。
　・ローカルネットワークの経路情報はホップ数をメトリックにディスタンスベクタ型
　　で求める。
・全Landmarkを求め、全ノードは全Landmarkに対するルーティング情報を求める。
　・Landmarkに対するルーティング情報は各Landmarkへの最短路上の次ホップ。

[ルーティング]
・宛先はLandmarkのアドレスと転送先アドレスの２つを指定する。
・投入時のローカルネットワークに宛先があるときはローカルネットワークのルーティン
　グを行う。
・それ以外の時、最寄りのLandmarkを経由し宛先Landmarkへ転送する。
　・宛先Landmarkへ到達したら、宛先ローカルネットワーク内の経路に従い転送する。
\end{verbatim}
\end{center}
}
\end{itembox}
\end{center}

\section{実装の詳細}
コンパクトルーティングを実装したProtocol Engineが持つルーティングテーブルは
タプル空間に格納されたXMLファイルから生成される。
この際、アドレスとして扱う情報は、IPアドレス:Port番号 ~の組で表した物を指す。
ルーティングテーブルとタプル空間でやり取りされるXMLデータの関係を図\ref{data}に示す。
\begin{figure}[htbp]
 \begin{center}
  \includegraphics[width=11cm]{fig/pdf/XMLandRoutingTable.pdf}
  \caption{ルーティングテーブルとタプル空間でやり取りされるXMLデータの関係}
  \label{data}
 \end{center}
\end{figure}


また、Local Access to Protocol, Link Configuration に関してはDistance Vector型
ルーティングを行う実装[3]と同様のものを利用する。
このような実装が可能なのはFederated Lindaが分散プログラムの３つの要素を明示的に
分けて記述している為であり、具体的なこれら３つの実装は表\ref{jissou1}のようになっている。

\begin{table}[htbp]                                                                        
 \begin{center}      
 \caption{分散プログラムの３つの要素}    
 \label{jissou1}
  \begin{tabular}{|l|l|} 
   \hline
   Local Access to Protocol & Linda API, \\ 
   & C言語モジュール\\ 
   \hline
   Protocol Engine  & Pythonスクリプト(新たに作成) \\
   \hline
   Link Configuration  &  Omni Graffleファイル, \\ 
   & XML生成Pythonスクリプト\\
   \hline
  \end{tabular}
 \end{center}
\end{table}

\subsection{Protocol Engineによるルーティングテーブルの構築}
Protocol EngineはPythonスクリプトで記述され、コンパクトルーティングを行う為の
ルーティングテーブルを生成する。ルーティングに必要なテーブルはローカルエリアネット
ワークとLandmarkに関するルーティングテーブルとなる。

この際、ルーティングテーブルに格納される情報は以下のようになる。
  \begin{figure}[htbp]
   \begin{center}
\includegraphics[width=13.5cm]{fig/pdf/routing_landmark.pdf}
   \end{center}
   \caption{ルーティングテーブルの例}
   \label{localarea}
  \end{figure}

\subsubsection{ローカルエリアネットワークの構築}
コンパクトルーティングを実装する場合、ローカルエリアネットワークを構築しなければ
ならない。そのネットワークは、Landmarkを中心とするネットワークである(図\ref{localarea})。
  \begin{figure}[htbp]
   \begin{center}
\includegraphics[width=10cm]{fig/pdf/landmark.pdf}
   \end{center}
   \caption{ローカルエリアのホップ数が１の場合}
   \label{localarea}
  \end{figure}

\subsubsection{LandMark情報の更新}
全ノードは全てのLandmarkに対するルーティング情報を持つよう更新される。
仮にローカルエリアがLandmarkから１ホップの範囲だとすると、
図\ref{configurator.new}のようにLandmark情報が更新される。

  \begin{figure}[htbp]
   \begin{center}
\includegraphics[width=9cm]{fig/pdf/land_update.pdf}
   \end{center}
   \caption{ローカルエリアのホップ数が１の場合のLandmark情報の流れ}
   \label{configurator.new}
  \end{figure}

\newpage
\subsection{Protocol Engineの継承による実装}
コンパクトルーティングを行うProtocol EngineはPythonスクリプトで記述される。
Pythonは汎用的で上位レベルな、オブジェクト指向のプログラミング言語であり、
それによってDistace Vector型ルーティング[3]を行うProtocol EngineのPythonスクリプトを、
コンパクトルーティングを実装するいくつかの点においてPythonコードの継承や流用を行うこと
が可能となる。例として、ルーティングテーブルの情報について挙げると、
Distance Vector型ルーティングの実装で用いたルーティングテーブルを、
クラスの継承を用いる事でコンパクトルーティングにおけるローカルエリアネットワーク
へのルーティングテーブルとして利用可能である。

\begin{center}
\begin{itembox}[l]{DV型ルーティング実装Routing.py}
%{\scriptsize
\begin{verbatim}
# 他のタプルスペースの情報を表すクラス
class TSInfo:
    def __init__(self, tsid, hopnum, nexthop):
        self.tsid = tsid        
        self.hopnum = hopnum    
        self.nexthop = nexthop 

# TSInfoのリストでルーティングテーブルを表すクラス
class RoutingTable:
    def __init__(self, name):
        self.tslist = {}
        self.name = name
\end{verbatim}
%}
\end{itembox}
\end{center}

\begin{center}
\begin{itembox}[l]{Cルーティング実装CompactRouting.py}
%{\scriptsize
\begin{verbatim}
# Landmark情報を表すクラス
class Landmark_TSInfo:
    def __init__(self, landmark_tsid, landmark_dst):
        self.landmark_tsid = landmark_tsid
        self.landmark_dst = landmark_dst

# クラスRoutingTableを継承し、Landmarkのリストを持つクラス
class CompactRoutingTable(RoutingTable):
    def __init__(self, name):
        RoutingTable.__init__(self, name)
        self.landmark_tslist = {}
\end{verbatim}
%}
\end{itembox}
\end{center}

上記のように定義した場合、クラスCompactRoutingTableは Distance Vector型ルーティングで
定義された、クラスRoutingTableを継承して利用できる。

また、Protocol Engineのメインループにおいても、変更が必要なメソッドのみを
オーバーライドして定義することで、Link Configurationなどの動作が以前の実装と
同様でも良い部分のコーディングを省略することができる。
以下にそのメインループのソースコードを示す。

\begin{center}
\begin{itembox}[l]{Protocol Engineのメインループ}
%{\scriptsize
\begin{verbatim}
while(True):	#polling base loop    
   # Link Configuration
   rep = linkConfigReply.reply()  
   if(rep):
       linkConfigReply = self.linda.In(TUPLE_ID_LINKCONFIG)
       # Link Configuration main (use Routing class method) 
       self.LinkConfig(self.tsid, rep)

   # Routing Protocol
   rep = routingReply.reply()
   if(rep):
       routingReply = self.linda.In(TUPLE_ID_ROUTING)
       cmd , data = self.unpack(rep)
       # connect to other tuplespace
       if (cmd == ROUTING_COMMAND_CONNECT):
           self.RoutingConnect(data)
       # disconnect other tuplespace
       elif (cmd == ROUTING_COMMAND_DISCONNECT):
           self.RoutingDisconnect(data)
       # transfer tuple
       elif (cmd == ROUTING_COMMAND_TRANSFER):
           self.RoutingTransfer(data)
       # update own routing table
       elif (cmd == ROUTING_COMMAND_UPDATE_TABLE):
           self.RoutingTableUpdate(data)
       else:
 	   self.flinda.sync()
#end while
\end{verbatim}
%}
\end{itembox}
\end{center}

このように、PythonによるProtocol Engineの実装は、
仮に新しい実装が必要になった場合でも新たに機能を拡張する差分だけを
プログラミングすればよいので、ソフトウェア開発の効率化が行えると言える。


\begin{verbatim}

\end{verbatim}
\subsection{ルーティングテーブルの構築、更新処理}
ルーティングテーブルの構築、及び更新処理はRutingTableUpdateメソッドで行われ、
それはDistance Vector型ルーティングにおける実装での同名メソッドに対して
オーバーライドして定義される。以下にそのソースコードを示す。
%\begin{verbatim}

%\end{verbatim}
\begin{center}
\begin{itembox}[l]{RoutingTableUpdateメソッド}
%{\scriptsize
\begin{verbatim}
def RoutingTableUpdate(self,data):
    print "update"
    srcname = self.rt.getdstname(data)

    # Landmark find                                                       
    if(self.rt.getNewLandmark()):
         self.rt.landmark_register(self.rt.name, 
	                           self.rt.name)

    if(self.rt.update_withLandmark(data, srcname)):
         # Send Update Info to Neighbors                          
         upedxml = self.rt.getxml_withLandmark()

         for n in self.neighbors.values():
             n.Out(TUPLE_ID_ROUTING, self.pack(upedxml, 
                         ROUTING_COMMAND_UPDATE_TABLE))
\end{verbatim}
%}
\end{itembox}
\end{center}
%\begin{verbatim}

%\end{verbatim}
RoutingTableUpdateメソッドにおいてはルーティング情報を表すXMLを受け取り、
それに記された送信元ノードの情報を取得する。
また、自ノードが新しくLandmarkになる条件を満たしていた場合は
自身のLandmarkテーブルに自ノードを追加した後、update\_withLandmarkメソッドで
ルーティングテーブルの更新処理を行う。
それから更新された情報を元に新しいXMLファイルを生成し、近傍ノードへ対して送信する。

\newpage
\begin{center}
\begin{itembox}[l]{update\_withLandmarkメソッド}
%{\scriptsize
\begin{verbatim}
def update_withLandmark(self, xmldoc, src_ts):
    rt = xml.dom.minidom.parseString(xmldoc).childNodes[0]
    tslist = rt.childNodes
    updateflag = False

    tmplist = []
    tmplandmarklist = []

    for t in tslist:
        # append tuplespace  
        if t.nodeType == t.ELEMENT_NODE 
        and t.localName == 'ts':
            tsattr  = t.attributes
            tsid    = tsattr['tsid'].nodeValue
            hopnum  = int( tsattr['hopnum'].nodeValue )
            ttl     = int( tsattr['ttl'].nodeValue )
            nexthop = src_ts

            tmplist.append(tsid)
            if (((not self.tslist.has_key(tsid)) 
                  or (self.tslist[tsid].hopnum > hopnum+1))
                  and (ttl-1 > 0)):
                    self.register(tsid, hopnum+1, ttl-1, 
                                                 nexthop)
                    updateflag = True    

        #parse landmark tsid/dst for register
        elif t.nodeType == t.ELEMENT_NODE 
        and t.localName == 'landmark':
            lkattr = t.attributes
            landmark_tsid = lkattr['tsid'].nodeValue
            landmark_dst  = lkattr['dst'].nodeValue

            tmplandmarklist.append(landmark_tsid)

            if (
            not self.landmark_tslist.has_key(landmark_tsid)):
                self.landmark_register(landmark_tsid, src_ts)
                updateflag = True
            ..................
\end{verbatim}
%}
\end{itembox}
\end{center}

\begin{center}
\begin{itembox}[l]{update\_withLandmarkメソッド---続き}
%{\scriptsize
\begin{verbatim}

    # delete tuplespace                                                             
    for t in self.tslist.values():
        if (( not t.tsid in tmplist ) and (t.ttl-1 > 0)):
            updateflag = True
            if (t.nexthop == src_ts):
                del self.tslist[t.tsid]

    for lt in self.landmark_tslist.values():
        if ( not lt.landmark_tsid in tmplandmarklist ):
            updateflag = True

    return updateflag

\end{verbatim}
%}
\end{itembox}
\end{center}

update\_withLandmarkメソッドにおいては、受け取ったXMLファイルと送信元ノードの情報を引数として受け取り、XMLファイルを読み込んでルーティングテーブルの更新を行い、ローカルネットワークとLandmarkのルーティング情報を登録する。

ローカルエリアネットワークの更新は受け取ったテーブルと自身のテーブルの統合を行う。
統合は、受け取ったテーブルにおいて
%\begin{enumerate}
%\item ローカルエリアのホップ数上限に満たない　　(ttlによる)
%\item 知らない宛先かまたは
%\item 既知の宛先だが、ホップ数が小さい
%\end{enumerate}

\begin{description}
\item[(1)] ローカルエリアのホップ数上限に満たない(ttlによる)
\item[(2)]知らない宛先か、または既知の宛先だがホップ数が小さい
%\item[   ]既知の宛先だが、ホップ数が小さい
\end{description}
場合のみ、自身のテーブルに統合する。ホップ数は登録するときに 1増やし、
TTL(Time To Live)を1減らす。


Landmarkに関する情報の更新は、現在のLandmarkテーブルに存在しないLandmark情報がある場合
に、そのLandmarkのアドレスと転送先アドレスとして、引数で与えられた送信元アドレスを登録
する。


これらの一連の処理により、ルーティングテーブルの構築、及び更新処理が完了する。




\newpage

\section{ルーティングテーブル構築時間の測定}
ここで、Distance Vector型のルーティングテーブルを構築する方法[3]と今回実装した
コンパクトルーティングを行う方法のルーティングテーブルの構築時間をそれぞれ
10,20,30のノードでトポロジはライン型トポロジとバイナリツリー型トポロジを用いて測定した。
格子状のメッシュ型トポロジに対しても同様に測定を行ったが、トポロジ依存によるパケットの
ビジールーブが解決できず、正確に測定が出来なかったためここには記載しない。
またこの場合、コンパクトルーティングを行う際のローカルネットワークのホップカウントは
2と固定して測定を行う。

\subsection{測定の流れ}
ルーティングテーブルについては、Link Configurationからの他タプルスペース
への接続要求を受け取ってから、ルーティングテーブルが最短経路を構築するま
での時間を各ノードで計り、その平均を出した。
\\ \\
以下の順序で実験を行う
\begin{enumerate}
\item LindaサーバーとProtocol Engineを全ノードで起動しておく。
\item LinkConfigure.pyでXMLを作成、初期ノードへXMLを投入する(測定開始)。
\item 収束を確認して、結果を集計
\end{enumerate}
Distance Vector型ルーティングは最短パスを構築するので、全ノードで各ホップ数が最短
になったら収束したと判断した。

\subsection{測定結果}
以下にLine型トポロジとBinary Tree型トポロジのルーティングテーブルを構築したときの
構築時間の結果を載せる(図\ref{routingtable})、(表\ref{routingtime})。

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

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

\begin{table}[htbp]                                                                        
 \begin{center}      
 \caption{Routing Table 構築にかかる時間}    
 \label{routingtime}                                                  
  \begin{tabular}{|c|c|c|} 
   \hline \hline
   \multicolumn{3}{|c|}{Compact Routing} \\
   \hline
   トポロジ & ノード数 & かかった時間(sec)\\ 
   \hline
   Line  & 10 & 1.19 \\
   \hline
   Tree  & 10 & 2.40 \\
   \hline
   Line  & 20 & 5.18 \\
   \hline
   Tree  & 20 & 6.95 \\
   \hline
   Line  & 30 & 7.56 \\
   \hline
   Tree  & 30 & 26.26 \\
   \hline \hline
   \multicolumn{3}{|c|}{Distance Vector Routing} \\
   \hline
   トポロジ & ノード数 & かかった時間(sec)\\ 
   \hline
   Line  & 10 & 2.66 \\
   \hline
   Tree  & 10 & 4.54 \\
   \hline
   Line  & 20 & 89.66 \\
   \hline
   Tree  & 20 & 29.91 \\
   \hline
   Line  & 30 & 8634.50 \\
   \hline
   Tree  & 30 & 127.55 \\
   \hline   
  \end{tabular}
 \end{center}
\end{table}



これらの結果より、コンパクトルーティングでのルーティングテーブル構築時間は
Distance Vector型でのルーティングテーブル構築時間より高速に構築可能であり、
ノード数に対しての増加比もDistance Vector型よりもスケーラビリティに優れているという事
がわかる。

\newpage
\section{考察}
本章ではFedarated Lindaによる分散アルゴリズムの実装として、コンパクトルーティングを用いた実装
を行った。

Distance Vector型ルーティングを行う時、ルーティングテーブルが構築されるまでにかかる
時間は、ノード数に対して２乗オーダ的に増加する。
これは、ルーティングテーブルの更新情報をノードが受け取ると、自身のルーティングテーブル
を更新し、接続している他のノードへ更新情報を配信するため、メッセージ数が２乗オーダに
増える為だと考えられる。
対して、コンパクトルーティングを行う実装では、持つべきテーブルはローカルネットワークと全
Landmarkの情報となるので、Landmarkの数が少ない、即ちローカルネットワークの大きさが大きけ
れば大きいほどテーブルサイズは小さくなる。
またネットワーク全体を伝搬するLandmarkのルーティング情報もDistance Vector型のルーティン
グ情報と違い、転送先とアドレスの２つしか持たないので、
総じてDistance Vector型よりルーティングテーブルの構築にかかる時間において
スケーラビリティに優れるという結果になった。

また、Protocol Engineの実装についてはPythonを用いた差分を拡張するプログラミングスタイルを
紹介し、実際のルーティングテーブルの構築、更新処理についても説明した。

しかし、この例を実装するにあたって現実装での問題点も明らかとなった。
それは、テスト駆動開発で分散プログラミングを行うのには開発環境の整備も重要な要素
であることを、今回の実装を通して知ったからである。
現在のFederated LindaはLindaサーバー、Protocol Engineスクリプトをそれぞれ単独で起動し、
多ターミナルでのテスト駆動開発によって開発を行っているが、
実際に開発を行ってみて気がつく開発のやりにくさやデバッグ環境の不備があった。

具体的例として、格子状のメッシュ型トポロジにおけるFederated Lindaの実装に原因特定不可能な
パケットのビジーループが見られた。現在のような多ターミナルによるテスト駆動開発では
このような問題を特定するのに十分なデバッグ情報を得る事ができず、また一回の駆動実験
にかかる起動コストも、よりテストを煩雑な物と化している。


よって、Federated Lindaを分散プログラム開発の為の環境として生かすには、
Lindaサーバー(すなわちタプル空間)への
より実践向きな機能拡張や分散環境下でのデバッグ機能が不可欠であると考える。