%%
%% 研究報告用スイッチ
%% [techrep]
%%
%% 欧文表記無しのスイッチ(etitle,eabstractは任意)
%% [noauthor]
%%

%\documentclass[submit,techrep]{ipsj}
\documentclass[submit,techrep,noauthor]{ipsj}



%\usepackage[dvips]{graphicx}
\usepackage[dvipdfmx]{graphicx}
\usepackage{latexsym}
\usepackage{url}


\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\|{\verb|}
%

%\setcounter{巻数}{59}%vol59=2018
%\setcounter{号数}{10}
%\setcounter{page}{1}


\begin{document}


\title{画像配信システム TreeVNC のマルチキャストの導入}

\etitle{}

%\affiliate{IPSJ}{情報処理学会\\
%IPSJ, Chiyoda, Tokyo 101--0062, Japan}


\paffiliate{IEUR}{琉球大学工学部情報工学科\\
Information Engineering, University of the Ryukyus.}

\author{安田 亮}{Ryo Yasuda}{IEUR}[riono210@cr.ie.u-ryukyu.ac.jp]
\author{大城 由也}{Yuya Oshiro}{}
\author{河野 真治}{Shinji Kono}{IEUR}[kono@ie.u-ryukyu.ac.jp]

\begin{abstract}
 TreeVNCとは当研究室で開発している画面配信システムである。しかし、画面共有は送信するデータ量が多いため、無線 LAN 接続の場合、画面の配信に遅延が生じてしまう。そこで、multicast でのデータ通信の実装やデータの分割・圧縮方法の評価を行い、TreeVNC のmulticastの有用性を評価する。
\end{abstract}



\maketitle

\section{画面配信ソフトウェア TreeVNCの活用}
現代の講義や発表、プレゼンなどではPC画面で用意した資料を見ながら進行することが多い。ゼミでは発表者のPC画面を切り替えを行いながら発表を行う場合もある。通常このような場面では資料やスライドを表示するためにプロジェクタが利用される。その際、発表者のPC画面を切り替えるたびにケーブルを差し替える必要がある。発表者のPCによっては接続するアダプターの種類や解像度の設定により、正常にPC画面を表示できない場合がある。また、参加者もプロジェクタに集中を割く必要があり、手元のPCと相互に参照する場合、負担になる場合がある。

当研究室で開発している画面配信システムTreeVNC\cite{taninari:2011a}は、発表者の画面を参加者のPCに表示するソフトウェアである。そのため、参加者は不自由なく手元のPCを操作しながら講義を受けることが可能になる。更に発表者の切り替えの際もケーブルを差し替えずに、共有する画面の切り替えが可能になっている。

\begin{figure}[htb]　%PDF
\begin{center}
    \includegraphics[width=8cm]{Image/vnc-crop.pdf}
\caption{従来のVNCの接続方法}
\label{fig:UntilVNC}
\end{center}
\end{figure}

VNC(Virtual Network Computing)は、クライアント(ビューワー)側とサーバ側からなるリモートデスクトップソフトウェアである。遠隔操作にはサーバを起動し、クライアント側がサーバに接続をすることで可能としている。また、動作にはRFBプロトコルを用いている。
TreeVNCはVNC\cite{vnc}を利用した画面配信を行なっている。しかし通常のVNCでは配信側のPCに全ての参加者への配信を行う負荷がかかってしまう。(図\ref{fig:UntilVNC})

RFB(Remote Frame Buffer)プロトコル\cite{rfbprotocol}とは、自身のPC画面をネットワーク上に送信し他人の画面に表示を行うプロトコルである。画面が表示されるユーザ側をRFBクライアントと呼び、画面を送信のためにFramebufferの更新が行われる側をRFBサーバと呼ぶ。Framebufferとは。メモリ上に置かれた画像データのことである。RFBプロトコルでは、最初にプロトコルのバージョン確認や認証が行われる。その後、クライアントへ向けてFramebufferの大きさやデスクトップに付けられた名前などが含まれている初期メッセージを送信する。RFBサーバ側はFramebufferの更新が行われるたびに、RFBクライアントに対してFramebufferの変更部分のみを送信する。更に、RFBクライアントのFramebufferUpdateRequestが来るとそれに答え返信する。変更部分のみを送信する理由は、更新がある度に全画面を送信すると、送信するデータ面と更新にかかる時間面において効率が悪くなるからである。

TreeVNCはサーバに接続してきたクライアントをバイナリツリー状に接続する。接続してきたクライアントをノードとし、その下に新たなノード二つを接続していく。
これにより、人数分のコピーと送信の手間を分散することができる。(図\ref{fig:TreeStructure})。
バイナリツリー状に接続することで、N台のクライアントが接続しにきた場合、従来のVNCではサーバ側がN回のコピーを行なって配信をする必要があるが、TreeVNCでは各ノードが2回ずつコピーをするだけで配信が可能となる。
送信されるデータは従来の方法ではNノードに対してN-1の通信が必要であるが、木構造を用いても通信の数は変わらない。

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

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{Image/treevnc-crop.pdf}
\caption{TreeVNCの接続方法}
\label{fig:TreeStructure}
\end{center}
\end{figure}

\section{TreeVNCの通信プロトコル}

TreeVNCの通信経路として以下の6つが挙げられる。


\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}


\subsection{メッセージ通信}
TreeVNCの各NodeとVNCServer間で通信されるメッセージを表\ref{tb:message}に示す。

\begin{table*}[htbp]
 	\caption{通信経路とメッセージ一覧}
	\scalebox{1}{	
    	\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:message}
\end{table*}
	
\subsection{MulticastQueue}
配信側の画面が更新されるとVNCServerから画像データがFRAME\_BUFFER\_UPDATEメッセージとして送られる。その際、画像データの更新を複数のNodeに同時に伝えるためにMulticast Queueというキューに画像データを格納する。


\subsection{木構造の再構成}
TreeVNCはバイナリツリーでの接続のため、Nodeが切断されたことを検知できないと構成した木構造が崩れてしまい、新しいNodeを適切な場所に接続できなくなってしまう。そこで木構造を崩さないよう、Node同士の接続の再構成を行う必要がある。
TreeVNCの木構造のネットワークトポロジーはRoot Nodeが持っているnodeListで管理している。Nodeの接続が切れた場合、Root Nodeに切断を知らせなければならない。
TreeVNCはLOST\_CHILDというメッセージ通信で、Nodeの切断を検知および木構造の再構成を行なっている。LOST\_CHILDの検出方法にはMulticastQueueを使用しており、ある一定時間MulticastQueueから画像データが取得されない場合、MemoryOverFlowを回避するためにTimeoutスレッドが用意されている。そして、Timeoutを検知した際にNodeとの接続が切れたと判断する。

\subsection{ZRLEE}
TreeVNCでは、ZRLEE\cite{}というエンコード方法でデータの圧縮を行う。ZRLEEはRFBプロトコルで使用できるZRLEというエンコードタイプを元に生成される。
ZRLEはZlib\cite{}で圧縮されたデータとそのデータのバイト数がヘッダーとして送信される。Zlibはjava.util.zip.deflaterとjava.util.zip.inflaterで圧縮と解凍が行える。しかしjava.util.zip.deflaterはデコードに必要な辞書を書き出す(flush)ことが出来ない(図\ref{fig:ZRLE})。従って、圧縮されたデータを途中から受け取るとデータを正しく解凍することが出来ない。
そこでZRLEEは一度Root Nodeで受け取ったZRLEのデータをunzipし、データをupdate rectangleと呼ばれる画面ごとのデータに辞書を付与してzipし直すことで初めからデータを読み込んでいなくても解凍できるようにした(図\ref{fig:ZRLEE})。
辞書をクリアすることによりadaptive compressionを実現していることになり圧縮率はむしろ向上する。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{Image/EncodeZRLEE.pdf}
\caption{Multi Network Tree}
\label{fig:multinetworktree}
\end{center}
\end{figure}

\subsection{ShareScreen}
従来の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サーバと通信を始める。


\subsection{ネットワーク複数時の接続}
TreeVNCはRoot Nodeが複数のネットワークに接続している場合、図\ref{fig:multinetworktree}のようにネットワーク別に木構造を形成する。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{Image/MultiNetworkTree.pdf}
\caption{Multi Network Tree}
\label{fig:multinetworktree}
\end{center}
\end{figure}

TreeVNCはRoot NodeがTreeManagerというオブジェクトを持っている。TreeManagerはTreeVNCの接続部分を管理しており、木構造を管理するnodeListを生成する。このnodeListを元に、新しいNodeの接続や、切断検出時の接続の切り替え等を行う。Tree ManagerはRoot Nodeの保持しているネットワーク毎に生成される。新しいNodeが接続してきた際、interfacesからNodeのネットワークと一致するTree Managerを取得し、Node接続の処理を任せる。


\section{マルチキャストの導入}
\subsection{有線接続との接続形式の違い}
画面配信のデータ量は膨大なため、現在のTreeVNCでVNCServerに無線LAN接続を行なった場合、画面配信の遅延が大きくなってしまう。
この場合でも画面切り替えの機能は有効である。つまり、画面を提供するPCのみを無線経由で接続し、配信を希望する側は有線を
使用することができる。

ここで、Wifi のMulticast の機能を用いて配信側にもWifiを使用することが可能であると考えられる。Tree Root は無線LANに対して、
変更する UpdateRectangle を Multicast で一度だけ送信する。

Wifi のMulticast packet のサイズは 64kbyte が最大となっている。HDや4Kの大きさの画面更新は8Mb * 8byteで圧縮前で64MB程度になる。
これを圧縮しつつ、64kbye 毎のパケットに変換して送る必要がある。

Wifi のMulticast packet は確実に送られること保証されていない。通し番号を付けて欠落を検出することはできるが、再送処理は
複雑であることが予想される。

ここではまずBlocking について考察と実験を行う。

\section{RFBのUpdateRectangle の構成}

RFB のUpdateRectangle は以下の構成になっている。一つのupdateRectangleには複数のRectangleは入っていて、
さらに一つ一つのRectangleの encoding type がある。ここでは ZRLEで encode された rectangle  が一つサーバから送られてくる。
rectangle には zlib で圧縮されたデータが指定された長さだけ付いてくる。このデータは、64x64 の tile にさらに分割されている。
tile 内はパレットとかがある場合があるが、Run length encode されたRGBデータである。

\begin{table}[htbp]
    \caption{updateRectangleの構成}
    \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}
    \label{tb:updateRectangle}
\end{table}

このパケットを64kbyteに収まる三つのRectangleに再構成する。この時に、tile 内部は変更する必要はないが、Rectangleの構成は変わる。
ZRLE を展開しつつ、パケットを構成する必要がある。

zlib はちょうど良い所で圧縮を flush する必要がある。このためには、zlib のAPIを用いて、適当なタイミングで flush を呼ぶ。
この時に1 tileずづ flush してしまうと圧縮率を下げる可能性がある。

64kbyte のpacketの中には複数の tile が存在するが、連続して Rectangle を構成する必要がある。行の途中から始まり、途中で
終わる可能性があるので、三つのRectangleが必要になる。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{Image/FrameUpdateRectangle.pdf}
\caption{Multi Network Tree}
\label{fig:multinetworktree}
\end{center}
\end{figure}


\section{まとめ}

Tree VNC に Wifi 上の Multicast packet を用いる手法について考察した。画面圧縮にHareware supported なMPEG4などを用いることができれば
より効率的な転送が可能であるが、ここでは Java 上で実装できる安易な方法をあえて選択した。Wifi の速度と Multicast の信頼性が高ければ
これでも実用になると可能性がある。

Blocking は実装中であり、再圧縮の時間は前画面の時でも実用的な時間ですむことが予想されている。Wifi 上の Multicast packet の
drop 率は、接続環境に依存すると思われるのでさらなる実験が必要だと思われる。

有線使用時よりも、画面共有の質が落ちるのはある程度はやむを得ないが、再送が必要である場合には、必要なプロトコルを実装する。


\nocite{*}
\bibliographystyle{ipsjunsrt}
\bibliography{riono-sigos}

\end{document}