%これはちょっとマジで書きかけたものです．
%気にしないで，使ってください．
%minru

\documentclass[twocolumn, a4j, twoside]{jarticle}
\usepackage{master_proc}
%\usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}

% dvipdfm を使って PDF ファイルに日本語の栞をつける
% \usepackage[dvipdfm]{color}
% \usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,%
% bookmarkstype=toc]{hyperref}

\jtitle{分散プログラミングモデル Federated Linda と 分散デバッグ}		%和文タイトル
\etitle{Distributed Programming Model : Federated Linda and Distributed debugging}%英文タイトル
\author{渕田 良彦}	%著者名
\studentid{068514D}	%学籍番号
\teacher{河野 真治}	%指導教官

\begin{document}
  \maketitle
  \section{はじめに}
並列・分散環境におけるプログラミングは、今後ますますその重要性が高まっていくと考えられる。
しかし、分散プログラム開発において、スケーラビリティを確保することは難しい。 
スケーラビリティとは、参加ノードの数が小規模から大規模に変化しても性能が劣化しない
という性能基準のことを示す。
%スケーラビリティ等を確保したまま、分散プログラムを正しく記述することやデバッグ 
%を行う為に、これまで多くの分散プログラミングモデルが開発されてきたが、それらは 
%遂次プログラミングモデルの延長であったり、アプリケーション開発者が複雑で理解しにくい
%記述を熟知しなければならなかった。
そこで本研究室では、自然にスケールする分散プログラミン 
グモデルを提供することを目的として Federated Linda を開発した。
Federated Lindaは実験的に分散アルゴリズムを実装し、そのスケーラビリティを測る
ことができる分散プログラミングモデルである。

本研究では、本研究室で開発した分散プログラミングモデル Federated Linda を用いた 
分散アルゴリズムの記述事例として、Compact Routing の実装を行い、 
その開発によって得られた知見から本モデルに必要な機能の拡張を提案する。 
本モデルへの機能拡張としてまず最初の段階で、Federated Linda の実装をC言語から
Java言語へと移行した。その上で、分散デバッグ機能について検討を行い、
実際に分散デバッグ機能を実装する。
実装した分散デバッグ機能の評価として、Federated Linda での
分散アルゴリズムにおけるバグの特定を行い、その有用性を示す。
\section{Federated Linda}
Federated Lindaは本研究室で開発された非同期型Lindaで構築される。
非同期型Lindaは、タプルというデータ単位をネットワーク上の「タプル空間」に
出し入れする事で通信を行うLindaという通信モデルを用い、その通信を、明確な
待ちを行わない非同期的な通信によって行う。しかし、集中型の通信を行う
非同期型Lindaはスケーラビリティをもたない。そこで、複数のタプル空間を接続し、
ノード間にてタプルを中継させる分散モデルとしてFederated Lindaを提案する。
これによって、通信の集中型モデルから脱し、スケーラビリティを得る。
また、分散プログラムにおける構成要素を、３つに分離することで、各要素毎に
切り替えが可能となり、ポータビリティが向上する。

３つに分離されるFederated Lindaの構成要素には以下の３つがある。
{\small
\begin{verbatim}
Local Access Protocol
・'in','read','out'といったLindaのAPI、ユーザープログラ
　ムからの通信、プロトコルへのアクセス
Protocol Engine
・分散アルゴリズムを内包するエージェントプログラム、タプル
　空間から別ノードのタプル空間へとタプルを転送する
Link Configuration
・タプル空間やProtocol Engineの接続をXMLで表し、そのXML
に沿ったコネクション確立処理を行う
\end{verbatim}
}
Federated Lindaでは、玩具的に分散アルゴリズムを実装し、実験する事が可能であり、
その教育的な利用も考えられる。

\section{Compact Routingの実装と評価}
Federated Lindaにおける分散アルゴリズム、つまりProtocol Engineの実装として
Distance Vector Routingの実装が先行研究[1]によって行われた。これは、自ノードから
宛先ノードまで、距離が最短のルーティングを行う分散アルゴリズムであるが、ネットワーク
が複雑になるほど経路の情報量が増え、スケーラビリティに劣ると考えられた。よって
今回、階層型ルーティングを用いた、ルーティングテーブル収束速度や、ネットワーク
のスケーラビリティに対して優位な分散アルゴリズムである'Compact Routing'[3]の実装を
行った。

評価としてDistance Vector RoutingとCompact Routingそれぞれにおけるルーティングテーブル構築
時間の比較を行い、表\ref{routingtime}に示す結果となった。
\vspace{-7mm}
\begin{table}[htbp]
 \begin{center}
 \caption{ルーティングテーブル構築にかかる時間}
 \label{routingtime}
{\small
  \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}
\vspace{-8mm}

比較の結果、Distance Vector Routingではルーティングテーブル構築時間が、ノード
数の増加に対して大幅に増加する結果となったのに対し、Compact Routingでは、
階層型ルーティングを用い、ノード数の増加に対するルーティングテーブルのサイズや、
更新量を抑えることによってルーティングテーブルの構築時間が短くなる事を確認できた。
以上の結果より、Compact RoutingはDistance Vector Routingよりもスケーラビリティに
優れる分散アルゴリズムであると言える。
\vspace{-6mm}
\subsection{問題点}
今回の評価実験において、Distance Vector RoutingとCompact Routingの両実装を
格子状のメッシュ型トポロジにおいて用いた所、何らかのバグが原因と考えられる
問題点が明らかとなった。しかし、当時のFederated Lindaにおける開発環境が、多数の
ターミナルによって全プロセスを起動するテスト駆動開発であり、それらに対して逐次的
デバッグを行うことではバグ要因を特定する事は困難であった。

よって、Federated Lindaの機能を拡張し、分散プログラム開発に適した'分散デバッグ機能'を
実装することを提案し、その機能の検討と実装を行った。


\section{Java言語への移行と分散デバッグ機能の実装}
\subsection{Java言語への移行}
Federated Lindaへ分散デバッグ機能を実装する為に、これまでのC言語によるLindaサーバーや
Linda APIの実装を、Java言語での実装へ移行した。そのことにおける利点を以下に示す。
{\small
\begin{verbatim}
1. Java言語への移行において設計や仕様の見直しを行い、機能拡
   張を行いやすい実装とする
2. オブジェクト指向、自動化されたリファクタリングを用いること
   による開発の効率化
3. マルチプラットホームへの対応
4. デュアルスタック化によるIPv4/IPv6の同時接続に対応
\end{verbatim}
}
%\vspace{-3mm}
\subsection{分散デバッグ機能の検討}
分散環境におけるプログラムのデバッグでは、多くの場合、逐次デバッガ(gdb等)を用いた
二分法でデバッグ可能である。しかし、通信の状態が全体に依存する場合では、単体のデバッグ
では全体の正しさをデバッグできないという状況が存在する。その状況を示した図を以下に示す。
\vspace{-2mm}
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=5.5cm]{fig/nonseqdeb.pdf}
\vspace{-5mm}
\caption{逐次デバッグが困難な通信の例}
\label{nonseqdeb}
\end{center}
\end{figure}
\vspace{-8mm}

図\ref{nonseqdeb}に示す様に、通信が全体に影響し、その順序に任意性が存在する場合
（分散プログラムの非決定性）、逐次型デバッガによるデバッグを用いることは出来ない。
よって、全体の通信を止めずにデバッグが行える仕組みが必要であると考える。

\subsection{通信状態のデバッグ機能}
Federated Lindaの分散デバッグ機能として、Java版Lindaサーバーの機能を拡張し、
通信状態のデバッグを、全体の通信を止める事無く行う機能を実装した。
この機能は以下の２点からなる。
\vspace{-3mm}
{\small
\begin{verbatim}
1. Federated Lindaにおける全体の通信を止める事無く、通信状
   態のログを取得する機能
2. 取得したログを用いて通信状態を視覚的に表示し、ステップ実行
   によって通信の状態を確認できるモニターツール
\end{verbatim}
}
\vspace{-3mm}

\section{評価}
実装した分散デバッグ機能の評価として、以前デバッグが困難であった、格子状メッシュ型トポロジ
におけるルーティングアルゴリズムのデバッグを行った。用いた実験は以下の２つである。
\vspace{-3mm}
{\small
\begin{verbatim}
・6ノードの格子状メッシュ型トポロジにおけるDistance Vector 
  Routingのルーティングテーブル構築 
・6ノードの格子状メッシュ型トポロジにおけるCompact Routing 
  のルーティングテーブル構築
\end{verbatim}
}
\vspace{-3mm}
上記２点のFederated Lindaにおけるルーティングテーブル構築を行い、
その通信状態のログを取得した。その取得したログに対して、モニターツールを
用いた通信状態の確認よるデバッグを行い、バグ要因の特定を行う。その様子を
図\ref{exec1},図\ref{exec2}に示す。

\begin{figure}[htbp]
\begin{tabular}{cc}
\begin{minipage}{0.5\hsize}
\begin{center}
\includegraphics[width=4.25cm]{fig/debug1.pdf}
\vspace{-5mm}
\caption{トポロジ及び通信イベントの表示}
\label{exec1}
\end{center}
\end{minipage}
\begin{minipage}{0.5\hsize}
\begin{center}
\includegraphics[width=4.25cm]{fig/debug2.pdf}
\vspace{-5mm}
\caption{実行シーケンスでの転送タプル内容を表示}
\label{exec2}
\end{center}
\end{minipage}
\end{tabular}
\end{figure}

\subsection{バグ要因の発見}
通信状態ログのモニターツールを用いてデバッグを行った結果、Link Configuratetionが
正常終了していない為に、ルーティングテーブル構築時の通信量が増えているというバグ要因を特定した。

\newpage
このバグは、Distance Vector RoutingとCompact Routingの両実装に見られ、格子状のメッシュ型トポロジに
おける問題の原因となっていた。図\ref{bug}にその状況を示す。

\vspace{-2mm}
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=8.5cm]{fig/bug.pdf}
\vspace{-5mm}
\caption{別経路からのLink Configuration}
\label{bug}
\end{center}
\end{figure}
\vspace{-8mm}

以上のことより、以前のFederated Linda における開発環境ではデバッグが困難な状況を、
通信状態のデバッグ機能を実装することによって解消したと評価する。

\section{他の分散プログラミングモデルとの比較}
Federated Lindaと他の分散プログラミングモデルとの比較を、Overlay Weaver, StarBEDを対象に行う、
以下にその結果を示す。
\vspace{-2mm}
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=9cm]{fig/table.pdf}
\vspace{-5mm}
\caption{他の分散プログラミングモデルとの比較}
\label{table}
\end{center}
\end{figure}
\vspace{-8mm}

\section{まとめと今後の課題}
本研究では、自然にスケールする分散プログラミングモデルを実現する為、 
実験的に分散アルゴリズムを実装し、スケーラビリティを測ること 
ができる分散モデルとしてFederated Lindaを提案した。
Federated Lindaにおける分散アルゴリズムの実装としてCompat Routingを実装し、評価した。 
また、その実装の経験から必要と分かった分散デバッグ機能について検討し、実装と評価を行った。 
本研究における今後の課題としては、スナップショットを用いた分散デバッグ機能の実装が挙げられる

{\small
\begin{thebibliography}{9}
 \bibitem{dinamicrouting}安村 恭一, 河野 真治,
動的ルーティングによりタプル配信を行なう分散タプルスペース Federated  Linda, 
日本ソフトウェア科学会第22回大会, 2005.

\bibitem{dinamicrouting_compact}渕田 良彦, 河野 真治, 
連邦型タプルスペースを使ったコンパクトルーティングの実験, 
情報処理学会プログラミング研究会, 2007.

\bibitem{compactrouting}L. J . Cowen,
Compact Routing with Minimum Stretch, Proc. SODA’99, pp.255-260 (1999).

\end{thebibliography}
}

\end{document}