HIERASについて - syuu1228's blog

誰も日本語でHIERASの仕組みについて書いてくれないので、一番乗りしてみようかと思う。
Chordは沢山情報があるのに、階層化DHTとなると全然ですね。
そんな事研究したり実装してる人なんて、居ないのか。
未だあまりニーズが無いのかな？

■HIERASとは？
現在世の中で使われているP2Pシステムは階層型構造を利用しておらず、システムに参加する全ノードが一次元的なオーバレイネットワークに接続されている（例：Chordのリング構造）。
HIERASはDHTのパフォーマンスを向上させる為に、ルーティングアルゴリズムに階層型構造を導入したもの。
具体的にはChordのリングを複数作る事により階層構造を実現している。

■２階層の時のHIERASの例
第１階層のリングには全ノードが接続されている。
第２階層のリングは、ネットワーク距離の近いノード同士が集められており、それぞれのリングは独立している（どこかのノードで重複したりはしない）。
新しく接続されるノードが第二階層のどのリングに接続されるかは”distributed binning scheme”を用いて決定している。
※Topologically-aware overlay construction and server selection
http://berkeley.intel-research.net/sylvia/infocom02.pdf
追加対象ノードがネットワーク内で相対的にどのノードに近いかをICMPを用いた遅延計測で導き出し、この情報を元にノードを適切なリングに割り振ることにより、追加対象ノードがどのリングに参加すべきか判断できる。
この時、計測の基準点となるノードをランドマークノードと言い、予めインターネット上に公開されている必要がある。

■階層の深さとパフォーマンス
階層が増えるとホップ数が増えてしまうが、１ホップ間のレイテンシは小さくなる。
もっともパフォーマンスが良くオーバヘッドが少ないのは２〜３階層程度。

また、HIERAS全体で維持しなければいけないテーブル長は、階層間でノードが重複している為　階層数×ノード数　となる。

■データ構造
・Chordでは一つだったFingerTableを各層毎に用意する。
・ランドマークノードの情報を保持する為にランドマークテーブルを持つ。
ランドマークテーブルは単純に全てのランドマークノードのIPを持っている。
・他のリングの情報を保持する為にリングテーブルを持つ。
リングテーブルの構造は以下の通りである：
ringid, ringname, node(largest id), node(second largest id), node(smallest id), node(second smallest id)
ringnameはノードをringに割り付ける時に与えられるlandmark order。
ringidはringnameを元にコリジョンフリーなアルゴリズムを用いて生成する。
ノード情報としては、最もIDが大きいノード、二番目に大きいノード、最も小さいノード、二番目に小さいノードの４つを記録する。
リングテーブルはフォールトレランスの為に幾つかのノードが複製を持つ。
リングテーブルを持つノードは定期的にリングテーブルに載っているノードをチェックし、エラーがあればルーティング情報・リングテーブルを更新する。
リングテーブルは新しいノードが追加されるときにも用いられる。

■ルーティングアルゴリズム
ルーティング処理はリクエストを開始したノードが参加する最下層リングから始め、通常のChordと同じ方法でIDが最も近いノードへ到達する。未だその上に層がある場合は、更に上の層で同じくIDが最も近いノードへ進んでいく。この時の処理の違いはどの層向けのFingerTableを使うか、という事だけである。最終的に最上層でたどり着いた先がそのIDを所持するノードになる。
Predecesor・successorリストはこの処理の加速の為に使うことが出来る。
全ての層で、IDが最も近いノードへ到達した時にはそのノードがIDを所持するノードか否かの判断が行われる。
もしそのIDを所持するノードであれば、以降の処理はスキップされる。

■ノード操作
新しくネットワークに接続するノードは既にネットワークに接続済みなノードに接続し、ランドマークノードのテーブルを取得、ランドマークノードとの距離を計測、”distributed binning scheme”でどのリングに参加するか決定、接続しにいく。

次に、FingerTableなどのルーティング情報を最上層から順に構築していく。
最上層はChordの手法をそのまま用いる。
それより下の層では、以下の処理を用いる：
・参加先のringidをring table requestメッセージに乗せて最上位層のリングテーブルを所持するノードへ送る。このメッセージの送受信方法自体はChordのルーティング処理を用いる。
・Ring tableリクエストを受け取ったノードはリングテーブルから要求されたリングに属するノードリストを送り返す。
・ノードリストを受け取り、finger table creationリクエストを接続先のリングに送る。送り先は自分自身のノードIDとする。
・リクエストを受け取ったノードでは、Chordと同じメカニズムでリクエスト元向けのFingerTableを新たに作成し、送り返す。
・これで接続が確立する。
・自分のノードIDとRingTableのノードIDを比べ、更新の必要が有る場合は更新を行う。
以上のシーケンスを層数分繰り返す必要がある。

HIERASではChordと同様にノード離脱については特に処理を行う必要はない。
通信が出来ないノードが発生するとルーティングテーブルが補正される。