Source
Peer Peer
Peer
Peer
TTL=0 になった
報告
TTL -1
通信開始
IP における TTL の扱い
Unstructured P2P の問題点と解決手法
z Unstructured P2P の問題点
z
ネットワーク負荷の増加z Flooding
を利用するために通信量が増加z
検索範囲が狭いz
検索範囲はTTL
によって限定されるため、検索対象が発見できない可能性がある
z いくつかの解決手法
z Structured P2P
を利用するz P2P
ネットワークの階層化z
アプリケーションの動作を工夫（Winny
を例に後述）Structured P2P
z Unstructured に比べ検索効率が高い
z 検索時のトラフィックの抑制を実現
z Distributed Hash Table
（分散ハッシュ表）を利用
z
検索対象の発見を効率化する仕組みz
検索対象を複数のノードで分散管理する仕組みz
提案されているDHT
プロトコルz Chord, CAN, Pastry, Tapestry, Kademlia, etc..
z DHT
を実装しているソフトウェアz BitTorrent, Warez P2P, eMule, etc..
http://en.wikipedia.org/wiki/Distributed_hash_table
ハッシュ値とハッシュ関数
ハッシュ関数では
A
≠B
の場合、F(A)
≠F(B
）が成り立つWikipedia, Hash Function, http://en.wikipedia.org/wiki/Hash_table
ハッシュテーブルとは
z
キーと値の組（エントリと呼ぶ）を複数個格納し、キーに 対応する値をすばやく参照するためのデータ構造Wikipedia, Hash Table, http://en.wikipedia.org/wiki/Hash_table
DHT 関連の論文
z Ion Stoica, Robert morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan, Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Aplications, IEEE/ACM Trans. Networking, Vol.11, No.1, p.
17-32, Feb. 2003.
z Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker, A Scalable Content-Addressable Network, In Proc. ACM SIGCOMM 2001, August 2001
z Antony Rowstron and Peter Druschel, Pastry: Scalable, decentraliszed object location and routing for large-scale peer-to-peer systems, Lecture Note in Computer Science, Vol.2218, pp. 329-350, 2001.
z Ben Y. Zhao, John Kubiatowicz, and Anthony D. Joseph, Tapestry: An
Infrastructure for Fault-tolerant Wide-area Location and Routing, Technical Report UCB/CSD-01-114, Computer Science Division, U. C. Berkeley April 2001, 55
z Petar Maymounkov and David Mazieres, Kademlia: A Peer-to-peer Information System Based on the XOR Metric, In Proceedings of IPTPS02, Cambridge, USA, March2002
P2P ネットワークの階層化（ Kazaa, Skype ）
z
スーパーノードが連携してインデックスを管理するスーパーノードクラスター
情報の保持
情報の保持 情報の保持
1.
ファイル検索要求2.
ファイル検索3.
ファイル転送内部では
DHT
を利用Skype の場合
z
ノード
z
NAT
やファイアウォールによって内向きの接続ができないこともあるz スーパーノードへ接続することで
P2P
ネットワークへ接続するz
スーパーノード ( リレーノード )
z スパーノード同士で通信し、ユーザー情報を同期する
z
P2P
ネットワークトポロジーの形成z
Firewall/NAT
でノード同士の直接通信ができない場合の中継役中継z
NMS （ Network Management Server ）
z 唯一、
Skype(Skype
を作ってる団体)
が管理するz スーパーノードの紹介
z ネットワークの最適化・ネットワークの品質管理
Skype 通話の仕組み
A B
スーパーノードの条件
•グローバルIPアドレス
•マシン性能が良い
•回線速度が速い
•Skype起動時間が長い、など