Subject: Re: [P2PSIP] Review RELOAD Chord Spec chapter

From: "Cullen Jennings (fluffy)" <[email-masked]>
Date: Mon, 18 Jun 2012 21:37:08 +0000

switched to your suggested text in next version - thanks

On Apr 13, 2012, at 4:44 PM, Roland Bless wrote:

> Hi Cullen,
> 
> On 13.04.2012 22:49, Cullen Jennings wrote:
>> There is one comment inline in the email that I'd really appreciate
>> it if you could look at the change I made and see if it looks right
>> to you.
> 
> See comments below and inline.
> 
>> The places N was being used for a specific peer, I moved the N to X
>> to help clarify this.
> 
> looks ok.
> 
>>> p. 108: "   o  RELOAD uses a 128 bit hash instead of a 160 bit
>>> hash, as RELOAD is not designed to be used in networks with close
>>> to or more than 2^128 nodes (and it is hard to see how one would
>>> assemble such a network)."
>>> 
>>> The reasoning here is a little bit odd since the address space size
>>> is more related to how many objects one can store and the number of
>>> objects can very much larger than the number of actually existing
>>> nodes.
>> 
>> clarified. this is a bit complicated in Reload as the size the
>> Node-ID does not need to the be the same size as Resource-ID.
> 
> Change is ok, but for section 10 they actually have the same size (as probably for all structured KBR schemes).
>   "For this Chord based topology plugin, the size of the Resource-ID is
>   128 bits."
> 
>>> sec. 9.1:
>>> 
>>> minor: It would be helpful to describe that neighbor table and
>>> finger table only contain Node-IDs and that the mapping to locators
>>> is done by using the Attach procedure via the overlay (such entries
>>> will be kept in the Connection Table then?!).
>> added
> 
>   "The neighbor and finger tables have a logical Node-ID but the
>   actually mapping of a IP level addressing information to reach that
>   Node-ID is kept in the connection table."
> I'm not a native speaker, but I'd rather propose:
>   "The neighbor and finger table entries contain logical Node-IDs as
>   values but the actual mapping of an IP level addressing information
>   to reach that Node-ID is kept in the connection table."
> 
>>> " Fundamentally, the chord data structure ": this is somewhat
>>> confusing since it is not clear what you mean by "the chord data
>>> structure", because it was not defined. In this context it seems to
>>> mean the logical data structure across all nodes and not a
>>> particular data structure inside a single node. This may confuse
>>> readers since "the chord data structure" is nothing that actually
>>> needs to be implemented.
>> 
>> fixed
> 
> ok.
> 
>>> May 9.1 is also the section where you could state that N=2^128?
>> fixed
> 
> ok.
> 
>>> It should be clarified that this is only meant conceptually (one
>>> shouldn't implement it that way). "The routing table is
>>> conceptually the union of the neighbor table and the finger
>>> table."
>> 
>> fixed
> 
> ok.
> 
>>> sec. 9.4: typo old: "   success response.  It MUST then sends a
>>> Store request to its" new: "   success response.  It MUST then send
>>> a Store request to its"
>>> 
>> 
>> fixed
> 
> ok.
> 
>>> 9.5:  (p.110) "   4.  JP MUST enter all the peers it has contacted
>>> into its routing table." presumably only successfully contacted
>>> peers should be entered into the routing table, so maybe better: "
>>> 4.  JP MUST enter all the peers it has successfully contacted into
>>> its routing table."
>> 
>> fixed
> 
> ok.
> 
>>> p.111: " 7. ... AP can now forget any data which is assigned to JP
>>> and not AP." I think that this should be kept as long as AP is in
>>> the replica set (cf. 9.7.3)
>> 
>> fixed
> 
> ok.
> 
> 
>>> Major: "In order to set up its finger table entry for peer i, JP
>>> simply sends an Attach to peer (n+2^(128-i)." should be changed
>>> to: "In order to set up its finger table entry for peer at finger
>>> index i (i.e., finger[i]), JP simply sends an Attach to peer
>>> n+2^(127-i)." as finger[0] should point to node n+2^127, i.e.
>>> halfway round the ring, otherwise n+2^128-0 would point to n
>>> itself.
>> 
>> This is ( and related stuff in 9.7.4.2) is the change I really want
>> you to check.
> 
> New formulation with i'th finger is much better (though still a bit
> confusing since the finger[i] notation is mentioned in the overview and
> also the original Chord paper), but the particular sentence is not
> quite correct.
>  "In order to set up its i'th finger table entry for peer i, JP simply
>   sends an Attach to peer (n+2^(128-i)."
> The i'th finger this is usually not for peer i and there is a
> superfluous "(".
> So better correct to:
>  "In order to set up its i'th finger table entry, JP simply
>   sends an Attach to peer n+2^(128-i)."
> 
>> Look at how I clarified this and check you think I got it right. The
>> arrays start at 0 or 1 and been a point of confusion several times in
>> the past on this and it does not matter as long as it is clear. Check
>> with respect to section 9.7.4.2 too.
> 
> Yep. Clearer now.
> 
>>> sec. 9.7.1: p. 113, typo? old: "   If the neighbor failure effects
>>> the peer's range of responsible IDs," new: "   If the neighbor
>>> failure affects the peer's range of responsible IDs,"
>> 
>> fixed
> 
> ok.
> 
>>> sec. 9.7.3: change throughout the section N to n
>> 
>> Look at how I clarified this too.
> 
> looks good.
> 
>>> Major: sec. 9.7.4.2: "  entries in the finger table.  A finger
>>> table entry i is valid if it is in the range [ n+2^( 128-i ) ,
>>> n+2^( 128-(i-1) )-1 ].  Invalid" new: "  entries in the finger
>>> table.  A finger table entry at index i (finger[i]) is valid if it
>>> is in the range [ n+2^( 127-i ) , n+2^( 127-(i-1) )-1 ].  Invalid"
>>> 
>>> So finger[127] will be the successor.
>> 
>> check fix here too
> 
> That's ok now.
> 
> Regards,
> Roland
>

---

From: Roland Bless <[email-masked]>
Date: Tue, 19 Jun 2012 12:56:44 +0200

Hi Cullen,

> switched to your suggested text in next version - thanks

Ok, meanwhile I have some more comments, mostly clarification questions.
Two major comments though:

- The Connection Table is somewhat unclear.
  * Is it correct that it contains all nodes that are directly connected
    to a node, including those from the routing table?
  * Does it belong more to the topology plugin or to the forwarding &
link management?
  * In case one has to route a message towards a destination, should the
connection table be searched first (for an exact match), then the
neighbor set and then the finger table?

- It is unclear to me why (sec. 10.7.1, p.) the spec states:
  "peer MUST remove the entry from its neighbor table and replace it
   with the best match it has from the other peers in its routing table.
   If using reactive recovery, it then sends an immediate Update to all
   nodes in its Neighbor Table."
  so the peer replaces the failed entry with one of its fingers,
  which is maybe a poor choice, and sends this information to
  its neighbors. IMHO it makes much more sense to request routing
  information from the neighbors in order to get a better replacement
  for the lost peer, instead of "confusing" the neighbors with more
  inaccurate routing information.

Then some more clarifications/nits:
=====
Sec. 10.5 (p.110):
"The join process for a joining party (JP) with Node-ID n"
why joining _party_ if the terminology section mentions
Joining Peer and AP is the Admitting Peer?

=====
"1.  JP MUST connect to its chosen bootstrap node."
it is unclear what "connect" exactly means. This is actually
described in Sec. 11.5:
  "When contacting a bootstrap node, the joining node MUST first form
   the DTLS or TLS connection to the bootstrap node and then sends an
   Attach request over this connection with the destination Node-ID set
   to the joining node's Node-ID."
So my suggestion is to explain it a little but more or to put a forward
reference to section 11.5.

=====
"2.  JP SHOULD send an Attach request to the admitting peer (AP) for
       Node-ID n.  The "send_update" flag should be used to acquire the
       routing table for AP."
Here, it is not clear how the JP finds the AP. This is explained in
Section 12:
  "JP then sends an Attach through that
   peer to a resource ID of itself (JP).  It gets routed to the
   admitting peer (AP) because JP is not yet part of the overlay."
I suggest to change it to:
"2.  JP SHOULD send an Attach request to Node-ID n in order to contact
 the admitting peer (AP). The "send_update" flag should be used to
acquire the routing table for AP, i.e., it gets an UpdateReq message
after connecting (via TLS) to AP."
Question: should it be "acquire the routing table of AP" or "acquire the
routing table from AP"?

=====
"3.  JP SHOULD send Attach requests to initiate connections to each of
     the peers in the neighbor table as well as to the desired finger
     table entries.  Note that this does not populate their routing
      tables, but only their connection tables, so JP will not get
      messages that it is expected to route to other nodes."
here it is unclear that the Attach requests are sent via the AP
and what "desired" finger table entries means, e.g., in contrast to all?
=====

Sec. 10.7.:
" A peer MUST maintain an association (via Attach) to every member of
  its neighbor set. "
why only to the neighbor set and not the whole routing table?

=====
Sec. 10.7.1:
" Every time a connection to a peer in the neighbor table is lost (as
  determined by connectivity pings or the failure of some request),"
I think that "connectivity pings" means periodically sent Pings to all
members of the Connection Table by the Link Management Layer as
mentioned in sec. 6.5. A reference may help here.
However, I couldn't find out how often such "connectivity pings" should
be sent (the chord-ping-interval is only related to pinging finger table
entries).
=====
"If the neighbor failure effects the peer's range of responsible IDs,
 then the Update MUST be sent to all nodes in its Connection Table."
Why Connection Table? I think this must be Neighbor Table!

=====
Sec. 10.7.2.:
"If a finger table entry is found to have failed,"
how is it determined to have "failed"? 10.7.1 is only
related to neighbor failures...does the same definition
apply here?

=====
Sec. 10.7.3.:
"When a peer discovers that its range of responsible IDs have changed,
 it MUST send an Update to all entries in its connection table."
Why connection table? Why not neighbor or routing table?

=====
Sec. 10.7.4.1.:
"A peer MUST periodically send an Update request to every peer in its
 Connection Table."
Why connection table? Why not neighbor table?

=====
"A peer SHOULD randomly offset these Update requests so they do not
 occur all at once."
This is a little bit too imprecise.
How should this be done? A typical mechanism
is using a randomly chosen offset from an interval [0.5*Tp,1.5*Tp]
where Tp is the target period, cf.
S. Floyd, V. Jacobson, „The Synchronization of Periodic Routing
Messages“, IEEE/ACM Transactions on Networking, Vol. 2, No. 2, April,
1994, http://portal.acm.org/citation.cfm?id=187045

=====
Sec: 10.7.4.2.:
"A peer SHOULD NOT send Ping requests looking for new finger table
 entries more often than the configuration element "chord-ping-
 interval", which defaults to 3600 seconds (one per hour)."
This paragraph should probably moved some paragraphs down as it
has been stated yet that a peer should actually send Ping requests
at all (this is explained in the subsequent paragraphs).

=====
Sec 12:
- throughout the figures: "Update" should be "UpdateReq"
  and Attach should be AttachReq?

=====
Neighor Table and Connection Table are written sometimes
in lower case and sometimes in upper case style. I'm sure that
the RFC editor will ask for consistency in writing...

Regards,
 Roland