分散ハッシュテーブル(Kademlia) churn下での実験

ノードの生存時間は1/5120=λとする指数分布に従って，ランダムに発生させgetの成功回数と，RTTを測定しました．なお，この場合，平均生存時間は5120秒となります．(c.f. "A Measurement Study of Peer-to-Peer File Sharing Systems", Stefan Saroiu, P. Krishna Gummandi, Steven D. Gribble, 2002)

測定マシンは，2GHz Core Duo，2GB RAM, MacOS X 10.4.11 Tigerです．

ノード数	get成功回数	get失敗回数	平均RTT[s]
5000	930	70	0.17519
4000	981	19	0.16227
3000	968	32	0.13779
2000	976	24	0.12875
1000	979	21	0.14112

また，Kademliaはルックアップ等でルーティングテーブルを更新するため，事前にルーティングテーブルを更新するような操作を行ってから，同じように測定してみました（2回getして2回目を測定）．

ノード数	get成功回数	get失敗回数	平均RTT[s]
5000	930	13	0.05952
4000	999	1	0.06782
3000	992	8	0.08494
2000	999	1	0.13705
1000	995	5	0.04849

という感じで，頻繁に使うほどルーティングテーブルがアップデートされ，get成功率が高くなるようです．また，一時的にデータが取得できなくても，一定時間後にはほとんど確実にデータを取得できます．これは，データを定期的に再配置しているからです．

5000ノードの時に性能ががくんと落ちていますが，これはおそらく，CPUリソースが足りないからだと思われます．topで確認しつつ実験を行ってみると，5000ノードの時は，CPU idleが0%とかが頻出していたので，リクエストがタイムアウトして，get失敗したのではないかと思われます．