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
