--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/chapter3.tex	Mon Feb 03 16:56:17 2014 +0900
@@ -0,0 +1,337 @@
+\chapter{画面共有システムTreeVNCの設計}
+
+\section{木構造を用いたTreeVNCの設計}
+まず、多人数が参加している授業でVNCを使う場合に起こる問題は、一つのコンピュータに多人数が繋がり、処理が集中してしまって、性能が大幅に落ちてしまうところである(図\ref{fig:vnc})。
+多人数の同時接続を可能にするには、一極集中で接続するのではなく、Node同士で負荷を分散させることによって実現できるのではないかと考えた。\\
+負荷分散を行う際、Node同士どのようなトポロジを組むのが適切か検討した結果、上から流れてきたデータを下のNodeへと伝えていくことのできる木構造が良いと考えた。\\
+　今回行った設計ではNodeを木構造に接続させデータを流すためにサーバとNodeの間にRoot Node(サーバとNodeの通信を仲介するもの)を設置する方式をとった。Root Nodeは主にNodeの管理とServerから流れてきた画像データの管理を担当する。\\
+木構造で設計したものを(図\ref{fig:treestructure})に示す。\\
+
+
+\begin{figure}[htbp]
+ \begin{minipage}{0.5\hsize}
+  \begin{center}
+   \includegraphics[width=80mm]{./images/vnc.pdf}
+  \end{center}
+  \caption{VNCの構造}
+  \label{fig:vnc}
+ \end{minipage}
+ \begin{minipage}{0.5\hsize}
+ \begin{center}
+  \includegraphics[width=80mm]{./images/treestructure.pdf}
+ \end{center}
+  \caption{TreeVNCの構造}
+  \label{fig:treestructure}
+ \end{minipage}
+\end{figure}
+
+\newpage
+
+\section{TreeVNCの原理}
+TreeVNCがどのような負荷分散を行った結果、どのように負荷が分散されているのかを説明する。\\
+通常のVNCでは、一極集中型でサーバに接続してしまうのでサーバに負荷がかかって性能を低下させたり停止してしまっている。そこでNodeを木構造に配置させることで、負荷がなくなっているように見える。しかし、実は負荷がスイッチにかかっていて、消えているわけではない。
+通常のVNCとTreeVNCの構造を比較した図を(図\ref{fig:comparenormalandtree})に示す。\\
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=130mm]{./images/comparenormalandtree.pdf}
+\end{center}
+\caption{TreeVNCの構造}
+\label{fig:comparenormalandtree}
+\end{figure}
+
+
+(表\ref{tb:oneporttraffic})はポート一本あたりの通信量である。\\
+表から推察できるように、ポート一本あたりの負荷は通常のVNCの場合はNode数に比例して増えている。しかしTreeVNCの場合はTreeの子供の数が一定なので、Node数に関係なく一定である。\\
+送信する量も通常のVNCの場合Node数に比例した量のデータ送信しなければならいので、CPUに負荷がかかり性能が低下したり停止したりしている。\\
+対してTreeVNCはが増えても配信するデータは一定なので性能が低下せず使用することができる。
+
+\begin{table}[htbp]
+\caption{ポート一本あたりの通信量(NはNode数、MはTreeの子供の数)}
+\label{tb:oneporttraffic}
+\begin{center}
+  \begin{tabular}{|c|c|c|} \hline
+    & 通常のVNC & TreeVNC  \\ \hline
+    通信量 & N * データ量 & (M + 1) * データ量  \\ \hline
+  \end{tabular}
+\end{center}
+\end{table}
+
+
+
+%\section{画面拡大縮小}
+%\section{画面描画範囲の指定}
+
+\subsection{木の生成}
+負荷を分散させるために木構造を用いるので、Nodeをツリー状に接続する仕組みが必要である。TreeVNCでは、以下の点順で、木の構成を行う。\\
+図\ref{fig:createtree}は、２分木で木を構成する際の手続きを示したシーケンスダイアグラムである。\\
+1.初めにNodeはRoot Nodeに接続先IPを尋ねる(Where connect)。\\
+2.Root Nodeは、Nodeに接続するべきホストのIPを引き渡す(Answer)。\\
+3.Nodeは指定されたホストに接続する(Connect)。
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=140mm]{./images/createtree.pdf}
+\end{center}
+\caption{TreeVNCの構造}
+\label{fig:createtree}
+\end{figure}
+\newpage
+
+
+\subsection{Root Nodeの仕事}
+Root Nodeの大きな仕事は、Nodeの管理である。NodeのIPアドレス情報をJavaのLinkedListで保持している。
+LinkedListの簡単な説明を\ref{tb:LinkedList}に示す。
+
+\begin{table}[htbp]
+\caption{LinkedList}
+\label{tb:LinkedList}
+\begin{center}
+  \begin{tabular}{|c||c|} \hline
+    関数 & 説明    \\ \hline
+     add(E e) & Listの最後にeを追加する。 \\ \hline
+     get(int index) & リストの$index$番目の値を取得する。\\ \hline
+     remove(int index) & リストの$index$番目の値を削除する。 \\ \hline
+  \end{tabular}
+\end{center}
+\end{table}
+
+
+Listing\ref{src:tree}はNodeを管理している部分のプログラムである。
+%$line$は接続先を訪ねてきたNodeのIPアドレスであり、$(nodeCounter - 1) / treebranch$で接続するべき親を求め結果を返している。\\
+%treebranchは木の分岐数である。
+
+$line$は接続先を訪ねてきたNodeのIPアドレスである。初めに接続してきた、Nodeのアドレスを自分が保持しているlist(LinkedList)に登録する。\\
+親の番号は$(counter - 1)/TreeBraanche$で求めることができるので、listに親の番号を指定し、親のIPアドレスを取得する。\\
+取得したIpを接続してきたNode($line$)に送り返すことで、NodeはどのIPアドレスに接続すればよいのか知ることができる。
+
+\begin{lstlisting}[language=java,frame=lrbt,label=src:tree,caption=クライアント管理のプログラム,numbers=left]
+  private LinkedList<String> ls = new LinkedList()<String>;
+  private synchronized void replyCreateTree(PrintStream os, String line) throws InterruptedException {
+    ls.add(line);
+    parentnum = (nodeCounter - 1) / treebranch;
+    request = ls.get(parentnum);
+    outputStream(os, request, String.valueOf(parentnum), String.valueOf(nodeCounter));
+  }
+\end{lstlisting}
+
+
+\newpage
+\section{表示画面の切り替え}
+VNCを使用して画面共有を行う場合、授業などでは講師の画面を共有していれば問題ない。しかし、ゼミなどの発表者が多数いる場合は画面共有の対象をを切り替えなければならない。画面共有対象の切り替えを行う場合、発表者ごとにサーバを立ち上げ直さなければならないという問題が発生する。そこで、ユーザ側からRoot Nodeにリクエストを出して、画面共有の対象を切り替える機能が必要になる。
+画面を切り替えるときは、Root Nodeだけが接続を切り替え、Nodeたちはそのデータを受け取るだけで良い(図\ref{fig:change})。
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=100mm]{./images/changeserver.pdf}
+\end{center}
+\caption{表示画面の切り替え}
+\label{fig:change}
+\end{figure}
+画面の切替をどのユーザが行うのかという問題がある。Root Nodeに対してユーザが毎回IPアドレスを入力して切り替えるのは手間がかかる。そこで、Node側に画面切り替えボタンを設置し、ボタンを押すとRoot Nodeに自分の画面へ切り替えるように命令を出しRoot Nodeが了承すると画面が切り替わるように設計した。
+
+\newpage
+\section{マルチディスプレイの対応}
+マルチディスプレイを用いてVNCを行うと、すべてのディスプレイのデータが繋がって表示されてしまう。通常発表などに使用されるディスプレイは一つである。すべての画面のデータを送ってしまうとその分だけ無駄なデータを送っていることになる。そこで、発表用に使用する画面のデータだけを送ることのできるようにディスプレイが指定できるようになることが必要になる。
+
+
+\section{再接続}
+木を構成することはできたが途中のNodeが切断してしまった場合に木を再構成しなければならない。
+木を再構成する手順は以下の用に行う。
+　\begin{enumerate}
+  \item 子供のリーダー(最初に親につないだ子供)が親が落ちたことをRoot Nodeに対して報告する。
+　\item Root Nodeは報告を受けると番号の一番大きいNode(最後のNode)に対して落ちた親の代\
+わりになるように報告する。
+　\item Root Nodeから命令を受けたNodeは指定されたNodeに接続をしなおす。
+　\item Root NodeはNodeのリストを更新して、親が落ちた子供たちに新しい親の情報を教える。
+　\item 親が切断された子供たちは、Root Nodeからもらった情報を元に新しい親に対して接続を行う。
+　\end{enumerate}
+このようにして木を再構成することができる。
+\newpage
+
+図\ref{fig:reconnection}は再接続の様子を記したコラボレーションダイアグラムである。以下に関数の説明をする。
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=140mm]{./images/reconnection.pdf}
+\end{center}
+\caption{再接続の手続き}
+\label{fig:reconnection}
+\end{figure}
+
+1:lostHost():親に切断されたこと報告する関数である。\\
+
+2:reportLastNode():番号の一番大きい(最後のノード)に対して親の代わりをするように命令する関数である。\\
+
+3:listUpdate():Root Nodeが持つNodeのリスト情報をアップデートする(切断したノードを削除し最後のノードのアドレスをそこに追加する)。\\
+
+4:waitReply.start():NodeはwaitReplyというクラスをmainスレッドとは別にスレッドを作成して走らせている。
+もしRoot Nodeからの命令が来るとNodeはRoot Nodeから指定された場所に接続を行う。\\
+
+\newpage
+
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=140mm]{./images/reconnection2.pdf}
+\end{center}
+\caption{再接続の手続き２}
+\label{fig:reconnection2}
+\end{figure}
+
+6:replyChildlen()は、親が切断した子供たちに対して新しい親の情報を報告する関数である。\\
+
+7:reConnection()はRoot Nodeから来た情報をもとにVNC接続を行う関数である。
+
+以上の関数を用いることでNodeが落ちても木を再構成することができる。
+
+\newpage 
+
+\section{MulticastQueue}
+画面が更新された際に画像の更新をNodeに伝えなければならない。ノードが多数ある場合、各ノードに順番に更新を知らせるのではなく、同時に画面の更新を知らせたい。
+同時に更新を知らせるために、CountDownLatchを用いてMultiCastQueueを作成した。
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=100mm]{./images/countdownlatch.pdf}
+\end{center}
+\caption{CountDownLatch}
+\label{fig:CountDownLatch}
+\end{figure}
+
+
+java.util.concurrent.CountDownLatchはjavaの並列用に用意されたAPIで他のスレッドで実行中の操作が完了するまで、複数のスレッドを待機させることのできるクラスである。
+使い方は、カウント(何回カウントしたらスレッドを開放するのかの数)を指定してCountDownLatchの初期化を行う。
+countDownメソッドを使うとカウントダウンを行うことができる。
+awaitメソッドはcowntDownメソッドの呼び出しの結果カウントがゼロになるまでの間スレッドをブロックすることができる。
+countDwonメソッドの結果がゼロになるとawaitメソッドで停止していたスレッドが動き出す(図\ref{fig:CountDownLatch})。
+MulticastQueueはQueueのように使用することができる。
+putメソッドを使用してデータをqueueに追加する。データをputする際にCountDownLatchをカウントダウンする。
+pollメソッドを用いることで、次のデータを取得することができる。
+pollメソッドの中でawaitが使われているので次のputでデータが来るまでスレッドがブロックする。(図\ref{fig:multicastqueue})
+
+新しくデータがputされるとデータの読み込みが再開される。(図\ref{fig:multicastqueue2})
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=120mm]{./images/multicastqueue.pdf}
+\end{center}
+\caption{MulticastQueue(データが来るまで待つ)}
+\label{fig:multicastqueue}
+\end{figure}
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=120mm]{./images/multicastqueue2.pdf}
+\end{center}
+\caption{MulticastQueue(新しいデータが来るとデータを読み出す)}
+\label{fig:multicastqueue2}
+\end{figure}
+
+\newpage
+\subsection{TimeOut}
+MultiCastQueueを使ってのデータの取得には問題が発生した。
+それは、接続してきたNodeがデータを取得しない状況、例えばサスペンド状態になったときにRoot Nodeのメモリの中にデータが残り続けるというものである。
+メモリに残り続けたデータはやがてメモリオーバーフローを引き起こしてしまうのである。その様子を図\ref{fig:TimeOut}に示す。
+TimeOutスレッドがNodeの代わりにデータを取得することで、MulticastQueueの中からデータが削除されRoot Nodeのメモリを圧迫することがなくなった。(図\ref{fig:TimeOut2})
+
+\begin{figure}[tb]
+\begin{center}
+  \includegraphics[scale = 0.5]{images/TimeOut.pdf}
+\end{center}
+\caption{
+Nodeサスペンド時のRoot Nodeのメモリの様子。
+データが残り続けメモリを圧迫してしまう。
+}
+\label{fig:TimeOut}
+\end{figure}
+
+
+そこで、ある一定の時間が経過すると代わりにデータを取得してくれるTimeOut用のスレッドを作成した。
+TimeOutスレッドはサスペンドしているNodeの代わりにデータを取得する。
+
+\begin{figure}[tb]
+\begin{center}
+\includegraphics[scale = 0.5]{images/TimeOut2.pdf}
+\end{center}
+\caption{
+TimeOutが代わりにデータを取得する
+}
+\label{fig:TimeOut2}
+\end{figure}
+
+
+
+
+
+
+\section{圧縮の問題}
+VNCで扱うRFB プロトコルには、使えるエンコーディングのタイプの1つとしてZRLE(Zlib Run-Length Encoding)がある。
+ZRLEはZlibで圧縮されたデータとそのデータのバイト数がヘッダーとして付けられ送られてくる。
+Zlibはフリーのデータ圧縮及び解凍を行うライブラリである。
+可逆圧縮アルゴリズムの圧縮と解凍が行えるjava.util.zip.deflaterとjava.util.zip.inflaterを実装している。
+
+\subsection{java.util.zip.deflaterの実装の問題}
+Zlib圧縮は辞書を持っていて、その辞書に登録されているデータを元に解凍が行われる(図\ref{fig:ZRLE})。
+しかし、java.util.zip.deflaterは現在持っている辞書を書き出すこと(flush)ができないことが分かった。
+辞書を書きだすことができない為、Zlib圧縮されたデータを途中から受け取ってもデータが正しく解凍を行うことができない
+(図\ref{fig:ZRLE2})。
+%元々のZlibの規約にはこの辞書をflushする機能があったがJavaには実装されていなかった\\
+                                                                                  
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=100mm]{images/ZRLE.pdf}
+\end{center}
+\caption{
+ZRLE
+}
+\label{fig:ZRLE}
+\end{figure}
+
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=100mm]{images/ZRLE2.pdf}
+\end{center}
+\caption{
+ZRLE2
+}
+\label{fig:ZRLE2}
+\end{figure}
+
+
+\subsection{ZRLEE}
+そこで、Root NodeがZRLEで受け取ったデータをunzipし、データをzipし直して最後にfinish()
+をいれることで初めからデータを読んでいなくても解凍を行えるようにした
+(毎回新しい辞書を使うようにした)。(図\ref{fig:ZRLEE})
+このエンコードはZRLEEエンコードと定義した。
+一度ZRLEEエンコードに変換してしまえば、そのデータをそのまま流すだけで良い。
+よって変換はRoot Nodeが行う一回だけですむ。
+ただし、deflater,inflaterでは前回までの通信で得た辞書をクリアしないといけないため、
+Root NodeとNode側では毎回新しく作る必要がある(Node側はinflaterだけ)。
+また、ZRLEEはNode側が対応していなければならないという問題がある。
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=120mm]{images/ZRLEE.pdf}
+\end{center}
+\caption{
+ZRLEE
+}
+\label{fig:ZRLEE}
+\end{figure}
+
+
+\subsection{接続先自動検索システム}
+NodeがRoot Nodeに接続する際、Root NodeのIPアドレスを指定する必要がある。IPアドレスを毎回入力するのは手間がかかる上、間違うと接続することができない。\\
+そこで、Nodeが起動した際に、起動しているTreeVNCのRoot Nodeを検索し、IPアドレスの情報を取得し、一覧にして選択させることによって直接アドレスを手入力する必要がなくなる。\\
+TreeVNCのRoot Nodeを検索する際には、Broadcast通信を用いることによって実現することができる。\\
+
+
+
+
+
+
+
+