P2P サービスにおける 物理ネットワークを考慮した 論理トポロジー設計手法

Presentation on theme: "P2P サービスにおける 物理ネットワークを考慮した 論理トポロジー設計手法"— Presentation transcript:

1 P2P サービスにおける 物理ネットワークを考慮した 論理トポロジー設計手法
後藤 嘉宏 大阪大学　大学院基礎工学研究科 情報数理系専攻　博士前期課程　 大阪大学　大学院基礎工学研究科の後藤と申します。 本日は「P2P サービスにおける物理ネットワークを考慮した論理トポロジー構築手法」 と題して発表させていただきます。 2002/2/8 MVE/CQ/NIM 研究会

2 研究の背景 P2P サービス Napster, Gnutella, Freenet など サービス提供に特定の端末を必要としない
各端末 (ピア) で論理ネットワークを構成し、資源を共有 発展段階にあり通信品質が十分でない 物理ネットワークの特性を考慮していない まず、研究の背景について説明いたします。 近年、インターネットにおける新たな通信モデルとして、ピア・ツー・ピアモデルを用いた サービスが注目されており、例えば Napster,Gnutella,Freeenet などの P2P ファイル共有 アプリケーションが実際に利用されています。 P2P では、従来主流であったサーバ・クライアントモデルと異なり、 サーバのような特定の端末を設定せずに ピアと呼ばれる端末間の協調によって論理ネットワークを構成し、 サービスを実現します。 そのため、すべての資源は各ピアに分散され、 サーバ・クライアント方式で問題とされる、特定のサーバあるいはネッ トワークへの負荷集中がおこりにくくなります。 しかしながら、 P2P モデルはまだ発展段階にあり、その通信品質は十分とは言えません。 その原因の一つとして、構成される論理ネットワークが下層にあたる物理ネットワークの 特性を考慮していないことが挙げられます。 MVE/CQ/NIM 研究会 2002/2/8

3 P2Pサービス Gnutella を対象 Gnutella におけるファイル取得 ソースコードが広く公開 改変が容易 論理ネットワークに参加
ファイル問い合わせのためのメッセージ送信 目的ピアに接続しファイルを取得 そこで、本研究ではP2P サービスの一つとして、ソースコードが公開されている クライアントソフトが存在し、改変が容易であるGnutellaを例に取り、その論理 ネットワークについて考えることにします。 まず、Gnutellaにおけるファイル取得の流れを紹介致します。 大まかに言うと、 ファイル取得を行いたい端末は、まずファイル検索ののために、 gnutella 論理ネットワークに参加します。次に、取得したい ファイルがどのピアに存在するかを、問い合わせメッセージを用いて調べます。 そして、問い合わせに対する回答メッセージをもとに、 目的のピアに対して直接接続し、ファイルを取得します。 以降で、それぞれの手順の詳しい方法について説明します。 MVE/CQ/NIM 研究会 2002/2/8

4 論理ネットワークへの参加 ネットワーク上へのピアへ接続 接続ピアの障害に備え複数ピアへ接続 Gnutella 論理ネットワーク
これは既に論理ネットワーク上にあるピアに接続することで行います。 また、接続しているピアがダウンした場合に論理ネットワークから 切り離されてしまうことがないように、通常複数のピアへの接続を保ちます。 MVE/CQ/NIM 研究会 2002/2/8

5 ファイル名をキーとするクエリ（問い合わせ）メッセージを接続ピアに送信 各ピアは送られてきたクエリメッセージを隣接ピアに転送
問い合わせメッセージの送信 ファイル名をキーとするクエリ（問い合わせ）メッセージを接続ピアに送信 各ピアは送られてきたクエリメッセージを隣接ピアに転送 Gnutella 論理ネットワーク 論理ネットワークに参加できると、探しているファイル名を持たせたクエリメッセージを 接続ピアに送信します。 各ピアは送られてきたメッセージを転送し、結果クエリメッセージはネットワーク 上に広がっていきます。 MVE/CQ/NIM 研究会 2002/2/8

6 目的ピアへの接続とファイル取得 クエリメッセージを受信したピアに該当ファイルが存在すれば、返答メッセージを送信
受信した応答メッセージの送信ピアに対して接続し、ファイルを取得 複数のピアからの応答メッセージが到着した場合 ピア（ユーザ）が判断し、接続ピアを決定 Gnutella 論理ネットワーク クエリメッセージを受信したピアは、該当するファイルを持っていた場合返答メッセージを 送信元ピアに送ります。 検索を行っているピアは返答メッセージの情報を元に目的ファイルを持つピアに データ転送用の接続をし、そこからファイルを取得します。 このとき、複数のピアから応答メッセージが得られた場合はユーザがファイル取得先を決定します。 MVE/CQ/NIM 研究会 2002/2/8

7 通信品質を考慮した P2P サービス 通信品質を向上させるための改善点 論理ネットワークに参加 ファイルの問い合わせ
より広い到達範囲 ファイルの問い合わせ より安定した論理ネットワークの接続性 ピアへの接続とファイル取得 高速なファイル転送と安定した通信 以上のような操作において、各段階で次のような通信品質が考えられます。 論理ネットワークに参加する段ではその状態でメッセージを送った ときの到達範囲があげられます。 ファイルの問い合わせ時には応答メッセージがきちんとルーティング されるために論理ネットワークが安定している必要があります。 また、ファイル転送のためのピア接続をおこなう時には その転送が高速かつ安定して行えることが求められます。 MVE/CQ/NIM 研究会 2002/2/8

8 研究の目的 物理ネットワーク特性を考慮した論理ネットワーク 構築手法 トラヒック計測に基づく論理ネットワーク特性の分析 ネットワーク参加時
接続ピア数と選択方法 クエリ送出時 メッセージ到達範囲 メッセージトラヒックによる影響 ファイル取得時 ピア選択方法 本研究では物理ネットワークの特性を考慮した論理ネットワークを構築する手法を確立することを 目的とします。 そのために、 まず、ネットワークへの参加時に何カ所のピアへ接続するか、また、接続先はどうやって選択するか。 次に、クエリの送出時にはそのメッセージをどのくらいの範囲に届ければよいか、 そのためのパラメータに応じたトラヒックの影響はどのようなものか、 最後にファイルの取得を行う際に、その相手となるピアをどうやって選択するか、 を考えます。 また、ネットワーク構築の際に利用できる情報として、トラヒック計測により 論理ネットワークの特性を分析します。 トラヒック計測に基づく論理ネットワーク特性の分析 MVE/CQ/NIM 研究会 2002/2/8

9 メッセージの到達範囲 TTL (Time To Live) 同時接続数 特性に応じて適切に設定する必要
メッセージ送信時に設定、転送毎に1減少 接続ピアとのホップ数が TTL 以内のピアと通信可能 同時接続数 特性に応じて適切に設定する必要 ネットワーク特性の分析により適切なパラメータ導出 TTL, 同時接続数 を増加させることで拡大 必要以上に大きくするとトラヒック量増大、ネットワーク負荷増 まず、送信したメッセージの到達範囲について考えます。 メッセージの到達範囲を規定するパラメータとして送信メッセージに設定するTTLがあります。 これはメッセージの転送毎に1減少される値であり、そのメッセージが何ホップ先まで 送られるかを指示するものです。 また、ネットワーク参加についての説明時に述べた同時接続数によってもメッセージの 到達範囲が変化します。 これらのパラメータを増やすことでメッセージの到達範囲を拡大することが出来ます。 メッセージ到達範囲の拡大により例えば検索でのファイル発見率が高くなることが 期待できますが、必要以上に大きくすると論理ネットワーク上のトラヒック量が増え ネットワーク全体に対する負荷も増大します。 そこで、本研究ではネットワーク特性を分析し、適切なパラメータを導出する方法を検討します。 MVE/CQ/NIM 研究会 2002/2/8

10 TTL による効果 TTL増加に従って到達可能ピア数は増える TTL t での到達可能ピア数を r(t) とする TTL と到達ピア数の関係
このグラフはgnutellaの論理ネットワークを流れるメッセージの 観測によって得られた、TTL と到達可能ピア数の関係です。 図の横軸は、TTL を示し、縦軸は到達可能ピア数を示しています。 これよりメッセージが到達するピアの数は TTL の増加にしたがって大きくなる t の関数であるとと考えることができます。 以降ではこれを r(t) と表します。 MVE/CQ/NIM 研究会 2002/2/8

11 同時接続ピア数による影響 接続数を増やせば到達可能範囲が拡大 到達可能範囲の重複により効果は減少 到達範囲の重複度分布
次に、同時接続数と到達範囲の関係を見ることにします。 あるピアに接続することで、そこからTTLによって定められる範囲内にあるピアに メッセージが届くため同時接続数を増やせば、その分到達可能範囲は拡大すると考えられます。 しかし一方、接続数を増やすことで到達範囲がより重複し、同時接続数を増やす ことの効果は徐々に小さくなるとも考えられます。 このグラフは論理ネットワーク上でランダムに2つ選んだピアに接続し、 TTL10でPing メッセージを送信した場合に、両方のサブネットから返答があったピアの割合の 分布を表しています。 横軸が重複度、縦軸がその累積密度になっています。 このグラフのとき、重複度の平均は約5%になっています。 MVE/CQ/NIM 研究会 2002/2/8

12 TTL と重複部分の関係 TTL が小さいうちは重複度も小。TTL に従って大きくなる TTL t での重複度を v(t) とする
MVE/CQ/NIM 研究会 2002/2/8

13 TTL と接続ピア数による 到達範囲の導出 r(t), v(t)、同時接続数 k より到達可能範囲を導出 MVE/CQ/NIM 研究会
以上のように TTL t での到達可能ピア数 r(t)、重複度 v(t)、同時接続数 kとすると、 TTL t,同時接続数 kにおける到達可能範囲 S はこのような式で表すことができます。 式の詳細は時間の都合上省略させていただきます。詳しくは予稿集をご覧ください。 MVE/CQ/NIM 研究会 2002/2/8

14 到達範囲数値例 同時接続数k の増え方に対し、到達可能ピア数 S の増え方は徐々に小さくなる
S に閾値を定め、適切な k を求めることが可能 同時接続数と到達範囲の関係 グラフは、式から導かれる数値例として TTL 10, 到達可能ピア数1200, 重複率5% のときの 同時接続数kと到達可能ピア数Sの関係を示したもので、横軸が同時接続数, 縦軸が到達可能ピア数にあたります。 これより、同時接続の増加に対して到達範囲の増分は徐々に小さくなっていくことが分かります。 このことから、例えば到達範囲に閾値を設定し、 それをもとに適当な同時接続数の値を決定することが考えられます。 MVE/CQ/NIM 研究会 2002/2/8

15 メッセージトラヒックによる影響 到達範囲が拡大する一方で、メッセージトラヒックは増大
パラメータ設定にはメッセージトラヒックの影響も考慮すべき Gnutellaのメッセージ Ping,Pong,Query,Query Hit,Push プロトコルの転送仕様からパラメータとメッセージ量の関係を考察 これまでに述べましたように、メッセージの到達範囲は TTL や同時接続数を 増やすことで拡大することができますが、 その一方でメッセージトラヒックが増大することが考えられます。 そこで、ここではGnutellaの5種類のメッセージ、ネットワーク上のピア発見に用いるPing, Pong, 検索に用いるQuery, Query Hit, ファイルのパッシブ受信に用いるPushについて プロトコル上の転送仕様からパラメータとそれに応じたメッセージの関係を考え、 各パラメータによるメッセージトラヒック量の影響について考えます。 MVE/CQ/NIM 研究会 2002/2/8

16 メッセージトラヒックによる影響 (Ping/Query)
ピアに対する問い合わせメッセージ T(k) : TTL=7 のときのメッセージ到達範囲 Ping, Queryは論理ネットワーク上のピアに対して問い合わせを行うメッセージです。 受信メッセージの数は自身のピアに対してメッセージを届けられるピア数、すなわち一般に よく使われるTTL 7でメッセージを送った際のメッセージ到達範囲T(k)に従います。 これらはブロードキャストされるメッセージであることから、 送信メッセージの数は同時接続数に比例していることが分かります。 受信メッセージ T(k) 送信メッセージ　kT(k) MVE/CQ/NIM 研究会 2002/2/8

17 メッセージトラヒックによる影響 (Pong/Query Hit)
Ping,Queryに対する返答 Pong,Query HITは論理ネットワーク上のピアに対して返答を行うメッセージです。 いずれも受信メッセージの数は同様に自ピアに対してメッセージを届けられるピア数、 メッセージ到達範囲T(k)に従います。 しかしながら、Query Hitを返すのは検索キーに該当するファイルを持っている場合 に限られるので、メッセージ数はPingより少なくなっています。 これらは対応するping/queryの送信元のみに返されるメッセージなので、 送信メッセージの数は受信メッセージとほぼ同じになります。 受信メッセージ T(k) 送信メッセージ　T(k) MVE/CQ/NIM 研究会 2002/2/8

18 メッセージトラヒックによる影響 (Push)
ファイル要求時に提供ピアがファイアウォール内にあるという状況のみに用いられメッセージの絶対量が少ない 受信メッセージ 送信メッセージ 最後にPushですが、グラフの結果より、ほとんど観測されていないことが分かります。 これはPushがファイアウォールを介した場合のファイル取得の際にのみ使用される メッセージであり、通常ほとんど発生しないためであると考えられます。 MVE/CQ/NIM 研究会 2002/2/8

19 メッセージトラヒックの影響を考慮した パラメータ設定
t, k を大きくすることでメッセージ到達範囲は広くなるが、メッセージによる負荷が増大 メッセージトラヒックが利用する上限帯域を決定し、上限内で到達範囲が広くなる t, k を決定 以上のとおり、t,kを大きくすることでメッセージ到達範囲を広くできますが、 その分メッセージによる負荷が増大することになります。 したがって、これより、メッセージトラヒックにどれだけの帯域を利用させるかという 上限を設定しその範囲内で到達範囲が最大になるt,kを決定するというパラメータ設定法 が考えられます。 MVE/CQ/NIM 研究会 2002/2/8

20 物理ネットワークの特性を考慮することで安定した接続を維持
ネットワーク特性を考慮した ピア接続手法 論理ネットワーク構成のためのピア接続 物理ネットワークの特性を考慮することで安定した接続を維持 メトリック ホップ数 共有リンク数 存在時間 帯域 RTT 次に論理ネットワーク構成のためのピア接続を考えることにします。 ここでは物理ネットワークの特性に応じて接続先ピアを選択をすることで、 構成される論理ネットワークの構造を物理ネットワークを考慮したものに変えることを目指します。 このとき考慮するメトリックとして、 ホップ数や、共有リンク数、存在時間、帯域、RTTなどが考えられます。 この詳細について次に説明します。 MVE/CQ/NIM 研究会 2002/2/8

21 接続ピア選択時に 考慮するメトリック(1) ホップ数 共有リンク数 論理ネットワーク上での存在時間 リンク障害の影響を抑えることが期待できる
ネットワークの性能予測には精度が不十分 共有リンク数 リンク障害発生時のピアへの影響を軽減 測定のための計算コストがやや大きい 論理ネットワーク上での存在時間 ネットワークの安定が期待できる 定期的な観測が必要で、定常的な負荷が発生 まず、ホップ数です。 ホップ数を小さくすることで物理ネットワーク上での経由地点が減り、 それだけ障害の影響を受けにくくなります。 しかし、１ホップの意味は物理ネットワーク上でも場所により大きく異なり、 性能予測に用いるには精度が不十分であるということが考えられます。 次に共有リンク数です 共有リンクをなるべく避けることで、障害の発生時に同時に失われる接続数を 小さく抑える効果があります。しかし、その評価にはホップ数などと比較し 大きい計算コストが必要となります。 また、論理ネットワーク上での存在時間も考えられます。 これは、論理ネットワーク上に長い間存在しているピアはこの先も存在続ける 可能性が高いことを期待したものです。これにより比較的安定した接続が期待できますが、 メトリック調査のため定期的なネットワークの観測を続ける必要があります。 MVE/CQ/NIM 研究会 2002/2/8

22 接続ピア選択時に 考慮するメトリック(2) 帯域 RTT (Round Trip Time) 直接的な指標
ここで挙げた他のメトリックに対して計測のためのトラヒック消費量が大きい RTT (Round Trip Time) Pingなどで容易に直接計測可能 変動が大きく誤差が生じやすい 次に帯域が考えられます。 これは目的に対してより直接的な指標ですが、計測のためのトラフィックが 他のメトリックと比べて大きくなる傾向にあります そして、RTT ですが これはpingなどを用いることで容易に直接計測できます。 しかしながらその値には変動が大きく、誤差が生じやすいため、 RTT を精度よく計測するための仕組みが必要となる問題があります。 MVE/CQ/NIM 研究会 2002/2/8

23 ホップ数を考慮したピア選択手法 ピアに到着する pong メッセージから、論理ネットワーク上の他のピア情報を記録
記録されたピア集合から再接続先のピアを決定 このときホップ数が最小のものを選択 記録するピア数を変化させる 0 : 従来と同様ランダムにピア選択 記録ピア数が 4, 6, 8 の場合を評価 まず、ホップ数についてメトリックの組み込み方とその効果について調べます。 一般にgnutellaクライアントは現在の接続先のダウン等に備え再接続のためのピア情報を Pongメッセージから得て記録しています。再接続の際にはこのピア情報を元に新たな接続を 行うことになりますが、この際に複数あるピア情報のうちホップ数が最小のものを選択 するよう変更します。 比較のための従来通りのランダム選択と、メトリック考慮選択が用いる記録の数 4, 6, 8の3通り、計4通りの条件で行いました。 MVE/CQ/NIM 研究会 2002/2/8

24 ホップ数を考慮したピア選択手法 - シミュレーション結果 -
500ピアのデータを用いたシミュレーションで評価 ピア選択手法の変更により、ランダムの場合と比べてホップ数が小さい傾向になるよう影響を与えられている ピア選択手法と平均ホップ数の関係 評価は500ピアのデータを用いたシミュレーションで行いました。 hグラフの縦軸は平均ホップ数の90%範囲を示しており、横軸は左から順にランダム、 メトリック考慮候補数4,6,8となっています。 グラフの結果より、ピア選択時にホップ数を考慮することによって平均ホップ数が軽減し、 リンク障害がおこる可能性を下げることができるとがわかります。 MVE/CQ/NIM 研究会 2002/2/8

25 存在時間に基づくピア選択手法 論理ネットワーク上における存在時間が長いピアを選択
存在時間が長いピアはその先も存在している可能性が高く、安定した接続が期待できる　　　 ピア間接続持続時間分布 多くは短時間で接続が失われる 残りの一部は長時間の接続が保たれる 次に、存在時間に基づくピア選択の効果について調べます。 グラフは横軸のピア間接続持続時間に対して縦軸にその累積密度分布を取ったものです。 これより、多くの接続は短時間で失われている反面、一部は長時間持続していることが分かります。 したがって、存在時間の長いピアに対して優先的に接続することで、 接続が長時間保てる安定したネットワーク となることが期待できます。 MVE/CQ/NIM 研究会 2002/2/8

26 存在時間に基づくピア選択手法 キャッシュ上の各ピアについて、pongメッセージにより存在を確認して存在期間を記録
再接続時に確認されている存在期間が最長のものを選択 存在時間にもとづくピア選択により、ピアに対する接続性が向上 平均接続時間の増大 再接続回数の減少 ここでは再接続に備えて記録しているピア情報それぞれについて メッセージにより存在が確認されるたびに確認存在時間を更新し、 再接続の際にはその期間が最長のものを選択するように変更を加えました。 約半日の実測による結果はこの表の通りです。 平均接続持続時間は長く、再接続回数は少なくという方向に変化しており、 メトリック考慮の影響が測定結果にも現れていることが見て取れます。 ランダム 長時間存在ピア選択 平均時間 (秒) 430 487 再接続回数 (回) 483 385 MVE/CQ/NIM 研究会 2002/2/8

27 まとめと今後の課題 まとめ 今後の課題 論理ネットワーク構築におけるパラメータ特性を調べ、導出法を提案した
物理メトリックを考慮したピア選択手法を提案した 物理ホップ数とピアの存在時間を例に有効性を検証 今後の課題 TTL t と r(t) の関係 パラメータと検索能力の関係から適切なパラメータ設定法を導く ファイル取得時のメトリックを考慮したピア選択 最後に、まとめと今後の課題を述べさせていただきます 今回の発表では まずP2P論理ネットワークに置けるパラメータの特性を調べ、その導出法を提案しました。 また、論理ネットワークに物理ネットワークの特性を導入する手段として、 物理メトリックを考慮したピア選択手法を提案し、その効果を確かめました。 今後の課題としましては、 TTLと到達可能領域に関するさらなる調査、 パラメータと検索能力の関係調査、 検索後のファイル取得段へのメトリック導入 などを考えています。 以上で発表を終わらせていただきます。 ご静聴ありがとうございました。 MVE/CQ/NIM 研究会 2002/2/8