** P2Pの技術的位置付け
技術者の多くは、世の中に次から次に現れる新しい技術用語を冷めた目で見ていると思います。些細な差に新しい用語を当てることが多いからです。本誌の読者の中にも、P2Pなんて用語には技術的に何の意味も無いと否定している人もいると思います。今から、P2Pという用語の技術的な位置付けを行います。読んで賛同してくれる人もいると思います。こんな分類に意味が無いと感じる人もいるかもしれません。賛同できない場合でも、本記事の範囲では、P2Pをこう位置づけて書いている、と理解して読んでください。
P2Pという用語で最も誤解を招きやすい表現は、P2Pは個人のPCが直接通信するネットワークです、という言い方です。個人のPCが直接やりとりするので、yahooのWebサーバにアクセスすることとは訳が違う、と言われても、普通の技術者であれば反発を覚えるのが普通でしょう。そもそもPCの定義とは何か、と文句をつけたくなるかもしれません。あるいは、家のPCにFreeBSDを入れてApacheを動かしていれば、yahooと何が変わるものか、と思うかもしれません。個人のPCが直接通信することで P2Pを定義するのが、技術用語として適切でないことは明らかです。本記事もこの定義は採用しません。どうしてもこの概念から抜けられない人には、P2P 通信、という用語を使うことがあります。今から述べる多ノードの対称ネットワークを意味するP2PネットワークやP2Pシステムと区別するためです。
現在、P2P(ネットワーク)という用語の最も一般的な定義は、対称(対等)なノードが作るネットワーク、です。クライアント・サーバモデルではノードの役割が決まっているのに対し、P2Pネットワークでは、あるノードがクライアントとして動作したりサーバとして動作したりします。ある瞬間の動作を切り出してみると、結局、クライアント・サーバと変わらないのでは、という疑問が湧くかもしれません。P2Pのファイル交換アプリでも、ある2台のPCの瞬間的動作を切り出すと、ftpやWebと変わらない動作です。これに関しては、2台だけの動作や瞬間的な動作など局所的な部分を切り出して論じることは意味が無い、と個人的に考えています。つまり、P2Pネットワークは、多ノードで構成される協調システム全体を意味する、という考えです。
P2Pを多ノードが構成する協調システム全体と定義するなら、従来のクラスタなどの冗長化システムと何が違うのか、と思う人がいるかもしれません。これらとP2Pを差別化する特徴はふたつあると考えています。ひとつは、中心が無いネットワークという特徴です。言い替えると、システム全体を管理するノードが無くても動作するシステムです。では、中央サーバを持つ代わりに完全冗長化したクラスタはどうでしょうか。10台のクラスタの場合、どの1台も残りの9台の状態を知っているシステムです。このようなシステムはP2Pとは違う、と考えています。P2Pでは、どのノードもシステム全体の状態を知りません。部分的な状態管理をするノードの集合が、全体として動作することが特徴です(*脚注)。もうひとつP2Pを特徴付ける点は、ノードの安定性や管理の問題です。ノードが不安定であることでP2Pを定義づけるのは、少し曖昧です。クラスタを構成するノードがたまたま不安定であればP2Pと呼ぶのか、と反論があるかもしれません。ここでは、突然ノードが参加したり離脱することを誰も制御できないシステム、を想定しています。別の言葉で言うと、ノードが不意に参加したり離脱したりすることをシステム要件として組み込んでいるのがP2Pです。
まとめると、対称なノードが作るP2Pネットワークは、中心が無く、全体を管理するノードが無く、不意にノードが参加や離脱をするような環境でも、多ノードが協調動作できるシステム、と言えます。現状のインターネット環境では、 TCP/IP層の上にアプリ層が作るオーバーレイネットワークで実現されるのが普通です(*脚注)。
このようなP2Pネットワークには、スケーラビリティ、耐障害性、アドホック性の高さの3つの利点があります。中心が無く、システム全体を管理するコストが無いP2Pは、ノード数やファイル数に対する高いスケーラビリティを誇ります。ホストにもネットワークにも単一障害点を持たないため、耐障害性に優れています。ノードの参加や離脱に対して自律的に適応できるシステムなので、アドホック性に優れています。

[*footnote*] Napsterはどうなんだ、と疑問に思うかもしれません。個人的な意見ですが、NapsterはP2Pではない、という見解です。少し妥協しても、探索に関してNapsterはP2Pではない、という意見です。
[*footnote*] アプリ層のオーバーレイネットワークという要件を外すと、P2Pを規定する特徴がインターネットそのものとほとんど同じになってしまうという罠があります。一方、無線のアドホックネットワークをP2Pの一分野としてとらえると、P2Pの定義にアプリ層のネットワークという縛りはつけたくない気もします。この辺の用語の境界はグレーゾーンです。


** 探索と配信
前節で、P2Pを多ノードが協調動作するネットワークと規定しました。何をするかまでは規定しませんでした。何をするかという自由度をまだ奪いたくない、という思いがあるからです。ただ、現実的にP2Pがうまく活用されている領域はまだ多くありません。探索と配信でカテゴリ化するだけで、充分に概観可能だと思います。
探索は、ファイル交換アプリのファイル検索を想像するのが最も分かりやすいでしょう。探索という用語は、ファイル名のようなキーからファイル自体を見つける検索から、Webのサーチエンジンのような全文検索まで幅広いですが、本記事では、ファイル名のようなキーによる検索に意味を限定します。

P2P探索で最も有名なアーキテクチャはGnutella型です。ネットワーク的にはフラッディングと呼ばれる手法を使います。Gnutella型の探索では、図のように探索要求をネットワーク全体に転送します(フラッド)。探索結果は、探索要求が伝播した経路を逆向きに伝播します。探索アルゴリズム的には幅優先探索を行っていると言えます。ネットワーク全体を管理する中心ノードが無くても、万単位のノードの中で探索を行うことができます。各ノードが持つネットワーク状態は、ごく少数の近接ノードへの経路を持つだけです。アドホック性が高く耐障害性に優れています。探索動作は完全に分散した形で進行するので、探索対象のコンテンツ数に対するスケーラビリティは高くなります。一方、ノード数が増えると、ネットワークトラフィックが増える欠点があります(*脚注)。

[*image*] Gnutellaの図
ノード間をlookupコマンドが伝播する図。
ノード間をhitが逆伝播する図。

[*footnote*] 多くのGnutella型P2Pファイル交換ソフト(KaZaAなど)では、ノードの階層化や様々な実装上の工夫でトラフィックの増加を抑制しています。

Gnutella と並んで有名なP2Pの探索アーキテクチャはFreenet型です。Freenetに触発されたと言われるWinnyや、Freenet作者による Dijjerなどが同じ系譜に属します[*脚注]。説明を探索アーキテクチャに限定するので、Freenetを特徴づける匿名性保証などの説明は省略します。
Freenetでファイルを探索する時、内部的には、ファイル名そのものではなくファイル名から生成するハッシュ値を使います。このハッシュ値を探索キーと呼びます。各ノードが探索キーを転送して探索を行う点は、Gnutellaに似ています。しかし、ノードが持つ状態と転送のアルゴリズムは異なります。Freenetノードは、近接ノードのIPアドレスと探索キーの組の集合を保持します(これを経路表と呼びます)。各ノードは、探索キーと数値的に最も近いキーを経路表から探し、その近接ノード(ひとつだけ)に探索要求を転送します。この転送は、TTL終了かループ検出の形で経路が尽きるまで継続します(*脚注)。探索の経路が尽きると、探索の失敗を逆方向に伝播します。探索失敗を受けたノードは、経路表を見て、次に数値的に近いキーを探し、再び、近接ノードに探索要求を転送します。
Gnutellaの幅優先探索に対し、Freenetは深さ優先探索的に動作します。一見すると、 Freenetの探索の効率はとても悪いように感じるかもしれません。しかし、Freenetは人気のあるコンテンツが素早く拡散し、拡散したファイルが自動的にクラスタ化する特性があります。このため、深さ優先で探索しても人気のあるファイルは早く見つかります。この仕組みは次のように成り立ちます。探索が成功した場合、コンテンツ本体が探索要求の経路を逆向きに転送されます(*脚注)。この時、各中継ノードは、その探索キーと経路上のノードを経路表に追加します。転送の時、数値的に近いキーで転送先ノードを選ぶと説明しましたが、探索成功時の経路表の更新の結果、数値的に近い探索キーの探索要求は、時間とともに特定のノード(群)に集中していきます。探索キー(ハッシュ値)が数値的に近いことはファイルの内容と無関係で恣意的ですが、探索のパターンによって、ファイルが自動的にクラスタ化します。

GnutellaやFreenetは、ノード数のスケーラビリティの問題があります。これを解決するために、近年、DHT(分散ハッシュテーブル)という技術が開発されています。DHTの詳細、およびその実装例としてPastryの説明は、次節で行います。

[*footnote*] GnutellaのコマンドはTTL(Time To Live)値を持ちます。ホップごとにTTLが1減り、TTLがゼロになるとコマンドの転送が止まります。Gnutellaはコマンドごとにユニークな IDを割り当てます。このIDはuuid(iso-11578)です。各ノードは転送したコマンドのIDを記憶して、コマンド転送のループを検出します。

[*footnote*] Dijjer<http://dijjer.org/>。Freenet作者によるファイル配布ソフトです。Skypeで採用していることでも知られるUDP Hole PunchingというNAT越え技術も特徴のひとつです。

[*footnote*] Gnutellaの場合、探索要求の経路を逆向きに転送されるのは位置情報です。

[*image*] Freenetのlookup伝播の図
http://www.doc.ic.ac.uk/~twh1/academic/papers/icsi-revised.pdf の7ページの図

P2P 技術をファイル(コンテンツ)やメタ情報の配信に適用するシステムも多くあります。配信システムはファイル交換ソフトと表裏一体になることもありますが、ここでは、ネットワーク全体への配信(distribution)や購読者(subscriber)への配信(publish)の効率化に焦点を絞った P2P技術を概観します(*脚注)。P2P技術のファイル配信システムで最も有名になったシステムはBitTorrentだと思います。 BitTorrentに関しては次章で詳しく説明します。ストリーミングのP2P配信としてPeerCastが有名です。Peercastはストリーミングデータをノードからノードへ転送します。
メタ情報はファイル本体ほどサイズが大きくないので、まだP2P配信にあまり強い動機は無いようです。しかし、P2Pの特徴として挙げた、スケーラビリティ、耐障害性、アドホック性の強みから、メタ情報をP2P配信する動きは今後でてくるかもしれません。アルゴリズムのひとつとして、gossipingと呼ばれるアルゴリズムのrumor mongeringを紹介します(*脚注)。探索だけでは無いP2Pの一面が見られます。rumor mongeringを始めるノードをノードXと呼びます(配信の開始ノード)。ノードXはインターバルT秒ごとに適当なノード(ノードYと呼びます)を選択して、情報を送ります(噂の送信)。情報を受けたノードYは、同じロジックで情報の送信を開始します。こうして各ノードに送信開始モードが伝播します。ノードは、送信先ノードが連続してn個、既に情報を持っていた場合、送信を止めます。適切なnを選ぶには全体のノード数に関する知識が必要ですが、非常に局所的な状態管理だけで全体に情報を拡散できるアルゴリズムです。
P2Pコンテンツ配信のビジネスで有名なのがKontikiです。各ノードが配信元になるP2Pの特性から、よりIP的に近いノードからの転送や複数ノードからの並行転送で、配信のネットワーク効率を向上しています。

[*footnote*] この分野には、配信元の身元を隠す技術領域もありますが、本記事では扱いません。
[*footnote*] PlanetPで使われています。http://www.panic-lab.rutgers.edu/Research/planetp/


* Pastry詳解
** DHT(分散ハッシュテーブル)とは
DHT は2001年頃に提案された新しい技術です(*脚注)。技術的な系譜は、分散DBやWebキャッシュの研究からつながっています。コンテンツを複数サーバに均等にばらまくことで負荷分散するアイディアがあります。このために、コンテンツのハッシュ値を計算して、ハッシュ値に応じて複数サーバにコンテンツを分配します。DHTの基本戦略も、探索対象のハッシュ値を計算し、そのハッシュ値に応じてP2P上のノードにばらまくことです。従来のネットワークハッシュ技術(Consistent hashingやDistributed Dynamic Hashingがあります(*脚注))とDHTの大きな違いは、DHTがP2P環境、つまり中心の無いネットワーク環境で動作することです。つまり、 DHTでは、ハッシュ値とノードの対応を管理する中央ディレクトリサーバが存在しません。同様に、レジストリサーバなどが無く、ノードは不意に参加したり離脱したりします。つまり、DHTにはハッシュ空間全体を管理する特別なノードは存在しません。個々のノードはハッシュ空間上を局所的にしか管理しません。局所的管理をするノードの集合が協調動作を行い、P2Pネットワーク全体での探索を行います。探索の協調動作をいかに効率良く行うか、そして、不意のノードの参加や離脱に対していかに耐性を持つか、これがDHTのアルゴリズムの肝となります。

DHTの基本アイディアは次のようなものです。まず、P2Pネットワークを構成する各ノードにハッシュ値を割り当てます。例えば、そのノードのIPアドレスからハッシュ値を計算します。この時のポイントは、ハッシュ値の取りうる範囲が充分に広いことと、値が一様にばらけることです。前者はSHA1など160ビットのハッシュ関数を使うことで、構成ノード数より遥かに広い範囲の値を得られます。後者はハッシュ関数が本質的に持つ特性です。ノードに割り当てられるハッシュ値は、それぞれのノードが独立に計算しても、重なりや偏りが無く一様に分布することが期待されます。次に探索対象のハッシュ値を計算します。例えば探索対象がファイルであれば、ファイル名のハッシュ値を計算します。説明のために、しばらく探索対象をファイルに限定します。ファイル名のハッシュ値の取りうる範囲は、ノードに割り当てたハッシュ値と同じにします。一般には、単に同じハッシュ関数を使います。ハッシュ値の数値空間上で、ノードとファイルが一様で疎に分布した状態を想像してください。ここでノードとファイルを結びつけます。このための前提として、ハッシュ値の数値空間上に距離を定義します。距離の定義に何を採用するかは、 DHTのアルゴリズムごとに異なります。後で具体的なアルゴリズムを説明するまで、直感的な空間上の距離を想定してください。各ノードは距離が近いファイルの位置情報を管理します。ハッシュ値の数値空間を図のように円で表現すると、次のようになります。位置情報が管理されないファイルは探索できません。全てのファイルは、どれかのノードに位置情報を管理される必要があります。

[*footnote*] Consistent hashingについてはhttp://cs.brown.edu/courses/cs296-2/papers/consistent.pdf を参照。Distributed Dynamic Hashingについてはhttp://db.cs.berkeley.edu/papers/S2K-94-50.pdf を参照してください。
[*footnote*] Chord, CAN, Pastry, Tapestryなどが代表的なシステムです。
[*image*] Chordの図 or 概念図(空間上で各ノードが近傍のファイルを管理する図)

ファイルを探索する場合、ファイル名からハッシュ値を計算して、ファイルの位置情報(*脚注)を管理するノードを探索します。ノードの数が少なければ、全てのノードに問い合わせることもひとつの手です。これは、ノードの数が増えると効率が悪いことが分かるでしょう(*脚注)。ノード数に対するスケーラビリティを確保するため、DHTでは探索要求を転送(ルーティング)します。探索要求の転送は、ホップごとに、探しているファイルのハッシュ値と距離が近いハッシュ値のノードに近づきます。ハッシュ値の空間上で、ノードをホップしながら、所望のファイルに近づくイメージです。ファイルから一番近いノードに至ると、ファイルの位置情報を得られます(*脚注)。探索要求の転送を行うため、各ノードは経路表(ルーティングテーブル)を持ちます。これは、IP層の経路表とは無関係で、アプリ層(オーバーレイネットワーク)の経路表であることに注意してください。DHTの経路表は、自ノードからのハッシュ値空間上の距離と、その(距離空間の)範囲に属するノードへの経路から成ります。各ノードはそれぞれの経路表を参照して、探索要求を転送します。各ノードは、距離が近い空間にいるノードへの経路は密に知っています。逆に、距離が遠い空間にいるノードへの経路は疎にしか知りません。これは、ハッシュ値が一様に分布することからの帰結です。経路表が持つ局所性への敏感さは、ノードが参加や離脱を行った時の、各ノードの経路表の更新処理の効率さにつながります。経路表のサイズは有限なので、一般に、各ノードは最も近いノードではなく、より近いノードへ探索要求を転送します。転送のホップごとに探索空間が1/nずつ小さくなった場合、探索はノード数に対してlogオーダーで終了します。
ファイルの探索の前処理として、ファイルの登録が必要です。登録処理は、事実上、探索処理と同じです。登録するファイルのハッシュ値に距離的に近いハッシュ値を持つノードを探して、そのノードにファイルの位置情報を登録する処理だからです。

[*image*] 経路表を参照する転送の概念図(ホップごとに探索が1/nずつ収束する図)

[*footnote*] 位置情報はIPアドレスやURLです。位置情報ではなくファイルそのものを持つシステムもあります。本記事は、下位層の具体的なアドレス表現から独立した概念に、「位置情報(ロケーション)」という用語を使います。
[*footnote*] ノード数nに対してO(n)になります。
[*footnote*] 多くのDHTは冗長性のために、複数の近傍ノードがファイルの位置情報を持ちます。


** Pastryアルゴリズム
PastryはDHTの中でも古参の一種です。マイクロソフトリサーチが開発しました(*脚注)。Pastryの特徴を以下に挙げます。

+ ハッシュ値の距離の定義は、prefixの一致度で定義します(prefix-baseルーティング)
+ ハッシュ値の長さは128bitです
+ 探索は、ノード数に対してlogオーダーです
+ 通常の経路表とは別に、leaf setと呼ぶ一種のショートカット経路を持ちます
+ 隣接ノードがレプリカを保持して冗長化します
+ (DHTから見ると下位層の)IP層の局所性をアルゴリズムに組み込み、IP的に近いノードを優先的に経路表に入れます
+ BSD風ライセンスの実装があります(FreePastry, Bamboo)

[*footnote*] http://research.microsoft.com/~antr/Pastry/
http://freepastry.rice.edu/FreePastry/
http://bamboo-dht.org/

DHTの理解の第一歩は経路表を理解することです。経路表が決まると探索要求の転送が定まります。経路表の更新(維持)も重要な要素です。この維持コストが高いと実用になりません。
ノードには128bitのハッシュ値が割り当てられます。このハッシュ値をノードIDと呼びます。DHTの概論で説明したように、どこかの中央サーバから割り当てられるIDではなく、各ノードが独立に計算して取得するIDです。Pastryは任意の整数パラメータbを持ちます。bはシステム設計時に決める値です。推奨値は4なので、本記事ではb=4とします。4bitを1-digitと扱います。この時、Pastryのハッシュ値空間での距離は次のようになります。あるノードXの経路表を考えます。ノードXのノードIDと先頭n-digit(prefix)が一致したノードIDを持つノードは、ノードXから見て距離がnと見なします。表1に経路表の例を載せます(4bitの1-digitを0からfまでの1文字の16進数表現で表記しています)。例は経路表が全て埋まっているように書いていますが、実際には空のセルもあります。経路表の上の方の行は、prefixの一致長が小さく、Pastryの距離の定義上、遠いノードです。例えば、1行目の意味する事実は、ノードXから見て遠くて広い空間(空間全体の1/32の範囲)の探索を、最大で僅か15個のノードへの経路でカバーすることです。
探索対象のハッシュ値(ファイル名など探索キーから計算されるハッシュ値)が与えられると、ノードXでは、ノード IDと探索キーのハッシュ値の距離を計算します。その距離nで経路表を引き、転送先ノードを決定します。探索要求が転送されたノードをノードYと呼ぶと、ノードYはそれ自身のノードIDからの距離に応じた経路表を持ちます。探索対象のハッシュ値に関して、ノードYはノードXよりも相対的に良い経路表を持っているはずです。


[*table1*]
9522369b54ca4c46b3fbaba0d64ca6e5のノードIDの経路表の例
+ 表記が長いので、先頭8数字のみを書きます
+ .は任意の数字(0-f)を意味します
+ selfは自ノードを意味します
+ prefix一致長が大きいと距離が近いことを意味します
+ 実際の経路表は全部のセルは埋まりません

|prefix一致長|ノード0|ノード1|(省略)|ノードf|
|0|0.......|1.......|2.......|(3から7まで省略)|8.......|self|a.......|(bからeまで省略)|f.......|)
|1|90......|91......|92......|93......|94......|self|96......|(7からeまで省略)|9f......|
|2|950.....|951.....|self|953.....|954.....|(5からeまで省略)|95f.....|
|3|9520....|9521....|self|9523.....|9524.....|(5からeまで省略)|952f....|
|4|95220...|95221...|95222...|self|95224...|95225...|(6からeまで省略)|9522f...|
(5行名から最後の1行前まで省略)
|32|9522369b54ca4c46b3fbaba0d64ca6e0|9522369b54ca4c46b3fbaba0d64ca6e1|(3からeまで省略)|9522369b54ca4c46b3fbaba0d64ca6ef|


ファイル探索の動作例を図で示します。表記を短くするため、ハッシュ値を16bitに限定します(b=4なので4-digit)。例として、探索開始のノードのノードIDを0d64、探索対象のファイル名のハッシュ値をa6e5とします。図では、経路表が必ず埋まっていて、またファイルのハッシュ値と完全一致したノードIDのノードが見つかっています。現実には、経路表のセルが空白のことがあります。また、ファイルのハッシュ値と完全一致ではなく、充分に近い値のノードIDが見つかれば、そのノードがファイルの位置情報を持ちます。
経路表のセルが空白であったり、そのノードが反応しない場合、少しでも自ノードより探索対象に近いノードに転送します。a6e5とのprefixの一致長が自ノードとの一致長以上で、かつ数値的にa6e5に自ノードより近いノードに転送します。この候補ノードは、経路表、あるいは後に述べるleaf setやneighborhood setから探します。


[*image*]
ノード: nodeid=0d64
0d64とa6e5のprefix一致長は0なので、経路表の0行名を参照
routing-table
|0|(カラム0から9まで省略)|a613ノードへの経路|(省略)| <=== 0行目、カラムaの経路があれば、そのノードに探索要求を転送
|1|...|
|2|...|
|3|...|

ノード: nodeid=a613
a613とa6e5のprefix一致長は2なので、経路表の2行名を参照
routing-table
|0|....|
|1|....|
|2|(カラム0からdまで省略)|a6e9|(省略)| <==2行目、カラムeの経路があれば、そのノードに探索要求を転送
|3|...|

ノード: nodeid=a6e9
a6e9とa6e5のprefix一致長は3なので、経路表の3行名を参照
routing-table
|0|....|
|1|....|
|2|....|
|3|(カラム0から4まで省略)|a6e5|(省略)| <==3行目、カラム5の経路があれば、そのノードに探索要求を転送


Pastry の各ノードは、経路表以外に、leaf setとneighborhood setと呼ばれるふたつの経路セットを持ちます。leaf setはショートカット経路です。距離が近いノードへの経路を、通常の経路表とは別に一定数保持します。経路表を索く前にleaf setで経路を索くことで、探索を効率化します。経路表のセルが空の場合、通常、leaf setから転送先ノードを選びます。後述するように、leaf setの維持コストは、経路表より充分に低いものです。leaf setを適切に維持することで、ネットワーク全体のトポロジの分離を防ぎます。
neighborhood setは、IP的に近いノードの経路を保持します(*脚注)。経路表のセルに入りうるノードは複数の候補があります。Pastryは、IP的により近いノードを経路表に使います。ハッシュ値の論理空間上の距離とは別の尺度であることに注意してください。

[*footnote*] アルゴリズム上IP層という規定はありません。事実上、IP層での近さです。近さの判定は、IPアドレスの比較やRTTの比較で行います。

探索コストと並んで重要なのが、経路表の維持コストです。維持コストは、経路表の構築コストから始まり、ノードの参加や離脱時における更新コストまで含みます。DHTの経路表の維持コストに関する研究は、定性的にも定量的にも、研究が続いている分野です(*脚注)。

[*footnote*] USENIX2004の"Handling Churn in a DHT"<http://www.usenix.org/events/usenix04/tech/general/rhea/rhea_html/index.html>など参照。

Pastry は経路表を次のように構築します。新しく参加するノードをノードXと呼びます。ノードXはPastryネットワークに参加するために、既にPastry ネットワークに参加しているノードのアドレスを、最低ひとつ知る必要があります。最初に知るべきノードをブートストラップノードと呼びます。ブートストラップノードの検出はPastryアルゴリズムの範囲外です。IPマルチキャスト(LAN内のUDPブロードキャストなど)での検出等を想定しているようです。このブートストラップノードをノードAと呼びます。ノードXは、自ノードのノードIDを決定します(これをnodeid-Xとします)。ノードX は、ノードAにkey=nodie-Xのjoin要求を投げます。このjoin要求は、探索要求と同じ仕組みで、Pastryのノード上を転送されます。 join要求を転送した経路上のノードをノードA、ノードB、ノードC,...,ノードZと呼びます。ノードXは、これらのノードと経路表の交換を行います。ノードXの経路表構築であると同時に、ノードAからノードZの経路表の更新処理も兼ねます。経路表の更新を図で示します。
leaf setの初期値はノードZから複製します。neighborhood setの初期値はノードAから複製します。ノードZのleaf setをもらうことはleaf setの定義から自明です。ノードAからneighborhood setをもらうことは、IP的に近いノードからブートストラップする仮定に基づいています。leaf setの更新は、leaf set内の適当なノードにleaf setを問い合わせてその複製をもらうことで行います。neighborhood setも同様に、neighborhood set内の適当なノードからneighborhood setをもらって更新します。

ノードの離脱には次のように対応します。経路表のL行目カラムdのノードが離脱している(反応しない)場合、L行目の他のセルのノードに問い合わせます。そのノードの経路表のL行目のカラムdのセルが所望のノードです。所望のノードが見つからない場合、経路表のL+1行目のノードに問い合わせます。そのノードの経路表のL行目のカラムdのセルが所望のノードです。

[*image*] 経路表の構築処理の図
[*image*] ノード離脱時の処理の図