« [P2P]自己署名証明書を用いたDHTにおける認証について | トップページ | [P2P]DHTコミュオフ会について »

2005.03.18

[P2P]DHTによるサーバレス・マルチキャストシステムの提案

今回はサーバがなくても、DHT(分散ハッシュテーブル)を使って自律的にマルチキャストNWを修復するシステムのシンプルな例を提案したい。PeercastのようなものをDHTで実現するためにはどうすればよいか?という問題である。

◇マルチキャストの基礎知識
DHTでマルチキャストを行うのであれば、アプリケーションレベルのマルチキャストとなる。
ところで、マルチキャストを行うには配信先ノードを頂点としたツリー構造が望ましい。つまり、この問題はDHTでツリー構造を構築し、さらに自動的にそれを修復するモデルを提案できれば良いことになる。

■基本原理
まずはスマートさなどを考えずに素朴にDHTでマルチキャストを実現する方法を考えてみよう。

1)配信元ノードA0はNノードに対して配信することができるとしよう。一般に自分の帯域、CPUパワーによってマルチキャストできるノード(つまり子ノード)は限定すべきである。これを各ノードXの配信ノード数N_Xと定義する。

2)配信ノードA0と接続したいノードはまず、A0に聞いて、配信ノードの子ノード数がN_A0に達してないか確認する。達してなければ、A0の子ノードとなる。このとき配信ノードA0の子ノードなので、A1_iとしよう。(iはA1のノードのi番目とする)

3)もし、A0の子ノード数が配信ノード数N_A0に達してれば、A0の子ノードA1_jに対して接続要求を掛ける。これもA0と同じようにN_(a1_j)以上に子ノードが存在するか確認する。

...このようなことを再帰的に行う。

4)マルチキャストツリーに参加できると、ノードA(i)_jはA(i-2),A(i-1)のノードを知っている事になる。つまり、直接の親ノードA(i-1)がなくなってもその親ノードA(i-2)からまた再帰的に接続要求を掛けて、新たなノードにつなげればマルチキャストツリーは修復する。

■応用編
基本原理でもマルチキャストツリーを構築する事ができたが、これは結構面倒だ。例えば親ノードが離脱した場合、
マルチキャストツリーに再参加するには時間がかかる。

そこで、DHTを使ってよりスマートなことを考える。
つまり、あるノードにマルチキャストツリーのトポロジー状態を記録させてしまうということだ。

1)配信元ノードA0は、充分帯域があり既に長時間DHTに参加しているノードZにマルチキャストツリーの状態を記録させるようにする。なお、A0がZを兼ねても良い。

2)参加するノードはノードZのマルチキャストツリー情報を入手する。この情報より最適なノードと接続交渉をする。

3)接続交渉がうまく行けば、マルチキャストツリーに参加できる。また、ノードZにマルチキャストツリーの変更を申し出る。参加したノードPは、まだ新たに接続が可能なノードをノードZの情報からランダムにQだけ抽出すること。これをノード群Qとしよう。ノードPはノードQとリンクをしておく。

4)ノードPは親ノードが落ちた場合、速やかにノードZに知らせてマルチキャストツリーの変化を申告する。それとともに
ノードPはノード群Qからノードをひとつを選び、マルチキャストに参加する。その情報を元に、マルチキャストツリーの変化をノードZに申告する。

マルチキャストツリーを管理するノードZには多くのノードから参照がかかる可能性があるので、マルチキャストツリーの情報を分割して、あるノード群で管理するのも良いだろう。

今回の提案では接続するノード数を端末毎に異なる事により、ノードによる性能の大小を有る程度考慮している。ただし、例えばCPUの負荷が他のアプリケーションによって突発的に変わったりした時の対処は考えていない。
このときには子ノードとの接続を強制的に切断することで、自分の負荷を下げる事などが考えられるだろう。
また、ノード間の遅延についても考慮すべきだろう。これをどのように対処するかは皆様のコメントを頂きたい。

|

« [P2P]自己署名証明書を用いたDHTにおける認証について | トップページ | [P2P]DHTコミュオフ会について »

P2P」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/3349263

この記事へのトラックバック一覧です: [P2P]DHTによるサーバレス・マルチキャストシステムの提案:

« [P2P]自己署名証明書を用いたDHTにおける認証について | トップページ | [P2P]DHTコミュオフ会について »