--- a/paper/main.tex	Thu Feb 04 18:49:58 2016 +0900
+++ b/paper/main.tex	Thu Feb 04 18:50:39 2016 +0900
@@ -54,13 +54,191 @@
 \label{chap:concept}
 
 \section{VNC}
+VNC(Virtual Network Computing) は、 RFBプロトコルを用いて遠隔操作を行うリモートデスクトップソフトウェアである。
+VNC はサーバー側とクライアント(ビューア)側に分かれている。 サーバを起動し、クライアントがサーバに接続を行い遠隔操作を可能とする。
+
 \section{RFB プロトコル}
+RFB(remote frame buffer)プロトコル\cite{rfbProtocol}とは、自身の画面を送信し、ネットワーク越しに他者の画面に表示するプロトコルである。
+ユーザが居る側をRFBクライアント側と呼び、Framebufferへの更新が行われる側はRFBサーバと呼ぶ。
+Framebufferとは、メモリ上に置かれた画像データのことである。
+RFBプロトコルでは、最初にプロトコルバージョンの確認や認証が行われる。
+その後、クライアントに向けてFramebufferの大きさやデスクトップに付けられた名前などが含まれている初期メッセージが送信される。
+RFBサーバ側はFramebufferの更新が行われるたびに、RFBクライアントに対してFramebufferの変更部分だけを送信する。
+更にRFBクライアントのFramebufferUpdateRequestが来るとそれに答え返信する。
+RFBプロトコルは、描画データに使われるエンコードが多数用意されており、また独自のエンコードを実装することもできるプロトコルである。
+
 \section{多人数で VNC を使用する際の問題}
+VNCを使用すればクライアント側にサーバー側の画面を表示することが可能である。 
+しかし、多人数のクライアントが1つのサーバーに接続してしまうと処理性能が落ちてしまうという問題点がある。
+
+また、 ゼミ等の発表で画面配信者が頻繁に切り替わる場合、
+配信者が替わる度にアプリケーションを終了し、接続をし直さないといけないという問題がある。
+
 \section{TreeVNC の構造}
+TreeVNC は Java を用いて作成された TightVNC(Tight Virtual Network Computing)\cite{tightvnc} を元に作成されている。
+
+TreeVNC は クライアント同士を接続させ、画面描画のデータを受け取ったクライアントが次のクライアントにデータを流す方式を取っている。
+また、サーバへ接続しに来たクライアントをバイナリツリー状に接続する(図\ref{fig:tree})。
+バイナリツリー状に接続することで、$N$台のクライアントが接続しに来た場合、画面配信の画像データをコピーする回数は従来の VNC ではサーバ側で$N$回する必要があるが、TreeVNCでは各ノードが2回ずつコピーするだけで済む。 
+
+TreeVNCで通信される画像のデータ量は大きいため、大きなネットワークスループットが必要である。
+そのため、有線接続が必須である。
+
+バイナリツリーのルートのノードを Root Node と呼び、 Root Node に接続されるノードを Node と呼ぶ
+Root Node は子 Nodeにデータを流す機能に加え、各 Node の管理、 VNC サーバーから流れてきた画像データの管理を行う。 
+Node は 親 Node から送られたデータを 自分の子 Node に流す機能、 逆に子 Node から送られてきたデータを 親 Node に流す機能がある。
+
+\begin{figure}[ht]
+    \begin{center}
+        \includegraphics[width=70mm]{./pic/TreeVNC.pdf}
+    \end{center}
+    \caption{構成される木構造}
+    \label{fig:tree}
+\end{figure}
+
 \section{圧縮形式}
+TreeVNC は ZRLEE\cite{taninari:2012a} というエンコードでデータのやり取りを行う。
+ZRLEE はRFB プロトコルで使えるエンコーディングタイプの ZRLE を元に生成される。
+
+ZRLE は Zlib\cite{zlib} で圧縮されたデータとそのデータのバイト数がヘッダーとして付けて送られてくる。
+Zlib は java.util.zip.deflater と java.util.zip.inflater で圧縮と解凍が行える。
+
+しかし、 java.util.zip.deflater は解凍に必要な辞書を書き出す(flush)ことが出来ない。
+辞書を書き出すことが出来ないため、 Zlib圧縮されたデータを途中から受け取ってもデータを正しく解凍することが出来ない。
+
+そこで ZRLEE は 一度 Root Node で受け取った ZRLE のデータを unzip し、 データをzip し直して最後に finish() をいれることで初めからデータを呼んでいなくても解凍を行えるようにした。
+
+一度 ZRLEE に変換してしまえば子 Node はそのデータをそのまま流すだけで良い。
+ただし、deflater と inflater では前回までの通信で得た辞書をクリアしないといけないため、 Root Node と Node 側では毎回新しく作る必要がある。
+
 \section{通信経路}
+TreeVNC の通信経路として以下が挙げられる
+\begin{itemize}
+    \item ある Node から Root Node に直接通信を行う send direct message (Node to Root)
+    \item Root Node からある Node に直接通信を行う send direct message (Root to Node)
+    \item Root Node から木の末端の Node までのすべての Nodeに通信を行う messeage down tree (Root to Node)
+    \item ある Node から木構造を上に辿って Root Nodeまで通信を行う message up tree (Node to Root)
+    \item Root Node から配信者の VNC サーバーへの通信を行う send message (Root to VNCServer)
+    \item VNC サーバーから Root Node への通信を行う send message (VNCServer to Root)
+\end{itemize}
+
+\section{ノード間で行われるメッセージ通信}
+RFBプロトコルで提供されているメッセージに加え、 TreeVNC 独自のメッセージを使用している。
+TreeVNC で使用されるメッセージの一覧を表\ref{tb:message}に示す。
+
+\begin{table}[h!]
+    \caption{通信経路とメッセージ一覧}
+    \large
+    \scalebox{0.4} {
+        \begin{tabular}{|l|l|l|} \hline
+            通信経路            & message                    & 説明 \\ \hline \hline
+                                & FIND\_ROOT                 & TreeVNC接続時にRoot Nodeを探す。 \\ \cline{2-3}
+            send direct message & WHERE\_TO\_CONNECT         & 接続先をRoot Nodeに聞く。 \\ \cline{2-3}
+            (Node to Root)      & LOST\_CHILD                & 子Nodeの切断をRoot Nodeに知らせる。 \\ \hline \hline
+
+                                & FIND\_ROOT\_REPLY          & FIND\_ROOTへの返信。 \\ \cline{2-3}
+            send direct message & CONNECT\_TO\_AS\_LEADER    & 左子Nodeとして接続する。接続先のNodeが含まれている。 \\ \cline{2-3}
+            (Root to Node)      & CONNECT                    & 右子Nodeとして接続する。接続先のNodeが含まれている。 \\ \hline \hline
+
+            message down tree   & FRAMEBUFFER\_UPDATE        & 画像データ。EncodingTypeを持っている。\\ \cline{2-3}
+            (Root to Node)      & CHECK\_DELAY               & 通信の遅延を測定する。 \\ \hline \hline
+
+            message up tree     & CHECK\_DELAY\_REPLY        & CHECK\_DELAYへの返信。 \\ \cline{2-3}
+            (Node to Root)      & SERVER\_CHANGE\_REQUEST    & 画面切り替え要求。 \\ \hline \hline
+
+                                & FRAMEBUFFER\_UPDATE\_REPLY & 画像データの要求。 \\ \cline{2-3}
+            send message        & SET\_PIXEL\_FORMAT         & pixel値の設定。 \\ \cline{2-3}
+            (Root to VNCServer) & SET\_ENCODINGS             & pixelデータのencodeTypeの設定。 \\ \cline{2-3}
+                                & KEY\_EVENT                 & キーボードからのイベント。 \\ \cline{2-3}
+                                & POINTER\_EVENT             & ポインタからのイベント。 \\ \cline{2-3}
+                                & CLIENT\_CUT\_TEXT          & テキストのカットバッファを持った際のmessage。 \\ \hline \hline
+
+                                & FRAMEBUFFER\_UPDATE        & 画像データ。EncodingTypeを持っている。 \\ \cline{2-3}
+            send message        & SET\_COLOR\_MAP\_ENTRIES   & 指定されているpixel値にマップするRGB値。 \\ \cline{2-3}
+            (VNCServer to Root) & BELL                       & ビープ音を鳴らす。 \\ \cline{2-3}
+                                & SERVER\_CUT\_TEXT          & サーバがテキストのカットバッファを持った際のmessage。 \\ \hline
+        \end{tabular}
+    }
+    \label{tb:message}
+\end{table}
+
+図\ref{fig:message}は TreeVNC で Node が Root Node に接続し、画像データを受信するまでのメッセージ通信の様子である。
+図\ref{fig:message}の手順として
+
+\begin{itemize}
+    \item 接続を行う Node (以下 Client Node)はMulticast通信で Root Node に対してFIND\_ROOTを送信する(1:findRoot())
+    \item Root NodeがFIND\_ROOTを受信し、FIND\_ROOT\_REPLYを送信する(2:findRootReplay())
+    \item Client Node 側で、どのRoot Nodeに接続するかを選択するパネルが表示される
+    \item Client Node はパネルで接続するRoot Nodeを選択し、Rootに対して接続先を要求するWHERE\_TO\_CONNECTを送信する(3:whereToConnect())
+    \item 受信した Root Node は Client Node の接続先をCONNECT\_TOで送信する(4:connectTo)
+    \item Client Node は Root の指定した接続先に接続しに行く
+    \item Root Node, Client Node間の接続が確立後、Root Node から Clinet Node に対して定期的に画像データFRAME\_BUFFER\_UPDATEを送信する(5:framebufferUpdate())
+\end{itemize}
+
+を行っている。
+
+\begin{figure}[ht]
+    \begin{center}
+        \includegraphics[width=65mm]{./pic/message.pdf}
+    \end{center}
+    \caption{node 間で行われるメッセージ通信}
+    \label{fig:message}
+\end{figure}
+
 \section{MulticastQueue}
 \section{木の再構成}
+TreeVNC はバイナリツリーでの接続という特性上 Node が切断されたことを検知できずにいると、Node 同士で構成された木構造が崩れてしまい、新しい Node が接続に来た場合に適切な場所に Node を接続することができなくなってしまう。
+木構造を崩さないよう、Node 同士の接続を再構成を行う必要がある。
+
+TreeVNC の木構造のネットワークトポロジーは Root Node が持っている nodeList というリストで管理している。
+つまり、Node の接続が切れた場合、木の再構成を行うため Root Node に知らせなければならない。
+
+TreeVNC は Lost\_CHILD というメッセージ通信で Node の切断を検知・木の再構成を行っている。
+
+TreeVNC は VNC サーバーから送られる画像データ(FRAME\_BUFFER\_Update)を MulticastQueue というキューに蓄積しており、
+Node はこのキューから画像データを取得し、画面を描画している。
+Lost\_Child の検出方法はこの MulticastQueue を使用している。
+ある一定時間 MulticastQueue から画像データが取得されない場合 Memory Over Flow を回避するために Timeout スレッドが用意されている。
+Timeout を検知した際、Node との接続が切れたと判断する。
+
+Lost\_Child の検知・木の再構成を以下に示す。
+\begin{itemize}
+  \item 子 Node の切断を検知した Node が Root Node へ LOST\_CHILD メッセージを送信する(図\ref{fig:lostchild1}中, 1:lostChild())
+  \item LOST\_CHILD メッセージを受け取った Root Node は nodeList の更新を行う(図\ref{fig:lostchild1}中, 2:updateNodeList())
+  \item 切断した Node を nodeList から消し、nodeList の最後尾の Node に切断した node number を割り当てる
+  \item Root Node は最後尾の Node に、切断した子 Node が接続していた親 Node に接続する様に CONNECT\_TO メッセージを送信する(図\ref{fig:lostchild1}中, 3:connectTo(1))
+  \item 最後尾の Node が子 Node を失った親 Node へ接続しに行く(図\ref{fig:lostchild1}中, 4:connectToParent(1))
+\end{itemize}
+
+\begin{figure}[ht]
+  \begin{center}
+    \includegraphics[width=70mm]{./pic/lostChild1.pdf}
+  \end{center}
+  \caption{LOST\_CHILD を検知・再接続}
+  \label{fig:lostchild1}
+\end{figure}
+
+LOST\_CHILD によって、 切断された全ての Node を検知することができるため、 nodeList の更新が正しく行われる。
+よって、新しく接続に来た Node を適切な場所に接続することが可能となる。
+
+\section{共有画面切り替え}
+ゼミでは発表者が順々に入れ替わる。発表者が入れ替わる度に共有する画面の切り替えが必要となる。
+ゼミを円滑に進めるために、画面の切り替えをスムーズに行いたい。
+
+画面の共有にプロジェクタを使用する場合、 発表者が変わる度にケーブルの抜き差しを行う必要がある。
+その際に、ディスプレイ解像度を設定し直す必要が出たり、 接続不良が起こる等の煩わしい問題が生じることがある。
+
+従来のVNCを使用する場合、 画面の切り替えの度に一旦VNCを終了し、発表者の VNC サーバーへと再接続を行う必要がある。
+
+TreeVNC は配信者の切り替えの度に生じる問題を解決している。
+TreeVNC を立ち上げることで、ケーブルを使用する必要なしに、各参加者の手元のPCに発表者の画面を共有することができる。
+画面の切り替えはユーザが VNC サーバーへの再接続を行うことなく、ビューアの Share Screen ボタンを押すことによって、配信者の切り替えを行うことができる。
+
+TreeVNC の Root Node は配信者の VNC サーバーと通信を行っている。
+VNC サーバーから画面データを受信し、そのデータを 子 Node へと送信している。
+配信者切り替え時に Share Screen ボタンが押されると、
+Root Node は Share Screen ボタン を押したクライアントの VNC サーバーと通信を始める。
+そのためTreeVNCは配信者切り替えの度に VNC を終了し、再接続する必要がない。
 \section{複数ネットワークへの対応}
 
 % 実験