ネットワークとノードの情報を利用したオーバレイネットワークの最適化

Presentation on theme: "ネットワークとノードの情報を利用したオーバレイネットワークの最適化"— Presentation transcript:

1 ネットワークとノードの情報を利用したオーバレイネットワークの最適化
環境情報学部　仲山 昌宏

2 ネットワークやノードの状態に基づいて構成を動的に変更し、オーバレイネットワークの構成を効率化する。
本研究の目的 ネットワークやノードの状態に基づいて構成を動的に変更し、オーバレイネットワークの構成を効率化する。 複数の中経者を介在した通信において パフォーマンスの低下を低減させる。 絵を描く。 同じネットワークのノードが海向こうのノード経由でつながっている。 2003/02/01 2002年度卒論最終発表会

3 研究の背景 匿名の必要性 匿名サービスの普及 匿名にしたい理由 匿名掲示板、エスクローサービス 悪意を持つ人から自分の情報を守る
ネットワーク上での行為と実世界の個人を隔離 2003/02/01 2002年度卒論最終発表会

4 研究の背景 オーバレイネットワークによる匿名通信路
サーバを利用する匿名サービスの限界 利用者の情報が集中 転送量の増大 オーバレイネットワークによる匿名の提供 直接通信をせず、第三者が中継転送を行う。 ネットワーク上で個人の識別子となりえる IPアドレスを隠匿することができる。 2003/02/01 2002年度卒論最終発表会

5 研究の背景 オーバレイネットワークによる匿名通信路
データの転送に中継を利用する。 B A 2003/02/01 2002年度卒論最終発表会

6 研究の背景 匿名通信路の特徴と問題点 実時間性の高い通信を対象としている。
チャット(数秒) 掲示板(数分) 直接通信を行う場合と比べ、中継を行うノードやそこに至るネットワークの影響を受けやすい 2003/02/01 2002年度卒論最終発表会

7 関連研究 Gnutella Winny P2Pストリーミング Ultrapeerによる二段階の階層化 測定による接続先ノード選択
帯域幅による階層化 キーワードによるクラスタ化 P2Pストリーミング 配信ツリーの動的構成 2003/02/01 2002年度卒論最終発表会

8 関連研究の比較 転送 ノード ネットワーク Ultrapeer 直接 階層化 - 測定による接続先選択 稼働時間 ホップ数 Winny
中継転送 帯域幅 キーワード P2P ストリーミング 2003/02/01 2002年度卒論最終発表会

9 目的 オーバレイネットワークのトポロジの効率化 「ノード間のリンク」を対象 情報の検索は対象外 キャッシングやメッセージの経路制御は対象外
最終的に、近いノード同士でクラスタを構成することを目指す。 2003/02/01 2002年度卒論最終発表会

10 手法 ノードやIPネットワークの状況に応じてオーバレイネットワークのトポロジを最適化 帯域幅 処理性能 稼働時間 Hop数 RTT
実効帯域幅 2003/02/01 2002年度卒論最終発表会

11 システムの概要 ノード情報の交換と測定によってリンクを変化させる。 C ：IP Network D ：Link B ：NodeAdv
：Measurement 2003/02/01 2002年度卒論最終発表会

12 設計 動作概要 新しく接続したノードAはノード広告メッセージをオーバレイネットワーク上に送出する。
ノード広告メッセージを受信したノードBはノードAに対し測定を行う。 ノード広告メッセージに含まれるノード情報と測定結果から優先度を算出 既存のリンクよりも優先度が高ければ接続 2003/02/01 2002年度卒論最終発表会

13 設計 初期状態(接続直後) C the Internet A D B 2003/02/01 2002年度卒論最終発表会

14 設計 1. ノード広告メッセージ送出 C NodeAdv MSG ノード情報 the Internet A D B 2003/02/01
2002年度卒論最終発表会

15 設計 2. 測定 測定！ C the Internet A D 測定結果 B Hops: 3hop 2003/02/01
2002年度卒論最終発表会

16 設計 3. 優先度を算出 C the Internet A D Node: A 優先度: ～～ B 2003/02/01
2002年度卒論最終発表会

17 設計 4. 優先度が高ければ接続 C the Internet A D B 2003/02/01 2002年度卒論最終発表会

18 設計 最適化の例 C the Internet A D B 2003/02/01 2002年度卒論最終発表会

19 実装 手法を評価するためのプロトタイプを実装 Unix環境で動作 オーバレイネットワークの構築 ノード広告メッセージの送出
ネットワーク状態の測定 リンクの動的変更 Unix環境で動作 FreeBSD(4.7)、NetBSD(1.6)、Linux(Vine-2.1.5) 2003/02/01 2002年度卒論最終発表会

20 システム構成 Application Message Procedure Link Measurement Manager
Link Buffer Node Buffer Control Msg Result Link Manager Measurement Module(s) Other Node(s) Target Node 2003/02/01 2002年度卒論最終発表会

21 運用実験の概要 実環境上で実験を行い、効率化が機能することを確かめた。 RGNet上のホスト 自宅のホスト(128kbps)
ec.sfc.wide.ad.jp jam.sfc.wide.ad.jp 自宅のホスト(128kbps) omoikane.uryusoft.net WIDE Network上のホスト sh.wide.ad.jp 2003/02/01 2002年度卒論最終発表会

22 自宅 WIDE藤沢 RG-Net omoikane the Internet jam sh ec 2003/02/01
2002年度卒論最終発表会

23 運用実験の結果 オーバレイネットワークが、IPネットワークのトポロジに近づくように効率化された。 実装を進める上でいくつかの問題が浮上した。
ノード情報がうまく反映されるかは、より大規模な実験が必要。 2003/02/01 2002年度卒論最終発表会

24 定性評価 転送 ノード ネットワーク Ultrapeer 直接 階層化 - 測定による接続先選択 稼働時間 ホップ数 Winny 中継転送
帯域幅 キーワード P2P ストリーミング 本システム 処理性能 2003/02/01 2002年度卒論最終発表会

25 今後の課題 実装中に明らかになった問題の解決 匿名通信路に利用するためのライブラリ化 ノード広告メッセージのルーティング
ノード広告のタイミング より良い測定手法の確立 匿名通信路に利用するためのライブラリ化 2003/02/01 2002年度卒論最終発表会

26 おわり ご静聴ありがとうございました。 2003/02/01 2002年度卒論最終発表会

27 おまけ：その他スライド

28 研究の概要 匿名通信路の実現に必要な、効率化されたオーバレイネットワークが必要である。
ノードやIPネットワークの情報を利用してオーバレイネットワークを動的に組み替える機構を提案する。 この機構が有効であることを示すプロトタイプを実装し評価を行った。 2003/02/01 2002年度卒論最終発表会

29 修士研究計画 「仮想ネットワーク上で匿名性と相手の特定を両立するシステムの構築」
匿名性を保ったまま特定の相手との間に暗号通信路を提供するシステム 匿名性を提供するために、オーバレイネットワーク上の中間ノードが通信の中継を行う。 2003/02/01 2002年度卒論最終発表会

30 修士研究計画 中継者による匿名性の実現[往路]
! B Src: A [ ] Dst: ? Mes: Search Query Src: A [ ] Dst: ? Mes: Search Query C D Src: A [ ] Dst: ? Mes: Search Query A 2003/02/01 2002年度卒論最終発表会

31 修士研究計画 中継者による匿名性の実現[復路]
B Src: B [ ] Dst: A [ ] Mes: Response Src: B [ ] Dst: A [ ] Mes: Response C D Src: B [ ] Dst: A [ ] Mes: Response A 2003/02/01 2002年度卒論最終発表会

32 中継者が遠い場合 C the Internet A D B 2003/02/01 2002年度卒論最終発表会

33 中継者の持つ帯域が 細い場合 the Internet A C B D 2003/02/01 2002年度卒論最終発表会

34 中継者が 高負荷の場合 the Internet A C B D 2003/02/01 2002年度卒論最終発表会

35 最適化された状態 the Internet A D C B 2003/02/01 2002年度卒論最終発表会

36 運用実験 優先度の計算式として以下を設定 優先度 = -8 × ホップ数 ＋ log10 (帯域幅) ＋ 負荷( load )
優先度 = -8 × ホップ数 ＋ log10 (帯域幅) ＋ 負荷( load ) 2003/02/01 2002年度卒論最終発表会

37 設計 IPマルチキャストによるノード探索 ノード探索メッセージを、IPマルチキャストで特定のマルチキャストアドレスにTTL=1で投げる。
ノード発見メッセージが帰ってきたらそのノードに接続する。 時間内に帰ってこなければTTLを徐々に増やして再びノード探索メッセージを投げる。 2003/02/01 2002年度卒論最終発表会

38 アプリケーションの分類 ICQ, MSNメッセンジャー Groove ShareCast, PeerCast Napster/WinMX
動的なデータ ICQ, MSNメッセンジャー Groove ShareCast, PeerCast Napster/WinMX Gnutella Winny Freenet　 間接（中継） 直接 静的なデータ 2003/02/01 2002年度卒論最終発表会

39 設計 6. 最終目標 2003/02/01 2002年度卒論最終発表会

40 研究の背景 クライアント・サーバの限界 利用者の情報が集中 転送量の増大 格好の攻撃対象 運営の不備による漏洩 利用者数の増加
一人あたりの帯域幅の増加 2003/02/01 2002年度卒論最終発表会

41 研究の背景 オーバレイネットワークの登場 IPネットワークの上にTCP等を利用して構築されたアプリケーションによるネットワーク
ファイル共有: Napster/WinMX, gnutella 匿名ファイル共有: Freenet, Winny ストリーミング: ShareCast, PeerCast グループウェア: Groove 2003/02/01 2002年度卒論最終発表会

42 評価 定性的評価 定量的評価 IPネットワークのトポロジに近いネットワークを構成できているかどうか
ノードが増減した場合にネットワーク構成の最適化に要する時間 ノード広告メッセージの転送とホップ数測定に要するトラフィック 繋ぎ変える機構を採用しない場合とのホップ数やスループットの差異 2003/02/01 2002年度卒論最終発表会

43 関連研究1 Gnutella Ultra P2Pサービスにおける物理ネットワークを考慮した論理トポロジー構築手法 gnutellaを利用
Hop数と生存時間から最適なノードを選択 帯域幅等のノードの情報を無視している。 2003/02/01 2002年度卒論最終発表会

44 関連研究2 Winny 匿名性を実現するファイル共有アプリケーション
自己申告した帯域幅によるツリー状の階層化と、指定したキーワードのマッチングによるクラスタリングを併用 IPネットワークのトポロジを無視しているため偶然に大きく左右される。 2003/02/01 2002年度卒論最終発表会