tipc-discussion

Re: [tipc-discussion] [PATCH net-next 0/3] fix broadcast sync issue

[Jon M. <jon...@er...>]

On 03/08/2013 01:10 PM, jason wrote:
> 在 2013-3-8 下午11:14，"Jon Maloy" <jon...@er...>写道：
>>
>> On 03/07/2013 11:15 PM, jason wrote:
>>> Hi Jon,
>>>
>>> And my solution to the "random acknowledge number" problem is just
> simply
>>> reversing the following piece of patch of the new bcast sync mechanism:
>>>
>>> @@ -2058,9 +2059,11 @@ static void link_recv_proto_msg(struct tipc_link
>>> *l_ptr, struct sk_buff *buf) l_ptr->max_pkt = l_ptr->max_pkt_target; }
>>> l_ptr->owner->bclink.supportable = (max_pkt_info != 0); +
>>> l_ptr->owner->bclink.sync = msg_bclink_sync(msg);
>>>
>>> /* Synchronize broadcast link info, if not done previously */- if
>>> (!tipc_node_is_up(l_ptr->owner)) { + if (!tipc_node_is_up(l_ptr->owner)
> &&
>>> + !l_ptr->owner->bclink.sync) { l_ptr->owner->bclink.last_sent =
>>> l_ptr->owner->bclink.last_in = msg_last_bcast(msg);
>>
>> Hi jason,
>>
>> You are clearly not looking at the current code version at netdev.
>> There are no "supported" or "sync" flags in that version.
>>
>> The scenario you have in mind really goes like this:
>>
>>     0: Node A has next_out_no N, Node B has next_out_no M
>>
>>     1: Node A sends an ACTIVATE message to B, where last_bcast = N -1,
>>        effectively telling B it to start acking broadcast packets from
> that
>>        sequence number.
>>
>>     2: Node B receives the ACTIVATE, activates its link endpoint, and
>>         sets next_in = N -1.
>>         Note that B is not open for receiving broadcasts yet, and does not
>>         know where to start receiving. It only knows which bcast_ack value
>>         to  send in its unicasts.
>>
>>    ( 2.5: Node A and B may now send out more broadcasts, but A doesn't
>>         expect any acknowledges from A, or vice versa, since neither node
> is
>>        in the peer's broadcast receiver's list.
>>        Below, I'll assume that no broadcasts are sent, since this doesn't
>>        affect the reasoning.)
>>
>>     3: Node B sends a BCAST_SYNC as *first* unicast message to A. This
>>        message contains bcast_ack = N -1 ,  and last_bcast = M - 1,
>>        meaning that A should start receiving from M.
>>
>>     4: Node A receives the BCAST_SYNC message and opens up to start
>>        receiving from packet M from node B, setting last_in = M -1.
>>        The bcast_ack value from B  is ignored, since it is lower than N.
>>
>>       We are now in the the situation you describe in your example.
>>       As you see, all values are strictly defined and valid.
>>
>>
>>
>>      5: Node B goes on sending NAME_DISTR messages after the BCAST_SYNC
>>         was sent. Those will all contain bcast_ack = N -1, since B cannot
>>         have received any broadcast messages until it has received its own
>>         BCAST_SYNC. All those acks will be ignored by A, as described
> above.
>>
>>      6: Node B may now also send broadcasts M, M + 1 etc. to A, which A
>>         will receive and deliver, but A will send no acks before its  own
>>        BCAST_SYNC has been sent out.
>>
> Here I would like to ask a question. Assume node A spend a lot of time
> before sending its own BCAST_SYNC out (not to say tipc-2.0, but say
> tipc-1.7.7 which send nametable over unicast link before sending BCAST_SYNC
> out) There will be an possibility that Node B's bcast out queue window
> becomes full if B broadcast many messages at the same time, because B
> ignored any bcast_ack from A until B got BCAST_SYNC from A. Right?
> 
> In my opinion, here B shall not ignored bcast_ack from A before B got
> BCAST_SYNC from A. More general, getting a BCAST_SYNC from peer (set
> recv_permitted = true ) is just a signal for openning up our receiving,  it
> shall not prevent us from processing peer's acknowledge which is a matter
> of our sending. This is not a case for tipc-2.0 which does not have
> nametable unicasting between link up and sending BCAST_SYNC, but it is much
> more important to tipc-1.7.7. Please consider it. Thank you!

Good point. It looks like condition on recv_permitted we do before 
we  call tipc_bclink_acknowledge() we do in tipc_revc_msg ()
is not necessary. The bcast_acks coming in at this stage
are valid, and no harm is done if they result in released packets.
Eventually we'll have to do the same in tipc 2.0, when we introduce
multicast name table update.

///jon

> 
>>      7: Node A sends a BCAST_SYNC as first unicast message to B. It
> carries
>>         bcast_ack = M - 1  (or M + x  if some broadcasts were received).
>>         This is now a valid ack value.  last_bcast = N - 1 (disregarding
> that A may
>>        already have  sent N, N+1 etc)
>>
>>      8: Node B receives the BCAST_SYNC, finds it can (and must) start
>>         receiving from N, and open up for reception. If A has already
>>         sent N + 1,  N + 2 etc, Node B will either have them in its
>>         deferred queue, or it will have to ask for retransmission.
>>
>>
>> I hope this answers your concern.
>>
>> Regards
>> ///jon
>>
>>>
>>> Therefore, we early set last_in to a valit value from peer as soon as
>>> possible to prevent it remains a invalid value.
>>> 在 2013-3-8 上午9:03，"jason" <huz...@gm...>写道：
>>>
>>>> Hi Jon,
>>>>
>>>> Just a quick resend of my previous mail( to make my point clear.)
>>>>
>>>> Node A just update B.acked as its next_out_no when it found out node B
> is
>>>> up(node A calls node_established_contact()). But it seems there is
> nothing
>>>> can prevent B from carry a acknowledge lower than that. It may be a
> random
>>>> number which occasionally greater than that until B finally init its
>>>> last_in at the time that B  got BCAST_SYNC message from A(B calls
>>>> tipc_bclink_info_recv()).
>>>> 在 2013-3-8 上午7:27，"jason" <huz...@gm...>写道：
>>>>
>>>>> Hi Jon,
>>>>> Node A just update B.acked as its next_out_no when it found out node
> B is
>>>>> up. But it seems there is nothing can prevent B from carry a
> acknowledge
>>>>> lower than that. It may be a random number which occasionally greater
> than
>>>>> it.
>>>>>  在 2013-3-8 上午6:22，"Jon Maloy" <jon...@er...>写道：
>>>>>
>>>>>> On 03/06/2013 01:27 AM, Ying Xue wrote:
>>>>>>> On 03/06/2013 11:41 AM, jason wrote:
>>>>>>>> Hi All,
>>>>>>>> Let's say there are to nodes in cluster ,nodeA and nodeB. There is
>>>>>>>> possibility that A has opened bcast receiving for B while B hasen't
>>>>>>>> opened bcast receiving for A. Therefore, B hasen't sync its
> last_in to
>>>>>>>> what A has sent ,then every messages sent by B will carry a invalid
>>>>>>>> bcast acked seq number for A.
>>>>>>
>>>>>>>> Because A has open bcast receiving for B,
>>>>>>>> it will process those invalid acks from B in
>>>>>> tipc_bclink_acknowlegde().
>>>>>>
>>>>>> No it won't.
>>>>>> The broadcast themselves don't carry valid acknowledges, since there
> is
>>>>>> no single node to acknowledge.
>>>>>> Unicasts B -> A will carry acknowledges, but those will be ignored
> by A
>>>>>> because they will be lower than the lowest acknowledge value A can
> accept
>>>>>> from B. A knows that value; it is A's "next_out_no" value at the
> moment
>>>>>> it opened for reception. (And sent its own BCAST_SYNC message).
>>>>>>
>>>>>> Regards
>>>>>> ///jon
>>>>>>
>>>>>>>> It seems may cause problem I think. Please consider this.
>>>>>>>>
>>>>>>>> On Jan 31, 2013 6:06 PM, "Ying Xue" <yin...@wi...
>>>>>>>> <mailto:yin...@wi...>> wrote:
>>>>>>>
>>>>>>> No, it's possible for you not to completely understand the root
> cause.
>>>>>>> Of course, I admit it's is a hard thing to clearly know every detail
>>>>>>> things. A least, after a while, I almost forgot why it happens and
> what
>>>>>>> reason is.
>>>>>>>
>>>>>>> the key reason why it appears is that TIPC does not properly cope
> with
>>>>>>> the sync problem between unicat link and multicast link. Even if one
>>>>>>> unicast link is set up by sending link state message via unicast
>>>>>>> channel, link states on both endpoints are not sync immediately due
> to
>>>>>>> distribution environment.  For example, there have two nodes, one
>>>>>> sender
>>>>>>> of sending multicast messages and one message receiver respectively.
>>>>>>> Suddenly one new node joins the cluster as another multicast
> messages
>>>>>>> receiver. As the link sate between new receiver and the sender is
> not
>>>>>>> sync timely, for instance, the sender still thinks there only has
> one
>>>>>>> receiver although the new receiver actually starts to receive the
>>>>>>> multicast messages sent by the sender at the moment. That means,
> during
>>>>>>> the time of link state being inconsistent sender can release
> message in
>>>>>>> its outbound queue as long as it receives one ack from one of the
> two
>>>>>>> receivers. In normally there has no big problem. But if one receiver
>>>>>>> finds one message is missed from a series of sequential received
>>>>>>> packets, it then sends retransmission request to ask the sender to
> send
>>>>>>> the missed packet again. But the missed packet has been released by
>>>>>>> sender as the sender already received an ack of the missed packet
> from
>>>>>>> another receiver. Therefore, sender cannot send out the missed
> packet
>>>>>>> for ever, however, the receiver must receive the missed packet. So
>>>>>>> deadlock happens.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>
>>
> 

Re: [tipc-discussion] [PATCH net-next 0/3] fix broadcast sync issue

[Jon M. <jon...@er...>]

On 03/08/2013 11:06 AM, jason wrote:
> Hi Jon,
> Thank you for the detailed explanation very much. It is the step 2 that
> answered my concern. In step 2 of your scenario, if node B do not set
> next_in = N -1, then B will have the invalid bcast_ack issue that I
> described.

You're welcome. 
It was actually a useful exercise for me to revisit the algorithm,
because I spotted something else that we probably should fix.

At step 7 in my description (pasted in below) I realized that node B
may receive broadcast packets that were sent from A *before* the link
was established. Sequence number N in the example is the state when
A sends out its ACTIVATE message, not the state when the link is 
established in A and the BCAST_SYNC is sent.

This will work fine, of course, and I am not sure it is a real problem.
But it would probably be more correct to let BCAST_SYNC carry a 
last_bcast = (N + x) instead, i.e. the value of next_out_no -1 at the 
moment of establishing the link. I'll have to consider this.

Regards
///jon

> 
> I am currently using tipc-1.7.7 and  assume that Ying's patch at the
> beginning of this thread is the final version for tipc-1.7.7 to introduce
> this new bcast sync mechanism, so all my concerns are base on tipc-1.7.7
> plus this patch. Do you have plan to update 1.7.7 to include the final
> version of this new bcast sync mechanism in future? Or I have to switch to
> netdev version to have it?
> 
I think Ying is the right person to answer on this.

///jon

0: Node A has next_out_no N, Node B has next_out_no M

    1: Node A sends an ACTIVATE message to B, where last_bcast = N -1,
       effectively telling B it to start acking broadcast packets from that
       sequence number.

    2: Node B receives the ACTIVATE, activates its link endpoint, and
        sets last_in = N -1.
        Note that B is not open for receiving broadcasts yet, and does not 
        know where to start receiving. It only knows which bcast_ack value 
        to  send in its unicasts.

   ( 2.5: Node A and B may now send out more broadcasts, but A doesn't 
        expect any acknowledges from A, or vice versa, since neither node is
       in the peer's broadcast receiver's list.
       Below, I'll assume that no broadcasts are sent, since this doesn't
       affect the reasoning.)

    3: Node B sends a BCAST_SYNC as *first* unicast message to A. This 
       message contains bcast_ack = N -1 ,  and last_bcast = M - 1, 
       meaning that A should start receiving from M.

    4: Node A receives the BCAST_SYNC message and opens up to start 
       receiving from packet M from node B, setting last_in = M -1.  
       The bcast_ack value from B  is ignored, since it is lower than N.  

      We are now in the the situation you describe in your example.
      As you see, all values are strictly defined and valid.



     5: Node B goes on sending NAME_DISTR messages after the BCAST_SYNC
        was sent. Those will all contain bcast_ack = N -1, since B cannot
        have received any broadcast messages until it has received its own
        BCAST_SYNC. All those acks will be ignored by A, as described above.

     6: Node B may now also send broadcasts M, M + 1 etc. to A, which A 
        will receive and deliver, but A will send no acks before its  own 
       BCAST_SYNC has been sent out.

     7: Node A sends a BCAST_SYNC as first unicast message to B. It carries 
        bcast_ack = M - 1  (or M + x  if some broadcasts were received). 
        This is now a valid ack value.  last_bcast = N - 1 (disregarding that A may 
       already have  sent N, N+1 etc)

     8: Node B receives the BCAST_SYNC, finds it can (and must) start 
        receiving from N, and open up for reception. If A has already
        sent N + 1,  N + 2 etc, Node B will either have them in its
        deferred queue, or it will have to ask for retransmission.

Re: [tipc-discussion] [PATCH net-next 0/3] fix broadcast sync issue

[Jon M. <jon...@er...>]

On 03/08/2013 01:44 PM, Jon Maloy wrote:
> On 03/08/2013 11:06 AM, jason wrote:
>> Hi Jon,
>> Thank you for the detailed explanation very much. It is the step 2 that
>> answered my concern. In step 2 of your scenario, if node B do not set
>> next_in = N -1, then B will have the invalid bcast_ack issue that I
>> described.
> 
> You're welcome. 
> It was actually a useful exercise for me to revisit the algorithm,
> because I spotted something else that we probably should fix.
> 
> At step 7 in my description (pasted in below) I realized that node B
> may receive broadcast packets that were sent from A *before* the link
> was established. Sequence number N in the example is the state when
> A sends out its ACTIVATE message, not the state when the link is 
> established in A and the BCAST_SYNC is sent.
> 
> This will work fine, of course, and I am not sure it is a real problem.
> But it would probably be more correct to let BCAST_SYNC carry a 
> last_bcast = (N + x) instead, i.e. the value of next_out_no -1 at the 
> moment of establishing the link. I'll have to consider this.

Forget about this mail. Looking closer at the code, I find that it 
already works this way. I missed that node->bcast.acked is updated 
when the link is established, and that is the value sent in BCAST_SYNC.

///jon

> 
> Regards
> ///jon
> 
>>
>> I am currently using tipc-1.7.7 and  assume that Ying's patch at the
>> beginning of this thread is the final version for tipc-1.7.7 to introduce
>> this new bcast sync mechanism, so all my concerns are base on tipc-1.7.7
>> plus this patch. Do you have plan to update 1.7.7 to include the final
>> version of this new bcast sync mechanism in future? Or I have to switch to
>> netdev version to have it?
>>
> I think Ying is the right person to answer on this.
> 
> ///jon
> 
> 0: Node A has next_out_no N, Node B has next_out_no M
> 
>     1: Node A sends an ACTIVATE message to B, where last_bcast = N -1,
>        effectively telling B it to start acking broadcast packets from that
>        sequence number.
> 
>     2: Node B receives the ACTIVATE, activates its link endpoint, and
>         sets last_in = N -1.
>         Note that B is not open for receiving broadcasts yet, and does not 
>         know where to start receiving. It only knows which bcast_ack value 
>         to  send in its unicasts.
> 
>    ( 2.5: Node A and B may now send out more broadcasts, but A doesn't 
>         expect any acknowledges from A, or vice versa, since neither node is
>        in the peer's broadcast receiver's list.
>        Below, I'll assume that no broadcasts are sent, since this doesn't
>        affect the reasoning.)
> 
>     3: Node B sends a BCAST_SYNC as *first* unicast message to A. This 
>        message contains bcast_ack = N -1 ,  and last_bcast = M - 1, 
>        meaning that A should start receiving from M.
> 
>     4: Node A receives the BCAST_SYNC message and opens up to start 
>        receiving from packet M from node B, setting last_in = M -1.  
>        The bcast_ack value from B  is ignored, since it is lower than N.  
> 
>       We are now in the the situation you describe in your example.
>       As you see, all values are strictly defined and valid.
> 
> 
> 
>      5: Node B goes on sending NAME_DISTR messages after the BCAST_SYNC
>         was sent. Those will all contain bcast_ack = N -1, since B cannot
>         have received any broadcast messages until it has received its own
>         BCAST_SYNC. All those acks will be ignored by A, as described above.
> 
>      6: Node B may now also send broadcasts M, M + 1 etc. to A, which A 
>         will receive and deliver, but A will send no acks before its  own 
>        BCAST_SYNC has been sent out.
> 
>      7: Node A sends a BCAST_SYNC as first unicast message to B. It carries 
>         bcast_ack = M - 1  (or M + x  if some broadcasts were received). 
>         This is now a valid ack value.  last_bcast = N - 1 (disregarding that A may 
>        already have  sent N, N+1 etc)
> 
>      8: Node B receives the BCAST_SYNC, finds it can (and must) start 
>         receiving from N, and open up for reception. If A has already
>         sent N + 1,  N + 2 etc, Node B will either have them in its
>         deferred queue, or it will have to ask for retransmission.
> 
> 
> 
> ------------------------------------------------------------------------------
> Symantec Endpoint Protection 12 positioned as A LEADER in The Forrester  
> Wave(TM): Endpoint Security, Q1 2013 and "remains a good choice" in the  
> endpoint security space. For insight on selecting the right partner to 
> tackle endpoint security challenges, access the full report. 
> http://p.sf.net/sfu/symantec-dev2dev
> _______________________________________________
> tipc-discussion mailing list
> tip...@li...
> https://lists.sourceforge.net/lists/listinfo/tipc-discussion
>