[P2P]オーバーレイネットワークでのマルチキャスト（案）

今まで分散ハッシュについていろいろ見てきたが、P2Pマルチキャストを上手く実現できないか、というのが筆者が最初から考えていたことであった。ちょっと考えてみたので（まだ全然アイデアベース）書いてみる。

サーバレスでマルチキャストなソフトとしてPeerCastがあって、その仕組みは既に下記のHPで紹介している。
初心者向けPeerCast解説

分散ハッシュの概念を一部取り入れてスケーラビリティの良いマルチキャストシステムをなんとかできないものか。。。

さて、P2Pマルチキャストといえば、ツリー構造の方が相性が良さそうだ。分散ハッシュでもP-Gridやkademliaがあるが、これらは節にノードがない。2分木の説明は以下のHPを参照
2分木

そこで、枝にもルートにも葉にもノードがあって、一意的なNode_IDを割り当てたいと考えている。Node_IDの割り当て方は次のとおり。今、Node_IDを6桁の3進法の整数とする。
(1)ルートのNode_IDは10000
(2)ルート直下の節については右側の節が11000（これをノード１とする）、左側の節が12000（これをノード２とする）
(3)ノード１の直下の右側の葉（または節）については11100、左側の葉（または節）については11200
(4)ノード２の直下の右側の葉（または枝）については12100、左側の葉（または節）については12200
......
つまり、ある節のノードについて、 Node_IDの一番桁が高い０の部分を直下の右側のノードは1,左側のノードは2にし、それ以下の桁の数は０にする。これで2分木の各ノードにユニークなNode_IDをつけることができた。

新しいノード（これをノードXとする）が2分木に参加するには、ノードXが6桁の乱数R（１００００＜R＜２００００）を振る。
ただし、乱数の各桁に０は含まれないこと。ノードXはルートから乱数Rに近いノードを2分木で探し、もっともRに近いノードに接続する。ただし、検索途中で２つに枝が分岐してないところがあれば、そこにノードを挿入し、枝を２つにさせる。
（※一番良い手段は葉の深さを計測し、一番深さの浅い葉に新しいノードを追加することだが、参加ノードが多いとこの計算が高速にできるか気になる。。。）

逆にノードが抜けた場合はやっかりである。今、ノードPが抜けた場合、直下のノードQ、Sのうちどちらかが「一時的」にノードPの代わりをする。今回はノードQがその代わりをするとしよう。ノードQは乱数R1を振るのだが、今ノードQの
Node_IDを122200とすると、122200＜R1とする。（ただし、R１は各桁に０を含まないとする。）これによって、R1がしめすNode_IDは必ずノードQ下部の葉を示す事になる。

2分木を使ってR1に一番近い葉を見つけ、そのノード（これをノードZとする）がノードPの代わりにする。ノードZはノードPのNode_IDを引き継ぐ。このときノードQはノードPの代わりをやめる。こうすれば、ツリー構造はネットワークでノードが離脱してもほぼ同じで、複雑なNode_IDの変換をする必要はない。

ルーティングテーブルは最低で自分の直上と直下のノードだけ知ればよい。もちろん、耐障害性を高めるのであれば、もっと大きなルーティングテーブルを持てばよい。

オーバレイネットワークでのP2Pマルチキャストについて、アイデアベースだが簡単に紹介した。ただし、これらの技法については帯域や遅延の影響は全く無視している。いずれにせよ、ツリー構造がマルチキャストには非常に有効なので、このような方法が今後考察されるかもしれない。皆様のアイデア、お待ちしています♪