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

From: Xavi Vilajosana Guillen <[email-masked]>
Date: Mon, 21 Nov 2016 21:56:58 +0100

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
> [email-masked]
> 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| [email-masked] | 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)

---

From: Thomas Watteyne <[email-masked]>
Date: Tue, 22 Nov 2016 08:23:31 +0100

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 <
[email-masked]> wrote:

> 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

-- 
_______________________________________

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
_______________________________________

---

From: Yasuyuki Tanaka <[email-masked]>
Date: Tue, 22 Nov 2016 17:47:41 +0100

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 at 9:56 PM, Xavi Vilajosana Guillen <[email-masked] <mailto:[email-masked]>> wrote:
>
>     Hi Yatch,
>     my 2 cents inline
>
>
>     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.
>
>
>     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
>
>         [email-masked] <mailto:[email-masked]>
>         https://www.ietf.org/mailman/listinfo/6tisch <https://www.ietf.org/mailman/listinfo/6tisch>
>
>
>
>
>     --
>     +34 646 633 681 <tel:%2B34%20646%20633%20681>| [email-masked] <mailto:[email-masked]> | Skype: xvilajosana
>     http://xvilajosana.org <http://xvilajosana.org>
>     http://wine.rdi.uoc.edu/
>
>     [email-masked] <mailto:[email-masked]>
>     https://www.ietf.org/mailman/listinfo/6tisch <https://www.ietf.org/mailman/listinfo/6tisch>
>
>
>
>
> --
> www.thomaswatteyne.com <http://www.thomaswatteyne.com>

---

From: Qin Wang <[email-masked]>
Date: Wed, 23 Nov 2016 23:02:17 +0000 (UTC)

Hi Yasuyuki,
Regarding to the reasons of inconsistent allocation asked in your email, I think, roughly speaking, they are (1) failure in communication because of PHY problems like bed channel condition, collision, and (2) failure in processing because of MAC problems such as buffer overflow. 
The approach of 6P ACK/NACK may address reason (2), but cannot address reason (1), because 6P ACK/NACK may drop also. According to my understanding, the 2bits Generation Counter can cover the two reasons of inconsistent allocation in very high probability and keep 6P simple as well. Thus, I prefer the 2bits Generation Counter solution also.
ThanksQin

    On Tuesday, November 22, 2016 11:47 AM, Yasuyuki Tanaka <[email-masked]> wrote:

Best,
Yatch

---

From: Yasuyuki Tanaka <[email-masked]>
Date: Thu, 24 Nov 2016 15:27:07 +0100

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

---

From: Qin Wang <[email-masked]>
Date: Tue, 29 Nov 2016 21:40:32 +0000 (UTC)

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 <[email-masked]> wrote:

 Hi Qin,

Best,
Yatch

---

From: Yasuyuki Tanaka <[email-masked]>
Date: Wed, 30 Nov 2016 00:03:38 +0100

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:
> 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

---

From: Qin Wang <[email-masked]>
Date: Wed, 30 Nov 2016 16:39:35 +0000 (UTC)

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 <[email-masked]> wrote:

 Hi Qin,

Best,
Yatch

---

From: Yasuyuki Tanaka <[email-masked]>
Date: Wed, 30 Nov 2016 19:49:18 +0100

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