P2Pのお勉強適当編

P2P技術を検索・ルーティング技術の観点から分類する

大別するとこの3つ

ハイブリッドP2P型
ピュアP2P型
スーパーノード型（混在型）

スーパーノード型

FastTrackのP2Pプラットフォーム（www.fasttrack.nu）が行っており，KaZaA （www.kazaa.com）のようなアプリケーションによって広まってきている．しかし，階層構造の頂上近くに位置するスーパピアの故障に対する復元力を犠牲にしている．また，これらの方法はオブジェクトを見つけ出す保証をしていない．
Looking up data in P2P systems

KaZaAやSkypeのように、処理能力の高いノード（上位ノード）がサーバとして働き（ピュアP2P）、下位ノードは、検索は上位ノードに問い合わせ、その他の処理はP2Pを用いて行う（ハイブリッドP2P）、この複合型の方式をスーパーノード型ハイブリッドP2Pと呼ぶ。
Peer to Peer - Wikipedia

ピュアP2P型

WinnyやGnutellaのように、特定のサーバを持たず、全ての処理をP2Pを用いて行うようなネットワークはピュアP2Pと呼ばれる。
Peer to Peer - Wikipedia

ブロードキャスト方式（Gnutella,LimeWire,BearShare）

Gnutellaでは，ファイルを検索したいピアは隣接のピアに検索パケット（クエリ）をバケツリレーしてファイルを検索する．
ホップ数は通常7段（重複がなければ約２万のピアが検索対象）．
このホップ数を大きくすれば，ネットワーク全体を検索対象にできるが，トラフィックが増加したり，無駄が多すぎるので問題．（『P2Pサービスにおける物理ネットワークを考慮した論理トポロジー構築手法』とかに隣接ピア数とホップ数の違いによってどの程度トラフィックが増加するのか，みたいな実験があった）

“ブロードキャスト”方法は，ブロードキャストメッセージによって消費される帯域幅や，メッセージを処理しなければいけない多数のノードによって消費される計算サイクルが原因となり，拡張性がない．実際， Napster
が閉鎖した次の日，Gnutella ネットワークは，音楽を共有しようと移行して来た多数のユーザのために生じた負荷によって崩壊してしまった．
Looking up data in P2P systems

シェアドリンク方式

Welcome to SIONet World !!: ƒ†ƒrƒLƒ^ƒXP2P : ¯‡—²¬ (hoshiai)
さまざまな属性に基づいて｢同好の志を発見｣し、｢それらとグループを動的に形成｣し、｢グループ内で情報やサービスを共有｣すること、および、グループ間のシームレスな連携が可能な｢次世代コミュニケーションツール｣です。

ピアは自分に関するメタデータを登録できる．そして，自分に近しいメタデータの付いているピアと優先的に繋がる．
パケットを送信するときに，パケットに対してメタデータを付与できる．そして，そのパケットはメタデータの概念と合致するリンクにのみ選択的にパケットをリレーする．

depth-first方式（Freenet）

ネットワーク内の隣接ピアに対し，発見の可能性の高いルートから優先的に検索パケットを伝播する．（ルーティングテーブルを持ってる．DHTの一歩手前，かな？）

キャッシング方式（Freenet,Winny）

検索される頻度の高いリソースをキャッシングすることにより，検索距離を短くし，ネットワーク全体のトラフィックも押さえ，検索の効率化を図れる．

分散ハッシュテーブル（DHT）方式

上記の方式は，必ず目的のリソースが発見できるという保障がない．
本方式は，一定のホップ数で求めるリソースにたどりつける効率性を保障するために，DHTを用いたリソースやピアを管理する．

SRID方式

下記で挙げるDHT方式は『検索の多段リレー』による方式だが，この方式はRDV(Rendezvous Peer View)と呼ばれるテーブルで，存在するすべてのランデブーピア（リソースやピアを管理する代表者．クラスタヘッドとかシンクノードみたいなもの…かな）を管理する．
この方式はランデブーピアがある程度永続的に存在する必要性や，ランデブーピアを管理するのが大規模になると難しいよね，っていう問題がある．

CAN方式とChord方式…その他もろもろ

アルゴリズム間の主な差異は，O(log N)の検索を提供するために経路表として用いるデータ構造にある．
Chordは skiplistに似たデータ構造を維持する． Kademlia， Pastry， Tapestryでは個々のノードは木に似たデータ構造を維持する． Viceroy はbutterfly データ構造を維持する．このデータ構造では各ノードは定数個の
他のノードについての情報を保持するだけで，O(log N)検索を提供する．
Looking up data in P2P systems

- CAN(Content Addressable Network)

こいつだけちょっと違って，検索のためのコストが $O(dN^{\frac{1}{d}})$ かかる．（d次元空間）

- Chord

こいつはConsistent Hashing(http://www.hyuki.com/yukiwiki/wiki.cgi?ConsistentHashing)の改良版．
ChordはConsistent Hashingの多くの性質を踏襲しているが，そのスケーラビリティの問題を解決している．（Consistent Hashingは他のほとんどすべてのホストの情報を把握している必要があった．Consistent Hashingの方は原理的には１ホップでリソースにたどり着ける）*1