%%
%% 研究報告用スイッチ
%% [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{Multicast Wifi VNCの実装と評価}

\affiliate{KIE}{琉球大学大学院理工学研究科情報工学専攻}
\affiliate{IE}{琉球大学工学部工学科知能情報コース}

\author{安田 亮}{Ryo Yasuda}{KIE}[riono210@cr.ie.u-ryukyu.ac.jp]
\author{河野 真治}{Shinji Kono}{IE}[kono@ie.u-ryukyu.ac.jp]

\begin{abstract}
講義やゼミではPC画面で用意した資料を見ながら進行することが多い。PCごとにアダプターや解像度が異なっており、正常にPC画面を表示できない場合がある。
当研究室で開発しているTreeVNCは、発表者のPC画面を参加者のPCに表示する画面配信システムである。TreeVNCの画像共有は、送信するデータ量が多いために有線LANでの接続に限られている。
本稿では無線LANでもTreeVNCを利用可能にするため、Wifi上にシステム制御用の従来の木構造と、画像データ送信用のMulticastの両方を構築を行う。
Multicastでは、サーバから送信された画像データUpdateRectangleを小さいパケットに分割し送信を行うよう実装した。
\end{abstract}

\maketitle


\section{画面配信ソフトウェアTreeVNCの活用}

%% 現代の講義や発表、LTなどではPC画面で用意した資料をプロジェクタに移しながら進行することが多い。ゼミでは発表者を交代する際に、PC画面の切り替えを行う必要がある。

%% その場合、発表者のPCを接続するたびにケーブルを差し替える必要がある。発表者のPCによっては接続するアダプターの種類や解像度の設定により、正常にPC画面を表示できない場合がある。また、参加者もプロジェクタに集中を割く必要があり、同時に手元のPCで作業を行う場合集中の妨げとなってしまう。

最近の社会情勢により、世間ではリモートワークが増えている。リモートワークではビデオ通話を行いながら自宅で仕事をすることになるが、PCの画面共有を利用して情報を共有することも多い。

ビデオ通話ソフトウェアの1つにZoomがある。Zoomはカメラを利用したビデオ通話に重点を置いて開発されているため、送信される画像に対してある程度のロスを許容して圧縮が行われている。そのためPC画面を共有した際に書類の文字がはっきり見えないということが発生する。またビデオ通話には、各地に存在するサーバを経由して通信を行っている。

当研究室で開発している画面配信システムTreeVNC\cite{taninari:2011a}は、発表者の画面を参加者のPC画面に表示するソフトウェアである。画面共有に特化しており、共有するPC画面をロスなく圧縮しデータを送信することが可能である。またPC同士で通信を行うため外部のサーバに接続する必要がなく、一般的なサーバ通信よりも高速に通信が可能である。


%そのため、参加者は不自由なく手元のPCを操作しながら講義を受けることが可能になる。さらに、発表者の交代もケーブルの差し替えを行わずに、全体に共有する画面の切り替えが可能となっている。

しかし、画面共有は送信するデータ量が多いため、無線LAN接続で接続を行なった際に有線接続よりも遅延が大きくなってしまう。そこで本研究では、Multicast通信の実装を行い無線LAN接続でもTreeVNCを利用可能にし、TreeVNCの有用性を評価することで講義やゼミを円滑に行えることを目標とする。

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

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

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

RFBサーバ側はFramebufferの更新が行われるたびに、RFBクライアントに対してFramebufferの変更部分を送信する。さらに、RFBクライアントからFramebuffer - UpdateRequestが来るとそれに答え返信する。変更部分のみを送信する理由は、更新があるたびに全画面を送信すると、送信するデータ面と更新にかかる時間面において効率が悪くなるからである。

TreeVNCはjavaを用いて作成されたTight VNC\cite{tightvnc}を元に作成されている。TreeVNCはVNCを利用して画面配信を行なっているが、従来のVNCでは配信(サーバ)側のPCに全ての参加者(クライアント)が接続するため負荷が大きくなってしまう(図\ref{fig:vncStruct})。
　
\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{fig/vncStruct.pdf}
\caption{従来のVNCでの接続構造}
\label{fig:vncStruct}
\end{center}
\end{figure}

そこでTreeVNCではサーバに接続を行なってきたクライアントをバイナリツリー状(木構造)に接続する。接続してきたクライアントをノードとし、その下に新たなノードを最大2つ接続していく。これにより人数分のデータのコピーと送信の手間を分散することができる(図\ref{fig:TreevncStruct})。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{fig/TreevncStruct.pdf}
\caption{TreeVNCでの接続構造}
\label{fig:TreevncStruct}
\end{center}
\end{figure}

通信の数は、送信されるデータは従来の方法だとN個のノードに対してN-1回必要である。これはバイナリツリー状の構造を持っているTreeVNCでも通信の数は変わらない。


バイナリツリー状に接続することで、N台のクライアントが接続を行なってきた場合、従来のVNCではサーバ側がN回のコピーを行なって画面配信する必要があるが、TreeVNCでは各ノードが最大2回ずつコピーするだけで画面配信が可能となる。

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

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

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

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

TreeVNCの木構造のネットワークトポロジーはRoot Nodeが持っているnodeListで管理している。Nodeの接続が切れた場合、Root Nodeに切断を知らせなければならない。

TreeVNCはLOST\_CHILDというメッセージ通信で、Node切断の検知および木構造の再構成を行なっている。LOST\_CHILDの検出方法にはMulticastQueueを使用しており、ある一定時間MulticastQueueから画像データが取得されない場合、MemoryOverFlowを回避するためにTimeoutスレッドが用意されている。そして、Timeoutを検知した際にNodeとの接続が切れたと判断する。

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

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)ことができない。従って、圧縮されたデータを途中から受け取ってもデータを正しく解凍することができない。

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

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

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

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

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

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

\section{有線接続と無線接続の違い}
現在のTreeVNCでは有線接続と無線LAN接続のどちらでも、VNCサーバから画面配信の提供を受けることが可能である。しかし画面配信のッデータ量は膨大なため、無線LAN接続を行なった場合画面配信の遅延が大きくなってしまう。

無線LAN接続の場合でも画面切り替えの機能は有効であるため、VNCサーバ側が無線LAN接続を行い、クライアント側は有線接続を行うことで画面配信が可能となる。ここで、WifiのMulticastの機能を用いてクライアント側でもWifiを使用することが可能であると考えられる。Root Nodeは無線LANに対して、変更するUpdate RectangleをMulticastで一度だけ送信すればよい。

有線接続の場合は従来通り、VNCサーバ、Root Node、Nodeからなるバイナリツリー状に接続されるため、有線接続時と無線LAN接続時でのVNCサーバの接続方法を分割することが可能である。(図\ref{fig:coexistence})。こうすることにより、新しいNodeが無線LAN接続であっても有線接続の木構造に影響を及ぼさない。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{fig/coexistence.pdf}
\caption{接続方法の分割}
\label{fig:coexistence}
\end{center}
\end{figure}

WifiのMulticast Packetのサイズは64KBが最大となっている。4Kディスプレイと例にとると、画面更新には8MBの画素数 * 8Bの色情報となり、圧縮前で64MB程度となる。

\section{RFBのUpdateRectangleの構成}
\begin{table}[htp]
    \caption{UpdateRectangleによるPacketの構成}
    \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}

RFBのUpdate Rectangleによって送られてくるPacketは以下の表\ref{tb:updateRectangle}のような構成となっている。

1つのUpdate Rectangleには複数のRectangleが入っており、さらに1つ1つのRectangleにはx,y座標や縦横幅、encoding typeが含まれているRectangle  Headerを持っている。ここではZRLEで圧縮されたRectangleが1つ、VNCサーバから送られてくる。Rectangleには、Zlib圧縮されたデータがdetalengthsと呼ばれる指定された長さだけ付いてくる。このデータは、さらに64x64のTileに分割されている。(図\ref{fig:BlockingUpdateRectangle}中 Tile)。

\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{fig/FrameUpdateRectangle.pdf}
\caption{Rectangleの分割}
\label{fig:BlockingUpdateRectangle}
\end{center}
\end{figure}

Tile内はパレットなどがある場合があるが、通常はRun Length encodeされたRGBデータである。
これまでのTreeVNCではVNCサーバから受け取ったRectangleを分割せずにZRLEEへ再構成を行なっていた。これをMulticastのためにデータを64KBに収まる最大3つのRectangleに再構成する。(図\ref{fig:BlockingUpdateRectangle})。この時にTile内部は変更する必要はないが、Rectangleの構成は変わる。ZRLEを展開しつつ、Packetを構成する必要がある。

64KBのPacketの中には複数のTileが存在するが、連続してRectangleを構成する必要がある。3つのRectangleの構成を下記に示す。

\begin{itemize}
\item 行の途中から始まり、行の最後までを構成するRectangle(図\ref{fig:BlockingUpdateRectangle}中 Phase0)
\item 行の初めから最後までを構成するRectangle(図\ref{fig:BlockingUpdateRectangle}中 Phase1)
\item 行の初めから、行の途中までを構成するRectangle(図\ref{fig:BlockingUpdateRectangle}中 Phase2)
\end{itemize}

\section{TileLoop}
TileLoopはVNCサーバから受け取ったZRLEを図\ref{fig:BlockingUpdateRectangle}のようにRectangleを分割し、ZRLEEに再構成を行ったPacketを生成する。

以下の図\ref{fig:Packet}にTileLoopで生成されるPacket全体と、分割される各PhaseのRectangleを示した。
\begin{figure}[htb]　%PDF
\begin{center}
\includegraphics[width=8cm]{fig/Blocking.pdf}
\caption{ZRLEEのPacketの構成と分割されたRectangle}
\label{fig:Packet}
\end{center}
\end{figure}


Packet Headerには表\ref{tb:updateRectangle}に示したmessageID、padding、n of rectangleが核にのうされている。また、分割されたRectangleにはそれぞれ表\ref{tb:rectangleheader}に示したRectangle Headerを持っている。

\begin{table}[htp]
    \caption{Rectangle Headerの構成}
    \begin{center}
    \begin{tabular}{|rr|l|} \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}
    \end{center}
    \label{tb:rectangleheader}
\end{table}

次にTileLoopの処理について説明する。以下の図\ref{fig:TileLoopFlow}はTileRoopのフローチャートである。

\begin{figure}[htp]　%PDF
\begin{center}
\includegraphics[width=8cm]{fig/TileLoopFlow.pdf}
\caption{TileLoopのフローチャート}
\label{fig:TileLoopFlow}
\end{center}
\end{figure}

図\ref{fig:TileLoopFlow}中1にて、TileLoopの初期化でBlockingと構築するPacketの準備を行う。Loop本体ではZRLEで受け取ったRectangleを1Tile 64x64に分割し、1Tileずつ処理を行う。そして受け取ったZRLEより処理を行うTileのデータを取得し、圧縮段階に入る。


TileLoopにはc1Rectと呼ばれるRectangleを持っている。これは読み込んだTile分だけ縦横を拡張していくことによってRectangleの再構成を行なっている。図\ref{fig:TIleLoopFlow}中2の圧縮段階では、読み込んだTileのデータを圧縮用のStreamに格納し、java.util.zip.deflaterを利用して圧縮を行なっている。Packetのサイズは60KBとしているが、一旦の制限として42KBまでを格納可能としている。

java.util.zip.deflaterには下記の3種類の圧縮方法がある。

\begin{itemize}
\item NO\_FLUSH : Streamに格納されたデータを最効率で圧縮を行う。Streamにある入力データが規定量に満たない場合は圧縮されない
\item SYNC\_FLUSH : これまでにStreamに圧縮されたデータの圧縮を行う。ただし圧縮率が低下する可能性がある
\item FULL\_FLUSH : SYNC\_FLUSH同様、これまでにStreamに格納されたデータ圧縮を行う。異なる点はこれまでの辞書情報がリセットされるため、圧縮率が極端に低くなる可能性がある
\end{itemize}

ZRLEとjava.util.zip.deflaterを使用した圧縮では、圧縮後のデータ長を予測することができない。Packetが満杯になってしまうと、圧縮書き込みの途中であっても圧縮書き込みが中断する。そのため、Packetサイズを余分に確保する必要がある。したがって最初から最大の60KBではなく、42KBに制限を行なっている。TileLoopではデータの圧縮にNO\_FLUSHを利用していたが、圧縮後のデータがPacketの上限である60KBを超えてしまうことが多発した。

これは圧縮されるための入力データの規定量が想定以上に多く、圧縮後のデータ長がMulticast Packetの上限を超えてしまったためである。

そこで圧縮率は悪くなるが、確実にPacketに書き込まれるSYNC\_FLUSHを利用し、ZRLEEの生成を行う。

図\ref{fig:TileLoopFlow}中3ではPacketの上限までいかなかった場合の分岐である。
分岐の初めではRectangleの構成を行なっているc1Rectと、ZRLEから送られてきたRectangleなどと比較を行い、Phaseの確認をする。

Phaseの変更がなかった場合はLoopの先頭に戻るが、Phaseの変更があった場合、これまで構成していたRectangleとしてc1RectをそのPhaseのRectangle Headerに書き出す。c1Rectは次のPhaseに向けて初期化される。またこの時、図\ref{fig:Packet}の各Rectangleの行末にあるように、FULL\_HLUSHを行う理由は、次の行に移る際圧縮用のStreamにデータを残さないためである。

図\ref{fig:TileLoopFlow}中4の処理は、Packetが一旦の上限42KBまで達したことで分岐する。

java.util.zip.deflaterを使用した圧縮では、Packetが一杯になってしまうと、圧縮書き出し中でも中断してしまう。そこでPacketの余剰分を解放し上限を60KBにすることで、確実に書き込みを可能とする。図\ref{fig:Packet}中Last Tileとは、Packetが一杯になった際に読み込まれているTileのことを指す。Last Tileは圧縮前で最大16KBと考えられる。これを圧縮すると3 - 4KB程度であるので、その分のマージンを持っていくことで、読み込んだ最後のTileまできちんとPacketに書き込むことができる。

Packetに書き込み後はZRLEEでのMulticast Packetが完成したため、子Nodeへの送信のためにMulticastQueueへPacketが格納される。

以上のルーチンをZRLEで受け取ったRectangle内のTile全てで行うことによって、VNCサーバから受け取ったZRLEの画像データをZRLEEとして生成を行うことができる。


\section{Multicast用のシステム構成}




\section{まとめ}

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

\end{document}