Binary file Paper/riono-sigos.pdf has changed

--- a/Paper/riono-sigos.tex	Wed May 08 20:31:38 2019 +0900
+++ b/Paper/riono-sigos.tex	Thu May 09 02:15:22 2019 +0900
@@ -32,7 +32,7 @@
 
 \title{画像配信システム TreeVNC のマルチキャストの導入}
 
-\etitle{}
+\etitle{Introduction of multicast of screen delivery software  TreeVNC}
 
 %\affiliate{IPSJ}{情報処理学会\\
 %IPSJ, Chiyoda, Tokyo 101--0062, Japan}
@@ -42,15 +42,16 @@
 Information Engineering, University of the Ryukyus.}
 
 \author{安田 亮}{Ryo Yasuda}{IEUR}[riono210@cr.ie.u-ryukyu.ac.jp]
-\author{大城 由也}{Yuya Oshiro}{}
+\author{大城 由也}{Yuya Oshiro}{}[oshiro@cr.ie.u-ryukyu.ac.jp]
 \author{河野 真治}{Shinji Kono}{IEUR}[kono@ie.u-ryukyu.ac.jp]
 
 \begin{abstract}
- TreeVNCとは当研究室で開発している画面配信システムである。しかし、画面共有は送信するデータ量が多いため、無線 LAN 接続の場合、画面の配信に遅延が生じてしまう。そこで、multicast でのデータ通信の実装やデータの分割・圧縮方法の評価を行い、TreeVNC のmulticastの有用性を評価する。
+講義やゼミではPC画面で用意した資料を見ながら進行することが多い。しかし、発表者のPC画面の切り替えでケーブルを差し替えを行う必要や、PCと接続するアダプターによっては正常にPC画面を表示できない場合がある。当研究室で開発しているTreeVNCは、発表者のPC画面を参加者のPCに表示する画面配信システムである。サーバに接続したクライアントをバイナリツリー状に接続し、配信コストを分散させる仕組みを取ることで、多人数が接続しても処理性能が下がらないような設計になっている。しかし、画面共有は送信するデータ量が多いため、無線 LAN 接続の場合、画面の配信に遅延が生じてしまう。そこで、multicast でのデータ通信の実装やデータの分割・圧縮方法の評価を行い、TreeVNC のmulticastの有用性を評価する。
 \end{abstract}
 
-
-
+\begin{eabstract}
+In lectures and seminars, it often progresses while looking at the materials prepared on the PC screen. However, it may be necessary to replace the cable by switching the PC screen of the presenter, or the PC screen may not be displayed properly depending on the adapter connected to the PC. TreeVNC, developed by our laboratory, is a screen distribution system that displays the presenter's PC screen on the participant's PC. The client connected to the server is connected in a binary tree, and distribution cost is distributed, so that the processing performance does not decrease even if many people connect. However, since screen sharing involves a large amount of data to be transmitted, in the case of wireless LAN connection, there will be a delay in screen distribution. Therefore, we evaluate the implementation of data communication in multicast and the data division / compression method, and evaluate the usefulness of TreeVNC's multicast.
+\end{eabstract}
 \maketitle
 
 \section{画面配信ソフトウェア TreeVNCの活用}
@@ -58,6 +59,13 @@
 
 当研究室で開発している画面配信システムTreeVNC\cite{taninari:2011a}は、発表者の画面を参加者のPCに表示するソフトウェアである。そのため、参加者は不自由なく手元のPCを操作しながら講義を受けることが可能になる。更に発表者の切り替えの際もケーブルを差し替えずに、共有する画面の切り替えが可能になっている。
 
+しかし、画面共有は送信するデータ量が多いため、現在のTreeVNCでは無線LAN接続の場合、画面の配信に遅延が生じてしまう場合がある。そこで本研究では、multicastでのデータ通信の実装やデータの分割・圧縮方法の評価を行うことにより、無線LANでの配信環境の向上を目指し、TreeVNCの有用性を評価することで講義やゼミを円滑に行えることを目標とする。
+
+\section{TreeVNCの基本概念}
+VNC(Virtual Network Computing)は、クライアント(ビューワー)側とサーバ側からなるリモートデスクトップソフトウェアである。遠隔操作にはサーバを起動し、クライアント側がサーバに接続をすることで可能としている。また、動作にはRFBプロトコルを用いている。
+
+TreeVNCはVNC\cite{vnc}を利用した画面配信を行なっている。しかし通常のVNCでは配信側のPCに全ての参加者への配信を行う負荷がかかってしまう。(図\ref{fig:UntilVNC})
+
 \begin{figure}[htb]　%PDF
 \begin{center}
     \includegraphics[width=8cm]{Image/vnc-crop.pdf}
@@ -66,16 +74,14 @@
 \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(Remote Frame Buffer)プロトコル\cite{rfbprotocol}とは、自身のPC画面をネットワーク上に送信し他人の画面に表示を行うプロトコルである。画面が表示されるユーザ側をRFBクライアントと呼び、画面を送信のためにFramebufferの更新が行われる側をRFBサーバと呼ぶ。Framebufferとは。メモリ上に置かれた画像データのことである。RFBプロトコルでは、最初にプロトコルのバージョン確認や認証が行われる。その後、クライアントへ向けてFramebufferの大きさやデスクトップに付けられた名前などが含まれている初期メッセージを送信する。RFBサーバ側はFramebufferの更新が行われるたびに、RFBクライアントに対してFramebufferの変更部分のみを送信する。更に、RFBクライアントのFramebufferUpdateRequestが来るとそれに答え返信する。変更部分のみを送信する理由は、更新がある度に全画面を送信すると、送信するデータ面と更新にかかる時間面において効率が悪くなるからである。
+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
@@ -89,8 +95,6 @@
 \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)
@@ -145,33 +149,29 @@
 
 \subsection{木構造の再構成}
 TreeVNCはバイナリツリーでの接続のため、Nodeが切断されたことを検知できないと構成した木構造が崩れてしまい、新しいNodeを適切な場所に接続できなくなってしまう。そこで木構造を崩さないよう、Node同士の接続の再構成を行う必要がある。
-TreeVNCの木構造のネットワークトポロジーはRoot Nodeが持っているnodeListで管理している。Nodeの接続が切れた場合、Root Nodeに切断を知らせなければならない。
-TreeVNCはLOST\_CHILDというメッセージ通信で、Nodeの切断を検知および木構造の再構成を行なっている。LOST\_CHILDの検出方法にはMulticastQueueを使用しており、ある一定時間MulticastQueueから画像データが取得されない場合、MemoryOverFlowを回避するためにTimeoutスレッドが用意されている。そして、Timeoutを検知した際に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})。
+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)ことが出来ない。従って、圧縮されたデータを途中から受け取るとデータを正しく解凍することが出来ない。そこで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}
+\label{fig:ZRLEE}
 \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}
@@ -180,34 +180,48 @@
 \end{center}
 \end{figure}
 
-TreeVNCはRoot NodeがTreeManagerというオブジェクトを持っている。TreeManagerはTreeVNCの接続部分を管理しており、木構造を管理するnodeListを生成する。このnodeListを元に、新しいNodeの接続や、切断検出時の接続の切り替え等を行う。Tree ManagerはRoot Nodeの保持しているネットワーク毎に生成される。新しいNodeが接続してきた際、interfacesからNodeのネットワークと一致するTree Managerを取得し、Node接続の処理を任せる。
+\subsection{ネットワーク複数時の接続}
+TreeVNCはRoot Nodeが複数のネットワークに接続している場合、図\ref{fig:multinetworktree}のようにネットワーク別に木構造を形成する。TreeVNCはRoot NodeがTreeManagerというオブジェクトを持っている。TreeManagerはTreeVNCの接続部分を管理しており、木構造を管理するnodeListを生成する。このnodeListを元に、新しいNodeの接続や、切断検出時の接続の切り替え等を行う。Tree ManagerはRoot Nodeの保持しているネットワーク毎に生成される。新しいNodeが接続してきた際、interfacesからNodeのネットワークと一致するTree Managerを取得し、Node接続の処理を任せる。
 
 
-\section{マルチキャストの導入}
-\subsection{有線接続との接続形式の違い}
+%\section{マルチキャストの導入}
+\section{有線接続との接続形式の違い}
 画面配信のデータ量は膨大なため、現在のTreeVNCでVNCServerに無線LAN接続を行なった場合、画面配信の遅延が大きくなってしまう。
-この場合でも画面切り替えの機能は有効である。つまり、画面を提供するPCのみを無線経由で接続し、配信を希望する側は有線を
-使用することができる。
-
-ここで、Wifi のMulticast の機能を用いて配信側にもWifiを使用することが可能であると考えられる。Tree Root は無線LANに対して、
-変更する UpdateRectangle を Multicast で一度だけ送信する。
+この場合でも画面切り替えの機能は有効である。つまり、画面を提供するPCのみを無線経由で接続し、配信を希望する側は有線を使用することができる。ここで、Wifi のMulticast の機能を用いて配信側にもWifiを使用することが可能であると考えられる。Tree Root は無線LANに対して、変更する UpdateRectangle を Multicast で一度だけ送信する。
 
 Wifi のMulticast packet のサイズは 64kbyte が最大となっている。HDや4Kの大きさの画面更新は8Mb * 8byteで圧縮前で64MB程度になる。
 これを圧縮しつつ、64kbye 毎のパケットに変換して送る必要がある。
-
-Wifi のMulticast packet は確実に送られること保証されていない。通し番号を付けて欠落を検出することはできるが、再送処理は
-複雑であることが予想される。
+Wifi のMulticast packet は確実に送られること保証されていない。通し番号を付けて欠落を検出することはできるが、再送処理は複雑であることが予想される。
 
 ここではまずBlocking について考察と実験を行う。
 
+
+
 \section{RFBのUpdateRectangle の構成}
 
-RFB のUpdateRectangle は以下の構成になっている。一つのupdateRectangleには複数のRectangleは入っていて、
+RFB のUpdateRectangle は以下の表\ref{tb:updateRectangle}の構成になっている。一つのupdateRectangleには複数のRectangleは入っていて、
 さらに一つ一つのRectangleの encoding type がある。ここでは ZRLEで encode された rectangle  が一つサーバから送られてくる。
-rectangle には zlib で圧縮されたデータが指定された長さだけ付いてくる。このデータは、64x64 の tile にさらに分割されている。
+rectangle には zlib で圧縮されたデータが指定された長さだけ付いてくる。このデータは、64x64 の tile にさらに分割されている(図\ref{fig:rectangle})。
 tile 内はパレットとかがある場合があるが、Run length encode されたRGBデータである。
 
-\begin{table}[htbp]
+
+このパケットを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{Rectangleの分割}
+\label{fig:rectangle}
+\end{center}
+\end{figure}
+
+\begin{table}[hp]
     \caption{updateRectangleの構成}
     \begin{tabular}{|rrr|l|} \hline
         1 byte & & & messageID    \\
@@ -225,35 +239,33 @@
     \label{tb:updateRectangle}
 \end{table}
 
-このパケットを64kbyteに収まる三つのRectangleに再構成する。この時に、tile 内部は変更する必要はないが、Rectangleの構成は変わる。
-ZRLE を展開しつつ、パケットを構成する必要がある。
+\section{木構造とマルチキャストの共存}
+現在のTreeVNCでは有線接続と無線LAN接続のどちらでも、VNCサーバから画面配信の提供を受けることが可能である。しかし無線LANで接続しているNodeが存在すると、バイナリツリーを形成している全体の配信遅延に繋がってしまう。
+この問題点を解決するために、有線接続時と無線LAN接続時でのVNCサーバの接続方法の分割を提案する。
 
-zlib はちょうど良い所で圧縮を flush する必要がある。このためには、zlib のAPIを用いて、適当なタイミングで flush を呼ぶ。
-この時に1 tileずづ flush してしまうと圧縮率を下げる可能性がある。
-
-64kbyte のpacketの中には複数の tile が存在するが、連続して Rectangle を構成する必要がある。行の途中から始まり、途中で
-終わる可能性があるので、三つのRectangleが必要になる。
+有線接続の場合は従来通り、VNCサーバ、Root Node、Nodeからなるバイナリツリー状に接続される。
+無線LAN接続の場合は、Multicastで接続を行う。こうすることにより、新しいNodeが無線LAN接続出会っても有線接続のバイナリツリーには影響を及ぼさない(図\ref{fig:interface})。
 
 \begin{figure}[htb]　%PDF
 \begin{center}
-\includegraphics[width=8cm]{Image/FrameUpdateRectangle.pdf}
-\caption{Multi Network Tree}
-\label{fig:multinetworktree}
+\includegraphics[width=8cm]{Image/interface-crop.pdf}
+\caption{接続方法の切り替え}
+\label{fig:interface}
 \end{center}
 \end{figure}
 
 
 \section{まとめ}
 
-Tree VNC に Wifi 上の Multicast packet を用いる手法について考察した。画面圧縮にHareware supported なMPEG4などを用いることができれば
-より効率的な転送が可能であるが、ここでは Java 上で実装できる安易な方法をあえて選択した。Wifi の速度と Multicast の信頼性が高ければ
-これでも実用になると可能性がある。
+Tree VNC に Wifi 上の Multicast packet を用いる手法について考察した。画面圧縮にHareware supported なMPEG4などを用いることができればより効率的な転送が可能であるが、ここでは Java 上で実装できる安易な方法をあえて選択した。Wifi の速度と Multicast の信頼性が高ければこれでも実用になると可能性がある。
 
-Blocking は実装中であり、再圧縮の時間は前画面の時でも実用的な時間ですむことが予想されている。Wifi 上の Multicast packet の
-drop 率は、接続環境に依存すると思われるのでさらなる実験が必要だと思われる。
+
+Blocking は実装中であり、再圧縮の時間は前画面の時でも実用的な時間ですむことが予想されている。Wifi 上の Multicast packet のdrop 率は、接続環境に依存すると思われるのでさらなる実験が必要だと思われる。
 
 有線使用時よりも、画面共有の質が落ちるのはある程度はやむを得ないが、再送が必要である場合には、必要なプロトコルを実装する。
 
+VNCサーバへの接続方法の分割についても、Node接続時のinterfacesから有線接続か無線LAN接続かを完全に区別出来ない。接続時にユーザが選択するか、接続時にある程度区別する処理を実装する必要がある。
+
 
 \nocite{*}
 \bibliographystyle{ipsjunsrt}