バトンオーバーレイ

BATON ( Ballanced Tree Overlay Network )は、ピアツーピア(P2P) システム用に設計された分散ツリー構造です。分散ハッシュ テーブルを使用する他のオーバーレイとは異なり、BATON は分散ツリーでピアを編成して範囲検索を容易にします。BATON はAVL ツリーと同様にバランスの取れたツリーの高さを維持することを目指しており、その結果、完全一致検索と範囲検索のクエリ、および更新操作 (結合/離脱) が制限されます。 ${\displaystyle O(\log N)}$

BATON はバイナリ ツリーです。各ツリー レベルでは、ノードはツリー内の位置によって名前が付けられます。

BATON の各ノードは、次の 4 種類のリンクを保持します。

1. 親ノードへのリンク（ルートでない場合）
2. 最大2つの子ノードをリンクする
3. 左と右の隣接ノードへのリンク
4. 左ルーティングテーブル（LRT）と右ルーティングテーブル（RRT）に保持されている隣接ノードを選択するためのリンク。これらを組み合わせてルーティングテーブルが作成されます。${\displaystyle RT:={LRT}\cup {RRT}}$

どのノードのレベルも、その親のレベルより 1 つ高くなります。ルートはレベル 0 にあります。位置 のノードの場合、有効な については位置 のノードで左側のルーティング テーブルを埋め、有効な については位置 のノードで右側のルーティング テーブルを埋めます。ルーティング テーブルの構造は、Chord のフィンガー テーブルと少し似ています。 ${\displaystyle p}$${\displaystyle p-2^{x}}$${\displaystyle x\geq 0}$${\displaystyle p+2^{y}}$${\displaystyle y\geq 0}$

したがって、例の構造によれば、ノード2:1は、

• 1:0（親）
• 3:2（子供）
• 0:0と3:2 (隣接)
• 2:0、2 : 2、2 : 3（近隣）

高さバランス

BATON は、ツリー内の任意のノードの 2 つのサブツリーの高さが最大 ​​1 だけ異なる場合にのみバランスが取れていると見なされます。高さバランスの制約に違反していることをいずれかのノードが検出すると、ツリーのバランスを保つために再構築プロセスが開始されます。

BATON で新しいノードがネットワークに参加しようとすると、その参加要求は常にリーフ ノードに転送されます。リーフ ノードは、ルーティング テーブルがいっぱいかどうかを確認します。テーブルがいっぱいの場合、そのレベルにノードがいっぱいであることを意味し、リーフ ノードは新しいノードを子として受け入れて、新しいレベルのノードを作成できます。テーブルがいっぱいでない場合、リーフ ノードは新しいノードを転送して、空いている位置の 1 つを引き継ぐ必要があります。

一方、ノードがネットワークから離脱する場合、親ノード、子ノード、隣接ノード、ルーティングノードのルーティングテーブルを更新する必要があります。離脱するノードがリーフノードであれば、安全にネットワークから離脱できます。ただし、リーフノードでない場合は、その位置を置き換えるリーフノードを見つける必要があります。

BATON では、各ノードは連続したキー空間を維持します。新しいノードが子として参加すると、ノードは空間を分割し、その半分を子に割り当てます。この分割方法により、ツリーを順番に移動する場合には、ツリーを昇順でトラバースできます。これが、BATON が範囲クエリをサポートする理由です。

範囲クエリ q を実行するために、BATON は最初に左の境界 q.low を見つけます。次に、検索プロセスはツリーを順番に (隣接リンクによって) 移動し、上限 q.up に到達します。単一のキーを見つけるために、BATON はChordと同様のルーティング戦略を使用します。要求は最初に、キーをオーバーシュートしない最も遠いルーティング ノードにルーティングされます。そのようなルーティング ノードが存在しない場合は、親リンク、子リンク、または隣接リンクが使用されます。

ノード x が参加ノード y を子として受け入れ、ツリーのバランスが崩れていることを検出すると、再構築プロセスを開始します。一般性を失わずに、この再構築が右方向に向かっていると仮定しましょう。y が x の左の子として参加するとします。システムのバランスを再調整するために、x は y にその位置を置き換えるように通知し、右隣のノード z に x が z の位置を置き換えることを通知します。次に、Z は右隣のノード t をチェックして、その左の子が空かどうかを確認します。空で、t に子を追加してもツリーのバランスに影響しない場合は、z は t の左の子の位置を新しい位置として取得し、再構築プロセスは停止します。t の左の子がいっぱいであるか、t がバランス プロパティに違反することなく x を左の子として受け入れることができない場合、z は t の位置を占有し、t は右隣のノードに進むことによって自分自身の新しい位置を見つける必要があります。

BATONは2種類の負荷分散戦略を採用しています。ノードnが過負荷状態を検出すると、

1. 左または右の隣接ノードの負荷が軽い場合、ノードは負荷を軽減するために隣接ノードにデータを転送します。
2. 隣接するノードが負荷を共有できない場合、ノードはプロセスを呼び出して、ネットワーク内でランダムに負荷の軽いノードを探します。負荷の軽いノードは元の位置を離れ、過負荷のノードの子として参加し、そのデータの一部を引き継ぎます。再構築プロセスが呼び出される場合があります。

• BATON* - バランス型 m-ary ツリー オーバーレイ ネットワーク: 効率性、フォールト トレランス、負荷分散のための追加リンクを備えた、BATON の高さバランス型 m-ary 検索ツリー拡張。
• nBATON* - null-BAlanced m-ary Tree Overlay Network: 必要なルーティング ホップに関して最大​​ 50% 優れたパフォーマンスを備えた、BATON* の null-balanced m-ary 検索ツリー拡張。

• コード
• できる
• ペストリー

• HV Jagadish、Beng Chin Ooi、Quang Hieu Vu (2005)。「BATON: ピアツーピア ネットワークのバランスの取れたツリー構造」(PDF)。ノルウェー、トロンハイムで開催された第 31 回国際大規模データベース会議の議事録。661 ～ 672 ページ。ISBN 1-59593-154-6。

• HV Jagadish、Beng Chin Ooi、Quang Hieu Vu、Rong Zhang、Aoying Zhou (2006)。「VBI-Tree: 多次元インデックス スキームをサポートするピアツーピア フレームワーク」(PDF)。第 22 回国際データ エンジニアリング会議の議事録。p. 34。ISBN 0-7695-2570-9。
• HV Jagadish、Beng Chin Ooi、Kian-Lee Tan、Quang Hieu Vu、Rong Zhang (2006)。「マルチウェイ ツリー構造によるピアツーピア ネットワークの検索の高速化」( PDF)。2006 ACM SIGMOD 国際データ管理会議の議事録。pp. 1–12。ISBN 1-59593-434-0。
• Shiyuan Wang、Beng Chin Ooi、Tung, AKH、Lizhen Xu (2007)。「ピアツーピア ネットワークでの効率的な Skyline クエリ処理」(PDF)。第 22 回国際データ エンジニアリング会議の議事録。pp. 1126–1135。ISBN 978-1-4244-0803-0。
• A. Gonzalez-Beltran、P. Milligan、P. Sage (2008)。「スキップ ツリー グラフ上の範囲クエリ」(PDF)。Computer Communications。pp . 358–374。ISSN 0140-3664  。
• Peter Detzner、Jana Gödeke、Steffen Bondorf (2021)。「ツリー構造のP2Pオーバーレイにおける低コスト検索：ヌルバランスの利点」（リンク）。第46回ローカルコンピュータネットワーク会議（LCN）。pp. 358–374。

• BestPeerプロジェクトのウェブサイト