Subject: [P2PSIP] replication for p2psip

From: "Bruce Lowekamp" <[email-masked]>
Date: Mon, 3 Dec 2007 10:43:42 -0800

I'm attaching a first draft of slides for the replication discussion
on Wednesday.  (I'm also including the raw text below, which is a
little bit hard to read.)  I have tried to summarize the important
concepts and issues, and at the end I propose a high-level view of a
solution, as I perceive the conclusion of the earlier email threads.

I would appreciate specific comments on the slides, missing important
issues, or just general conversation on these issues.

Bruce

Replication for P2PSIP
Bruce Lowekamp
12/5/2007
2
Replication vs Erasure Codes
This talk discusses "replication."  For
P2PSIP, where the primary resource is
a AoR->URI or similar mapping, this is
the right approach.  For storage of
larger objects, mechanisms such as
erasure codes are more appropriate.
Most of the same issues of placement
and responsibility are still applicable
with only slight modifications.
3
The Questions
What should replication achieve?
What peer is responsible for replication?
What layer is responsible?
How many replicas?
Where to put the replicas?
4
Goals of Replication
Persistence
• Data retained after crash of responsible peer
• "Permanence" after storing peer leaves
Security
• DoS by responsible peer
• Routing attacks along path to responsible peer
Load Balancing
• Queries for a popular resource distributed
between replicas
5
Popular Replication Schemes
Neighbors
• Persistence with loss of responsible peer
• DHT-dependent definition
• Vulnerable to routing attacks
• Depends on responsible peer
Random replicas
• Fixed offsets or text addition before hashing
• Paths to different replicas are independent
• Harder to replace on loss of responsible peer
Query-path
• Replicas added along path to responsible peer
• Good for load balancing
6
Who Replicates?
Storing (owner) peer
• Cares the most about the outcome
• Should bear work responsibility
• Can't refresh after leaving
Responsible peer
• "Responsible"
• Easiest support for "permanent" resources
• Low overhead for neighbors
• Higher overhead for random replicas
7
What Layer Replicates?
DHT
• Appropriate replication scheme related to DHT
algorithm
Application
• Knows requirements
Persistence
Reliability
Popularity
• Knows when owner is present
• Only layer that can generate new signatures (if
needed)
8
Possible Solutions?
No single approach solves all problems.
Proposal: We need both
• DHT-level replication always appropriate, can't be
done by application-layer.
• Only application-layer knows enough about
requirements to justify/define further replication.
• Responsible peer needs to make application-layer
decisions about its resources.  Not just DHT-level.
• Interaction between these layers may be useful to
detect malicious peers.
_______________________________________________
P2PSIP mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/p2psip

---

From: Ingmar Baumgart <[email-masked]>
Date: Mon, 03 Dec 2007 11:09:47 -0800

Hi Bruce,

thank you for slides on replication. I agree with mosts statements on
your slides. Just a few comments:

- Replication on neighbors is not always vulnerable to routing attacks.
If you use iterative routing many overlay topologies allow you to reach
all neighbors over disjoint paths. One benefit of replication on
neighbors is, that you have a much closer relationship among replicating
nodes, which makes replication by the responsible peers more efficient
and secure.

- "Who Replicates?". There is a second alternative for replication by
the responsible peer(s). I suppose the approach mentioned in your slides
is that the responsible peers pushes the records to all replicating
peers. The second alternative (as it is done in P2PNS) is that all
replicating peers pull the records from all other peers. In this sense
there is not a single responsible peer, but all neighbors are equally
responsible. I think having a single responsible peer is a big security
problem.

- I don't understand what we gain by additional replication by the
application layer. In P2PNS replication is done only by the DHT layer
and I would be interested if there are any (especially security) issues
with that.

Regards,
  Ingmar

Bruce Lowekamp wrote:
> ------------------------------------------------------------------------
> 

-- 
Dipl.-Inform. Ingmar Baumgart
Institut für Telematik, Universität Karlsruhe (TH)
Zirkel 2, 76128 Karlsruhe, Germany
Phone: +49 721 608 8281, Fax: +49 721 608 6789

---

From: "Bruce Lowekamp" <[email-masked]>
Date: Mon, 3 Dec 2007 17:21:03 -0800

> nodes, which makes replication by the responsible peers more efficient

Good point.  I was thinking specifically of chord and then trying to
generalize, and that statement isn't true in the generalization.

> responsible. I think having a single responsible peer is a big security

I'm sorry, I didn't see this in the p2pns draft, but I may have read
too fast.  Where is it?  My understanding from your statement is that
you're having the peers storing each replica mutually refresh each
other to maintain persistence? You're right, I should probably fit
that in somehow.

> and I would be interested if there are any (especially security) issues

I think the key question is whether there is one replica scheme that
can be appropriate for all applications that the overlay will be
supporting.  The requirements for, say, storage of voicemail until it
is retrieved are different than for storage of a user's current
location that the user can refresh itself on a regular interval.  Do
we want to use the same replication strategy for both or do we need to
somehow support options?  That's the question I'm trying to get at
with slide 7.  Maybe I should be more explicit there.

Bruce

---

From: Ingmar Baumgart <[email-masked]>
Date: Mon, 03 Dec 2007 19:27:40 -0800

> other to maintain persistence? You're right, I should probably fit

Every time a peer joins it retrieves all data records close to his
nodeID by querying all his neighbors. To ensure consistency this can be
repeated periodically (e.g. every hour).

Unfortunately there is only a very short description on this in the
current draft. It's in section 5.4.1:

> Data records are replicated on several nodes, because a malicious
> node may arbitrarily tamper with locally stored data records.  The
> replicas are stored on neighbor nodes close to the key as these nodes
> can be efficiently discovered by a single KBR lookup.

> A peer resolves a P2PName to nodeID mapping by querying all replicas
> in parallel.  Thereupon the peer makes a majority decision on all
> received replies to determine the most plausible destination nodeID.
> In order to handle churn every newly joined node first requests all
> data records in his responsibility from his neighbor nodes and stores
> them locally.

> with slide 7.  Maybe I should be more explicit there.

Thank you for this explanation. I didn't get this from the slides.

Regards,
  Ingmar

---

From: jiangxingfeng 36340 <[email-masked]>
Date: Tue, 04 Dec 2007 15:54:37 +0800

> the responsible peer(s). I suppose the approach mentioned in your 
> slidesis that the responsible peers pushes the records to all 
> replicatingpeers. The second alternative (as it is done in P2PNS) 
> is that all
> responsible. I think having a single responsible peer is a big 
> securityproblem.
> 

the pull mode may work. But if the <key, Value> has been changed or deleted, how does the replicating peer learn it has changed?

---

From: Song Yongchao <[email-masked]>
Date: Tue, 04 Dec 2007 17:35:52 +0800

Hi, all

The attachment is the draft slides for our suggested replication mechanism
in DHT level by the responsible peer. It has the following benefits:

1) It can be adapted to all DHT algorithms,

2) It can achieve load balance by distributing the requests to replica
nodes,

3) The maintenance of replicas is simple,

4) It can achieve the availability and persistence of resource objects.

Best Regards!
Song Yongchao

> -----Original Message-----
> From: Bruce Lowekamp [mailto:[email-masked]]
> Sent: Tuesday, December 04, 2007 2:44 AM
> To: P2PSIP Mailing List
> Subject: [P2PSIP] replication for p2psip
> 
> ? Data retained after crash of responsible peer
> ? "Permanence" after storing peer leaves
> Security
> ? DoS by responsible peer
> ? Routing attacks along path to responsible peer
> Load Balancing
> ? Queries for a popular resource distributed
> between replicas
> 5
> ? Persistence with loss of responsible peer
> ? DHT-dependent definition
> ? Vulnerable to routing attacks
> ? Depends on responsible peer
> Random replicas
> ? Fixed offsets or text addition before hashing
> ? Paths to different replicas are independent
> ? Harder to replace on loss of responsible peer
> Query-path
> ? Replicas added along path to responsible peer
> ? Good for load balancing
> 6
> Who Replicates?
> Storing (owner) peer
> ? Cares the most about the outcome
> ? Should bear work responsibility
> ? Can't refresh after leaving
> Responsible peer
> ? "Responsible"
> ? Easiest support for "permanent" resources
> ? Low overhead for neighbors
> ? Higher overhead for random replicas
> 7
> What Layer Replicates?
> DHT
> ? Appropriate replication scheme related to DHT
> algorithm
> Application
> ? Knows requirements
> ?Persistence
> ?Reliability
> ?Popularity
> ? Knows when owner is present
> ? Only layer that can generate new signatures (if
> needed)
> 8
> Possible Solutions?
> ? DHT-level replication always appropriate, can't be
> ? Only application-layer knows enough about
> ? Responsible peer needs to make application-layer
> ? Interaction between these layers may be useful to
> detect malicious peers.

---

From: Ingmar Baumgart <[email-masked]>
Date: Tue, 04 Dec 2007 08:50:53 -0800

> the pull mode may work. But if the <key, Value> has been changed or deleted, how does the replicating peer learn it has changed?

In case the owner modifies a record it pushes it to all currently
responsible nodes. This modification is signed with the owner's private
key (in P2PNS only the owner is allowed to change a record).

Regards,
  Ingmar

---

From: Ingmar Baumgart <[email-masked]>
Date: Tue, 04 Dec 2007 10:07:24 -0800

Hi,

is there a draft which describes your "Responsible Peer Replication"?

As far as I've understood your slides, there are several issues:

- What if the responsible peer is malicious? In this case a single
malicious node is sufficient to tamper with a stored date record.

- In your slides it looks like replica nodes are determined by using
multiple hash functions. In this case it is very inefficient for the RP
to constantly verify all replica nodes, because there is no direct
relationship to these nodes (these nodes a not in your routing tables
and are not covered by normal routing table maintenance).

- If the RP fails, which of the replica peers is authorized to transfer
the record to the new RP? (some of the replica peers could also be
malicious).

- The load balancing seems to be broken. Why do you always contact the
RP first and let than the RP relay the request to one of the replicas? I
would be much better to directly contact the replicas yourself.

Regards,
  Ingmar

Song Yongchao wrote:
>> This body part will be downloaded on demand.

---

From: Song Yongchao <[email-masked]>
Date: Wed, 05 Dec 2007 10:12:46 +0800

> From: Ingmar Baumgart [mailto:[email-masked]]
> Sent: Tuesday, December 04, 2007 11:28 AM
> To: Bruce Lowekamp
> Cc: P2PSIP Mailing List
> Subject: Re: [P2PSIP] replication for p2psip
> 

I don't think it works. A peer usually has tens of entries in his neighbor
table. Why do you pull resource objects from all his neighbors? Why do we
need so many replicas? That is a large waste of bandwidth and storage.

---

From: Song Yongchao <[email-masked]>
Date: Wed, 05 Dec 2007 10:54:35 +0800

> Sent: Wednesday, December 05, 2007 2:07 AM
> To: Song Yongchao
> Cc: 'Bruce Lowekamp'; 'P2PSIP Mailing List'

We will prepare a draft when needed.

> malicious node is sufficient to tamper with a stored date record.

Resource object has the signature with the owner's private key. No peer
except the owner can modify the resource object.

> and are not covered by normal routing table maintenance).
How to choose replica nodes is an open issue. Powerful nodes with enough
spare space in the neighbor/routing table are preferred. Other peers that
can provide large storage service can also be taken into account.

The number of replicas needed is determined by the overly churn rate. It is
an open issue that should be discussed in the mail list.

> the record to the new RP? (some of the replica peers could also be

Any replica peer that detects the failure of the RP must lookup with the key
of the resource object in the overlay. Then any replica peer can find the
new responsible peer for the record. This can be adapted to all DHT
algorithms. The replica peer that first detects the failure must transfer
the record to the new RP. The security of the record is protected by
signature with the owner's private key.

BR
Song Yongchao

---

From: Ingmar Baumgart <[email-masked]>
Date: Tue, 04 Dec 2007 18:59:42 -0800

> need so many replicas? That is a large waste of bandwidth and storage.

Sorry, querying "all neighbors" was a bit vague. Actually we query only
the k closest neighbors (k could also be as small as 1).

Regards,
  Ingmar

---

From: Ingmar Baumgart <[email-masked]>
Date: Tue, 04 Dec 2007 19:38:05 -0800

Okay, so this depends on the requirements the application has for DHT
layer security. Signing a resource object does not prevent a malicious
node from not storing the object or adding an additional object with the
same ID.

Regards,
  Ingmar