Subject: [homenet] DNCP questions

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 23 Feb 2015 03:57:42 +0100

I have a few questions and comments about DNCP.  (I haven't finished
grokking HNCP yet, so that will have to wait.)

1. Fragmentation

The minimum MTU in IPv6 is 1280 bytes, and the minimum maximum packet size
(before fragmentation) is 1500 bytes.  This means that a Short Network
Status can carry information about 160 nodes or so, which is a little
tight for comfort.  Is there a fragmentation mechanism I've missed
somewhere?

Related to that -- what happens if you receive a Node Data Request, and
the reply doesn't fit in the MTU?  Are you allowed to split it into
multiple Node Data Replies?  If so, how do you know if you've received the
whole set?

2. Packet loss

What happens on packet loss?

  * what happens when the reply to a Node Data Request doesn't arrive?
    Are you supposed to resend the request?  With exponential or linear
    backoff, and with what constants?

  * is there a way to detect that a link exhibits packet loss?  There are
    no sequence numbers in state updates (there's the state seqno, but
    that's not incremented with each message), so you cannot easily find
    how many you've missed.

  * Are you allowed to do something special when you have new data to
    publish over a connection that exhibits packet loss?  For example
    keeping I at Imin for two or three updates?

3. Extensibility

What should I do if I receive an unknown TLV?  I assume I should silently
ignore it if it's inside a Data TLV, and include it in my database and
flood it if it's within a Data TLV, right?

Which messages are allowed to contain extra TLVs?  For example, what
should I do if I receive a Long Network State Update with a bunch of
unknown TLVs interleaved with the Node State TLVs?

4. Jitter

Am I missing something or you're not applying jitter to keepalives?

5. Connections

There's a single connection for all neighbours on a given interface,
right?  Why not call that an Interface, then?

6. Link-local addresses

You're assuming a link-local multicast group, right?  What about the
sender address and unicast packets?  What should I do if I receive a DHCP
message from a global address?  Discard it, right?

7. Neighbor graph

The notion of "neighbor graph" suddenly appears in Section 5.4.  It's
pretty obvious what you mean, but this should be precisely defined
somewhere.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Mon, 23 Feb 2015 12:00:54 +0200

> grokking HNCP yet, so that will have to wait.)

Thanks, we definitely need more eyes on this (keepalive logic was actually flawed in -00, but I dare you to find it without looking at our git repo on drafts :>).

> tight for comfort.  Is there a fragmentation mechanism I've missed

I assume you refer to Long Network Status (on multicast); post MTU, or in secure mode, it should just use the Short one (which is of fixed length). 
The network state TLV used in the short one is just one hash of (ordered sequence of) hashes of all nodes on the network.

The Long is just opportunistic scheme to enable clients to do immediate requests for node data, instead of unicast exchange, if network is small enough and not in secure mode.

> multiple Node Data Replies?  If so, how do you know if you've received the

The assumption currently is that replies are always unicast, and the IPv6 fragmentation works on local link. Current assumption is that sane set of node data fits inside one (potentially fragmented) IPv6 packet (non-jumbogram), essentially limiting the maximum size to <64kb.

(If we hit that size limit, I would rather advocate some sort of node data delta transmission protocol in any case.)

>    backoff, and with what constants?

Nothing happens. You wait for the event that caused the original request to happen again (essentially, Trickle ensures that everyone hears of an update ‘few’ times before it backs off down to relatively long value.)

>    how many you’ve missed.

Nope.

>    keeping I at Imin for two or three updates?

Not in the current spec; the whole thing is ‘best-effort’ and _intentionally_ much slower than it could be. e.g. initial transmission is caused by Trickle, and not immediately, always; a lot of routing protocols for example send immediately (at least in some cases), but current aim is for “sufficient” speed of the state sync and processing/bandwidth conservation than raw speed.

As Trickle parameters used are local implementation choice, I _suppose_ we could actually mandate just a Trickle-like sending algorithm, with default recommendation being Trickle, but it gets complex in writing if not in implementation :) Pull requests welcome though.

> flood it if it’s within a Data TLV, right?

Right. Almost all of node data is essentially opaque to the DNCP base protocol, with the few noted exceptions.

> unknown TLVs interleaved with the Node State TLVs?

Any of them. The messages are defined just by the MUST be present TLVs. 

However, interesting question is, what if the received payload matches multiple messages? Current text 

> 4. Jitter
> 
> Am I missing something or you’re not applying jitter to keepalives?

That is a good point; we will address that in -01. (Similarly to what we do to replies to multicast messages; just [0, Imin/2] SHOULD delay.)

> right?  Why not call that an Interface, then?

In case of HNCP, this is true, as it has connection=(link-local IPv6 UDP-using) interface. In DNCP, a connection may be just e.g. one unicast endpoint you want to talk with over the internet.

> message from a global address?  Discard it, right?

This is specified in HNCP as it is the one with link-local address binding. DNCP can be also used with globals so I do not think the limitation fits there (although obviously the profile will probably want to limit global use to secure mode).

> pretty obvious what you mean, but this should be precisely defined

The later traversing definition more or less describes what it ‘is’; any idea of what a good definition would look like?

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 23 Feb 2015 16:24:54 +0100

>> (before fragmentation) is 1500 bytes.

> I assume you refer to Long Network Status (on multicast);

Yes, sorry.

> post MTU, or in secure mode, it should just use the Short one (which is
> of fixed length).

Ok.  So I send multicast SNS.  I receive NSR.  I'm supposed to send LSR,
right?  But it doesn't fit in maximum packet size, even with fragmentation.

RFC 2460, Section 5:

   A node must be able to accept a fragmented packet that, after
   reassembly, is as large as 1500 octets.  A node is permitted to
   accept fragmented packets that reassemble to more than 1500 octets.
   An upper-layer protocol or application that depends on IPv6
   fragmentation to send packets larger than the MTU of a path should
   not send packets larger than 1500 octets unless it has assurance that
   the destination is capable of reassembling packets of that larger
   size.

> Current assumption is that sane set of node data fits inside one
> (potentially fragmented) IPv6 packet (non-jumbogram), essentially
> limiting the maximum size to <64kb.

You cannot count on that.  See above.

> Right.

Please make that very clear.  Implementors will get it wrong, and we'll
find ourselves unable to extend the protocol.

> Any of them. The messages are defined just by the MUST be present TLVs. 

Again, please make this very clear.  In particular, make it clear that
upon encountering an unknown TLV, the rest of the packet must be processed
as usual.  (The other possible choice is that the whole rest of the packet
is ignored.)

> In case of HNCP, this is true, as it has connection=(link-local IPv6
> UDP-using) interface. In DNCP, a connection may be just e.g. one unicast
> endpoint you want to talk with over the internet.

I see.  I still dislike the term of "connection", which seems to imply
a point-to-point thing.  Ideas?

> The later traversing definition more or less describes what it ‘is’; any
> idea of what a good definition would look like?

Actually, looking at it again, I'm not sure I know what is the neighbour
graph.  It's the directed graph defined by all neighbour TLVs, or the
undirected graph that you get after removing unidirectional neighbours?
I assume the latter.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 23 Feb 2015 17:51:47 +0100

Another question -- is it possible to participate in Trickle-driven
flooding without building the full topology graph?

If not, that's a little disappointing, since Trickle is designed so that
it can be implemented while knowing just my immediate neighbours.  But it
looks to me like I cannot do the activities mandated in Section 5.4
without building full topology.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Mon, 23 Feb 2015 19:00:13 +0200

>   the destination is capable of reassembling packets of that larger

I guess this is another MUST to be added to HNCP text (DNCP itself is not IPv6-specific as such).

I am not convinced by the trend to add fragmentation to every protocol on top of IP{v4,v6} but can be convinced otherwise of course given good arguments. At least in case of HNCP as it works on link-local level only, I think saying you MUST have sane IP stack on both nodes is not overreaching it as there are no middleboxes to worry about.

> You cannot count on that.  See above.

I consider it documentation error, see above :)

> find ourselves unable to extend the protocol.

Ok, I will add one more MUST (although reading the text, I thought it obvious already from the context but guess not).

+      Whole “node data" is owned by the node that
+      publishes it, and it MUST be passed along as-is, including TLVs
+      unknown to the forwarder.

> as usual.  (The other possible choice is that the whole rest of the packet

       <t>DNCP profiles MAY add additional TLVs to the message specified
-      here, or even define additional messages as needed.</t>
+      here, or even define additional messages as needed. TLVs not
+      recognized by the receiver MUST be ignored. </t>

> a point-to-point thing.  Ideas?

Not from me; we had relatively long (and fruitless) internal discussion on this in November IIRC. 

> undirected graph that you get after removing unidirectional neighbours?

The latter. Edited text a bit in few places, dunno if it really helped :)

-Markus

---

From: Markus Stenberg <[email-masked]>
Date: Mon, 23 Feb 2015 19:17:18 +0200

> without building full topology.

You are coming up with same things I have thought about quite a bit too.

The current answer based on strict reading of the spec is no.

The reason isn’t 5.4 (it is just a SHOULD, because you can implement something stubby that just relies on LNS being complete list of nodes known by neighbors). 

Why is it impossible then? Simply because the 5.2 specifies that node data requests MUST be always responded to (as you may not want to actually store any data about anyone else than yourself to start with). I have been debating with myself how to change this.

Is this desirable to be changed? Probably so. 

Simplest change to achieve this would be simply to add ‘if available’ to 5.2 (and perhaps to note in section 4 that the data model is not really normative), and some sort of flag about stubby behavior (notably, assume that there is no HNCP talkers behind the node so it is asked only about it’s own state).

With this scheme, you can have:

[1] ’really stubby HNCP write-only’ which does not store anything except (possibly empty-ish set) of it’s own published node data and one neighbor - the non-stubby router it has chosen. All it needs to know about the other nodes is just a copy of LNS stored somewhere so it can interact with non-stubby router (and pretend nobody else exists so no need for keeping track of even other local neighbors). 

However, I am not sure if this scheme is actually sensible; in practise, if you want ‘write-only’, you really want to just have some exchange with a genuine long-lived HNCP participant with a TTL + early revocation scheme.

[2] ’bit less minimal but still stubby’ HNCP could just keep all node data that has reference in LNS of it’s peers but otherwise work like [1]. Relatively useful, and much simpler to implement than whole thing still.

Note that both of these ’stubby’ variants need ’non-stubby’ one to leech off on the same link. Both would be fine to stick in e.g. host though.

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 24 Feb 2015 23:56:59 +0100

>> should not send packets larger than 1500 octets unless it has assurance
>> that the destination is capable of reassembling packets of that larger
>> size.

> not IPv6-specific as such).

You mean that every HNCP node MUST ba able to accept packets of up to 64kB?
What's the status of typical embedded stacks?

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 25 Feb 2015 00:10:09 +0100

> The current answer based on strict reading of the spec is no.
[...]
> Is this desirable to be changed? Probably so. 

There's not only the stub case that you consider, but also the pure
client/forwarder node -- a node that doesn't wish to publish any data, but
uses static HNCP data, and serves as a link between two parts of the
network.  Ideally, such a node should not contribute any replicated state.

(Note that a Babel/AHCP router that doesn't announce any routes
contributes no state whatsoever to non-neighbouring nodes.  So you can add
arbitrary many intermediary hops with no cost incurred by distant nodes.)

The reason I'm asking is somewhat out of scope for Homenet -- I'm looking
into deprecating AHCP in mesh networks in favour of a subset implementation
of HNCP.  AHCP is a very simple protocol, and one can implement an AHCP
client/forwarder in constant space.  Not so with HNCP -- in HNCP, every
node has a copy of the topology, and contributes a vertex to the replicated
neighbour graph.

HNCP is naive link state, with no network nodes (pseudonodes) and no
DR/DIS/MPR election.  So its scaling is quadratic in the worst case.
Consider a network containing a switched Ethernet backbone consisting
a mere 30 routers.  Unless I'm missing something, this backbone will
contribute no less than 30 vertices and 435 edges in the neighbour graph,
and this state will be duplicated in every single node in the network.

There's an obvious solution -- it is to have pure client nodes that
participate in Trickle but don't contribute a vertex to the neighbour
graph.  But HNCP doesn't support that.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 25 Feb 2015 10:15:01 +0200

On 25.2.2015, at 0.56, Juliusz Chroboczek <[email-masked]> wrote:
> What’s the status of typical embedded stacks?

Configuration dependant more than implementation at least in the few I have played with, but usually they’re really short of RAM so usually configuration is rather conservative. Sticking (say) DTLS in one is probably no-go due to lack of computing power to start with so I am not sure this is that relevant.

That said, from my point of view, if this is really thought to be an issue by the WG, correct solution is to use TLS (+TCP) instead of DTLS (+UDP) in any case.

Cheers,

-Markus

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 25 Feb 2015 10:37:12 +0200

> arbitrary many intermediary hops with no cost incurred by distant nodes.)

That sounds like distance vector <> link state tradeoff (and yes, we know HNCP isn’t a routing protocol but it both exists due to politics, and isn’t one due to politics; good luck shoving IS-IS on top of *TLS, or sticking in dozen+ random TLVs there).

Suggestions on how to address that are welcome of course.

(Forward case is tricky; client isn’t problematic, see below.)

> and this state will be duplicated in every single node in the network.

Yep, intentionally so for now; of course, we could turn it even more in the scalable (routing) protocol direction if there is desire. In another draft for a different WG I have specified auto-area extension for it already :p

> graph.  But HNCP doesn’t support that.

That shouldn’t be hard to address if it seems desirable, but doing (robust) (stateless) forwarding that way is problematic. Willingness to drop one lets you get the other, but not both I think

For the ‘pure client’ (and especially ‘limited client’) case, I would argue that they are not interested in most of the state in HNCP in any case and would want just some sort of request-reply of current state, and possibly notifications about state changes from their first-hop non-client node. 

As an alternative, some flag to say that ‘I do not want to be your neighbor’ would allow read-only client usage of HNCP state using normal RNS+RNDxN messages, but I think nodes would be more interested in per-TLV state that is applicable, and not retrieving whole network state just to get e.g. assigned addresses.

Cheers,

-Markus

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 26 Feb 2015 08:23:23 +1300

> That said, from my point of view, if this is really thought to be an issue by the WG, correct solution is to use TLS (+TCP) instead of DTLS (+UDP) in any case.

I've thought about this in the Anima/GDNP context and reached the
same conclusion. Why make life complicated when TLS makes it simple?

   Brian

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 27 Feb 2015 13:04:49 +0100

> Yep, intentionally so for now; of course, we could turn it even more in
> the scalable (routing) protocol direction if there is desire.

That's not quite what I meant.  I'll try to put it differently.

Right now, an HNCP node performs the following actions:

1. participate in Trickle-based flooding;
2a. contribute a neighbour TLV to the global state;
2b. optionally contribute other TLVs;
3a. maintain a full set of TLVs being published;
3b. maintain a copy of the topology graph.

Now there are different costs associated to these activities, both for
this node and for other nodes.  (1) is cheap for both.  (2) is cheap for
this node, but expensive for other nodes -- the state being contributed is
replicated in all the other nodes.  (3) is the opposite -- it's expensive
for this node, since it requires storing the whole replicated state, but
doen't contribute anything to other nodes.

Now HNCP doesn't allow participating in just some of those activities.  In
particular, there is no way to participate in flooding without
contributing a neighbour TLV (and hence increasing the size of the
replicated state and the replicated neighbour graph).

When you split HNCP into DNCP, I was hoping that you were providing
a means to have nodes that do (1) and (3a) without contributing to the
replicated global state.  But unless I'm missing something, it doesn't.

-- Juliusz