PDF フォーマル資料 ネットワーク分散型計算機環境における最適データ再配置手法

フォーマル資料

ネットワーク分散型計算機環境における最適データ再配置手法

慶應義塾大学 政策・メディア研究科 自署：＿＿＿＿＿＿＿＿＿

学籍番号80749317 平成22年2月1日

概要

本研究では、分散ファイルシステム環境における”データ移動性”を実現するData Preforwardingを提案する。仮想計算 機環境の成熟に伴い、ユーザは端末に縛られることのないアプリケーション環境の構築を行うことが予想される。その際、

既存の分散ファイルシステムでは、ファイルの格納場所は、ユーザの実際のファイル利用場所とは無関係にネットワーク 上に配置されるため、ユーザがデータにアクセスする際に大きな遅延が発生する可能性がある。本研究では、ユーザがイ ベント毎にアクセスするファイルに傾向があることに着目し、ネットワーク負荷、ストレージ負荷に考慮した上で、ユー ザのネットワーク移動に伴う最適なデータ再配置を行う手法を提案する。

1 はじめに

計算機の常時接続環境の整備、移動体通信技術の 成熟に伴い、ユーザはいかなる場所、いかなる時にお いても計算機環境を利用することが可能となった。一 方、ユーザは物理的作業場所に基づいて、個別の計算 機ハードウェアに依存した個別のアプリケーション環 境を構築している。例えば、ユーザはオフィス、自宅 において個別のOSによるアプリケーション環境を構 築し、そのアプリケーション環境はOSをインストー ルしたハードウェアに大きく依存した構成となる。さ らに、移動中は、ユーザは携帯電話等の移動端末上で 構成されるアプリケーション環境を用いた作業を行う こととなり、結果として、異なるアプリケーション環 境の間で作業を継続することができない。今日のコン ピュータ環境はこのように計算機の物理ハードウェア に大きく依存した計算機環境が構築されており、した がって複数のアプリケーション環境を統合することが 不可能な構成となっている。

これらの問題を解決するため、近年、仮想計算機環 境を実現するための技術が注目を集め、実運用され 始めている。従来のコンピュータ環境において、ユー ザにアプリケーション環境とユーザインターフェース を提供するための基盤システムであるOSを仮想化す るOS仮想化技術は実際に運用される段階にまで成熟 している。また、iSCSI[2]やiUSB[3]等、計算機の物 理構成要素であるパーツの物理バスとしてIPネット ワークを利用することで、複数のOSから透過的に単 一の物理パーツに接続、通信するための技術も提案、

実装されている。上記のように、次世代の計算機環境 において、世界規模の広域分散ネットワークであるイ ンターネットを計算機内の共有バスとして用いること は、最も優先度の高い機能用件となっている。

本研究では、インターネットバスを利用した次世代 計算機環境の要求事項を整理し、単一アプリケーショ ン環境をユーザが利用し続けるための技術要件を定義 する。その上で、ユーザデータに着目し、その動的最 適再配置手法を提案する。

2 研究概要

今日のユーザコンピュータ利用環境を再考するなら ば、ユーザは場所、場面に依存して複数の計算機環境 を用いていると言える。ユーザはその物理的移動に 伴い、物理場所に依存した計算機を使わざるを得ず、

結果として、複数拠点における継続的な作業の継続は 困難となっている。これまで、端末移動をIPネット ワーク上で透過的に扱う技術は多く提案されてきた が、ユーザアプリケーション環境、ユーザ計算機環境 を透過的に移動させるための技術は未だ成熟していな い。また、仮想化技術の発達、IPネットワークを経由 したデバイスIPバス環境の整備も急速に発達してき ているが、それらを統合的に用いた上でのアプリケー ション環境の動的再構築技術は定義されていないまま である。

本章では、以下にユーザの継続的かつ透過的なアプ リケーション環境を支援するための計算機アーキテク チャであるAll-IPコンピュータ環境を定義し、その機 能要件を整理する。

2.1 機能要件

All-IPコンピュータ環境の構築には以下の機能要件

が存在する。

• サービス発見

• アプリケーション環境のユーザ追従性

• 状況に応じたコンピュータ環境の構築

All-IP環境の構築には、ユーザはAll-IP計算機環境 のサービスネットワークの発見を行う必要がある。そ の際、ユーザの認証、ユーザ利用デバイス設定情報を 反映できる必要がある。また、ユーザのネットワーク 移動に伴い、動的にユーザアプリケーション環境の呼 び出しを行い、ユーザの現在ネットワークにおける資 源の割当を行うことは不可欠である。さらに、ユーザ のアプリケーション環境利用状況に応じたコンピュー タ環境の構築を行う必要がある。

3 All-IP コンピュータ資源管理手 法

3.1 資源管理手法概要

図1はAll-IPコンピュータ資源管理手法の外観図

である。

図1: 資源管理手法概要図

All-IPコンピュータ環境では、ユーザは”ユーザタ

グ”と呼ばれる小型端末を持つことが前提となる。ユー ザタグには、認証情報やデバイス設定情報が保存され る。ユーザはネットワークを移動する際、異動先ネッ トワークでこのユーザタグをネットワークへ接続し、

ネットワーク上に存在する資源管理サーバへと認証要 求/資源割当要求を発行する。本研究では、この資源 管理サーバをRendezvous Manager (RM)と定義す る。このRMにより、Host OSと呼ばれるAll-IPコ ンピュータ管理OSへとIPネットワークを経由した デバイス接続が行われる。

3.2 Rendezvous Manager

RMは、資源管理のための情報とユーザ認証情報を 管理する。RMが管理する資源情報は以下の通りで ある。

• デバイス名

「キーボード」「ディスプレイ」のようなデバイ スタイプ

• デバイスIPアドレス

デバイスに割り当てられたグローバルアドレス

• デバイス利用状況

デバイスの利用状況。デバイスがすでに利用され ている場合は、デバイスを利用しているAll-IPコ ンピュータIDを示す。

• デバイス物理位置

入出力デバイスでのみ利用される。新規All-IP コンピュータを構成する場合、近接の入出力デ バイスをまとめるために用いられる。All-IPコ ンピュータの構成が完了すると、この情報を基に ユーザに計算機利用可能場所を通知する。

RM は 大 別 し て Local RM(lRM) と Remote

RM(rRM)に分類される。lRMはユーザの訪問先ネッ

トワークに設置されているRMであり、rRMはユーザ のホームネットワークに設置されるRMである。lRM はユーザタグからの情報を基にユーザが自ネットワー クにおいてAll-IPコンピュータを利用可能であるか を判断する。認証が成功した場合、ユーザに対して利 用可能I/Oデバイス群を割り当てる。次に、ユーザ タグからの通知に従い、ユーザが固定的にAll-IPコ ンピュータの構成に用いるデバイス情報とそれらのデ バイスを管理するrRMのIPアドレス情報を取得す る。その後、rRMに対してユーザ認証要求を送信し、

ホームネットワークに接続されているデバイスの使用 許可を受ける。その後、ユーザアプリケーション環境 を提供するHost OSをローカルネットワークに移動 させることが出来る場合は移動させ、Host OSに対し て接続するべきデバイスのIPアドレス情報を通知す る。最後にユーザに対してI/Oデバイスの所在を通知 し、その処理を終える。

4 All-IP コンピュータユーザデー タ配置手法

ネットワーク上にユーザデータを配置し、ユーザに 透過的なファイルアクセスインターフェースを提供す るシステムとして分散ファイルシステムがある。本研

究では、ユーザにデータアクセスインターフェースを 提供するシステムとして分散ファイルシステムを前提 とする。分散ファイルシステムを用いる際、ユーザが データにアクセスする際のアクセス遅延はユーザサー ビス使用感に大きく影響する[5]。広域分散ファイル システムにおいて、ユーザデータアクセス遅延を最小 にするためには、利用可能性がある全てのユーザデー タをユーザが接続する可能性がある全ての拠点に複 製するのがもっとも効率的である。しかし、全ての拠 点に全ユーザデータを複製する場合、各拠点のファイ ルサーバ容量に大きな負荷をかけてしまうため、スト レージ容量の観点からはこのような手法は効率的とは 言えない。

また、広域分散ファイルシステムにおいて、ファイ ルはファイルシステムの基盤として動作するIPネッ トワークと同等の広がりを持って分散配置される。そ の際、ユーザのデータ利用場所と該当ユーザデータの 格納場所のネットワーク距離が大きくはなれていた場 合、アクセス遅延が大きくなるとともに、データ配送 時の経由リンク数も増えるため、通信の安定性が損な われてしまう。通信の安定性の欠如は、フロースルー プットの不安定さ、ジッタとしてデータ転送フローに 影響を及ぼす。したがって、データ転送時の経由リン ク数を最小限とすることが必要となる。

本研究では、分散ファイルシステムにおいて、ユー ザのネットワーク位置に着目し、場所に応じたユー ザ行動に基づくデータ再配置手法Data Preforward- ingを提案する。本章では、以下に関連研究を整理し、

Data Preforwardingの機能要求を整理した上で、Data Preforwardingの概要を示す。

4.1 関連研究

ファイルシステム上においてファイル関連性を定義 する際、ファイルのアクセスパターンを参照する手法 は広く知られている。ユーザがあるファイルにアクセ スする可能性は、直前にアクセスされたファイルから 推測可能である、という結果はいくつかの先行研究で 示されている[9][10][11]。例えば、あるプログラムが いくつかの設定ファイルを読み込む際、その設定ファ イル群をよみこむ順序はプログラムによって固定的で あるため、ファイルアクセス履歴に基づいて後にアク セスされると予想されるファイルを類推することは可 能である。[8]では、それまでのような単純なLRUに よってファイルのアクセスパターンを類推するのでは なく、ユーザのファイルアクセスパターンを参照した 上で、アクセスパターンに基づいたファイル関連性の トライ構造を作成する。その上で、トライ構造により 定義される関連性をスコア付けし、現在、参照されて いるから将来アクセスされる可能性が高いファイルを

プリフェッチする。

上記のようなファイルシステム内の全イベントを包 括的に参照するアクセスパターン予測手法は分散ファ イルシステムにおいては実効的でないとする研究も存

在する[12]。これは、分散ファイルシステムでは、複数

ユーザがそれぞれのパターンにより複数のプログラム を起ち上げてファイルにアクセスするため、単純にファ イルシステム内のイベントを参照するだけでは効率的 なアクセス予測ができないためである。FARMER[15]

は、分散ファイルシステムにおいて、ユーザ、プログ ラム、ファイルパスのそれぞれを参照してファイル関 連性を定義し、ファイルアクセス履歴と統合すること により、プリフェッチ効率を高めることが可能である ことを示している。また、Ellardらの研究[13][14]に よると、NFS環境において、ファイルアクセスモード

(読み込み、書き込み、実行)やファイル名等のファイ

ル属性により、ファイルのアクセスオペレーションを 類推可能である、としている。さらに、類似ファイル をファイル属性から類推し、グループ分けすることに より関連ファイルを様々な粒度で定義可能である。

ユーザのネットワーク上での振る舞いを考えると、

ユーザがネットワークへ接続する際、その接続形式に は一定以上のパターンが存在することが示されてい る。Otiy[7]では、ワイヤレスメッシュネットワーク における位置情報管理サーバへのノード移動情報更新 をユーザ直近のサーバへ登録するための機構が提案さ れている。その際、ユーザの移動を追跡した結果とし て、ユーザには週毎に一定の接続ネットワーク切り替 えパターンが存在することを示している。したがって、

ユーザのネットワーク切断をイベントとし、直前複数 週のアクセスパターンを参照することにより、次接続 ネットワークを判断することが可能となる。lcron[6]

では、ユーザが接続ネットワーク毎にアプリケーショ ン挙動を変化させることに着目し、接続ネットワーク 毎にアプリケーション挙動を変化させるシステムを構 築している。例えば、メールの受信を行う際、ユーザ が必要とする受信メールは接続ネットワーク毎に異な る。自宅では、契約ISPアカウントからのメール受信 を行う必要があり、その読み込み周期は比較的長めで よい。しかし、オフィスでメール受信を行う際には、

オフィスのメールサーバからメールを受信する必要が あり、さらにその受信周期は短いことが望ましい。そ のような接続ネットワークによるアプリケーション挙 動制御を、接続ネットワークを判断したcronベース のシステムにより実現している。

本項では、ファイルシステムにおけるファイル関連 性に関する先行研究とユーザのネットワーク挙動につ いての関連研究を示した。本項で述べたファイル関連 性評価では、基本的にファイルへのアクセスをイベン トとして将来におけるファイルアクセスを予測するた

め、ユーザ移動に伴うデータアクセス予測を行うData Preforwardingには不十分である。そして、先行研究 によるとユーザの接続ネットワーク予測は可能であり、

また、接続ネットワーク毎にアプリケーション挙動が 変化することが示されている。本研究では、ユーザの 接続ネットワーク毎の挙動を意識した上で、分散ファ イルシステムにおける最適なデータ配置ならびにデー タ転送を行うシステムの構築を行う。

4.2 機能要件

Data Preforwardingの機能要件は以下の通りであ る。

• ユーザ行動の把握

• ファイル関連性の定義

• 場所に応じたデータ転送

• サービス発見

• サーバクラスタリング

Data Preforwardingでは、ユーザデータを場所に 応じて転送することが必要になる。そのためには、ま ず、ユーザ行動と場所を測定する必要がある。本研究 では、「場所」を接続ネットワークとして定義する。

ユーザは、物理的な移動に伴い、接続ネットワークを 変化させる。その際、ユーザは物理位置に従ってその 接続ネットワークインターフェースを切り替える。ネッ トワーク上のデータ保存場所を考慮するならば、物理 位置による近傍性評価よりも接続ネットワークに基づ いた近傍性評価が望ましい。本研究では、以上の理由 からユーザ接続ネットワークをユーザ場所として定義 する。

ユーザ接続ネットワーク情報を取得した後、Data Preforwardingはファイルシステムに対するユーザ行 動を記録する。ファイルシステムに対するユーザの行 動とは、ファイル読み込み、書き込み、作成などのファ イルシステムイベントである。Data Preforwardingで は、これらのファイルシステムイベントと場所情報と しての接続ネットワーク情報を関連付け、ユーザがど の「場所」においてどのデータを必要としているのか を把握する。そして、推測された必要データを必要箇 所にのみ複製/転送することにより使用ストレージ容 量を削減した上でユーザのデータアクセス遅延を解消 することが可能となる。

Data Preforwardingでは、Anycastサービス発見手 法を用いる。Anycast経路制御では、複数ホストに同 一のIPアドレスを設定した上で、同一IPアドレス をそれぞれの拠点から広告する。複数地点から広告さ

れたアドレスへの経路は、経路制御プロトコルに基づ いた最短経路が選択されるため、各地点において最も 近いホストへ接続することが可能となる。これまで、

Anycastの導入には多くの問題があるとされてきた。

その最大のものは、経路制御設定に関する問題である。

Anycastを用いたホストグループを形成するためには、

多くの状況で複数のネットワークにおいてAnycastア ドレスの経路広告が行われなければならない。そのた めには、複数のネットワークドメインの管理者がアド レス広告の設定を行わなければならず、したがって基 盤環境の構築に多大な労力が必要となる。

本研究では、Anycastサービス発見の基盤環境構築 にIPトンネルを用いた仮想Anycastオーバーレイ ネットワーク技術を用いる[4]。IPトンネルを用いて

各Anycast経路制御が実際に設定できたドメイン間

を接続することで、Anycast経路制御が行われていな いドメインを超えてデータを転送可能となる。[4]で 提案されるシステムは、トンネルを経由した転送を行 う際の経路選択ポリシとして、RTTを用いた近接性 評価を行い、ネットワーク距離が近いサイトを選択可 能な機構である。本研究では、上記のような広域環境 でも動作可能なIP Anycastサービス発見手法を採用 する。

Data Preforwardingでは、ファイルサーバ間でデー タ交換を行う頻度が高いため、単一のサーバに多くの 負荷がかかる可能性がある。単一のファイルサーバに 対する転送が多くなれば、そのファイルサーバのスト レージ容量を消費し、結果として転送が実現されない 可能性がある。ユーザデータ利用場所に対してデータ を転送することができなければ、ユーザがデータにア クセスする際の遅延が発生する。したがって、本研究 では、ファイルサーバをRTTによる近傍性評価をし た上でクラスタとして集合化する。

時節では、以上の機能要求をふまえたシステム設計 を行う。

4.3 システム全体像

図2に、Data Preforwardingのシステム概要図を 示す。

ユーザは、ネットワークに接続すると、ファイルシ ステムドメインAnycastアドレスに対して認証要求 を発行する。認証要求はAnycast転送により、ファイ ルシステムドメイン内の最近傍ファイルサーバに転送 される。最近傍ファイルサーバは、ユーザからの認証 要求をPreforwarding Contorollerに対して転送する。

Data Preforwardingシステムは、このPreforwarding Controller (PFC)により制御される。PFCはユーザの 認証情報、ユーザ接続ネットワーク、接続ネットワーク

図 2: システム概要図

における最近傍ファイルサーバ、ユーザのファイルア クセス履歴などを管理し、ユーザ移動にあわせたファ イル転送を促す。

4.4 ネットワーク毎のユーザの振る舞い

ユーザは、自身のユーザデータにアクセスする際、

その接続ネットワークに応じてその挙動を変化させる。

例えば、ユーザはオフィスにおいては、自身の職務に 関連したファイルにアクセスする可能性が高い、と予 想される。一方、自宅においては、マルチメディアデー タなど、比較的趣味性の高いファイルに対するアクセ スが比較的に大きな割合を占める、という予想は直感 的である。本節では、ユーザの場所に応じたファイル アクセスパターンが存在することを、各拠点における アクセスファイルの拡張子に着目することで示す。

以下のデータは、2009/09/28から2009/10/07まで の10日間における、あるユーザのユーザデータアク セス傾向を2拠点において観測したデータである(図 3)。

図3: 場所におけるユーザファイルアクセスパターン

各地点において上位3アクセス拡張子に着目すると、

場所1においては、cファイル、oファイル、hファ イルについてアクセスしていることが分かる。一方、

場所2においては、jpgファイル、mp3ファイル、flv ファイルについてアクセスが多い結果となっている。

これは、場所1においては開発系のファイルに多くア クセスしていることを示し、場所2においては趣味性 の高いファイルがアクセスされる傾向にあることが分 かる。そして、少数ではあるが、jpgファイルやmp3 ファイル等、2拠点双方からアクセスされるファイル タイプも存在する。

以上の結果から、単一地点からのみアクセスされる ファイルについては、そのファイルを「場所に依存し て利用されるファイル」として定義し、利用場所に近 いファイルサーバに対してデータを蓄積することで、

ファイルストレージ利用量を低減しつつ、ユーザデー タアクセス遅延を低減できると言える。また、複数拠 点から用いられるファイルについては、各地点直近に 存在するファイルサーバに対してデータ複製を行うこ とが効率的である、と言える。ファイル複製作成ポリ シについては後述する。

4.5 イベントクラスタリング

Data Preforwardingでは、ユーザ毎にイベントを 管理し、該当イベント中にアクセスされたファイルア クセス履歴からイベント毎の相関を定義する。まず、

イベントはユーザのネットワーク接続/接続断を基に 作成される。その際に、各イベント毎に以下の項目を 同時に記録する。

• イベント開始時間/終了時間

• ファイルアクセス履歴

• 最近傍ファイルサーバ

次に、ある時間におけるユーザイベントを定義す る。[7]に示される通り、ユーザ接続ネットワークの 変遷は、週毎に同一傾向を繰り返す可能性が高い。例 えば、月曜日の午後2時からあるネットワークに接続 したユーザは、別の週においても同様の時間に同一の ネットワークに接続する可能性が高い。これは、ユー ザの行動スケジュールが週単位で決定されていること が多いためである。したがって、ある週のユーザ接続 ネットワークとその接続時間を記録することによって、

未来のイベントを予測することが可能である、との推 察を行うことができる。

しかし、直前週のイベントログ内のファイルアクセ ス履歴のみを用いて、将来のアクセスファイルを予測 するだけでは十分とは言えない。なぜなら、同一週内 においても同一のファイルアクセス傾向を持つイベン

トが発生する可能性が高く、さらにユーザはあるイベ ントについて最新のアクセスパターンを踏襲する可能 性が高いからである。同一のファイルアクセス傾向を 持つイベントは同一イベントとした上で、直近のファ イルアクセス履歴に基づいたファイルアクセス予測を 行うことで、より正確なアクセスファイル予測を行う ことができると考えられる。

イベントクラスタ作成時には、まずはアクセスネッ トワークにより、大きくイベントクラスタが分けられ る。次に、ユーザがネットワークに接続してから切断 するまでにアクセスしたファイルアクセス履歴のう ち、総アクセスイベントに対するある拡張子を持った ファイルへのアクセスイベントの割合を求め、割合が 10%を超える拡張子についてキーファイル拡張子と定 義する。さらに、イベントクラスタ拡張子とイベント キー拡張子を比較し、一致率が5割以上のイベント についてアクセスクラスタに加え、新たなイベントの キー拡張子がアクセスクラスタ拡張子に存在しない場 合、該当するアクセスクラスタのイベントクラスタ拡 張子に追加する。

図 4: ユーザイベントクラスタ例

図4はあるユーザのファイルアクセスパターンに基 づいたイベントクラスタの例である。計測は1週目 火曜日から始まり、4週目月曜日をもって終了してい る。図4では、一日を大きく日中、夜間に分け、それ ぞれについてイベントクラスタを示している。「日中」、

「夜間」は特定の時刻によって定義されるのではなく、

ユーザのネットワーク接続/接続断の時間帯を基に判 定している。まず、月曜日についてイベントクラスタ を観察すると、2週目日中において「日中: クラスタ

1」と判定された履歴は、3週目、4週目においても同

様のものとしてクラスタリングされていることが分か る。夜間についても2, 4週目については同様のクラス タリングがされているが、3週目については、ユーザ はデータに全くアクセスしていない。火曜日について は、1, 2週目は同一のイベントクラスタリングが可能 であり、水曜日については、1, 3週については同様の パターンを持っている。金曜日については観測外ネッ トワークにユーザが接続しているため、特に日中にお いてイベントクラスタリングが行われていない。

次に、週末のイベントクラスタを見ると判定の不整 合が大きくなっていることが観測されている。1週目 土曜日は、日中夜間ともにクラスタ2と判定されてい

るが、2週目日中はクラスタ1として、3週目日中は クラスタ2として判定されている。同様に日曜日は2, 4週目日中においてクラスタ2と判定され、3週目日 中にはクラスタ3として判定されている。このような 不整合は計測期間中は週末のみに発生しているが、週 日においても発生する可能性がある。つまり、前週の 同一時間帯におけるイベントのみを参照するのでは、

データ予転送を誤る可能性があり、結果としてユーザ データアクセス時の遅延が発生する可能性がある。本 研究では、データアクセス時の遅延を低減するため、

直前複数週のイベントを参照し、発生する可能性のあ る複数イベントについて考慮したデータ予転送を行う ことでデータアクセス遅延を低減するシステム構築を 行う。

将来においてアクセスされる可能性の高いファイル を定義するためには、拡張子のみに注目した手法では 不十分である。拡張子とディレクトリに着目した手法 では、アクセス頻度の高いディレクトリ内にあるイベ ントキー拡張子をPreforwardingすることは可能であ るが、拡張子の異なるファイルについてはたとえ関連 性が高かったにせよPreforwardingを行えない可能性 がある。イベントキー拡張子を持つファイル以外のファ イルに対応するため、本研究では、あらかじめ全ての ファイルのキーワードインデックスを作成し、キーワー ドによるファイルクラスタリングを行う。その上で、

ファイルアクセス履歴からファイル名の形態要素解析 を行い、頻度分析を行った上でキーワードを抽出し、

関連ファイルのPreforwardingを行う。該当イベント においてファイルからキーワードが抽出できなかった 場合には、上記の拡張子に基づいたデータ転送が行わ れる。

4.6 イベントクラスタ学習を用いないイベ ント学習

前節では、イベントクラスタ学習によるイベント定 義手法について述べた。しかし、上述の手法だけでは、

非定例のイベント学習は行えない。ユーザ行動は基本 的に周期的であるために、周期的な行動についてはイ ベント学習可能であるが、突発的かつ不規則に発生す るイベントも存在し、それらについて学習することは 困難である。そのため、本研究では、突発イベントに 対しては周期学習ではなく、外部システムからの学習 を可能とする機構を追加する。外部システムからイベ ントを学習する際、イベントキーワードをイベント名 より抽出する。キーワードによりクラスタリングされ た関連ファイルを同様に外部アプリケーションから読 み込んだネットワークに対して送信することで、突発 イベントへの対応を実現する。その際のネットワーク 近傍ファイルサーバ選択は、各サーバクラスタから該

当ネットワークに対する近傍性評価により行われる。

4.7 データ転送

Data Preforwardingは、該当時間において学習さ れたイベントを予測し、その上でそのイベントが属す るイベントクラスタの直前イベントを参照してデータ 転送を行う。図4を参照すると、第2週火曜日、土曜 日、第3週、火曜日、水曜日、木について同一のイベ ントクラスタとして判定されているが、作業ディレク トリに着目すると、(2火、3木、およびそれ以降)、(2 土、3水)、(3火)と3つのディレクトリについてアク セスしている。前週のイベントにおけるファイルアク セス履歴のみを参照する方式では、このように変遷す るユーザデータアクセスパターンに対応することがで きない。本研究では、直前数イベントのアクセスディ レクトリを参照した上で、イベントキー拡張子をもつ ファイルを転送する。

4.7.1 イベントクラスタ予測

Data Preforwardingを行う際には、ある曜日/時間 帯における関連ファイルを類推する必要がある。その ためには、その曜日/時間帯におけるイベントがどの イベントクラスタに属するものであるのか、を予測す る必要がある。図5にイベントクラスタ予測手法の概 要を示す。

図 5: イベントクラスタ予測手法

図5は図4中の第4週目土曜日日中におけるイベン ト予測を行う際の手順である。該当時間におけるイベ ントを参照すると、直前3週の同一時間帯におけるイ ベントを参照すると、第1週においてイベントクラス タ2に属するイベント、第2週においてクラスタ1に 属するイベント、第3週においてクラスタ2に属する イベントが発生している。この際、第4週に発生する イベントとしてはクラスタ1、クラスタ2の2つのイベ ントを推測可能である。Data Preforwardingでは、こ の場合、2つのイベント双方が発生するものとしてファ イルの転送を行う。なぜならば、Data Preforwarding の最大目標は、ユーザのデータアクセス遅延の最小化 であるため、発生可能性が高いイベント全てに対応し

てファイルを転送することが目標を満たす可能性が高 いためである。

該当時間における関連イベントが予測できた場合、

関連イベントに属する直前1週分のアクセス履歴を参 照し、アクセス頻度の高いディレクトリ中、イベント キー拡張子を持つファイルがイベント関連場所に対し て転送される。

4.7.2 単一地点から読み込まれるファイル

Data Preforwardingを行う際には、ファイルに対 する読み込みオペレーションを考慮する必要がある。

ファイルの読み込み地点に着目すると、ファイルは、

単一地点から読み込まれるファイルと、複数地点から 読み込まれるファイルが存在する。本項では、まず前 者について解説する。ファイル読み込みには大別して 2つのオペレーションがある。すなわち、一括読み込み と順次読み込みである。一括読み込みファイルについ ては、ユーザがファイルにアクセスする段階でファイ ル全体を読み込む必要があるため、ユーザ直近のファ イルサーバに対してファイル全体を転送する必要があ る。その際、転送元ファイルサーバに保存されている ファイルをマスターファイルとし、複製ファイルを転 送先サーバに転送する。そして、実際にファイルアク セスがあった場合、該当複製ファイルをマスターファ イルとし、元マスターファイルを消去する。

順次読み込みファイルについては、ユーザがデータ にアクセスする瞬間に全データが利用場所に存在する 必要がない。ユーザアプリケーションのファイル読み 込み速度を考慮し、ファイルの末尾を読み込むまでの 間にネットワーク転送によってデータが完全に読み込 まれることが可能であるならば、ユーザデータアクセ ス遅延は発生しない。したがって、あらかじめ転送す るデータ量を抑制することにより使用ストレージ容量 を低減することが可能となる。そのためには、該当す るファイルの読み込み速度と、予測されるストレージ 間実効帯域の情報が必要となる。

ファイル読み込み速度は、ユーザファイルアクセス 時に記録することにより予測する。転送開始時にファ イル読み込み速度が記録されていないファイルについ ては、同一拡張子を持つファイルのうち、最高読み込 み速度を持つファイルの値を仮に用いる。また、ネッ トワークにおける実効帯域はファイルサーバ間におけ る過去に実現された実効帯域を基に推測する。ネット ワークのトラフィック量は、曜日時間毎に一定の傾向 をもつことが示されている[16]。本研究では、過去に 同一時間帯において実現された実効帯域を統計的に処 理することにより、実効帯域の予測を行う。インター ネットのような共有型ネットワークにおいては、突発 的大量データ転送の影響が考えられるため、統計デー

タのみでは不十分ではあるが、Data Preforwardingに よる転送は比較的長期のため、これらの突発的データ 転送の影響が比較的小さくなることが考えられる。順 次読み込みファイルについても、データの完全転送が 完了した段階で、マスターファイルの置き換え、元マ スターファイルの消去が行われる。

4.7.3 複数地点から読み込まれるファイル

複数地点から読み込まれる可能性あるファイルにつ いては、それぞれのファイルについてデータ複製処理 を行う。一括読み込みファイルについては、単一地点 から読み込まれるファイルと同様の処理が行われる が、マスターファイルの置き換えを行わず、各拠点に 複製データを配置する手法をとる。以下に順次読み込 みファイルについての処理を述べる。まず、利用され る可能性がある地点のファイルサーバ間でRTTを基 にし、中間ファイルサーバを決定する。中間ファイル サーバにマスターファイルを配置し、各拠点への実効 帯域を記録することによって、各拠点へのバッファリ ング容量を決定し、バッファリング容量のみあらかじ め転送する。完全読み込みが行われた際、複製ファイ ルを消去するか、保持したままとするかは、読み込み が行われた拠点におけるストレージ残量に依存する。

4.7.4 ファイル書き込み処理

ファイルへの書き込み処理が行われる場合、そのファ イルはFPCによりロックされた上で、該当ファイル に随する全ての複製ファイルはシステム上から一旦消 去される。書き込み処理が完了した後、一括読み込み ファイルについては、複製ファイルが存在したファイル サーバへあらたなファイルが複製として転送され、書 き込み処理が行われた地点のファイルがマスターとな る。順次読み込みファイルの場合、マスター保存サー バに対してのみ更新ファイルが転送され、全ての複製 データは消去される。しかし、Data Preforwardingの 転送ポリシに従い、利用が推測される地点へデータは あらかじめ転送される場合には、ユーザはデータアク セス時のアクセス遅延を体感することはない。

4.8 サーバクラスタリング

Data Preforwardingでは、ユーザ移動に伴ってユー ザデータがファイルサーバ間で転送される。その際、

転送先ファイルサーバの負荷が高い、転送先ファイル サーバのストレージ容量に余裕がない、等の理由で 転送が行われない可能性がある。その場合には、直 近サーバに必要ファイルが存在しないため、ユーザが

ファイルにアクセスする際の遅延が大きくなる可能性 がある。

本研究では、上記の問題を解決するため、ファイル サーバ間でサーバクラスタを行う。新規ファイルサーバ が、ファイルシステムドメインに参加する場合、FPC に対して参加要求を送信する。FPCはそれに対し、参 加応答とともにクラスタヘッドアドレス情報を送信す る。新規サーバは、各クラスタヘッドへのRTTを計 測し、クラスタヘッドへのRTTが閾値以下、かつ最 小のRTTを持つクラスタに対してクラスタ参加要求 を発行する。該当クラスタヘッドが存在しない場合、

新規ファイルサーバは新規サーバクラスタ作成要求を FPCに対して発行する。

以上のようにサーバクラスタリングを行うことで、

仮にファイル転送先サーバがなんらかの原因でファイ ル転送要求を拒否した場合でも、同一クラスタ内の サーバにファイルを転送することが可能となる。

4.9 評価指針

Data Preforwardingの評価は2段階に分けて行わ れる。すなわち、イベント関連ファイル選択アルゴリ ズムの検証とシステム評価である。イベント関連ファ イル選択アルゴリズムの構築は、現在、複数ユーザの データアクセスパターンに基づいたものではない。し たがって、複数ユーザのデータアクセス履歴を取得し、

その上で正当にイベントクラスタの構築を行った上で、

イベントクラスタ毎に関連ファイルを選択可能である ことを示す。イベントクラスタ、ファイル関連性評価 アルゴリズムの正当性を示すためには、該当時間にお いて、ユーザが実際にアクセスしたにも関わらず、本 システムにおいて関連ファイルとして定義できなかっ たファイルの率を求める。

その上で、分散ファイルシステム上にユーザデータ を展開し、模倣環境においてシステム全体の評価を行 う。その際の評価項目は、ユーザデータアクセス遅延、

ストレージ容量、ネットワーク負荷の3項目である。

その際、全ての拠点に対してデータを複製した場合、

複製を行わなかった場合と比較し、本システムの優位 性を示す。

4.10 Data Preforwarding まとめ

Data Preforwardingは、ユーザの移動に伴い、ユー ザデータの移動性を実現する機構である。Data Pre-

forwardingでは、ユーザの行動パターンに着目するこ

とで、あらかじめユーザ移動先にファイルを転送し、

ユーザのファイルアクセス遅延を低減する。その際、

ネットワーク負荷、ストレージ負荷を考慮することに

より、既存の分散ファイルシステムにおけるデータ配 置を効率化することができる。

5 論文、活動

5.1 国際論文

Kouji Okada, Keisuke Muda, Yoshifumi Nishida, Hideaki Yoshifuji, Ryuji Wakikawa, and Jun Murai,

“Protocol Design for All-IP Computer Architecture”, International Conference on Information Networking 2008 (ICOIN2008) , January 2008.IEEE Digital Li- brary copy

Kouji Okada, Ryuji Wakikawa, Jun Murai,

“MANET and NEMO Converged Communica- tion”, ASIAN INTERNET ENGINEERING CON- FERENCE (AINTEC), Bangkok, Thailand, 28-30 November 2006

Ryuji Wakikawa, Kouji Okada, Noriyuki Shigechika, Tomohiro Ishihara, Yuki Oyabu, Yuri Nagai, Jun Murai, “A Networked Human Transporter as an Experimental Testbed of Mobile Gateway”, 1st IEEE Workshop on Automotive Networking and Applications (AutoNet 2006)

Kouji Okada, Ryuji Wakikawa, Jun Murai.,”IPv6 OLSR Implementation on Zebra Platform”, 3rd OLSR Interop and Workshop 2006, Tokyo Japan, 02 October 2006

Ryuji Wakikawa, Kouji Okada, Rajeev Koodli, Anders Nilsson, Jun Murai, “Design of Vehicle Net- work: Mobile Gateway for MANET and NEMO Converged Communication”, The Second ACM In- ternational Workshop on Vehicular Ad Hoc Networks (VANET 2005), Poster, Cologne, Germany, Septem- ber 2, 2005

Kouji Okada, Ryuji Wakikawa, Keisuke Uehara, Jun Murai, “OLSR for InternetCar System”, OLSR Interop and Workshop 2004, San Diego CA USA, August 6-7 2004

5.2 作品

zebra-olsr6d

6 進捗状況と今後の日程

現在は、分散ファイルシステムであるgLusterFS上 にData Preforwarding機構の実装を行っている。ま た、ユーザファイルアクセスパターンについてより詳 細な検討を行うため、複数ユーザのファイルアクセス パターンデータ取得を行っている。

今後の課題として以下の項目が考えられる。

• ファイル関連性アルゴリズムの改良

現在のファイル関連性アルゴリズムでは、イベン トキー拡張子とアクセス頻度の高いディレクトリ にのみ基づいたデータ転送が行われている。しか し、先行研究ではファイルのアクセス履歴とファ イル属性情報を組み合わせることにより、より正 確なファイル関連性評価が可能であることが示さ れている。本研究では、複数ユーザによるファイ ルアクセス履歴データを評価した上で、現状のア ルゴリズムで精度に問題が発生した場合、アルゴ リズムの精度向上のためにこれらの情報を用いる ことを計画している。

• 通信帯域予測アルゴリズムの改良

本研究では、過去に実現された実効通信帯域を統 計的に処理することにより、ファイルサーバ間の 通信帯域を予測する手法を用いる。しかし、この 直感的な予測は、実現可能通信帯域の予測はある 程度の粒度で可能と言えるが、突発的な大量デー タ転送を予測できない問題を持っている。そして、

突発的データ転送の影響はエッジネットワークに 近づくほど大きくなってしまう。さらに、統計処 理をするために十分なデータが収集できていな い場合には、本アルゴリズムの精度は著しく低下 してしまう。したがって、統計データを補完する 実測評価を行う必要があると考えられる。本研究 では、各サーバクラスタ間で定期的にネットワー ク遅延を測定している。それらのネットワーク遅 延のばらつきから通信帯域予測を行い、実際のフ ロースループット情報と組み合わせることでより 正確な通信帯域予測が可能だと考えられる。

以上の課題を解決した上で、2010年度上半期にお いて論文誌への投稿を予定している。

参考文献

[1] T. Hirofuchi, E. Kawai, K. Fujikawa, H .Suna- hara, “USB/IP - a Peripheral Bus Extension for

Device Sharing over”,IP Networ k Proceedings of the 2005, USENIX. Annual TechnicalConfer- ence, April, 2005

[2] J. Satran, K. Meth, C. Sapuntzakis, M.

Chadalapaka, E. Zeidner“Internet Small Com- puter Systems Interface (iSCSI)”,Request for Comments (Draft Standard), Internet Engineer- ingTask Force, April 2004.

[3] K. Muda, Y. Nishida, K. Okada, H. Yoshifuji, R.

Wakikawa, “Problem Statement of Internet Uni- versal Serial Bus (iUSB)(work in progress, draft- muda-iusb-ps-00).”Internet Draft, Internet En- gineering Task Force,July 2, 2007.

[4] Hitesh Ballani, Paul Francis, “Towards a Global IP Anycast Service,” SIGCOMM 2005, August, 2005, Philadelphia

[5] E. Riedel and G. Gibson, “Understanding Cus- tomer Dissatisfaction with Underutilized Dis- tributed File Servers,” Proc. Fifth NASA God- dard Space Flight Center Conf. on Mass Storage Systems and Technologies, 1996

[6] John Heidemann , Dhaval Shah, “Location- aware scheduling with minimal infrastructure”, Proceedings of the Annual Technical Conference on 2000 USENIX Annual Technical Conference, p.11-11, June 18-23, 2000, San Diego, California [7] Mathias Boc, Anne Fladenmuller, Marcelo Dias de Amorim, “Otiy: Locators tracking nodes.”

3rd CoNext 2007, December 10-13, New York, NY, USA, 2007

[8] Thomas M. Kroeger, Darrell D. E. Long, “Pre- dicting file system actions from prior events”, In Proceedings of the 1996 annual conference on USENIX Annual Technical Conference, San Diego, CA, 1996

[9] A. Amer, D. D. E. Long, J. F. Paris, and R. Burns. “File access prediction with ad- justable accuracy”. In Proceedings of the Inter- national Performance Conference on Computers and Communication (IPCCC 02). Phoenix, AZ, USA. April 2002.

[10] T. M. Kroeger and D. D. E. Long. “The case for efficient file access pattern modeling” In Pro- ceedings of the Seventh Workshop on Hot Topics in Operating Systems (HotOS-VII), pages 149, Rio Rico, Arizona, Mar. 1999. IEEE.

[11] J. Griffioen and R. Appleton. “Reducing file sys- tem latency using a predictive approach.” In USENIX Summer Technical Conference, pages 197207, June 1994.

[12] T. Yeh, D. D. E. Long, S. A. Brandt, “Using program and user information to improve file prediction performance” In Proceedings of the International Symposium on Performance Anal- ysis of Systems and Software (ISPASS’ 01). Tuc- son, AR, USA. November 2001.

[13] D. Ellard, M. Mesnier, E. Thereska, G. R.

Ganger, M. Seltzer. “Attribute-Based Predic- tion of File Properties” Harvard Computer- Science Group Technical Report TR-14-03. De- cember 2003.

[14] frank wang, c. liao, n. helian, chris thompson, s. wu, y. deng, v. khare and a. parker, “accel- erating linux/windows file systems by predict- ing access frequency”, in poster sessions of uk e-science all hands meeting, 2007.

[15] Peng Xia , Dan Feng , Hong Jiang , Lei Tian , Fang Wang, “FARMER: a novel approach to file access correlation mining and evaluation refer- ence model for optimizing peta-scale file system performance”, Proceedings of the 17th inter- national symposium on High performance dis- tributed computing, June 23-27, 2008, Boston, MA, USA

[16] 原田義明, 岡村耕二, “統計情報を利用したトラ フィックバリエーションの見積もりに関する研究”, 信学技報,電子情報通信学会,2007.10.