なぜペストリーDHTが効率的なルーティングを持っているのですか

Question

最近ペストリーDHTに関するいくつかの記事を読んでいます。ペストリーDHTには効率的なルーティングがあります。ペーストリーのルーティングでは、各ステップのノードIDは、 IDはランダムに割り当てられているので、宛先に到着する前にメッセージが非常に長い距離移動し、結果としてルーティングが効率的でない可能性があります。

たとえば、Pastryルーティング、宛先ノードIDはd467c4、開始ノードIDは65a1fc、ルーティングプロセスは65a1fc-> d13da3-> d4213f-> d462ba-> d46702-> d467c4です。このルーティング上のノードは世界中にあります（IDはランダムに割り当てられます）。メッセージは最終ノードに到着する前に世界中を移動します。このルーティングは効率的ではありません。

なぜPastry DHTに効率的なルーティングがあるのですか？

Answer 1

あなたの効率の概念によります。オーバレイネットワークを設計する場合、第1の関心事は、通常、ネットワークサイズに対するホップの総数を制限することである。言い換えれば、nノードが存在しない場合、O（n）ルートの場合は、O（ログn）の経路がネットワーク全体を意識することなく達成できるため、通常の目標です。

リンクに沿ったレイテンシ、パスコスト、または最小帯域幅に関するルート長は、第2位の懸案事項です。これは、ホップ長が最適化された後に、ある種の地域認識またはクラスタリングを追加することによって達成されることが多い。

ペストリーはホップメトリックに対して効率的です。