2011 年度 修士論文
ファイル転送量をメトリック としたデータ駆動型 ALM
提出日： 2012 年 1 月 31 日
指導：後藤滋樹教授
早稲田大学大学院 基幹理工学研究科 情報理工学専攻 学籍番号： 5110B073-3
高田 綾香
目次
1 序論 5
1.1 研究の背景 . . . 5
1.2 研究の目的 . . . 5
1.3 本論文の構成 . . . 6
2 マルチキャストとその種類 7 2.1 マルチキャスト . . . 7
2.1.1 IPマルチキャスト . . . 7
2.1.2 ALM (Application-Layer Multicast) . . . 7
2.2 ALMの種類 . . . 8
2.2.1 ツリー型ALM . . . 8
2.2.2 メッシュ型ALM . . . 9
2.2.3 データ駆動型ALM . . . 9
2.3 ALMの課題 . . . 10
3 提案手法 11 3.1 ファイル転送量を考慮したデータ駆動型ALM . . . 11
3.2 ファイル転送量の取得 . . . 11
3.3 隣接ノードの選別 . . . 12
3.3.1 新規参加ノードに対する選別 . . . 12
3.3.2 離脱ノードに対する代替選別 . . . 13
3.4 提案手法の評価方法 . . . 13
4 実証実験 14 4.1 実験の前段階 . . . 14
4.1.1 目的 . . . 14
4.1.2 データ駆動型ALMの実装 . . . 14
目次
4.1.3 隣接ノード選別の実装 . . . 16
4.2 実験の内容 . . . 16
4.2.1 実験の環境 . . . 16
4.2.2 実験に用いたノードの詳細 . . . 17
4.3 実験の詳細 . . . 18
4.3.1 実験1：個々のノードの転送所要時間とその変動 . . . 18
4.3.2 実験2：全体配信の転送所要時間 . . . 18
5 実験の結果と考察 19 5.1 実験1：個々のノードの転送所要時間とその変動. . . 19
5.1.1 転送時間測定の結果と考察 . . . 19
5.1.2 転送時間の変動測定の結果と考察 . . . 22
5.2 実験2：全体配信の転送所要時間 . . . 23
5.2.1 実験2の結果 . . . 23
5.2.2 実験2の考察 . . . 24
6 結論と今後の課題 25 6.1 結論 . . . 25
6.2 今後の課題 . . . 25
図一覧
2.1 IPマルチキャスト（左）とALM（右） . . . 8
2.2 ツリー型ALM（左）とメッシュ型ALM（右） . . . 9
2.3 データ駆動型ALM . . . 10
3.1 新規参加ノードに対する隣接ノードの選別 . . . 12
3.2 離脱ノードに対する代替選別 . . . 13
4.1 サーバノードとセカンダリサーバノード . . . 14
5.1 個別ノードの転送時間 . . . 19
5.2 個別ノード転送時間の変動 . . . 22
5.3 個別転送所要時間の合計 . . . 23
表一覧
4.1 実験に用いたノード . . . 17 5.1 トラフィックを増大させる通信処理 . . . 21 5.2 提案手法と既存手法の転送時間増加率 . . . 24
第 1 章 序論
1.1 研究の背景
ひとつの発信元から送られたファイルを複数の宛先に同時に送信する技術をマルチキャスト という。通常のマルチキャストは経路上のルータがファイルをコピーし情報を伝播するが、こ れをアプリケーションレイヤで実現、つまりルータの代わりに各エンドホストにファイルをコ ピーさせ伝播する手法をALM (Application-Layer Multicast)と呼ぶ。
ALMは別名P2Pマルチキャストとも呼ばれ、ファイル共有などと同様にコンテンツ配信の 手法として注目を集める技術のひとつである。データ転送方式の観点からALMはツリー型、
メッシュ型、そしてデータ駆動型の３種に大別されている。既存の研究では先述した３種の方 式のどれか、あるいはその複合形式上での転送経路の決定法、遅延の解消や状況変化への耐性 が問われてきた。
1.2 研究の目的
データ駆動型ALMは各ノードが隣接するノードと保持するデータ情報を交換し、それを元 に互いに足りないデータを要求しあう方式である。そのためノードがデータを受信するまで にかかる時間は、隣接ノードの選別方法によって大きく左右されることとなる。しかし隣接 ノード選別に用いられるメトリックとしては、すでに隣接しているノード数以外にはノード間 スループットだけが実際に広く使われてきた。データ転送の性質上単純にスループットをメト リックとして用いたとき、その遅延はあくまでリンク間の距離に依存するものとなり、場合に よってはノードごとに受信時間に大きな差がでることとなる。
そこで本論文は隣接ノードの選別にスループット以外のメトリックとしてファイル転送量、
すなわちノードがすでに受信しているデータ量を取り入れた手法を提案する。提案手法を実験 によって既存のスループットをメトリックとした手法と比較し、その有効性を示す。
第 1 章 序論
1.3 本論文の構成
本論文は以下の章により構成される。
第1章 本研究の概要を述べる。
第2章 マルチキャスト及び従来のALMを説明する。
第3章 提案手法を解説する。
第4章 評価実験について述べる。
第5章 実験結果を示して、結果を考察する。
第6章 まとめと今後の課題を述べる。
第 2 章
マルチキャストとその種類
2.1 マルチキャスト
ひとつの相手ではなく複数の相手にデータを送るとき、通常の1対1の通信では何回も繰り 返しデータを送らなければならない。それに対して1回の送信で複数の相手にデータを届ける 仕組みがマルチキャストである。主にコンテンツ配信サービスなどで使用される。
同じくコンテンツ配信に用いられるファイル共有とは違い短時間、あるいは同時に複数の ノードにデータを送るために使われることが多い。現在はラジオやテレビ、テレビ会議などを 含むリアルタイムなコンテンツ配信サービスに用いられている。
2.1.1 IPマルチキャスト
IPマルチキャストは後述のALMと比較しIPレイヤで実現されるマルチキャストであるこ とからこう呼ばれ、通常マルチキャストとはこちらのほうを指す。送信元はマルチキャストア ドレスという特殊なアドレスに1度データを送るだけでマルチキャストを利用できる。送り出 されたデータはその経路の途中で、必要に応じてルータによって複製されていき、マルチキャ ストアドレスが割り当てられた受信者すべてに届けられる。
マルチキャストはそのアドレス集約の困難さにより経路情報が膨大になってしまうことや、
プロトコルの実装そのものが難しいなどの問題がある。現在IPTVなどすでにいくつかの商用 サービスで使用されてはいるが、いまだに広く普及するには至っていない。
2.1.2 ALM (Application-Layer Multicast)
ALMはマルチキャストを上位のアプリケーションレイヤで実現させた仕組みである。デー タの複製やルーティングをルータの代わりにノードが行う。各々のノードが機能を管理するた め、サーバの負荷を大幅に軽減し、なおかつIPマルチキャストが抱えるアドレス集約の困難 性や実装・設計の問題をすべて解決できるという利点がある。
第 2章 マルチキャストとその種類
図 2.1: IPマルチキャスト（左）とALM（右）
上の図2.1に、IPマルチキャストとALMの挙動の違いを示した。
2.2 ALM の種類
IPマルチキャストではルーティングは送信元を根とするデータ配信木によって行われる。一 方ALMはより柔軟で自由な設計が可能なので、木構造である配信木を利用する他にも網状の メッシュ型や、２つを組み合わせたハイブリッド型など複数のデータ転送方式が存在する。こ れら方式はツリー型、メッシュ型、そしてデータ駆動型の3つに大別できる。3つの方式の挙 動の概略図をツリー型とメッシュ型は図2.2、データ駆動型は図2.3に示し、それぞれについて の解説を以下に述べる。
2.2.1 ツリー型ALM
データは送信元である根から木に沿って葉までの経路を辿る。そのため、経路の管理がしや すく遅延も少ないのがこの方式の特徴である。その反面、ノードの離脱や故障が起こるたび にツリーを再構成する必要があり、離脱が頻繁に起きがちなALMシステムでは対策が必須と なっている。木構造では1つのノードが離脱すると、その下のノードすべての配信処理が滞る など影響を受けてしまう。問題のノードが根に近ければ近いほどツリーの再構成による影響は 増大する。また再構成の失敗は即配信の失敗へとつながるので、ツリー型ALMの既存研究は、
そのほとんどが配信木の構築法だけでなく耐障害性についても言及している。既存の解決策と しては、あらかじめ代替経路を用意し再構成にかかる時間と手間を減らす方法[2]、配信木を 分割し、複数の部分木を並列に利用する方法[3]などが提案されている。
第 2章 マルチキャストとその種類
図 2.2: ツリー型ALM（左）とメッシュ型ALM（右）
2.2.2 メッシュ型ALM
ツリー型から親子関係の制約をなくし、ノード間の関係をより緩くした手法。メッシュ状の ネットワークにflooding、つまりすべての相手に対してデータを送りつけることで配信を実現 している。この手法ではノードはデータを受け取り、初めて受信したものであるれば送り元以 外の隣接ノードにデータをまた送信、そうでなければ転送を行わないという単純な動作を繰り 返す。複数のノードからデータを受信可能なので高いデータ浸透率を誇るが、何度も同じデー タを受け取ることになるなど転送の無駄が多く効率は悪い。そのため、この方式ではいかに データ転送の無駄を抑えるかが課題となっている。既存の研究では同じ相手に一定回数繰り返 して送り終えるまでランダムに選んだ隣接ノードにデータを送り続ける方式や、ツリー型と組 み合わせて通常は親から、足りないデータだけを隣接ノードから入手する方式[4]が提案され ている。
2.2.3 データ駆動型ALM
メッシュ型ALMのようにデータを送るのではなく、保持しているデータの情報を送ること で、足りないデータだけを相手に要求させる手法。メッシュ型の転送の無駄を省き、なおかつ ノードの離脱に強いメッシュ型ALMの性質を保てるのが利点。ただし他２種類のALM方式に 比べると、データの転送前に一度要求を受けるという動作を挟んでいるため遅延時間が長くな る。またデータを受け取るたびに保持情報を周囲に通知すると、頻繁な通知のやり取りによっ てトラフィックが圧迫され、遅延が増大する危険性がある。しかし通知頻度を下げると、今度
第 2章 マルチキャストとその種類
図 2.3: データ駆動型ALM
は周囲のノードに保持情報が渡るのが遅れ、結果的に全体にデータが行き渡るまでの所要時間 が長くなる恐れがある。よって通知を毎回ではなく、一定の時間ごとに制限したり、一度通知 した後は要求すべてを処理し終えるまで次の通知を行わない[5]、などの方式が提案されてい る。
保持情報の通知頻度だけでなく、データ駆動型ALMでは隣接ノードの選び方も重要な問題で ある。たとえば隣接ノードとのスループットが悪ければ、当然データの受信にも時間がかかるよ うになる。また隣接するノードの数が多ければそれだけより多くの相手からデータをもらえる ので、逆に時間を短縮できる。単純なランダムで選別する方式に加え、CoolStreaming/DONet [6]ではスループットに応じても選別を行う方法がとられている。
2.3 ALM の課題
これまでにマルチキャストとはなにか、ALMとその種類についてそれぞれの利点と問題を 述べた。ALMは提案されて以降、例として挙げたものを含めさまざまな研究がなされてきた。
しかしALMはいまだ発展途上であり研究の余地が大いに残っている。既存の研究はそのほと んどがあくまでIPマルチキャストの拡張・発展形といったのものが多かった。しかしネット ワーク層で動作するIPマルチキャストと比べるとアプリケーション層で動くALMは、より多 くの情報を活用できるはずである。
たとえば、今までルーティングにおけるメトリックとしてはスループットのみが注目されて いる。そこで“ファイル転送を考慮したALMルーチング手法の最適化” [7]ではツリー型ALM システムでの配信木の構築において、ノードがすべてのファイルを受け取り終えるまでに必要 なデータ量をメトリックに加え、結果的にスループットだけをメトリックとしたときよりも高 い性能を実現している。次の章ではこのことを踏まえ、ファイル転送を考慮した新たなデータ 駆動型ALM方式を提案し、その仕組みについて述べる。
第 3 章 提案手法
3.1 ファイル転送量を考慮したデータ駆動型 ALM
データ駆動型ALMは、ノード間で互いのデータ保持情報を通知することでデータを補完し あう方式である。ゆえにデータ保持情報を隣接ノードのデータ補完の目的以外でメトリックと して扱った場合でも、比較的少ないオーバーヘッドで処理できると推測される。さらに、デー タ駆動型ALMのノードは、隣接ノードの保持情報をもとに足りないデータを要求するので、
保持するデータ量が大きなノードと隣接すれば、ノードはより多くのデータを一度に得られる と期待できる。またこれは各ノードがスループットの高いノードと隣接する従来の手法と異な り、データを受信する時間がノード間のスループットに依存しないという利点もある。
そこで本研究では隣接ノードを割り当てるときのノード選別時のメトリックとして、従来の ノード間スループットではなくファイル転送量を採用した手法を提案する。ここでいうファイ ル転送量とは、１個のファイルを配信するにあたりファイルを複数のデータ片に分割して送信 する状況を想定したとき、全体のデータ量に対する受信済みデータ量の割合とする。
以下では提案手法の具体的な動きについて述べる。
3.2 ファイル転送量の取得
各ノードのデータ保持情報は、通常隣接ノードに対してのみ通知される。提案手法ではこ れに加え、データ保持情報をサーバノードにも通知を行う。サーバは受け取った情報を元に各 ノードのファイル転送量を把握し、隣接ノード選別のメトリックに用いる。
ここで、データ保持情報の通知はノードが新たなデータを受信するたびに行うこととする。
2.2.3節で述べたように、通知頻度が高ければトラフィックを圧迫し、低ければ保持情報の周
知に遅れが出ることとなる。今回はファイル転送量をメトリックとして扱っているため、トラ フィックの解消よりもノードのデータ保持情報を正確に捉えることを優先させた。
第 3章 提案手法
図 3.1: 新規参加ノードに対する隣接ノードの選別
3.3 隣接ノードの選別
隣接ノードの選別が行われるタイミングは以下の2つである。
(1) ネットワークに新規ノードが参加するとき
(2) 隣接ノードが離脱し、隣接ノード数が少なくなったとき
3.3.1 新規参加ノードに対する選別
1 最初に新規ノードはサーバに対し、ネットワークへの参加要求を送信
2 サーバは新規ノードを自身がもつノードリストに追加、リストからランダムに選んだ ノードのうち、ファイル転送量が大きいものを新規ノードの隣接ノードとして選別する 3 新規ノードはサーバから受け取った情報をもとにノードと隣接し、受信を始める
(1) の“ネットワークに新規ノードが参加するとき”とは、文字通り新たにノードがALMネッ
トワークに参加するときを指す。その挙動を上の図3.1に示した。ファイル転送量が大きいノー ドと隣接することで、新規ノードはそれだけ早く、かつ多くのデータを受信できる。
第 3章 提案手法
図 3.2: 離脱ノードに対する代替選別
3.3.2 離脱ノードに対する代替選別
1 ノードが隣接ノードの離脱を検知
2 隣接ノード数が下限 （後述）を下回ると、 サーバに代わりのノードの 割り当てを要求する
3 ノードリストからランダムに選んだノードのうち、ファイル転送量が大きいものを 隣接ノードとして選別する
4 サーバはノードと新しい隣接ノード両方に、お互い隣接するよう通知
(2) の“隣接ノードが離脱し、隣接ノード数が少なくなったとき”とは、(1) とは違いすでに
ネットワークに参加しているノードについて、その周辺の隣接ノードが離脱したときを指す。
隣接ノードが減ることはノードにデータを送信する相手が減ることと等しい。ゆえに、隣接 ノードが減りすぎた場合には、離脱したノードの代わりを探す必要がある。提案手法では隣接 ノード数に下限を設け、隣接ノード数がその下限を下回るときに代わりのノードの割り当てを 行うこととする。選別の様子を図3.2に示した。隣接ノード数に下限を設けることで、ノード は常に一定数以上の通信相手を確保し、データを受信できる。
3.4 提案手法の評価方法
以上、この章では提案手法とその挙動について解説した。次章では本研究で行った既存手法 と提案手法の比較実験について述べる。
第 4 章 実証実験
4.1 実験の前段階
4.1.1 目的
実験では第3章で挙げた提案手法と既存の手法を比較し、提案手法の有効性を検証した。
既存手法と提案手法の最大の違いはデータ駆動型ALMにおける隣接ノード選別のときに、
既存手法 ： ノード間リンクのスループット 提案手法 ： ファイル転送量 のどちらをメトリックとして用いたかという点である。
環境としてはデータ駆動型ALMシステムを実際に用意し、次にその上でそれぞれの手法を 用いたファイル配信を行った。このときにノードがシステムに参加してからデータをすべて受 信完了するまでの所要時間を、以降転送時間と表記する。また今回実装したデータ駆動型ALM システムは、一般的なALMの用途としてリアルタイムなコンテンツ配信サービスを想定して いる。具体的には動画ストリーミング配信を想定し、約13MBの動画ファイルを8個に分割、
サーバから1つずつ定期的に配信していく形をとった。
4.1.2 データ駆動型ALMの実装
実装したシステムではまず図4.1のように、サーバとセカンダリサーバを用意した。
図 4.1: サーバノードとセカンダリサーバノード
第 4章 実証実験
サーバノードはデータの配信元であり、新規ノードの登録や隣接ノードの選別などを行う 管理サーバの役目を負ったノードである。またセカンダリサーバはサーバから直接データを受 け取る唯一のノードであり、初めからALMネットワークに登録されている。配信の初期の新 規ノードに対し隣接し、サーバから受信したデータを送信する役目を負う。このサーバとセカ ンダリサーバのみがALMネットワークに存在する状態を初期状態とし、そこから新規ノード が加わっていく。初期状態からは以下のような動作を行った。
データ駆動型ALMの動作
1 サーバが5秒ごとにセカンダリサーバにデータを転送
（実際はデータの情報を通知 → セカンダリがデータの要求を送り返す → 送信の順）
2 ランダムに新規ノードがサーバに参加要求を送る
3 サーバは新規ノードをノードリストに登録
選別した隣接ノードの情報を新規ノードに、隣接ノードに新規ノードの情報を通知
4 ノードは隣接ノードからデータ保持情報を受け取り、足りないデータがあれば要求
5 データを受信し終えたノードは隣接ノード及びサーバにデータ保持情報を通知
6 各ノードは隣接ノードからのデータ要求、またはサーバからの 新しい隣接ノードの通知を受け取るまで待機
7 すべてのデータを受信した後は、5分後にサーバと隣接ノードに通知してから離脱
第 4章 実証実験
4.1.3 隣接ノード選別の実装
新規ノード、あるいは離脱ノードの代わりとして隣接ノードの選別を行うときの動作につい て述べる。まずサーバはノードリストからランダムに5個のノードを選ぶ。さらにその5つの ノードからファイル転送量がもっとも大きいもの、もしくはスループットが高いもの2つを隣 接ノードとして選別する。前者が提案手法、後者が既存手法にあたる。
ファイル転送量は前述の“データ駆動型ALMの動作”におけるでノードから得たデータ5 保持情報をもとに得ている。一方スループットは、新規ノードがネットワークに参加してきた ときに、5個の隣接ノード候補それぞれとのRTTをtracerouteコマンドにより計測したもの をスループットとして用いた。
4.2 実験の内容
4.2.1 実験の環境
ここでは今回使用した実験環境について述べる。環境の構築にはPlanetLab [1]を利用した。
PlanetLabとは、世界各地の大学や企業などの組織が中心となって形成している大規模な実験
ネットワークである。Planetlabに参加する組織はネットワーク上のノードとなるPCを2台提 供することで、他の参加しているすべてのノードを実験に使用できるようになっている。今回 の実験はこのPlanetLab上で実装したデータ駆動型ALMシステムを使って行った。
第 4章 実証実験
表 4.1: 実験に用いたノード ノードID ドメイン名
【０】 nis-planet2.doshisha.ac.jp
【１】 planetlab6.goto.info.waseda.ac.jp
： planetlab1.bupt.edu.cn
： ・・・ ・・・ ・・・
： ・・・ ・・・ ・・・
： ・・・ ・・・ ・・・
： ・・・ ・・・ ・・・
： ・・・ ・・・ ・・・
【50】 planetlab3.comp.nus.edu.sg
4.2.2 実験に用いたノードの詳細
配信実験では最大51個のノードを使って転送所要時間を計測した。ここで51個のノードは、
表4.1のようにそれぞれサーバノード、セカンダリサーバノード、残り49個の一般ノードに よって成る。つまり、ファイルはサーバから最大50個の受信ノードに対して配布される。
さらにノードにはネットワークへの参加順にそれぞれIDを付与している。実験の初期状態 ではネットワーク上に存在するノードは、サーバとセカンダリサーバだけなので、この2つに はそれぞれ固定ID ”0”と”1”がふられている。それ以降のノードには参加次第IDが割り振ら れていくので、IDは不定である。
今回の実験では世界規模の広域な配信環境を想定している。そこで51個のノードはPlanetLab 上から互いの地理的な距離が近いものから遠いものまで、偏りなく選んだ。
第 4章 実証実験
4.3 実験の詳細
以下2つの実験は、どちらも提案手法と既存手法の両方について転送所要時間を計測した。
4.3.1 実験 1：個々のノードの転送所要時間とその変動
ノードの最大数である50個のノードにファイルが配信されたとき、個々のノードがシステ ムに参加してから受信終了までの所要時間を転送時間として計測した。さらにノードごとの転 送時間の変動を測り、配信時間の公平性を探った。
4.3.2 実験 2：全体配信の転送所要時間
各ノードのネットワークへの参加は、完全にランダムなタイミングで行われるため、実験開 始からノード全体にファイルが行き渡るまでの時間もまたランダムである。そこでネットワー ク上の各ノードの転送時間を合計し、全体配信の転送時間とした。本実験では受信ノードの総 数が1個〜50個だったときそれぞれの場合について、ノードの転送時間を計測し、合計した。
第 5 章
実験の結果と考察
この章では4.2.2節で述べた2つの実験の結果と考察について述べる。
5.1 実験 1 ：個々のノードの転送所要時間とその変動
5.1.1 転送時間測定の結果と考察
図 5.1: 個別ノードの転送時間
第 5章 実験の結果と考察
まず、各ノードにかかる転送時間がノード1個の初期状態から参加するノードが増えるにつ れ、どのように増減しているかについて解説する。図5.1を見ると、提案手法については、当 初転送時間が減少しているが途中でごく緩やかな増加を始め、最後は約78000ミリ秒 = 約1 分18秒のあたりに収束していくことがわかる。この結果は、配信時間が提案手法によって選 別された隣接ノードのおかげで短縮されていることを示している。また配信時間がひとつの値 に収束していくことから、提案手法を用いることで、ノードの総数に関わらず全ノードの転送 時間をほぼ同程度に保てていると推測できる。
次に、提案手法と比較して、既存手法を用いたときの転送時間について述べる。図5.1では 転送時間は一度は減少しているものの、その後は増加していく傾向にあることが見て取れる。
これはノード数の増加によってデータの送受信や保持情報の通知によるトラフィックが増し、
システム全体が遅れているためだと考えられる。なおトラフィックの増加による転送時間の増 大は提案手法でもみられるが、こちらは前者に比べるとごくわずかである。
その理由を考察するために、データ駆動型ALMでのトラフィックが増加する原因となりう る処理を整理してみたところ、以下の3つに分類できた。
・保持情報の通知
・隣接ノード選別に必要なメトリックの情報収集 ・データの送受信
提案手法と既存手法でのこれら処理の負荷を比べるため、その頻度や通信する相手、やりと りするデータサイズを次の表5.1にまとめた。
第 5章 実験の結果と考察
表 5.1: トラフィックを増大させる通信処理
保持情報の通知 メトリックの情報収集 データの送受信 提案手法 既存手法 提案手法 既存手法 提案手法 既存手法
処理の頻度 ＜
保持情報通知 と同じ
隣接ノード選別回数
と同じ ＜
通信相手 隣接ノード 隣接ノード サーバ 隣接ノード候補 ノード ノード
データサイズ 小 小 小 小 ＞
まずメトリックの情報収集については、その頻度が既存手法ではせいぜい50程度であるこ とに比べると、提案手法ではノードの増加と比例するため、一見後者の負荷がより重くなって いるかとおもわれる。しかし後者はサーバに一回情報を送信しているだけなので、各隣接ノー ド候補とのスループットを計測している既存手法での情報収集のほうが負荷は重く、オーバー ヘッドが大きい。
次のデータの送受信では、提案手法のほうが一度に多くのデータを提供できるという理由か ら、より少ない回数かつ大きいサイズのデータを送ることができる。また保持情報はデータの 受信のたびに通知されているので、提案手法は少ない回数で処理でき、これもまた既存手法よ りも負荷が軽いことになる。
以上の考察から、既存手法でのノード数増加によるトラフィック増大の原因をさらに絞り込 む。ここで3つの処理の内、メトリックの情報収集は確かに大きなオーバーヘッドとなってい るが、そのためのトラフィック量は常に一定でノード数とは比例しないため、これが原因だと は考えにくい。ゆえにトラフィック増大の原因は、ノード数の増加にともなって増えた保持情 報の通知とデータの送受信処理だとわかった。
第 5章 実験の結果と考察
5.1.2 転送時間の変動測定の結果と考察
図 5.2: 個別ノード転送時間の変動
上の図5.2により、スループットをメトリックに用いた既存手法での転送時間が明らかに広 い範囲に分布していることと比較すると、提案手法ではどのノードもほとんど同じ転送時間で あることがわかる。前者が広い範囲にわたるのは、転送時間が隣接ノードとのスループットに 依存しているからである。ノードによっては数ミリ秒から1分、最大で約390000ミリ秒=約 6分30秒もの差があることを考えれば、既存手法では転送時間の公平性が保たれているとは言 いがたい。一方提案手法では、ノードごとの転送時間の差は大きくとも約57000ミリ秒 = 約 57秒で、ほぼ同じ程度の転送時間でファイルを受信できていることになる。
第 5章 実験の結果と考察
5.2 実験 2 ：全体配信の転送所要時間
5.2.1 実験2の結果
図 5.3: 個別転送所要時間の合計
上の図5.3 が結果のグラフである。これによりファイル転送量を用いた提案方式では全体の 転送時間は、受信ノードの数が増えるにつれ一定の比率で大きくなっていることが見て取れる。
一方のスループットを使った従来方式では、こちらもほぼ直線状ではあるが明らかに増加の勢 いがより激しい。
第 5章 実験の結果と考察
5.2.2 実験2の考察
ここで、ALMネットワーク上のノード総数に対する合計転送時間の比率を転送時間増加率 とする。転送時間増加率は以下の式で算出できる。
転送時間増加率 [秒/個] = 合計転送時間[ミリ秒]* 1000／ ノード総数 [個]
提案手法と既存手法、それぞれの転送時間増加率を算出したところ、表5.2のようになった。
表 5.2: 提案手法と既存手法の転送時間増加率 転送時間増加率（秒/個）
提案手法 約78.06
既存手法 約138.89
これはおおよそ1.78倍の差であり、提案手法を用いることでALMネットワークに参加し ているノード数に関わらず、大幅に転送時間を短縮できることが示せた。
第 6 章
結論と今後の課題
6.1 結論
今回評価した提案手法では、データ駆動型ALMシステムにおける隣接ノードを従来のス ループットではなくファイル転送量をもとに選別し、ノードに割り当てた。実験からはノード がファイル転送量の大きいノードと隣接することで、より短時間に効率よくデータを受信でき ることがわかった。また、従来の手法ではネットワークに参加するノードが増加すると、トラ フィックも増大しシステム全体に影響が出ていたが、提案手法を用いることでトラフィックの 増大を抑えられることがわかった。
さらに、ノードがファイルを受信し終えるまでの時間は既存の方式では周囲の隣接ノードと のスループットに依存し、ノードによって時間に大きな差がみられた。一方提案手法ではノー ドによる差はほとんどなく、公平性の高い配信を実現できることがわかった。
6.2 今後の課題
本論文ではファイル転送量を隣接ノード選別に用いることで、スループットをメトリックと して選んだ場合よりも短い時間でデータを受信できることを示した。しかしながら、従来の手 法の転送時間はあくまでスループットに左右されるものなので、ノード間スループットがきわ めて小さい環境では既存手法のほうが有効である可能性は大いにある。また今回はそれぞれの 手法を個別に評価したが、今後はメトリックとしてファイル転送量とスループットの両方を使 用した場合の評価も行いたい。
謝辞
本学士論文の作成にあたり日頃より御指導を頂いた早稲田大学理工学部の後藤滋樹教授に深 く感謝致します。また、多大なる御協力を頂きました後藤研究室の諸氏に感謝致します。
参考文献
[1] planet-lab.org,
“Planet Lab—An open platform for developing, deploying, and accesing planetary-scale services”,
https://www.planet-lab.org/
[2] 渡辺雅人, 高橋修,高橋信行, “アプリケーションレベルマルチキャストにおける ノード情報を用いた予備親決定手法の提案と評価”,
http://ci.nii.ac.jp/naid/110007338510
[3] 小林正裕, 中山英久, Nirwan Ansari, 加藤寧, “利用可能帯域を考慮した ALMツリー構築法の提案”,
http://ci.nii.ac.jp/naid/110006419332
[4] D. Kosti’c, A. Rodriguez, J. Albrecht, A. Vahdat, “Bullet:High Bandwidth Data Dissemination Using an Overlay Mesh”,
http://nsl.epfl.ch/dkostic/publications/bullet-sosp03.pdf
[5] 越賀雅士, 太田義勝, 鈴木秀智, “データ駆動型ALMによるデータ配信手法について”, http://ci.nii.ac.jp/naid/110007499342
[6] X. Zhang, J. Liuy, B. Liz, T.P. Yum, “CoolStreaming/DONet : A Data-Driven Overlay Network for Efficient Live Media Streaming”, http://www.cs.sfu.ca/~jcliu/Papers/CoolStreaming.pdf
[7] 牧村真吾, 三好匠, “ファイル転送を考慮したALMルーチング手法の最適化”, http://ci.nii.ac.jp/naid/110003172828.
