\documentclass[submit]{ipsj}
%\documentclass[submit,draft]{ipsj}
%\documentclass[submit,techreq]{ipsj}
\def\newblock{} 
%\usepackage[dvips]{graphicx}
\usepackage[dvipdfmx]{graphicx}
\usepackage{latexsym}
\usepackage{listings}

\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\|{\verb|}

\setcounter{巻数}{53}
\setcounter{号数}{2}
\setcounter{page}{1}

\受付{2011}{11}{4}
%\再受付{2011}{7}{16}   %省略可能
%\再再受付{2011}{7}{20} %省略可能
\採録{2011}{12}{1}

\begin{document}


\title{VNCを用いた授業用画面共有システムの設計・開発
}

\etitle{Design and implementation of Screen Sharing System with VNC for lecture
}

\affiliate{IPSJ}{情報処理学会\\
IPSJ, Chiyoda, Tokyo 101--0062, Japan}


\paffiliate{JU}{情報処理大学\\
Johoshori Uniersity}

\author{谷成 雄}{Taninari Yu}{IPSJ}[you@cr.ie.u-ryukyu.ac.jp]
\author{大城 信康}{Oshiro Nobuyasu}{IPSJ}
\author{河野 真治}{Kono Shinji}{IPSJ}


\begin{abstract}
VNCを用いて多人数で画面共有を行う際、一つのコンピュータに同時にアクセスすると
CPU使用率やネットワークに対する負荷が高くなってしまう。
そこで本研究室ではクライアントを木構造に接続させるTreeVNCを設計し、実装した。
現在TreeVNCはMulticastを用いて通信を行なっている。
TreeVNCをBroadcastを用いた通信に変更するとパフォーマンスどの程度変わるのかを検証するために
Broadcastを用いた通信に変更するためにはどのような変更が必要になってくるのかを考える必要がある。
本研究では、TreeVNCをBroadcastで行うためにどのような変更が必要か考察し設計を行う。
\end{abstract}


\begin{jkeyword}
情報処理学会論文誌ジャーナル，ネットワークプロトコル，マルチキャスト，画面共有
\end{jkeyword}

\begin{eabstract}
This document is a guide to prepare a draft for submitting to IPSJ
Journal, and the final camera-ready manuscript of a paper to appear in
IPSJ Journal, using {\LaTeX} and special style files.  Since this
document itself is produced with the style files, it will help you to
refer its source file which is distributed with the style files.
\end{eabstract}

\begin{ekeyword}
IPSJ Journal, Network Protocol, Multicast, Screen Sharing
\end{ekeyword}

\maketitle

%1
\section{研究背景と目的}
普段授業を行う際、プロジェクタなどを使って授業を進めている。
しかし、後ろの席から見えにくいなどの不便を感じることがよくある。
授業をうけている生徒の手元にパソコンがあるならば、そこに先生のスライドを
表示して授業を進めれば後ろの席に座っても手元に画面があるので見えづらいという問題は解消される。

Ustream Producerを使用することで画面を生徒のコンピュータに配信することができる。
しかし、使用してみた結果解像度が低くて、ソースコードを読む際などに見えづらいという問題が発生した。

他にもVNCを使えば、スライドを生徒の手元の画面に表示することができる。
VNCについては次の章で説明する。
VNCは共有したい画面の解像度のままのデータを配信することができる。
しかし、多人数の生徒が先生のパソコンに同時に接続してしまうとサーバ側が送信するデータの量が増えるので
処理性能が落ちて授業の進行に画面がついていかなくなってしまう。
この問題は一つのコンピュータに多人数が同時に繋がるときに起こる問題である。

そこでクライアントをTree構造に接続させていくことによって処理を分散させることにした。
クライアントをTree構造に接続させることによって、
見えない部分でスイッチに対する負荷が増えている分サーバに対する負荷が軽減している。

今回TreeVNCはMulticastで実装しているが、Broadcastで実装されたものとどちらが性能がいいのか
どれくらい性能差が出るのかという疑問がでてきた。

今回、Broadcastを設計する際にいろいろな課題が見えてきたので本論文では、Multicastを用いたTreeVNCの実装と
Broadcast版の設計について以下に詳しく説明していく。


%2
\section{VNCについて}
VNC(Virtual Network Computing)は、RFB プロトコルを用いて画面を送信して
操作権を与えるリモートデスクトップソフトである。
VNCはサーバ側とクライアント(ビューア)側に分かれていて、サーバを起動し、
クライアントがサーバに接続を行い遠隔操作を可能にする。

%2.1
\subsection{RFB Protocol}
RFB (remote frame buffer) プロトコルは、GUI操作をリモートアクセスで行うためのプロトコルである。
画面の描画の更新は画面の差分が発生した部分を矩形毎で送り描画される。
また、画面の描画データに使われるエンコードが多数用意されており、
また独自のエンコードを実装することもできるシンプルなプロトコルである。


%3
\section{TreeVNCの方針}
まず、多人数が参加している授業でVNCを使う場合に起こる問題は、
最初で述べたように、一つのコンピュータに多人数が繋がり、
理性能が大幅に落ちてしまうところが問題である。
%この問題を解決する為に、一つのコンピュータに多人数がつながるのではなく
目的のコンピュータに繋がっているコンピュータに繋げれば目的の画面を共有することができる。

この問題を解決する為に、クライアント同士を接続させ、
画面描画のデータを受け取ったクライアントが次のクライアントにデータを流すという方法を考えた。

%一つのコンピュータに多人数がつながるのではなく目的のコンピュータに繋がっている
コンピュータに繋げれば目的の画面を共有することができる。                       

画面共有を行いたいクライアントが一種のVNCサーバ自体にもなる。
%誰が誰に繋げばよいかを管理することが出来れば多人数が同時に画面共有をスムーズに行うことが出来ると考えた。

また、クライアント同士の接続はツリー構造で行うことで管理がしやすくなると考えた。
クライアント同士の接続の管理はツリーの一番上にいるPC(Top)で行い、このTopだけがVNCサーバへ接続を行うようにする。

今回作成したTreeVNCは、上記の実装でツリー状にクライアントを接続していくように実装を行った。
画面の共有だけを行うように実装した。



\subsection{Treeの構成}
Topはクライアントが接続してくるたびにjava.util.LinkedListにクライアントの情報を追加していく。

クライアントからアクセスが来るたびにスレッドを作成しているので、
複数のクライアントが同時に接続してきても対応することができる。

しかし、多数のスレッドが同じjava.util.LinkedListなどの共有資源に対して同時に接続を行うと
共有資源の情報が正しく更新されない可能性が出てくる。

このような共有資源を更新する際はjavaのsynchronizedメソッドを使用して複数のスレッドが共有資源
に同時にアクセスすることができないようにした。

TopはtreeBranch(木の分木数)を定数で持っていて
クライアントが接続してくるごとにcounterをインクリメントしていき
LinkedListの(counter - 1)/treeBranche番目に入っている親の情報を
接続してきたクライアントに教えることで木を構成することができる


\subsection{Treeの再構成}
木を構成することはできたが途中のクライアントが落ちてしまった場合に木を再構成しなければならない。
木を再構成する手順は以下の用に行う。
\begin{enumerate}
\item 子供が親が落ちたことをTopに対して報告する。
\item Topは報告を受けると番号の一番大きいノード(最後のノード)に対して落ちた親の代わりになるように報告する。
\item Top命令を受けたクライアントはTopの指定された場所に接続をしなおす。
\item Topはクライアントのリストを更新して、親が落ちた子供たちに新しい親の情報を教える。
\item 親が落ちた子供たちは新しい親に対して接続を行う。
\end{enumerate}
このようにして木を再構成することができる。
以下のソースは、親が落ちた子供が接続してきた時に、子供全員の接続を待つ部分のコードの一部である。

\begin{verbatim}
  final int TIMEOUT = 3000;
  if (passNumber == 0) {
    passNumber++;
    wait(TIMEOUT)
    passNumber = 0;
    } else {
    if (++passNumber == TREEBRANCH) {
      notifyAll();
      passNumber = 0;
      } else {
      wait(TIMEOUT);
      }
  }
\end{verbatim}

上記のコードでは落ちた子供たちの報告を待ち合わせることができる。
TREEBRANCHは木を構成する際の分木数であるフィールド変数としてfinalで定義されている。
passNumberは報告する子供たちを数えるためのカウンタである。
プロキシは子供分の報告全て揃うと子供たちに新しい親の情報を流し始める。
TIMEOUTが設定されているのは、子供が報告の際に落ちて報告が届かない場合があるのでそれに対応したものである。

\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.3]{fig/reconnectionCollaboration01.pdf}
\end{center}
\caption{
再接続の様子
}
\label{figure:reconnection}
\end{figure}

図1は接続の様子を記したコラボレーションダイアグラムである。以下に関数の説明をする。

\begin{enumerate}
  \setlength{\parskip}{0cm} % 段落間
  \setlength{\itemsep}{0cm} % 項目間

  \item lostHost()は親が落ちたことを報告する関数である。
  \item reportLastNode()は番号の一番大きい(最後のノード)に対して親の代わりをするように命令する関数である。
  \item listUpdate()はプロキシが持つクライアントのリスト情報をアップデートする
(落ちたノードを削除し最後のノードのアドレスをそこに追加する)。
  \item lostHost()は上記で説明したとおりである。なぜ間に2と3が呼ばれているのかというと最初にlostHost()が呼ばれて、
listUpdate()が終わるまで他のノードの報告はブロックされるからである。Client4が先に報告に行く場合もある。
  \item waitReply.start()はクライアントはwaitReplyというクラスをmainスレッドとは別にスレッドを作成して走らせている。
もしプロキシからの命令が来るとクライアントはプロキシから指定された場所に接続を行う。


\begin{figure}[tb]
\begin{center}
\includegraphics[scale = 0.4]{fig/reconnectionCollaboration02.pdf}
\end{center}
\caption{
再接続の様子
}
\label{figure:reconnection2}
\end{figure}


  \item replyChildlen()はListing1で説明したとおり全クライアントが報告に来るまで待った後、
親が落ちた子供たちに対して新しい親の情報を報告する関数である。

  \item reConnection()はプロキシから来た情報をもとにVNC接続を行う関数である。

\end{enumerate}

以上の関数を用いることでクライアントが落ちても木を再構成することができる。


\section{リファクタリング}
はじめにTreeVNCを作成する際に、Top用のプログラムとクライアント用のプログラムを別々に作成していた。

Topとクライアントのプログラムはだいたい同じことをしているのにソースが2つあるので共通部分を片方を変更するすると、
もう片方も同じ変更をしなければならない。片方の変更を忘れるとプログラムが正常に動作しなくなることもある。

2つのコードを変更するのは手間がかかるので、同じ部分は一つのプログラムにまとめることにした。

リファクタリングを行う際にabstract factoryを使用して2つのプログラムを一つにまとめることができた。


\section{圧縮の問題}

VNCで扱うRFB プロトコルには、使えるエンコーディングのタイプの1つとしてZRLE(Zlib Run-Length Encoding)がある。
ZRLEはZlibで圧縮されたデータとそのデータのバイト数がヘッダーとして付けられ送られてくる。

Zlibはフリーのデータ圧縮及び解凍を行うライブラリである。
可逆圧縮アルゴリズムの圧縮と解凍が行えるjava.util.zip.deflaterとjava.util.zip.inflaterを実装している。


\subsection{java.util.zip.deflaterの実装の問題}
Zlib圧縮は辞書を持っていて、その辞書に登録されているデータを元に解凍が行われる。
しかし、java.util.zip.deflaterは現在持っている辞書を書き出すこと(flush)ができないことが分かった。
辞書を書きだすことができない為、Zlib圧縮されたデータを途中から受け取ってもデータが正しく解凍を行うことができない。
%元々のZlibの規約にはこの辞書をflushする機能があったがJavaには実装されていなかった。                                

\subsection{ZRLEE(ZRLE Economy)}
そこで、TopがZRLEで受け取ったデータをunzipし、データをzipし直して最後にfinish()
をいれることで初めからデータを読んでいなくても解凍を行えるようにした(毎回新しい辞書を使うようにした)。

このエンコードはZRLEEエンコードと定義した。
一度ZRLEEエンコードに変換してしまえば、そのデータをそのまま流すだけで良い。
よって変換はTopが行う一回だけですむ。

ただし、deflater,inflaterでは前回までの通信で得た辞書をクリアしないといけないため、
Topとクライアント側では毎回新しく作る必要がある(クライアント側はinflaterだけ)。
また、ZRLEEはクライアント側が対応していなければならないという問題がある。

\subsection{ZRLEとZRLEEのデータ圧縮率の比較}
RAW,ZRLE,ZRLEEのデータ量の比較を行った。
図6は1920 * 1080の画面の全描画にかかるデータ量を測った結果を示した図である。
ZRLEEの方がデータ量が少なくですんでいる。
これは、ZRLE(Zlib)が初めに送られた辞書を用いての解凍が余り有効的に働いていない場合があるからだと思われる。
つまりVNCの場合はZRLEEの様に毎回辞書のデータを付加させて送ってもデータ量に差がでない可能性があることが分かった。


\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale = 0.5]{fig/compare_encoding.eps}
\end{center}
\caption{
RAW,ZRLE,ZRLEEによる1画面(1920*1080)描画にかかるデータ量。
x軸はピクセル数、y軸はバイト数を表している。
}
\label{figure:splaying}
\end{figure}

\section{授業などでの使用}
実際の授業で実装したTreeVNCを使用してみた。
実際に使ってみての感想などを聞いてみると良かったなどの意見がでてきた。
しかし、実際に使ってみて新しい問題などもみつかった。

TreeVNCでは各クライアントが自分自身のタイミングで画像データを取得できるように
MulticastQueueを作成して、データをQueueにもたせている。

クライアントが接続を持ったままsuspend(停止)してしまうとQueueにデータがたまり続けてしまい
Memory Overflowを起こしてしまう。そこで、TimeOutスレッド作成して、
一定時間取得されないデータはQueueから削除して、クライアントが読み込みを
開始した際に、消された次に入っているデータを送るというように設計されている。

一つ目の問題は画像の更新が少ない画面の共有を行う際に、たまにデータが送られてこないとう問題がある。
この問題はおそらく上記で説明したTimeOutスレッドが更新データを落としてしまっているのではないかと考えられる。

二つ目の問題は発表者が複数いる際は発表者が変わるごとにTopを起動しなおさなければならないということである。
この問題については次の章でもう少し詳しく説明する。


\section{UserInterfaceの設計と実装}
普通VNCで接続を行う際にクライアントを起動する際に相手のアドレスを指定しなければならない。

そこで、TreeVNCはクライアントが起動する際にBroadcastパケットを送信して同じセグメント内に、
Topが起動しているかどうかを調べ、起動していたら起動しているTopの一覧を表示するように設計・
実装を行った。

これによりクライアントは起動する際に何も打ち込まなくても起動することができる。

前章で説明したように、ゼミなど発表者が多数いる際に、TreeVNCを使用すると発表者ごとにTopを立て直す必要がある。
このような際にボタンひとつで、画面共有を行う対象を変更できると便利である。
しかし、VNCでは違う画面サイズのデータが流れてくると落ちてしまう仕様になっている。

そのため、画面を切り替える際はクライアントに画面が切り替わることを教えるプロトコルを作成する必要がある。
上のような設計で画面の切り替えは今後実装する予定である。


\section{Broadcast版の設計}
この章ではBroadcast版を設計する際に見えてきた問題点などを解説する。


\subsection{Broadcastパケットの性質}
Broadcastパケットの性質とし大きすぎるデータの送信などができないという性質がある。
実際にBroadcastパケットでどの程度の大きさのデータが送れるのかを測ってみたところ
有線のBroadcastだと約64000byteまでのデータ量だと送信することができた。
無線のBroadcastの場合も約64000byteのデータを送信することができたが、無線だと不安定で
データが沢山落ちたりすることもあった。

もう一つの問題はBroadcastパケットの性質としてデータが落ちてもわからないという性質があり
更新データが落ちたのをクライアント側が気づくことができないという問題である。
この問題に対しての考えは後述する。

\subsection{パケットの分割}
VNCでは画像を更新する際に矩形単位で更新データを送信する。

画面全体の更新などはどうしても更新データのサイズが大きくなってしまう。
Broadcastでは約64000byteまでのデータしか送ることができないので、
データを送信する際は64000byte以下になるようにデータを分割して送らなければならない。

第5章で説明したとおりTreeVNCでは、VNC ServerからZRLE圧縮されたデータをうけとり、
Topが一旦解凍をして、圧縮し直してZRLEE圧縮されたデータを送信している。

この一旦解凍されたデータを分割64000byte以下にしてクライアントに送信してやれば良い。
ZRLEを解凍すると、64*64ピクセルのタイル群のデータになる。

よってデータの分割はこのタイル群数個分で分割することでうまくいくと考えた。
最後に分割したデータを圧縮しなおして、headerデータを付加してクライアントに流してやれば良い。



\subsection{dropしたパケットの検出}
Broadcastの性質で説明したとおり、Broadcastではデータが落ちていることをクライアントが知ることができない。
そこでプロトコルを拡張してデータごとにシリアル番号を振ってやり連続でない値が来た時はデータが正しく
届いていないと判断することができる。このようにすることでdropしたデータの検出ができると考えた。


\subsection{Acknowledgeの設計}
データがdropした際に、どのようにして落ちた部分のデータをTopに再送してもらうかが問題となってくる。
クライアントはdropしたパケットのシリアル番号がわかっている。

ちなみに、Broadcast版の実装でもクライアントをTree構造で接続させておく必要がある。
その理由として、初期接続のパケットはBroadcastでは送れないのでTCPを用いなければならないや
クライアントがdropを検出したときTopに知らせてdropした部分のパケットを再送信してもらわなければならない。
再送信をする際はTCPで送信する。

ここでTree構造で組んでいない場合、全クライアントがTOPに対して接続に行ってしまうと接続が一箇所に集中
してしまい通常のVNCと変わらなくなってしまう。

以上の理由からBroadcastの際にもTree構造で組む必要がある。
そうすると、Tree構造でどのようにしてdropしたパケットをTopに教えるかを考えなければならない。

クライアントは上のクライアントに対してどの番号のパケットがdropしたのかを指定して
最終的にTopに届くように上へ上へと送信していく。
ここで、上へ送信していく際に途中で目的のデータが上から送られてきた際には、そのパケットはそこで破棄するように
する。


\section{まとめと今後の展開}
本研究では、作成したTreeVNCのUserInterfaceの設計を行い実装を行った。
さらに、TreeVNCはMulticastでパケットを送信しているが、Broadcastで送信することができるように
するための設計を行った。設計を行うことでいろいろな問題が見えてきた。

今後の展開として、発表者が変わるたびにTopを立て直すまたはひとつのコンピュータで発表を行うなど不便
な部分があるので発表者をボタンひとつで切り替えられるように実装を行いたい。

それから、今回設計を行ったBroadcast版の実装を行い、Multicast版のTreeVNCとBroadcast版の性能比較を
行いたい。


%\begin{adjustvboxheight}
\begin{thebibliography}{10}

%\bibitem{latex}
%Lamport, L.: {\em A Document Preparation System \LaTeX User's Guide \&
%  Reference Manual}, Addison Wesley, Reading, Massachusetts (1986).
% （Cooke, E., et al.訳：文書処理システム \LaTeX，アスキー出版局
%  (1990)）.


\bibitem{VncReflector}{TightVNC: VNC-Compatible Free Remote Control / Remote Desktop Software}: 
http://vnc-reflector.sourceforge.net/

\bibitem{TightVNC}{TightVNC: VNC-Compatible Free Remote Control / Remote Desktop Software}: 
http://www.tightvnc.com/

\bibitem{VNC}{Tristan Richardson, Quentin Stafford-fraser, Kenneth R. Wood, Kenneth R. Wood, Andy Hopper}:
Virtual Network Computing (1998): Virtual Network Computing (1998)

\bibitem{ZLIB}{P. Deutsch, J-L. Gailly }:
ZLIB Compressed Data Format Specification version 3.3

\bibitem{ソフトウェア科学会}{谷成雄,大城信康,河野真治 }:
VNCを用いた授業用画面共有システムの設計と実装 日本ソフトウェ ア科学会第 28 会大会, Sep 2011



\end{thebibliography}
%\end{adjustvboxheight}


\end{document}