Self-Tuning Distributed Hash Table (DHT) for REsource LOcation And Discovery (RELOAD)
draft-ietf-p2psip-self-tuning-15

An interesting, good extension based on what looks like lots of research.  I wish we had more drafts like this.

Thanks for addressing all my comments in version -13.  The one we're still talking about, now a non-blocking comment, is below:

1. In the Introduction:

   These
   characteristics are then used to configure the DHT in a static
   fashion by using fixed values for parameters such as the size of the
   successor set, size of the routing table, and rate of maintenance
   messages.  The problem with this approach is that it is not possible
   to achieve a low failure rate and a low communication overhead by
   using fixed parameters.  Instead, a better approach is to allow the
   system to take into account the evolution of network conditions and
   adapt to them.  This document extends the mandatory-to-implement
   chord-reload algorithm by making it self-tuning.  Two main advantages
   of self-tuning are that users no longer need to tune every DHT
   parameter correctly for a given operating environment and that the
   system adapts to changing operating conditions.

Does this mean that this self-tuning version is intended to be the way chord-reload is implemented in the future?  Or is it just meant to be an optional feature, which might or might not be implemented for chord-reload?  It seems that self-tuning doesn't work unless most peers support it and share the necessary information.

Reply from Jouni:
" The self-tuning version is an optional feature. But it needs to be supported by all the peers in the overlay. A RELOAD overlay can either choose to use chord-reload or the self-tuning version."

As a non-blocking comment, would it be useful to say what you just told me as part of the text I quote above?  I suggest this, which you may accept or decline as you see best (it also inserts a paragraph break for the long paragraph):

NEW
   These
   characteristics are then used to configure the DHT in a static
   fashion by using fixed values for parameters such as the size of the
   successor set, size of the routing table, and rate of maintenance
   messages.  The problem with this approach is that it is not possible
   to achieve a low failure rate and a low communication overhead by
   using fixed parameters.  Instead, a better approach is to allow the
   system to take into account the evolution of network conditions and
   adapt to them.

   This document extends the mandatory-to-implement chord-reload
   algorithm by making it self-tuning.  The self-tuning feature is
   optional. When it is used, it needs to be supported by all peers in
   the overlay.  Two main advantages of self-tuning are that users no
   longer need to tune every DHT parameter correctly for a given
   operating environment and that the system adapts to changing
   operating conditions.
END

Probably a very simple question from browsing through the doc (mainly due to my lack of RELOAD knowledge, combined with my laziness to review the 175 page RFC 6940)

   This document extends the mandatory-to-implement chord-reload
   algorithm by making it self-tuning.  The use of the self-tuning
   feature is optional.  However, when used, it needs to be supported by
   all peers in the RELOAD overlay network.

From an operational point of view, what is the mechanism to discover that all peers support this optional self-tuning feature?

Thanks for a nice write up of security considerations as well as addressing the questions from the SecDir review.

5.

Tilting at a windmill: The MUSTs in the section don't help the implementer:

s/MUST be used/is used
s/MUST maintain/maintains
s/MUST restart the time and carry out/restarts the timer and carries out

5.1

   Regardless of the type, all Update requests
   include an 'uptime' field.  Since the self-tuning extensions require
   information on the uptimes of peers in the routing table, the sender
   of an Update request MUST include its current uptime in seconds in
   the 'uptime' field.

I think in the newspaper business, this is called "burying the lede". The MUST is in the wrong place. What's important is that all Update requests MUST include an 'uptime' field. The MUST in the second sentence makes it confusing as to whether there are choices about other kinds of Updates or different format for time ("Are there other senders that don't have to use 'uptime'?" "Could they send minutes instead of seconds, and you can only use seconds in Updates? Is that why they're saying 'MUST'?" I suggest replacing with:

NEW
   The self-tuning extensions require information on the uptimes of
   peers in the routing table. The sender of an Update request includes
   its current uptime (in seconds) in the 'uptime' field. Regardless of
   the type, all Update requests MUST include an 'uptime' field.
END

Maybe I'm not understanding how this works, but the laste sentence of this section is confusing to me. Is the rule that if I've got enough space in my data structure for everything I got from my peer *and* what I had in there before, I keep everything? What if there's not enough space to keep everything? Do I trim what I had and add everything I got in the update, or do I trim what I got in the update?

5.2.

   Therefore, when the self-tuning
   mechanisms are used, each peer MUST send a periodic Update request
   only to its first predecessor and first successor on the Chord ring.
   
Again, potentially confusing because you've described the requirement backwards:

NEW
   Therefore, when the self-tuning mechanisms are used, each peer only
   sends a periodic Update request to its first predecessor and first
   successor on the Chord ring; it MUST NOT send Update requests to
   others.
END

In the last two paragraphs of this section, which of the MUSTs are actual requirements that an implementation needs to be aware of, and which are just statements of the way things are done in the protocol? In other words, why is the following not a reasonable replacement?

NEW
   The neighbor stabilization routine is executed when the
   stabilization timer fires.  To begin the neighbor stabilization
   routine, a peer sends an Update request to its first successor
   and its first predecessor.  The type of the Update request MUST be
   'neighbors'.  The Update request includes the successor and
   predecessor lists of the sender.  If a peer receiving such an Update
   request learns from the predecessor and successor lists included in
   the request that new peers can be included in its neighborhood set,
   it sends Attach requests to the new peers.

   After a new peer has been added to the predecessor or successor list,
   an Update request of type 'peer_ready' is sent to the new peer.
   This allows the new peer to insert the sender into its neighborhood
   set.
END

If the answer to the question, "Why does it say MUST?" is "Because if you don't do that, you're not doing the protocol", that's going to confuse implementers and can make for brittle code.

Please review 5.3, 5.4, 6.1, 6.3, 6.4, 6.5, 6.6 for similar uses.

6.2:

   The size of the successor list MUST be set to ceiling(log2(N)).  An
   implementation MAY place a lower limit on the size of the successor
   list.

MUST/MAY conflict. I think the first sentence should say "MUST be set to a maximum of".

In the last paragraph, change "MAY" to "can".

Thanks for producing this document. The static configuration seemed kind of lame when I was following RELOAD more closely - this seems like a much better idea!

Providing a way to estimate N seems like a fine improvement
over 6940. Good stuff.

- 5.6: What does a "better predecessor" mean here? Asking
because there's stuff you MUST do when you find one. 

- 5.6: I also wondered if there's any security issue
associated with having a MUST there - could a leaving node
use that to force its successor to talk to nodes the leaving
node has chosen for some nefarious purpose? (Apologies, I
forget RELOAD, which may already counter that;-)

In 6.2:

   A peer MAY choose to maintain a fixed-size predecessor list with only
   three entries as specified in RELOAD base.  However, it is
   RECOMMENDED that a peer maintains ceiling(log2(N)) predecessors.

I see that this text is the subject of negotiations with Pete, so I don't want to belabor it too much, but it seems to me that the only reason a peer would choose to do this would be that it didn't support self-tuning, since it seems that supporting a short predecessor list would make the node vulnerable to failures that the longer list is intended to prevent. The motivation for allowing this behavior is thus unclear to me. It may be that it's explained adequately and I missed it, but if not it might help to explain it here.

This is really cool work, and I greatly enjoyed reading it.   Thanks for documenting it!