4

私は現在Chordプロトコルを扱っています。

各ノードには 2 つの関数がfindSuccessorあり、closestPrecedingNodeこれらは疑似コードとして提供されます。

findSuccessorは：

n.findSuccessor(id)
  if(id is.in (n, successor])
    return successor;
  else
    n' = closestPrecedingNode(id);
    return n'.findSuccessor(id);

closestPrecedingNodeは：

n.closestPrecedingNode(id)
  for i = m downto 1
    if(finger[i] is.in (n, id))
      return finger[i];
  return n;

ノードが作成されると、そのサクセサは最初にノード自体に設定され、finger テーブルは空になります。

ここで私の質問は、ノードが 1 つしかない場合に何が起こるかということです。ノード自体の ID 以外の ID を要求されます。次に、ブロックをfindSuccessor実行してを呼び出します。finger テーブルが空なので、ノード自体は に戻されます。したがって、 は に等しくなります。elseclosestPrecedingNodefindSuccessorn'n

その後、自分自身への再帰呼び出しであるfindSuccessoron が呼び出されます。n'

そして、無限ループが発生します...または何か不足していますか?

注: 疑似コードは、Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications、ページ 5 から取得したものです。

4

1 に答える 1

6

「jchord」の実装者は、次のコードを に追加しているため、あなたに同意しているようですfindSuccessor。

if (this == successor) {
    return this;
}

しかし、疑似コードに近い、より洗練された解決策があるようです。ID が間隔 (n、後継者] (左除外、右包含) 内にあるかどうかをチェックする場合、そのチェックを周期的にします。jDHTUQ は次のように実行するようです (75 行目から。警告:本当に醜いコード):

http://jdhtuq.svn.sourceforge.net/viewvc/jdhtuq/source_code/distributed_lookup_service/LookupService/src/co/edu/uniquindio/utils/hashing/Key.java?revision=63&view=markup

私見が周期的な方法で間隔チェックを実行することは正しいことのようです。リンクした論文には次のように書かれています（4ページ）：

(a; b] という表記は、a から時計回りに移動して (a を含まず)、b に到達する (および b を含む) ことによって得られるコードリングのセグメントを示します。

単一ノードの場合、次のことを確認します。

id is.in (n, n]

trueid は の直後に始まりnで終わるリング内にあるため、これは生成されるはずnです。

于 2012-12-10T17:07:36.353 に答える