構造化P2Pの安定性(Stability)

1次元のID空間を使う構造化P2Pネットワークにも色々なタイプがあり、それぞれが異なるルーティング戦略を採用しています。例えば、ChordはID値を基にしたルーティングですし、P-RingやChord#はID空間上のホップ数を基本にしたルーティングを採用しています。他にも、PastyはBinary Treeに基づいたルーティングですし、SkipGraphはメンバーシップ関数を用いた確率的なルーティングを使っています。

私の現在の研究の出発点がChordであったことや、提案しているP2Pネットワークの構造がChord#やP-Ringに近いことから、これらのP2Pネットワークを実装して特性を調べたりしています。それで分かってきたことの1つは、ホップ数に基づいたルーティング戦略を用いる構造化P2Pネットワーク(Chord#やP-Ringなど)は、高Churn環境での安定性(Stability)がChordに比べて低いことです。というより、Chordの安定性が高いのですけどね。

図1: 新しいノードの参加によるルーティング先の変化

例えば、図1左のように4個ノードで構成された構造化P2Pネットワークがあったとします。この場合、ChordでもChord#でも同じルーティングテーブルが作成されます。そして、4個の新たなノードが参加し、参加ノード数が8個に増加したとしても、ChordとChord#のルーティングテーブルは同じように見えます。しかし、実際にこれらのP2Pネットワークを実装して確かめてみると、ルーティング先が安定するまでにかかる時間は「Chord << Chord#」なのです。 [caption id="attachment_765" align="alignright" width="320" caption="図2: Chordの場合のルーティング先の変化"][/caption]

Chordの場合、ルーティング先は「ID空間上の距離」を基準に決定します。そのため、「ID空間上のルーティング先として適した範囲」に新たにノードが参加しない限りルーティング先を変更する必要はありません。例えば、図2の場合、4個のノードで構成されていた構造化P2Pネットワークに新たに4個のノードが参加していますが、下方の赤いノードが新たに作成した(更新した)ルーティング先は(3)の1個だけとなります。他のルーティング先である(1)と(2)は変更していません。このように、Chordでは、ノードの参加と離脱によるルーティング先の更新が少ないため、高Churn環境での安定性は高いものになります。さらに、ノード1個が参加したときに更新されるルーティングテーブルは平均O(logN)個ですので、うまく更新情報を通知することでリアルタイムにルーティングテーブルを更新できます。

図3: Chord#の場合のルーティング先の変化

一方、Chord#では、ノードが参加した時にネットワークが安定状態となるまでに必要とする時間はChordより長くなります。これは、Chord#の場合、ルーティング先を「ID空間上で間に存在するノードの数」を基準に決定しているためです。例えば、図3の場合、4個のノードで構成されたChord#のネットワークに新たに4個のノードが参加すると、下方の赤いノードは「すべての」ルーティング先を更新します。ノードが増加したことにより(3)のルーティング先を新たに作成していますが、これ以外の(1)と(2)についても張り替えを行います。このルーティング先の更新に必要な時間は最大O(logN)となります。1個のノードが参加すると、他のノードの約半数がルーティング先を変更するため、うまく通知してリアルタイムにルーティング先を更新することもできません。そのため、高Churn環境ではChord#の安定性は低いものになります。

ただし、Chord#の安定性が低いといっても、ネットワークが崩壊するわけではないし、検索時間がO(N)となるわけでもありません。また、Chord#やP-RingのようにID空間上のホップ数に基づいたルーティング戦略を採用している構造化P2Pネットワークには範囲検索に対応できるという最大の利点があります。一方で、動的負荷分散を導入する必要があるという欠点もあるのですが。他の仕組みに目を向けると、Tree型のPastyには負荷分散の問題があり、SkipGraphにも検索効率の問題があります。もちろん、Chordにも範囲検索に対応できないという欠点があるわけで、Chord#やP-Ringが劣った構造化P2Pネットワークというわけではありません。それぞれの特性ということです。

カテゴリー: 研究活動 タグ: , パーマリンク