自律分散協調システム論 第13回「Peer-to-peer systems」 中村　修 osamu@sfc.wide.ad.jp

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

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

Winny悪用による逮捕者とそのインパクト 2003年11月27日に逮捕者がでた段階で日本中のトラフィックは2割減少した http://www.mfeed.co.jp/jpnap/fr-traffic.html http://www.zdnet.co.jp/news/0311/27/nj00_winny.html

Winnyの悪用者が逮捕・製作者宅捜索 http://www.asahi.com/national/update/1127/035.html

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

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

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

例(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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Skypeと自律分散協調

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

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

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

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

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

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としてノード発見に利用されている

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

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

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

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

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

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

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

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

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

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

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

実際の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回行った

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

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

参考文献 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 {salman,hgs}@cs.columbia.edu September 15, 2004 http://www1.cs.columbia.edu/~library/TR-repository/reports/reports-2004/cucs-039-04.pdf