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

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

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

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

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

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

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

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

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

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