\chapter{TreeVNCの基本概念}
\label{chap:concept}

\section{Virtual Network Computing}
Virtual Network Computing(以下VNC)は、サーバ側とクライアント(ビューワー)側からなるリモートデスクトップソフトウェアである。遠隔操作にはサーバを起動し、クライアント側がサーバに接続することで可能としている。

\section{Remote Frame Bufferプロトコル}
Remote Frame Buffer(以下RFB)プロトコルとはVNC上で使用される、自身のPC画面をネットワーク上に送信し他人のPC画面に表示を行うプロトコルである。画面が表示されるユーザ側をRFBクライアントと呼び、画面送信を行うためにFrameBufferの更新が行われる側をRFBサーバと呼ぶ。

FrameBufferとは、メモリ上に置かれた画像データのことである。RFBプロトコルでは、最初にプロトコルのバージョンの確認や認証が行われる。その後、RFBクライアントへ向けてFramebufferの大きさやデスクトップに付けられた名前などが含まれている初期メッセージを送信する。

RFBサーバ側はFramebufferの更新が行われるたびに、RFBクライアントに対してFramebufferの変更部分を送信する。さらに、RFBクライアントからFramebuffer - UpdateRequestが来るとそれに答え返信する。変更部分のみを送信する理由は、更新があるたびに全画面を送信すると、送信するデータ面と更新にかかる時間面において効率が悪くなるからである。
\newpage
\section{TreeVNCの構造}
TreeVNCはjavaを用いて作成されたTight VNCを元に作成されている。 TreeVNCはVNCを利用して画面配信を行っているが、従来のVNCでは配信(サーバ)側のPCに全ての参加者(クライアント)が接続するため負荷が大きくなってしまう(図\ref{fig:vncStruct})。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[scale=0.33]{fig/vncStruct.pdf}
\figcaption{従来のVNCでの接続構造}
\label{fig:vncStruct}
\end{center}
\end{figure}


そこでTreeVNCではサーバに接続を行ってきたクライアントをバイナリツリー状(木構造)に接続する。接続してきたクライアントをノードとし、その下に新たなノードを最大2つ接続していく。これにより人数分のデータのコピーと送信の手間を分散することができる(図\ref{fig:TreevncStruct})。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[scale=0.35]{fig/TreevncStruct.pdf}
\figcaption{TreeVNCでの接続構造}
\label{fig:TreevncStruct}
\end{center}
\end{figure}


バイナリツリー状に接続することで、N台のクライアントが接続を行ってきた場合、従来のVNCではサーバ側がN回のコピーを行って画面配信する必要があるが、TreeVNCでは各ノードが最大2回ずつコピーするだけで画面配信が可能となる。

送信されるデータは従来の方法だとN個のノードに対してN-1回の通信が必要である。これはバイナリツリー状の構造を持っているTreeVNCでも通信の数は変わらない。

バイナリツリーのルートのノードをRoot Nodeと呼び、そこに接続されるノードをNodeと呼ぶ。Root Nodeは子Nodeにデータを渡す機能、各Nodeの管理、VNCサーバから送られてきたデータの管理を行っている。各Nodeは、親Nodeから送られてきたデータを自身の子Nodeに渡す機能、子Nodeから送られてきたデータを親Nodeに渡す機能がある。

\section{TreeVNCの通信プロトコル}
TreeVNCの通信経路としては以下が挙げられる。
\begin{itemize}
\item 任意のNodeからRoot Nodeに直接通信を行うsend direct message (Node to Root)
\item Root Nodeから任意のNodeに直接通信を行うsend direct message (Root to Node)
\item 任意のNodeから木構造を上に辿ってRoot Nodeまで通信を行う message up tree (Node to Root)
\item Root Nodeから木の末端のNodeまでの全てのNodeに通信を行うmessage down tree (Root to Node)
\item Root Nodeから配信者のVNCサーバへの通信を行う send message (Root to VNC Server)
\item 配信者のVNCサーバからRoot Nodeへの通信を行う send message (VNC Server to Root)
\end{itemize}

Node間で行われるメッセージ通信にはRFBプロトコルで提供されているメッセージに加え、TreeVNC独自のメッセージを使用している。TreeVNCで使用されるメッセージの一覧を表\ref{tb:messageTable}に示す。

\begin{table}[tbp]
	\begin{center}
	\tblcaption{通信経路とメッセージ一覧}
	\scalebox{0.7}{
    	\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\_TO					& 右子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:messageTable}
    \end{center}
\end{table}

\newpage

\section{MulticastQueue}
配信側の画面が更新されると、VNCサーバから画面データがFRAME\_BUFFER\_UPDATEメッセージとして送らる。その際、画像データの更新を同時に複数のNodeに伝えるためにMulticastQueueというキューにデータを蓄積している。
各Nodeはこのキューから画像データを取得し、画面の描画を行う。

\section{木の再構成}
TreeVNCはバイナリツリー状での接続のため、Nodeが切断されたことを検知できずにいると構成した木構造が崩れてしまい、新しいNodeを適切な場所に接続できなくなってしまう。そこで木構造を崩さないよう、Node同士の接続の再構成を行う必要がある。

TreeVNCの木構造の接続形態はRoot Nodeが持っているnodeListというリストで管理している。nodeList内のtreeNumという値が各Nodeに割り当てられており、これによって木構造のどの位置にNodeが接続されているかの判別が可能である。
よって、Nodeの接続が切れた場合Root Nodeに切断を知らせなければならない。TreeVNCはLOST\_CHILDというメッセージ通信で、Node切断の検知および木構造の再構成を行っている。

LOST\_CHILDの検出方法には、MulticastQueueを用いている。ある一定時間MulticastQueueから画像データが取得されない場合MemoryOverFlowを回避するためにTimeoutスレッドが用意されている。Timeoutを検知した際にNodeとの接続が切れたと判断する。
LOST\_CHILDの検知と木構造の再構成の手順を以下に示す。

\begin{itemize}
\item 子Nodeの切断を検知したNodeがRoot NodeへLOST\_CHILDメッセージを送信する(図\ref{fig:lostchild}中、1: lostChild())
\item LOST\_CHILDメッセージを受け取ったRoot NodeはnodeListの更新を行う(図\ref{fig:lostchild}中、2: updateNodeList())
\item 切断したNodeをnodeListから削除し、nodeListの最後尾のNodeに切断したNodeとtreeNumを割り当てる
\item Root Nodeは最後尾のNodeに、切断した子Nodeが接続していた親Nodeに接続するよう、COMMECT\_TOメッセージを送信する(図\ref{fig:lostchild}中、3: connectTo(1))
\item 最後尾のNodeが子Nodeを失った親Nodeへ接続を行う(図\ref{fig:lostchild}中、4: connectToParent(1))
\end{itemize}

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[scale=0.5]{fig/LostChild.pdf}
\figcaption{LOST\_CHILDの検知・再接続}
\label{fig:lostchild}
\end{center}
\end{figure}

LOST\_CHILDによって、切断された全てのNodeを検知することができるため、nodeListの更新が正しく行われる。よって、新しく接続を行ってきたNodeを適切な場所に接続することが可能となる。

\section{データの圧縮形式}
TreeVNCはZRLEEというエンコードタイプでデータのやり取りを行う。ZRLEEはRFBプロトコルで使用できるZLREというエンコードタイプを元に生成される。

ZLREはZlibで圧縮されたデータとそのデータのバイト数がヘッダーとして付与され送信される。Zlibはjava.util.zip.deflaterとjava.util.zip.inflaterで圧縮と解凍が行える。しかしjava\.util.zip.deflaterは解凍に必要な辞書を書きだす(flush)ことが出来ない。従って、圧縮されたデータを途中から受け取ってもデータを正しく解凍することが出来ない。

そこでZRLEEは一度Root Nodeで受け取ったZRLEのデータをunzipし、後述するupdate Rectangleと呼ばれる画面ごとのデータに辞書を付与してzipし直すことで、初めからデータを読み込んでいなくても解凍を出来るようになっている(\ref{fig:ZRLEtoZRLEE})。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[scale=0.5]{fig/EncodeZRLEE.pdf}
\figcaption{ZRLEEへ再圧縮}
\label{fig:ZRLEtoZRLEE}
\end{center}
\end{figure}




TreeVNCではRFBプロトコルによって配信側の画面の変更部分はFRAME\_BUFFER\_UPDATEメッセージとして送られてくる。メッセージの中には変更部分の原点のx,y座標と縦横の幅が含まれており、長方形として展開される。この長方形をupdate Rectangleと呼ぶ。以下の表\ref{tb:updateRectangle}にupdate Rectangleの構成を示す。

\begin{table}[hp]
    \caption{updateRectangleの構成}
    \begin{center}
    \begin{tabular}{|rrr|l|} \hline
        1 byte & & & messageID    \\
        1 byte & & & padding   \\
        2 byte & & & n of rectangles   \\ \hline
        & 2 byte & & U16 - x-position  \\
        & 2 byte & &  U16 - y-position  \\
        & 2 byte & &  U16 - width  \\
        & 2 byte & &  U16 - height  \\
        & 4 byte & &  S32 - encoding-type  \\
        & 4 byte & &  U32 datalengths   \\ \hline
        &  & 1 byte & subencoding of tile     \\
        &  & n byte & Run Length Encoded Tile \\ \hline
    \end{tabular}
    \end{center}
    \label{tb:updateRectangle}
\end{table}



\section{ShareScreen}