Re: [6tisch] Handling Inconsistent Allocation in 6P

[Yasuyuki Tanaka]

Hi Qin,


I think nodeA=>nodeB request process includes two parts, one is Tx
from nodeA to nodeB, another part is for nodeB's MAC to process the
Request message. As you mentioned, failure of the first part can be
identified by mac-ack from nodeB, but not the second part. Right?


Yes, that's right! I believe we are now on the same page about the
approach using timeout.

In this sense, ability to identify failure without inconsistency
occurred in the second part is the only advantage of the generation
counter, which is achieved by consuming four bits in every 6P packet
and keeping inter-transaction state for every neighbor. In my opinion,
this advantage is a little thing for the price to pay...

Best,
Yatch


On 2016/12/01 21:45, Qin Wang wrote:

Hi Yasuyuki,

I think nodeA=>nodeB request process includes two parts, one is Tx from nodeA 
to nodeB, another part is for nodeB's MAC to process the Request message. As you 
mentioned, failure of the first part can be identified by mac-ack from nodeB, but 
not the second part. Right?

Thanks
Qin


On Wednesday, November 30, 2016 1:49 PM, Yasuyuki Tanaka 
 wrote:


Thanks, Qin.


(1) Timeout in nodeA can be triggered either by failure in
nodeA=>nodeB request process and by failure in nodeB=>nodeA response
process (i.e the process in above example). nodeA cannot tell exact
reason for a event of Timeout by itself. In another word, nodeA
cannot tell there is a inconsistency between its schedule and
nodeB's schedule just based on Timeout. Right?


That is right; failure in the nodeA=>nodeB case is what I called
"false positive." But, nodeA could lower the possibility of false
positive by using MAC-layer ACK, implementation efforts. If nodeA
doesn't receive a MAC-layer ACK to its request frame, nodeA can
consider the transaction as having failed without inconsistency.


(2) sending CLEAR, or STATUS, or LIST usually happens after a
inconsistency is found, and the function of generation counter is
exactly to find out the inconsistency. Make sense?


I'd say the generation counter is not the only way to detect
inconsistency. STATUS/LIST could detect it as well, although
STATUS/LIST always fails with RC_ERR_GEN in a case of inconsistency
according to the latest draft.

The generation counter can find inconsistency as you mentioned, but it
has disadvantages:

- It needs 6P to keep per-neighbor states (ignore SeqNum for now) even
  when there is no ongoing transaction.

- It cannot detect inconsistency until a subsequent transaction; it
  may take a long time.

The reactive approach using timeout doesn't have such disadvantages;
furthermore, it's simpler than the the schedule generation management,
in my opinion.

I still cannot see why the generation management at 6P is really needed...

Best,
Yatch


___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Qin Wang]

Hi Yasuyuki,
I think nodeA=>nodeB request process includes two parts, one is Tx from nodeA 
to nodeB, another part is for nodeB's MAC to process the Request message. As 
you mentioned, failure of the first part can be identified by mac-ack from 
nodeB, but not the second part. Right?
ThanksQin  

On Wednesday, November 30, 2016 1:49 PM, Yasuyuki Tanaka 
 wrote:
 

 Thanks, Qin.

> (1) Timeout in nodeA can be triggered either by failure in
> nodeA=>nodeB request process and by failure in nodeB=>nodeA response
> process (i.e the process in above example). nodeA cannot tell exact
> reason for a event of Timeout by itself. In another word, nodeA
> cannot tell there is a inconsistency between its schedule and
> nodeB's schedule just based on Timeout. Right?

That is right; failure in the nodeA=>nodeB case is what I called
"false positive." But, nodeA could lower the possibility of false
positive by using MAC-layer ACK, implementation efforts. If nodeA
doesn't receive a MAC-layer ACK to its request frame, nodeA can
consider the transaction as having failed without inconsistency.

> (2) sending CLEAR, or STATUS, or LIST usually happens after a
> inconsistency is found, and the function of generation counter is
> exactly to find out the inconsistency. Make sense?

I'd say the generation counter is not the only way to detect
inconsistency. STATUS/LIST could detect it as well, although
STATUS/LIST always fails with RC_ERR_GEN in a case of inconsistency
according to the latest draft.

The generation counter can find inconsistency as you mentioned, but it
has disadvantages:

- It needs 6P to keep per-neighbor states (ignore SeqNum for now) even
  when there is no ongoing transaction.

- It cannot detect inconsistency until a subsequent transaction; it
  may take a long time.

The reactive approach using timeout doesn't have such disadvantages;
furthermore, it's simpler than the the schedule generation management,
in my opinion.

I still cannot see why the generation management at 6P is really needed...

Best,
Yatch

On 2016/11/30 17:39, Qin Wang wrote:
> Hi Yasuyuki,
>
> (1) Timeout in nodeA can be triggered either by failure in nodeA=>nodeB 
> request process and by failure in nodeB=>nodeA response process (i.e the 
> process in above example). nodeA cannot tell exact reason for a event of 
> Timeout by itself. In another word, nodeA cannot tell there is a 
> inconsistency between its schedule and nodeB's schedule just based on 
> Timeout. Right?
>
> (2) sending CLEAR, or STATUS, or LIST usually happens after a inconsistency 
> is found, and the function of generation counter is exactly to find out the 
> inconsistency. Make sense?
>
> Thanks
> Qin

___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch


   ___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Yasuyuki Tanaka]

Thanks, Qin.


(1) Timeout in nodeA can be triggered either by failure in
nodeA=>nodeB request process and by failure in nodeB=>nodeA response
process (i.e the process in above example). nodeA cannot tell exact
reason for a event of Timeout by itself. In another word, nodeA
cannot tell there is a inconsistency between its schedule and
nodeB's schedule just based on Timeout. Right?


That is right; failure in the nodeA=>nodeB case is what I called
"false positive." But, nodeA could lower the possibility of false
positive by using MAC-layer ACK, implementation efforts. If nodeA
doesn't receive a MAC-layer ACK to its request frame, nodeA can
consider the transaction as having failed without inconsistency.


(2) sending CLEAR, or STATUS, or LIST usually happens after a
inconsistency is found, and the function of generation counter is
exactly to find out the inconsistency. Make sense?


I'd say the generation counter is not the only way to detect
inconsistency. STATUS/LIST could detect it as well, although
STATUS/LIST always fails with RC_ERR_GEN in a case of inconsistency
according to the latest draft.

The generation counter can find inconsistency as you mentioned, but it
has disadvantages:

- It needs 6P to keep per-neighbor states (ignore SeqNum for now) even
  when there is no ongoing transaction.

- It cannot detect inconsistency until a subsequent transaction; it
  may take a long time.

The reactive approach using timeout doesn't have such disadvantages;
furthermore, it's simpler than the the schedule generation management,
in my opinion.

I still cannot see why the generation management at 6P is really needed...

Best,
Yatch

On 2016/11/30 17:39, Qin Wang wrote:

Hi Yasuyuki,

(1) Timeout in nodeA can be triggered either by failure in nodeA=>nodeB request 
process and by failure in nodeB=>nodeA response process (i.e the process in above 
example). nodeA cannot tell exact reason for a event of Timeout by itself. In another 
word, nodeA cannot tell there is a inconsistency between its schedule and nodeB's 
schedule just based on Timeout. Right?

(2) sending CLEAR, or STATUS, or LIST usually happens after a inconsistency is 
found, and the function of generation counter is exactly to find out the 
inconsistency. Make sense?

Thanks
Qin


___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Qin Wang]

Hi Yasuyuki,
(1) Timeout in nodeA can be triggered either by failure in nodeA=>nodeB request 
process and by failure in nodeB=>nodeA response process (i.e the process in 
above example). nodeA cannot tell exact reason for a event of Timeout by 
itself. In another word, nodeA cannot tell there is a inconsistency between its 
schedule and nodeB's schedule just based on Timeout. Right?
(2) sending CLEAR, or STATUS, or LIST usually happens after a inconsistency is 
found, and the function of generation counter is exactly to find out the 
inconsistency. Make sense?
ThanksQin   

On Tuesday, November 29, 2016 6:03 PM, Yasuyuki Tanaka 
 wrote:
 

 Hi Qin,

Hmm, in your example, node A can resolve the inconsistency without
using the generation counter by sending CLEAR to node B after the
timeout occurs. Node A could use STATUS or STATUS+LIST before sending
CLEAR in order to confirm inconsistency if the schedule generation
inconsistency detection was disabled...

Best,
Yatch


On 2016/11/29 22:40, Qin Wang wrote:
> Hi Yasuyuki,
>
> I'm not sure I fully understand you.
>
> Let's assume node A wants to ADD cells with nodeB in 2-step
> transaction. After nodeA sends ADD Request to nodeB, the Timeout of
> nodeA is set. nodeB receives the ADD Request, adds the cells to its
> schedule and sends Response back to nodeA at same
> time. Unfortunately, nodeA does not get the Response before Timeout,
> then the schedules on two sides become inconsistent. In this case,
> only generation counter in the following message exchange can tell
> the difference. right?
>
> Thanks
> Qin

___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch


   ___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Yasuyuki Tanaka]

Hi Qin,

Hmm, in your example, node A can resolve the inconsistency without
using the generation counter by sending CLEAR to node B after the
timeout occurs. Node A could use STATUS or STATUS+LIST before sending
CLEAR in order to confirm inconsistency if the schedule generation
inconsistency detection was disabled...

Best,
Yatch


On 2016/11/29 22:40, Qin Wang wrote:

Hi Yasuyuki,

I'm not sure I fully understand you.

Let's assume node A wants to ADD cells with nodeB in 2-step
transaction. After nodeA sends ADD Request to nodeB, the Timeout of
nodeA is set. nodeB receives the ADD Request, adds the cells to its
schedule and sends Response back to nodeA at same
time. Unfortunately, nodeA does not get the Response before Timeout,
then the schedules on two sides become inconsistent. In this case,
only generation counter in the following message exchange can tell
the difference. right?

Thanks
Qin


___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Qin Wang]

Hi Yasuyuki,
I'm not sure I fully understand you.
Let's assume node A wants to ADD cells with nodeB in 2-step transaction. After 
nodeA sends ADD Request to nodeB, the Timeout of nodeA is set. nodeB receives 
the ADD Request, adds the cells to its schedule and sends Response back to 
nodeA at same time. Unfortunately, nodeA does not get the Response before 
Timeout, then the schedules on two sides become inconsistent. In this case, 
only generation counter in the following message exchange can tell the 
difference. right?
ThanksQin 

On Thursday, November 24, 2016 9:27 AM, Yasuyuki Tanaka 
 wrote:
 

 Hi Qin,

Thank you for replying to my long email!!

I put the two cases you provided below, in which schedule generation
inconsistency could occur:

(1) failure in communication because of PHY problems like bed channel
    condition, collision

(2) failure in processing because of MAC problems such as buffer
    overflow.

These failures cause timeout at the 6P layer, don't they?

Why don't we consider a transaction ending with timeout as conceivably
inconsistent? If we would do that, we would not need to maintain the
generation counter; we would use wider bit space for SeqNum in a 6P
message. 6P could be simpler. It's up to a corresponding SF how to
deal with such a transaction.

Relying on timeout alone, we cannot tell if a concerned operation is
committed by a correspondent when the transaction ends with timeout. An
example is the case where a request is lost because of (1) or (2) in
2-step transaction. If the operation is not committed, the requester
takes wrongly the transaction as inconsistent. This case is what I
call false positive. It's not a big deal, I guess...

Best,
Yatch



   ___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Yasuyuki Tanaka]

Hi Qin,

Thank you for replying to my long email!!

I put the two cases you provided below, in which schedule generation
inconsistency could occur:

(1) failure in communication because of PHY problems like bed channel
condition, collision

(2) failure in processing because of MAC problems such as buffer
overflow.

These failures cause timeout at the 6P layer, don't they?

Why don't we consider a transaction ending with timeout as conceivably
inconsistent? If we would do that, we would not need to maintain the
generation counter; we would use wider bit space for SeqNum in a 6P
message. 6P could be simpler. It's up to a corresponding SF how to
deal with such a transaction.

Relying on timeout alone, we cannot tell if a concerned operation is
committed by a correspondent when the transaction ends with timeout. An
example is the case where a request is lost because of (1) or (2) in
2-step transaction. If the operation is not committed, the requester
takes wrongly the transaction as inconsistent. This case is what I
call false positive. It's not a big deal, I guess...

Best,
Yatch

___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Yasuyuki Tanaka]

Xavi, Thomas, thank you for the responses!

I'm replying both of you in a single email to save bandwidth ;-)

Sorry for making this email so long... I put a shorter response first.

thomas> From an implementation point of view, cells that are in the
thomas> process of being reserved (i.e. 6P add request sent but no
thomas> response received yet) should be marked as "reserved" and only
thomas> committed to the schedule once the 6P transaction if over. I
thomas> believe this captures Nicola's idea, but turning it into a
thomas> recommendation for implementers, rather than a protocol
thomas> feature.

This idea covers the requester side in a 2-step transaction. From the
point of view of the respondent, it has no idea if its response
reaches the requester in time. Therefore, there is no chance for the
responder to decide whether to commit the operation or not after
success in sending the response. Of course, the generation counter
detects a inconsistency case where a response is out of time without
Nicola's idea (the generation counter of the respondent is ahead of
one of the requester).

xavi> it adds complexity and more messages over the air, which are
xavi> costly and can also fail (e.g external interference). What
xavi> happens if we loose the 6P NACK? How the NACK sender know that
xavi> the NACK has been received?

Thanks, they are good questions. I guess timeout would cause an error
like "unrecoverable inconsistency", then CLEAR could be sent.

xavi> What causes less overhead, 2 bits per each 6P command or 1 or 2
xavi> extra packets per transaction (assuming only write/state
xavi> modification transactions). For me the former is way simpler.

I agree with you, Xavi. The former is less overhead. Basically, less
message is better.

Let me explain my little concerns on the generation management at 6P:

  (1) it makes 6P aware of a series of transactions, at least the
  result of a previous transaction, which is already taken care of
  by a SF

  (2) it limits options to deal with inconsistency

The first item, (1), is what I felt something a bit strange with when
I was writing code for the GTX/GRX stuff. Until then, I thought the
role of 6P was abstracting a set of the 6top operations and getting
every single transaction done well; it didn't care about past
transactions (let's set aside SeqNum for now). And, in my thoughts, a
SF on 6P was in charge of a whole scheduling process to each neighbor
involving a series of transactions. This was a simple architectural
concept for me. Now, this is not the case because of the generation
counter at the 6P layer. I'm in favor of the simple concept, although
there may have been no such a concept in 6top as I thought...

The second one is more practical. While the draft says a post-action
after detecting inconsistency is up to a SF, the SF has no choice but
sending CLEAR because other command is not accepted, responded with
RC_ERR_GEN, under a generation inconsistency situation. This means,
one inconsistent transaction will ruin all the rest of scheduled cells
which are still valid. I feel that this is rooted in the first item I
mentioned; there are two entities managing consistency.

By the way, I may not understand fully how an inconsistency
occurs... Are there any inconsistency cases which timeout of either
side cannot detect, requester side or respondent side? In other words,
are there any inconsistency cases which 6P can detect but SFs cannot?
Answers to this question would help me understand why the generation
management at 6P is really necessary...

If the generation management was not necessary, I'd propose to remove
it and to add a rollback command to 6P in order to cancel the previous
operation in a separate transaction, operation to cancel which is
specified by SeqNum of the concerned operation in the rollback command
payload. A transaction with the rollback command is supposed to be
initiated when the previous transaction ends with timeout. This
proposal would make no changes on the current transaction patterns. It
would simplify 6P, which would not need to do for consistency
management nor generation management. There could be false positives
caused by inconsistency detection with timeout, but I assume they are
not big deal.

# In this sense, I prefer calling the value Transaction ID rather than
# SeqNum.

Thank you all for reading up to here...

Best,
Yatch

On 2016/11/22 8:23, Thomas Watteyne wrote:

I'd like to keep 6P simple, and just have a mechanism to detect inconsistencies. I 
believe roll-back to a previous schedule generation adds too much complexity. From an 
implementation point of view, cells that are in the process of being reserved (i.e. 6P 
add request sent but no response received yet) should be marked as "reserved" 
and only committed to the schedule once the 6P transaction if over. I believe this 
captures Nicola's idea, but turning it into a recommendation for implementers, rather 
than a protocol feature.

On Mon, Nov 21, 2016 

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Thomas Watteyne]

I'd like to keep 6P simple, and just have a mechanism to detect
inconsistencies. I believe roll-back to a previous schedule generation adds
too much complexity. From an implementation point of view, cells that are
in the process of being reserved (i.e. 6P add request sent but no response
received yet) should be marked as "reserved" and only committed to the
schedule once the 6P transaction if over. I believe this captures Nicola's
idea, but turning it into a recommendation for implementers, rather than a
protocol feature.

On Mon, Nov 21, 2016 at 9:56 PM, Xavi Vilajosana Guillen <
xvilajos...@uoc.edu> wrote:

> Hi Yatch,
> my 2 cents inline
>
>
>> I've been thinking about how to handle inconsistencies. I know the
>> current draft has an inconsistency detection mechanism with generation
>> management; just wondering if there is another way or a supplemental
>> mechanism to deal with such a situation.
>>
>> We decided at the IETF meeting last week to reduce the number of
> generation counters from 2 to 1 (2bits field) as now 6P commands can add
> different types of cells so we need to account for transactions now. I
> state that here to outline that the proposed mechanism is very simple. At
> every transaction we increment a generation counter. It cannot happen that
> the two sides of the transaction have inconsistent counters. If this
> happens, then the schedules are reset. I agree that this is detected after
> the error has occurred.
>
>
>> I thought that the 2-phase commit (2PC) protocol could be useful
>> here. Then, I found the nice idea by Nicola in the ML archive. In
>> terms of the 2PC protocol, 6P ACK is Commit. 6P NACK (mentioned in
>> another email by Nicola) is Abort or Rollback.
>> # We may need another type of message to acknowledge Commit or Abort.
>>
>> An advantage of this approach is that 6P can resolve an inconsistency
>> when it occurs at the least cost, by cancelling the concerned
>> operation alone. An apparent disadvantage is adding further complexity
>> to 6P.
>>
>
> it adds complexity and more messages over the air, which are costly and
> can also fail (e.g external interference). What happens if we loose the 6P
> NACK? How the NACK sender know that the NACK has been received?
>
>>
>> What others think...?
>>
>
> I like to answer with another question. What causes less overhead, 2 bits
> per each 6P command or 1 or 2 extra packets per transaction (assuming only
> write/state modification transactions). For me the former is way simpler.
>
> regards,
> X
>
>
>
>>
>> Best,
>> Yatch
>>
>> ___
>> 6tisch mailing list
>> 6tisch@ietf.org
>> https://www.ietf.org/mailman/listinfo/6tisch
>>
>
>
>
> --
> Dr. Xavier Vilajosana Guillén­
> Research Professor
> Wireless Networks Research Group
> Internet Interdisciplinary Institute (IN3)
> Universitat Oberta de Catalunya­
>
> +34 646 633 681| xvilajos...@uoc.edu­ | Skype­: xvilajosana
> http://xvilajosana.org
> http://wine.rdi.uoc.edu/
>
> Parc Mediterrani de la Tecnologia
> Av. Carl Friedrich Gauss, 5. Edifici B3
> 08860 Castelldefels (Barcelona)
>
>
>
> ­
>
> ___
> 6tisch mailing list
> 6tisch@ietf.org
> https://www.ietf.org/mailman/listinfo/6tisch
>
>


-- 
___

Thomas Watteyne, PhD
Research Scientist & Innovator, Inria
Sr Networking Design Eng, Linear Tech
Founder & co-lead, UC Berkeley OpenWSN
Co-chair, IETF 6TiSCH

www.thomaswatteyne.com
___
___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch

Re: [6tisch] Handling Inconsistent Allocation in 6P

[Xavi Vilajosana Guillen]

Hi Yatch,
my 2 cents inline


> I've been thinking about how to handle inconsistencies. I know the
> current draft has an inconsistency detection mechanism with generation
> management; just wondering if there is another way or a supplemental
> mechanism to deal with such a situation.
>
> We decided at the IETF meeting last week to reduce the number of
generation counters from 2 to 1 (2bits field) as now 6P commands can add
different types of cells so we need to account for transactions now. I
state that here to outline that the proposed mechanism is very simple. At
every transaction we increment a generation counter. It cannot happen that
the two sides of the transaction have inconsistent counters. If this
happens, then the schedules are reset. I agree that this is detected after
the error has occurred.


> I thought that the 2-phase commit (2PC) protocol could be useful
> here. Then, I found the nice idea by Nicola in the ML archive. In
> terms of the 2PC protocol, 6P ACK is Commit. 6P NACK (mentioned in
> another email by Nicola) is Abort or Rollback.
> # We may need another type of message to acknowledge Commit or Abort.
>
> An advantage of this approach is that 6P can resolve an inconsistency
> when it occurs at the least cost, by cancelling the concerned
> operation alone. An apparent disadvantage is adding further complexity
> to 6P.
>

it adds complexity and more messages over the air, which are costly and can
also fail (e.g external interference). What happens if we loose the 6P
NACK? How the NACK sender know that the NACK has been received?

>
> What others think...?
>

I like to answer with another question. What causes less overhead, 2 bits
per each 6P command or 1 or 2 extra packets per transaction (assuming only
write/state modification transactions). For me the former is way simpler.

regards,
X



>
> Best,
> Yatch
>
> ___
> 6tisch mailing list
> 6tisch@ietf.org
> https://www.ietf.org/mailman/listinfo/6tisch
>



-- 
Dr. Xavier Vilajosana Guillén­
Research Professor
Wireless Networks Research Group
Internet Interdisciplinary Institute (IN3)
Universitat Oberta de Catalunya­

+34 646 633 681| xvilajos...@uoc.edu­ | Skype­: xvilajosana
http://xvilajosana.org
http://wine.rdi.uoc.edu/

Parc Mediterrani de la Tecnologia
Av. Carl Friedrich Gauss, 5. Edifici B3
08860 Castelldefels (Barcelona)



­
___
6tisch mailing list
6tisch@ietf.org
https://www.ietf.org/mailman/listinfo/6tisch