Relating to Pastry, specifically FreePastry:
- We haven't had a neighbor-set in years, just the routing table and leafset.
- In-degree skew is only caused by Proximity Neighbor Selection (PNS) and
nothing else.
Thus if Pastry and Chord are deployed in the same physical network with PNS,
they will have very similar indegree distributions.
Thanks!
-Jeff
------------------------------------------------------------------------
Subject:
Re: [p2p-hackers] indegree and node distribution
From:
Tien Tuan Anh Dinh <[EMAIL PROTECTED]>
Date:
Thu, 08 Mar 2007 13:11:22 +0000
To:
theory and practice of decentralized computer networks
<[email protected]>
To:
theory and practice of decentralized computer networks
<[email protected]>
It is true that the hash function will not distribute node ID evenly,
but in term of in-degree, it should not be very skewed. And it seems
more imbalanced in Pastry than in Chord, because of it maintaining a
leafset + neighborset in addition to routing table.
This problem sounds like a minor load-balancing problems, but at node
level. One solution that i have read is to use Virtual Servers, i.e: one
real node maybe responsible for several virtual nodes in the overlay,
depending on its capacity.
Cyrus Hall wrote:
I don't have a paper to point you at, but my intuition is that all
geometrically constrained DHTs have irregular in-degrees. Even though
nodes are "uniform random," there are local differences in distribution,
which lead to some nodes being selected more than others, as they are
responsible for more space. In some simulations we've seen up to an
order of magnitude difference for in-degree. In general (although not a
rule), the more constrained the node-selection, the more skewed the
in-degree.
This probably isn't much of a problem for an Internet over-lay, but for
a DHT on a mobile or resource limited platform it can become an issue.
One of our current projects is to create DHTs with greatly relaxed
geometries, which allow individual nodes to have greater control over
their in-degree.
Cyrus Hall
University of Lugano
On Thu, 2007-03-08 at 15:29 +1100, John Allan Casey wrote:
Hi All, does any one have any pointers to how the in-degree of various
DHTs like Chord and Pastry is characterized? I think Chord will likely
have a uniform in-degree whereas nodes in Pastry will most likely be
skewed? probably because of proximity neighbor selection. So what sort of
distribution can be used to characterize the in-degree of nodes in Pastry?
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
