« [Skype]Skype勉強会を開催しようかと。 | トップページ | [P2P]P2Pの定義を考えてみる »

2005.04.02

[DHT]クラスターの概念を取り入れたDHTの提案

先日、DHTでスモールワールドの概念を取り入れたSymphonyを紹介した。
スモールワールドを応用したDHT:Symphony

Symphonyの大きな特徴として、参加しているノード数に関わらずリンク数が同じであることが挙げられる。
逆にいうと、DHTの実装者は自分でノードが他ノードとリンク数を好きに設定できる。
ちなみにホップ数はリンク数を2k+2とすると、O([log(N)]2/k)だ。

ところで、最近ノードのリンク数について色々と考えていた事がある。
というのはDHTではリンク数がノードのよらず対称である。しかし、ノードにはCPUやメモリーなどの差もあるし、それよりも深刻なのはノードによってDHTに参加している時間は大きく異なるのである。
そのようなことを考えると、リンク数は非対称な空間を形成した方がDHT全体にとってはありがたいのではないかと。

ここでは上記の考えに従ってSymphonyを改造していこう。

1)参加するノードは他ノードと総計2k+2のリンクを形成する。リンクの仕方はSymphonyと同じ。
2)参加するノードはCPUやメモリリソースにより、リンク上限Zを決定する。
3)参加するノードはある単位時間毎にリンク数を2pずつ増やしておく。
4)ある時間が来ると、 リンク総数 (2k+2)+2p > Zとなるタイミングが来る。それ以上はリンク数は増やさない。
5)リンク上限ZはPCリソースによってゆるやかに増減可能である。それによりリンク総数がZを超えた場合には、
ある確率(P(x)~1/x,xは自分のノードからのハッシュ空間の距離)の従いランダムにリンクを切断する。

※ちなみにGnutellaでは長時間参加しているノードは、引き続き参加する確率が高いというデータが出ている事を紹介しておこう。

このようにすると、
■PCリソースが大きいノード
■DHTに参加する時間が長いノード

についてはリンク数が増えることになる。これにより上記2条件を満たすノードはクラスタを構築し、結果的にはDHTのホップ数が減少するはずである。ただし、ホップ数の評価はしていないので興味のある方は計算して欲しい。
ちなみにSymphonyに対抗してこのDHTをConcertoと名づける事にしよう。(笑)
⇒concertoは「協奏曲」のこと。あるノードがクラスターを形成することにより、ソリストのように力をつけることから。

リンク数を非対称にする試みは他の人も色々と考えているようだ。このような事を考えてみると面白いDHTが構築できると思う。

|

« [Skype]Skype勉強会を開催しようかと。 | トップページ | [P2P]P2Pの定義を考えてみる »

P2P」カテゴリの記事

コメント

PCのリソース、ネットワークの接続時間に比例して動的に他ノードとのリンクを形成する仕組みは非常に面白いと思います。この仕組みで現在のDHTを利用したシステムより、他ノードとの接続において安定した動作がみこめると思います。
 ぜひ、実現してほしいです!

投稿: トモ | 2005.04.04 14:53

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: [DHT]クラスターの概念を取り入れたDHTの提案:

« [Skype]Skype勉強会を開催しようかと。 | トップページ | [P2P]P2Pの定義を考えてみる »