Cacheの配布

neco Presentation
network communication
yuuki(M2)
scottie(M1)
ami(B4)
masa(B4)
ami-ta(B3)
odakei(B3)
junk(B1)
egichan(D1)
P2Pチュートリアル



P2Pの基礎
P2Pの仕組み
最近の話題
P2Pの基礎
昔から存在したP2Pモデル

P2P



Peer to Peer
同等の関係
発祥は10年以上前に遡る

ARPANet


コンピュータ同士を対等な「ピア」として結びつけるという観念
の上に成り立っていた
アプリケーション

NetWare-Lite…小規模なネットワークシステムに利用
P2PとC/Sの特徴

P2Pの特徴 – みんな頑張れ



安価なコストで構築できる
管理や監視がしにくい、隠蔽性が高い
C/Sの特徴 – サーバー頑張れ



クライアントの処理能力が小さくて済む
高性能なサーバーや大容量の回線等コストが
かかる
中央管理や監視がしやすい
P2Pのいろいろなサービス



タイプA: ファイル共有
タイプB: CPU資源共有
タイプC: 協調作業支援
タイプA: ファイル共有

MP3などのファイルを共有、検索、交換できる
♪
♪
♪
タイプA: ファイル共有の例

Napster


Gnutella



Pure P2P型
WinMX
Freenet


ハイブリット型
匿名性を高めている
もっとも盛んな分野

Crypttobox, Espera, Winny, iMesh, Scour Exchange, Aimster,
KaZaA
タイプB: CPU資源共有

巨大な処理をコンピュータで分散して処理


C/S
例）世界中のコンピュータで分担処理
例）複数のCPUで処理を分担
TypeA
タイプB: CPU資源共有の例

SETI@HOME



http://setiathome.ssl.berkeley.edu/
地球外からの電波を分析をし、地球外生命体
の存在を探す
ガン治療プロジェクト


http://www.geocities.co.jp/Playtown/2824/
jp2.html
ガンの治療薬の開発
タイプC: 作業環境の共有


ファイル共有に加え、IM, 音声チャット、テレビ
会議など
アプリケーション共有
タイプC:作業環境の共有の例

Groove


Lotus Notesの設計をしたOzzie氏
サーバーのいらないグループウェア


データは各ユーザーが保持
Plug-in形式のサポート

Microsoft Officeアプリケーションの共有等ができる
Groove 見てみよう
P2Pの分類


Hybrid
Pure
Hybrid P2P
データの
インデックス
ファイル名・user名
※Napsterがこの形態
server
IPアドレス・ポート
番号・パス
コネクト要求
PC
データ蓄積
ダウンロード開始
PC
データ蓄積
Pure P2P

Cacheの配布
ファイルやindexをサーバントへ配布
→ファイルの保有情報

ディスカバリー
サーバントが目的のファイルを持っているピアを探す手段
→目的ファイル場所の特定

転送
目的のファイルをダウンロード
Gnutella




NullSoft の Justin Frankel と Tom Pepper
により2000年3月に開発されたP2Pタイプ
のファイル共有ソフトウェア
Pure P2P型での実装、中央サーバーを必
要としない
あらゆる種類のデータを扱うことができる
帯域幅をけっこう消費するため、リッチな回
線環境が必要である
Gnutella型(1)
Cacheの配布
B
F
Network
C
A
自分のピア
G
D
E
•ネットワーク内のノードはつながっているが、
互いに何を保持しているかは検索するまでわからない
Gnutella型(2)
ディスカバリー
B
F
見つかった！
C
A
data
自分のピア
D
E
求めるデータのあるピア
Gnutella型(3) 転送
B
F
C
A
data
自分のピア
G
D
E
求めるデータのあるピア
Freenet




イアン・クラークの1999年の論文“A
distributed decentralized information
storage and retrieval system”「分散自立
型情報の保管と検索システム」
オープンソースで開発
情報の検閲なき配布
広帯域幅コンテンツの効率的分配
Freenet型


ブロードキャストの代わりにルーティングを
導入
関係のないピアには問い合わせを発行し
なくてすみ、負荷が軽減される。
Freenet型(1)
Cacheの配布
B
F
C
A
data
※HTL（TTL）=2
Network
Hash値
ソースデータ
data
data
Hash値
Hash値
D
E
G
情報保持者
•ソースデータとHash値をまわりにばらまく
Hash
next
F
100～299
100～300
Freenet型(2)
ディスカバリー
B
求めるデータの
ハッシュ値=300
300～499
301～499
E
・・・
・・・
F
見つかった！
C
A
Hash = 300
data
hash
自分のピア
hash
next
0～699
C
700～799
B
・・・
・・・
D
E
Next
うちには無いよ！
C
200～299
G
100～300
求めるデータのあるピア
G
400～999
・・・
・・・
Freenet型(3)
転送
B
F
data
C
A
data
data
自分のピア
G
D
E
求めるデータのあるピア
既存の問題点

Gnutella型



検索要求が溢れたり届かなかったりすることが多い
人気のあるノードでボトルネックが発生
Freenet型



キャッシュがすぐに押し出される
安定するのに時間がかかる
帯域幅やトポロジを考えていない (中継者が細い等)
最近の話題
Winny

ダウンロード板＠2ch.netにて開発中




申告した通信速度によって、階層的に接続
転送時に中間のノードが中継し匿名化
ダウンロード/中継したノードがキャッシュ
内容ではなく保持キーをばらまく。
Winny (接続画面)
Winny (検索画面)
Winny (ダウンロード画面)
Winnyの例(検索リンク)
1000
1000
100
A:60
B:300
80
200
50
C:50
15
Winnyの例(保持キー)
1000
100
A:60
index
B:300
index
index
data
80
1000
•上流に保持キーを
流していく。
index
index
50
200
C:50
15
Winnyの例(検索キー)
1000
100
A:60
index
B:300
index
index
80
1000
•上流に検索キーを
流していく。
index
!
index
50
200
C:50
15
Winnyの例(転送リンク)
1000
1000
100
B:300
80
A:60
data
•発見したノードが
中継を行う。
!
200
50
C:50
15
現時点での問題点

保持キー/検索キーがやはり溢れる。



現時点で推定１万ノード超
保持キーがバッファから押し出される。
カテゴリによるグループ化(未実装)
グループ化

角度がカテゴリ、中心からの距離が速度
FTTH
ISDN
xDSL
グループ化(Cont.)

近いノードは検索が成功しやすい。
映画
A
B
C
JPOP
おしまい
P2Pの歴史
昔から存在したP2Pモデル

P2Pとは



Peer to Peer
同等の関係
発祥は10年以上前に遡る

ARPANet



コンピュータ同士を対等な「ピア」として結びつけるという観念
の上に成り立っていた
草創期のインターネットプログラムは，接続を簡素化するた
め，サーバを仲介せずに，コンピュータ同士で通信するもの
だった
アプリケーション

NetWare-Lite…小規模なネットワークシステムに利用
ディスカバリー
求めるファイル･サービス
を提供してくれる相手を
どうみつけるの？
Winny型




あらかじめ、データを持っているピアから、そのデータが
あるというインデックスの情報が、グループ内に投げられ、
キャッシュされている。
データがほしいピアはそのインデックスの情報を探しに、
問い合わせを投げる。
求めるデータのインデックスに達することができればよい
ので、早い時点で見つかる可能性は高い。
ただ、インデックスと実データの同期が取れているとは限
らず、インデックスが見つかったのに、実際のデータを
持っているピアがオフラインだったりする可能性はある。
P2Pのいろいろなサービス
[email protected]
P2Pモデルの分類
P2Pなコミュニケーション
ICQ
MSN-Messanger
P2Pアプリケーション
Napster
Gnutella
FreeNet
Winny
再び注目されるP2P

Napster
従来の技術を使ったWebサイトにはない優位
性
従来だと…
P2P技術を用いると…

・すべてのデータを持
つのでサーバーに重
い負荷がかかる
・優秀なエンジニアや
サイト構築に多大な
資金が必要
・データの目次だけ持てば
いいのでサーバーへの
負荷が軽減される
・少ないコストと人材で
構築できる
Pure P2P
※Gnutellaがこの形態
Network
自分のindexを検
ない索
検索依頼
Aの検索依頼
検索結果
Cの検索結果
A
自分のindexを検
索
B
コネクト要求
C
ダウンロード開始
ディスカバリー



Gnutella型
Freenet型
Winny型
Cacheの配布



Gnutella型…Cacheなし
Freenet型…データのhash値をブロード
キャスト
Winny型…データのindexのcacheをブ
ロードキャスト
※hash関数…原文から固定長のぶつかりの少な
い値を生成する演算手法。
P2Pの今後

様々な研究分野がある。




ネットワークの構成
相手の発見
セキュリティの確保(匿名性,正確性,etc.)
アプリケーション
ネットワークの構成

網状に構成するだけでは効率が悪い。

自律的なグルーピング


ハッシュ値を利用(Freenet)
通信速度を利用(Winny)
相手の発見

意味情報を利用した検索(SIONet)




NTTみらいねっと研究所
ファイル名の代わりに意味情報を付加。
イベントプレースとして転送範囲を限定するこ
とで意味情報の一意性を確保。
自然言語処理による自動分類
セキュリティの確保

匿名性

基本的には転送に中継を挟むことで確保



Freenet
Winny
正確性

電子署名等を利用
Winny型（１）：Cacheの配布
index
Network
index
index
自分のピア
情報保持者
• 保持データのindexをbroadcast
※HTL（TTL）=2
Winny型（２）：ディスカバリー
B
F
C
A
index
Index
index
data
G
自分のピア
見つかった！
D
E
index 求めるデータのあるピア

Download Report