Subject: [homenet] More about state desynchronisation in DNCP

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 01 Jul 2015 14:44:12 +0200

In my previous mails, I used the term "persistent state desynchronisation".
Since this apparently worried some people, so I guess I'll explain.

DNCP uses dynamic timers (Trickle) to flood a hash of the global state and
separate unicast request/response pairs to propagate actual data.  Bad
things will happen if the hash is successfully flooded but the data cannot
be propagated, for example because it doesn't fit in the maximum packet
size, because a node is not publishing enough NEIGHBOR TLVs, or because of
implementation bugs.

More precisely, under such circumstances each attempt to flood the
inconsistent network hash is followed with a flurry of request/response
pairs and a reset of the Trickle timers to their minimal value (200ms).
The result is persistent spam.

Therefore, (1) we must make sure that a compliant implementation does not
cause state to become persistently inconsistent, and (2) we should develop
some mechanism that detects persistently desynchronised neighbours and
rate-limits them.  (1) needs to go in the spec, while (2) is a "mere"
implementation detail.

-- Juilusz

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 1 Jul 2015 15:54:54 +0300

> rate-limits them.  (1) needs to go in the spec, while (2) is a "mere"

Your definition of the worst-case here is slightly pessimistic I believe 
(c.f. appendix B changenotes); in practise, as Trickle reset occurs if 
and only if _locally_ calculated network state changes, if stuff coming 
in doesn't agree with what we already have, we just do request+reply 
every Trickle interval (local+remote) that fails, but Trickle timers do 
back off eventually if we cannot actually change local state (of remote 
nodes).

Obviously, it results in a partitioned network with 'spam' unicast 
exchanges occuring every now and then on the border so it is not 
desirable, but it does not cause network-wide problems nor any real 
state churn beyond extra unicast packets that are essentially ignored or 
replied to and then ignored.

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 01 Jul 2015 15:07:30 +0200

> (c.f. appendix B changenotes); in practise, as Trickle reset occurs if and
> only if _locally_ calculated network state changes,

I've obviously missed something.  RFC 6206 says

    6.  If Trickle hears a transmission that is "inconsistent" and I is
        greater than Imin, it resets the Trickle timer.  To reset the
        timer, Trickle sets I to Imin and starts a new interval as in
        step 2.  If I is equal to Imin when Trickle hears an
        "inconsistent" transmission, Trickle does nothing.

If I read this correctly, I will never exceed I_min * 2.

> it does not cause network-wide problems nor any real state churn beyond
> extra unicast packets that are essentially ignored or replied to and
> then ignored.

I'm probably missing something again.  If node A has two neighbours B and
C that reply with different data for node D, what avoids persistent churn
at A?

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 01 Jul 2015 15:10:58 +0200

> I've obviously missed something.

Yes, I have.  Section 4.3:

    The Trickle state for all Trickle instances is considered
    inconsistent and reset if and only if the locally calculated network
    state hash changes.  This occurs either due to a change in the local
    node's own node data, or due to receipt of more recent data from
    another node.

I'm officially an idiot.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 1 Jul 2015 16:43:21 +0300

>      node's own node data, or due to receipt of more recent data from

Not to worry, so am I; there's almost year's worth of drafts proving 
that in this case alone. All versions before dncp-00 had this problem 
(that is, the old unified HNCP drafts <= -03).

It took me that long to realize that use of Trickle to detect that 
[1]_someone has different state_ is very different from [2]_you are able 
to actually get that state_.

The original Trickle spec seems to assume that [2] is automatic given 
[1] occurs (or I misunderstand the RFC). Unfortunately, it really is 
not, given multicast+unicast nature of DNCP, unidirectional links and 
the examples of nastiness that came up in this thread. If you cannot get 
the new state (yet know it exists), you just spam forever uselessly due 
to constant Trickle resets.

That said, there is one refinement that could be added to this, but I 
have so far omitted it as it seems extra complexity to address a corner 
case. TLVs (e.g. keep-alives) in general could be ignored if remote node 
has not been in sync with us FOR A LONG TIME even if they come via 
unicast; given that, the partitioned graph would lose stale parts 
eventually. I have considered adding MAY for that for awhile, but have 
yet to convince myself about the complexity/usefulness tradeoff there.
Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 01 Jul 2015 16:03:36 +0200

> to actually get that state_.

Markus, this is *very* enlightening.  You *must* put that in the draft.

Now what happens if I get an inconsistent network state, I send a request,
and the reply gets lost?  Since I didn't reset my trickle timer, I'm going
to wait the full ~17 seconds until I try again, right?

MAY I reset the trickle timer after I see a transition from synchronised
to unsynchronised network state?

> That said, there is one refinement that could be added to this, but I have
> so far omitted it as it seems extra complexity to address a corner
> eventually. I have considered adding MAY for that for awhile, but have yet
> to convince myself about the complexity/usefulness tradeoff there.

I need to think it over, but it seems like a bad idea, at least for
Homenet.  If the network is not synchronising properly, you want to see
the unsynchronised nodes in the GUI.  In the current version of the
algorithm, they would appear as nodes that don't publish any data, which
is pretty cool.

Markus, this is a very elegant protocol.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 1 Jul 2015 21:13:40 +0300

> Markus, this is *very* enlightening.  You *must* put that in the draft.

In some form I think we will, as essentially it is slightly different 
from traditional Trickle viewpoint where state is atomic; in this case, 
state has two parts, that network really cares about; the network state 
hash _and_ the node data of individual nodes, and we _really_ care only 
about change to the latter, but use the former to detect the change we 
care about.

> to wait the full ~17 seconds until I try again, right?

You essentially wait for the other party to resend their network state. 
Given chance has happened recently, this may be sooner than you may 
think (Trickle I near I_min). In case where seldom changing graphs merge 
and packet loss occurs, this may of course lead to retries with interval 
close to min(keepalive-interval, I_max).

> to unsynchronised network state?

Ideally not. However, doing it will not really break anything either. 
Due to rate limiting etc, the other party is not guaranteed to reply 
even if they get your initial message.

All Trickle parameters _and_ actually even use of Trickle at all are 
ultimately strictly local choice; all that matters is that Network State 
TLVs get pumped out, as that primes the MUST flow of state 
synchronization specified in Section 4.3/4.4 (+ keepalives if applicable).

The document attempts to describe a sane combination of how Trickle 
SHOULD<>MUST be used (if it quacks like a duck, ..), and how to react to 
Network State TLVs (and what triggers off them).

At some point I considered writing just 'SHOULD use Trickle, MUST do 
stuff in Section 4.4 + keepalives' but I imagined non-Trickle-users 
would behave badly so it is a MUST for now.

> algorithm, they would appear as nodes that don't publish any data, which

Hm, no.. Let's assume topology like this:

A - B - C

Let us assume that B is crap node, that has limits(tm).

1. At some point, C state exceeds those. What happens?

A continues to see C _forever_ in the state it was before B's limits 
were encountered (given neighbor TLVs stay around, and why would they not?).

This is because B drops every update of C state as it cannot handle it 
(and it _cannot_ also forge state that looks empty, as that leads to 
e.g. collision loops).

B likewise.

C has full visibility of the rest, until

2. A exceeds the limits.. and then:

A sees changes of B
C sees changes of B
and A and C see each other as frozen in time.

Same reasoning as above.

> Markus, this is a very elegant protocol.

Thanks ;) Funnily enough, the core of it has actually shrunk down over 
the time.

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 01 Jul 2015 20:23:13 +0200

> (given neighbor TLVs stay around, and why would they not?).

Milliseconds since origination overflow?

(By the way -- where does it say what a non-originator node should do when 
the field overflows?)

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 2 Jul 2015 13:37:50 +0300

On 1.7.2015 21.23, Juliusz Chroboczek wrote:
> (By the way -- where does it say what a non-originator node should do
> when the field overflows?)

In dncp-07. Implementation fixed already :)

Cheers,

-Markus