自律分散協調システム論 第13回「Peer-to-peer systems」

Presentation on theme: "自律分散協調システム論 第13回「Peer-to-peer systems」"— Presentation transcript:

1 自律分散協調システム論 第13回「Peer-to-peer systems」
中村　修

2 今日の概要 P2P P2Pモデルとクライアントサーバモデル P2Pのアプリケーション

3 クライアントサーバモデルと P2Pモデル

4 Winny悪用による逮捕者とそのインパクト
2003年11月27日に逮捕者がでた段階で日本中のトラフィックは2割減少した

5 Winnyの悪用者が逮捕・製作者宅捜索

6 ポート番号からサービス 特定がしにくい時代
P2Pのインパクト – trafficの推移 出典: WIDE報告書( ) はdaily sampling ポート番号からサービス 特定がしにくい時代 P2P登場 WWW全盛

7 クライアントサーバモデル インターネット上の通信の基本モデル 2種類のコンピュータ サーバ : サービスを提供するコンピュータ
クライアント : サービスを受けるコンピュータ クライアント サーバ あるポート番号でクライアントからの要求を常に 待ち受けているプログラム 必要なときにサーバプログラムと通信して要求を送るプログラム データだよ クライアント サーバプログラム データちょうだい クライアントプログラム

8 クライアントサーバはSingle Point of Failure
ボトルネック サーバの計算能力 ネットワーク帯域 ボトルネック解消のアプローチ ロードバランサの利用 キャッシュ/CDNの利用 P2Pモデルの導入 アクセスの集中による 回線の飽和 Server サーバのダウン Clients

9 例(1/4) : IRCの負荷分散方法 IRC(Internet Relay Chat) 一つサーバに処理が集中しない RFC1459
Client 1 Server 1 Server 2 Hi! グループに1,2,3が 加わってる場合 Server 4 Hi! Client 2 Server 3 Hi! Server 4にはグループに加 わったクライアントがない ためメッセージはこない Client 4 Client 3

10 例(2/4) : ロードバランシング 同じIPアドレスで複数のサーバが反応
ラウンドロビン、URLで、重み付け、負荷、コネクション数、反応速度などで割り振る 利点 CPU負荷を軽減できる 問題点 ログが分割される メンテナンス負荷は高くなる コネクション要求 負荷分散装置

11 例(3/4) : DNSを利用した負荷分 同じ名前で複数のサーバが登録されている 物理的に別の場所で処理 www.asahi.comなど
利点 回線資源を 分散利用できる 問題点 均等に負荷が 分散されない 落ちている サーバにも振る Cacheがあるため タイムラグがある Client 1 Client 2 Wwwld2.asahi.com Uunet3.asahi.com だよ だよ

12 例(4/4） : キャッシュを利用した負荷分散 Accelia Durasite ファイルを広域に分散しネットワーク負荷を分散 Akamai クライアントに一番近い、最 適なキャッシュを探す サーバのかわりにキャッシュ がクライアントに応答 利点 CPU資源の分散 回線資源の分散 Clients Server キャッシュを拠点に置き アクセスを分散させる コンテンツの配置 Cache Servers

13 P2Pとは？ Peer-To-Peer 特徴 Peerとは端末ノードのこと(中継ノードではない)
代表的なアプリケーション ファイル共有・交換・配信型 Napster コラボレーション型 Groove 分散コンピューティング型 特徴 耐故障性の実現 資源分散が可能 自由なランデブー

14 コミュニケーションとは？ コミュニケーションには主体がある。 P2Pではこれらは対等のものとしてpeerと呼ぶ。
誰かとコミュニケーションをとるためには、まずその主体同士が、 相手を発見・識別する コミュニケーションを開始する コミュニケーションを終了する ……という手順が必要になる 相手の発見と識別 コミュニケーションの開始 コミュニケーションの終了

15 クライアントサーバ、P2Pモデルの比較 クライアントサーバ ハイブリッドP2P ピュアP2P ランデブーも通信も中心で行う
: Server 中心 : Server ピア ピア ピア ランデブーも通信も中心で行う ランデブーを中心で行い、通信をピア同士で行う ランデブーも通信もピア同士で行う WWWなどのインターネット上の大部分のアプリケーション Napster MSN Messengerなどの主要IM Gnutella ,Freenet, Winny

16 身近なＰ２Ｐアプリケーション ファイル共有 ストリーミング インスタントメッセンジャー Napster Gnutella Morpheus
WinMX Winny Share GNUnet ストリーミング PeerCast Joost (Skype) インスタントメッセンジャー MSNメッセンジャー ICQ、Jabber 3degrees、Skype Groove、Ariel AirOne 資源分散 OceanStore HyperBee ネットワークゲーム Diablo Age of Empire

17 P2Pを考察する際のメトリック 性能 匿名性 可用性 堅牢性 Open性

18 WWW、FTP Napster、WinMX Gnutella Winny
ファイル共有の変遷 WWW、FTP Napster、WinMX Gnutella Winny

19 ファイル共有: P2Pモデルの代名詞 ファイル共有アプリケーション 自律的なコミュニケーションとしてどう実現するか
ファイルの公開・検索・転送を実現する WWWとの比較(登場人物と役割は？) 公開：WWWサーバへのアップロード 検索：検索エンジン 転送：ブラウザによるページの取得 自律的なコミュニケーションとしてどう実現するか オリジナル・ファイルは各Peerが分散して保有 ネットワーク上に分散したファイルからの検索 ファイルの転送 中継転送、キャッシュの利用 直接転送

20 ファイル共有 以前はWWWやFTPを利用 WWWやFTPサーバ上にファイルの複製を送信 HTTP/FTPによってファイルを取得
検索は外部の検索エンジンやサーバ内で実現 サーバはディスクを潤沢に必要とした。 WWW/FTPサーバ ファイルを取得 ファイルの複製を送信

21 P2Pシステムの台頭 第1世代P2Pファイル共有システム 第2世代P2Pファイル共有システム 第3世代P2Pファイル共有システム
ファイルの転送はノード間 ノード情報は中央管理サーバが持つ Ex. Napster, WinMX 第2世代P2Pファイル共有システム 特定のサーバを必要としない Ex. Gnutella 第3世代P2Pファイル共有システム さらにキャッシュ機能を有する Ex. Winny

22 Napster インデックスサーバの利用 所持ファイルの一覧をサーバに送信 検索条件をサーバに送り、結果をもらう。
公開されているファイルをサーバが制御できる。 インデックスサーバ ファイルの検索 自分の持つファイルを登録 ファイルを取得

23 Napsterの問題 インデックス・サーバの運営者が責任を持つ 中央集権的なサーバ無しでやるにはどうすればいい？
→　サービス停止 現在は著作権者と提携し、Napster2へ…… 中央集権的なサーバ無しでやるにはどうすればいい？ Napsterは ハイブリッドP2P 中心にインデクッス・ サーバが存在 ピア インデックスサーバに障害が発生すると、システム全体が停止する

24 あのファイルが欲しい… 皆に聞いてみよう！
Gnutella 自律的に参加するPeerの集合体 インデックス・サーバに依存しない P2Pネットワーク上で検索要求を転送(TTLは最大7) 検索者が積極的にファイルを探しに行く ファイルの所持者は受動的 持ってないよ！ 持ってないよ！ 持ってないよ！ 持ってないよ！ 持ってないよ！ 持ってないよ！ Aさん Bさん もってるよ！ 送るね！ あのファイルが欲しい… 皆に聞いてみよう！

25 Winny ピュアP2P 堅牢性の実現 高い匿名性 Winnyを悪用した犯罪行為が多発 インデクッス・サーバに依存せず 知的所有権を侵害
中継したキャッシュを再公開 高い匿名性 間接的な接続により、取得者には公開元が不明 暗号化により、中継者には通信内容が不明 Winnyを悪用した犯罪行為が多発 知的所有権を侵害 摘発されにくかったが…

26 Winny: ネットワーク ノードの持つネットワーク速度（自己申告）に応じて階層化 より高速 より低速

27 P2Pの鶏と卵問題 何も知らないピアがP2Pネットワークに参加する 1つでもP2Pネットワークのノードを知らないと参加できない
中心のないシステムの宿命 Winnyでは「初期ノード」の登録を手動で行うことで解決 オーバレイ ネットワーク ピア ランデブーも通信もピア同士で行う どうやってオーバレイ ネットワークに参加？

28 Winny: 広告と検索 公開者がより積極的に広告を行う 公開者は、ファイルの情報をP2Pネットワークを通じて隣接するPeerに広告
BさんのファイルをAさんが 探してる！！ Bさんがあの ファイルを持ってる 持ってないよ！ Bさんがあの ファイルを持ってる 持ってないよ！ 持ってないよ！ Cさん Aさん Bさん 広告 あのファイルが欲しい… 皆に聞いてみよう！ このファイルを持ってることを 皆に教えてあげよう！

29 Winny: ファイルの公開 オリジナルファイルからキーとボディを生成 キーに含まれる情報 ファイルの公開と同時にキーがネットワーク上を拡散
ファイルサイズ 更新時刻 ハッシュ値 ファイルの所在を表すIPアドレス・ポート番号　など ファイルの公開と同時にキーがネットワーク上を拡散 upload folder キー（ファイルの要約情報） ファイルボディ（ファイルの本体） file.ppt

30 Winny: ファイルの転送 Winnyでは中継転送とキャッシュを採用 Napster、WinMX、Gnutellaは相手に直接接続
第三者を介在する 匿名性を実現 Napster、WinMX、Gnutellaは相手に直接接続 公開者と検索者だけ転送が完結

31 私のファイル人気があって 配るのが大変……
Winny: 中継転送 中継転送 P2Pネットワークでの中間のPeerが転送を中継 下の例では検索と広告を合致したCさんが中継転送 転送のパフォーマンスを犠牲にすることで、キャッシュを持つPeerを増やし冗長性を確保 Bさんのファイルを 中継してあげよう！ Cさん Aさん Bさん Cさんが持ってたんだね！ 私のファイル人気があって 配るのが大変……

32 Winny: キャッシュ キャッシュ ファイルを取得したPeerや、中継転送したPeerがそのファイルの複製を第三者に自動的に再公開
耐故障性の実現(冗長性の確保) 検索効率の向上 中継したファイルを他の人にも配って良いよね！ Cさん Aさん Bさん このファイルを他の人にも配ってあげよう！ 他の人も配ってくれると 楽で良いね！

33 Winny: 中継転送とキャッシュによる匿名性
一度流れたデータを誰も消せないシステム キャッシュとして多数のPeerに情報が残っている ソフトの例：Freenet、Winny 用途の例：P2P掲示板、ファイル共有 解決しなければならない問題 公開した元の人間の特定 法的に問題のあるコンテンツ 　 の転送を知らずに行えない 　 ようにする (ということが必要かもしれない) Bさんのファイルを 中継してあげるね！ Cさんが持ってたんだね！ Aさん Bさん Cさん このファイルを他の人にも配ってあげよう！ 中継したファイルを他の人にも配って良いよね！ 私が最初に公開したと わからなくなる！ Aさん Bさん Cさん

34 Winny: ネットワークの上流と下流 能力の高いノードにキーとキャッシュが集まる より高速 より低速 キャッシュ キャッシュ キー キー
高速なノードほど データの流量が多い （処理に負荷がかかるがデータは大漁） キャッシュ キャッシュ キー キー キー キャッシュ キャッシュ キー キャッシュ キー キャッシュ キャッシュ キャッシュ キー より高速 キー キー キー オリジナル ファイル より低速 キー キー オリジナル ファイル キャッシュ 低速なノードほど データの流量が少ない

35 Winny: クラスタリング 検索嗜好のより近いものでグルーピング より効率のよい検索が可能となる 嗜好A 嗜好B 嗜好C クラスタA
輪を絞って ファイルを探索 全体の輪の中 からファイルを探索 クラスタA クラスタB クラスタC

36 Skypeと自律分散協調

37 ファイル交換でないP2Pソフトウェアの例: Skype
各ノードの自律性はどのようになっているか？ 何を分散し、何を分散していないか？ 分散しないことによって担保されているのは何か？ Loginプロセスを中心に考察

38 Skypeとは？ KaZaaの開発者によって開発されたVoIPクライアント 音声通話とテキストメッセージングが可能
MSN/Yahoo IMアプリケーションと以下の点で類似する 音声通話ができる テキストメッセージングができる カンファレンスができる バディリストを備える 基本となるプロトコル、技術はまったく異なる

39 SkypeのLook and Feelとできること
音声通話 テキスト・メッセージング ファイル送信 ユーザ識別子 Skype ID 一意性のあるID バディリストに登録できる バディリストから選んで 通話 チャット

40 Skype Network Skypeの利用するオーバーレイネットワーク 2種類のノード Ordinary Hosts
普通はこれ Super Nodes (SN) Skypeネットワークにordinary hostsが収容される端点 Global IP addressが利用できる 十分なCPU、メモリ、帯域を備える 自動的に選択される

41 Skype Login Server User namesおよびpasswordを管理し、ユーザの認証を行う
User nameがSkype名前空間内で一意であることを保証 Skypeノードではないものの、Skypeネットワークの重要なエンティティである ordinary hostsはログインの際、super nodeに接続するだけでなく、Skype login serverへも接続

42 Host Cache (HC) オーバレイネットワークを構成するためにSkype Client (SC)内に記録更新される情報
Super Node の IP address / port number 少なくとも1つは利用できるエントリが無いと、動作しない SCとして2日間動作すると、HCとして最大200エントリまで増えることが観測されている Skype Node内のWindows registryに記録される host/peer cacheは目新しいものではなく、Chordでは、Finger tableとしてノード発見に利用されている

43 (参考) Skypeでlistenしているport
connectionダイアログボックスで設定されたTCP/UDPポート これはインストール時にランダムに設定される 通常のインターネット上のプロトコルのように一定しない それ以外に80/TCP (HTTP)および443/TCP (HTTPS)を利用する

44 Buddy Listの利用 Buddy ListをWindows registry内に保存 電子証明および暗号化されている
SCにローカルに保存されているだけで中央には一切おかれない ユーザがSCとして異なるマシンを利用した場合、バディリストを再構築する必要がある

45 (参考)Skypeで利用しているCodec
iLBC iSAC 未知のコーデックがあるかもしれない GlobalIPSound iLBCおよびiSACを実装し、Skypeがパートナーであると彼らのWEBで明言している SkypeはGlobalIPSoundのcodecを使用しているものと推測される 測定の結果50-8,000 Hz がSkypeのcodecで利用可能であった これはwideband codecの特徴として認められる

46 Skypeの暗号化 通話とインスタントメッセージングを暗号化
AES(Advanced Encryption Standard, Rijndel)を使用と明言 256-bit暗号化 1.1 x 10^77の鍵を使用可能 また、AES共通鍵のネゴシエーションに bitのRSAを使用 ユーザの公開鍵がログイン時に使用されている

47 NAT/Firewall通過 STUNを利用NAT/Firewallの種類特定し、UDP Hole punchingを使って通信していると推測 UDP Hole punchingが使用出来ない場合はスーパーノード越しに通信 NAT/Firewall通過のためのサーバは存在しないと推測される SCは定期的にNAT/Firewallについて調査し、結果をWindows Registry内に保存 UDP Hole punchingとは？ パケット (1) (2) パケット :1234 宛にパケットを送ると到達 P2P-friendly NAT パケットのsourceを見ると :1234

48 Skypeの動作は以下に分類できる startup login user search call establishment
tear down media transfer presence messages

49 (参考) Startup SCのソフトウェアが導入され、初めて動作する際にSkype server (skype.com)にHTTP 1.1 GETリクエストを送る このリクエストには‘installed’というキーワードが含まれる 次に、新しいバージョンのSkypeが利用可能かを判断するためにHTTP 1.1 GETリクエストを送る このリクエストには‘getlatestversion’というキーワードが含まれる

50 Loginプロセスとは？ 何も知らないピアがオーバレイネットワークに参加する 1つでもオーバレイネットワークのノードを知らないと参加できない
オーバレイネットワークに参加していればピアについて認知できる 鶏と卵 中心のないシステムの宿命 オーバレイ ネットワーク ピア ランデブーも通信もピア同士で行う どうやってオーバレイ ネットワークに参加？

51 Skype Loginの2つの意味 Skypeネットワークへの参加 SkypeID認証 オーバレイネットワークにピアとして参加する
場合によってはSuper Nodeにもなりうる SkypeID認証 Skype IDが一意であることを保証している基盤 認証を行う

52 オーバレイネットワークへの参加 自分以外のピアおよびバディに対してオンラインになったことを広告する
NAT/Firewallの背後にいるかどうか、型の判定 Global IP AddressのSkypeピアを発見する Host Cache (HC)は1つ以上の有効なエントリがなければいけない HCに有効なエントリがない場合、Skypeネットワークに参加できない このばあい、login failureとなる

53 Login ServerによるSkype ID認証
SNにSCが接続すると、SCはUser Name / passwordを用いてLogin Serverに認証される Skype User Nameの一意性を保証する役割 Login Serverは、Skype Networkにおける唯一の中央集権的なエンティティ 観測によると SCはいつも というIP addressのノードとTCPで通信していた これがlogin serverではないかと思われる DNS(NSレコード)の逆引き ns14.inet.tele.dk ns15.inet.tele.dk

54 実際のLogin Processの流れ HCを空にしてみる
SC内のキャッシュをクリアした 1つのエントリを記録させた このエントリのマシンはSkypeが動作していない SCはログインを試みた HCに無効なエントリしかないので、Skypeネットワークに到達できないが、 UDPパケットをエントリのマシンに向けて送ることがわかった 大体5秒くらい返答がない場合、SCはTCPコネクションを先ほどのエントリに張ろうとする これは、HCのIP Addressへ80(HTTP)での通信を試みる さらに失敗すると、HCのIP Addressへ443 (HTTPS port)での通信を試みる その後大体6秒くらい待つ login failureとなった後、それら全てのプロセスをさらに4回行った

55 Bootstrap Super Nodes ソフトウェアのインストール後に初めてログインした場合 逆引きにより4つのISPにあることが分かる
7つのエントリを持っているらしい まれに違うこともあるが大体ここへつなげに行く Bootstrap Super Nodesと呼ぶ 7つ以上のHCで初期化される場合も、この7つは必ず含まれている 逆引きにより4つのISPにあることが分かる IP address:port Reverse lookup result :33033 sls-cb10p6.dca2.superb.net :33033 ip9.181.susc.suscom.net : x50a15b19.boanxx15.adsl-dhcp.tele.dk : x50a15b0c.albnxx9.adsl-dhcp.tele.dk :33033 rs ev1.net :33033 rs ev1.net :33033 ns2.ev1.net

56 まとめ:Skypeにおける鶏と卵の解決方法
まずは、 Bootstrap Super Nodesをハードコーディングしておき、Super Nodeのリストをどんどん追加・更新 SkypeID認証 Skype IDが一意であることを保証している基盤 認証を行うエンティティは世界で1つのLogin Server 唯一、分散できていない部分 議論 DNSSECのような信頼の伝播ができているわけではない DoS攻撃があったら？

57 参考文献 An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol
Salman A. Baset and Henning Schulzrinne Department of Computer Science Columbia University, New York NY 10027 September 15, 2004