\chapter{TreeVNC の基本概念}
% VNCとはなにか？どのようなものか？どのようにしてなりたっているか？

　TreeVNC は当研究室で開発している画面配信ソフトウェアである。

本章は TreeVNC の基本概念となっている技術について説明する。

% どういう概念？ どうしてそうするの？ どうやってつかうの？ 
\section{Virtual Network Computing}
TreeVNC の名称にもある VNC (Virtual Network Computing) は、RFB プロトコルを用いて PC の遠隔操作を行うことを目的としたリモートデスクトップソフトウェアである。

サーバー側とクライアント側に分かれており、起動したサーバーにクライアントが接続することで遠隔操作を可能にしている。


\section{RFB プロトコル}
RFB (Remote Frame Buffer) プロトコルは、自身の画面をネットワークを通じて送信し他者の画面に表示するプロトコルである。

ユーザがいる(画面を表示される)側と FrameBuffer への更新が行われる(自身の画面を送信する)側に分かれ、それぞれを RFB クライアント、RFB サーバと呼ぶ。FrameBuffer は、メモリ上に置かれた画像データのことである。

RFB プロトコルでは、始めにプロトコルバージョンの確認、認証を行う。その後クライアントに向けて FrameBuffer の大きさやデスクトップに付けられた名前などが含まれている初期メッセージが送信される。RFB サーバ側は FrameBuffer の更新が行われるたびに RFB クライアントに対して FrameBuffer の変更部分だけを送信する。更に、RFB クライアントの FramebufferUpdateRequest が来るとそれに答え返信する。変更部分だけを送信する理由は、更新がある度に全画面を送信していると、送信するデータ面、更新にかかる時間面において効率が悪いからである。


\section{TreeStructure}
TreeVNC はサーバーに接続してきたクライアントをバイナリツリー状に接続している。また、接続してきたクライアントをノードとし、その下に新たなクライアントを接続していくことでサーバーが画面のデータを配信する回数を抑えることで負荷分散している(図\ref{fig:treevnc})。バイナリツリー状に接続することで、画像データのコピーを各ノードに負担させることができ、従来の VNC ではクライアントが N 台接続するとサーバー側が N 回コピーを行なって配信していた(図\ref{fig:vnc})が、この接続方法であれば各ノードが 2 回ずつコピーすることで配信を可能にしている。

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



\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.55}{\includegraphics{fig/treevnc-crop.pdf}}
 \end{center}
 \caption{TreeVNC の接続方法}
 \label{fig:treevnc}
\end{figure}


\begin{figure}[htpb]
 \begin{center}
  \scalebox{0.55}{\includegraphics{fig/vnc-crop.pdf}}
 \end{center}
 \caption{従来の VNC の接続方法}
 \label{fig:vnc}
\end{figure}

\newpage
\section{通信経路}
TreeVNC の通信経路は以下の六つである。
\begin{itemize}
 \item Root Nodeから任意のNodeに直接通信を行う send direct message (Root to Node)
 \item 任意のNodeからRoot Nodeに直接通信を行う send direct message (Node to Root)
 \item Root Nodeから木の末端までの全てのNodeに通信を行う message 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{メッセージ通信}
TreeVNC の各 Node と VNCServer 間で通信されるメッセージを表\ref{tb:message}に示す。

\begin{table}[htbp]
    \scriptsize
    \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}
    \caption{通信経路とメッセージ一覧}
    \label{tb:message}
\end{table}


\newpage
\section{MulticastQueue}
配信側の画面が更新されると VNC Server から画像データが FRAME\_BUFFER\_UPDATE メッセージとして送られる。その際、画像データの更新を複数の Node に同時に伝えるために Multicast Queue というキューに画像データを格納する。


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

TreeVNC の木構造のネットワークトポロジーは Root Node が持っている nodeList で管理している。
Node の接続が切れた場合、Root Node に切断を知らせる必要がある。この時 LOST\_CHILD というメッセージで Node の切断を検知・木の再構成を行う。LOST\_CHILD の検出方法には MulticastQueue を使用している(一定期間 MulticastQueue から画像データが取得されない場合、 MemoryOverFlow を回避するために Timeout スレッドが用意されており、これを検知した場合 Node の接続が切れたと判断する)。

\section{ZRLEE}



\section{ShereScreen}
従来の VNC では、配信者が切り替わるたびに VNC の再起動、サーバー、クライアント間の再接続を行う必要がある。TreeVNC では、画面上にある ShareScreen ボタンを押すことで配信者の切り替えを実行できるように設定し、この問題に対処している。

ShareScreen 実行後、Root Node に対し SERVER\_CHANGE\_REQUEST というメッセージが送信される。このメッセージには ShereScreen ボタンを押した Node の番号やディスプレイの情報が付加されている。メッセージを受け取った Root Node は配信を希望している Node の VNC サーバーと通信を行い、切り替え作業に入る。