# HG changeset patch # User Nobuyasu Oshiro # Date 1315551248 -32400 # Node ID ccdc3d3faafd0812abc7b6256f110a2549d6e7ba # Parent eaf3f3d169fe6d2ba87fc6818f02ec2655d3e1ae modify index.html diff -r eaf3f3d169fe -r ccdc3d3faafd OpenSourceConference/index.html~ --- a/OpenSourceConference/index.html~ Thu Sep 08 17:23:58 2011 +0900 +++ b/OpenSourceConference/index.html~ Fri Sep 09 15:54:08 2011 +0900 @@ -8,7 +8,12 @@ .center { margin-left: auto; margin-right: auto; +text-align: center; } +.textcenter { +text-align: center; +} + 2011/9/6 @@ -92,118 +97,134 @@
-

VNCによる画面共有の問題点

-
  • 一極集中型の為、VNC Server(VNCされる側)の負荷が重い。
    • -
  • 1本のEthernetからデータを配信するため、クライアントが増えれば通信速度が落ちてしまう。
    • -

    - -

    +

    通常のVNCの問題点

    + + + + + +
    +

    + +

    +     		+
  • VNC Serverの負荷が重い。
    • +
  • Server側の通信網1本への通信負荷が高い。
    • +
    - +
  • VNCに使われるCPUの使用率が100%になり、スループットが5分の1まで下がっている。
    • + +

    VNCの問題点の解決策

    -
  • クライアントからクライアントへ描画データを転送することで問題を解決させるTree VNCの設計と実装を行った。

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

    - クライアント同士を接続させる

    TreeVNCの利点

    -
  • クライアントが増えても負荷がある程度以上は掛からない。
    • -
  • 1本のEthernetへの負荷が減り、安定した通信できる。
    • - +

    通常のVNC TreeVNC
    - + - +
    +
  • クライアントが増えてもかかる負荷一定。
    • +
  • 通信網1本に対する負荷が減り、安定した通信ができる(有線)。
    • +
    + + +
    +

    TreeVNCの利点

    + + + + + + + + + +

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

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

    TreeVNCの設計

    -
  • クライアント同士を木構造で接続させ、描画データをクライアントからクライアントへ転送させる。
    • -
  • 木構造を管理するTop Proxy(TreeVNC Proxy)が一台あり、このTop ProxyだけがVCN Serverへ接続する。
  • TreeVNCのクライアントは最初にTop Proxyに接続を行う。
    • - +
  • データは木の下へと流れていく。
  • tightVNC ViewerのJava版(ver 1.3)を元にTreeVNCの実装を行う。
    • -
    - -

    発表内容

    • RFB Protocol
      • -
    • データ量の見積もり
      • +
    • データ転送量
      • +
    • ZRLE Encodingの問題
    • データ転送に用いたMulticastQueueについての説明
      • -
    • TreeVNCのデモ
      • +
    • 木構造の再構築
      • -
    • ZRLE Encodingの問題
    @@ -211,7 +232,22 @@

    RFB protocol

  • Remote Frame Buffer Protocol :
    GUI操作によるリモートアクセス用の通信プロトコル。VNCで用いられる。
  • 転送される画面(フレームバッファ)のデータは変更があった部分(差分)だけが矩形単位で送られる。
    • -
  • キーイベントやマウスイベントも扱っている。
    • + + + + + + +
    + + + + + +
    + +

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

    +
    @@ -219,33 +255,26 @@
    - + - -
  • 1~5までは使用するプロトコルのバージョン、認証方法、エンコーディング等の決定を行う。
    • -
  • 6からフレームバッファや、リモート操作の為キーボード・マウスの入力情報を行う通信が行われる。
    • -     + +
  • 1~5まではinitial seaquenceとなる。
    • +
  • 6以降は繰り返し行われる処理。画面のデータが転送されてくる。
    • +
    -

    RFB protocol

    -
  • FramebufferUpdateが描画のデータを転送する部分となる。
    • -
  • クライアントはFramebufferUpdateRequestで、VNC Serverへ関心のある領域についてリクエストを出す。
    • -
  • リクエストに対してのサーバの返信がFramebufferUpdateとなる。
    • -
  • Requestを出してupdateを受け取るということを繰り返し行い画面の共有を行っている。
    • -
    - -

    RFB Protocol

    -
  • FramebufferUpdateRequestの内容
    • +
  • FramebufferUpdateRequest:
    • +
  • 画面に差分が発生したらサーバから教えて貰うためのリクエスト
    • - +
    - - -
    - +
    @@ -290,32 +319,17 @@
    バイト数 
    型　　　[値]
    		 - - - - -incrementalについて - - - -
  • 0の場合、VNC Serverは指定された領域の矩形データを送ってくる。
    • -
  • 0以外の場合はその領域内で差分が発生した時に矩形データを送る。
    • -
    -
    +
  • このリクエストはTop Proxyだけが行う。

    • RFB Protocol

    -
  • FramebufferUpdate
    • +
  • FramebufferUpdate: 画面の更新データ
    • + - -
    - +
    @@ -324,7 +338,7 @@ - + @@ -342,8 +356,15 @@
    バイト数 
    型　　　[値]
    1
    U8         0
    U8          0
    		 message-type
  • 以下number-of-rectanglesの数だけ矩形のデータが続く
    • + - + +
    + + + + + + @@ -375,169 +396,444 @@ + + + + + + +
    バイト数
    型　　　
    		説明
    2encoding-type
    ...
    ...
    		PIXEL DATA
    
     		
+
 
 
    
+
+
 
 	
       
-      
-      
    
-	
    RFB Protocol
    
-	
  • 図を入れる
    • 
-	
  • 指定された領域の矩形を更新しているのが分かる図 
    • 
-	
    
-      
       
    
 	
    RFB Protocol
    
-	
  • RFB ProtocolにはFramebufferUpdateRequestだけではなく、キーボード・マウスポインタの入力を伝えるkeyEventやPointerEvent等もある。
    • 
-	
  • TreeVNCでは画面の共有を行いたいのでそれらのイベントに対しての実装は行っていない。
    • 
-	
    
+	
  • 例:FramebufferUpdate
    • 
+
+  
+    
+    
+  
+
+  
+    
+    
+  
+
+  
+    
+    
+  
+
+  
+    
+    
+  
+
+  
+    
+    
+  
+
+  
+    
+    
+  
+
    x-position336
    y-position388
    width724
    height449
    encoding-type16(ZRLE)
    ZRLE...
    
+
+	
+	  
+	    
+	    
+	    
+	    
+	    
    
+	      
+	      
+	      
+	      
+	      
+	      
    
+
+	  
       
       
    
-	
    負荷分散
    
-	
  • 負荷分散を行う上で重要： -> 転送するデータ量を見積もること 
    • 
-	
  • ネットワークの帯域やswtichにかかる負荷を把握するため。負荷を把握していないと負荷分散できているかどうかも解らない。
    • 
-	
  • RFB Protocolで送られてくるデータ量: -> 先頭の20バイトを読むことで見積もることができる。 
    • 
+	
    データ転送量
    
+	
    
+	  矩形の大きさと描画に必要なデータ量(単位:Byte)
+	
    
+	  
+	    
+	      
+	      
+	      
+	    
+
+	    
+	      
+	      
+	      
+	      
+	    
+
+	    
+	      
+	      
+	      
+	      
+	    
+
+	    
+	      
+	      
+	      
+	      
+	    
+
+	  
    矩形の大きさ \ エンコードRAWZRLE
    724 * 4491.3M0.8M
    1920 * 640.5M0.15M
    1920 * 10808.2M3.4M
    
+
+	
    
+	   
    
+	    RAW、ZRLE、ZRLEEエンコードのデータ量の比較
+	
    
 	
    
       
       
    
-	
    データ量の見積もり
    
-	
  • FramebufferUpdate(以下update)毎にデータを扱うためには、update1回分で送られてくるバイト量を知る必要がある
-	  
    （どこまで読みこめば終わりなのか知る必要がある）。 
    • 
-	
  • 先頭の20バイトを読むことでupdate1回分のバイト量を知ることができる(厳密にはエンコード次第だが...)。 
    • 
-	
  • updateは最初に送られてくる情報に矩形の横と縦幅(width,height)が含まれていてそれと扱われるエンコードによって全体のデータ量を計算することができる。
    • 
+	
    データ転送量
    
+	
  • クライアントが60台の時の通常のVNCと、２分木構成にしたTreeVNCの通信網への負荷の理論値を考える。
    • 
+	
+	  
+	    
+	    
+	    
+	  
+	  
+	    
+	    
+	    
+	  
+	
    通常のVNCTreeVNC
    最大負荷 N * データ量(クライアントの数に比例)  (M+1) * データ量
    
+	
    クライアントの数をN、木構造の子供の数をMとする 
    
+	
  • N = 60、 M = 1 となる。
    • 
+	
  • 724 * 449 の画面分のデータ(0.8M)を送信するとする。 
    • 
+	
 	
    
+	
+	
    
+	  
    データ転送量
    
+	
     理論値
+	
+	  
+	    
+	    
+	    
+	  
+	  
+	    
+	    
+	    
+	  
+	
    通常のVNCTreeVNC
    最大負荷48M2.4M
    
+	
+	  
+	    
+	    
+	  
+	  
+	    
+	    
+	  
+	    
    
+	  
    通常のVNCTreeVNC
    
+		
+	      
+	      
+	    
    
+	  	  
+	  
    クライアント:60台 TreeVNCは2分木でTreeを構成 
    
+	  
+      
    
       
       
    
-	
    データ量の見積もり
    
-	
  • ZRLEエンコードの場合
    • 
-	  
  • 最初の4bitにどれだけのデータ量が送られてくるのかという情報が送られてくる。
    • 
+	
    エンコード
    
+	
  • MacintoshでVNCを行うとZRLEを使うことができる。
    • 
+	
  • データ量がRAWデータの約4分の1ですむ。
    • 
+	
  • TreeVNCではこのZRLEを扱っている。
    • 
+      
    
+      
+      
    
+	
    ZRLE
    
+	
  • ZRLE : Zlib Run-Length Encoding 
    • 
+	
      
+	  
    • Zlib圧縮(gzip)されたデータ扱うエンコーディング。
      • 
+	
    
+	  
  • 最初の4バイトにはZlibのデータの長さが、続いてZlibのデータが送られてくる。
    • 
 	  
-	  
+	  
    
-	      
+	      
-	    
 	    
-	    
 	    
-
 	  
    
 	    
    	
       バイト数
    型　　　[値]
    型　
    		
 	      説明 
 	    
    
 	      4
 	      U32
 	      length
 	    
    
 	      length
 	      U8 array
 	      zlibData
 	    
    
 	      
-	  
-	
      
-	  
    • ZlibDataはgzipされたデータのこと
      • 
-	  
    • 
+
+	  
    • Zlibデータ
      • 
+	  
        
+	    
      • Zlibデータは辞書を元にデータの解凍を行う
        • 
 	
      
-	      
+	
    • 辞書がなければデータを正しく解凍できない
      • 
+	
    
+      
+      
    
+	
    ZRLEの問題
    
+	
  • 辞書はZlibデータの最初に送られてくる。
    • 
+	
  • ZRLEのデータを最初から送ることができれば、辞書も送ることができる。
    • 
+	
  • データの途中から送ると辞書は送られず、正しく解凍を行うことができない。
    • 
+	
+	  
+	    
+	
+	
+	  
    
+	  
+	  
+	    
+	  
    
 	
    
       
       
    
-	
    データ量の見積もり
    
-	
  • 先頭20バイトを読みupdate一回分のデータ量を調べる。
    • 
-	
  • update1回分のデータを読み込み次のクライアントに送信する。
    • 
-	
  • また、描画データを送信すると同時に画面の更新を行うようにする。
    • 
-	
  • 描画データの管理はMulticastQueueで行った。 
    • 
+	
    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のデータ量
    
+	
+	  
+	    
+	    
+	  
+	
    
+	      
+	    
+	      毎回辞書が付与される分データ量が増えるのではないか？
+	    
    
+      
    
+      
+      
    
+	
    圧縮したデータの転送
    
+	
  • 一度ZRLEEに圧縮してしまえば、データはそのまま流すことができる。
    • 
+	
  • また、データの転送は複数いる子へ並列に行われる。
    • 
+	
    
+	  
+	  
    
+	
  • MulticastQueueクラスを用いてデータの転送を行った。
    • 
       
    
       
       
    
 	
    MulticastQueue
    
-	
  • MulticastQueueはjava.util.CountDownLatchを用いて実装されたクラスである。 
    • 
-	
  • クライアントから接続されると、データ転送用のスレッド(sender)が走る。 
    • 
-	
  • このスレッドは次に流すデータが来るまでは待機して置かなければならない。そして流すべきデータがくるとまた動き始めなければならない。
    • 
-	
  • このスレッドの待機・解放を行うのがMulticastQueueとなる。 
    • 
+	
  • データを順序よく読み込ませるクラス：MulticastQueue
    • 
+	  
+	    
+	      
+	      
+	      
+
+	      
+		
+		
+	      
+	    
    
+		
+		
+		
+	      
    
+		  次のデータがなければwaitする
+		
+		  データがputされ次第読み込みを再開する
+		
    
+	      
    
+		  MulticastQueueは、java.util.CountDownnLatchにより実装されている。
+	      
    
+	
    
+      
 
-	
+      
+
       
       
    
 	
    MulticastQueue
    
-	
  • MulticastQueueの図を入れる。 
    • 
-	
    
-	
-	  接続されてきた時点からデータの送信が始まる。データは読み込まれるまでメモリ上に残っている。
-	
-	
    
-	
    
+	
+	  
+	    
+	  
+	  
+	    
+	      
+	      
+	    
+	
    
+	  
+	    
+	    
  • putでデータの入力
    • 
+	    
  • pollでデータの取り出し
    • 
+	    
  • Proxyは常に最新のデータだけを保持
    • 
+	    
    
+				
+	      
+		
  • クライアントは最新のデータから読み込み始める。
    • 
+	      
    
+	      
    実際のソースでみてみる
    
+      
       
       
    
 	
    MulticastQueueの問題点
    
-	
  • Clientがデータを読み込まないとデータが溜まりメモリを圧迫してしまう。 
    • 
-	
    
-	
-	
    
+	
  • クライアントがデータを読み込まない時...
+	
+	  
+	    
+	    
+	  
+	
    
+	      
+	    
+	      
+	    
    
+	    
  • 読み込まれないデータはProxyのメモリに残り続ける。
    • 
 	
    
       
       
    
 	
    MulticastQueueの問題点
    
-	
  • 解決策
    • 
-	
    
-	
-	
    
-	  
-	  
  • TimeOut(TO)スレッドを走らせ、一定の時間データを読み込まなければ代わりにこのTOが読み込むようにする。
    • 
-	      
+	
  • TimeOut(TO)スレッドを走らせ、最新のデータから取得できるようする。
    • 
+	
+	  
+	    
+	    
+	  
+	
    
+	      
+	    
+	      
+	    
    
+	  
  • どこからも参照されないデータはProxyのメモリから削除される。
    • 
 	
    
       
       
    
-	
    TreeVNCのデモ
    
-	
  • では実際に動かしてみる。
    • 
+	
    まとめ
    
 	
  • 
 	
    
       
       
    
-	
    エンコードの問題　
    
-	
  • ZRLE : Zlib Run-Length Encoding 

    • データをZlib圧縮扱うエンコーディング。
-	  
    Macintoshでもこのエンコードは使うことができる。
-	
  • Rawエンコードより約1/8倍少ないデータ量ですむ。
    • 
-	
  • 解凍器(Deflater)は辞書を持っていて、その辞書を元に解凍を行う。
    • 
-	
  • この辞書を吐き出す(flush)する機能がJavaにはなかった。
    • 
-	
    
-      
-      
    
-	
    ZRLEの問題
    
-	
  • 解凍に必要な辞書を取り出すことができないため、ZRLEのデータはそのまま投げるだけでは正しく解凍されない。
    • 
-	
  • そこで、VNC Serverへ接続するTop ProxyはZRLEで送られてきたデータを毎回新しく圧縮し直すという方法をとった。
    • 
-	
  • 一度圧縮し直されたデータはそのまま流すことができる。よってクライアント側では圧縮し直す必要はない。 
    • 
-     	
  • このエンコードはZRLEE(Economy)として扱うことにした。
    • 
+	
    テスト環境の構築
    
+	
  • CUI版のVNCクライアントを作成
    • 
+	
  • 48台あるクラスタでCUI版のクライアントをはしらせてVNCをかけさせる。
    • 
+	
  • 最初の1台目と48台めをGUI版のクライアントで接続を行い見比べてみる。 
    • 
 	
    
       
       
    
-	
    TreeVNCの利点と欠点
    
-	
      
-	  
    • ケーブル1本への負荷が減る。一極集中型よりスループットを維持できる。
      • 
-	  
    • 無線を使われると遅くなる。
      • 
-	
    
+	
    TreeVNCの発端
    
+	
  • 大学のB3でうける授業の1つ、programming4で作り始めたことがきっかけ。
    • 
+	
  • programming4はグループで作りたいものを提案して作る授業。 
    • 
+	
  • 授業が終わっても改良を加えていた。
    • 
+	
  • B4になりこの場で発表してみることになった。
    • 
 	
    
       
-      
    
-	
    テスト環境について
    
-	
  • CUI版のVNCクライアントを作成
    • 
-	
  • 48台あるクラスタでCUI版のクライアントをはしらせてVNCをかけさせる。
    • 
-	
  • 最初の1台目と50台めをGUI版のクライアントで接続を行い見比べてみる。 
    • 
-	
    
-      
-      
    
-	
    
-	
  • 
-	
  • 
-	
    
-      
+
-      
    
-        
    
-	
  • 
-	
    
+-->