Subject: [p2p-sip] Possible infinite loop in draft-bryan-sipping-p2p-02

From: jf.wauthy at gmail.com (Jean-François Wauthy)
Date: Tue, 3 Oct 2006 15:05:03 +0200

Hi,

I'm currently trying to prototype draft-bryan-sipping-p2p-02 and have run
into what could be a big issue:

If you take the simple network used in the example (section 11), start with
only node 3 connected and add node 10. After joining the overlay, node 10
state is the following:

 - predecessor: 3
 - successor: 3

Just after node 10 joining the overlay (and before stabilizing) node 3 state
is:

 - predecessor: 10
 - successor: 3

Then, stabilization begins and node 3 discovers its successor is now 10, it
updates that information and sends a REGISTER structured as if it is
entering the system to node 10 (subsection 9.8). Node 10 receives the
message and answers with a 302 response to redirect the request to node 3
because it doesn't manage the registering node id. Node 3 state is now:

 - predecessor: 10
 - successor: 10

Thus, node 3 performs registration with itself and must set its successor to
be the admitting node and its predecessor to be the admitting node's
predecessor (subsection 9.4). Therefore node 3 state becomes:

 - predecessor: 10
 - successor: 3

The joining process finishes by performing a stabilization (as strongly
suggested at the end of 8.2.2.2) which discovers that node 10 is the actual
successor of node 3 and the same process starts looping infinitely.

Did i miss something ?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://lists.cs.columbia.edu/pipermail/p2p-sip/attachments/20061003/5beb7e6c/attachment.html

---

From: enrico.marocco at telecomitalia.it (Enrico Marocco)
Date: Tue, 03 Oct 2006 15:28:55 +0200

Jean-Fran?ois Wauthy wrote:
> I'm currently trying to prototype draft-bryan-sipping-p2p-02 and have 
> run into what could be a big issue:

Actually that draft has many open issues.  In fact, other than leading 
to loops as happened to you, it doesn't even deal with failures.  It is 
likely that it will be fixed in the future; in the meantime, you could 
think about possible solutions and propose them.  The sipdht project is 
an attempt to do that too.

--
Ciao,
Enrico

Ahem.. Sorry, the notice below is not my fault :-(
--------------------------------------------------------------------

CONFIDENTIALITY NOTICE

This message and its attachments are addressed solely to the persons above and may contain confidential information. If you have received the message in error, be informed that any use of the content hereof is prohibited. Please return it immediately to the sender and delete the message. Should you have any questions, please contact us by replying to webmaster at telecomitalia.it.

        Thank you

                                        www.telecomitalia.it

--------------------------------------------------------------------

---

From: marcia at sipeerior.com (Marcia Z Bryan)
Date: Mon, 9 Oct 2006 16:27:49 -0400

I think part of the problem you are experiencing is that all of the
startup/base cases haven't explicitly been dealt with in the draft.  Also in
the course of building our company's implementation, I've found two errors
in the draft that might cause some confusion.

STARTUP/BASE cases:

- The draft fails to discuss intervals that contain NULL predecessors.  When
the 2nd node is joining the system, the admitting node (original node) in
the system has to determine if the joining node's node ID  is between the
admitting node's predecessor ID and the admitting node's ID.  In this case,
the admitting node's predecessor is NULL.  The draft should, but does not
currently, state the following in section 9.4:

"...the admitting node MUST reply with a 200 response if the joining node
has a Node-ID between the admitting node's predecessor's Node-ID and the
admitting node's Node-ID or if the admitting node's predecessor's Node-ID is
NULL."

- Likewise, when the 2nd node joining the system receives a 200 response
from the other node in the system, the 200 response will have a NULL
predecessor (or no predecessor at all? This needs to be made explicit in the
draft) in the response.  So the joining node will set it's predecessor =
NULL.

ERRORS:

- In section 9.4, Node admission, there is a typo error that switches the
order of the interval that the admitting node uses to determine if a 200
response should be generated.  The draft currently says

"When handling an initial join from a node, the admitting node MUST reply
with a 200 response if the joining node has a Node-ID between the admitting
node's Node-ID and the admitting node's predecessor's Node-ID."

but what it should say (including the earlier change I mentioned) is:

"When handling an initial join from a node, the admitting node MUST reply
with a 200 response if the joining node has a Node-ID between the admitting
node's predecessor's Node-ID and the admitting node's Node-ID or if the
admitting node's predecessor's Node-ID is NULL."

 To summarize:

Check if joining node's Node-ID is in (admitting node's Node-ID, admitting
node's predecessor's ID) should be replaced with check if joining node's
Node-ID is in (admitting node's predecessor's ID, admitting node's Node-ID)

- The second is more of an unclear statement than an error.  It deals with
the Chord Periodic Stabilization in section 9.8.  The draft currently says
"If it is not, the node MUST update their own successor with the predecessor
returned, and additionally MUST send a REGISTER to this node, structured as
if the stabilizing node had just entered the system. This will serve to
properly update the overlay. This is analogous to the notify procedure in
Chord."

What is confusing here is that the stabilizing node does not process the
response to this register as a joining node would. Rather, the stabilizing
node ignores the response to the REGISTER (though it may do something if it
doesn't receive a 200??).  The REGISTER sent by the stabilizing node serves
only as a notify.

Here's just a summary of what should happen for Node Admission and Chord
Periodic Stabilization:

Node Admission:
1) Joining Node Tasks: send REGISTER to admitting node and wait for 200
response
     a) set joining node's successor = admitting node
     b) set joining node's predecessor = admitting node's predecessor (this
can be NULL)
2) Admitting Node Tasks: check if joining node's Node-ID is in (admitting
node's predecessor's Node-ID, admitting node's Node-ID)
     a) if yes or if admitting node's predecessor == NULL
         - send 200 response with successor and predecessor in the message
         - set admitting  node's predecessor = joining node
     b) else, send 302

Chord Periodic Stabilization:
1) Stabilizing Node's Tasks:  query successor for successor's Node-ID and
check to see if successor's predecessor returned in the response is equal to
stabilizing node
    a) if predecessor in response message  == stabilizing node, great, move
along nothing to do here...
    b) but if predecessor in response message != stabilizing node
         - set stabilizing node's successor = predecessor in response
message
         - stabilizing node sends REGISTER to predecessor in response
message (and does nothing with the response)
2) (If REGISTER sent by stabilizing node)  Notified Node's Tasks:  check if
stabilizing node's Node-Id is in (notified node's predecessor's Node-Id,
notified node's Node-Id)
     a) if yes, then set notified node's predecessor = stabilizing node

Now here's an example of how this works:

1) Node 3 Starts overlay.
   Node 3 State--> Succ= 3, Pred = NULL

2) Node 10 joins system (asks node 3 for admission)
   Node 3 State--> Succ = 3, Pred = 10
   Node 10 State-->Succ = 3, Pred = NULL

3) Node 10 runs periodic stabilization
    Node 3 State--> Succ = 3, Pred = 10
    Node 10 State--> Succ = 3, Pred = NULL

4) Node 3 runs periodic stabilization
   Node 3 State--> Succ = 10, Pred = 10
   Node 10 State--> Succ = 3, Pred = 3

5) Node 14 joins the system
    Node 3 State--> Succ = 10, Pred = 14
    Node 10 State--> Succ = 3, Pred = 3
    Node 14 State--> Succ = 3, Pred = 10

6) Node 14 runs periodic stabilization
    Node 3 State--> Succ = 10, Pred = 14
    Node 10 State--> Succ = 3, Pred = 3
    Node 14 State--> Succ = 3, Pred = 10

7) Node 10 runs periodic stabilization
    Node 3 State--> Succ = 10, Pred = 14
    Node 10 State--> Succ = 14, Pred = 3
    Node 14 State--> Succ = 3, Pred = 10

--Marcia

On 10/3/06, Jean-Fran?ois Wauthy <jf.wauthy at gmail.com> wrote:
> If you take the simple network used in the example (section 11), start
> with only node 3 connected and add node 10. After joining the overlay, node
> 10 state is the following:
>
>  - predecessor: 3
>  - successor: 3
>
> Just after node 10 joining the overlay (and before stabilizing) node 3
> state is:
>
>  - predecessor: 10
>  - successor: 3
>
> Then, stabilization begins and node 3 discovers its successor is now 10,
> it updates that information and sends a REGISTER structured as if it is
> Thus, node 3 performs registration with itself and must set its successor
> to be the admitting node and its predecessor to be the admitting node's
> suggested at the end of 8.2.2.2) which discovers that node 10 is the
> actual successor of node 3 and the same process starts looping infinitely.
>
> Did i miss something ?
>
> _______________________________________________
> p2p-sip mailing list
> p2p-sip at cs.columbia.edu
> https://lists.cs.columbia.edu/cucslists/listinfo/p2p-sip
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://lists.cs.columbia.edu/pipermail/p2p-sip/attachments/20061009/e6850a32/attachment-0001.html