I think it is fairly clear that mandatory-to-implement overlay algorithm
must have a fixed length node-ID; otherwise, interoperability is a
non-starter.
Unstructured overlays do not use a hash function to map resources to
nodes, so node-ID length is a non-issue; it simply has to be unique.
DHTs, however, use a hash function to map resources to nodes, so node-ID
length and hash function output length becomes an issue. The confusion
lies in the ability to use a hash function that emits a greater than
128-bit value, and then mapping it to the 128-bit node-ID by dropping the
most significant bits. The argument is that by dropping the MSBs, we
likely loose the randomness guarantees which are necessary from the load
balancing perspective. Thus, we are restricted to using a 128-bit hash
function for all DHTs (Kademlia, Pastry, CAN etc). Restricting the use of
hash functions for all DHTs is not necessarily ideal from the viewpoint of
future proofing.
-s
On Wed, 17 Feb 2010, Cullen Jennings wrote:
On Dec 10, 2009, at 2:30 PM, Roni Even wrote:
According to section 1 Reload is based on the concepts introduced in
ietf-p2psip-concepts. The concept draft is currently expired and I noticed
some contradictions between the two drafts. I think that the reload draft
should progress with the concept draft.
According to the concepts draft "The P2PSIP WG will not standardize how the
peer-ID and the credentials are obtained, but merely standardize at least
one acceptable format for each. To ensure interoperability, it is expected
that at least one of these formats will be specified as
"mandatory-to-implement"." According to RELOAD the node-id is mandated as a
128 bit value. According to the concept draft it can be as mandatory to
implement format but others should be allowed. I also think that section
5.4.1 allows for different node-id length (see "o The length of the
Resource-IDs and Node-IDs. For DHTs, the hash algorithm to compute the hash
of an identifier."
Sounds like the concepts draft needs some work.
On the one topic of node-id being fixed length or variable length, we discussed
the length of resource-id and and node-id a lot in the past. I have never seen
someone raise the argument of we need Node-ID short than 128 bits. Several
times people have raised the issue of we need node-id to be longer than 128.
Specifically it is generally requested that they could be 160 bits because the
output of SHA-1 is 160 bits. This request is generally fairly confused in that
it's actually the Resource-Id they are confusing with the Node-ID. IN reload
the resource-id are variable length and could be 160 bits. This was put in
largely because Salman argued strongly that this would be needed to support
unstructured overlays. The only time I can imagine that you could possible need
more than 128 bits in a Node-ID is when you assign node-id randomly and you
have more than approximately 2^64 nodes in a single DHT or you assign node-id
non randomly and you have more than 2^128 nodes in a rin!
g.
I don't think anyone is arguing either of these are problems and I have not
heard any other technical argument for making these larger. There are a bunch
of advantages of fixed size but ignoring all that, it does not even seem like
it's worth discussing if there is no technical reason to move to larger
node-ids.
Good catch on section 5.4.1. Fixed that typo - thanks.
Cullen Jennings
For corporate legal information go to:
http://www.cisco.com/web/about/doing_business/legal/cri/index.html
_______________________________________________
P2PSIP mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/p2psip
_______________________________________________
P2PSIP mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/p2psip
