% withpage: ページ番号をつける (著者確認用)
\documentclass[techrep, ,dvipdfmx]{ipsjprosym}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\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}
\input{dummy.tex} %% Font 

\begin{document}

% ユーザー定義したマクロなど
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)} 
\def\>{\(\rangle\)} 
%\def\|{\verb|} 
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline} 
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\} 
\def\LATEX{\iLATEX\Large} 
\def\LATEx{\iLATEX\normalsize} 
\def\LATex{\iLATEX\small} 
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em 
\   T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX} 
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi} 
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi} 
\def\Quote{\list{}{}\item[]} 
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
    $\backslash$#1\fi}

% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{有線上のPC画面配信システムTreeVNCの改良}

\affiliate{IE}{琉球大学工学部情報工学科}

\author{伊波 立樹}{Tatsuki IHA}{IE}
\author{河野 真治}{Shinji KONO}{IE}

\begin{abstract}
    ゼミや授業等で、それぞれがPC端末を持っている場合では、PCの機能を活かしたコミュニケーションが可能である。教員が操作する画面をそのまま学生に配信したり, ゼミなどで、発表する学生の画面を切り替えたりすることを可能にしたい。
    TreeVNCは参加したクライアントをバイナリツリー状に接続し、配信コストを分散させる仕組みを取っている。そのため,多人数が参加しても処理性能が下がらない。また、ツリーのRootが見ているVNCサーバーを変更することで、ケーブルの差し替えなしに画面の切替が可能となる。
    今研究ではTreeVNCの改良として、WANへの対応、 マルチディスプレイへの対応を行う。
\end{abstract}

\begin{jkeyword}
\end{jkeyword}

\maketitle

% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{研究背景と目的}
ゼミや授業等で、それぞれがPC端末を持っている場合では、
PCの機能を活かしたコミュニケーションが可能である。
教員が操作する画面をそのまま学生に配信したり、
ゼミなどで、発表する学生の画面を切り替えたりすることを可能にしたい。

TreeVNC画面配信システムは、
参加したクライアントをバイナリツリー状に接続し、
配信コストをクライアントにバランスさせる仕組みになっている。
なので、多人数が参加しても処理性能が下がらない。
また、RFBプロトコルを用いているので、ケーブルの差し替えなしに
共有している画面の切り替えが可能になっている。

今研究では、 WAN、 マルチディスプレイへの対応を行った。
WANへの対応として、新しい接続方法を提案し、実装を行った。
また、マルチディスプレイへの対応としては配信する際に、配信するディスプレイ情報を取得し、配信を行うことで、対応した。

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

\subsection*{[TightVNC]}
TightVNC(Tight Virtual Network Computing)\cite{tightvnc}はJavaを用いて作成されたRFBプロトコルのクライアントである。
本研究で作成したTreeVNCはTightVNCを元に作成されている。

\subsection*{[多人数で VNC を使用する時の問題点]}
多人数で従来の VNC を使用する際、1つのコンピュータに多人数が同時につながり、
処理が集中してしまい、性能が大幅に落ちてしまうという問題が生じる。

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

\subsection*{[TreeVNC の構造]}
多人数で VNC を用いるために、クライアントの接続がサーバに一極集中してしまう問題を解決する。
そのために、 TreeVNC はサーバへ接続しに来たクライアントをバイナリツリー状に接続する(図\ref{fig:tree})。
バイナリツリーなら、各nodeに最大2台分のクライアントしか接続されない。
$N$台のクライアントが接続しに来た場合、画面配信の画像データをコピーする回数は、
従来の VNC ではサーバ側で$N$回する必要があるが、TreeVNCでは各 node が2回ずつコピーするだけで済む。
TreeVNC は、root への負荷を各 node に分散することにより、処理性能が向上している。

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

\subsection*{[Multicast や Broadcast を用いたVNC]}
Multicast とは、
同一ネットワーク内でマルチキャストアドレスを持っている端末に対してデータを送信することである。
Broadcast とは、
同一ネットワーク上の全ての端末に対してデータを送信することである。
どちらの通信方法も、root からのデータ送信は1回でよく、
1度データの送信を行うとデータの複製はルータが行う。

VNC を Multicast や Broadcast の通信方法を用いて実装すると、
画像データの送信が1度で済むため、負荷分散のために木構造を形成する必要もなくなる。

しかし、これらの通信方法でのパケットの扱いには
\begin{itemize}
    \item 送信可能なパケットのブロックサイズが 64000byte までであると決まっている
    \item パケットが途中で消失してしまっても特定することができない
\end{itemize}
といった性質がある。


VNC でこれらの通信方法を用いて実装する場合、
パケットの扱いの性質を乗り越えなければならない。

送信可能なパケットのサイズが決まっているので、
画面データは 64000byte 以下に分割し送信しなければならない。
しかし、現在の TreeVNC で用いている方法では、
データ分割の処理には時間がかかってしまう。

パケットの消失を検知するために、
各パケットに対してシリアル番号を振り分ける。
パケットを受信した node 側で、
シリアル番号が連番で届いているのかどうかを調べれば、消失を検知することが可能である。
もしパケットが届いていなかった場合は、root に対して再送要求を送信すれば良い。
しかし、Multicast や Broadcast 通信ではパケットロス率が高かった。

これらの通信方法を用いての VNC の実装にはもう更なる工夫が必要である。



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


\begin{table}[h!]
  \large
  \scalebox{0.4} {
  \begin{tabular}{|l|l|l|} \hline
    通信経路            & message                    & 説明 \\ \hline \hline
                        & FIND\_ROOT                 & TreeVNC接続時にrootを探す。 \\ \cline{2-3}
    send direct message & WHERE\_TO\_CONNECT         & 接続先をrootに聞く。 \\ \cline{2-3}
    (child to root)     & LOST\_CHILD                & 子nodeの切断をrootに知らせる。 \\ \hline \hline

                        & FIND\_ROOT\_REPLY          & FIND\_ROOTへの返信。 \\ \cline{2-3}
    send direct message & CONNECT\_TO\_AS\_LEADER    & 左子nodeとして接続する。接続先のnodeが含まれている。 \\ \cline{2-3}
    (root to child)     & CONNECT                    & 右子nodeとして接続する。接続先のnodeが含まれている。 \\ \hline \hline

    message down tree   & FRAMEBUFFER\_UPDATE        & 画像データ。EncodingTypeを持っている。\\ \cline{2-3}
    (root to child)     & CHECK\_DELAY               & 通信の遅延を測定する。 \\ \hline \hline

    message up tree     & CHECK\_DELAY\_REPLY        & CHECK\_DELAYへの返信。 \\ \cline{2-3}
    (child 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}


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

手順として

\begin{itemize}
    \item nodeはMulticast通信でrootに対してFIND\_ROOTを送信する(1:findRoot())
    \item rootがFIND\_ROOTを受信し、FIND\_ROOT\_REPLYを送信する(2:findRootReplay())
    \item node側で、どのrootに接続するかを選択するパネルが表示される
    \item nodeはパネルで接続するrootを選択し、rootに対して接続先を要求するWHERE\_TO\_CONNECTを送信する(3:whereToConnect())
    \item 受信したrootはnodeの接続先をCONNECT\_TOで送信する(4:connectTo)
    \item nodeはrootの指定した接続先に接続しに行く
    \item root・node間の接続が確立後、rootから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}


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

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

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

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

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

しかし、配信者と受信者の画面サイズの違いや、
マルチディスプレイ全体を共有してしまう問題があるので、
それらを解決する必要がある。


\subsection*{[MulticastQueue]}
配信側の画面が更新されると、 VNCServer から画像データが FRAME\_BUFFER\_UPDATE messageとして送られてくる。
TreeVNC は、画像の更新を複数の node に同時に伝えるため、
MulticastQueue という Queue に画像データを格納する。

各 node は MulticastQueue からデータを取得するスレッドを持つ。
MulticastQueue は複数のスレッドから使用される。

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

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

親node は、接続している全ての子nodeが画像データを取得するまで
MulticastQueueの中に持っている画像データを削除することができない。
node が MulticastQueue からデータを取得せずに、
Queue にデータが溜まり続けると、Memory Over Flowを起こしてしまう。
この問題を避けるために、Timeout用のスレッドを用意している。
Timeout スレッドは、ある一定時間取得されない画像データがある場合、
そのデータを node の代わりにpollするという仕組みである。
Timeout スレッドにより、Memory Over Flowを防ぐことができる。

\section{QUALITYモードとSPEEDモード}
高解像度のまま拡大・縮小の処理を行うと、
PC のスペックによっては描画処理に時間がかかってしまうことがある。
配信者の画面をリアルタイムに取得するため、
描画処理に時間のかからないモードを追加する。

画像描画処理には、
高画質優先の QUALITY モードと描画速度優先の SPEED モードがある。
今まで TreeVNC は QUALITY モードで使用していた。

今回、どちらのモードを使用するかを Viewer から変更出来るようにした。
これにより、描画処理の遅延を解決することができた。

\section{マルチディスプレイ対応}
画面配信側のPCがマルチディスプレイの場合、
VNCServer からは複数の画面全体の画像データが送信されてしまう。

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

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

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

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


\section{無線LANへの対応}
授業でTreeVNCを使用する場合、
有線を使用するか否かは学生によって違う。
TreeVNCを有線・無線の両方からの接続に対応したい。

従来の TreeVNC は、クライアントの接続する木構造が単一であった。
そのため、単一のネットワークインターフェースでしか使用することができなかった。

この問題を解決するために、
図\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 が TreeManager というオブジェクトを持っている。
TreeManager は TreeVNC の接続部分を管理している。
TreeManager では木構造を管理する nodeList が生成される。
この nodeList を元に、新しい node の接続や、node の切断検出時の接続の切り替え等を行う。

root の保持しているネットワークインタフェース毎に
TreeManager を生成する様に変更した。
ソースコード\ref{createtreemanager}に、nodeList を生成する部分を示す。

\begin{table}[htb]
    \lstinputlisting[label=createtreemanager, caption=TreeManager の生成]{source/GetNetworkInterfaces.java}
\end{table}

\begin{itemize}
    \item for 文を使用し root が所持しているネットワークインタフェースを取得する(2行目)
    \item その中から、起動しており Multicast に対応しており、また、ループバックインタフェースでないネットワークインタフェースを取得する(4行目)
    \item 取得してきたネットワークインタフェースの、ネットマスク、ホストネームを取得する(6,7行目)
    \item TreeManager を生成する(8行目)
    \item TreeManager にネットマスクとネットアドレスを追加する(14行目)
    \item HashMap である interfaces に ネットワークインタフェースと対応する TreeManager を追加する(15行目)
\end{itemize}

新しい node が接続してきた際、
interfaces から node のネットワークインタフェースと一致する TreeManager を取得する。
その TreeManager に、node 接続の処理を任せる。

こうすることによって、TreeVNC を複数のネットワークインターフェース別に
木構造を構成することができる。


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

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

Direct Connection した node はそのネットワークの root になり、node はそのネットワークの root に接続し、木を生成する。

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

これにより、別ネットワークでの画面共有が可能となる。

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


\section{評価}
\subsection*{[木の深さによるメッセージ伝達の遅延]}
VNCServer から受信する画像データ、
TreeVNC で扱われるメッセージ通信は構成された木を伝って伝達される。
接続する人数が増える毎に木の段数は増えていく。
そこで root から木の末端の node まで、
メッセージが遅延することなく伝達できているかを検証する実験を行った。


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

\subsection*{[メッセージを使用した実測]}
TreeVNC を伝搬するメッセージに、CHECK\_DELAY・CHECK\_DELAY\_REPLY を追加した。
CHECK\_DELAY は root から node の末端まで伝達するメッセージ(図\ref{fig:checkdelay}, 左)、
CHECK\_DELAY\_REPLY は各 node から root まで伝達するメッセージ(図\ref{fig:checkdelay}, 右)である。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=70mm]{./pic/checkDelay.pdf}
    \end{center}
    \caption{CHECH\_DELAY, CHECK\_DELAY\_REPLY}
    \label{fig:checkdelay}
\end{figure}

CHECK\_DELAY message は、送信時刻を付けて送信する。
root から CHECK\_DELAY 送信し、
末端 node まで各 node を伝いながら伝達して行く。

CHECK\_DELAY\_REPLY には、CHECK\_DELAY から受け取った送信時刻をそのまま付つけて送信する。
CHECK\_DELAY を受け取った各 node は、
CHECK\_DELAY\_REPLY を接続している親 node に送信する。

CHECK\_DELAY\_REPLY を受け取った root は、
メッセージの伝達にどれだけの時間がかかったかを計算する。

計算方法を以下のソースコード\ref{calc}に記述する。
各 node にデータを下ろす際も、root にデータが上る際も、
木を伝い受け渡されている。
なので、データが root から末端 node に伝わる時間は、
CHECK\_DELAY を送信した時間と、
CHECK\_DELAY\_REPLY を受信した時間の半分であるといえる。

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


\subsection*{[depth毎の遅延結果]}
バイナリツリーで木を構成した場合、
node 数が34台だと深さが5となる。
各木構造の階層毎に、メッセージの伝搬にかかった時間を測定した。

図\ref{fig:test}は遅延の分布を示したヒストグラムである。
X軸はメッセージ伝達にかかった秒数(ms)、
Y軸は CHECK\_DELAY\_REPLY を送信した node の割合を表している。

ほとんどのメッセージの伝達は 0.0 〜 4.0 ミリ秒内に収まっている。
木の段数毎に、メッセージ伝達速度の差が生じている。
深い段数の node ほど、メッセージ伝達速度が落ちている。

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{./pic/test.pdf}
    \end{center}
    \caption{遅延の分布}
    \label{fig:test}
\end{figure}

\section{まとめ}
本研究では画面配信システムTreeVNCをマルチディスプレイ、WAN に対応させた。

マルチディスプレイに対応したことで、 配信者が配信したいディスプレイを選択し、画面配信することが可能となった。

WANに対応することで別ネットワークにいるユーザーが TreeVNC に参加することが可能となった。

今後の課題として、画面切り替えの安定化、 ユーザビリティの向上、 共有機能の追加を行う。

現在のTreeVNCでは、share button を押すと、その時配信されている画面から、自動的に画面が切り替わってしまうという問題がある。
それを防ぐために share button が押されるとその時の配信者に切り替え確認を行う処理を追加する。

また、今回追加した Direct Connection などの一部の機能はコマンドラインオプションで指定する必要があるため、一般ユーザーでは操作するのが困難である。
そこで、 今までコマンドラインオプションで指定していた機能を Viewer で操作するように変更を行う。

共有機能の追加としては、音声、質問・意見 等が上げられる。
\nocite{*}
\bibliographystyle{ipsjunsrt}
\bibliography{prosym}

\end{document}