\documentclass[techrep, ,dvipdfmx]{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage[dvipdfmx]{color}
\usepackage{url}
\usepackage{listings}
\lstset{%
  language={C++},%使用言語
  basicstyle={\small},%書体
  commentstyle={\small\itshape},%コメントの書体
  keywordstyle={\small\bfseries},%キーワードの書体
  %identifierstyle={\small},%
  %ndkeywordstyle={\small},%
  stringstyle={\small},%文字列の書体
  frame={trlb},%外枠
  breaklines=true,%改行
  columns=[l]{fullflexible},%
  xrightmargin=0zw,%
  xleftmargin=3zw,%
  %numbers=none,%行番号の表示
  %numberstyle={\scriptsize},%行番号の書体
  %numbersep=1zw,%
  %stepnumber=1,
  lineskip=-0.5ex,%
  captionpos=b,%キャプションの位置
  moredelim=**[s][\color{red}]{\"compressed}{\"},
}
\renewcommand{\lstlistingname}{Code}
\input{dummy.tex} %% Font 

% ユーザが定義したマクロなど．
\makeatletter

\begin{document}

% 和文表題
\title{分散システム向けのTopology Managerの改良}
% 英文表題
\etitle{Improvement of Topology Manager for distributed system}

% 所属ラベルの定義
\affilabel{1}{琉球大学理工学研究科情報工学専攻\\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
\affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}

% 和文著者名
\author{
  照屋 のぞみ\affiref{1}\and
  河野 真治\affiref{2}
}

% 英文著者名
\eauthor{
  Nozomi TERUYA\affiref{1}\and
  Shinji KONO\affiref{2}
}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{照屋 のぞみ\\
        〒903-0213 沖縄県西原町千原1番地\\
	琉球大学工学部情報工学科\\
        TEL: (098)895-2221\qquad FAX: (098)895-8727\\
        email: kokubo@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
Aliceでは、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現するために、ComputationとMetaComputationによる階層化を採用している。
分散環境の構築等の複雑な処理をAliceがMeta Computationとして提供することで、仕様変更を抑え、変更前の信頼性を保ったまま拡張可能にする。
本研究では、分散トポロジー管理のMeta ComputationであるTopology ManagerにNAT越えを実現するための設計を行う。
そしてその設計がAliceアプリケーション同士の接続も可能にすることを示す。
\end{abstract}

% 英文概要　仮
\begin{eabstract}
\end{eabstract}

% 表題などの出力
\maketitle

% 本文はここから始まる

\section{分散アプリのTopology Manager}
当研究室ではデータをData Segment、タスクをCode Segmentという単位で記述する分散フレームワークAlice\cite{Alice}の開発を行っている。
Aliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
ここで言う信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。

Aliceでは、処理をComputationとMeta Computationに階層化し、コアな仕様と複雑な例外処理に分離する。
そして分散環境の構築に必要な処理をMeta Computationとして提供する。
プログラマはコアな仕様の変更を抑えつつプログラムの挙動変更ができるため、信頼性の高い分散アプリケーションの記述が可能となる。

分散アプリケーションでは複数のノードを管理する必要がある。
接続する分散アプリケーションを見つけ、それらを接続し合ってトポロジーを構成する。
その際にはNATなどネットワークの問題を考慮しなければならない。
そして、ノードの障害発生時にはトポロジーの再構成などの対応を用意しなければならない。
また、別々の分散アプリケーション同士を接続・連携させる拡張をしたい場合もある。
このように分散アプリケーションにおいてノードのトポロジー管理は重要である。
しかし、プログラマがそれを全て記述するのは困難である。

AliceのMeta ComputationのひとつであるTopology Managerは、アプリケーション外部からトポロジーの構成・管理をサポートする。
本研究では、分散アプリケーションにおける課題であるNAT越えなどの機能をTopologyManagerで実現するための設計を行う。
同時にAliceVNCやAliceChatといったAlice上でのアプリケーションを連携するための設計を行うことで、
相互干渉なく容易にアプリケーションの接続・拡張ができる環境の提供を目指す。
今までは１つの分散アプリケーションに対して１つのTopology Managerを用いていたが、
Topology Managerを複数用意しそれぞれにLAN内とWAN内のトポロジーを管理させることで、NAT越えや別の分散アプリケーションの連携が容易にできることが期待される。

%ToDo:Topologymanagerが必要な理由
%分散アプリケーションは複数のノードを管理しないといけない。
%　　１．分散アプリを見つける
%    ２．ノードをトポロジーに接続する（物理ネットワークとの対応：NATの対応）
%    ３．故障など問題発生時の再構成
%    4.複数アプリのセパレーション・インタラクション
%    LAN内を構成するTopMとWANをGTopMが対応することで解決
%    直接の応用がTreeVNC（いままではこう）。
%    いままではTopMだけだったがGTopMを追加する

\section{分散フレームワーク Alice の概要}
\subsection*{[Data SegmentとCode Segment]}
AliceではCode Segment（以下CS）とData Segment（以下DS）の依存関係を記述することでプログラミングを行う。
CSは実行に必要なDSが全て揃うと実行される。CSを実行するために必要な入力されるDSのことをInputDS、CSが計算を行った後に出力されるDSのことをOutput DSと呼ぶ。
データの依存関係にないCSは並列実行が可能である（図 \ref{fig:CS} ）。
CSの実行においてDSが他のCSから変更を受けることはない。そのためAliceではデータが他から変更され整合性がとれなくなることはない。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=60mm]{images/dsandcs2.pdf}
    \end{center}
    \caption{CodeSegmentの依存関係 }
    \label{fig:CS}
\end{figure}

AliceはJavaで実装されており、DSはJava Objectに相当する。プログラマがCSを記述する際は、CodeSegmentクラスを継承する。


\subsection*{[Data Segment Manager]}
DSは数値や文字列などの基本的なデータの集まりを指し、Aliceが内部にもつデータベースによって管理されている。このデータベースをAliceではDS Manager(以下DSM)と呼ぶ。
CSは複数のDSMを持っている。DS Managerには対になるString型のkeyが存在し、それぞれのManagerにkeyを指定してDSにアクセスする。
DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。
Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する（図 \ref{fig:Remote DSM} ）。
他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い。

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=60mm]{images/remote_datasegment.pdf}
    \end{center}
    \caption{Remote DSMは他のノードのLocal DSMのproxy }
    \label{fig:Remote DSM}
\end{figure}

\subsection*{[ComputationとMeta Computation]}
Aliceでは、計算の本質的な処理をComputation、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
AliceのComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。
それに対して、AliceのMeta Computation は、Remoteノードとの通信時のトポロジーの構成やデータの表現形式の選択の処理と言える。
つまりこれらの処理はAliceのComputationを支えているComputationとみなすことができる。

Aliceの機能を追加するということはプログラマ側が記述するComputationを支えるためのMeta Computationを追加することと言い換えられる。
AliceではMeta Computationとして分散環境の構築等の機能を提供するため、プログラマはCSを記述する際にトポロジー構成や切断、再接続という状況を予め想定した処理にする必要はない。
プログラマは目的の処理だけ記述し、切断や再接続が起こった場合の処理をMeta Computationとして指定する。
このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。

\subsection*{[Topology Manager]}

Aliceでは、ノード間の接続管理やトポロジーの構成管理を、Topology ManagerというMeta Computationが提供している。
このTopology ManagerもCS/DSを用いて実装されている。



\textbf{静的トポロジー}

プログラマはトポロジーファイルを用意し、Topology Managerに読み込ませるだけでトポロジーを構成することができる。
トポロジーファイルはDOT Language\cite{dot}という言語で記述される。
DOT Languageとは、プレーンテキストを用いてデータ構造としてのグラフを表現するためのデータ記述言語の一つである。
ソースコード\ref{src:topologyfile}は3台のノードでリングトポロジーを組むときのトポロジーファイルの例である。

\begin{table}[html]
    \lstinputlisting[label=src:topologyfile, caption=トポロジーファイルの例]{source/TopologyFile.dot}
\end{table}

また、DOT Languageファイルはdotコマンドを用いてグラフの画像ファイルを生成することができる。そのため、記述したトポロジーが正しいか可視化することが可能である。

Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント（以下、Topology Node）に接続するべきクライアントのIPアドレスやポート番号、接続名を送る（図\ref{fig:topologymanager}）。

\begin{figure}[h]
\begin{center}
\includegraphics[width=40mm]{images/topologymanager.pdf}
\end{center}
\caption{Topology Managerが記述に従いトポロジーを構成}
\label{fig:topologymanager}
\end{figure}

トポロジーファイルでlavelとして指定した名前はRemote DSMの名前としてTopology Nodeに渡される。
そのため、Topology NodeはTopology ManagerのIPアドレスさえ知っていれば自分の接続すべきノードのデータを受け取り、ノード間での正しい接続を実現できる。



\textbf{動的トポロジー}

実際の分散アプリケーションでは参加するノードの数が予め決まっているとは限らない。
そのためTopology Managerは動的トポロジーにも対応している。
トポロジーの種類を選択してTopology Managerを立ち上げれば、あとは新しいTopology Nodeが参加表明するたびに、
Topology ManagerからTopology Nodeに対して接続すべきTopology Nodeの情報が渡され接続処理が順次行われる。
そしてTopology Managerが持つトポロジー情報が更新される。
現在Topology Managerでは動的なトポロジータイプとしてBinary Tree とStarに対応している。



\textbf{障害発生時の対応}

ノード間接続が切れた場合、次の通信が行われるまで切断を発見することができない。また、接続状態ではあるが応答に時間がかかる場合もある。
これらの問題を検知するために、KeepAliveという定期的にheart beatを送信しノードの生存確認を行うMeta Computationが用意されている。
一定時間内にノードからの応答がない場合、そのノードのRemote DSMが切断され、再接続すべきノード情報を要求する。

また、各ノードに切断・再接続時に対する処理を特別に用意したい場合がある。
そのために、切断・再接続を検知した際に任意のCSを実行できるMeta Computationもある。
プログラマは切断の際に実行したいCSを書き、Meta Computationに指定しておくだけで良い。

これらのMeta ComputationはTopology Managerにも含まれているため、
Topology Managerを用いることで構成したノード間の接続が途切れてもトポロジーを再構成することができる。


\section{TreeVNCのNAT越え}
TreeVNCとは、当研究室で開発を行っている授業向け画面共有システムである\cite{TreeVNC}。
オープンソースのVNCであるTightVNC \cite{tightVNC} をもとに作られている。
授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう。
この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図 \ref{fig:TreeVNC})。

\begin{figure}[h]
\begin{center}
\includegraphics[width=50mm]{images/treestructure.pdf}
\end{center}
\caption{TreeVNC の構造}
\label{fig:TreeVNC}
\end{figure}

TreeVNCは授業向けのシステムであるため、プライベートネットワーク内のみでの使用を前提に作られている。
しかし学外から授業に参加したい場合、教室にカメラを設置するだけではスクリーンに写した教員のPC画面までは見ることは困難であるため、
学外のノードからでも画面配信のTreeに入りたい要求が生まれた。
つまり、NATを越えた通信に対応する必要がある。
そのために、TreeVNCでは画面配信側ネットワークがグローバルIPアドレスを持っていることを前提とし、
別ネットワーク上のノードが画面配信側ルートノードのIPアドレスを指定して直下の子になるDirect Connectionを実装した(図 \ref{fig:DirectConnection})。

\begin{figure}[h]
\begin{center}
\includegraphics[width=70mm]{images/directConnection.pdf}
\end{center}
\caption{TreeVNC のDirect Connection}
\label{fig:DirectConnection}
\end{figure}

しかし、この方法だと複数の別ネットワークからの接続があった場合、ルートノードに大量に子が接続されてしまうためルートノードに接続台数分の負荷がかかってしまう。

また、別ネットワーク側のノードが途中で画面を配信したい場合（Server Change Request）がある。
TreeVNCではソケットの反転が考案されたが、ソースコードが膨大で拡張した場合どこに影響するかわからないほど複雜であったため、実装までに至らなかった。

さらに、どちらのノードもプライベートネットワークであった場合、TreeVNCではNAT越えのための中間サーバをプログラマが作らなければならない。

このように、NAT越えは分散アプリケーション構築における課題の1つでもあるが、その実装は容易ではない。
AliceのTopology ManagerにもNAT越えをサポートする機能が必要であると考えた。


\section{AliceVNCとAliceChatの接続}
Aliceが実用的なアプリケーションを実装するのに充分な性能があるかをテストする例題として、Alice上にTreeVNCとStarトポロジーのChatが実装された。
それぞれをAliceVNC、AliceChatと呼ぶ。
これらは全く別のアプリケーションであるが、お互いに接続させたい要求がでてきた。
例えば、AliceChat上にAliceVNCの画面のスナップショットを載せたい場合や、AliceVNC上にAliceChatの内容をコメントとして画面に流したい場合である。

このように別トポロジーのアプリケーション間で相互干渉なく接続するための機能が必要であると考えた。


\section{Topology Managerの拡張設計}
\subsection*{[別トポロジー間での接続]}
AliceVNCとAliceChatのように同一ネットワーク内での別アプリケーションの接続を実現する仕組みが図 \ref{fig:private} である。

\begin{figure}[h]
\begin{center}
\includegraphics[width=70mm]{images/private2.pdf}
\end{center}
\caption{プライベートネットワーク内での接続}
\label{fig:private}
\end{figure}

\begin{enumerate}
    \item {\ttfamily  接続を要求する側のいずれかのNodeが接続先Topology Manager(A)のIPアドレスを自身を管理するTopology Manager(B)のDSMに保存}
    \item {\ttfamily Topology Manager(B)はRootNode(B)にTopology Manager(A)への接続をするよう要求}
    \item {\ttfamily RootNode(B)がTopology Manager(A)と接続し、自身の接続先ノードの情報を取得}
    \item {\ttfamily 取得した情報をもとにRootNode(A)に接続}
\end{enumerate}

これでAliceChat側にAliceVNCのスナップショット情報を送ることができる。

また、(1)の手順を踏むことでAliceChatのトポロジーの再構成時にAliceVNCへ再接続も自動で行うことができる。
TopologyManagerはNode間の接続が切れるとトポロジーを再構成するため、RootNode(B)が落ちると、それを検知したTopology Manager(B)が他のノードをRootNodeとして配置し接続をやり直す。
どのノードが落ちてもTopology Manager(B)が接続先Topology Manager(A)の情報を保持したままなので、再び(2)以降の手順でAliceVNCの接続が行われる。

今までのAliceでは、ノードに対してTopology Managerは１つと決められていた。
Topology Managerと各ノードのやり取りをするのは、ノードごとに実行されるTopology NodeというMeta Computationである。
Topology Managerは接続されたnodeの情報（nodeNameとIPアドレスのHashMap）を"nodeTable"というKeyに対応するDSとして保存している。
そしてTopology NodeはTopology Managerから割り当てられたnodeNameを"hostname"というKeyに保存する。
つまり、接続するTopology Managerが増えればTopoloyNodeに割り当てられるnodeNameも増えるため、今までのように"hostname"という1つのKeyだけでは対応できない。
TopologyNodeが複数のTopologyManagerに対応できるようにしなければならない。

そこで、Meta Computationとして、通常のLocal DSMとは別にTopology ManagerごとのLocal DSMを立ち上げる方法が考えられる(図 \ref{fig:hostname})。

\begin{figure}[h]
\begin{center}
\includegraphics[width=60mm]{images/somehostname2.pdf}
\end{center}
\caption{Topology Nodeは複数のnodeNameを持つ}
\label{fig:hostname}
\end{figure}

\newpage

それぞれのTopology Managerに対応するDSMを作り、そこにそれぞれのnodeNameを格納することで、
DSMを切り替えるだけでTopologyNodeの仕様は変えずに複数のTopology Managerに対応できる。

しかし、現在のAliceのコードではDSMを管理するclassがstatic classであったため、複数のLocal DSMを持つことができない。
staticを取り除くためにはAliceの大部分のコードを修正する必要がある。
そのため、現状ではKeyである"hostname"のあとにTopology Managerごとの番号を付け加えることで、KeyによってTopology Managerごとの対応を分けている。
Aliceの再設計を行う際にはstatic classのない実装を行い、DSM切り替えによる方式を実現したい。


\subsection*{[別ネットワーク間での接続]}
TreeVNCでお互いにプライベートネットワークのノードの接続をするには、NAT越えのための中継プログラムをプログラマが書かなければならなかった。
しかし、Aliceではトポロジー管理をアプリケーションから分離しているため、グローバルIPアドレスを持ったTopology Manager(以下、Global Topology Manager)を立てるだけで良い。
プライベートネットワークのTopology Manager（以下、Private Topology Manager）はプライベートネットワーク内で木を構成し、
Global Topology Managerは各ネットワークのRootNodeで木を構成する。つまり、3次元的な木構造が構成される。
そのため、複数のTopology Managerを立ち上げるだけで、Topology Manager自体の「参加表明のあったノードを木構造」に接続するという仕様に変更はない。

NAT越えはTopology Managerの「参加表明したノードでトポロジーを構成する」Computationを支えるComputation、つまりMeta Meta Computationと言える。
NAT越えのため以下の機能をTopology Manager/NodeのMeta Meta Computationとして取り入れる。

\begin{figure}[h]
\begin{center}
\includegraphics[width=70mm]{images/globalconnect.pdf}
\end{center}
\caption{NATを越えた接続}
\label{fig:global}
\end{figure}

\begin{enumerate}
    \setcounter{enumi}{-1}
    \item {\ttfamily 接続を受け入れる側(Network1)のルートノードがグローバルIPアドレスを持ったGlobal Topology Managerを立ちあげておく}
    \item {\ttfamily 接続を要求する側(Network2)のいずれかのNodeがGlobal Topology ManagerのIPアドレスを自身を管理するTopology ManagerのDSMに保存}
    \item {\ttfamily Topology ManagerはRootNodeにGlobal Topology Managerへの接続をするよう要求}
    \item {\ttfamily RootNodeがGrobal Topology Managerと接続し、自身のIPアドレスを送る。Global Topology Managerが受け取ったIPアドレスがプライベートアドレスであれば、ノードに対してNATの外側IPアドレス/ポート番号を要求されるので、RootNodeはそれに返答。}
    \item {\ttfamily UDP hole punchingが行われ、Network1のRootNodeとNetwork2のRootNodeが接続される}
    \item {\ttfamily もし接続が確立されなければ、Global Topology Managerがデータ中継用のCSを用意しデータを中継する}
\end{enumerate}

Meta Meta ComputationがNAT越えをサポートするため、Topology ManagerもTopology Nodeも接続要求のあったノードがグローバルかプライベートかを気にせず扱うことができる。

\section{他言語等との比較}
\subsection*{[Erlang]}

並列指向プログラミング言語Erlang\cite{Erlang}は、プロセスと呼ばれるid付きの独立したタスクに対して、データをメッセージでやりとりする。
タスクをプロセスという細かい単位に分割して並列に動かす点や、メモリロックの仕組みを必要としない点はAliceと同様である。

しかしErlangでは分散環境の構築等はプログラマ自身が記述しなければならない。
Aliceでは分散環境の構築はTopology Managerが一括して管理するため、プログラマはトポロジーを指定するだけで良い。

ErlangにはNAT越えをサポートするためのライブラリが存在し\cite{Erlang-NAT}、
NAT機器と通信し外側IPアドレスを取得メソッドや、NATに指定したポート番号でポートマッピングするメソッドが用意されている。

Aliceでは、それらの機能もTopology Nodeの一部に含めることで、NAT越えを意識しなくともTopology Nodeを用いるだけでサポートできるようにする。


\subsection*{[Akka]}

Akka\cite{Akka}はScala・Java向けの並列分散処理フレームワークである。
アクターモデルを採用しており、アクターと呼ばれるアドレスを持ったタスクに、データをメッセージでやりとりする点がErlangと似ている。
Akkaの特徴として、メッセージを送りたいプロセスのアドレスを知っていればアクターがどのマシン上にあるかを意識せずにプログラミングできるという点がある。
逆にAliceはどのRemote DSMに対してやり取りをするかを考慮するが、CSがOutputしたDSを次にどのCSに渡すかを意識する必要がない。
この点はアクターモデルとCS/DSモデルのパラダイムの違いと言える。

また、Akkaのもう一つの特徴として、アクターで親子関係を構成できる点がある。
分散通信部分を子アクターに分離し、親アクターは子アクターのExceptionが発生した時に再起動や終了といった処理を指定できる。
さらにRouterという子アクターへのメッセージの流れを制御するアクターや、Dispatcherというアクターへのスレッドの割当を管理する機能をAkkaが提供している。
このように処理を階層化し複雑な処理をフレームワーク側が提供する仕組みはAliceのMeta Computationと共通している。

AkkaではNATに対応するために、外側IPアドレスとポート番号を指定することができる。
しかしNAT機器へのポートマッピングはプログラマが記述しなければならない。


 \section{まとめ}
並列分散フレームワークAliceでは、スケーラブルかつ信頼性の高いプログラムを記述する環境を実現するため、CS/DSの計算モデルとMeta Computationによる実装の階層化を採用している。
NATを越えたノード間通信及びAlice上のアプリケーション間接続を実現するために、分散トポロジーの構成・管理をするMeta ComputationであるTopology Manager/Nodeの拡張設計を行った。
DSMの切り替えによりTopology Nodeを複数のTopology Managerに対応させ、さらにMeta Meta ComputationとしてNAT越えの機能を追加することで、
Topology Manager/Nodeのコードを大きく変えずに別トポロジー・別ネットワーク間のノードの接続が行われ、自由度の高い通信が可能になると期待される。
しかし、それを実装するにはAliceのDSMを管理するstatic classのstaticを取り除かなければならず、それは容易ではなかった。
今後の課題としては、Aliceそのものの再設計を行った後にこれらの機能を実装し、NATを越えたアプリケーションの接続が実際にできるかをテストする必要がある。
 
\nocite{*}
%\nocite{opencl}
%\nocite{opencl:ref}
%\nocite{opencl:applied}
%\nocite{yutaka:os}
\bibliographystyle{ipsjunsrt}
\bibliography{sigos}
%\bibliography{cerium,book}


\end{document}