% withpage: ページ番号をつける (著者確認用)
% english: 英語原稿用フォーマット
\documentclass[techrep, ,dvipdfmx]{ipsjprosym}
%\documentclass[withpage,english]{ipsjprosym}

\usepackage[dvipdfmx,hiresbb]{graphicx}
\usepackage{listings}
\usepackage{url}
\lstset{%
  language={Java},%使用言語
  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=left,%行番号の表示
  numberstyle={\scriptsize},%行番号の書体
  numbersep=1zw,%
  stepnumber=1,
  lineskip=-0.5ex,%
  captionpos=b,%キャプションの位置
  moredelim=**[s][\color{red}]{\"compressed}{\"},
}
\renewcommand{\lstlistingname}{Code}
\input{dummy.tex} %% Font 

\begin{document}

% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{分散フレームワークAliceのPC画面配信システムへの応用}
\author{照屋 のぞみ}{Nozomi Teruya}{琉球大学工学部情報工学科}[dpop@cr.ie.u-ryukyu.ac.jp]
\author{河野 真治}{Shinji Kono}{琉球大学工学部情報工学科}[kono@ie.u-ryukyu.ac.jp]

\begin{abstract}
当研究室ではデータを Data Segment、タスクを Code Segment という単位で分割して記述する手法を提唱しており、
それに基づく並列分散フレームワークAliceを開発している。
Aliceが分散プログラムを記述する能力を有することは水族館の例題等において確認された。
しかし、実用的な分散アプリケーションを構築するには圧縮形式で通信を行う機能等が必要であることが分かった。
本研究では、 実用的なアプリケーションである画面共有システムTreeVNCをAliceで実装するにあたり必要となった圧縮機能等をMeta Computationとして実装した。
データの多態性の実現により、扱うデータの形式を元のコードを大きく変更することなく指定することができ、ノード間通信における自由度の向上を図った。
\end{abstract}

\begin{jkeyword}
並列分散フレームワーク
\end{jkeyword}

\maketitle

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

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

先行研究 \cite{senkokenkyu} の水族館の例題等において、Aliceが分散プログラムを記述する能力を有することは確認された。
しかし、実用的な分散アプリケーションを作成するためには、動的トポロジーを管理・構成する機能や通信時にData Segmentを圧縮形式で扱う機能が必要な場合がある。
本研究では、Alice上に実用的な分散アプリケーションの例題である画面共有システムTreeVNC \cite{treeVNC} を構築する。
構築するにあたり必要となった圧縮などの機能を、AliceのMeta Computationとして実装する。
そして Alice を使用していないTreeVNCとの比較を行うことでMeta Computationの役割と有効性を示す。

\section{分散フレームワークAlice}
\subsection{Code Segment と Data 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=70mm]{images/dsandcs2.pdf}
    \end{center}
    \caption{CodeSegmentの依存関係 }
    \label{fig:CS}
\end{figure}

実際にはAliceはJavaで実装されており、DSはJavaObjectでCSはRunnableThreadである。プログラマーがCSを記述する際は、CodeSegmentクラスを継承し、DSを操作するAPIを使用する。

\subsection{DataSegmentManager}
DSは数値や文字列などの基本的なデータの集まりを指し、Aliceが内部にもつデータベースによって管理されている。このデータベースをAliceではDS Manager（以下DSM）と呼ぶ。

DSには対になるString型のkeyが存在し、このkeyを指定してDSの保存・取得を行う。
一つのkeyに対して複数のDSを登録することもでき、その場合DSはqueueに保存されFIFOで取り出される。

DSMにはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。
Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する（図 \ref{fig:RemoteDSM} ）。
他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い。
Remote DSMを立ち上げるには、DataSegment.classが提供するconnectメソッドを用いる。
接続したいノードのipアドレスとport番号、そして任意のManager名を指定することで立ちあげられる。その後はManager名を指定してData Segment APIを用いてDSのやり取りを行う。
\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{images/remote_datasegment.pdf}
    \end{center}
    \caption{Remote DSMは他のノードのLocal DSMのproxy }
    \label{fig:RemoteDSM}
\end{figure}

\newpage

\subsection{Data Segment API}
DSの保存・取得にはAliceが提供するAPIを用いる。
putとupdateはOutput DS APIと呼ばれ、DSをDSMに保存する際に用いる。
peekとtakeはInput DS APIと呼ばれ、DSをDSMから取得する際に使用する。

\begin{itemize}
\item {\ttfamily void put(String managerKey, String key, Object val)}
\end{itemize}
DSをDSMに追加するためのAPIである。第一引数はLocalDSMかRemoteDSMかといったManager名を指定する。そして第二引数で指定されたkeyに対応するDSとして第三引数の値を追加する。
\begin{itemize}
\item {\ttfamily void update(String managerKey, String key,  Object val)}
\end{itemize}
updateもDSをDSMに追加するためのAPIである。putとの違いは、queueの先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。

\begin{itemize}
\item {\ttfamily void take(String managerKey, String key)}
\end{itemize}
takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ （Blocking）が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。

\begin{itemize}
\item {\ttfamily void peek(String managerKey, String key)}
\end{itemize}
peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。

\subsection{Code Segmentの記述方法}
CSをユーザーが記述する際にはCodeSegment.classを継承して記述する(ソースコード \ref{src:StartCodeSegment} , \ref{src:CodeSegment})。
継承することによりCode Segmentで使用するData Segment APIを利用する事ができる。

\begin{table}[html]
    \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
    \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
\end{table}

Alice には、Start CS (ソースコード \ref{src:StartCodeSegment} )というC の main に相当するような最初に実行される CS がある。
Start CSはどのDSにも依存しない。つまりInput DSを持たない。
このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。

ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS（ソースコード \ref{src:CodeSegment} ）を作成している。8行目でOutput DS APIを通してLocal DSMに対してDSをputしている。
Output DS APIはCSの{\tt ods}というフィールドを用いてアクセスする。
{\tt ods}は{\tt put}と{\tt update}を実行することができる。
TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でputが行われるとTestCodeSegmentは実行される。


ソースコード\ref{src:CodeSegment}は、0から9までインクリメントする例題である。
2行目で取得されたDSが格納される受け皿を作る。Input DS APIがもつcreateメソッドを使うことで作成できる。
\begin{itemize}
\item {\ttfamily Receiver create(CommandType type)}
\end{itemize}

引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
Input DS API はCSの{\tt ids}というフィールドを用いてアクセスする。
Output DSは、{\tt ods}が提供するput/updateメソッドをそのまま呼べばよかったが、Input DSの場合{\tt ids}にpeek/takeメソッドはなく、create/setKeyメソッド内でCommandTypeを指定して実行する。

4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。

TestCodeSegmentのコンストラクタが呼ばれた際には、
\begin{enumerate}
\item CSが持つフィールド変数 {\tt Receiver input}に{\tt ids.create(CommandType.TAKE)}が行われ、{\tt input}が初期化される。
\item 5行目にあるTestCodeSegmentのコンストラクタのTAKEが実行される。
\end{enumerate}

5行目はInput DS APIがもつsetKeyメソッドによりLocal DSMからDSを取得している。
\begin{itemize}
\item \verb+void setKey(String managerKey, String key)+
\end{itemize}
setKeyメソッドはpeek/takeの実行を行う。どのDSMのどのkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。

runメソッドの内容としては
\begin{enumerate}
\item 10行目で取得されたDSをInteger型に変換してcountに代入する。
\item 12行目でcountをインクリメントする。
\item 16行目で次に実行されるCSが作られる。（この時点で次のCSはInput DSの待ち状態に入る）
\item 17行目でcountをLocal DSMにputする。Input DSが揃い待ち状態が解決されたため、次のCSが実行される。
\item 13行目が終了条件であり、countの値が10になれば終了する。
 \end{enumerate}
となっている。

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

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

\subsection{DSのMeta Computation}
CSはアプリケーションを動作させるために必要なタスクであり、ユーザーによって定義される。
それに対してMeta CSはAliceを構成するタスクである。つまりMeta CSの群はAliceのComputationと言い換えることができる。一部のみユーザーが定義をすることができ、Aliceの挙動を変更することができる。

\textbf{Topology Manager}

Aliceでは、ノード間の接続管理やトポロジーの構成管理を、Topology ManagerというMetaComputationが提供している。このTopology ManagerもCS/DSを用いて実装されている。
プログラマーはトポロジーファイルを用意し、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}）。
また、トポロジーファイルでlavelとして指定した名前はRemoteDSMの名前としてTopology Nodeに渡される。
そのため、Topology NodeはTopology ManagerのIPアドレスさえ知っていれば自分の接続すべきノードのデータを受け取り、ノード間での正しい接続を実現できる。
\begin{figure}[h]
\begin{center}
\includegraphics[width=60mm]{images/topologymanager.pdf}
\end{center}
\caption{TopologyManagerが記述に従いトポロジーを構成}
\label{fig:topologymanager}
\end{figure}

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

\textbf{Data Segmentの表現}

DSの表現にはMessagePack for Java \cite{MessagePack} を利用している。
\begin{itemize}
\item {\ttfamily DSは一般的なJavaのクラスオブジェクト}
\item {\ttfamily MessagePackを用いて変換したbyte[]で表現されたバイナリオブジェクト}
\end{itemize}
の２種類があり、LocalDSMにputされた場合は一般的なJavaのクラスオブジェクトとして追加される。
RemoteDSMにputされた場合は通信時にbyteArrayに変換されたバイナリオブジェクトが追加される。

\subsection{CSのMeta Computation}

\textbf{KeepAlive}

\textbf{切断・再接続時の処理}


\section{AliceVNC}
AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。
そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った。

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

TreeVNCは通信処理部分の記述が大変複雑になっている。しかし、Aliceで記述すれば本質的な処理とそれを支える通信処理部分で分離できる。
そのため、TightVNCからの修正も少なく、見通しの良い記述で構成可能と期待される。

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

\newpage
\section{Aliceの新機能}
実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。
\subsection{転送機能}
Input DSをRecieverに取得したあと、プログラマーはRecieverから値を任意の型で取り出し、値を操作した後putメソッドで再度別クラスに変換されOutput DSとして出力する。
しかし、Input DSとして取得したデータをそのまま子ノードにOutput DSとして出力する場合、一度Recieverから取り出し再変換する操作は無駄である。

そこで、Input DSとして受け取ったDSをそのままOutput DSとして転送する機能をput/updateとは別にflipメソッドをData Segment APIに実装した。
Input DSであるReceiverを展開せずにflipメソッドに引数として渡すことで、展開のオーバーヘッドをなくしている。
TreeVNCでは親ノードから受け取った画面データをそのまま子ノードに配信するため、Meta Computationとして転送機能が有用である。

\subsection{Data Segmentの表現の追加（圧縮機能）}
TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。
そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。
しかし、ただデータを圧縮する機構を追加すればいいわけではない。

AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DSMに送信する。
ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。
しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。
圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。

そこで、１つのData Segmentに対し複数の表現を持たせることで、必要に応じた形式でDSを扱うことを可能にした。
DSを扱うReceiveData.classに、次の3種類の表現を同時に持つことができる。

\begin{enumerate}
  \item 一般的なJavaのクラスオブジェクト
  \item MessagePack for Javaでシリアライズ化されたバイナリオブジェクト
  \item 2を圧縮したバイナリオブジェクト
\end{enumerate}

ソースコード \ref{src:ReceiveData} はReceiveData.classが持つ表現であり、{\tt val}に(1) 一般的なJavaのクラスオブジェクト の表現でデータ本体が保存される。
{\tt messagePack}には(2) シリアライズ化されたバイナリオブジェクトが保存され、通常のRemoteDSMへの通信にこの表現が扱われる。
そして、{\tt zMessagePack}には(3) 圧縮されたバイナリオブジェクトが保存される。

\begin{table}[html]
\lstinputlisting[label=src:ReceiveData, caption=データを表現するクラス]{source/ReceiveData.java}
\end{table}

\newpage
また、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerを追加した。
Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。

ソースコード \ref{src:before} はRemoteDSMに対しInt型のデータをputする記述である。
これをDSを圧縮形式で行いたい場合、ソースコード \ref{src:after} のように指定するDSM名の先頭に"compressed"をつければCompressed DSM内部の圧縮Meta Computationが走りDSを圧縮状態で扱うようになる。

\begin{table}[html]
\lstinputlisting[label=src:before, caption=通常のDSを扱うCSの例]{source/beforeCompress.java}
\end{table}

\begin{table}[html]
\lstinputlisting[label=src:after,caption=圧縮したDSを扱うCSの例]{source/afterCompress.java}
\end{table}


これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現を持つDSを扱うことができる。
ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipメソッドで転送すれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。
画面表示の際はReceiveData.class内の{\tt asClass()}(ソースコード\ref {src:asClass} )を使うことで適切な形式でデータを取得できる。
{\tt asClass()}はDSを目的の型にcastするメソッドであり、ReceiveData.classが圧縮表現だけを持っている場合はこのメソッド内で解凍してcastを行っている。
これによりDSの表現を必要になったときに作成できる。

\begin{table}[html]
\lstinputlisting[label=src:asClass, caption=asClassの処理]{source/asClass.java}
\end{table}

\subsection{Aliceの通信プロトコルの変更}
2.4 Data Segmentの表現 で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。
しかし、TreeVNCのようにもとからbyteArrayの画像データをputする場合、MessagePackでシリアライズされたものかの判別が付かない。
また、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判断する必要がある。

そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード \ref{src:CommandMessage} )にシリアライズ状態表すフラグと、圧縮状態を表すフラグを追加した。

\begin{table}[html]
\lstinputlisting[label=src:CommandMessage, caption=CommandMessage]{source/CommandMessage.java}
\end{table}

\newpage
\begin{table}[htbp]
\caption{CommandMessageの変数名の説明}
\label{tb:variable}
\begin{center}
\begin{tabular} {|l|l|}
  \hline
  変数名&説明\\
  \hline
  type&CommandType {\tt PEEK, PUT}などを表す\\
  \hline
  seq&\shortstack{Data Segmentの待ち合わせを行っている\\Code Segmentを表すunique number }\\
  \hline
  key&どのKeyに対して操作を行うか指定する\\
  \hline

  quickFlag&SEDAを挟まずCommandを処理を行うかを示す\\
  \hline
  serialized&データ本体のシリアライズ状態を示す\\
  \hline

  compressed&データ本体の圧縮状態を示す\\
  \hline

  dataSize&圧縮前のデータサイズを表す\\
  \hline

\end{tabular}
\end{center}
\end{table}


これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。
また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。

\section{評価と考察}
TreeVNCをAlice上で構築するために必要な機能をAliceのMeta Computationとして実装した。
それにより、AliceVNCが簡潔な記述でTreeVNCと同等の性能を出せれば、実用的な分散アプリケーションの実装においてAliceのMeta Computationは有用であるといえる。
そこで、TreeVNCとAliceVNCの性能評価としてメッセージ伝達速度の比較を、コードの評価としてコード量とその複雑度の比較を行った。

また、AliceのMeta Computationの価値を明確にするため、他言語・フレームワークとの比較を行った。

\subsection{メッセージ伝達速度の比較}
TreeVNC/AliceVNCにおいて、配信する画像データは構成した木を伝ってノードに伝搬され、接続する人数が増える毎に木の段数は増えていく。
そこで、木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測した。

\textbf{実験環境}

講義内で学生に協力してもらい、最大17名の接続がある中でTreeVNC、AliceVNC(圧縮・転送機能あり)、AliceVNC(圧縮・転送機能なし)の木の段数1~3の測定を行った。

\textbf{実験内容}

ルートノードから画面データを子ノードに伝搬する際に、計測用のヘッダをつけたパケットを子ノードに送信する。
各子ノードはパケットを受け取り自身のViewerに画面データを表示すると同時に、計測用ヘッダ部分のみのDSを作成し、親ノードに送り返す（図 \ref{fig:mesure}） 。
計測用DSは木を伝ってルートノードまで送り返され、ルートノードは受け取った計測用DSから到達時間を計算する。
\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{images/delay.pdf}
    \end{center}
    \caption{各ノードごとに到達時間を測定}
    \label{fig:mesure}
\end{figure}

計測用のヘッダは以下の要素で構成されている。
\begin{table}[htbp]
\caption{計測用ヘッダの変数名の説明}
\label{tb:variable}
\begin{center}
\begin{tabular} {|l|l|}
  \hline
  変数名&説明\\
  \hline
  time&ルートノードがパケットを送信した時刻\\
  \hline
  depth&木の段数。初期値=1。\\
  \hline
  dataSize&送信時の形式に変換済みの画面データのサイズ\\
  \hline
\end{tabular}
\end{center}
\end{table}
timeにはパケットの送信時刻を、dataSizeには画面データのサイズを付けて送信する。
今回、TreeVNCとAliceVNC(圧縮・転送機能あり)では圧縮形式の画面データのサイズを、AliceVNC(圧縮・転送機能なし)ではMessegePack形式でのサイズをdataSizeにセットする。
depthは各ノードに到達するごとにインクリメントされる。

計算方法をソースコード \ref{src:mesurement}に示す。
到達時間は、計測用DSを受け取った時刻とDSのtime（送信した時刻）の差をとる。
この到達時間は画面データがノードまで到達した時間と計測DSをルートまで送り返す時間を含めているが、送り返す時間は誤差として考える。
また、depthは各ノードに到達するごとにインクリメントされるため、送り返す際もインクリメントされる。そのため、木の段数を計算するにはdepthを1/2した値となる。

\begin{table}[html]
\lstinputlisting[label=src:Mesurement, caption=到達時間・木の段数の計測方法]{source/mesurement.java}
\end{table}

\textbf{実験結果}  

3段目の測定結果の散布図を示す（図\ref{fig:TreeVNC_delay} 〜 \ref{fig:AliceVNC_notcompress_delay}）。
X軸が画面データのサイズ(byte)、Y軸が計算した到達時間(ms)である。
実験時間の都合上、AliceVNC（圧縮・転送機能あり）の計測時間が他より短くなってしまったためプロットされた点の数が少なくなっている。
また、それぞれの図で処理に10000ms以上かかっている点の集合が見られるが、これは今回の実験において3段目にPCのスペック上処理が遅いノードが1台あったためである。そのため比較においてこの点集合は無視する。

どの図も同様の傾向があり、画面データのサイズが小さいうちは処理時間も5ms程度だが、50000byte以上から比例して処理時間も遅くなっている。このことからAliceVNCはTreeVNCと同等の処理性能があることがわかる。

また、AliceVNCを圧縮機能の有無でデータサイズ比較すると、圧縮機能のないAliceVNCはデータサイズがほとんど1000byte以上なのに対し、圧縮機能のあるAliceVNCではTreeVNC同様10byte程度のサイズに抑えるので圧縮も成功している。

さらに転送機能の有無で比較した場合、転送機能がないAliceVNCでは木の段数に関係なく1000ms近く到達に時間がかかってしまっているが、転送機能のあるAliceVNCではデータサイズが大きくなっても100ms程度に抑えられている。これは転送機能が余計なコピーを防いでいるためだと考えられる。
このことから、圧縮・転送のMeta Computationは分散通信において有用であると言える。
\newpage
\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{images/TreeVNC_depth3.pdf}
    \end{center}
    \caption{TreeVNCの測定結果}
    \label{fig:TreeVNC_delay}
\end{figure}

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{images/AliceVNC_notcompress_depth3.pdf}
    \end{center}
    \caption{AliceVNC(圧縮・転送機能なし)の測定結果}
    \label{fig:AliceVNC_notcompress_delay}
\end{figure}

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{images/AliceVNC_compress_depth3.pdf}
    \end{center}
    \caption{AliceVNC(圧縮・転送機能あり)の測定結果}
    \label{fig:AliceVNC_compress_delay}
\end{figure}
\newpage

\subsection{コードの比較}
\textbf{コード量}

TreeVNCとAliceVNCのコード量を比較した表が表\ref{tb:code}である。
TightVNCを含むコード全体にwcを行い、行数と単語数を比較した。
また、hg diffでTightVNCからの変更行数を調べ変更量を比較した。

表からわかるように、Aliceを用いればコードの行数が25\%削減できる。
また、TreeVNCではTightVNCに大幅に修正を加えながら作成したため仕様の変更が多かった。
しかし、AliceVNCではTightVNCにほとんど修正を加えることなくトポロジー構成等のAliceのMeta Computationを使うために新しいクラスを作成したのみであった。
そのためTreeVNCに比べ75\%も仕様の変更が抑えられている。
\begin{table}[htbp]
\caption{コード量の比較}
\label{tb:code}
\begin{center}
\begin{tabular} {|l|l|l|l|}
  \hline
   &行数&単語数&変更行数\\
  \hline
  TreeVNC&19502&73646&7351\\%11369+8133=19502,47010+26636,2094+5257
  \hline
  AliceVNC&14647&59217&1129\\%689+7094+6864=14647,23035+34610+1572,689+395+45
  \hline
  減少率(\%)&25&20&75\\
  \hline
\end{tabular}
\end{center}
\end{table}


\textbf{コードの複雑度}

コード量の比較で述べたように、TreeVNCはTightVNCからの変更が多い。
その理由の一つがトポロジーの構成や通信処理がコアな仕様と分離できておらず、
そのためTreeVNCは大変複雑な記述になってしまっている。

そこでTreeVNCとAliceVNCにおいてコードの複雑度を比較した。
今回、複雑度の指標としてThomas McCabeが提案した循環的複雑度\cite{complaxy}を用いた。
循環的複雑度とはコード内の線形独立な経路の数であり、if文やfor文が多ければ複雑度も高くなりバグ混入率も高まる。
一般的に、循環的複雑度が10以下であればバグ混入率の少ない非常に良いコードとされる。
計測にはIntelliJのCodeMetrics計測プラグインであるMetricsReloadedを使用した。

表\ref{tb:complex}はTightVNC、TreeVNC、AliceVNCにおける循環的複雑度の比較である。
プロジェクト全体でのクラスの複雑度の平均値と最高値をとった。
平均値・最高値ともにAliceVNCのほうが複雑度が低いことから、Aliceではシンプルな記述が可能だということがわかる。

TreeVNCで最高値を出したTreeRFBProto.classは全てプログラマーが記述したコードであり、データの待ち合わせのためのタイマー処理や通信処理、画面データの圧縮処理などの複数のスレッド処理が集中した複雑なコードになっている。
これをAliceで記述した場合、データの待ち合わせはCSが行うためプログラマーがデータの不整合を気にする必要はなく、また通信処理や圧縮処理もMeta Computationが提供するためコードが複雑になることはない。

AliceVNCで複雑度の最高値を出したSwingViewerWindow.classはTightVNCで最高値を出したクラスと同じであり、コード量の比較でも示したようにAliceVNCで変更を加えた点がほとんどない。つまりこの複雑度は元来TightVNCが持っている複雑度と言える。

\begin{table}[htbp]
\caption{複雑度の比較}
\label{tb:complex}
\begin{center}
\begin{tabular} {|l|l|l|}
  \hline
   &平均値&最高値\\
  \hline
  TightVNC&13.63&97\\
  \hline
  TreeVNC&15.33&141\\
  \hline
  AliceVNC&10.95&99\\%(4.12+13.64)/2 (4.12+9.16+19.59)/3
  \hline
\end{tabular}
\end{center}
\end{table}

AliceVNCとTreeVNCの性能比較・コード比較から、AliceVNCはTreeVNCと同等の性能を持つ分散アプリケーションの記述ができ、かつコードの修正量・複雑度共に低く抑える能力を有することがわかった。

\subsection{他言語・フレームワークとの比較}

Aliceが採用しているCS/DSのプログラミングモデルやMeta Computationの特性を明確にするため、他言語・フレームワークとの類似点・相違点を比較した。

\textbf{Erlang}

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

しかしErlangでは分散環境の構築等はすべてプログラマ自身が記述しなければならない。
Aliceでは分散環境の構築はTopology ManagerなどのMeta Computationが行うためプログラマーはトポロジーを指定するだけで良い。
また、Erlangでは複数のデータの待ち合わせのための再帰処理も自分で書かないといけない。
一方、Aliceのプログラミング手法はCSが必要なデータが全て揃うまで待ち合わせを行うためその必要はない。


\textbf{Akka}

Akka\cite{Akka}はScala・Java向けの並列分散処理フレームワークである。
アクターモデルを採用しており、アクターと呼ばれるアドレスを持ったタスクに、データをメッセージでやりとりする点がErlangと似ている。
AkkaもErlangもプロセス/アクターに直接データをやりとりする。データには名前がないため、メッセージを受け取ったあとにその内容を確認した上で次にどう振る舞うかを判断する。
一方Aliceでは、DSをCSに直接やりとりはせず、keyを指定してDSMにputする。
また、DSをtakeするときもkeyを指定して取り出すためどんなデータが入っているかを確認する必要がなく、扱い易い。

Akkaの特徴として、メッセージを送りたいプロセスのアドレスを知っていればアクターがどのマシン上にあるかを意識せずにプログラミングできるという点がある。
逆にAliceはどのRemoteDSMに対してやり取りをするかを考慮するが、CSがOutputしたDSを次にどのCSに渡すかを意識する必要がない。この点はアクターモデルとCS/DSモデルのパラダイムの違いと言える。

一方AliceとAkkaは提供されるAPIという点で類似している。AkkaのメッセージAPIでは、メッセージを送るtellメソッドと、メッセージを送って返信を待つaskメソッドが用意されている。これはAliceのDataSegment APIのput/takeメソッドに対応している。

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


\section{まとめ}
並列分散フレームワークAliceでは、スケーラブルかつ信頼性の高いプログラムを記述する環境を実現するため、CS/DSの計算モデルとMeta Computationによる実装の階層化を採用している。
Aliceが実用的な分散アプリケーションを記述するために必要なMeta Computationとして、d動的なトポロジー管理・構成機能や多態性を持つデータを扱う機能、データを無駄なコピーをすることなく転送する機能などを実装した。
そしてMeta Computationを用いて分散アプリケーションTreeVNCをAlice上で実装し性能評価を行った。
その結果、TreeVNCで使用される基本機能はAliceでも実現でき、同等の性能を出すことができるということが分かった。
またコードの観点からTreeVNCとAliceVNCを比較した結果、Aliceが仕様の変更を抑えたシンプルな記述を実現し、信頼性の高い実用的な分散アプリケーションを構築するに有用であることが確認された。

今後の課題としては、TreeVNCで実装が困難であったNATを超えたノード間通信をAliceVNCで実現し、その性能とコード修正量を比較することが挙げられる。
図\ref{fig:overNAT}は２つの違うプライベートネットワークを超えた接続の設計例である。

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=75mm]{images/overNAT.pdf}
    \end{center}
    \caption{複数のTopologyManagerでNAT超えを実現}
    \label{fig:overNAT}
\end{figure}

各ネットワークごとにTopoogy Managerを立ち上げることでネットワークを超えたノード間接続を実現する。
プライベートネットワークのTopoogy Managerは今までどおりネットワーク内に木を構築・管理する。
他のネットワークにあるノードBがノードAに接続したい場合は、グローバルアドレスを持ったTopology Managerに参加表明をすればノードAの情報が提供され、ノードAの子ノードとして接続される。
つまり、Topology Managerを複数用意するだけで、Topology Manager自体の「参加表明のあったノードで木を構成する」という仕様は全く変更しないで良い。
TreeVNCでは500行以上の変更が必要とされたが、Aliceでは複数のTopology Managerに接続するためのconfigファイルを変更するだけなので、AliceVNCの仕様の変更を抑えられると期待される。
この機能も実現できれば、AliceのMeta Computationが拡張性の高い環境を提供できると言える。

また、現在のAliceはネットワーク通信においてセキュリティをサポートしていない。
しかし、圧縮機能と同様に、暗号化形式を扱うMeta Computationを追加すれば、プログラマーが記述するComputation部分を大きく変えずに自由度の高い通信を行うことができる。





\nocite{*}
\bibliographystyle{ipsjunsrt}
\bibliography{prosym}


\end{document}