--- a/Paper/Makefile	Mon May 04 15:34:01 2020 +0900
+++ b/Paper/Makefile	Mon May 04 23:38:11 2020 +0900
@@ -12,20 +12,18 @@
 
 .PHONY: all pdf dvi clean
 
-all: dvi pdf 
+all: $(TARGET).pdf
 	open $(TARGET).pdf
 
 $(TARGET).pdf: dvi pdf
 
 dvi: $(TARGET).tex
-	echo $<
-	echo $@
 	$(LATEX) $<
 	$(BIBTEX) $(TARGET)
 	$(LATEX) $<
 	$(LATEX) $<
 
-pdf: $(TARGET).tex $(TARGET).dvi
+pdf: $(TARGET).dvi
 	$(DVIPDF) $(DVIPDF_OPT) $(TARGET).dvi
 
 clean:

Binary file Paper/riono-sigos.pdf has changed

--- a/Paper/riono-sigos.tex	Mon May 04 15:34:01 2020 +0900
+++ b/Paper/riono-sigos.tex	Mon May 04 23:38:11 2020 +0900
@@ -130,8 +130,145 @@
 
 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接続を行なった場合画面配信の遅延が大きくなってしまう。
 
-\section{Blockingの実装}
+無線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用のシステム構成}