\chapter{TreeVNCの実装}
\label{chap:introduction}


\section{木の生成}
今回は、ホストに対しクライアントがツリー状に繋がっていくように実装した。ツリー\\
の構成は以下の手順で行う。
　\begin{enumerate}
  \item クライアントが接続する際、ホストに接続をしているプロキシ（今後このプロ\\
キシのことをTopと記述する）に接続する。
　\item Topはクライアントの接続を受けると、どこに接続すれば良いかをクライアントに教える(この時にクライアントにシリアルナンバーを振っていく)。
　\item クライアントはTopから指定されたノードに接続を行う。
　\end{enumerate}
\subsection{Topの仕事}
Topはクライアントが接続してくるたびにjava.util.LinkedListにクライアントの情報を追加していく。

クライアントからアクセスが来るたびにスレッドを作成しているので、
複数のクライアントが同時に接続してきても対応することができる。
しかし、多数のスレッドが同じjava.util.LinkedListなどの共有資源に対して同時に接続を行うと
共有資源の情報が正しく更新されない可能性が出てくる。
このような共有資源を更新する際はjavaのsynchronizedメソッドを使用して複数のスレッドが共有資源
に同時にアクセスすることができないようにした。

TopはtreeBranch(木の分木数)を定数で持っていて
クライアントが接続してくるごとにcounterをインクリメントしていき
LinkedListの(counter - 1)/treeBranche番目に入っている親の情報を
接続してきたクライアントに教えることで木を構成することができる。
\newpage
\section{木の再構成}
木を構成することはできたが途中のクライアントが落ちてしまった場合に木を再構成しなければならない。
木を再構成する手順は以下の用に行う。
　\begin{enumerate}
  \item 子供が親が落ちたことをTopに対して報告する。
　\item Topは報告を受けると番号の一番大きいノード(最後のノード)に対して落ちた親の代わりになるように報告する。
　\item Top命令を受けたクライアントはTopの指定された場所に接続をしなおす。
　\item Topはクライアントのリストを更新して、親が落ちた子供たちに新しい親の情報を教える。
　\item 親が落ちた子供たちは新しい親に対して接続を行う。
　\end{enumerate}
このようにして木を再構成することができる。
以下のソースは、親が落ちた子供が接続してきた時に、子供全員の接続を待つ部分のコードの一部である。

\begin{lstlisting}[label=src:AcceptClient, caption=wait()]
  final int TIMEOUT = 3000;
  if (passNumber == 0) {
    passNumber++;
    wait(TIMEOUT)
    passNumber = 0;
    } else {
    if (++passNumber == TREEBRANCH) {
      notifyAll();
      passNumber = 0;
      } else {
      wait(TIMEOUT);
      }
  }
\end{lstlisting}

上記のコードでは落ちた子供たちの報告を待ち合わせることができる。
TREEBRANCHは木を構成する際の分木数であるフィールド変数としてfinalで定義されている。passNumberは報告する子供たちを数えるためのカウンタである。
プロキシは子供分の報告全て揃うと子供たちに新しい親の情報を流し始める。
TIMEOUTが設定されているのは、子供が報告の際に落ちて報告が届かない場合があるのでそれに対応したものである。
\newpage

\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.6]{fig/reconnectionCollaboration01.pdf}
\end{center}
\caption{
再接続の様子
}
\label{figure:reconnection}
\end{figure}

図5.1破砕接続の様子を記したコラボレーションダイアグラムである。以下に関数の説明をする。\\

1:lostHost()は親が落ちたことを報告する関数である。\\

2:reportLastNode()は番号の一番大きい(最後のノード)に対して親の代わりをするように命令する関数である。\\

3:listUpdate()はプロキシが持つクライアントのリスト情報をアップデートする
(落ちたノードを削除し最後のノードのアドレスをそこに追加する)。\\

4:lostHost()は上記で説明したとおりである。なぜ間に2と3が呼ばれているのかというと最初にlostHost()が呼ばれて、
listUpdate()が終わるまで他のノードの報告はブロックされるからである。Client4が先に報告に行く場合もある。\\

5:waitReply.start()はクライアントはwaitReplyというクラスをmainスレッドとは別にスレッドを作成して走らせている。
もしプロキシからの命令が来るとクライアントはプロキシから指定された場所に接続を行う。\\

\newpage

\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.6]{fig/reconnectionCollaboration02.pdf}
\end{center}
\caption{
再接続の様子
}
\label{figure:reconnection2}
\end{figure}

図5.2は前のページ続きを記したものである。以下に関数の説明を行う。\\

6:replyChildlen()はListing5.1で説明したとおり全クライアントが報告に来るまで待った後、
親が落ちた子供たちに対して新しい親の情報を報告する関数である。\\

7:reConnection()はプロキシから来た情報をもとにVNC接続を行う関数である。\\

以上の関数を用いることでクライアントが落ちても木を再構成することができる。

\newpage

\section{クライアントとの通信}
 TreeVNCは、受け取った画面の描画データをそのまま自分に繋がっている次のクライアントに送信する。
描画データを受け取ったクライントはまた次のクライアントへデータをそのまま送信する。
内部では、まず受け取った描画データの読み込みを先に行いBytebufferでコピーを行う。
次にクライアントへの送信と自身のビューアへの描画を並列に行う。


\subsection{データの先読み}
1回のFramebufferUpdateで送られくるデータ量はエンコードタイプまで読みこめば知ることができる。
例えば、RAWエンコードの場合は width * height * 4 のバイト数が送られてくる(4はピクセルのデータ量である)。
計算で求めた数の分とヘッダーを合わせた数だけバイトを読み込むことで
1回分のFramebufferUpdateのコピーを行うことができる。

\subsection{FramebufferrUpdate}
RFB プロトコルでの画面の描画の更新は、FramebufferUpdateで行われる。
FramebufferUpdateを受け取ることで画面の再描画が行われる。
FrameBufferUpdateでは、メッセージタイプと画面の矩形の数がまず送られ、
次にx座標、y座標、横幅、縦幅、エンコードのタイプ、描画データが矩形の数だけ送ら\\
れてくる。
描画データはエンコードのタイプに従った方法で送られてくる。

\subsection{MulticastQueue}
画面が更新された際に更新をクライアントに伝えなければならない。ノードが多数ある場合、一人一人に更新を知らせるのではなく、同時に画面の更新を知らせたい。
同時に更新を知らせるために、CountDownLatchを用いてMultiCastQueueを作成した。

java.util.concurrent.CountDownLatchはjavaの並列用に用意されたAPIで
他のスレッドで実行中の操作が完了するまで、複数のスレッドを待機させることのできるクラスである。

使い方は、カウント(何回カウントしたらスレッドを開放するのかの数)を指定してCountDownLatchの初期化を行う。

countDownメソッドを使うとカウントダウンを行うことができる。

awaitメソッドはcowntDownメソッドの呼び出しの結果カウントがゼロになるまでの間スレッドをブロックすることができる。

countDwonメソッドの結果がゼロになるとawaitメソッドで停止していたスレッドが動き出す。



MulticastQueueはQueueのように使用することができる。

putメソッドを使用してデータをqueueに追加する。データをputする際にCountDownLatchをカウントダウンする。
pollメソッドを持ちいることで、次のデータを取得することができる。
pollメソッドの中でawaitが使われているので次のputでデータが来るまでスレッドがブロックする。(図5.3)

新しくデータがputされるとデータの読み込みが再開される。(図5.4)

このようなことを行うことでデータの更新が来た際に複数のクライアントに対して
並列にデータを転送することが出来る。(図5.5)
\vspace{5mm}


\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.5]{fig/multicastqueue2.pdf}
\end{center}
\caption{
データがなければwaitする
}
\label{figure:multicastqueue}
\end{figure}

\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.5]{fig/multicastqueue.pdf}
\end{center}
\caption{
新しいデータが来るとデータを読み出す
}
\label{figure:multicastqueue2}
\end{figure}




\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.7]{fig/multicastqueue.eps}
\end{center}
\caption{
クライアントへは並列にデータを送信する。
}
\label{figure:multicastqueue}
\end{figure}

\newpage


\subsection{TimeOut}
MultiCastQueueを使ってのデータの取得には問題が発生した。
それは、接続してきたクライアントがデータを取得しない状況、例えばサスペンド状態になったときにTopのメモリの中にデータが残り続けるというものである。
メモリに残り続けたデータはやがてメモリオーバーフローを引き起こしてしまうのである。その様子を図5.6に示す。


\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.7]{fig/TimeOut2.eps}
\end{center}
\caption{
クライアントサスペンド時のTopのメモリの様子。
データが残り続けメモリを圧迫してしまう。
}
\label{figure:TimeOut2.eps}
\end{figure}


そこで、ある一定の時間がたつと代わりにデータを取得してくれるTimeOut用のスレッドを作成した。
TimeOutスレッドはサスペンドしているクライアントの代わりにデータを取得する。
\newpage


\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.7]{fig/TimeOut3.eps}
\end{center}
\caption{
TimeOutが代わりにデータを取得する
}
\label{figure:TimeOut3.eps}
\end{figure}

TimeOutスレッドがクライアントの代わりにデータを取得することで、MulticastQueueの中からデータが削除されTopのメモリを圧迫することがなくなった。(図5.7)


\newpage
\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圧縮は辞書を持っていて、その辞書に登録されているデータを元に解凍が行われる。(図5.8)
しかし、java.util.zip.deflaterは現在持っている辞書を書き出すこと(flush)ができないことが分かった。
辞書を書きだすことができない為、Zlib圧縮されたデータを途中から受け取ってもデータが正しく解凍を行うことができない。
(図5.9)
%元々のZlibの規約にはこの辞書をflushする機能があったがJavaには実装されていなかった。

\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale = 0.6]{fig/ZRLE.pdf}
\end{center}
\caption{
ZRLE
}
\label{figure:ZRLE}
\end{figure}


\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale = 0.6]{fig/ZRLE2.pdf}
\end{center}
\caption{
ZRLE2
}
\label{figure:ZRLE2}
\end{figure}
\newpage 

\subsection{ZRLEE}
そこで、TopがZRLEで受け取ったデータをunzipし、データをzipし直して最後にfinish()
をいれることで初めからデータを読んでいなくても解凍を行えるようにした
(毎回新しい辞書を使うようにした)。(図5.10、図5.11)
このエンコードはZRLEEエンコードと定義した。
一度ZRLEEエンコードに変換してしまえば、そのデータをそのまま流すだけで良い。
よって変換はTopが行う一回だけですむ。
ただし、deflater,inflaterでは前回までの通信で得た辞書をクリアしないといけないため、
Topとクライアント側では毎回新しく作る必要がある(クライアント側はinflaterだけ)。
また、ZRLEEはクライアント側が対応していなければならないという問題がある。

\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale = 0.7]{fig/ZRLEE2.pdf}
\end{center}
\caption{
ZRLEE
}
\label{figure:ZRLEE2}
\end{figure}

\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale = 0.7]{fig/ZRLEE3.pdf}
\end{center}
\caption{
ZRLEE2
}
\label{figure:ZRLEE3}
\end{figure}


\subsubsection{ZRLEとZRLEEのデータ圧縮率の比較}
RAW,ZRLE,ZRLEEのデータ量の比較を行った。                                        
図6は1920 * 1080の画面の全描画にかかるデータ量を測った結果を示した図である。
ZRLEEの方がデータ量が少なくですんでいる。(図5.12)
これは、ZRLE(Zlib)が初めに送られた辞書を用いての解凍が余り有効的に働いていない
場合があるからだと思われる。                                                    
つまりVNCの場合はZRLEEの様に毎回辞書のデータを付加させて送ってもデータ量に差が
でない可能性があることが分かった。                                              


\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale = 0.8]{fig/compare_encoding.eps}
\end{center}
\caption{
RAW,ZRLE,ZRLEEによる1画面(1920*1080)描画にかかるデータ量。
x軸はピクセル数、y軸はバイト数を表している。
}
\label{figure:compare_encoding}
\end{figure}


\newpage


\section{UserInterface}
\subsection{プロキシの検索}
TreeVNCはクライアントが起動した際にBroadcastをもちいて、
同一セグメント内にプロキシが起動しているかを調べる。
プロキシはクライアントからBroadcastのリクエストが飛んでくると、
リクエストのあったクライアントに対してソケットを張ってクライアントに自分の情報を教える。
クライアントは上記の要領で同一セグメント内にあるプロキシの情報を得ることができるので、
同一セグメントに有るプロキシの一覧を表示することができるのでクライアントはその中から
どの画面に接続するかを選択することができる。

\subsection{TreeVNCの使い方}
今回作成したTreeVNCはクライアントが使いやすいように設計を行った。
TreeVNCはまずプロキシを起動させる事が必要である。
プロキシを始動するには-pオプションを指定してやる事で
localhostに対してVNC要求を出すことができる。
この時自分の画面にアクセス要求が来るので画面を共有を認証するとプロキシが立ち上がる。

別のコンピュータに対して画面共有を行いたい場合は-pオプションを指定してやるか
、第一引数にIpAddress,第二引数にportを指定してやる事で別のコンピュータの
画面共有も行う事ができる。

クライアントは引数なしで実行すると(ダブルクリックで実行できる)
現在つなぐ事のできるプロキシの一覧が表示されるので、選択すると画面共有を行うことができる。

しかし、説明したとおりBroadcastを使用してプロキシの検索を行っているので、
別セグメントで起動しているプロキシを見つける事ができない。
そこで、TreeVNCを起動する際に-cオプションを付けてやる事で、
アドレス入力欄が表示されるので、そこに接続したいプロキシのアドレスを
入力する事で、別セグメントのプロキシとも画面共有を行えるようにした。

\newpage
\section{LionAuthenticate}
プロキシがサーバに対してVNC接続を行う際、ハンドシェイクが必要となる。
ハンドシェイクの手順として、まず始めにプロキシがサーバに接続を行うと、
サーバがサポートする最新のプロトコルバージョンが送られてくる。
プロキシはサーバから送られてきたプロトコルバージョン以下の使用できるバージョンを
サーバに対し送る。現時点で公開されているプロトコルバージョンは3.3、3.7、3.8だけである。
今回TreeVNCは3.855というバージョンを用意して3.855が来るとTreeVNCを使用するようにした。

プロトコルバージョンが決定すると、サーバ及びクライアントは、
その接続で使用されるセキュリティに合意しなければならない。
バージョン3.7移行ではサーバは自身のサポートするセキュリティタイプの一覧を提示する。
クライアントのサポートする有効なセキュリティタイプを少なくとも一つサーバが提示した場合、クライアントはその接続上で使用されるセキュリティタイプを表す単一バイトを送り返す。

登録されているセキュリティタイプの一例として(表 \ref{tb:authtype})のようなものがある。

\begin{table}[htbp]
\caption{AuthType}
\label{tb:authtype}
\begin{center}
\begin{tabular} {|l|l|}
  \hline
  {\bf 値}&名称\\
  \hline
  {\bf 0}&Invalid\\
  \hline
  {\bf 2}&None\\
  \hline
  {\bf 5}&RA2\\
  \hline
  {\bf 18}&TLS\\
  \hline
  {\bf 21}&MD5 ハッシュ認証\\
  \hline
\end{tabular}
\end{center}
\end{table}

MACOSX SnowLeopardで起動しているVNCサーバに接続するときには
MAC専用の認証の値35がありこれでパスワード認証を行うことができていた。

しかしMACOSX Lionでパスワード認証を行おうとすると、
MACOSX Lionにしてパスワード認証ができなくなったので、
別の認証方法で認証を行うことにした。

調べてみるとMACOSXはが返してくる認証番号は[30, 31, 32, 2, 35]がある。
32はサーバに対して画面要求の認証を求めるタイプの認証であることがわかった。
この認証を用いるとサーバに対してプロキシが接続する際にサーバ側に確認画面が出るようになる。
サーバ側がこれを容認すると認証が成立する。