階層型DHTについてのまとめメモ

一般的なDHTのアルゴリズムには、ノード間のネットワーク距離（≒レイテンシ）を反映したルーティングを行う事が出来ないという欠点が有る。

これを解決する一つの案として、階層型DHTがある。
具体的なアルゴリズムとしては、HIERAS、LCLVなどが存在する。

例としてHIERASのルーティングアルゴリズムを紹介する。
近傍ノードのみを集めたネットワークが沢山ある下位層、中程度の距離のノードを集めたネットワークがいくつかある中間層、全てのノードが参加する単一のネットワークがある上位層、のようにDHTネットワークを階層状に多数作成する。
キーの検索を行う時はまず下位層から検索を始める。
しかし、キーに対応するバリューを持っているノードは近傍ノードとは限らないので、下位層に於いて同一ネットワークに属していない場合もある。
この時は、下位層に於けるSuccessorノードでキーに対応するバリューが無い事を確認して更に中間層へ検索を行う。
中間層でも見つからなければ、上位層でも検索を行う。上位層には全てのノードが参加しているので必ずバリューが見つかる。

運良く下位層でバリューを取得出来ればレイテンシをかなり削減出来るが、上位層まで検索しなければバリューが見つからなかった時はかえってレイテンシが増大する事もある。ここがこのアルゴリズムの欠点。

あと、DHTネットワークはメンテナンスコストがかかるので、ネットワーク数が増えるだけメンテナンスコストが増大する事になる。

HIERASではノードをグループ分けする時にDistributed Binning Schemeを使っているが、これの精度によってもルーティング時のレイテンシが変わってくると思われる。