論文はこちら．
- Chord: A scalable peer-to-peer lookup service for internet applications
Chord
Chord は，構造化オーバレイの代表的なプロトコルのひとつである．Chord は，consistent hashing を用いてキーをノードに割り当てる．Consistent hashing は，ほぼ等しい数のキーをノードに割り当てることができるため，ノードの負荷を分散させることができる．また，ノードの参加や離脱の際，各ノードに割り当てられているキーの変化を必要最小限に抑えることができる．$N$ をオーバレイ上のノード数とするとき，定常状態では，それぞれのノードは，$O (\log N)$ の経路情報を保持する．あるキーの探索は，$O (\log N)$ のクエリで実現できる．
Consistent hashing は，ハッシュ関数を用いて，オーバレイ上のノードとデータに $m$ bit の ID を割り当てる．ノードの ID は，ノードの IP アドレスをハッシュすることによって，データの ID は，データのキーをハッシュすることによって，それぞれ決定される．ID のビット数 $m$ は，ハッシュ値が衝突する確率を無視できる程度に大きくする必要がある．ID は，Chord リングと呼ばれる，$2^m$ を法とする識別子空間上で順序づけられる．キー $k$ は，Chord リング上で $k$ から時計回りに進んで最初に見つかるノードに割り当てられる．このノードは，キー $k$ の successor と呼ばれ，$successor(k)$ と表記する．また，キー $k$ から反時計回りに進んで最初に見つかるノードは，キー $k$ の predecessor と呼ばれ，$predecessor(k)$ と表記する．ノード $n'$ がオーバレイに参加する場合，consistent hashing の整合性を保つために，$successor(n')$ に割り当てられていたキーの一部を $n'$ に再割り当てする必要がある．一方，ノード $n'$ がオーバレイから離脱する場合は，$n'$ に割り当てられていたキーをすべて $successor(n')$ に再割り当てする必要がある．キーの再割り当ては，ノード $n'$ と $successor(n')$ 以外のノードには生じない．
任意のキーへの探索を可能にするために，各ノードは，その successor への経路情報を保持している必要がある．経路情報とは，ID と IP アドレスの組である．あるキーの探索は，そのキーが割り当てられているノードへ到達するまで，探索クエリを successor に再帰的に転送することで実現する．探索結果は，探索クエリが通った経路を逆からたどるように再帰的に返戻される．
また，それぞれのノードは，finger table と呼ばれる経路表を持ち，$m$ 個の経路情報を保持する．ノード $n$ が持つ finger table の $i$ 番目のエントリは，$successor(n + 2^{i - 1} \mod 2^m)$ である．Finger table は，Chord リング上で自身に近いノードのいくつかを保持する．Finger table の各エントリは，ショートカットリンクとして機能し，$O (\log N)$ のクエリでの探索を可能にする．
ノード $n'$ がオーバレイに参加すると，$predecessor(n')$ は，自身の successor を修正する必要がある．なぜなら，Chord の探索アルゴリズムは，各ノードが successor への正確な経路情報を保持していることを前提としているためである．Chord では，バックグラウンドで定期的に実行される安定化プロトコルによって，successor と finger table を更新し，最新の状態に保つ．システムの堅牢性をより向上させるには，各ノードが自身から $r$ 個の successor への経路情報を持てばよい．この経路表は，successor list と呼ばれる．ノードの故障が確率 $p$ で生じるとすると，successor list 上のすべてのノードが故障している確率は $p^r$ となる．パラメータ $r$ を増減させることによって，堅牢性を任意に調節することができる．
参考文献
- Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan, ``Chord: A scalable peer-to-peer lookup service for internet applications,'' SIGCOMM 2001.
- Ion Stoica, Robert Morris, David Liben-Nowell, David Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, ``Chord: A scalable peer-to-peer lookup service for internet applications,'' IEEE Transactions on Networking 11, February 2003.
- Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, Steven Lim, ``A Survey and Comparison of Peer-to-peer Overlay Network Schemes,'' IEEE Communications Survey and Tutorial, Vol. 7, No. 2, pp. 72--93, 2005.
- Apostolos Malatras, ``State-of-the-art survey on P2P overlay networks in pervasive computing environments,'' Journal of Network and Computer Applications, Vol. 55, pp. 1--23, 2015.