Handling Churn in a DHT

p2p dht

「Handling Churn in a DHT」という論文のアブストラクトを読みました。

■著者
S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz Kubiatowicz.
■出典
In Proc. of USENIX Annual Technical Conference, 2004.

以下、アブストラクト原文です。

This paper addresses the problem of churn―the continuous process of node arrival and departure―in distributed hash tables (DHTs).
We argue that DHTs should perform lookups quickly and consistently under churn rates at least as high as those observed in deployed P2P systems such as Kazaa.
We then show through experiments on an emulated network that current DHT implementations cannot handle such churn rates.
Next, we identify and explore three factors affecting DHT performance under churn: reactive versus periodic failure recovery, message timeout calculation, and proximity neighbor selection.
We work in the context of a mature DHT implementation called Bamboo, using the ModelNet network emulator, which models in-network queuing, cross-traffic, and packet loss.
These factors are typically missing in earlier simulationbased DHT studies, and we show that careful attention to them in Bamboo’s design allows it to function effectively at churn rates at or higher than that observed in P2P file-sharing applications, while using lower maintenance bandwidth than other DHT implementations.

以下、僕によるへんてこな日本語訳です。最後の文がとっても長かったorz

本稿では、DHTにおけるノードの継続的な参加離脱を表す「churn」の問題を解決する。
我々は、DHTは、Kazaaなどの既に配備されたP2Pアプリケーションで見られるような高いChurn率においても、素早く一貫性を保ったLookupを行えるべきである、ということについて議論する。
それから我々は、エミュレーションによるネットワーク実験により、既存のDHT実装ではそのような高いChurn率に対応することができないことを示す。
次に、churn環境においてDHTに影響を与える3つの要因（定期的な障害回復に対する反作用、メッセージタイムアウト予測、近接ノードの選択）を特定・調査する。
我々は、十分に発達したDHT実装の一つであるBambooを利用する。
Bambooは、待ち行列、クロストラフィック（計測トラフィックに対して影響を与えるトラフィック）・パケットロスをモデル化するModelNetネットワークエミュレータを利用している。
これらの要因は、初期のシミュレーションベースのDHTに研究において典型的に書けているものである。
我々は、Bamboo DHTにでのそれらに対する慎重な注意が、Bamboo DHTを、P2Pファイル共有アプリケーションで見られる、あるいはそれよりもっと高いChurn率に効率的に機能できるようにすること示す。
（Bamboo DHTでは他のDHT実装より、狭い帯域しか使わないのにもかかわらず）

この論文を読んでわかったことは以下の通り。

  • DHTノードが継続的に参加・離脱を行うような状況を「churn」と表現する
  • （この論文の時点では）既存のDHT実装では高いChurn率（今既に存在するP2Pアプリケーションで観測されるような）に対応することができない。
  • Churn環境において考慮すべき要因は、reactive versus periodic failure recovery、message timeout calculation、近接ノードの選択手法である。
  • 初期のシミュレーションに基づいたDHT研究ではこれら３つの要因を考慮していない
  • 計測トラフィックに影響を与えるトラフィックを「クロストラフィック」と表現する

この論文を読んでわからなかったことは以下の通り。

  • reactive versus periodic failure recoveryって何だろう？
  • message timeout calculationって何だろう
  • Bamboo DHTにModelNetというネットワークエミュレータが含まれているんだろうか？

Churnが頻繁に発生する環境としては、モバイル環境や非常時接続環境などがありますでしょうか？
だとすると、僕の研究にも少し関わってきそうです。
Bamboo DHTの名前はものすごくよく聞くので、ちょっと勉強してみようかと思いまーす。