[P2PSIP] Answers to feedback on the Self-tuning DHT draft

[Jouni Mäenpää <[e-mail]>]

Hi,

We presented the draft "Self-tuning DHT for RELOAD"
(http://tools.ietf.org/id/draft-maenpaa-p2psip-self-tuning-00.txt) in
the P2PSIP session of the previous IETF meeting in San Francisco. We
would now like to address the feedback we received during the presentation.

First, it was asked whether the self-tuning algorithm could be made more
compatible with the algorithm in RELOAD base. The self-tuning draft
follows closely the original Chord DHT specified in [Stoica 2003]
whereas the Chord algorithm specified in the RELOAD base draft is a
modified version of the original Chord algorithm. The major difference
is that the algorithm in RELOAD base uses reactive stabilization for the
neighborhood set (neighborhood set consists of the successors and
predecessors of a peer on the Chord ring) whereas the self-tuning draft
uses periodic stabilization. To make the self-tuning algorithm and the
algorithm in RELOAD base more compatible, we would either need to make
the self tuning algorithm use reactive stabilization or make the
algorithm in RELOAD base use periodic stabilization. If the self-tuning
algorithm was modified to use reactive stabilization, then it would no
longer be able to handle large-scale and high-churn overlays, as was
discussed above. Consequently, keeping both approaches as two different
topology plugins seems to make sense.

There was also some discussion on reactive versus periodic
stabilization. It has been shown in [Rhea 2004] that reactive
stabilization works well for small overlays and moderate churn. However,
in large-scale (e.g., 1000 peers or more) or high-churn overlays,
reactive stabilization runs the risk of creating a positive feedback
cycle, which can eventually result in congestion collapse.  In [Rhea
2004], it is shown that a 1000-peer overlay under churn uses
significantly less bandwidth and has lower latencies when periodic
stabilization is used than when reactive stabilization is used. Although
in the experiments carried out in [Rhea 2004], reactive stabilization
performed well when there was no churn, its bandwidth use was observed
to jump dramatically under churn.  At higher churn rates and larger
scale overlays, periodic stabilization uses less bandwidth and the
resulting lower contention for the network leads to lower latencies. For
this reason, most DHTs use periodic stabilization.

Third, there was a question whether introducing self-tuning behavior
will make the overlay unstable, since there may be a delay between
getting information from the overlay and adapting the DHT parameters. In
a self-tuning DHT, each peer collects statistical data from the overlay
and then uses this data to adjust the DHT parameters. Each peer
maintains of history of the collected data (e.g., a failure history).
Thus, the best trade-off between accuracy and responsiveness to changed
network conditions can be achieved by selecting an appropriate size for
the history.  Guidelines for choosing an appropriate size for the
history are given for instance in [Ghinita 2006, Mahajan 2003]. A DHT
becomes unstable if peers use DHT parameters that are inappropriate for
the prevailing operating conditions. Self-tuning behavior does not make
a DHT unstable since peers try to adapt the DHT parameters when the
operating conditions change. It has been shown that a self-tuning DHT
outperforms a DHT using a fixed stabilization interval [Ghinita 2006].

Fourth, there was a question on how well the self-tuning algorithm
performs in a small-scale overlay. As described in [Rhea 2004], if a
fixed stabilization interval is used, periodic stabilization is wasteful
in a low-churn small-scale network because if configured
inappropriately, it executes the stabilization routines more often than
is actually necessary. However, a self-tuning DHT avoids this problem
since it adjust the stabilization interval by making it longer if it
observes that the churn rate becomes lower. Because of this, a
self-tuning DHT can perform well also in low-churn small-scale overlays.

Fifth, there was a question on how well the algorithm tolerates churn.
As explained above, a DHT using reactive stabilization can overload the
network with messages under high churn rates. On the other hand, a DHT
with periodic stabilization uses a fixed stabilization interval. The
problem with this is that if the churn rate becomes higher than
expected, the stabilization interval may be too infrequent and as a
result, the network becomes partitioned. The idea in a self-tuning DHT
is that if the churn rate is observed to increase, peers will adjust the
stabilization interval by making it shorter. This allows a self-tuning
DHT to tolerate high churn rates.

Finally, someone asked what happens if different peers have different
views of the network conditions. Each peer in the DHT uses only local
information to adjust the stabilization interval. A peer adjusts the
stabilization interval based on the failures it detects in its routing
table and also based on the session times of peers in the routing table.
Thus, each peer attempts to adjust the stabilization interval so that it
is appropriate for the observed network conditions. Because only local
information is used, each peer may not necessarily end up using exactly
the same stabilization interval. This does not matter, however, because
every peer uses a stabilization interval that is sufficient for the
local conditions.

Due to the length of this email, people answering something about one
topic should probably change the subject and start a new thread.

Best Regards,
Jouni Maenpaa

[Ghinita 2006] Ghinita, G. and Y. Teo, "An adaptive stabilization
framework for distributed hash tables", 20th International Parallel and
Distributed Processing Symposium April 2006.

[Mahajan 2003] Mahajan, R., Castro, M., and A. Rowstron, "Controlling
the cost of reliability in peer-to-peer overlays", In Proceedings of the
2nd International Workshop on Peer-to-Peer Systems Feb. 2003.

[Rhea 2004] Rhea, S., Geels, D., Roscoe, T., and J. Kubiatowicz,
"Handling churn in a DHT", In Proc. of the USENIX Annual Techincal
Conference June 2004.

[Stoica 2003] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D.,
Kaashoek, M., Dabek, F., and H. Balakrishnan, "Chord: A Scalable
Peer-to-peer Lookup Service for Internet Applications", IEEE/ACM
Transactions on Networking Volume 11, Issue 1, 17-32, Feb 2003.