コンテンツアドレスネットワーク

コンテンツアドレス ネットワーク( CAN ) は、インターネットのような規模でハッシュ テーブル機能を提供する分散型の非中央集権型P2Pインフラストラクチャです。CAN は、 Chord、Pastry、Tapestryと同時に導入された、最初の 4 つの分散ハッシュ テーブル提案の 1 つです。

他の分散ハッシュテーブルと同様に、CANはスケーラブル、フォールトトレラント、自己組織化を実現するように設計されています。アーキテクチャ設計は、マルチトーラス上のオーバーレイネットワークの一種である仮想多次元直交 座標空間です。このn次元座標空間は仮想論理アドレスであり、ノードの物理的な場所や物理的な接続とは完全に独立しています。空間内のポイントは座標で識別されます。座標空間全体はシステム内のすべてのノード間で動的に分割され、すべてのノードが全体の空間内に少なくとも1つの異なるゾーンを持ちます。^[1]

CANノードは、各隣接ノードのIPアドレスと仮想座標ゾーンを保持するルーティングテーブルを維持します。ノードは、座標空間内の宛先ポイントに向けてメッセージをルーティングします。ノードはまず、宛先ポイントに最も近い隣接ゾーンを決定し、次にルーティングテーブルを介してそのゾーンのノードのIPアドレスを検索します。^[1]

CAN に参加するには、参加ノードは次の条件を満たす必要があります。

1. オーバーレイ ネットワーク内にすでに存在するノードを検索します。
2. 分割できるゾーンを特定する
3. 新しく分割されたゾーンに隣接するノードのルーティングテーブルを更新します。^[1]

オーバーレイネットワークにすでに存在するノードを見つけるために、ブートストラップノードを使用して、現在オーバーレイネットワークに存在するノードのIPアドレスを参加ノードに通知することができます。^[1]

参加ノードは、CAN にすでに存在するノードの IP アドレスを受信すると、自身のゾーンを識別しようとします。参加ノードは座標空間内のポイントをランダムに選択し、ランダム ポイント宛てに参加要求を受信した IP アドレスの 1 つに送信します。オーバーレイ ネットワークにすでに存在するノードは、ゾーンから IP へのルーティング テーブルを介して参加要求を正しいデバイスにルーティングします。宛先ポイントのゾーンを管理するノードが参加要求を受信すると、ゾーンを半分に分割し、最初の半分を自身に割り当て、残りの半分を参加ノードに割り当てることで、参加要求に応じることができます。参加要求に応じない場合、参加ノードは座標空間内のランダム ポイントを選択し、これらのランダム ポイント宛てに参加要求を送信し続け、ネットワークへの参加に成功します。^[1]

ゾーンの分割と割り当てが完了すると、隣接するノードは2つの新しいゾーンの座標と対応するIPアドレスで更新されます。ルーティングテーブルが更新され、更新内容がネットワーク全体に伝播されます。^[1]

ノードの離脱を処理するために、CANは

1. ノードが出発していることを識別する
2. 離脱ノードのゾーンを隣接ノードに統合または引き継ぐ
3. ネットワーク全体のルーティングテーブルを更新する。^[1]

ノードの離脱の検出は、たとえば、近隣ノード間でルーティング テーブル情報を定期的にブロードキャストするハートビート メッセージを介して行うことができます。近隣ノードからの沈黙が一定期間続くと、その近隣ノードは障害が発生したと判断され、離脱ノードと見なされます。^[1] または、自発的に離脱するノードが、そのような通知を近隣ノードにブロードキャストすることもできます。

離脱ノードが特定された後、そのゾーンはマージされるか引き継がれる必要があります。まず、離脱ノードのゾーンが分析され、隣接ノードのゾーンが離脱ノードのゾーンとマージされて有効なゾーンを形成できるかどうかが判断されます。たとえば、2D 座標空間のゾーンは正方形または長方形のいずれかでなければならず、L 字型であってはなりません。検証テストでは、すべての隣接ゾーンを循環して、マージが成功するかどうかが判断されます。潜在的なマージの 1 つが有効なマージであると判断された場合、ゾーンはマージされます。潜在的なマージのいずれも有効ではないと判断された場合、最小のゾーンを持つ隣接ノードが離脱ノードのゾーンの制御を引き継ぎます。^[1] 引き継ぎ後、引き継ぎノードは、追加で制御するゾーンをそれぞれの隣接ゾーンと定期的にマージしようとします。

マージが成功すると、隣接ゾーンのノードのルーティング テーブルが更新され、マージが反映されます。ネットワークは、マージ後にオーバーレイ ネットワークのサブセクションを 1 つのゾーンとして認識し、すべてのルーティング処理をこの考え方で処理します。テイクオーバーを実行するには、テイクオーバー ノードが隣接ゾーンのノードのルーティング テーブルを更新し、いずれかのゾーンへの要求がテイクオーバー ノードに解決されるようにします。そのため、ネットワークはオーバーレイ ネットワークのサブセクションを 2 つの個別のゾーンとして認識し、すべてのルーティング処理をこの考え方で処理します。

シルヴィア・ラトナサミー、ポール・フランシス、マーク・ハンドリー、リチャード・カープ、スコット・シェンカー

• コード
• コンテンツアドレス可能ストレージ
• ペストリー
• タペストリー