Subject: [P2PSIP] Review RELOAD Chord Spec chapter

From: Roland Bless <[email-masked]>
Date: Fri, 13 Apr 2012 19:25:08 +0200

Hi,

as promised at the last IETF meeting I reviewed the
chapter that Cullen asked for (was chapter 9 in draft-20,
and is chapter 10 in draft-21). I didn't actually
implement it yet, however, I wanted to share my preliminary
findings.

Overall, the description seems to be detailed enough to implement it,
though some nits should be corrected. Maybe I'll provide an update in 
the next few days.

The variable N is used inconsistently. It's not clear whether
it is denoting the number of peers, objects or N=2^128, sometimes
it is used as peer number (e.g., 10.7.3. "When a peer, N,"). It is
easier to follow the description if this is used consistently.

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.

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?!).

" 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.

May 9.1 is also the section where you could state that N=2^128?

sec. 9.3:
    "The routing table is the union of the neighbor table and the finger
    table."

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."

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"

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."
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)

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.

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,"

sec. 9.7.3:
change throughout the section N to n

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.

Regards,
  Roland

---

From: Cullen Jennings <[email-masked]>
Date: Fri, 13 Apr 2012 14:49:12 -0600

Thanks for the review, comments inline but all of theses changes look good and I have made all of them. 

I did not submit a new version to the drafts directory ytet but I checked in the changes and you can see the diff at 

http://svn.resiprocate.org/rep/ietf-drafts/p2psip/draft-ietf-p2psip-base.diff.html

or get the new version of the draft at

http://svn.resiprocate.org/rep/ietf-drafts/p2psip/draft-ietf-p2psip-base.txt

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. 

Once again, thanks for the careful review of this. 

On Apr 13, 2012, at 11:25 AM, Roland Bless wrote:

> though some nits should be corrected. Maybe I'll provide an update in the next few days.
> 
> 

The places N was being used for a specific peer, I moved the N to X to help clarify this. 

> number of objects can very much larger than the number of

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. 

> Connection Table then?!).
added

> is nothing that actually needs to be implemented.

fixed 

> May 9.1 is also the section where you could state that N=2^128?
fixed

>   "The routing table is conceptually the union of the neighbor table and

fixed

> "   success response.  It MUST then send a Store request to its"

fixed 

> "   4.  JP MUST enter all the peers it has successfully contacted into

fixed

> I think that this should be kept as long as AP is in the replica set

fixed

> 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. 

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. 

> "   If the neighbor failure affects the peer's range of responsible IDs,"

fixed

> change throughout the section N to n

Look at how I clarified this too. 

> "  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"
> 

check fix here too 

> 
> Regards,
> Roland
> 
> _______________________________________________
> P2PSIP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/p2psip

---

From: Roland Bless <[email-masked]>
Date: Sat, 14 Apr 2012 00:44:18 +0200

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

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?

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.
>

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
>

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"
>>

That's ok now.

Regards,
  Roland