changeset 24:f854857fdbf6

fix
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 08 May 2019 20:20:37 +0900
parents 6a63940030f5
children f4c456e62629
files Paper/riono-sigos.pdf Paper/riono-sigos.tex
diffstat 2 files changed, 86 insertions(+), 36 deletions(-) [+]
line wrap: on
line diff
Binary file Paper/riono-sigos.pdf has changed
--- a/Paper/riono-sigos.tex	Wed May 08 20:05:25 2019 +0900
+++ b/Paper/riono-sigos.tex	Wed May 08 20:20:37 2019 +0900
@@ -58,40 +58,36 @@
 
 当研究室で開発している画面配信システムTreeVNC\cite{taninari:2011a}は、発表者の画面を参加者のPCに表示するソフトウェアである。そのため、参加者は不自由なく手元のPCを操作しながら講義を受けることが可能になる。更に発表者の切り替えの際もケーブルを差し替えずに、共有する画面の切り替えが可能になっている。
 
-TreeVNCはVNC\cite{vnc}を利用した画面配信を行なっている。しかし通常のVNCでは配信側のPCに全ての参加者が
-
+\begin{figure}[htb] %PDF
+\begin{center}
+    \includegraphics[width=8cm]{Image/vnc-crop.pdf}
+\caption{従来のVNCの接続方法}
+\label{fig:UntilVNC}
+\end{center}
+\end{figure}
 
-\section{TreeVNCの基本概念}
-\subsection{VNCについて}
 VNC(Virtual Network Computing)は、クライアント(ビューワー)側とサーバ側からなるリモートデスクトップソフトウェアである。遠隔操作にはサーバを起動し、クライアント側がサーバに接続をすることで可能としている。また、動作にはRFBプロトコルを用いている。
+TreeVNCはVNC\cite{vnc}を利用した画面配信を行なっている。しかし通常のVNCでは配信側のPCに全ての参加者への配信を行う負荷がかかってしまう。(図\ref{fig:UntilVNC})
 
-\subsection{RFBプロトコルについて}
 RFB(Remote Frame Buffer)プロトコル\cite{rfbprotocol}とは、自身のPC画面をネットワーク上に送信し他人の画面に表示を行うプロトコルである。画面が表示されるユーザ側をRFBクライアントと呼び、画面を送信のためにFramebufferの更新が行われる側をRFBサーバと呼ぶ。Framebufferとは。メモリ上に置かれた画像データのことである。RFBプロトコルでは、最初にプロトコルのバージョン確認や認証が行われる。その後、クライアントへ向けてFramebufferの大きさやデスクトップに付けられた名前などが含まれている初期メッセージを送信する。RFBサーバ側はFramebufferの更新が行われるたびに、RFBクライアントに対してFramebufferの変更部分のみを送信する。更に、RFBクライアントのFramebufferUpdateRequestが来るとそれに答え返信する。変更部分のみを送信する理由は、更新がある度に全画面を送信すると、送信するデータ面と更新にかかる時間面において効率が悪くなるからである。
 
-
-\subsection{TreeStructure}
-TreeVNCはサーバに接続してきたクライアントをバイナリツリー状に接続している。また、接続してきたクライアントをノードとし、その下に新たなノードを接続していくことでサーバが画面のデータを配信する回数を抑え、負荷分散を行なっている(図\ref{fig:TreeStructure})。バイナリツリー状に接続することで、N台のクライアントが接続しにきた場合、従来のVNCではサーバ側がN回のコピーを行なって配信をする必要がある(図\ref{fig:UntilVNC})が、TreeVNCでは各ノードが2回ずつコピーをするだけで配信が可能となる。
+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[scale=0.4]{Image/treevnc-crop.pdf}
+\includegraphics[width=8cm]{Image/treevnc-crop.pdf}
 \caption{TreeVNCの接続方法}
 \label{fig:TreeStructure}
 \end{center}
 \end{figure}
 
+\section{TreeVNCの通信プロトコル}
 
-\begin{figure}[htb] %PDF
-\begin{center}
-\includegraphics[scale=0.4]{Image/vnc-crop.pdf}
-\caption{従来のVNCの接続方法}
-\label{fig:UntilVNC}
-\end{center}
-\end{figure}
-
-\subsection{通信経路}
 TreeVNCの通信経路として以下の6つが挙げられる。
 
 
@@ -108,9 +104,9 @@
 \subsection{メッセージ通信}
 TreeVNCの各NodeとVNCServer間で通信されるメッセージを表\ref{tb:message}に示す。
 
-\begin{table}[htbp]
+\begin{table*}[htbp]
  	\caption{通信経路とメッセージ一覧}
-	\scalebox{0.55}{	
+	\scalebox{1}{	
     	\begin{tabular}{|l|l|l|} \hline
 	通信経路				& message						& 説明 \\ \hline \hline
                    				& FIND\_ROOT					& TreeVNC接続時にRoot Nodeを探す。 \\ \cline{2-3}
@@ -141,7 +137,7 @@
     \end{tabular}
     }
     \label{tb:message}
-\end{table}
+\end{table*}
 	
 \subsection{MulticastQueue}
 配信側の画面が更新されるとVNCServerから画像データがFRAME\_BUFFER\_UPDATEメッセージとして送られる。その際、画像データの更新を複数のNodeに同時に伝えるためにMulticast Queueというキューに画像データを格納する。
@@ -149,18 +145,22 @@
 
 \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を実現していることになり圧縮率はむしろ向上する。
 
-そこでZRLEEは一度Root Nodeで受け取ったZRLEのデータをunzipし、データをupdate rectangleと呼ばれる画面ごとのデータに辞書を付与してzipし直すことで初めからデータを読み込んでいなくても解凍できるようになった(図\ref{fig:ZRLEE})。一度ZRLEEに変換してしまえば子Nodeはそのデータを渡すだけで良い。ただしdeflaterとinflaterでは前回までの通信で得た辞書をクリアしなければならないため、Root NodeとNode側では毎回新しく作成する必要がある。
-
+\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は配信者の切り替えのた度に生じる問題を解決している。
@@ -174,7 +174,7 @@
 
 \begin{figure}[htb] %PDF
 \begin{center}
-\includegraphics[scale=0.4]{Image/MultiNetworkTree.pdf}
+\includegraphics[width=8cm]{Image/MultiNetworkTree.pdf}
 \caption{Multi Network Tree}
 \label{fig:multinetworktree}
 \end{center}
@@ -185,24 +185,74 @@
 
 \section{マルチキャストの導入}
 \subsection{有線接続との接続形式の違い}
-画面配信のデータ量は膨大なため、現在のTreeVNCでVNCServerに無線LAN接続を行なった場合、画面配信の遅延が大きくなってしまう。有線接続しているNodeのみでバイナリツリーを形成している状態に、無線LAN通信で接続を行ってきたNodeをツリーに加えてしまうと、そのNodeに対する通信が遅延してしまい、ツリー全体の配信遅延につながってしまう。
+画面配信のデータ量は膨大なため、現在の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データである。
 
-この問題点を解決する手法として、Muliticast通信の実装を提案する。Multicast通信では、サーバ側は一度の通信で接続しているデバイス全てにデータを届けることができるため、木構造の形成が必要ない。従って、無線LANで接続してきたNodeに対しMulticast通信を行うことで、有線接続の際と無線LAN接続の際で管理方法を分割でき、有線接続の木構造には影響が出ない(図\ref{fig:WirelessLAN})。
+\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[scale=0.4]{Image/interface-crop.pdf}
-\caption{Multicastでの接続図}
-\label{fig:WirelessLAN}
+\includegraphics[width=8cm]{Image/FrameUpdateRectangle.pdf}
+\caption{Multi Network Tree}
+\label{fig:multinetworktree}
 \end{center}
 \end{figure}
 
 
-\subsection{画像データのBlocking}
-画面配信のデータはサイズが膨大であり、送信する際に一度では送ることが出来ないため分割して送信される。
-しかし無線LAN接続では有線接続と比較して一度に送信できるデータ量が少ない。そのためサーバ側が送信した画面配信のデータが正確にクライアントに送られない可能性があり、更にデータを分割する必要がある。そこで、データを再分割する手法としてBlockingを実装した。
+\section{まとめ}
 
-\section{まとめ}
+Tree VNC に Wifi 上の Multicast packet を用いる手法について考察した。画面圧縮にHareware supported なMPEG4などを用いることができれば
+より効率的な転送が可能であるが、ここでは Java 上で実装できる安易な方法をあえて選択した。Wifi の速度と Multicast の信頼性が高ければ
+これでも実用になると可能性がある。
+
+Blocking は実装中であり、再圧縮の時間は前画面の時でも実用的な時間ですむことが予想されている。Wifi 上の Multicast packet の
+drop 率は、接続環境に依存すると思われるのでさらなる実験が必要だと思われる。
+
+有線使用時よりも、画面共有の質が落ちるのはある程度はやむを得ないが、再送が必要である場合には、必要なプロトコルを実装する。
 
 
 \nocite{*}