Mercurial > hg > Papers > 2020 > riono-thesis
annotate FinalThesis/chapter3.tex @ 32:77951f2269aa
fix TileLoop explain
| author | riono <e165729@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sun, 16 Feb 2020 05:27:40 +0900 |
| parents | 37ad9420dc84 |
| children | f93a34243a0b |
| rev | line source |
|---|---|
|
23
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
1 \chapter{Multicastに向けたBlockingの実装} |
| 1 | 2 \label{chap:poordirection} |
| 3 | |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
4 \section{有線接続と無線LAN接続との違い} |
|
23
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
5 現在のTreeVNCでは有線接続と無線LAN接続のどちらでも、VNCサーバから画面配信の提供を受けることが可能である。しかし画像配信のデータ量は膨大なため、現在のTreeVNCでVNCサーバに無線LAN接続を行なった場合、画面配信の遅延が大きくなってしまう。 |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
6 |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
7 無線LAN接続時の場合でも画面切り替えの機能は有効であるため、VNCサーバ側が無線LANで接続を行い、クライアント側は有線接続を行うことで画面配信が可能となる。ここで、WifiのMulticastの機能を用いてクライアント側でもWifiを使用することが可能であると考えられる。Root Nodeは無線LANに対して、変更するUpdate RectangleをMulticastで一度だけ送信する。 |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
8 |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
9 有線接続の場合は従来通り、VNCサーバ、Root Node、Nodeからなるバイナリツリー状に接続されるため、有線接続時と無線LAN接続時でのVNCサーバの接続方法を分割することが可能である(図\ref{fig:coexistence})。こうすることにより、新しいNodeが無線LAN接続であっても有線接続の木構造には影響を及ぼさない。 |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
10 |
|
23
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
11 \begin{figure}[htb] %PDF |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
12 \begin{center} |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
13 \includegraphics[scale=0.35]{fig/coexistence.pdf} |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
14 \figcaption{接続方法の分割} |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
15 \label{fig:coexistence} |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
16 \end{center} |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
17 \end{figure} |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
18 |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
19 |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
20 WifiのMulticast Packetのサイズは64KByteが最大となっている。4Kディスプレイを例にとると、4Kディスプレイの大きさの画面更新には8MByte(画素数) \* 8Byte(色情報)で圧縮前で、64MByte程度となる。 |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
21 |
| 1 | 22 |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
23 \section{Update Rectangleの構成} |
| 32 | 24 RFBのUpdate Rectangleによって送られてくるPacketは以下の表\ref{tb:updateRectangle}の構成となっている。 |
| 1 | 25 |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
26 \begin{table}[htp] |
| 32 | 27 \caption{UpdateRectangleによるPacketの構成} |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
28 \begin{center} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
29 \begin{tabular}{|rrr|l|} \hline |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
30 1 byte & & & messageID \\ |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
31 1 byte & & & padding \\ |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
32 2 byte & & & n of rectangles \\ \hline |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
33 & 2 byte & & U16 - x-position \\ |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
34 & 2 byte & & U16 - y-position \\ |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
35 & 2 byte & & U16 - width \\ |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
36 & 2 byte & & U16 - height \\ |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
37 & 4 byte & & S32 - encoding-type \\ |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
38 & 4 byte & & U32 datalengths \\ \hline |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
39 & & 1 byte & subencoding of tile \\ |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
40 & & n byte & Run Length Encoded Tile \\ \hline |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
41 \end{tabular} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
42 \end{center} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
43 \label{tb:updateRectangle} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
44 \end{table} |
| 1 | 45 |
| 32 | 46 1つのUpdate Rectangleには複数のRectangleが入っており、さらに1つ1つのRectangleにはx,y座標や縦横幅、encoding type が含まれているRectangle Headerを持っている。ここではZRLEで圧縮されたRectangleが1つ、VNCサーバから送られてくる。RectangleにはZlib圧縮されたデータが、datelengthsと呼ばれる指定された長さだけ付いてくる。このデータは、さらに64x64のTileに分割されている(図\ref{fig:BlockingUpdateRectangle}中 Tile)。 |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
47 |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
48 \newpage |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
49 |
| 32 | 50 Tile内はパレットなどがある場合があるが、通常はRun Length encodeされたRGBデータである。 |
| 51 これまでのTreeVNCではVNCサーバから受け取ったRectangleを分割せずにZRLEEへ再構成を行なっていた。これをMluticastのためにデータを64KByteに収まる最大3つのRectangleに再構成する(図\ref{fig:BlockingUpdateRectangle})。この時にTile内部は変更する必要はないが、Rectangleの構成は変わる。ZLREを展開しつつ、Packetを構成する必要がある。 | |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
52 |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
53 |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
54 \begin{figure}[htb] %PDF |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
55 \begin{center} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
56 \includegraphics[scale=0.5]{fig/FrameUpdateRectangle.pdf} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
57 \figcaption{Rectangleの分割} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
58 \label{fig:BlockingUpdateRectangle} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
59 \end{center} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
60 \end{figure} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
61 |
| 32 | 62 64KByteのPacketの中には複数のTileが存在するが、連続してRectangleを構成する必要がある。3つの |
|
23
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
63 Rectangleの構成を下記に示す。 |
| 1 | 64 |
|
23
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
65 \begin{itemize} |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
66 \item 行の途中から始まり、行の最後までを構成するRectangle(図\ref{fig:BlockingUpdateRectangle}中 Phase0) |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
67 \item 行の初めから最後までを構成するRectangle(図\ref{fig:BlockingUpdateRectangle}中 Phase1) |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
68 \item 行の初めから、行の途中までを構成するRectangle(図\ref{fig:BlockingUpdateRectangle}中 Phase2) |
|
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
69 \end{itemize} |
| 1 | 70 |
| 26 | 71 \newpage |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
72 |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
73 \section{TileLoop} |
| 32 | 74 TileLoopはVNCサーバから受け取ったZRLEを図\ref{fig:BlockingUpdateRectangle}のようにRectangleを分割し、ZRLEEに再圧縮を行ったPacketを生成する。 |
| 75 | |
| 76 以下の図\ref{fig:Packet}にTileLoopで生成されるPacket全体と、分割される各PhaseのRectangleを示した。 | |
| 77 | |
| 78 \begin{figure}[htb] %PDF | |
| 79 \begin{center} | |
| 80 \includegraphics[scale=0.45]{fig/Blocking.pdf} | |
| 81 \figcaption{ZRLEEのPacketの構成と分割されたRectangle} | |
| 82 \label{fig:Packet} | |
| 83 \end{center} | |
| 84 \end{figure} | |
| 85 | |
| 86 | |
| 87 Packet Headerには表\ref{tb:updateRectangle}に示したmessageID、padding、n of rectanglesが格納されている。また、分割されたRectangleにはそれぞれ表\ref{tb:rectangleheader}に示したRectangle Headerを持っている。 | |
| 88 | |
| 89 \begin{table}[htp] | |
| 90 \caption{Rectangle Headerの構成} | |
| 91 \begin{center} | |
| 92 \begin{tabular}{|rr|l|} \hline | |
| 93 2 byte & & U16 - x-position \\ | |
| 94 2 byte & & U16 - y-position \\ | |
| 95 2 byte & & U16 - width \\ | |
| 96 2 byte & & U16 - height \\ | |
| 97 4 byte & & S32 - encoding-type \\ | |
| 98 4 byte & & U32 datalengths \\ \hline | |
| 99 & 1 byte & subencoding of tile \\ | |
| 100 & n byte & Run Length Encoded Tile \\ \hline | |
| 101 \end{tabular} | |
| 102 \end{center} | |
| 103 \label{tb:rectangleheader} | |
| 104 \end{table} | |
| 25 | 105 |
| 31 | 106 \newpage |
| 107 | |
| 32 | 108 次にTileLoopの処理について説明する。以下の図\ref{fig:TileLoopFlow}はTileRoopのフローチャートである。 |
| 109 | |
| 110 | |
| 111 \begin{figure}[hp] %PDF | |
| 26 | 112 \begin{center} |
| 113 \includegraphics[scale=0.5]{fig/TileLoopFlow.pdf} | |
| 114 \figcaption{TileLoopのフローチャート} | |
| 115 \label{fig:TileLoopFlow} | |
| 116 \end{center} | |
| 117 \end{figure} | |
| 25 | 118 |
| 32 | 119 |
| 120 図\ref{fig:TileLoopFlow} 中1にて、TileLoopの初期化でBlockingと構築するPacketの準備を行う。Loop本体ではZRLEで受け取ったRecganleを1Tile 64x64に分割し、1Tileずつ処理を行う。そして受け取ったZRLEより処理を行うTileのデータを取得し、圧縮段階に入る。 | |
| 121 | |
| 122 | |
| 123 TileLoopにはc1Rectと呼ばれるRectangleを持っている。これは読み込んだTile分だけ縦横を拡張していくことによってRectangleの再構成を行なっている。図\ref{fig:TileLoopFlow} 中2の圧縮段階では、読み込んだTileのデータを圧縮用のStreamに格納し、java.util.zip.deflaterを利用して圧縮を行っている。Packetのサイズは60KByteとしているが、一旦の制限として42KByteまでを格納可能としている。 | |
| 124 | |
| 125 java.util.zip.deflaterには下記の3種類の圧縮方法がある。 | |
| 126 | |
| 127 \begin{itemize} | |
| 128 \item NO\_FLUSH : Streamに格納されたデータを最高率で圧縮を行う。Streamにある入力データが規定量に満たない場合は圧縮されない | |
| 129 \item SYNC\_FLUSH : これまでにStreamに格納されたデータの圧縮を行う。ただし圧縮率が低下する可能性がある | |
| 130 \item FULL\_FLUSH : SYNC\_FLUSH同様、これまでにStreamに格納されたデータの圧縮を行う。異なる点はこれまでの辞書情報がリセットされるため、圧縮率が極端に低くなる可能性がある | |
| 131 \end{itemize} | |
| 132 | |
| 133 ZRLEとjava.util.zip.deflaterを使用した圧縮では、圧縮後のデータ長を予測することができない。Packetが満杯になってしまうと、圧縮書き込みの途中であっても圧縮書き込みが中断する。そのため、Packetのサイズを余分に確保する必要がある。したがって最初から最大の60KByteではなく、42KByteに制限を行っている。TileLoopではデータの圧縮にNO\_FLUSHを利用していたが、圧縮後のデータがPacketの上限である60KByteを超えてしまうことが多発した。 | |
| 134 | |
| 135 これは圧縮されるための入力データの規定量が想定以上に多く、圧縮後のデータ長がMulticast Packetの上限を越えてしまったためである。 | |
| 136 | |
| 137 そこで圧縮率は悪くなるが、確実にPacketに書き込まれるSYNC\_FLUSHを利用し、ZRLEEの生成を行う。 | |
| 26 | 138 |
| 31 | 139 \newpage |
| 140 | |
| 32 | 141 |
| 142 図\ref{fig:TileLoopFlow} 中3ではPacketの上限まで行かなかった場合の分岐である。 | |
| 25 | 143 |
| 32 | 144 |
| 145 Phaseが変わるとそれまでに構成されたc1RectをRectangle Headerに書き出している。 | |
| 146 | |
| 25 | 147 |
| 26 | 148 \newpage |
| 25 | 149 |
| 32 | 150 |
| 151 | |
| 152 | |
| 153 | |
| 154 PacketにはMessage IDなどが入っているPacket Headerの他に、各RectangleのHeaderであるRectangle Headerが付いている。 | |
| 25 | 155 |
| 26 | 156 また、Phaseが変わるごとにRectangle を構成し直す必要があるため、各Phaseの終了時には確実にflushをする必要がある。 |
| 157 | |
| 158 Packetの上限は60KByte取っているがZlibの性質上、パケットの容量を予測して圧縮書き出しすることができず、圧縮時にPacketから溢れてしまう場合がある。そのため、初期上限を42KByteとしてPacketが一杯にになった際に上限を60KByteまで大きくする。 | |
| 159 | |
| 160 圧縮前の1Tileの大きさは最大で16KByteと考えられる。これを圧縮すると3 - 4 KByte程度であるので、その分のマージンを持っておくことで、読み込んだ最後のTileまできちんとPacketに書き込むことができる。 | |
| 25 | 161 |
|
21
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
162 |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
163 \section{Packet Lost} |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
164 WiftのMulticast Packetは確実に送られることが保証されていない。データに通し番号をつけて、欠落を検出することはできるが、再送処理は複雑であることが予想される。そこで、一定時間ごとに全画面のデータを送信することによってPacket Lostしても画面共有に影響はないと考える。 |
|
fa92cb03dac1
update chapter3 and add Blocking UpdateRectangle image
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
165 |
|
23
e18aecd16936
add new chapter4 and add coexistence img
riono <e165729@ie.u-ryukyu.ac.jp>
parents:
21
diff
changeset
|
166 |