\documentclass[a4j,12pt]{jreport}
\usepackage[dvips]{graphicx}
\usepackage{mythesis}
\usepackage{multirow}
\usepackage{here}
\usepackage{listings, jlisting}
\lstset{%
  language={java},%使用言語
  basicstyle={\small},%書体
  commentstyle={\small\itshape},%コメントの書体
  keywordstyle={\small\bfseries},%キーワードの書体
  %identifierstyle={\small},%
  %ndkeywordstyle={\small},%
  stringstyle={\small},%文字列の書体
  frame={trlb},%外枠
  breaklines=true,%改行
  columns=[l]{fullflexible},%
  xrightmargin=0zw,%
  xleftmargin=3zw,%
  numbers=left,%行番号の表示
  numberstyle={\scriptsize},%行番号の書体
  numbersep=1zw,%
  stepnumber=1,
  lineskip=-0.5ex,%
  captionpos=b,%キャプションの位置
  moredelim=**[s][\color{red}]{\"compressed}{\"},
}
\renewcommand{\lstlistingname}{Code}

\setlength{\itemsep}{-1zh}
\title{PC画面配信システムTreeVNCの NAT への対応}
\icon{
	\includegraphics[width=80mm,bb=0 0 595 842]{fig/ryukyu.pdf}
}
\year{平成27年度 卒業論文}
\belongto{琉球大学工学部情報工学科}
\author{125716B 伊波 立樹 \\ 指導教員 {河野 真治} }

%% TreeVNC のNATへの対応
%% マルチスクリーン TreeVNC
%% プリアンブルに記述
%% Figure 環境中で Table 環境の見出しを表示・カウンタの操作に必要
%%
\makeatletter
\newcommand{\figcaption}[1]{\def\@captype{figure}\caption{#1}}
\newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}}
\makeatother
\setlength\abovecaptionskip{0pt}

\begin{document}

% タイトル
\maketitle
\baselineskip 17pt plus 1pt minus 1pt

\pagenumbering{roman}
\setcounter{page}{0}

\tableofcontents	% 目次
\listoffigures		% 図目次
\listoftables		% 表目次

%以下のように、章ごとに個別の tex ファイルを作成して、
% main.tex をコンパイルして確認する。
%章分けは個人で違うので下のフォーマットを参考にして下さい。

% はじめに

\chapter{画面共有を利用したコミュニケーション}
\label{chap:introduction}
\pagenumbering{arabic}

%序論の目安としては1枚半ぐらい．
%英語発表者は，最終予稿の「はじめに」の英訳などを載せてもいいかも．


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

\section{VNC}
VNC(Virtual Network Computing) は、 RFBプロトコルを用いて遠隔操作を行うリモートデスクトップソフトウェアである。
VNC はサーバー側とクライアント(ビューア)側に分かれている。 サーバを起動し、クライアントがサーバに接続を行い遠隔操作を可能とする。

\section{RFB プロトコル}
RFB(remote frame buffer)プロトコル\cite{rfbProtocol}とは、自身の画面を送信し、ネットワーク越しに他者の画面に表示するプロトコルである。
ユーザが居る側をRFBクライアント側と呼び、Framebufferへの更新が行われる側はRFBサーバと呼ぶ。
Framebufferとは、メモリ上に置かれた画像データのことである。
RFBプロトコルでは、最初にプロトコルバージョンの確認や認証が行われる。
その後、クライアントに向けてFramebufferの大きさやデスクトップに付けられた名前などが含まれている初期メッセージが送信される。
RFBサーバ側はFramebufferの更新が行われるたびに、RFBクライアントに対してFramebufferの変更部分だけを送信する。
更にRFBクライアントのFramebufferUpdateRequestが来るとそれに答え返信する。
RFBプロトコルは、描画データに使われるエンコードが多数用意されており、また独自のエンコードを実装することもできるプロトコルである。

\section{多人数で VNC を使用する際の問題}
VNCを使用すればクライアント側にサーバー側の画面を表示することが可能である。 
しかし、多人数のクライアントが1つのサーバーに接続してしまうと処理性能が落ちてしまうという問題点がある。

また、 ゼミ等の発表で画面配信者が頻繁に切り替わる場合、
配信者が替わる度にアプリケーションを終了し、接続をし直さないといけないという問題がある。

\section{TreeVNC の構造}
TreeVNC は Java を用いて作成された TightVNC(Tight Virtual Network Computing)\cite{tightvnc} を元に作成されている。

TreeVNC は クライアント同士を接続させ、画面描画のデータを受け取ったクライアントが次のクライアントにデータを流す方式を取っている。
また、サーバへ接続しに来たクライアントをバイナリツリー状に接続する(図\ref{fig:tree})。
バイナリツリー状に接続することで、$N$台のクライアントが接続しに来た場合、画面配信の画像データをコピーする回数は従来の VNC ではサーバ側で$N$回する必要があるが、TreeVNCでは各ノードが2回ずつコピーするだけで済む。 

TreeVNCで通信される画像のデータ量は大きいため、大きなネットワークスループットが必要である。
そのため、有線接続が必須である。

バイナリツリーのルートのノードを Root Node と呼び、 Root Node に接続されるノードを Node と呼ぶ
Root Node は子 Nodeにデータを流す機能に加え、各 Node の管理、 VNC サーバーから流れてきた画像データの管理を行う。 
Node は 親 Node から送られたデータを 自分の子 Node に流す機能、 逆に子 Node から送られてきたデータを 親 Node に流す機能がある。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=70mm]{./pic/TreeVNC.pdf}
    \end{center}
    \caption{構成される木構造}
    \label{fig:tree}
\end{figure}

\section{圧縮形式}
TreeVNC は ZRLEE\cite{taninari:2012a} というエンコードでデータのやり取りを行う。
ZRLEE はRFB プロトコルで使えるエンコーディングタイプの ZRLE を元に生成される。

ZRLE は Zlib\cite{zlib} で圧縮されたデータとそのデータのバイト数がヘッダーとして付けて送られてくる。
Zlib は java.util.zip.deflater と java.util.zip.inflater で圧縮と解凍が行える。

しかし、 java.util.zip.deflater は解凍に必要な辞書を書き出す(flush)ことが出来ない。
辞書を書き出すことが出来ないため、 Zlib圧縮されたデータを途中から受け取ってもデータを正しく解凍することが出来ない。

そこで ZRLEE は 一度 Root Node で受け取った ZRLE のデータを unzip し、 データをzip し直して最後に finish() をいれることで初めからデータを呼んでいなくても解凍を行えるようにした。

一度 ZRLEE に変換してしまえば子 Node はそのデータをそのまま流すだけで良い。
ただし、deflater と inflater では前回までの通信で得た辞書をクリアしないといけないため、 Root Node と Node 側では毎回新しく作る必要がある。

\section{通信経路}
TreeVNC の通信経路として以下が挙げられる
\begin{itemize}
    \item ある Node から Root Node に直接通信を行う send direct message (Node to Root)
    \item Root Node からある Node に直接通信を行う send direct message (Root to Node)
    \item Root Node から木の末端の Node までのすべての Nodeに通信を行う messeage 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{ノード間で行われるメッセージ通信}
RFBプロトコルで提供されているメッセージに加え、 TreeVNC 独自のメッセージを使用している。
TreeVNC で使用されるメッセージの一覧を表\ref{tb:message}に示す。

\begin{table*}[htb]
    \caption{通信経路とメッセージ一覧}
    \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                    & 右子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:message}
\end{table}

図\ref{fig:message}は TreeVNC で Node が Root Node に接続し、画像データを受信するまでのメッセージ通信の様子である。
図\ref{fig:message}の手順として

\begin{itemize}
    \item 接続を行う Node (以下 Client Node)はMulticast通信で Root Node に対してFIND\_ROOTを送信する(1:findRoot())
    \item Root NodeがFIND\_ROOTを受信し、FIND\_ROOT\_REPLYを送信する(2:findRootReplay())
    \item Client Node 側で、どのRoot Nodeに接続するかを選択するパネルが表示される
    \item Client Node はパネルで接続するRoot Nodeを選択し、Rootに対して接続先を要求するWHERE\_TO\_CONNECTを送信する(3:whereToConnect())
    \item 受信した Root Node は Client Node の接続先をCONNECT\_TOで送信する(4:connectTo)
    \item Client Node は Root の指定した接続先に接続しに行く
    \item Root Node, Client Node間の接続が確立後、Root Node から Clinet Node に対して定期的に画像データFRAME\_BUFFER\_UPDATEを送信する(5:framebufferUpdate())
\end{itemize}

を行っている。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=65mm]{./pic/message.pdf}
    \end{center}
    \caption{node 間で行われるメッセージ通信}
    \label{fig:message}
\end{figure}

\section{MulticastQueue}
画用データの送信は MulticastQueue という Queue で行っている。
MulticastQueue は java.util.concurrent.CountDownLatch を用いて実装されている。


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

TreeVNC の木構造のネットワークトポロジーは Root Node が持っている nodeList というリストで管理している。
つまり、Node の接続が切れた場合、木の再構成を行うため Root Node に知らせなければならない。

TreeVNC は Lost\_CHILD というメッセージ通信で Node の切断を検知・木の再構成を行っている。

TreeVNC は VNC サーバーから送られる画像データ(FRAME\_BUFFER\_Update)を MulticastQueue というキューに蓄積しており、
Node はこのキューから画像データを取得し、画面を描画している。
Lost\_Child の検出方法はこの MulticastQueue を使用している。
ある一定時間 MulticastQueue から画像データが取得されない場合 Memory Over Flow を回避するために Timeout スレッドが用意されている。
Timeout を検知した際、Node との接続が切れたと判断する。

LOST\_CHILD の検知・木の再構成を以下に示す。
\begin{itemize}
    \item 子 Node の切断を検知した Node が Root Node へ LOST\_CHILD メッセージを送信する(図\ref{fig:lostchild1}中, 1:lostChild())
    \item LOST\_CHILD メッセージを受け取った Root Node は nodeList の更新を行う(図\ref{fig:lostchild1}中, 2:updateNodeList())
    \item 切断した Node を nodeList から消し、nodeList の最後尾の Node に切断した node number を割り当てる
    \item Root Node は最後尾の Node に、切断した子 Node が接続していた親 Node に接続する様に CONNECT\_TO メッセージを送信する(図\ref{fig:lostchild1}中, 3:connectTo(1))
    \item 最後尾の Node が子 Node を失った親 Node へ接続しに行く(図\ref{fig:lostchild1}中, 4:connectToParent(1))
\end{itemize}

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=70mm]{./pic/lostChild1.pdf}
    \end{center}
    \caption{LOST\_CHILD を検知・再接続}
    \label{fig:lostchild1}
\end{figure}

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

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

画面の共有にプロジェクタを使用する場合、 発表者が変わる度にケーブルの抜き差しを行う必要がある。
その際に、ディスプレイ解像度を設定し直す必要が出たり、 接続不良が起こる等の煩わしい問題が生じることがある。

従来のVNCを使用する場合、 画面の切り替えの度に一旦VNCを終了し、発表者の VNC サーバーへと再接続を行う必要がある。

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

TreeVNC の Root Node は配信者の VNC サーバーと通信を行っている。
VNC サーバーから画面データを受信し、そのデータを 子 Node へと送信している。
配信者切り替え時に Share Screen ボタンが押されると、
Root Node は Share Screen ボタン を押したクライアントの VNC サーバーと通信を始める。
そのためTreeVNCは配信者切り替えの度に VNC を終了し、再接続する必要がない。

\section{複数のネットワークの対応}
従来の TreeVNC は、クライアントの接続する木構造が単一であった。
そのため、Root Node が複数のネットワークに接続していても、 単一のネットワークでしか使用することができなかった。

この問題を解決するために、 図\ref{fig:multinetworktree}の様に、ネットワーク別に 木構造を形成するように設計した。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=70mm]{./pic/MultiNetworkTree.pdf}
    \end{center}
    \caption{Multi Network Tree}
    \label{fig:multinetworktree}
\end{figure}

TreeVNC は Root Node が TreeManager というオブジェクトを持っている。
TreeManager は TreeVNC の接続部分を管理している。
TreeManager では木構造を管理する nodeList が生成される。
この nodeList を元に、新しい Node の接続や、切断検出時の接続の切り替え等を行う。

Root Node の保持しているネットワーク毎にTreeManager を生成する用に変更を行った。
新しい Node が接続してきた際、 interfaces から Node のネットワークと一致する TreeManager を取得し、 Node 接続の処理を任せる。
そのため、 TreeVNC が複数のネットワーク別に木構造を構成することが可能となる。

% 実験
\chapter{TreeVNC の追加機能}
\section{マルチディスプレイ対応}
画面配信側のPCがマルチディスプレイの場合、
VNC サーバーからは複数の画面全体の画像データが送信されてしまう。

授業やゼミ等でTreeVNCを使用する場合、複数画面の表示は必要ない。
そこで、画面を共有する際、ディスプレイを選択させ、画面共有を行う機能を追加した。

ディスプレイの情報は個々のクライアントでしか取得ができない。
そのため、配信側は画面の切替を行う際に、ディスプレイを選択し、そのディスプレイの左上と右下の座標を取得する。
その座標を Root Node への画面切り替えを要求する SERVER\_CHANGE\_REQUEST メッセージに付加させる。 
Root Node は 配信側の VNC サーバー に画像データを要求する FRAMEBUFFER\_UPDATE\_REPLY メッセージに送信された座標を付加する。 
VNC サーバーは要求された座標内の画像データを FRAMEBUFFER\_UPDATE メッセージで Root Node に送信する。 
これにより、一画面のみの表示が可能となる。

図\ref{fig:multidisplay} は Display1 のみを画面共有する例を示している。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=70mm]{./pic/shareScreenToMultiDisplay.pdf}
    \end{center}
    \caption{マルチディスプレイへの対応}
    \label{fig:multidisplay}
\end{figure}

\section{NAT越え}
遠隔地からでもゼミや授業に参加できるよう、 NATを越えたネットワークから TreeVNC への接続を可能にした。

図\ref{fig:directConnection} にNATを越えたネットワークからの接続を示す。
別ネットワークからTreeVNCに参加する際、 直接配信側のネットワークの Root Node に接続を行う。
この接続を Direct Connection と呼ぶ。

Direct Connection した Node はそのネットワークの Root Node になる。 
そのネットワークの他の Node はそのネットワークの Root Node に接続し、木構造を生成する。

配信側の Root Node は Direct Connection で接続された Root Node に対して Framebuffer Update で 画像データを送信する。
Framebuffer Update が送信された Root Node は そのネットワークの Node に対して Framebuffer Update を送信する。

これにより、NATを越えたネットワークの画面共有が可能となる。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=80mm]{./pic/directConnection.pdf}
        \caption{遠隔地 Node からの接続}
        \label{fig:directConnection}
    \end{center}
\end{figure}

\section{ネックになっているノードへの対処}
\section{別 Thread での画面切り替え}

\chapter{TreeVNC の評価}
\section{画像データ伝達の遅延}
VNC サーバー から受信する画像データ、 TreeVNC で扱われるメッセージ通信は構成された木を伝って伝達される。
接続する人数が増える毎に木の段数は増えていく。 そこで Root Node から木の末端の Node までの画像データ伝達の遅延を検証する実験を行った。

\section{実験環境}
授業を受講している学生が TreeVNC を使用した状態で実験を行った。
TreeVNC には最大で17名が接続していた。

\section{メッセージを使用した実測}
TreeVNC を伝搬するメッセージに、CHECK\_DELAY,CHECK\_DELAY\_REPLYを追加した。
CHECK\_DELAY は Root Node から 末端の Node まで伝達するメッセージと画像データ、
CHECK\_DELAY\_REPLY は各 Node から Root Node まで伝達するメッセージである。

CHECK\_DELAY メッセージは送信時刻を付けて送信する。
Root Nodeから CHECK\_DELAY 送信し、末端の Node まで各 Node を伝いながら伝達して行く。

CHECK\_DELAY\_REPLY は CHECK\_DELAY から受け取った送信時刻をそのままに、 画像データのサイズを付けて送信する。
CHECK\_DELAY を受け取った各 Node は CHECK\_DELAY\_REPLY を接続している親 Node に送信する。

CHECK\_DELAY\_REPLY を受け取った Root Node はメッセージと画像データの伝達にどれだけの時間がかかったかを計算する。
データ計算方法を以下の Code \ref{calc}に記述する。 この変数 time は CHECK\_DELAY\_REPLY に付いている CHEKC\_DELAY の送信時刻である。

\begin{table}[htb]

    \begin{lstlisting}[label=calc, caption=遅延時間の計算方法]
    Long delay = System.currentTimeMillis() - time;
    \end{lstlisting}
\end{table}


\section{結果}
バイナリツリーで木を構成した場合、 Node 数が17台だと深さが4となる。
各木構造の階層毎に、画像データの伝搬にかかった時間を測定した。

図\ref{fig:depth}は遅延の分布を示した散布図である。
X軸はメッセージ伝達にかかった秒数(ms)、 Y軸は画像データのサイズ(Byte)である。

画像データの伝達はほぼ1秒以内に収まっているが、容量が小さい場合でも時間がかかる場合がある。
それはその送信の前に大容量の画像を送信した後の回線のDelayが残っているためだと考えられる。

また、深さ3で極端に遅い場合がある。 遅い原因として、1つの Node がボトルネックになっていることが判明している。
このような極端に遅い Node をそのまま木に配置した場合、その Node の子 Node 以下に影響を及ぼす場合がある。
そのため、遅い Nodeを検出して、木の最後尾に移動させる機能が必要である。

今回4段分のデータでは30名程度の遅延のみしか判断することができないため、更に大人数での実験を繰り返し行う必要がある。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=60mm]{./pic/depth1.eps}
    \end{center}
    \begin{center}
        \includegraphics[width=60mm]{./pic/depth2.eps}
    \end{center}
    \begin{center}
        \includegraphics[width=60mm]{./pic/depth3.eps}
    \end{center}
    \begin{center}
        \includegraphics[width=60mm]{./pic/depth4.eps}
    \end{center}
    \caption{深さ毎のデータサイズと遅延の関係(上から深さ1, 2, 3, 4)}
    \label{fig:depth}
\end{figure}
% 今後の課題

\chapter{まとめ}
\section{NATを越えた画面切り替え}
\section{新機能の評価}

% 参考文献
\def\line{−\hspace*{-.7zw}−}

\begin{thebibliography}{99}
        %\bibitem{*}内の * は各自わかりやすい名前などをつけて、
        %論文中には \cite{*} のように使用する。
        %これをベースに書き換えた方が楽かも。
        %書籍、論文、URLによって若干書き方が異なる。
        %URLを載せる人は参考にした年月日を最後に記入すること。

    \bibitem{hoge}
        hoge
\end{thebibliography}

% 謝辞

\chapter*{謝辞}
\thispagestyle{empty}

%基本的な内容は以下の通り．参考にしてみて下さい．
%厳密な決まりは無いので，個々人の文体でも構わない．
%GISゼミや英語ゼミに参加した人はその分も入れておく．
%順番は重要なので気を付けるように．(提出前に周りの人に確認してもらう．)

\hspace{1zw}本研究の遂行，また本論文の作成にあたり、御多忙にも関わらず終始懇切なる御指導と御教授を賜わりましたhoge助教授に深く感謝したします。

また、本研究の遂行及び本論文の作成にあたり、日頃より終始懇切なる御教授と御指導を賜わりましたhoge教授に心より深く感謝致します。

数々の貴重な御助言と細かな御配慮を戴いたhoge研究室のhoge氏に深く感謝致します。

また一年間共に研究を行い、暖かな気遣いと励ましをもって支えてくれたhoge研究室のhoge君、hoge君、hogeさん並びにhoge研究室のhoge、hoge君、hoge君、hoge君、hoge君に感謝致します。

最後に、有意義な時間を共に過ごした情報工学科の学友、並びに物心両面で支えてくれた両親に深く感謝致します。

\begin{flushright}
    2010年 3月 \\ hoge
\end{flushright}

% 付録

\end{document}