Pastry: Scalable Decentralized Object Location and Routing for Large Scale Peer to Peer Systems (2001)
November 7, 2023Pastryは、広域ネットーワーク規模のPeer-to-Peerなルーティングのアルゴリズムであり、メッセージをメッセージのキーに最も近いIDをもつノードに転送する。 Pastryに参加するノードは対称的で、すべてのノードは同じアルゴリズムにしたがう。
各ノードは、ルーティングテーブル、neighborhood set, leaf setを管理する。 ルーティングテーブルは\(\lceil \log_{2^b}N \rceil\)行\(2^b-1\)列のテーブルである。 ノードIDとメッセージキーは128ビットの整数であり、整数値は、整数値としてだけでなく、\(2^b\)進数の文字列としても比較される。 \(b\)のデフォルト値は4で、このときのノードIDは16進数の数列として解釈できる。 テーブルの\(n\)行\(c\)列には、\(n\)文字までのプレフィックスが等しいノードのIPアドレスを保存する。 \(c\)は、この共通するプレフィックスの次にある数字に対応し、そのために、この数字はノードIDの先頭\(n+1\)文字目にある文字と異なる。 neighborhood set \(M\)は、ノードから最も近くにある\(|M|\)個のノードのノードIDとIPアドレスのペアである。 leaf set \(L\)はノードIDの空間上の最近傍の集合であり、そのうちの\(|L|/2\)個のノードIDはより大きく、それ以外のノードには小さなIDが割り当てられている。
ノードが受信したメッセージの宛先でなければ、メッセージはキー\(D\)に最も近いノードID \(A\)のノードに転送される。 \(D\)がleaf setの最小値以上かつ最大値以下であれば、メッセージは、\(D\)に最も近いノードIDのノードに転送される。 範囲外であれば、\(D\)と\(A\)の共通するプレフィックスの最大長\(l\)とプレフィックスに続く\(D\)の文字が示すルーティングテーブルにノードのアドレスがあるかを調べる。
存在するのであれば、そのノードにメッセージを転送する。 次のノードでは、転送先のノードIDの共通プレフィックスの最大長は1以上長くなる。 テーブルに存在しなければ、\(L \cup U \cup M\)の要素のうちプレフィックスの最大長が\(l\)以上かつ\(D\)との距離が現在のノード\(A\)との距離よりも小さいノードにメッセージを転送する。
Pastryは動的にノードを追加、削除できる。 ただし、参加のアルゴリズムは、参加するノード\(X\)がPastryのノード\(A\)にアクセスできると仮定する。 \(X\)が参加のための特別なメッセージをノードIDをキーにして\(A\)宛てに送信すると、先述のアルゴリズムによって、メッセージは\(X\)のノードIDに最も近いノードIDの\(Z\)に転送される。 転送されるまでに経由した\(A\)などのノードは、自身の状態を\(X\)に送る。 \(X\)は、共有された状態から、ルーティングテーブル、neighborhood set, leaf setを生成する。 その後\(X\)は自分の状態をルーティングテーブル、neighborhood set, leaf setにあるノードにコピーする。
leaf setの最近傍のノードと通信できないければ、最近傍のノードがPastryから除外されたとみなす。このとき、欠けたleaf setの要素を補うために、通信できないノードのIDが自身のIDよりも小さいならば、leaf setのノードのうちIDが最小のノードにleaf setをリクエストし、大きければ最大のノードにリクエストする。 通信できなくなったノードがルーティングテーブルの\(l\)行\(d\)列にある場合、同じ行にある別のノードに\(l\)行\(d\)を問い合わせ、\(l\)行\(d\)列を上書きする。