専攻名(研究分野) Department
研究指導名 Research guidance
氏名 Name 学籍番号 Student ID
number
指 導 教 員 Advisor
印 Seal
研究題目 Title
Date of submission: 01/ 31/ 2012
修 士 論 文 概 要 書
Summary of Master’s Thesis
5110B073 – 3 CD 情報理工学専攻
情報システム工学研究
高田 綾香
後藤 滋樹
ファイル転送量をメトリックとしたデータ駆動型 ALM
概 要
データ駆動型ALMは各ノードが隣接するノードと保 持するデータ情報を交換し、それを元に互いに足りない データを要求しあう方式である。現在まで隣接ノード選 別に用いられるメトリックとしては、すでに隣接している ノード数以外にはノード間スループットだけが実際に広 く使われてきた。本論文では隣接ノードの選別にスルー プット以外のメトリックとしてファイル転送量、すなわち ノードがすでに受信しているデータ量を取り入れた手法 を提案する。提案手法は評価実験によって既存のスルー プットをメトリックとした手法と比較し、その有効性を 検討した。
1 マルチキャスト
1.1 IP マルチキャストと ALM
ひとつの発信元から送られたファイルを複数の宛先に 同時に送信する技術をマルチキャストという。転送経路 上のルータがファイルを複製し、伝播する手法をIPマル チキャスト、これをアプリケーションレイヤで実現、つま りルータの代わりに各エンドホストがファイルをコピー し伝播する手法をALM (Application-Layer Multicast)と 呼ぶ。
1.2 ALM の種類
ALMは別名P2Pマルチキャストとも呼ばれ、ファイル 共有などと同様にコンテンツ配信の手法として注目を集 める技術の1つである。データ転送方式の観点からALM は以下の３種に大別されている。
• ツリー型：送信元を根とする配信木に沿ってデータを転送
• メッシュ型：メッシュ状のネットワークにデータをflooding
• データ駆動型：保持するデータの情報を周囲に渡し、
足りないデータだけを相手に要求させる
図1にデータ駆動型ALMの挙動の様子を示した。
図1:データ駆動型ALM
どの種類のデータ転送方式でも、各ノードは1つ以上 のノードを隣接ノード（ツリー型では親、または子ノー
ド）として選び、データのやり取りを行う。ゆえにノー ドがシステムに参加してからデータをすべて受信完了す るまでの所要時間（=転送時間）は、隣接ノードの選び 方によって大きく左右される。
2 従来の手法
ALMにおいて各ノードが自身と隣接するノードを選ぶ 方法、つまり隣接ノード選別方式は、スループットをメ トリックとしたものがほとんどである。例えば参考文献 のCoolStreaming/DONet[2]では、まずランダムにノード をいくつか選び、さらにその中からスループットの高い ものを隣接ノードとして選ぶ方法がとられている。しか
しながらCoolStreamingを含む既存の研究はそのほとん
どがあくまでIPマルチキャストの拡張・発展形といった のものが多い。ネットワーク層で動作するIPマルチキャ ストと比べるとアプリケーション層で動くALMは、ス ループット以外のより多くの情報を活用できるはずであ る。そこで“ファイル転送を考慮したALMルーチング手 法の最適化” [3]ではツリー型ALMシステムでの配信木 の構築において、ノードがすべてのファイルを受け取り 終えるまでに必要なデータ量をメトリックに加え、結果 的にスループットだけをメトリックとしたときよりも高 い性能を実現している。このことを踏まえ、本稿ではファ イル転送を考慮した新たなデータ駆動型ALM方式を提 案する。次にその仕組みについて述べる。
3 提案手法
データ駆動型ALMは、ノード間で互いのデータ保持情 報を通知することでデータを補完しあう方式である（図 1参照）。ゆえにデータ保持情報を隣接ノードのデータ補 完の目的以外でメトリックとして扱った場合でも、比較 的少ないオーバーヘッドで処理できると推測される。さ らに、データ駆動型ALMのノードは、隣接ノードの保 持情報をもとに足りないデータを要求するので、保持す るデータ量が大きなノードと隣接すれば、ノードはより 多くのデータを一度に得られると期待できる。
本研究では隣接ノードを割り当てるときのノード選別 時のメトリックとして、従来のノード間スループットで はなくファイル転送量を採用した手法を提案する。ここ でいうファイル転送量とは、１個のファイルを配信する にあたりファイルを複数のデータ片に分割して送信する 状況を想定したとき、全体のデータ量に対する受信済み データ量の割合とする。
4 評価実験
4.1 実験の概要
本論文ではPlanetLab [1]上にデータ駆動型ALMシス テムを実装し、最大50個のノードを用いた実験を2つ 行った。
実験1では受信ノードにファイルが配信されたとき、個々 のノードがシステムに参加してから受信終了までの所要 時間を転送時間として計測した。さらにノードごとの転 送時間の変動を測り、配信時間の公平性を探った。
実験2ではネットワーク上の各ノードの転送時間を合計 し、全体配信の転送時間とした。また、ノードの総数が1 つ増えるたびに増加するノード全体の転送時間の大きさ を転送時間増加率とし、合計結果から算出した。
転送時間増加率は以下の式で計算できる。
転送時間増加率[秒/個] =
合計転送時間[ミリ秒] * 1000／ ノード総数[個]
4.2 実験 1 の結果と考察
図2:個別ノードの転送時間
図2から、スループットをメトリックに用いた既存手 法よりも、ファイル転送量をメトリックとした提案手法 のほうが格段に転送時間を短縮でき、有効であることが 示せた。また既存手法ではノードが増えるごとに転送時 間が延びていることから、スループットをメトリックに 使った場合、ノードの総数によってデータの送受信によ るトラフィックが増大することがわかった。一方の提案手 法では、トラフィックはノードの数に関わらずごくわずか で、ノードの転送時間は約1分18秒のあたりに収束して いる。ゆえに、提案手法を使った場合、ノード数の増加 によるトラフィックを抑えられる。
図3:個別ノード転送時間の変動
図3により、既存手法での転送時間が明らかに広い範 囲に分布していることと比較すると、提案手法ではどの ノードもほとんど同じ転送時間であることがわかった。前 者が広い範囲にわたるのは、転送時間が隣接ノードとの スループットに依存しているからであり、ノードによって は数ミリ秒から1分、最大で約6分30秒もの差がある。
一方後者の提案手法では、ノードごとの転送時間の差は 大きくとも57秒で、ほぼ同じ程度の転送時間でファイル を受信できていることになる。
4.3 実験 2 の結果と考察
提案手法と既存手法、それぞれの転送時間増加率を算 出したところ、表1のようになった。
表1:提案手法と既存手法の転送時間増加率 転送時間増加率[秒/個]
提案手法 約78.06
既存手法 約138.89
これはおおよそ1.78倍の差であり、提案手法を用いる ことでALMネットワークに参加しているノード数に関 わらず、大幅に転送時間を短縮できることが示せた。
5 結論
今回評価した提案手法では、ノードがファイル転送量 の大きいノードと隣接することで、より短時間に効率よ くデータを受信できることがわかった。また、従来の手 法ではネットワークに参加するノードが増加すると、ト ラフィックも増大しシステム全体に影響が出ていたが、提 案手法を用いることでトラフィックの増大を抑えられる ことがわかった。
さらに、提案手法ではファイルを受信し終えるまでの 時間はノードによる差はほとんどなく、公平性の高い配 信を実現できることがわかった。
6 今後の課題
従来の手法の転送時間はあくまでスループットに左右 されるものなので、ノード間スループットがきわめて小 さい環境では既存手法のほうが有効である可能性は大い にある。また今回はそれぞれの手法を個別に評価したが、
今後はメトリックとしてファイル転送量とスループット の両方を使用した場合の評価も行いたい。
参考文献
[1] planet-lab.org,
”Planet Lab”,https://www.planet-lab.org/
[2] X. Zhang, J. Liuy, B. Liz, “CoolStreaming/DONet”, http://www.cs.sfu.ca/˜jcliu/Papers/
CoolStreaming.pdf
[3] 牧村真吾,三好匠, “ファイル転送を考慮した ALMルーチング手法の最適化”,
http://ci.nii.ac.jp/naid/
110003172828.
