ルーティングテーブルの作り方

絶賛ルーティングテーブルの実装で困ってきたのでメモ代りに。

基本的にP2P型システムは各ノードがルーティングテーブルを持っている。
ハイブリッド型になるとそうでもないけど、Pure P2Pなら持ってる。当たり前だけど。
で、構造化はそのテーブルのルールが決まっていて非構造化は決まってない。
論文上では垣根があるけど、実装する時はあんまり考えないけどね。
と、いうことで、現在の実装は「構造化」＋「非構造化」みたいな感じ。
構造化P2Pとして持っておかないといけないエントリってのがある。
Chordみたいなリング型だと次のノード（Successor）だし、ツリーに作るのなら子とか親。
でも、それ以外のノード情報を知らなくてよいかっていうと、そうでもなくて、別にルーティングテーブルに書いておいて損は無い。
まぁ、Kademliaみたいな感じかな。研究してる内容上リングにしないとキツいのでリング構造を取ってるけど。

で、結局のところ実装では以下のようなルールを設けてる。

ルーティングテーブルはID順にソートして何でも突っ込む
ID=aなエントリのSuccessorは、テーブル内のaの次のIDとして取得する（JavaのNavigableMapとかなら楽勝）
とにかくそいつにForwardingする（実際にはSuccessorでなくても、そいつはより近いノードへとForwardingする）
自分は隣のノードを常に確認しておく

Chordのfinger tableはルーティングテーブルのエントリ数を制限してくれるっていう特徴があるんだけど、別に制限しなくていいやっていう思想だとこっちの方が実際にはルーティングが早い。
フルメッシュ状態だったらO(1)だからね。
1万ノードのエントリを持てないか、っていうと普通のPCなら持てるわけだし。

で、本題。

今の実装だと、送受信したノードの情報だけをルーティングテーブルに追加するんじゃなくて、
積極的に収集してる。
「お前のテーブル情報おせーて」
「いいよー。あげるー」
って感じで。
こういうことすると、Churnの頻度が高いときにルーティングテーブルがゴミだらけになる。
相手のテーブルにもゴミが紛れてるわけだし、それを貰ってホイホイ追加するとゴミが拡散してしまう。
実際の送受信に失敗したらエントリから消すんだけど、そのスパンをゴミの生成速度が上回ると全体が崩壊する。
まぁ、finger tableだろうとk-bucketだろうと同じだとは思うけど。（相手の生存を定期的に確認しないのであれば）
なので、そいつらの生存を確認する必要がある。
「俺の電話帳、大丈夫かな・・・。全員に電話してみよ」
っていう感じ。もしくは
「貰ったものの、このリストだいじょぶだろか・・・。全部に電話してみよ」
っていうのを定期的に行う。
つまり、

ルーティングテーブル内の掃除
貰ってきたルーティングテーブルの確認

ちなみに、そうなると1万エントリを持ってるってのは非現実的になってしまうわけで、やっぱり制限しないといけない。
制限したからといって確認しなくてもいいっていうわけじゃないので、やっぱりルーティングテーブル内のノードが生存しているかどうかを確認する必要がある。
で、結論から言うと、「評価実験に関しては」性善説を主張して、
貰ってきたルーティングテーブルに悪意はないものとする。
なので、貰ってきたテーブル情報はいつだって正しい。
と言う感じで、以下のルールを追加。

ルーティングテーブルのエントリにupdate timeを追加する
update time がしきい値より古い時間の場合は「他人に教えない」
定期的にテーブル内のノードにPINGメッセージを送信する（送信できたらupdateする）

とりあえず、これでどうにか凌げるかな・・・。
とはいえ、やっぱりPut・Get・Stabilize・その他の全てにおいて、相手のノードが死んでいることを前提に設計しないと、ある閾値を越えた瞬間にまったく動作しなくなる可能性がある。
おまけに、それら全てにいろいろと課題があるわけで。
例えば複製のPutによる耐Churn手法はConsistencyを下げるし、連続量の場合は難しいし。
論文のための評価実験とか、デモ用に使う分には問題ないんだけど、
実際のサービスデプロイはこの辺が非常に難しいんじゃないかな。
おまけに解いても論文にならんしねぇ。