Subject: [P2PSIP] New Load balancing in RELOAD draft

From: "Das, Saumitra" <[email-masked]>
Date: Tue, 3 Mar 2009 17:10:51 -0800

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

---

From: [email-masked]
Date: Wed, 4 Mar 2009 14:58:51 +0800

I have read your article, and agree that load balancing is a key issue 
especially when we deploy the backend server systems built by p2p 
technology.
Some questions following:
1)Does the finger table only include the primary virtual node ID?
2)How to change the estimated N parameter  and keep the services 
non-stopping? Supposing that it has been far away from the actual network 
scale.
3)Could the imbalance factor be reduced further?

Russell Wang

[email-masked] 写于 2009-03-04 09:10:51:

> Hi all,
> 
> I just submitted a draft that proposes a load balancing solution for
> the default DHT in RELOAD. Comments are appreciated.
> 
> 

> 
> Best,
> Saumitra
> 
> 
> 
> 
> www.saumitra.info 
> _______________________________________________
> P2PSIP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/p2psip

--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail is solely property of the sender's organization. This mail communication is confidential. Recipients named above are obligated to maintain secrecy and are not permitted to disclose the contents of this communication to others.
This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify the originator of the message. Any views expressed in this message are those of the individual sender.
This message has been scanned for viruses and Spam by ZTE Anti-Spam system.

---

From: "Das, Saumitra" <[email-masked]>
Date: Fri, 6 Mar 2009 12:57:59 -0800

Hi Russell,

  Thanks for going through the draft.

  The finger table only includes the primary virtual IDs. Routing always happens in two steps. In the first step, you can just imagine that you don’t have the secondary virtual node IDs and just have the primary ones. Then, as in the case of Chord, you would use the primary IDs to route the request to the primary ID closest to the object. At this point, the node that receives the request checks if it owns that part of the ID space. If yes, it simply returns the object/response. If no, then it uses the neighbor tables to route the requests. This would take a maximum of O(log N) additional hops.

2)How to change the estimated N parameter  and keep the services non-stopping? Supposing that it has been far away from the actual network scale. 

  I don’t think there will be a situation where it is far away from the actual network scale since the fingers keep updating as and when the network grows. In some ways, the update algorithm will ensure that this situation would not arise. In the worst case, if the situation happens to arise, then that would imply that this particular node is highly imbalanced and is handling a very large amount of load. Therefore, it would be of benefit for the node to offload some of its load. The change can be done by leaving joining the network with a new set of virtual ids and leaving the network with the old ones. This can be done slowly without afffecting services (not leave and join at the same time with all the virtual node ids).

Yes. The simplest way is by increasing alpha or by increasing delta. However, if you increase alpha or delta too much then routing would become less efficient requiring more than O(log N) hops. A more complicated way to reduce the imbalance factor is by employing a hierarchical approach and building Y0 over another Y0.

Thanks
Saumitra

From: [email-masked] [mailto:[email-masked]] 
Sent: Tuesday, March 03, 2009 10:59 PM
To: Das, Saumitra
Cc: [email-masked]; [email-masked]
Subject: 答复: [P2PSIP] New Load balancing in RELOAD draft

I have read your article, and agree that load balancing is a key issue especially when we deploy the backend server systems built by p2p technology. 
Some questions following: 
1)Does the finger table only include the primary virtual node ID? 
2)How to change the estimated N parameter  and keep the services non-stopping? Supposing that it has been far away from the actual network scale. 
3)Could the imbalance factor be reduced further? 

Russell Wang

---

From: "Das, Saumitra" <[email-masked]>
Date: Fri, 6 Mar 2009 13:00:18 -0800

Just a clarification

Yes. The simplest way is by increasing alpha or by increasing delta. However, if you increase alpha or delta too much then routing would become less efficient requiring more than O(log N) hops. A more complicated way to reduce the imbalance factor is by employing a hierarchical approach by clustering nodes into groups (doing the scheme in that group) and then do the same scheme on the supergroups as a whole. This can get complicated and we stayed away from it to keep the proposal simple.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Das, Saumitra
Sent: Friday, March 06, 2009 12:58 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [P2PSIP] New Load balancing in RELOAD draft

Hi Russell,

Thanks
Saumitra

Russell Wang

---

From: [email-masked]
Date: Mon, 9 Mar 2009 11:57:43 +0800

Hi saumitra
thanks for your clarification. I read the article again, and still was 
wondering that:

1)About data insertion procedure. A new data storing request should first 
arrive at the physical node which primary ID is the immediate successor of 
the object ID, then be dispatched to the neareast secondary node in the 
physical node? Can secondary ID migrate dynamically among peers?
2)About performance. In some managed p2p systems, performance is critical, 
so O(1) DHT is the preferable algrithm. For O(1) DHT, extra  O(LogN) hops 
introduced by load balancing may be too large.

"Das, Saumitra" <[email-masked]> 
2009-03-07 05:00

收件人
"Das, Saumitra" <[email-masked]>, "[email-masked]" 
<[email-masked]>
抄送
"[email-masked]" <[email-masked]>
主题
RE: [P2PSIP] New Load balancing in RELOAD draft

Just a clarification

Yes. The simplest way is by increasing alpha or by increasing delta. 
However, if you increase alpha or delta too much then routing would become 
less efficient requiring more than O(log N) hops. A more complicated way 
to reduce the imbalance factor is by employing a hierarchical approach by 
clustering nodes into groups (doing the scheme in that group) and then do 
the same scheme on the supergroups as a whole. This can get complicated 
and we stayed away from it to keep the proposal simple.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf 
Of Das, Saumitra
Sent: Friday, March 06, 2009 12:58 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [P2PSIP] New Load balancing in RELOAD draft

Hi Russell,

  The finger table only includes the primary virtual IDs. Routing always 
happens in two steps. In the first step, you can just imagine that you don
’t have the secondary virtual node IDs and just have the primary ones. 
Then, as in the case of Chord, you would use the primary IDs to route the 
request to the primary ID closest to the object. At this point, the node 
that receives the request checks if it owns that part of the ID space. If 
yes, it simply returns the object/response. If no, then it uses the 
neighbor tables to route the requests. This would take a maximum of O(log 
N) additional hops.

  I don’t think there will be a situation where it is far away from the 
actual network scale since the fingers keep updating as and when the 
network grows. In some ways, the update algorithm will ensure that this 
situation would not arise. In the worst case, if the situation happens to 
arise, then that would imply that this particular node is highly 
imbalanced and is handling a very large amount of load. Therefore, it 
would be of benefit for the node to offload some of its load. The change 
can be done by leaving joining the network with a new set of virtual ids 
and leaving the network with the old ones. This can be done slowly without 
afffecting services (not leave and join at the same time with all the 
virtual node ids).

Yes. The simplest way is by increasing alpha or by increasing delta. 
However, if you increase alpha or delta too much then routing would become 
less efficient requiring more than O(log N) hops. A more complicated way 
to reduce the imbalance factor is by employing a hierarchical approach and 
building Y0 over another Y0.

Thanks
Saumitra

Russell Wang

---

From: Bruce Lowekamp <[email-masked]>
Date: Mon, 9 Mar 2009 08:52:54 -0400

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

---

From: "Das, Saumitra" <[email-masked]>
Date: Tue, 10 Mar 2009 11:25:12 -0700

1. About data insertion procedure. A new data storing request should first arrive at the physical node which primary ID is the immediate successor of the object ID, then be dispatched to the neareast secondary node in the physical node?

Yes. This is correct.

2. Can secondary ID migrate dynamically among peers?

Primary IDs are fixed and a node has one primary ID assigned for its lifetime on the network similar to base RELOAD. The secondary IDs change dynamically as required (for example, during adding or removing nodes as in our update algorithm). I guess this is what you are asking or maybe I am misunderstanding your question. An id cannot be handed off between peers.

3. In some managed p2p systems, performance is critical, so O(1) DHT is the preferable algrithm. For O(1) DHT, extra  O(LogN) hops introduced by load balancing may be too large.

In the basic form, you would require O(log N) to get to the primary virtual node closest to the object ID (via Chord/Pastry etc.), and then an additional O(log N) hops to get to the correct physical node. The latter step is usually random-walk based where you just walk backwards from the primary virtual node until you get to a physical node that owns the object ID. 

Now, the step 1 can be easily implemented over a O(1) DHT just by replacing the Chord/Pastry like topology with the corresponding O(1) DHT. There are several proposals in research papers to do this. In Pastry you could vary the system parameters to achieve this.

If we want to make the random walk part also O(1), then the easiest way to do it is by including more neighbor state (e.g. O(log N) neighbors in addition to O(log N) fingers) in the node so that the object can be routed to the exact ID in O(1) hops.

So yes, in managed backed p2p systems which may not be too concerned with higher overhead as generic p2p systems, the scheme can be extended.

Thanks
Saumitra

From: [email-masked] [mailto:[email-masked]] 
Sent: Sunday, March 08, 2009 8:58 PM
To: Das, Saumitra
Cc: [email-masked]; Das, Saumitra
Subject: RE: [P2PSIP] New Load balancing in RELOAD draft

Hi saumitra 
thanks for your clarification. I read the article again, and still was wondering that: 

1)About data insertion procedure. A new data storing request should first arrive at the physical node which primary ID is the immediate successor of the object ID, then be dispatched to the neareast secondary node in the physical node? Can secondary ID migrate dynamically among peers? 
2)About performance. In some managed p2p systems, performance is critical, so O(1) DHT is the preferable algrithm. For O(1) DHT, extra  O(LogN) hops introduced by load balancing may be too large. 

"Das, Saumitra" <[email-masked]> 
2009-03-07 05:00 
收件人
"Das, Saumitra" <[email-masked]>, "[email-masked]" <[email-masked]> 
抄送
"[email-masked]" <[email-masked]> 
主题
RE: [P2PSIP] New Load balancing in RELOAD draft

Just a clarification

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Das, Saumitra
Sent: Friday, March 06, 2009 12:58 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [P2PSIP] New Load balancing in RELOAD draft

Hi Russell,

Thanks
Saumitra

Russell Wang

---

From: "Das, Saumitra" <[email-masked]>
Date: Fri, 27 Mar 2009 13:09:42 -0700

Hi Bruce,

  Have some answers now for some of your questions.

>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

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-masked]] 
Sent: Monday, March 09, 2009 5:53 AM
To: Das, Saumitra
Cc: [email-masked]
Subject: Re: [P2PSIP] New Load balancing in RELOAD draft

Saumitra,

Very interesting draft.

Bruce