Subject: [P2PSIP] Concurrent ATTACH between two peers

From: Michael Chen <[email-masked]>
Date: Mon, 01 Nov 2010 06:23:48 -0800

Hi,

The scenario is a peer (JP) joins a ring of two peers: AP and NP, where
AP is the admitting peer of JP.  Referring to Section 9.4 of the base-11
draft, step 7, AP sends an UPDATE to JP, immediately followed by step 8,
AP sends another UPDATE to NP.

If JP uses the technique discussed in thread "Clarification of initial
attach procedure" in which JP did not (or failed to) PING and ATTACH to
NP before JOIN, then after step 8, both JP and NP could simultaneously
send ATTACH to each other (via AP).

It's possible that both JP and NP receive the ATTACH request from the
other before receiving the reply to its own ATTACH request. The result
is two ICE checks may commence independently and lead to in two TLS
overlay links between JP and NP.

        JP                    NP
     ---------             ---------
     ATTACH_r1    ---->
<----    ATTACH_r2
     ATTACH_a2    ---->
<----    ATTACH_a1
         ICE-1 <--->
<--->    ICE-2
         TLS-1 <--->
<--->    TLS-2

Here is the problem. The draft does not define a heuristic to choose
one ATTACH/ICE/TLS among the two and drop the other.  For example, a
simple one could be comparing the transaction ID of both ATTACH as an
unsigned 64bit integer and drop the lesser one.

Any opinions on this?

Thanks

--Michael

---

From: Bruce Lowekamp <[email-masked]>
Date: Mon, 1 Nov 2010 07:57:16 -0700

I'm tempted to say it may be best to ignore this race condition---how
much harm does it really cause to have two connections?

To fix it, there's not only a race condition with simultaneous Attach,
but also a possible case where one peer has detected a failure of the
connection and tries to re-establish before the other realizes the
connection has failed.

Simply retaining the most recent connection to complete should work
fine in all situations---there shouldn't be a circumstance where both
peers do an immediate re-Attach, so if one accidentally drops the
connection, it should reconnect on a timer.

Another possibility would be implementing the connection table as a
multi-map and limiting the number of entries per peer to two.  That
seems like a pretty effective way to deal with this without
introducing too much additional complexity.

Otherwise, I think the heuristic you propose is probably fine.
Requires a bit more complexity in the implementation b/c you need to
remember the transaction ID for each connection in the connection
table, though I don't know if that's harder than other approaches.  I
think there would still be problems with one side noticing the failure
before the other, but that's no worse (and rarer) than restricting to
one connection.

I'd prefer to leave this as an implementation detail, maybe with some
text calling out the issue.

Bruce

On Mon, Nov 1, 2010 at 7:23 AM, Michael Chen <[email-masked]> wrote:
> _______________________________________________
> P2PSIP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/p2psip
>

---

From: Michael Chen <[email-masked]>
Date: Mon, 01 Nov 2010 15:15:57 -0800

What is the purpose of Section 9.4 step 8, where AP sends an UPDATE to NP.
Isn't that redundant since NP will receive the UPDATE sent from JP soon?
If step 8 is eliminated, the race condition is avoided.

--Michael

On 11/1/2010 6:57 AM, Bruce Lowekamp wrote:
> On Mon, Nov 1, 2010 at 7:23 AM, Michael Chen<[email-masked]>  wrote:
>> Hi,
>>
>>         ICE-1<--->
>>         TLS-1<--->

---

From: Bruce Lowekamp <[email-masked]>
Date: Tue, 2 Nov 2010 19:01:26 -0700

So I think we still ought to have some text somewhere about the
general case of simultaneous Attach.

However, in the case of the join process in 9.4, JP already sent
Attach requests to all of the peers in its neighbor table quite early
in the process (step 3 of the current draft).  I think there's the
possibility these may fail (or not complete quickly) and the
implementation moves on with the rest of the process, but I don't
think there's really a significant race condition in this case.

Bruce

---

From: Michael Chen <[email-masked]>
Date: Tue, 02 Nov 2010 19:59:29 -0800

Bruce,

As I said in the original post, the premise is JP uses the technique stated in
Section 11 of the draft (and discussed in the thread titled "Clarification of
initial attach procedure"), where JP did not PING and ATTACH to AP or NP before
sending JOIN to AP. Therefore, the race condition is highly likely when both
receive UPDATE from AP and discover that they are not connected, unless:

1) A duplicate ATTACH elimination heuristic is defined by the draft, which can
    stop one ATTACH from progressing to an ICE check and TLS overlay link; or

2) NP ignores the new predecessor (JP) in AP's UPDATE in anticipation of
    the UPDATE sent by JP if not already arrived.

Thanks

--Michael

On 11/2/2010 6:01 PM, Bruce Lowekamp wrote:
> On Mon, Nov 1, 2010 at 4:15 PM, Michael Chen<[email-masked]>  wrote:

---

From: Bruce Lowekamp <[email-masked]>
Date: Wed, 3 Nov 2010 07:27:29 -0700

inline

On Tue, Nov 2, 2010 at 8:59 PM, Michael Chen <[email-masked]> wrote:
> sending JOIN to AP.

I believe in the other thread, we concluded that Section 9.4 needs to
be revised to use Attach requests rather than Pings as currently
written.  However, the example in Section 11 currently has JP sending
Attach requests to both AP and NP as well as its entire finger table
before sending the Join.  Section 9.4, step 3 (of the current draft)
likewise has Attach requests being sent to the entire routing table
before the Join is sent.  I don't believe there's a problem here.

Bruce

> Therefore, the race condition is highly likely when both

---

From: Michael Chen <[email-masked]>
Date: Wed, 03 Nov 2010 11:22:07 -0800

On 11/3/2010 6:27 AM, Bruce Lowekamp wrote:
> inline
>
> On Tue, Nov 2, 2010 at 8:59 PM, Michael Chen<[email-masked]>  wrote:
>> Bruce,
>>
Thanks for explaining Section 9.4 and 11. The disparity in our implementation
is that JP does not ATTACH to NP, because NP will be in the UPDATE sent by AP
after accepting the JOIN from JP.  Only then will JP actually ATTACH to NP.
Looks like this approach doesn't offer too much optimization compared to JP
ATTACH to NP before JOIN.

However, the race condition is still possible of NP just joint the overlay
right before JP sending JOIN, in which case both JP and NP will show up in
the UPDATE sent to them by AP.

Thanks

--Michael

---

From: Michael Chen <[email-masked]>
Date: Wed, 03 Nov 2010 21:08:08 -0800

Bruce,

We are neglecting predecessors of AP. Let me re-frame this problem a bit as
follows:

JP is joining an overlay that looks like this: ...,P3,P2,P1,AP,S1,S2,S3,...
where AP will be the admitting peer of JP, P1 is the immediate predecessor
of AP, and S1 is the immediate successor of AP, etc.  Assume that JP has
ATTACH to AP via its bootstrap node (BP).

Join Method 1
=============
Using the technique described in Section 11 of base-11 draft, JP can ATTACH
to S1 using Resource-ID AP+1, to S2 using Resource-ID S1+1, and to S3 using
Resource-ID S2+1. JP has no means to find P1,P2,P3 before JOIN.

Then JP sends JOIN to AP and later receives UPDATE from AP. This UPDATE will
have the neighbor table: P2,P1,JP,AP,S1,S2,S3 (may be P3 as well). The same
UPDATE will also be sent by AP to P1, P2 and may be P3.  The JP entry in
this UPDATE is new to P1, P2 and P3, which will lead to these 3 peers to
ATTACH to JP. The same is true for JP.  The result is the race condition
we are talking about in this thread.

Join Method 2
=============
I am proposing this alternative in which JP does not attempt to ATTACH to
any of the successors of AP and send JOIN immediately after ATTACH to AP.
As usual, AP send STORE and followed by an UPDATE with the same neighbor
table: (P3),P2,P1,JP,AP,S1,S2,S3. Since all peers in this table except
AP are new to JP, JP starts to ATTACH to each of them one by one or
concurrently (advantage over method 1).

The same race condition still exist when S1,S2,S3,P1,P2,P3 receive UPDATE
from AP with the same neighbor table noting the new comer JP, which has
not ATTACH to any one of them.

I am in favor of method 2, because it is much easier to implement. JP
knows the exact Node-ID it needs to ATTACH.  No calculation is needed.
JP can ATTACH to all 6 peers simultaneously (ATTACH to S2 does not have
to wait for the completion of ATTACH to S1).

However, for either methods, the draft should address the race condition.
I believe a tie-breaker heuristic should be adopted by this draft. Here
are some possibilities:

1) Compare the transaction ID of two concurrent ATTACH as unsigned integer
and drop the lesser one and its resulting ICE check.

2) Compare the Node-ID of the two peers involved as unsigned integers and
drop the ATTACH initiated by the "lesser" peer.

3) Peers already in the overlay (S1,S2,S3,P1,P2,P3) never ATTACH to the
new immediate predecessor (JP) of the UPDATE sender (AP).

Thanks

--Michael

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 5 Nov 2010 08:03:22 -0700

Hi Michael,

Section 11 is an example, not normative. The normative description is in S
9.4.

In 9.4 (as revised by Bruce) you send ATTACHes to the expected routing table
entries. Eventually, we want JP to end up with connections to nodes around
the
overlay at predictable locations (the finger table) and to adjacent nodes
(the
neighbor table).

- The finger table can be formed directly by sending attaches.
- We discover the neighbor table by iteration.

This is done in step 3 (which will become step 2).

Step 7 and 8 result in JP attempting to connect to any neighbors he hasn't
connected
to in step 3 and similarly any such neighbors trying to form those
connections. With
chord, this should mainly just be the predecessor set of JP, which doesn't
seem so
bad. I would generally expect implementations to pace out their response to
updates
a bit (though I admit this isn't in the draft) so I'm not sure how many
simultaneous
connections you will get. I agree, however, that it makes sense to have a
tiebreaker
and I think smallest node-id is the logical one. [Note that if JP uses the
new
"send_update" flag, he can elicit an UPDATE from AP immediately and start
forming
the connections as soon as he ATTACHes].

WRT to the suggestion that you defer ATTACHes to the successor set prior to
receiving the UPDATE from AP, I agree that this makes the code somewhat
simpler
(though not that much), but at the cost of having JP have a quite incomplete
connection
set at the time it is allegedly part of the overlay, so I think that's a bad
tradeoff, so
I would prefer to leave that part of the algorithm as-is.

-Ekr

On Wed, Nov 3, 2010 at 10:08 PM, Michael Chen <[email-masked]>wrote:

>>> As I said in the original post, the premise is JP uses the technique
>>> stated
>>> in
>>> Section 11 of the draft (and discussed in the thread titled
>>> "Clarification
>>> of

---

From: Michael Chen <[email-masked]>
Date: Fri, 05 Nov 2010 15:14:55 -0800

Eric,

Using AttachReqAns.send_update is a fantastic idea. Brilliant!

Having AP send an UPDATE before JP send JOIN provides JP a precise set of
Node-IDs (S1,S2,S3,P1,P2,P3) to ATTACH.  The cost is an extra UPDATE
message, but it preempted the race condition (AP's predecessors included),
and JP can also do simultaneous attach to S1,S2,S3,P1,P2,P3. It's so worth it!

The AttachReqAns.send_update flag was added in base-10 back in August
of this year. Our code is quite old.  Thanks for the pointer.

I am also glad that we are in agreement on defining a tie-breaker heuristic
based on Node-ID comparison to address the race condition.  We should
move ahead to add it into the next draft.

--Michael

On 11/5/2010 7:03 AM, Eric Rescorla wrote:
> Hi Michael,
>
> Section 11 is an example, not normative. The normative description is in S 9.4.
>
> entries. Eventually, we want JP to end up with connections to nodes around the
> overlay at predictable locations (the finger table) and to adjacent nodes (the
> neighbor table).
>
> and I think smallest node-id is the logical one. [Note that if JP uses the new
> "send_update" flag, he can elicit an UPDATE from AP immediately and start forming
> receiving the UPDATE from AP, I agree that this makes the code somewhat simpler
> On Wed, Nov 3, 2010 at 10:08 PM, Michael Chen <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Bruce,
>
>         On Tue, Nov 2, 2010 at 8:59 PM, Michael Chen<[email-masked]
>         <mailto:[email-masked]>>  wrote:
>
>             Bruce,
>
>             As I said in the original post, the premise is JP uses the
>             technique stated
>             in
>             initial attach procedure"), where JP did not PING and ATTACH to AP
>             or NP
>             before
>             sending JOIN to AP.
>
>     [email-masked] <mailto:[email-masked]>

---

From: Bruce Lowekamp <[email-masked]>
Date: Sun, 7 Nov 2010 14:21:28 -0800

> of this year. Our code is quite old.  Thanks for the pointer.

We should probably update the description of how Update is used, since
JP isn't technically a peer at this point, but I think this is the
best solution here, given the current protocol.

> move ahead to add it into the next draft.

Node-ID makes a good comparison, but I think the issue of when to
apply it to terminate one of two duplicate connections is much more
complicated.  Would need to make sure that both sides perceive they
have duplicate active connections.  For example, if A and B are
connected and A believes the connection to B is dead, but B hasn't
detected it yet, it would be bad if B drops A's attempt to
re-establish the connection because it disagrees about the connection
state.

I still believe the protocol complexity to handle these situations
properly is not worth the benefit.

Bruce

---

From: Michael Chen <[email-masked]>
Date: Mon, 08 Nov 2010 20:53:00 -0800

On 11/7/2010 2:21 PM, Bruce Lowekamp wrote:
> On Fri, Nov 5, 2010 at 4:14 PM, Michael Chen<[email-masked]>  wrote:
>> Eric,
>>
This tie-breaker heuristic will only be use to eliminate concurrent ATTACH
and prevent the ensuing ICE check and TLS session. Here are the details:

Scenario-1 (Unconditional Rejection)
==========
Peer-A sends ATTACH to Peer-B and receives its reply. Then Peer-A receives
an ATTACH sent by Peer-B. Peer-A unconditionally rejects this ATTACH from
Peer-B and continue with the ICE check and TLS session derived from the
ATTACH initiated by Peer-A itself. No tie-breaker heuristic is applied.

Scenario-2 (Heuristic-based Rejection)
==========
Peer-A and Peer-B sends ATTACH to each other and simultaneously receive
the ATTACH request from the other before receiving the reply to its own
request. Both Peer-A and Peer-B apply the tie-breaker heuristic using
their Node-IDs as unsigned integers. Both Peer-A and Peer-B MUST reject
the ATTACH request sent by the peer with the smaller Node-ID and allow
the other ATTACH and its ensuing ICE check and TLS session to complete.

Using these two rejection rules, there will never be duplicate ICE check
and TLS links between any two peers.  What do you think?

Thanks

--Michael

---

From: Bruce Lowekamp <[email-masked]>
Date: Thu, 11 Nov 2010 22:33:49 -0800

I think heuristic 2 could work, though we should add something about a
node not initiating a new Attach request if one is in progress.  I'm
sort of neutral on whether it's worth the effort here, but I think
it's fairly minimal and won't break anything.

Bruce

On Mon, Nov 8, 2010 at 8:53 PM, Michael Chen <[email-masked]> wrote:
>>> and JP can also do simultaneous attach to S1,S2,S3,P1,P2,P3. It's so
>>> worth
>>> it!
>>>