Subject: [P2PSIP] Suggested enhancement for default Chord topology plugin

From: "Das, Saumitra" <[email-masked]>
Date: Thu, 13 Nov 2008 17:18:34 -0800

I would like us to consider including locality awareness in the default topology plugin that is being proposed in p2psip-base. Through simulations of large scale overlays, I have observed a reduction in lookup delay of 40-45% using such a technique.

Making progress in the identifier space can be expensive in terms of network latency. A successor and predecessor list can be used to optimize network latency by relaxing the requirement for finger selection. Specifically, for each finger table entry, a node A first determines a node X that matches the identifier of the finger. It then retrieves the successors and predecessors of X from X. Node A then PINGs the successors and predecessors of node X and chooses the topologically closest node among these as the choice for the finger table entry. The sizes of the successor and predecessor lists have an impact on network latency; the larger the value or these, the higher the probability of finding a topologically close finger table entry. 

Note that having successor and predecessor lists have been alternately proposed for improved robustness to failures and preventing the partition of a Chord network. We can have this benefit as well as the benefit of better lookup performance using locality awareness by exploiting this extra information. Some of the methods proposed in p2psip-diagnostics can be used for choosing the finger table entry. If the usage wants to avoid measurement overhead, virtual cooridnate systems such as GNP, vivaldi could be used to select a peer for locality awareness as well.

A simulation study with a different simulator in Ref 1 using 2^16 nodes and an euclidean RTT model and transit-stub model showed lookup stretch reductions of 31% to 40% as well.

Ref 1: "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications", IEEE/ACM Transactions on Networking, vol 11, 2003."

Thanks
Saumitra

_______________________________________________
P2PSIP mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2psip

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Fri, 14 Nov 2008 07:34:51 -0500

Saumitra,

You're absolutely right in the advantage of including topology
information in picking finger table entries.  However, one of our
goals in the base draft is to minimize complexity where possible.  In
this case, many application scenarios for p2psip are on a LAN (office
phone system, voicemail server cluster) and so don't need this
complexity.  Therefore, we'd rather avoid adding this to the base
draft as it would both complicate the overlay algorithm and require
diagnostics in every implementation.

I think there are two ways to address your concern without adding
complexity, however:
- we expect new overlay algorithms to be proposed, especially a better
DHT for Internet-scale use.  Would really like to see that.
- The terminology in the stabilization section doesn't use MUST to
describe how finger table entries are found.  I can work on the
wording a little bit to state that there may be alternative methods
for selecting good entries.

Bruce

---

From: "Das, Saumitra" <[email-masked]>
Date: Fri, 14 Nov 2008 13:12:13 -0800

Hi Vijay,

  The results are from the journal version of the Chord paper which is "Chord: A Scalable Peer-to-peer Lookup Service for Internet
Applications", IEEE/ACM Transactions on Networking, vol 11, 2003." The paper is available at: http://pdos.csail.mit.edu/chord/papers/paper-ton.pdf 

  Independent of that I have also performed simulations with a different platform and observed similar gains as reported in the paper above.

  Apart from these, there are several papers that list the benefits of locality awareness but for other DHTs such Pastry.

  Locality awareness has also been proposed for the popular Kademlia DHT which uses iterative routing. http://www2.computer.org/portal/web/csdl/doi/10.1109/P2P.2008.36 

Thanks,
Saumitra

-----Original Message-----
From: Vijay K. Gurbani [mailto:[email-masked]] 
Sent: Friday, November 14, 2008 8:53 AM
To: Das, Saumitra
Cc: Enrico Marocco
Subject: Re: [P2PSIP] Suggested enhancement for default Chord topology plugin

Das, Saumitra wrote:
> A simulation study with a different simulator in Ref 1 using 2^16
> nodes and an euclidean RTT model and transit-stub model showed lookup
> stretch reductions of 31% to 40% as well.
> 
> Ref 1: "Chord: A Scalable Peer-to-peer Lookup Service for Internet
> Applications", IEEE/ACM Transactions on Networking, vol 11, 2003."

Saumitra: The study you refer to above, is it public?  If so,
do you have the name of the paper that describes its results?

I am aware of one or two (the TU-Berlin work, for instance)
that fit the bill as described above, but am curious to see
if I have overlooked any.

Thanks,

- vijay
-- 
Vijay K. Gurbani, Bell Laboratories, Alcatel-Lucent
1960 Lucent Lane, Rm. 9C-533, Naperville, Illinois 60566 (USA)
Email: vkg@{alcatel-lucent.com,bell-labs.com,acm.org}
Web:   http://ect.bell-labs.com/who/vkg/
_______________________________________________
P2PSIP mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/p2psip

---

From: "Das, Saumitra" <[email-masked]>
Date: Fri, 14 Nov 2008 15:58:25 -0800

Hi Bruce,

  While there are application scenarios for LAN, even if we take an enterprise we are already seeing increasing use of enterprise mobile devices which sort of take this problem to a larger scale. Even if the enterprise itself may be in a few locations, the people part of the overlay could be spread out while traveling and once again locality awareness would come into play.

  In order to support it either as a better topology plugin to be proposed in the future or as part of the default DHT, what we need is the capability in the protocol to request the neighbor list of a targeted finger entry and receive it.

I concur with your concern about not adding complexity. However, I would argue that locality selection does not add much complexity to the system. A peer gets a list of peers in a ID neighborhood, pings those peers, and chooses the one with the lowest RTT as a finger. The draft would need to support the ability for a peer to give another peer a list of its id space neighbhors. A ping message is already supported, so no additional change is required for that. The exact details of how many neighbors to ping, how many pings to send, etc. can be left to the implementation to reduce the complexity of the base draft.

When put in the context of everything else that the base draft would specify, this may not be significantly complex. So while I concur that simplicity is an important design criterion, locality awareness designed in this way is in the spirit of that criterion and results in worthwhile gains.

Thoughts?

Thanks,
Saumitra

-----Original Message-----
From: Bruce Lowekamp [mailto:[email-masked]] 
Sent: Friday, November 14, 2008 4:35 AM
To: Das, Saumitra
Cc: [email-masked]
Subject: Re: [P2PSIP] Suggested enhancement for default Chord topology plugin

Saumitra,

Bruce

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Sat, 15 Nov 2008 17:03:46 -0500

>  While there are application scenarios for LAN, even if we take an enterprise we are already seeing increasing use of enterprise mobile devices which sort of take this problem to a larger scale. Ev…

I am really unconvinced that mobile devices in an overlay consisting
mostly of wired devices should be peers.  Particularly in an
enterprise environment, I don't think this is justifiable.

> I concur with your concern about not adding complexity. However, I would argue that locality selection does not add much complexity to the system. A peer gets a list of peers in a ID neighborhood,…

That's fine.  It requires no changes to the current draft other than
for the draft to recommend a basic way to select finger table entries
but allow that other methods are acceptable as long as the finger
table entries are valid for that range.  The RouteQueryReq already
handles probing for the existing neighbors.

Bruce

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Sat, 15 Nov 2008 17:31:16 -0800

> I am really unconvinced that mobile devices in an overlay 
> consisting mostly of wired devices should be peers.  
> Particularly in an enterprise environment, I don't think this 
> is justifiable.
> 

I don't quite understand what locality awareness has to do specifically with mobile devices. It is much more generic than that.  And, the kind of gains we are talking about in latency makes it definitely worth it.  

> >  In order to support it either as a better topology plugin 
> to be proposed in the future or as part of the default DHT, 
> what we need is the capability in the protocol to request the 
> neighbor list of a targeted finger entry and receive it.
> >
> > I concur with your concern about not adding complexity. 
> However, I would argue that locality selection does not add 
> much complexity to the system. A peer gets a list of peers in 
> a ID neighborhood, pings those peers, and chooses the one 
> with the lowest RTT as a finger. The draft would need to 
> support the ability for a peer to give another peer a list of 
> its id space neighbhors. A ping message is already supported, 
> so no additional change is required for that. The exact 
> details of how many neighbors to ping, how many pings to 
> send, etc. can be left to the implementation to reduce the 
> complexity of the base draft.
> >
> 
> That's fine.  It requires no changes to the current draft 
> other than for the draft to recommend a basic way to select 
> finger table entries but allow that other methods are 
> acceptable as long as the finger table entries are valid for 
> that range.  The RouteQueryReq already handles probing for 
> the existing neighbors.
> 

Unless I'm missing something about the RouteQuery messages, I don't think this is enough.  This message will return the next hop towards the destination.  If a particular resource id maps to itself, it is not going to return its neighbors from what I can tell.  What you need are hooks in the protocol to obtain information about a node corresponding to a point in the id space and some number of its predecessors and successors.  For now, all we would need the draft to specify is the messaging for this.  We don't have to get into how the fingers themselves are chosen here.  

Vidya

> Bruce
> 
> 
> > When put in the context of everything else that the base 
> draft would specify, this may not be significantly complex. 
> So while I concur that simplicity is an important design 
> criterion, locality awareness designed in this way is in the 
> spirit of that criterion and results in worthwhile gains.
> >
> > Thoughts?
> >
> > Thanks,
> > Saumitra
> >
> > Subject: Re: [P2PSIP] Suggested enhancement for default 
> Chord topology 
> > plugin
> >
> > Saumitra,
> >
> >> I would like us to consider including locality awareness 
> in the default topology plugin that is being proposed in 
> p2psip-base. Through simulations of large scale overlays, I 
> have observed a reduction in lookup delay of 40-45% using 
> such a technique.
> >>
> >> Making progress in the identifier space can be expensive 
> in terms of network latency. A successor and predecessor list 
> can be used to optimize network latency by relaxing the 
> requirement for finger selection. Specifically, for each 
> finger table entry, a node A first determines a node X that 
> matches the identifier of the finger. It then retrieves the 
> successors and predecessors of X from X. Node A then PINGs 
> the successors and predecessors of node X and chooses the 
> topologically closest node among these as the choice for the 
> finger table entry. The sizes of the successor and 
> predecessor lists have an impact on network latency; the 
> larger the value or these, the higher the probability of 
> finding a topologically close finger table entry.
> >>
> >> Note that having successor and predecessor lists have been 
> alternately proposed for improved robustness to failures and 
> preventing the partition of a Chord network. We can have this 
> benefit as well as the benefit of better lookup performance 
> using locality awareness by exploiting this extra 
> information. Some of the methods proposed in 
> p2psip-diagnostics can be used for choosing the finger table 
> entry. If the usage wants to avoid measurement overhead, 
> virtual cooridnate systems such as GNP, vivaldi could be used 
> to select a peer for locality awareness as well.
> >>
> >>
> >> A simulation study with a different simulator in Ref 1 
> using 2^16 nodes and an euclidean RTT model and transit-stub 
> model showed lookup stretch reductions of 31% to 40% as well.
> >>
> >> Ref 1: "Chord: A Scalable Peer-to-peer Lookup Service for 
> Internet Applications", IEEE/ACM Transactions on Networking, 
> vol 11, 2003."
> >>
> >> Thanks
> >> Saumitra
> >>

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Sat, 15 Nov 2008 20:54:37 -0500

> I don't quite understand what locality awareness has to do specifically with mobile devices. It is much more generic than that.  And, the kind of gains we are talking about in latency makes it defi…

Reread the text I was responding to that was directly above that
sentence.  It said that mobile devices justified locality awareness.

> Unless I'm missing something about the RouteQuery messages, I don't think this is enough.  This message will return the next hop towards the destination.  If a particular resource id maps to itself…

RouteQueryReq can be used to request that the responder sends an
Update.  The Update conveys the information you are seeking.

Bruce

---

From: "Narayanan, Vidya" <[email-masked]>
Date: Sat, 15 Nov 2008 23:46:56 -0800

> >>
> >
> > I don't quite understand what locality awareness has to do 
> specifically with mobile devices. It is much more generic 
> than that.  And, the kind of gains we are talking about in 
> latency makes it definitely worth it.
> >
> 
> Reread the text I was responding to that was directly above 
> that sentence.  It said that mobile devices justified 
> locality awareness.
> 

Ah! You are probably assuming that mobile devices meant handhelds or some lower capability devices.  Or, did you actually mean that laptops should not be peers?  Remote employees in enterprise scenarios connecting via laptops with <pick your favorite> wireless access is common. 

<snip>

> >
> 
> 
> RouteQueryReq can be used to request that the responder sends 
> an Update.  The Update conveys the information you are seeking.
> 

Can you point to the spec where this is described? 

Thanks,
Vidya

---

From: "Das, Saumitra" <[email-masked]>
Date: Sun, 16 Nov 2008 00:38:07 -0800

The point about mobile devices was made in response to your comment that many p2psip application scenarios are just for LAN (office systems etc). I was trying to point out that in many enterprises people may not even have a fixed desktop and use wireless LAN/ethernet docked laptops. That specific comment was not really targeted at justifying locality awareness which applies to fixed desktop based overlays as well. I just mentioned in passing that mobile devices would introduce more scenarios where locality awareness is useful due to the potential geogrpahic spread of the overlay. However, even fixed desktop based overlays are likely to have large enough geographic spread to justify locality-awareness.

Thanks
Saumitra

-----Original Message-----
From: Bruce Lowekamp [mailto:[email-masked]] 
Sent: Saturday, November 15, 2008 5:55 PM
To: Narayanan, Vidya
Cc: Das, Saumitra; [email-masked]
Subject: Re: [P2PSIP] Suggested enhancement for default Chord topology plugin

Bruce

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Sun, 16 Nov 2008 11:57:19 -0500

> The point about mobile devices was made in response to your comment that many p2psip application scenarios are just for LAN (office systems etc). I was trying to point out that in many enterprises…

Fully agree.

Bruce

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 16 Nov 2008 08:49:50 -0600

At Sat, 15 Nov 2008 17:31:16 -0800,
Narayanan, Vidya wrote:
> Unless I'm missing something about the RouteQuery messages, I don't
> think this is enough.  This message will return the next hop towards
> the destination.  If a particular resource id maps to itself, it is
> not going to return its neighbors from what I can tell.

No.

5.3.2.4.1

   A RouteQueryReq message indicates the peer or resource that the
   requesting peer is interested in.  It also contains a "send_update"
   option allowing the requesting peer to request a full copy of the
   other peer's routing table.

-Ekr