Java による授業向け画面共有システムの設計と実装

大城信康谷成雄

琉球大学並列信頼研究室

本日の内容

友人と作ったJavaによる画面共有システム「TreeVNC」について

TreeVNCを作るにあたって学んだJavaでの並列プログラミングの仕方やVNCの話

TreeVNCの目的と背景

大学の講義中、スクリーンに映されている画面は後ろの席程見えずらい。

その問題を手元のPCにも写せるようにすることで解決しようと考えた。

60人以上での画面共有を行うことを目標とする。

VNCによる画面共有

画面を共有する方法 -> VNC

VNC: Virtual Network Computing
ネットワークを介してコンピュータを遠隔操作するプログラム

VNCのリモートPCの画面を写す機能を利用する。

VNCを用いての画面共有

まず、iMacで複数のPCからVNCをかけてみた。

-> 10台と繋ぐ前にVNCでの画面がカクカクに...

さらにCPU使用率も跳ね上がった。

通常のVNCの問題点

VNC Serverの負荷が重い。

Server側の通信網1本への通信負荷が高い。

実際に測ってみた

通常のVNCの問題点

1台と48台でVNCをかけた時のスループットとサーバ側のCPU使用率

	スループット(単位:Byte)	CPU使用率
1台	20M(最大速度)	55%
48台	4M	100%

VNCに使われるCPUの使用率が100%になり、スループットが5分の1まで下がっている。

通常のVNCの問題点

サーバへのCPU負荷が高い

1本の通信網への負荷が高い

VNCの問題点の解決策

クライアントを木構造で接続させるTreeVNC

TreeVNCの利点

通常のVNC	TreeVNC

クライアントが増えてもかかる負荷一定。

通信網1本に対する負荷が減り、安定した通信ができる(有線)。

TreeVNCの利点

通常のVNC	TreeVNC

	通常のVNC	TreeVNC
最大負荷	N*データ量 (クライアントの数に比例)	(M+1) * データ量

クライアントの数をN、木構造の子供の数をMとする

TreeVNCの設計

木構造での接続

TreeVNCのクライアントは最初にTop Proxyに接続を行う。

データは木の下へと流していくようにする。

tightVNC ViewerのJava版(ver 1.3)を元にTreeVNCの実装を行う。

今回の主な内容

RFB Protocol
データ転送量
ZRLE Encodingの問題
データ転送に用いたMulticastQueueについての説明
木構造の再構築

RFB protocol

Remote Frame Buffer Protocol :
GUI操作によるリモートアクセス用の通信プロトコル。VNCで用いられる。

1~5まではinitial seaquenceとなる。

6以降は繰り返し行われる処理。画面のデータが転送されてくる。

画像の更新(FramebufferUpdate)

転送される画面(フレームバッファ)のデータは変更があった部分(差分)だけが矩形単位で送られる。

□ で囲まれている矩形のデータだけが送られてくる。

RFB Protocol

FramebufferUpdateRequest:

画面に差分が発生したらサーバから教えて貰うためのリクエスト

バイト数	型　　　[値]	説明
1	U8 3	message-type
1	U8	incremental
2	U16	x-position
2	U16	y-position
2	U16	width
2	U16	height

このリクエストはTop Proxyだけが行う。

RFB Protocol

FramebufferUpdateRequest:画面の更新データ

バイト数	型　　　[値]	説明
1	U8 0	message-type
1	U8	padding
2	U16	number-of-rectangles

以下number-of-rectanglesの数だけ矩形のデータが続く

バイト数	型	説明
2	U16	x-position
2	U16	y-position
2	U16	width
2	U16	height
4	U32	encoding-type
...	...	PIXEL DATA

RFB Protocol

例:FramebufferUpdate

x-position	336
y-position	388
width	724
height	449
encoding-type	16(ZRLE)
ZRLE	...

データ転送量

矩形の大きさと描画に必要なデータ量(単位:Byte)

矩形の大きさ \ エンコード	RAW	ZRLE
724 * 449	1.3M	0.8M
1920 * 64	0.5M	0.15M
1920 * 1080	8.2M	3.4M

RAW、ZRLE、ZRLEEエンコードのデータ量の比較

データ転送量

クライアントが60台とした時、通常のVNCと、２分木構成にしたTreeVNCの通信網への負荷の理論値を考える。

	通常のVNC	TreeVNC
最大負荷	N * データ量(クライアントの数に比例)	(M+1) * データ量

クライアントの数をN、木構造の子供の数をMとする

N = 60、 M = 2 、使用するエンコードはZRLEとする。

724 * 449 の画面分のデータ(0.8M)を送信するとする。

データ転送量

理論値

	通常のVNC	TreeVNC
最大負荷	48M	2.4M

通常のVNC	TreeVNC

クライアント:60台 TreeVNCは2分木でTreeを構成

エンコード

MacintoshでZRLEを使ってVNCを行うことができる

データ量がRAWデータの約4分の1ですむ。

TreeVNCではこのZRLEを扱っている。

ZRLE

ZRLE : Zlib Run-Length Encoding

Zlib圧縮(gzip)されたデータ扱うエンコーディング。

最初の4バイトにはZlibのデータの長さが、続いてZlibのデータが送られてくる。

バイト数	型	説明
4	U32	length
length	U8 array	ZlibData

VNCでZRLEを使う場合は単一のzrleストリームを使ってデータの解凍を行う。

問題が発生

ZRLEの問題

Zlibデータは辞書を元にデータの解凍を行う

辞書がなければデータを正しく解凍できない

ZRLEの問題

辞書はZlibデータの最初に送られてくる。

もしも、ZRLEのデータを最初から送っているのなら、辞書も送ることができる。

データの途中から送ると辞書は送られず、正しく解凍を行うことができない。

Zlibデータを解凍するjava.util.zip.Deflaterがエラーを吐く

ZRLEE

そこで、Top ProxyにZRLEのデータを再度圧縮し直すことで辞書を付けてもらうことにした。以下はその部分のソースである。

Deflater nDeflater = deflater; // new Deflater();
LinkedList out = new LinkedList();
unzip(inflater, inputs, 0 , out, INFLATE_BUFSIZE);
// dump32(inputs);
int len2 = zip(nDeflater, out, 0, bufs);

この圧縮し直したデータはZRLEEと名付けた。

ZRLEE

クライアント側は毎回新しいZRLEのストリームを使うようにする。

	    if (rfb.updateRectEncoding==RfbProto.EncodingZRLEE) 
   	       zrleInStream = null;
	    if (zrleInStream == null)
	       zrleInStream = new ZlibInStream();

JavaではZlibの辞書の取り出しが実装されていなかった為、このような方法をとることになった。

ZRLEに比べるとデータ量は増えないのか...?

ZRLEEのデータ量

毎回辞書の付与がされるため、ZRLEに比べるとデータ量が増える...?

ZRLEと比較してみるとデータ量は変わらないことが判明

ZRLEEのデータ量

1920*1080の描画にかかったデータ量

	ZRLE	ZRLEE
データ量	3.4M	3.2M

原因

ZRLEEは送られるデータ毎で最適な辞書が使われる。

ZRLEEを使う利点

データ量が少なくすむ

ZRLEよりも少なくですむ可能性がある。
圧縮率が高い為プロキシのメモリを食わないですむ。

そのままデータを流すことができる

圧縮作業は一回ですむ。

圧縮したデータの転送

一度ZRLEEに圧縮してしまえば、データはそのまま流すことができる。

-> 気にするのはスループットだけでいい。

また、データの転送は複数いる子へ並列に行われる。

MulticastQueueクラスを用いてデータの転送を行った。

MulticastQueue

MulticastQueue:データを順序よく読み込ませるクラス


次のデータがなければwaitする	データがputされ次第読み込みを再開する

MulticastQueueは、java.util.CountDownnLatchにより実装されている。

MulticastQueue

	putでデータの入力 pollでデータの取り出し Proxyは常に最新のデータの参照を渡す
	クライアントは最新のデータから読み込み始める。

実際のソースでみてみる

MulticastQueueの問題点

クライアントがデータを読み込まない時...

読み込まれないデータはProxyのメモリに残り続ける。

MulticastQueueの問題点

TimeOut(TO)スレッドを走らせ、最新のデータから取得できるようする。

どこからも参照されないデータはProxyのメモリから削除される。

木の構成手順

requestHostName();
プロキシに対してホストのアドレスを要求する関数。

木の構成手順

transferParentAddress();
クライアントに接続先を教える関数。

実際にクライアントにおくっているデータは
parentAddress -> 親のアドレス
parentNum -> 親の番号
treeNum -> 自分の木の番号
leaderFlag -> リーダフラグ
の４つである。
リーダーは子供の中で一番若い番号の人がなる。
リーダーフラグは木の再構成の際に使用する。

木の構成手順

connectAndAuthenticate();
プロキシから受け取ったデータをもとに接続を開始する関数。

木の構成手順

新しいクライアントが来るたびに今まで説明した３つの関数を呼び出す。

木の構成手順

ここで接続先がクライアント１になっているがこれはプロキシ側で
親の番号 = (自分の番号 - 1) / 親に対する子どもの数
を計算してどの親に接続させれば良いかを決めてクライアントに報告している。
このように番号で木を管理している。

木の再構成手順

クライアント１が落ちた時の再接続の処理についての説明。

木の再構成手順

lostHost();
木を構成する際にリーダを決めたが、そのリーダだけが呼び出す関数。
プロキシに対し落ちた親（クライアント１）の情報を報告する。

木の再構成手順

reportLastNode();
ラストノードに対し落ちたクライアントの代わりをするように命令を出す。

木の再構成手順

connectAndAuthenticate();
プロキシから受け取ったデータをもとに接続を開始する関数。

木の再構成手順

transferParentAddress();
落ちた親の子供たちに対し新しい親のアドレスを報告する関数。

木の再構成手順

connectAndAuthenticate();
プロキシから受け取ったデータをもとに接続を開始する関数。

最後に

今回のTreeVNCは大学の授業「programming4」で作り始めた。

Javaは基本知識だけ、VNCの仕組みについては全く知らない状態からのスタートあった。

木の再構成、MulticastやZRLEの問題にも出会ったがなんとかクリアすることができた。

Javaでの分散プログラミングは考えていたよりも楽であった。

ゼミ: 2011/ 9/ 6

並列信頼研

Java による授業向け画面共有システムの設計と実装

琉球大学 並列信頼研究室

本日の内容

TreeVNCの目的と背景

VNCによる画面共有

VNCを用いての画面共有

通常のVNCの問題点

通常のVNCの問題点

通常のVNCの問題点

VNCの問題点の解決策

TreeVNCの利点

TreeVNCの利点

TreeVNCの設計

今回の主な内容

RFB protocol

画像の更新(FramebufferUpdate)

RFB Protocol

RFB Protocol

RFB Protocol

データ転送量

データ転送量

データ転送量

エンコード

ZRLE

ZRLEの問題

ZRLEの問題

ZRLEE

ZRLEE

ZRLEEのデータ量

ZRLEEのデータ量

ZRLEEを使う利点

圧縮したデータの転送

MulticastQueue

MulticastQueue

MulticastQueueの問題点

MulticastQueueの問題点

木の構成手順

木の構成手順

木の構成手順

木の構成手順

木の構成手順

木の構成手順

木の構成手順

木の構成手順

木の構成手順

木の再構成手順

木の再構成手順

木の再構成手順

木の再構成手順

木の再構成手順

木の再構成手順

最後に

質問タイム

琉球大学並列信頼研究室