Zenn
Open3

Pastryについて

dht
fogfog

概要

  • Pastryは、分散ハッシュテーブル (DHT) をベースにしたP2Pネットワークのルーティングプロトコル
  • マイクロソフト社とRice大学で開発された
  • 物理ネットワークを考慮したルーティングができるという特徴がある
  • ノードIDは決まった基数と桁数をもつ整数を使用する
  • 目的のIDを探索する方法
    • Plaxton　類似アルゴリズムTapestryがある
  • Node IDがd進数の場合、n行d列の表になる
    • i行目　→　自Node IDとi桁目までのプレフィックスが一致したNode IDが並ぶ
    • j列目　→　i+1桁目の数字がちょうどjとなるNode IDが並ぶ

メッセージを特定のNodeに送る方法

目的のNode IDとPrefixが最長一致する近隣Nodeを選ぶ
そのNodeに中継してもらう

Node IDについて

128 bit, 2^b進数の整数を用いる
bはデフォルトが4

表について

ルーティングテーブル, leaf set, neighborhood set　と呼ばれる補助的な表を用いる

  • leaf setとは？
    • 近傍にあるNodeIDを保持する表
      • 保持するNode IDの数は16が推奨値
    • 自分のNode IDより小さいか大きいかで分けて保持する
  • neighborhood setとは？
    • ネットワーク的に近い距離にあるNode IDを保持する
      • 保持するNode数は32が推奨値
fogfog

Scribeとは？

  • Pastry上に構築されたスケーラブルなアプリケーションレベルのマルチキャスト基盤
    https://www.freepastry.org/SCRIBE/default.htm
  • オンラインゲームにおいて関心管理を実現するために使用されていたりする
    • SimMud (MMOGのプロトタイプ) で使用されている