Re: DHTシェルにおけるFinger Tableに関して

[Ryohei Banno]

はじめまして、北海道大学大学院の坂野と申します。

ご質問の件についてですが、
・ノード名とIDの区別
・参加ノード数とID空間の大きさの区別
を考えれば解決するのではないでしょうか？

以下解説です。まず、
　emu0,emu1・・・
というのはノード名であってオーバーレイ上のID（ハッシュ値）ではありませんので、
記載されているpredecessorからするとIDの順序関係が
　ID(emu0) < ID(emu3) < ID(emu2) < ID(emu1)
となっていると思われます。

またフィンガーテーブルについてですが、
chordの場合、2^mのハッシュ空間においてIDがxであるノードのフィンガーテーブルFは次のような式で表されます。

　F = { next(Z) }
　ただし、Z=x+2^i mod 2^m （0≦ i ≦m-1）

ここで、next(Z)というのは、ZというIDを管理するノードを指します。
つまり、ご質問の
「0のFinger Tableは1,2 1のFinger Tableは2,3 のようになる」
という部分は、
「ID=0のFinger Tableはnext(1),next(2) ID=1のFinger Tableはnext(2),next(3) のよ
うになる」
とするのが正しいと思われます。

例えばID空間が2^3=8の場合、IDが0であるノードのフィンガーテーブルF0は
　F0 = {next(1), next(2), next(4)}
になります。もしID空間上に存在するノードが
　ID=0,ID=4,ID=7
の3つだったとすると、フィンガーテーブルF0は
F0 = {next(1)=4, next(2)=4, next(4)=4}
= {4}
になります。

以上です。
的外れな回答でしたらすみません。
また、論文やOverlay Weaverの実装をチェックしながら書いているわけではないので、
誤りや表現のおかしい箇所があるかもしれませんがご容赦下さい。


On 6月22日, 午後8:49, Kouhei Toyama <a.i.r.98...@gmail.com> wrote:
> はじめまして、戸山と申します。
> 大学の卒業研究においてDHTを扱うことになり、Overｌay Weaverを利用させて頂いております。
> Finger Tableの値はどのように決定されているのでしょうか？
>
> ルーティング様式がhttp://overlayweaver.sourceforge.net/doc/overview/img/iterative-routi...
> 上記の画像のように説明されていたので、4ノードを立ち上げて
> emu0が1,2,3に対してinitを行えば、
> 0→1
> ↑　 ↓
> 3←2
> のようなDHTができて、Chordのアルゴリズムにより2のn乗に対してFinger Table
> を持つので、 0のFinger Tableは1,2 1のFinger Tableは2,3 のように
> なると考えていたのですが、以下のシナリオファイルで実行したところ、
> emu0のPredecessorは1 emu1は2 emu2は3 emu3は0
> 0→3
> ↑　 ↓
> 1→2
> 上記のようなDHTになり、Finger Tableはemu0は3,2 emu1は0,2 emu2は0,3 emu3は0
> となりました。emu0に関しては2のn乗になっているのですが、
> それ以外の1,2,3に関してはなりませんでした。
> 下記がシナリオファイルとなります。
>
> timeoffset 2000
> # 4node invoke
> class ow.tool.dhtshell.Main
> arg
> schedule 0,1000,4 invoke
> timeoffset 7000
> # 3 nodes join an overlay
> schedule 0 control 0 init emu1
> schedule 1000 control 0 init emu2
> schedule 2000 control 0 init emu3
> # status
> schedule 4000 control 0 status
> schedule 5000 control 1 status
> schedule 6000 control 2 status
> schedule 7000 control 3 status