Subject: Re: [homenet] Concerns about DNCP

From: Markus Stenberg <[email-masked]>
Date: Wed, 1 Jul 2015 12:28:34 +0300

On 30.6.2015 20.10, Juliusz Chroboczek wrote:
> Concerns about DNCP
> ===================
>
> DNCP is an elegant and small protocol that distributes HNCP data across
> the Homenet.  DNCP works by flooding a hash of the full network state over
> link-local multicast, and synchronising the actual state piecewise by
> using link-local unicast request/response pairs.  This document outlines
> a number of concerns with DNCP as described in draft-ietf-homenet-dncp-06.
>
> I very strongly support the work that is being done on DNCP and HNCP.
> I will be glad to see something very similar to the current drafts adopted
> by the Homenet WG.
>
>
> Packet format
> -------------
>
> ### There is no header
>
> A DNCP packet consists of just a sequence of TLVs.  This means that there
> is no way to version the DNCP protocol.  Should a change in the TLV format
> be required, a new UDP port will need to be allocated.  (A new multicast
> group is not sufficient, since DNCP also uses unicast).
>
> I recommend adding a fixed-size header with a version number.

I disagree with it. The points have been enumerated in response to 
Thomas C's review, but they boil down to:

- DNCP itself has no port, nor any assignments

- big TLV space, can reuse parts of it

- DNCP profiles can define versioning schemes (and HNCP does, and now 
our implementation might actually follow it, cough)

> ### NODE-ENDPOINT is stateful
>
> The DNCP/HNCP protocol suite uses the elegant technique of using
> recursively embedded TLVs: hop-to-hop data is in the packet toplevel,
> end-to-end data is in the NODE-STATE TLV, which may in turn contain TLVs
> that themselves contain embedded TLVs.  The TLVs are mostly stateless, in
> the sense that they can be sent in any order or even in independent
> packets.  NODE-ENDPOINT is an exception.
>
> NODE-ENDPOINT identifies the sender of this packet, and applies to all
> TLVs in this packet.  The current specification implies that the
> NODE-ENDPOINT may appear anywhere in the packet, which would force the
> receiver to make two passes over the packet.

Not really. In the current specified processing flow, the only 
dependency on endpoint is with the Network State TLV (and it's handling 
of consistent <> inconsistent per neighbor).

Assuming you keep that state as a flag during the processing, the 
Endpoint TLV itself can appear after Network State TLV too.

(This in case of datagrams; in a stream, it has to show up once, early, 
and then be remembered.)

> Conceptually, NODE-ENDPOINT is a packet header, and it is best treated
> that way.  Ideally, the information it contains would be part of the
> fixed-size packet header suggested above (but after the version number,
> which should be parsable even when the NODE-ENDPOINT format changes).
> Alternatively, specify that NODE-ENDPOINT MUST be the very first TLV in
> a packet, or at least appear before all currently-defined TLVs, which
> merely formalises what existing implementations already do.

See above. If there is call for it on the list, we can change it to:

- MUST be before Network State TLV (I am fine with this, it removes one 
flag from my current implementation's one-pass parsing)

- MUST be first (I strongly disagree with this design due to it 
potentially being problem later - what if there is second version with 
MUST have first of something else?)

> ### NODE-ENDPOINT is underspecified
>
> It is not clear whether NODE-ENDPOINT is required in all packets, and if
> not which TLVs are allowed in a packet without a NODE-ENDPOINT.  Existing
> implementations appear to differ in that respect.

Current text says MUST all (if desire bidir peer relationship), while in 
truth (for protocol to work) it is likely sufficient to include it only 
within subset:

- Network State TLV MUST given cursory inspection of the spec about this 
(those are used for keepalives and periodic Trickling -> should be 
enough to maintain the peer state)

- requests SHOULD, as it makes initial neighbor detection faster

The current spec is simpler, so I prefer that, and rather just fix 
implementations.

> ### Node data is underspecified
>
> The NODE-STATE TLV carries the end-to-end hash of the "node data".
> However, the exact "node data" is never specified exactly.  For example,
> there is padding applied between TLVs (look, Ma, I've saved 4ns parsing my
> packet), and it is nowhere specified whether this padding participates in
> the hashing (it does).
>
> It turns out that in the absence of fragmentation the "node data" is just
> the raw binary data in the NODE-STATE TLV.  This is the reasonable thing
> to do, and must be specified in this manner.  It must also be made clear
> that this binary data MUST NOT be modified in transit (parsing/reformatting
> is not likely to work reliably), and that its hash SHOULD (or is that MAY?)
> be validated on reception.

Agreed. Probably SHOULD, to avoid corrupt data <> hash combinations from 
spreading. Updating the text.

> ### Normalisation is apparently useless
>
> DNCP specifies that the TLVs within a node state be sorted.  Since both
> the raw binary data and the hash are end-to-end, it is not clear why this
> partial normalisation is useful.
>
> At the very least, the draft should make it clear that this normalisation
> should not be relied upon, and that peers MUST forward the binary data
> unchanged.  I recommend simply dropping the normalisation, although this
> will require changes to the fragmentation scheme.

Disagree. It is much more efficient to have guaranteed ordering done by 
publisher, and always available as such for receivers (there are amusing 
hacks using this, e.g. linear time delta processing, one-pass index 
creation for all packets with only one pointer or two per indexed data 
type, and others). I see the benefits of saying MUST as greater than 
lessening the requirements. No planned change.

> ### FRAGMENT-COUNT is stateful in the reverse direction
>
> FRAGMENT-COUNT is stateful, but in the reverse direction: it changes the
> interpretation of the enclosing NODE-STATE TLV.  Usually, the NODE-STATE
> hash carries exactly data being hashed; with a FRAGMENT-COUNT, it carries
> part of that data, and FRAGMENT-COUNT is not being hashed.
>
> FRAGMENT-COUNT is not end-to-end data, and it doesn't belong within the
> NODE-STATE TLV.  It should either be a field in the NODE-STATE TLV itself
> (not in an embedded TLV), or put in a TLV that contains the NODE-STATE
> TLV.
>
> ### Fragmentation is specified at the TLV level
>
> The section about fragmentation is not quite clear to me.  It appears to
> specify fragmentation in terms of TLVs (every fragment must consist of
> a valid series of TLVs), and appears to assume that the receiver is doing
> something smart in order to avoid reassembly timeouts.
>
> Unfortunately, this encoding makes it very difficult to implement
> a simpler scheme, where fragmentation and reassembly are TLV-agnostic and
> act entirely at the byte-stream level.  In particular, a fragment TLV does
> not specify an initial byte offset, and the total length of the
> reassembled packet is not known beforehand, which makes buffer management
> in the receiver challenging.
>
> I recommend a TLV-agnostic fragmentation scheme, with fragment offsets
> counted in octets and a total reassembled size explicitly encoded.
>
> ### The fragment timeout is not specified
>
> It is not clear when the receiver can discard an incomplete defragmentation
> buffer.  This might not be an issue if a TLV-based fragmentation scheme is
> used.

This sounds much more complex fragmentation scheme than what was 
intended; original intent was to essentially reuse Merkle tree as parts 
of node data, and without changing protocol, easiest way was to just use 
concatenated sets of node data.

I guess I have to see about other reviews, but I am essentially for 
removing whole fragmentation scheme, than adding something overly 
complex, especially as nobody has implemented it (nor seems to have 
plans for it) any time soon.

> ### Keep-alive intervals are flooded
>
> The KEEP-ALIVE-INTERVAL is within the node state, and hence flooded across
> the network.  This information is of no interest to remote nodes, this TLV
> should be within at the top level of the packet in order to reduce the
> amount of information being flooded.

It is assumed to be default, which is not published. The tradeoff is 
essentially between global state and on-link spam (this value is 
unlikely to change, but expecting yet more storage of other nodes is 
also awkward).

We prototyped both, but essentially global state is cheaper in a small 
network than constant payloads on the link. Non-constant payloads on the 
link make it more session-oriented than I like.

> Protocol dynamics
> -----------------
>
> ### Need to check sender
>
> Most of the packets in DNCP have exactly the same meaning whether they are
> sent to a unicast or a multicast address.  There is one exception: the
> keepalive timer is only reset for inconsistent network state when they
> are sent over unicast.  This requires that the receiver check the
> destination address of packets, which is non-portable and might be
> impossible on some systems.

Not in IPv6 at least given RFC3542 (IPV6_RECVPKTINFO).

Unicast and multicast also have different security properties (given 
security, which I recommend), so I rather not change all TLVs to say 'I 
am good guy, really', for example.

> I recommend removing the requirement to distinguish between unicast and
> multicast.  If such distinction is needed, make it explicit in the TLV
> contents.

The distinction is needed (I think); otherwise multicasting 'something' 
(=something completely braindead and-or topology graph-wise 
unidirectionally reachable now) would still be kept danngling as long as 
transmissions continue.

> ### Not clear when multicasts and unsolicited packets can be sent
>
> As it is written, the draft requires that all TLVs other than
> NETWORK-STATE be sent over unicast and does not allow unsolicited packets
> other than NETWORK-STATE.  However, the draft authors indicate that
> unsolicited multicast packets are allowed.

The draft specifies mandatory processing flow for particular TLVs (X 
happens, do Y). Those Y replies are by unicast. It (intentionally) does 
not say anything about {uni,multi}cast of X, and therefore X can come 
either way. It does not say you MUST NOT multicast additionally if you 
feel like it, for example.

> The draft should specify clearly when multicast and unsolicited packets
> are allowed.  In particular, it should mention whether it is legal to
> reply to a request over multicast (which may make sense, at least on some
> link layers), and which packets can be sent unsolicited over multicast.

I do not think it is unclear on MUST reply via unicast. How would you 
prefer it written out?

X part I am reluctant to explicitly specify, as there are already 
caveats about security, profile, etc constraining the valid X set for 
multicast. Those are already in the text.

> ### Non standard port
>
> The draft specifies that it is required to answer a request from a node
> that does not publish a node state.  What should happen when this request
> comes from a non-standard port?  Monitoring software may need to run on
> the same node as a normal DNCP implementation.

Transport specific issue, DNCP itself does not really specify port-level
semantics one way or another (HNCP might need something there though).

> ### Non-publishing nodes
>
> A node may want to participate in the full protocol without publishing
> a node state in order to reduce the amount of data being flooded.  Doing
> this naively might cause persistent state desynchronisation, leading to
> repeated resetting of the Trickle timers.
>
> Ideally, the draft would specify exactly which behaviours are allowed for
> non-publishing nodes.  At any rate, a warning about the dangers of
> non-publishing nodes should be included in the draft.

Agreed. Updating.

Cheers,

-Markus

---

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

> Not really. In the current specified processing flow, the only dependency
> on endpoint is with the Network State TLV (and it's handling of consistent
> <> inconsistent per neighbor).

I may be missing something, but I suspect you're assuming that the neighbour
(peer) table is indexed by addresses; in my implementation, it is indexed
by (id, eid, lid) triples, hence I cannot access my per-neighbour data
structure until I've learned your (id, eid).

If indexing by (interface, address) pair is the only legal implementation,
you'll need to make it explicit in the draft.  (What I'm doing here is
technically known as blackmail.)

> flag from my current implementation's one-pass parsing)

This will force me to change my implementation -- I'm currently not
sending a REQ-NODE-STATE unless I've seen an endpoint, so as to avoid
sending it to passive observers.

Please let me know if you prefer me to change my implementation, or
whether you're willing to add MUST NODE-ENDPOINT before NODE-STATE.

>> It is not clear whether NODE-ENDPOINT is required in all packets,

> Current text says MUST all [...] The current spec is simpler, so
> I prefer that, and rather just fix implementations.

I strongly disagree.  Sending NODE-ENDPOINT has the side effect of storing
a neighbour in the peer, which is not something a purely passive observer
should be doing.  If a node is not sending NETWORK- or NODE-STATE, it
shouldn't even need to choose an id -- it should be allowed to make
a simple request/response transaction that is completely stateless for the
responder.

I suggest MUST for NETWORK-STATE, and "SHOULD if available" for all others.
(And of course MUST for NODE-STATE if you make the change suggested above.)

> I am essentially for removing whole fragmentation scheme [...] especially
> as nobody has implemented it

I strongly agree.  Working code and all that.

>> ### Keep-alive intervals are flooded

[...]

> network than constant payloads on the link.

You've almost convinced me, so I'll just note that the same issue exists
with the NODE-ADDRESS TLV in HNCP -- there's no reason to flood this
information beyond the local link.  In that case, the amount of state
spuriously flooded could be moderately large (24 bytes per router per
attached link), which argues in favour of a mechanism that allows
publishing data that doesn't go beyond the local links.

As you say, not sure it's worth the complexity.

>> Protocol dynamics

I've reordered your replies to these two parts.

> I do not think it is unclear on MUST reply via unicast. How would you

I would like the licence to reply over multicast, at least in some cases.
For example, if I've just republished my state, all of my neighbours are
going to be interested in my new state, am I allowed to reply over
multicast once and for all?  (Of course, I can send a gratuitious multicast
NODE-STATE, but the new NETWORK-STATE may already have triggered a bunch
of requests, and I'd like to avoid having to reply to those individually.)

Another optimisation would be sending the "long" NETWORK-STATE over
multicast if I've buffered multiple requests over the same interface.

> unidirectionally reachable now) would still be kept danngling as long as

Epiphany!  The protocol may keep unidirectional links indefinitely, but
only if the network states are consistent on both sides (Section 6.1.4).
Which doesn't harm, since (i) the states are consistent, and (ii) the link
will be purged by the silly walk.  That's really smart, and really subtle.

I think that's subtle enough to be explicitly spelled out in the document.

Markus, for the sake of minimality, I would like you to work out exactly
which packets MUST be sent over unicast, and specify the exact minimal
set.  You're welcome to SHOULD the others.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 2 Jul 2015 10:22:54 +0300

> technically known as blackmail.)

In stream case, you may need to associate a connection with the remote 
peer (to store the remote endpoint id + node id) as it may not be 
available during TLV processing even if it is 'assumed' to be present. 
Otherwise, not really.

I'll bite and look at TLV processing:

- RNetS: no need (local state response)
- RNodeS: no need (local state response)
- Endpoint: depends on if we know the (peer, endpoint) already;
  unknown:
  * add peer (unicast), send RNetS (multicast)
  known:
  * update last contact (unicast)
- NetS: need (possibly with delay, to update Trickle state match; we do 
Trickle state update last so ordering does not matter)
- NodeS: no need (local state update, regardless of where it comes from)

Do you have some other TLVs and-or different interpretation on how the 
individual TLVs are processed?

> whether you're willing to add MUST NODE-ENDPOINT before NODE-STATE.

I do not know why you need it with NodeS, it should not be needed there 
as far as I understand it.

> a simple request/response transaction that is completely stateless for the

It is MUST if and only if you desire bidirectional peering relationship 
currently. So if you don't, you shouldn't need to still send it. Perhaps 
the text could be clarified more.

> (And of course MUST for NODE-STATE if you make the change suggested above.)

See above. Why do you need it with NodeS?

> As you say, not sure it's worth the complexity.

For SD purposes, we need at least 1 address per router. However, you are 
correct, that _all_ addresses are not really necessarily needed (as 
noted elsewhere). Perhaps we should just move this to a SHOULD 
(+~SLAAC+ND backup), and then MUST have at least 1 address published in 
the SD section if it is supported.

> multicast if I've buffered multiple requests over the same interface.

I find this problematic as then we get matrix of

- profile
- implementation
- security mode (=nothing valuable over multicast, please)
- .. and few other parameters

deciding whether or not a) what you sent is valid, and as a result, b) 
whether the network converges given multiple interpretations of the rules.

Spirit of the current spec _would_ allow for e.g. doing multicast reply 
by default, but probabilistically (e.g. 20%) or after awhile (if you are 
willing to spend the resources to keep track) responding also via 
unicast  - MUST _eventually_ reply is there for that reason - so that 
nodes that are not happy with multicast would still converge eventually, 
just slower.

Better descriptions on how to convey the idea would be welcome, as usual.

> set.  You're welcome to SHOULD the others.

I am worried about state space explosion in drafts (and our heads). Let 
me know if you it is still necessary given the above description on why 
MUST unicast does not kill most multicast dreams ;)

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 02 Jul 2015 11:55:40 +0200

You're right, I don't need endpoint except in NETWORK-STATE.

> Trickle state update last so ordering does not matter)

Well, for HNCP Trickle is per-interface, so it's only really needed in
order to update last_contact.

> - NodeS: no need (local state update, regardless of where it comes from)

You're right, my need of it is an artifact of an earlier version of my
code (I was indexing unicast buffers by neighbour, rather than by
sockaddr).  (And I'm realising that the buffer management code can be
further simplified.)

So the strict minimum for my implementation (once I've fixed it) is going
to be NODE-ENDPOINT MUST before unicast NETWORK-STATE only.  Requiring it
before all NETWORK-STATE simplifies the spec, but is not quite minimal.

-- Juliusz

P.S. Could you please push your HNCP-VERSION fix to OpenWRT?

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 02 Jul 2015 12:01:25 +0200

> correct, that _all_ addresses are not really necessarily needed (as noted
> elsewhere). Perhaps we should just move this to a SHOULD (+~SLAAC+ND
> backup), and then MUST have at least 1 address published in the SD section
> if it is supported.

Agreed.

-- Juliusz

---

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

> order to update last_contact.

True.

> before all NETWORK-STATE simplifies the spec, but is not quite minimal.

I guess I will add that ordering to the spec, as it simplifies the 
implementation. I will leave the datagrams without Network State TLV 
SHOULD (as per my updated text), because it speeds up initial peer 
establishment a bit if you already include it in the initial requests 
(for example).

> P.S. Could you please push your HNCP-VERSION fix to OpenWRT?

Current HEAD of master isn't exactly correct[1] (looks like my fancy 
one-pass update to the protocol handling broke something). We will push 
the updated version to OpenWrt routing before end of the week once we're 
happy about it[2] (and dncp-07 and hncp-07 are out, hopefully).

If you want, you can update your local routing feed hnetd to use git 
version 7e24726fa3698ac8ca6c033935656b887ef5a000, that one passed  tests 
and is more correct in terms of ignoring just HNCP TLVs in case of 
version conflict than our 'official' OpenWrt routing version right now.

Cheers,

-Markus

[1] Well, it works 99.9+% of the time, but I am perfectionist. There are 
some rare corner cases where it breaks right now. Thank $DEITY for 
serious stress tests.

[2] Close to 0% failure rate on system tests and 0% failure rate on unit 
tests (that we care about) / stress tests.