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

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

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

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

RFBサーバ側はFramebufferの更新が行われるたびに、RFBクライアントに対してFramebufferの変更部分を送信する。さらに、RFBクライアントからFramebuffer - UpdateRequestが来るとそれに答え返信する。変更部分のみを送信する理由は、更新があるたびに全画面を送信すると、送信するデータ面と更新にかかる時間面において効率が悪くなるからである。
\newpage
\section{TreeVNCの構造}
TreeVNCはjavaを用いて作成されたTight VNC\cite{tightvnc}を元に作成されている。 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が受け取った画像データを、同時に複数の子Nodeに伝えるためにMulticastQueueというキューにデータを蓄積を行う。

各NodeはMulticastQueueからデータを取得するスレッドを持つ。MulticastQueueは複数のスレッドから使用される。
MulticastQueueはjava.util.concurrent.CountDownLatchを用いて実装されている。CountDownLatchとはjavaの並列実行用に用意されたAPIで、他のスレッドで実行中の操作が完了するまで、複数のスレッドを待機させることができるクラスである。スレッドを解放するカウントを設定することができ、カウントが0になるまでawaitメソッドでスレッドをブロックすることができる。

TreeVNCでは、親NodeがMulticastQueueを持っており、接続されている子Nodeの数だけ画像データにカウントを設定する。子Nodeが画像データを取得すると、そのカウントが減る。接続している全ての子Nodeが画像データを取得するとカウントが0になり、MulticastQueueから画像データが削除される。

\newpage

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

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

LOST\_CHILDの検出方法には、MulticastQueueを用いている。親NodeがMulticastQueueを持っているが、接続している全ての子Nodeが画像データを取得するまでMulticastQueueの中に入っている画像データを削除することができない。子NodeがMulticastQueueから画像データを取得せずに、画像データが溜まり続けると親Nodeが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\cite{taninari:2012a}というエンコードタイプでデータのやり取りを行う。ZRLEEはRFBプロトコルで使用できるZLREというエンコードタイプを元に生成される。

ZLRE(Zlib Run-Length Encoding)とは可逆圧縮可能なZlib形式\cite{zlib}とRun-Length Encoding方式を組み合わせたエンコードタイプである。

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

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[scale=0.5]{fig/EncodeZRLE.pdf}
\figcaption{ZRLEでデータを途中から受け取った場合}
\label{fig:ZRLE}
\end{center}
\end{figure}

\newpage

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

一度ZRLEEに変換してしまえば、子Nodeはそのデータをそのまま流すだけでよい。ただし、deflaterとinflaterでは前回までの通信で得た辞書をクリアしないとけないため、Root Node側とNode側では毎回新しく作る必要がある。辞書をクリアすることで短時間で解凍され画面描画されるという、適応圧縮を実現していることになり圧縮率が向上する。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[scale=0.5]{fig/EncodeZRLEtoZRLEE.pdf}
\figcaption{ZRLEEへ再圧縮されたデータを途中から受け取った場合}
\label{fig:ZRLEtoZRLEE}
\end{center}
\end{figure}

\newpage

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

\section{ShareScreen}
ゼミでは発表者が順々に入れ替わる。発表者が入れ替わるたびに共有する画面の切り替えが必要となる。ゼミを円滑に進めるために、画面の切り替えをスムーズに行いたい。

画面の共有にプロジェクタを使用する場合、発表者が変わるたびにケーブルの抜き差しを行う必要がある。その際に、PCとプロジェクタを接続するための変換アダプタが必要になる場合や、接触不良が起こる等の煩わしい問題が生じることがある。

従来のVNCでは、配信者が切り替わるたびにVNCの再起動、サーバ・クライアント間の再接続を行う必要がある。TreeVNCは配信者の切り替えのたびに生じる問題を解決している。

TreeVNCを立ち上げることでケーブルを使用する必要なしに、各参加者の手元のPCに発表者の画面を共有することができる。画面の切り替えについてはユーザがVNCサーバへの際接続を行うことなく、ビューワー側のShare Screenボタンを押すことで配信者の切り替えが可能となっている。

TreeVNCのRoot Nodeは配信者のVNCサーバと通信を行なっている。VNCサーバから画面データを受信し、そのデータを子Nodeへと送信している。配信者切り替え時にShare Screenを実行すると、Root Nodeに対しSERVER\_CHANGE\_REQUESTというメッセージが送信される。このメッセージにはShare Screenボタンを押したNodeの番号やディスプレイ情報が付与されている。メッセージを受け取ったRoot Nodeは配信を希望しているNodeのVNCサーバと通信を始める。そのためTreeVNCは配信者切り替えのたびにVNCを終了し再接続する必要がない。

\newpage

\section{複数のネットワーク接続時の木の構成}
TreeVNCはRoot Nodeが複数のネットワークに接続している場合、図\ref{fig:multinetwork}のようにネットワーク別にを形成する。TreeVNCはRoot NodeがTreeManagerを持っている。TreeManagerはTreeVNCの接続部分を管理しており、木構造を管理するnodeListの生成を行う。このnodeListを元に、新しいNodeの接続や、切断検出時の接続の切り替え等を行なっている。

TreeManagerはRoot Nodeの保持しているネットワーク毎に生成される。新しいNodeが接続してきた際、interfacesからNodeのネットワークと一致するTree Managerを取得し、Node接続の処理を任せる。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[scale=0.7]{fig/MultiNetworkTree.pdf}
\figcaption{Multi Network Tree}
\label{fig:multinetwork}
\end{center}
\end{figure}