Subject: [P2PSIP] RELOAD's modified Chord algorithm

From: Jouni Mäenpää <[email-masked]>
Date: Wed, 16 Jul 2008 09:30:25 +0300

Hi,

The RELOAD draft specifies in chapter 12 a modified version of the Chord
algorithm. It seems to me that this modified Chord algorithm uses
reactive recovery from node failures instead of periodic recovery, which
is used by the original Chord algorithm as specified in [1]. In reactive
recovery, a node reacts to the loss of a node in its neighborhood set by
sending a copy of it neighbor table to all nodes in the neighborhood
set. Periodic recovery, in contrast, takes place independently of
changes in the neighborhood set. In periodic recovery, a node
periodically shares its neighborhood set with each of the members of
that set.

It has been shown in [2] that reactive recovery is only efficient at low
churn rates. With moderate and high churn rates, periodic recovery uses
less bandwidth and the resulting lower contention of the network leads
to lower latencies. My concern is that because it uses reactive
recovery, the performance of RELOAD's Chord algorithm may degrade under
moderate and high churn rates.

As an example, the first version of the Bamboo DHT algorithm used
reactive recovery. As a consequence, Bamboo suffered a performance
degradation under churn. To solve this issue, Bamboo was modified to use
periodic recovery from node failures.

Any comments?

[1] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H.
Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet
applications. Technical Report TR-819, MIT, March 2001
[2] S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in
a DHT. In Proc. of USENIX Technical Conference, June 2004

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

---

From: jiangxingfeng 36340 <[email-masked]>
Date: Wed, 16 Jul 2008 16:14:49 +0800

Hi,Jouni:

I agree. By the way, [2] also points out the a more intelligent time out value between neighor nodes will improve transaction latency and could be exploited to choose another better node timely. So periodical recovery or keepalive message facilitates the computation of the time out value. 

> Hi,
> 
> The RELOAD draft specifies in chapter 12 a modified version of the 
> Chordalgorithm. It seems to me that this modified Chord algorithm uses
> reactive recovery from node failures instead of periodic recovery, 
> whichis used by the original Chord algorithm as specified in [1]. 
> In reactive
> churn rates. With moderate and high churn rates, periodic recovery 
> usesless bandwidth and the resulting lower contention of the 
> network leads
> recovery, the performance of RELOAD's Chord algorithm may degrade 
> undermoderate and high churn rates.
> 
> Balakrishnan. Chord: A scalable peer-to-peer lookup service for 
> Internetapplications. Technical Report TR-819, MIT, March 2001

---

From: Bruce Lowekamp <[email-masked]>
Date: Wed, 16 Jul 2008 09:39:37 -0400

Jouni,

Thanks for the careful read.  I think there are a couple issues that 
your email raises.

The first is a general one of determining the requirements for the 
mandatory DHT algorithm for p2psip (the wg has voted to make at least 
one mandatory, I guess more is an option too).  Rhea's research shows 
that for large overlays with high churn rates, reactive recovery imposes 
too high a load and recommends periodic recovery.  I agree with that 
conclusion.  However, many of the scenarios proposed for p2psip have 
smaller overlays and lower churn rates.  In those cases, reactive 
recovery would be preferable.  Even in large-scale overlays, one could 
argue a p2psip overlay would expect session times on the longer end of 
the scale if people are leaving it up for incoming calls.  Regardless, 
if we have just one DHT specified, I don't think we're going to be able 
to reach an ideal solution for all use cases.

Looking at the algorithm in RELOAD, I believe it specifies reactive 
recovery for the neighborhood set (leaf set in Rhea's terminology) and 
periodic recovery for the finger table (routing table).  Actually, I 
don't think it specifies what exactly to do when a finger table entry 
fails, but it only specifies periodic checks for finger table entries 
and emphasizes that since they're just an optimization, it's OK to leave 
the finger table entries suboptimal.  So it's something of a compromise 
between the two options, using reactive recovery where it matters more 
and periodic (or choice left to the implementor) recovery where it 
doesn't matter.

I personally think that the balance in the current draft is good for 
what I expect to be the typical range of p2psip deployments.  I 
completely agree that it's not appropriate for a large-scale high-churn 
overlay.  However, my experience with smaller-scale overlays (office pbx 
scale) suggests that we do need reactive recovery in those environments. 
   If the WG decides that the mandatory DHT should specify tunable 
behavior or that we should have multiple mandatory DHTs to support a 
range of environments, I'm OK with that.

Parenthetically, I'm a bit embarassed that I've never rewritten the 
section on periodically searching for new finger table entries.  I 
intended to rewrite that to specify that the existing peer in a finger 
table entry (that is in that range) should not be replaced with a 
"better match" because we should prefer stable peers over better 
matches.  I think that change would be more in line with current best 
practices for dht routing.

Bruce

---

From: Jouni Mäenpää <[email-masked]>
Date: Fri, 18 Jul 2008 15:42:30 +0300

Hi Bruce,

Thanks for your answer. Below you say that in your experience, reactive
recovery is needed in smaller-scale overlays. Do you have any results to
share regarding the maximum level of churn and overlay size that
reactive recovery is able to handle? I have been experimenting in
PlanetLab with a 500-node Chord-based P2PSIP overlay, which uses only
periodic recovery. The churn rate has been such that there is one node
leaving and joining every five seconds on average. At this churn rate
and network size, periodic recovery seems to perform rather well.

Jouni

---

From: Bruce Lowekamp <[email-masked]>
Date: Mon, 21 Jul 2008 13:52:01 -0400

Jouni,

I haven't run experiments on the exact tradeoffs.  When I say office 
pbx, I'm thinking of working down to 4-50 peer systems.  In those cases, 
because a single peer can be responsible for such a large portion of the 
name space and wind up in the routing table of most of the other peers, 
it seems to be useful to have reactive recovery, and we don't have a 
performance problem with the extra messages.

I don't anticipate having time to do it, but it would be interesting to 
do and experiment comparing the overhead of reactive recovery for 
neighborhood/leaf set only vs for the whole finger table.  IIRC, Rhea's 
paper only looked at fully reactive vs fully periodic.

Bruce

---

From: Jouni Mäenpää <[email-masked]>
Date: Wed, 23 Jul 2008 09:41:20 +0300

Hi,

As pointed out in [1], DHT-based overlays usually need to be configured
statically (e.g. by assuming a certain churn level and network size).
The problem is setting the parameters so that the overlay achieves the
desired reliability and performance even in challenging conditions, such
as under heavy churn. This naturally results in high cost in the common
case or alternatively, poor performance or even network partitioning in
worse than expected conditions. This kind of hand-tuning rarely works in
real settings because it requires perfect knowledge about the future.

In my opinion, the P2PSIP WG should specify a self-tuning DHT algorithm
 which would adapt to the operating conditions (e.g. network size and
churn rate). This would make it possible to use the DHT in a wide range
of environments instead of e.g. only small-scale low-churn networks.

Any comments?

Jouni

[1] R. Mahajan, M. Castro, and A. Rowstron. Controlling the cost of
reliability in peer-to-peer overlays. In IPTPS, 2003

---

From: Bruce Lowekamp <[email-masked]>
Date: Thu, 24 Jul 2008 15:53:03 -0400

Jouni,

I like the concept of self-tuning DHT algorithms, but I'm a bit 
concerned about requiring a somewhat complex algorithm to be implemented 
as the base dht.  Two of the goals for the base dht in the current draft 
were implementation simplicity and reasonable performance across the 
full scale of environments.

You've raised the question of whether the reactive recovery will cause 
scaling problems for larger overlays.  I hope someone has a chance to 
look at that question.  reload's current dht uses a smaller neighborhood 
set than most other current DHTs (certainly than pastry), while 
specifying reactive rather than periodic recovery.  The one thing I 
think we can say for certain is that it's unclear what the tradeoffs of 
the various options are.  I'm not aware of any work that looks at both 
reactive/periodic combined with different neighborhood set sizes and 
whether just the neighborhood or the entire routing table is maintained 
with which algorithm.  And certainly those works don't address the 
appropriateness of their algorithms in small-scale overlays.

My belief has been that reactive recovery with the small neighborhood 
set is OK.  But I also believe that reactive recovery for failures could 
be avoided if the neighborhood is bigger (still needs to propagate new 
peers faster, though).  Would be interesting to compare.

Whatever we decide the requirements are, we're going to have to study 
the algorithm across a range of environments before we commit to it.

Bruce

---

From: Henry Sinnreich <[email-masked]>
Date: Fri, 25 Jul 2008 11:37:46 -0700

> Jouni

Actually, I would argue that a new P2PSIP protocol may be useful but not
necessarily mandatory at all and here is why:

1. Any P2P solution must work for more than SIP, especially with for other
Rich Internet Applications (RIA) and older ones as well: Application level
multicast, blogging, social networks, wikis, video, range search, not
invented yet.

2. This is possible only by using HIP for NAT traversal for _all_
application level protocols.

3. Using HIP, the existing native p2p protocols can be used such as Bamboo,
with SIP as one of several applications on top of the p2p overlay. No other
special protocols are required, though one may be useful. My problem is I
have not found any reason why a special protocol would be required of we
just use the following:

Application
=======================
SIP/RTP
=======================
Any P2P optimally suitable for the specific application
=======================
HIP with NAT traversal
=======================
UDP/TCP
=======================
IP
=======================

I would be interested to hear what else is required for SIP in particular.

Thanks, Henry

---

From: songhaibin 64081 <[email-masked]>
Date: Sun, 27 Jul 2008 03:09:44 +0800

Hi all,

In the merged p2psip security requirement draft, the authors analyze the p2psip security with p2p layers, with classfied application scenarios, and summarize the security requirements in the last. We also list the security threats in the appendix. It is a work in progress. If anyone has some comments to the draft, the authors will be very glad to hear and take into consideration.

Best Regards!
Song Haibin

---

From: Jouni Mäenpää <[email-masked]>
Date: Mon, 28 Jul 2008 15:00:23 +0300

Hi,

Currently, the RELOAD draft specifies one mandatory DHT algorithm, which
is a modified version of the Chord DHT algorithm. The reason for
specifying a mandatory algorithm is to allow interoperability. It seems
that this modified Chord algorithm is mostly useful in small-scale
low-churn scenarios. What I am trying to say is that the P2PSIP WG
should not forget about other scenarios such as
large-scale/medium-scale/high-churn/medium-churn etc. overlay networks.
 To handle these other scenarios, one either needs to hand-tune the DHT
algorithm specifically for each scenario (by setting appropriate values
for parameters such as the size of the neighborhood set, the size of the
finger table, and stabilization interval) or alternatively, one needs
self-tuning behavior. Hand-tuning will be very difficult in practice.

I agree that the P2PSIP work would benefit from HIP. However, regardless
of whether HIP is used or not, we would anyway benefit from a DHT
algorithm that can adjust its parameters dynamically as the size of the
network and/or the churn rate changes.

As an alternative to specifying only one DHT algorithm, perhaps the
P2PSIP WG could specify at least two DHT algorithms: a simple one which
would be easy to implement and which would work well in small, low-churn
networks (i.e. the modified Chord algorithm currently specified in the
RELOAD draft). Then there could be another, self-tuning algorithm, which
would scale also to bigger networks and to networks having higher churn
rates. Of course, ideally there would be only one algorithm.

Jouni

---

From: Dan York <[email-masked]>
Date: Tue, 29 Jul 2008 10:58:10 -0400

P2PSIP members,

Just to re-emphasize Song Haibin's point, the new security  
requirements draft (-03):

    http://www3.tools.ietf.org/html/draft-matuszewski-p2psip-security-requirements

is a merger of two previous drafts:

http://www3.tools.ietf.org/html/draft-matuszewski-p2psip-security-requirements-02
    - from Marcin Matuszewski and others
http://www3.tools.ietf.org/html/draft-song-p2psip-security-eval-00
    - from Song Haiban and others

While there is still work to do to fully merge the two documents, we  
(I am also involved) would like to hear comments on the merged  
document from list members.

- Is this merged draft going in the right direction?
- Are there major holes that you see in the document that need to be  
addressed?  (Outside of the security issues related to PSTN gateways  
that I have indicated in the Author's Note that I'll be adding.)
- Are the Appendices useful?
- Anything else you think should be added to this draft?  Anything you  
think should be removed?

There is not currently time on the P2PSIP agenda at IETF 72 to discuss  
this draft and so we would appreciate any comments that can be sent on  
the list.

Thank you,
Dan

On Jul 26, 2008, at 3:09 PM, songhaibin 64081 wrote:

> Hi all,
>
> In the merged p2psip security requirement draft, the authors analyze  
> the p2psip security with p2p layers, with classfied application  
> scenarios, and summarize the security requirements in the last. We  
> also list the security threats in the appendix. It is a work in  
> progress. If anyone has some comments to the draft, the authors will  
> be very glad to hear and take into consideration.
>
>
> Best Regards!
> Song Haibin

-- 
Dan York, CISSP, Director of Emerging Communication Technology
Office of the CTO    Voxeo Corporation     [email-masked]
Phone: +1-407-455-5859  Skype: danyork  http://www.voxeo.com
Blogs: http://blogs.voxeo.com  http://www.disruptivetelephony.com

Build voice applications based on open standards.
Find out how at http://www.voxeo.com/free

---

From: "Jing Chen" <[email-masked]>
Date: Wed, 30 Jul 2008 10:13:11 +0800

Hi Dan,
  I have three questions about the new security requirements draft (-03):
(1)  The threats and security requirements on DHT network or overlay are
discussed , but what about the threats and security requirements on SIP?
Especially that what are the threats on decentralized SIP?

(2) Why the layers in "Figure 2    P2PSIP architecture" are different from
the architecture layers in RELOAD? The KBR Layer isn't included in the
layers of RELOAD, and this layer is not defined in
draft-ietf-p2psip-concepts-02.

(3) As I know, PKI-based certificate is not flexible enough nor bandwidth
efficient because of the size of keys and certificates used. Why we don't
consider to use
Identity-based security framework ?

Best Regards,

J. Chen

2008/7/29 Dan York <[email-masked]>

> P2PSIP members,
>
> Just to re-emphasize Song Haibin's point, the new security requirements
> draft (-03):
>
>
> While there is still work to do to fully merge the two documents, we (I am
> also involved) would like to hear comments on the merged document from list
> members.
>
> addressed?  (Outside of the security issues related to PSTN gateways that I
> have indicated in the Author's Note that I'll be adding.)
> There is not currently time on the P2PSIP agenda at IETF 72 to discuss this
> draft and so we would appreciate any comments that can be sent on the list.
>
> Thank you,
> Dan
>
>
>
>> In the merged p2psip security requirement draft, the authors analyze the
>> p2psip security with p2p layers, with classfied application scenarios, and
>> summarize the security requirements in the last. We also list the security
>> threats in the appendix. It is a work in progress. If anyone has some
>> comments to the draft, the authors will be very glad to hear and take into
>> consideration.
>>
>>
>> Best Regards!
>> Song Haibin

---

From: songhaibin 64081 <[email-masked]>
Date: Wed, 30 Jul 2008 20:43:23 +0800

Hi Jing,

>(1)  The threats and security requirements on DHT network or overlay are discussed , but >what about the threats and security requirements on SIP? Especially that what are the >threats on decentralized SIP?
>

Good question. I have discussed this question with Dan before, but we are so busy. You will see the text about it in the next revision.
 
>(2) Why the layers in "Figure 2    P2PSIP architecture" are different from the >architecture layers in RELOAD? The KBR Layer isn't included in the layers of RELOAD, and >this layer is not defined in draft-ietf-p2psip-concepts-02.
>

I think the WG now have not achieved a consensus on the P2P layers. Bruce didn't mention that issue in his presentation. But I think the architecture are similar with Reload. We will surely make the architecture consistent with the WG's consensus.

>From many papers, you will find KBR layer is often used. Anyway, we will keep it consistent with the WG's consensus item.
 
>efficient because of the size of keys and certificates used. Why we don't consider to use

I think Identity-based security framework may be easy to use in the self organzed network. But the purpose of this draft mainly is not to provide the concrete solutions. It just tell you what the security issues are in the overlay, and you should consider them when you establish a p2p overlay.

Best Regards!
-Song Haibin