Hi Bruce, Have some answers now for some of your questions.
>Do you have experimental results of how this works in an >implementation? In particular, given the sensitivity of the load >distribution on delta, I'm wondering whether peers' different >perceptions of the size of the overlay creates its own load imbalance >factor. (may be able to do that quantitatively, I guess.) The load imbalance factor varies as a function of delta (delta is chosen as 1/Nest); as delta increases, the load imbalance reduces. More specifically, if the maximum factor error in estimating the network size is gamma_n, then it can be shown that with: alpha = 8 x (gamma_n/epsilon^2) x log N, the maximum share of a node is at most [(1+epsilon’)/(1-epsilon)^2] for large N (epsilon’ and epsilon > 0) when the node capacities are homogeneous. These results can be verified via simulations, and it can be shown that the load imbalance factor is at most 4 with alpha = 2 log N. >It also seems like the arrival of a new peer is going to cause a storm of data >migrations, and this would cause the overlay to suffer congestion >collapse in anything but a stable overlay. In the homogeneous case, when all nodes have equal capacity, the amount of data migrations when a new node joins/leaves would be of the order of O(1/N) which is the same as Chord. In the scenario when the nodes have unequal capacity, it can still be shown than the amount of data migration when a new node joins/leaves the overlay is of the order of O((1+epsilon)/N) as long as the errors in estimating the node capacity and network size are low. Some of these proofs are in the paper by godfrey et al cited in the draft. Thanks Saumitra -----Original Message----- From: Bruce Lowekamp [mailto:[email protected]] Sent: Monday, March 09, 2009 5:53 AM To: Das, Saumitra Cc: [email protected] Subject: Re: [P2PSIP] New Load balancing in RELOAD draft Saumitra, Very interesting draft. Do you have experimental results of how this works in an implementation? In particular, given the sensitivity of the load distribution on delta, I'm wondering whether peers' different perceptions of the size of the overlay creates its own load imbalance factor. (may be able to do that quantitatively, I guess.) It also seems like the arrival of a new peer is going to cause a storm of data migrations, and this would cause the overlay to suffer congestion collapse in anything but a stable overlay. Due to those concerns, and in particular because of the complexity of the implementation, I would oppose modifying the base dht algorithm in this manner. Not that load imbalance and handling peers with different resource levels isn't an issue with the base dht, but implementation complexity is already a serious issue that I remain concerned about. However, I believe a draft like this specifying an alternative dht algorithm is beneficial, and would support a further revision. Bruce On Tue, Mar 3, 2009 at 9:10 PM, Das, Saumitra <[email protected]> wrote: > Hi all, > > I just submitted a draft that proposes a load balancing solution for the > default DHT in RELOAD. Comments are appreciated. > > http://www.ietf.org/internet-drafts/draft-saumitra-p2psip-loadbalance-00.txt > > Best, > Saumitra > > > > > www.saumitra.info > _______________________________________________ > P2PSIP mailing list > [email protected] > https://www.ietf.org/mailman/listinfo/p2psip > _______________________________________________ P2PSIP mailing list [email protected] https://www.ietf.org/mailman/listinfo/p2psip
