物理網構成を考慮したハイブリッド型 P2P 動画像ストリーミング配信機構の提案と評価 大阪大学 大学院情報科学研究科 末次　信介 若宮　直紀　　村田　正幸 NEC インターネットシステム研究所 小西　弘一　　谷口　邦弘 ＊ 「物理網構成を考慮したハイブリッド型 P2P 動画像ストリーミング配信の提案と評価」というタイトルで発表をはじめさせていただきたいと思います。発表者は、大阪大学大学院情報科学研究科の末次信介です。よろしくお願いします。 July 15, 2004 CQ研究会

はじめに 研究の背景 研究の目的 提案機構の紹介 シミュレーションによる評価 まとめ はじめに、発表の流れを説明します。まず研究の背景と目的を述べ、次に提案機構の紹介をいたします。その後、提案機構の性能をシミュレーションにより評価し、最後に本報告のまとめを行います。 July 15, 2004 CQ研究会

研究の背景 動画像ストリーミング配信の普及 P2P 技術の発展 動画像データを受信しながら再生 映画の予告編、ニュース映像などの配信 サーバの負荷を軽減 配信ツリーの 構築 サーバ サーバ クライアント ピア 近年、動画像のストリーミング配信が普及しています。ストリーミング配信とは、動画像データを受信と同時に再生を行う方式です。左下の図に示しますように、従来のサーバ･クライアント型モデルでの配信は、サーバは全てのクライアントに動画像データを配信する必要があり、サーバやサーバ近傍に負荷が集中してしまいます。そこで、P2P技術を用いて、ピアが受け取ったデータを他のピアに直接配信する P2P マルチキャストという手法を用いることで、サーバはたった１度の配信で多くのクライアントに動画像データを配信することができ、負荷の問題を解決することができます。しかしながら、P2P マルチキャストを実現するためには、適切な配信ツリーの構築が必要になります。 July 15, 2004 CQ研究会 P2P マルチキャスト

研究の背景 より良い配信ツリーを構築するには？ 企業や大学などのネットワークでは…… 遅延や帯域など、物理網特性を計測 長時間の観測が必要 観測のために新たにネットワークに負荷をかける 企業や大学などのネットワークでは…… 組織構成にもとづいた物理網が構成されている 支社や部署、学部や学科など 物理網特性の計測が不要 簡単に、かつ迅速に配信ツリーを構築 現在、P2P マルチキャストに関する多くの研究が行われていますが、それらの研究では、効率的な配信ツリーを構築するため、帯域や遅延などといった物理網特性を計測して、転送遅延や使用帯域を削減しています。ところが、それらの計測には長い時間がかかり、さらには観測のために新たにネットワークに負荷をかけてしまいます。企業や大学などといった組織では、支社や部署、学部や学科といった組織構成にもとづいてネットワークが構築されています。そのため、物理網構成は既知のものであり、計測を行わずとも、簡単にかつ迅速に配信ツリーを構築することができます。 July 15, 2004 CQ研究会

研究の目的 組織構成にもとづいて階層化されたネットワークを対象とした動画像ストリーミング配信機構を提案 提案機構の目標 企業や大学など 数千、数万のユーザを有する 提案機構の目標 サーバやサーバ近傍の負荷集中の軽減 ネットワークの負荷の軽減 物理網上で遠く離れたピアが繋がるのを避ける 同じデータが同じリンクを往復するのを避ける 再生開始までの待ち時間を短縮 障害による、再生の途切れ時間を短縮 そこで本稿では、企業や大学など、組織構成にもとづいて階層化されたネットワークを対象に、スケーラブルな動画像ストリーミング配信機構を提案します。また、サーバやネットワークの負荷の軽減、再生開始までの待ち時間の短縮をし、また、耐障害性を考慮して、障害による再生の途切れによる待ち時間を短縮します。 July 15, 2004 CQ研究会

動画像ストリーミング配信機構の概観 支社 本社 サブネット代表 (STS) 拠点 部署 部署 サブネット サブネット 拠点 拠点 サブネット スケジュール サーバ (SS) ツリーサーバ (GTS) 拠点 サブネット 動画像サーバ (ORG) まずは、提案機構の概観を紹介します。本社には、スケジュールサーバ、ツリーサーバ、動画像サーバの３つのサーバがあります。スケジュールサーバは、いつ配信ツリーを構築するかを、また、ツリーサーバはどのような配信ツリーを構築するかを管理します。動画像サーバは、配信ツリーの根となり、動画像を配信します。 企業には複数の支社があり、支社ごとのネットワークを拠点と呼びます。また、支社には複数の部署があり、部署ごとのネットワークをサブネットと呼びます。各拠点からは拠点の代表が選ばれ、本社にある動画像サーバを根とした、拠点間の配信ツリーが構築されます。各サブネットからはサブネットの代表が選ばれ、拠点の拠点代表を根とした、サブネット間の配信ツリーが構築されます。サブネット内でも同様に、サブネット代表を根とした配信ツリーが構築されます。 部署 拠点代表 (LTS) 普通のピア（NP） 支社 July 15, 2004 CQ研究会 支社

動画像ストリーミング配信機構の概要 １．セグメント受信スケジュール決定アルゴリズム ２．配信ツリー構築機構 ３．障害回復機構 ピラミッドブロードキャスティングを用いる 再生開始までの待ち時間を短縮 ２．配信ツリー構築機構 P2P マルチキャストを用いた動画像配信ツリー構築 サーバの負荷を軽減 物理網構成にもとづく階層化 ネットワークやピアの負荷を軽減 ３．障害回復機構 分散自律制御により短時間で障害回復 障害時の動画像の再生の途切れを削減 つまり、提案機構は、以下の３つのシステムから成ります。いつどんなタイミングで配信ツリーに参加し、動画像データを受け取るかを決定するセグメント受信スケジュール決定アルゴリズム、物理網構成にもとづいて配信ツリーの構築を行う配信ツリー構築機構、また、障害が発生したときに、配信ツリーの再構築を行う障害回復機構、があります。それぞれにおいて、再生開始までの待ち時間の短縮、サーバの負荷の軽減、ネットワークやピアの負荷の軽減、障害児の再生の途切れの削減、を図ります。 以下、この３つの機構について、順に説明を行います。 July 15, 2004 CQ研究会

１．セグメント受信スケジュール決定アルゴリズム ピラミッドブロードキャスティング 再生速度 b セグメント 動画像データ ピア 再生→ ｔ ｔ スケジュール サーバ （SS） スロット 転送速度2b 各セグメントを、異なるチャネルで繰り返し配信 動画像サーバ （ORG） セグメント受信スケジュール決定アルゴリズムでは、ピラミッドブロードキャスティングといった手法を用います。この手法では、図のように、動画像データを、セグメントと呼ばれるかたまりに分割します。それぞれのセグメントは、図のように、異なるチャネル、異なる通信路を用いて、再生速度よりも速い速度で、繰り返し配信されるスケジュールになっています。この１つ１つの区間をスロットと言います。 ピアはまず、いつどんなタイミングで動画像を受信するかを決定するため、スケジュールサーバにスケジュール決定要求を送信します。スケジュールサーバは、要求の到着した時刻をもとに、もっとも近い時間に配信が開始されるスロットを選択し、ピアに通知します。ピアは、スケジュールサーバに指示されたタイミングでまず最初のセグメント、つまり第１セグメントを動画像サーバから受信し、再生を行います。次に第２セグメントを受信し、再生、以下順次受信と再生を行います。セグメント分割を上手く行うことで、このように再生に途切れのない動画像データの受信が可能となります。 July 15, 2004 CQ研究会

セグメント、スロットごとに配信ツリーを構築 ２．配信ツリー構築機構 次に、配信ツリー構築機構について説明します。配信ツリーは、各セグメント、各スロットごとに構築されます。例えば、先ほどのスケジュールでセグメントを受信するピアは、図のように３つの配信ツリーに参加することになります。 セグメント、スロットごとに配信ツリーを構築 July 15, 2004 CQ研究会

２．配信ツリー構築機構 拠点間ツリーの構築 拠点代表（LTS） 拠点代表 本社 拠点C 拠点A 拠点B この拠点での 初めての参加要求 ツリーサーバ （GTS） 接続要求 動画像サーバのアドレスを通知 動画像サーバのアドレスを通知 動画像サーバ （ORG） では、配信ツリー構築方法の説明を行います。 まずは拠点間の配信ツリーの構築を説明します。あるクライアントが動画像の要求を行ったとすると、このクライアントは、スケジュールサーバに指定されたタイミングで、ツリーサーバに配信ツリーへの参加要求を送信します。この要求は、この拠点内での初めての参加要求ですので、ツリーサーバはこのクライアントを、この拠点の代表に任命します。それと同時に、ツリーサーバは拠点代表に、動画像サーバのアドレスを通知します。拠点代表は、通知された動画像サーバに接続要求を送信します。そして、動画像サーバと拠点代表の間に接続が確立されます。 同様に、拠点Ａのあるクライアントがツリーサーバに接続要求を送信したとすると、これもこの拠点からの初めての参加要求ですので、拠点代表に任命され、同様の手順を踏み、動画像サーバと接続を確立します。 この拠点での 初めての参加要求 拠点代表 July 15, 2004 CQ研究会

２．配信ツリー構築機構 拠点間ツリーの構築 接続できない場合は、順次子を紹介して もらうことで、再帰的にツリーを構築 本社 拠点B 子のアドレスを通知 ツリーサーバ （GTS） 拠点C 動画像サーバ （ORG） 拠点A 拠点Ｃからも同様に拠点代表が選出されたとします。この場合も同様に動画像サーバに接続要求を送信しますが、負荷の集中を避けるため、動画像サーバには、持てる子の数に制限が設けられています。これをファンアウト数と呼びます。もしファンアウト数が２だった場合、動画像サーバは既に２つの子を持っていますので、拠点Ｃの拠点代表との間に接続を確立することができません。この場合は、動画像サーバは拠点代表に、自らの子のアドレスを通知します。拠点代表は、通知された子のアドレスに、接続要求を送信し、接続を確立することになります。このように、接続できない場合は順次子を紹介してもらうことで、最終的に必ず配信ツリーに参加できることになります。 ピアは、この手順の中で紹介されたピアのリストを保持します。例えば、拠点Ｃの拠点代表は、動画像サーバおよび拠点Ｂの拠点代表のアドレスを持つことになります。この情報は、後ほど説明します障害回復において用いることになります。 次に、拠点内での配信ツリー構築について説明します。 祖先リスト: 動画像サーバ → 拠点B 子の数に制限 ファンアウト数＝２ 接続できない場合は、順次子を紹介して もらうことで、再帰的にツリーを構築 July 15, 2004 CQ研究会 ピアは、紹介されたピアのリストを保存する

２．配信ツリー構築機構 サブネット間ツリーの構築 拠点代表（LTS） 拠点Ａ サブネットB サブネットＡ サブネットC サブネットD その拠点の 拠点代表のアドレスを通知 接続要求 ツリーサーバ （GTS） 参加要求 動画像サーバ （ORG） あるサブネット内のクライアントがツリーサーバに接続要求を送信したとします。この拠点には既に拠点代表が存在しますが、このサブネットからは初めての参加要求ですので、拠点代表はこのクライアントを、サブネットの代表に任命します。それと同時に、ツリーサーバは、動画像サーバではなくこの拠点の拠点代表のアドレスを通知します。サブネット代表は、通知された拠点代表に接続要求を送信します。以下、拠点間ツリーと同じように、ファンアウト数を考慮しながらサブネット間ツリーが構築されます。 最後に、サブネット内での配信ツリーの構築方法について説明します。 サブネット代表（STS） このサブネットでの 初めての参加要求 July 15, 2004 CQ研究会

２．配信ツリー構築機構 サブネット内ツリーの構築 第１セグメントと第２セグメント以降で異なる サブネット代表（STS） サブネットA ツリーサーバを介さず 前セグメントのサブネット代表へ ツリーサーバ （GTS） そのサブネットの サブネット代表のアドレスを通知 サブネット内での配信ツリーの構築は、第１セグメントとそれ以降で異なります。 第１セグメントの場合、あるクライアントがツリーサーバに参加要求を送信したとしますと、このサブネットには既にサブネット代表が存在するので、ツリーサーバはクライアントを普通のピアに任命します。それと同時に、ツリーサーバは普通のピアに、そのサブネットのサブネット代表のアドレスを通知します。普通のピアは、通知されたサブネット代表に接続要求を送信します。 第２セグメント以降の場合は、前セグメントで普通のピアであったピアは再び普通のピアとなり、ツリーサーバへ向かわず、前セグメントのサブネット代表に直接接続要求を送信します。その後、他の階層と同じ様に、普通のピア間の配信ツリーが構築されます。 普通のピア（NP） 第１セグメントの場合 第２セグメント以降の場合 July 15, 2004 CQ研究会

３．障害回復機構 同じ階層内での障害回復 障害 同じ階層内での障害回復 ピアの離脱 各ピアは、その階層の ツリーの根までの情報を持っている 様々な原因 様々なタイミング 同じ階層内での障害回復 各ピアは、その階層の ツリーの根までの情報を持っている どの階層のツリーでも同じ 拠点間ツリー サブネット間ツリー サブネット内ツリー ファンアウト数の制限 接続要求 障害回復 最後に、障害回復機構についての説明を行います。まず障害とは、図のように、たとえばあるピアが途中で離脱することによって、配信ツリーが崩壊してしまうことを言います。離脱の原因は、ユーザが途中で受信を拒否する、回線やルータの故障などがあり、また、配信ツリー構築中、動画像配信中、など様々なタイミングで発生します。まずは、同じ階層内での障害回復の様子を説明します。障害回復を行うのは、親を失ったこの２つのピアです。各ピアは、配信ツリー構築機構のところで説明したとおり、その階層の根までの情報を持っているため、親を失ったピアは祖父母にアクセスすることができます。祖父母に接続要求を送信することで、祖父母と接続を確立します。同様に右のピアも祖父母に接続要求を送信しますが、ピアにもファンアウト数の制限があり、ファンアウト数を２とすると、接続は確立されず、子のアドレスを通知されます。通知された子と接続を確立することで、障害回復を完了します。その後、動画像の続きを新たな親から受信します。 なお、この障害回復方法は、拠点間ツリー、サブネット間ツリー、サブネット内ツリーにおいて共通です。 July 15, 2004 CQ研究会

３．障害回復機構 異なる階層間での障害回復 祖先の情報を持っていない 障害回復: 祖先の情報があるときは祖先に接続要求 サブネットA ツリーサーバ （GTS） 障害回復 参加要求 昇格 障害回復 次に、異なる階層間での障害回復の様子を説明します。あるサブネット代表が離脱すると、その子である普通のピアも障害回復を行います。ところがこの普通のピアは、サブネット代表までの情報しか持っていないため、祖父母の情報を知りません。そこで、ツリーサーバに配信ツリーへの参加要求を提出することで、再度配信ツリーへの参加をやり直します。このサブネットには現在、サブネット代表が存在しませんので、この普通のピアはサブネット代表に任命され、サブネット代表に昇格します。昇格した場合、一旦下の接続を切り離し、親を失った２つのピアは同様に障害回復を行います。 障害回復の方法をまとめますと、祖先の情報を持つときは祖先に接続要求を送信し、持たないときはツリーサーバに参加要求を送信することで、配信ツリーの再構築を行います。 障害回復: 祖先の情報があるときは祖先に接続要求 祖先の情報がないときはツリーサーバに参加要求 July 15, 2004 CQ研究会

シミュレーション 評価項目 シミュレーション条件 サーバやピアの負荷 再生開始までの待ち時間 障害回復時間 再生の途切れ時間 拠点数、拠点内サブネット数: 5 1 秒間に平均 30 のピアが一様分布で到着 ある時刻に配信ツリーに参加しているピア数: 平均 2,790 ピア間の転送遅延: 20 （ミリ秒） サーバ・ピア間の転送遅延: 200 （ミリ秒） ファンアウト数: 3 いずれのピアも毎秒 0.004 の確率で離脱 およそ 47% のピアが最後まで動画像を受信 動画像の長さ: 186 （秒） 5つのセグメント （6秒、12秒、24秒、48秒、96秒） 提案機構の性能を評価するため、シミュレーションにより、サーバやピアの負荷、再生開始までの待ち時間、障害回復時間、再生の途切れ時間を評価しました。シミュレーション条件として、まず企業の拠点数、拠点１つあたりのサブネット数をともに５としました。また、１秒間当たりに平均３０のピアが、一様分布で到着するとしました。ある時刻に配信ツリーに参加しているピア数の平均は、２，７９０となります。また、ピア間の転送遅延を２０ミリ秒、サーバ・ピア間の転送遅延を２００ミリ秒とし、どのピアにも共通して毎秒０．００４の確率で障害を発生させました。およそ４７％のピアが最後まで動画像を受信する計算になります。さらに、動画像の長さを１８６秒としました。 得られた結果のうち、いくつかを紹介します。 July 15, 2004 CQ研究会

再生開始までの待ち時間の分布 平均 2.94 秒 最大でも 6 秒未満 累積確率 再生開始までの待ち時間 [sec] まずは、再生開始までの待ち時間の分布を示します。再生開始までの待ち時間とは、クライアントが最初にＳＳにスケジュール決定要求を送信してから、実際に動画像を取得できるまでの待ち時間を表します。横軸が再生開始までの待ち時間を表します。グラフは、横軸が再生開始までの待ち時間を、縦軸が累積確率を表します。平均で２．９４秒、最大でも６秒以下の待ち時間で動画像を取得できています。 平均 2.94 秒 最大でも 6 秒未満 July 15, 2004 CQ研究会

再生の途切れ時間の分布 およそ 0.5 % のピアだけが途切れを経験 最大でも途切れ時間は 1 秒以下 累積確率 再生の途切れ時間 [sec] 次に、再生の途切れ時間の分布を示します。再生の途切れ時間とは、動画像を再生中に障害に会い、障害回復のため動画像の受信が間に合わずに再生が途切れてしまう時間の合計を表します。横軸が再生の途切れ時間を表します。再生の途切れ時間を経験したピアは、全体のおよそ０．５％だけであり、待ち時間は最大でも１秒以下という、非常に小さな値を示しています。十分に耐障害性のある配信を行うことができていると言えます。 およそ 0.5 % のピアだけが途切れを経験 最大でも途切れ時間は 1 秒以下 July 15, 2004 CQ研究会

まとめと今後の課題 動画像ストリーミング配信機構の提案 問題点と今後の課題 セグメント受信スケジュール決定アルゴリズム 配信ツリー構築機構 障害回復機構 提案機構により、再生開始までの待ち時間、 再生の途切れ時間が十分小さい動画像 ストリーミング配信が提供できることを示した 問題点と今後の課題 ツリーサーバに負荷が集中している 冗長な拠点間ツリーが構築されている 物理網上で遠く離れたピアが繋がっている では、本稿のまとめに入ります。本稿では、階層化された組織向けに、３つの機構からなる動画像ストリーミング配信機構を提案しました。シミュレーションによる評価を通して、提案機構により、再生開始までの待ち時間、再生の途切れ時間が十分小さい配信が提供できていることを示しました。 ところが、時間の都合上結果をお見せできませんでしたが、ツリーサーバに負荷が集中していること、また、拠点間の配信ツリーの構築に冗長性が残る、などの問題点が残っています。これらを、今後の研究で解決して行きたいと思います。 July 15, 2004 CQ研究会

ご静聴ありがとうございました。 以上で発表を終わらせていただきます。ご静聴ありがとうございました。 July 15, 2004 CQ研究会