[Roll] Review of draft-ietf-roll-enrollment-priority-05

[Konrad Iwanicki <[e-mail]>]

Dear Rahul, Pascal, Michael, and all,

As promised, I am sending my remarks about the enrollment priority 
draft, version 05, so as to point out the issues I have with the draft, 
thereby providing some starting point for discussion at the August 
interim. Sorry for the text being rather lengthy, but I wanted to 
highlight all major issues that came to my mind. I am not providing any 
editorial changes, because those below are more important at this point.


PROTOCOL OPERATION WRT. FIELD MIN PRIORITY

Based on your comments on my previous review, I gather that there are 
two different ideas on how the protocol should work, clarifying which 
was also the reason for the questions I put in my previous review (of 
the draft version 04).

Unless noted otherwise, the text below refers only to the management of 
field min priority. In other words, let us completely ignore field 
DODAG_Size for a while. We will return to it later.


IDEA 1 (GLOBAL)

The first idea on how the min priority field should be managed is 
supported by Pascal, and I will refer to it as GLOBAL. Essentially, it 
works as follows:

1. The min priority values are generated solely by the DODAG root node; 
other nodes are not allowed to change these values.

2. A node extracts the value from a received option, stores it locally, 
and uses it as a base when computing the proxy priority for EBs, which 
may also account for the node's local constraints (e.g., load); however, 
per 1., only the originally received (and stored) value of min priority 
is used in the options in DIOs sent by the node.

3. An option received from ANY node can be used as the source of the min 
priority value but the receiving node has to be able to judge whether 
the received value is fresher than the one it already stores locally.

4. To this end, a lollipop sequence counter that I proposed, let's call 
it OSN, can be used. I suggested adding it to the option, but others 
suggested using some existing counters. This is immaterial for 
now---more on that later; instead, let us just assume that we have OSN 
mapped to some counter.

5. In any case, the root node bumps its OSN when it produces a new value 
of min priority. (This condition can also be relaxed but I'd rather not 
make this text longer. We can discuss this during the interim.)

6. Whenever a node receives an option with a value of OSN that is 
greater than its own local value of OSN, it adopts the received value of 
OSN and the received value of min priority as its local ones. Those 
values will then be sent in the options in DIOs transmitted by the node.

This is a really simple and robust solution. Its main advantage is that 
there are normally many paths that allow a node to learn the value of 
min priority, which alleviates the problem of nodes that do not support 
the option or nodes that experience (temporal) down times, overload, and 
the like. The problem of the different paths being asynchronous, and 
hence offering different propagation times for the values of min 
priority, is in turn solved by OSN: the counter unambiguously 
discriminates between fresher and older values. The effect is that as 
long as each node has at least one neighbor (not necessarily a parent) 
that supports the option, the min priory values will be eventually 
consistent globally.

In contrast, the main drawback of this solution is that the value of min 
priority is global. In particular, it does not take into account any 
heterogeneity in the load, available resources, etc. in different 
regions of the DODAG.


IDEA 2 (FLEXIBLE)

Michael and Rahul thus advocate an alternative idea, let's call it 
FLEXIBLE. In this approach, it is possible to adjust the value of min 
priority per node by incrementing the base value the node has originally 
received. Although the new version (05) of the draft does not describe 
this in sufficient detail, from Michael's comments I gather that the 
envisioned solution is something as follows:

1. The root sets a value of min priority in the option in its DIOs.

2. A non-root node obtains the value of its min priority only from an 
option received from its preferred parent and stores this value locally. 
It can then only increase the local value, for instance, accounting for 
its local constraints, before putting it into EBs and the options 
transmitted in its own DIOs to its children. In other words, the value 
of min priority can only grow at each hop, reflecting the local 
constraints of the nodes on the path upward to the root.

3. Since for each node, there is only one source of min priority values 
(its preferred parent), there are no conflicts. Consequently, in theory, 
we could omit OSN, as is the case in the current version of the draft. 
(This approach is wrong, as we will see shortly.)

4. To be compatible with the DIO processing rules in RFC 6550, a node 
receiving an option with min priority from any neighbor performs the 
processing according to the following rule (currently missing in the 
draft): "When processing the option, a node ignores the value of min 
priority in the option if the option does not come from the node's 
preferred parent." (This rule is again wrong, as we will see shortly.)

5. If the node's preferred parent does not support the option, the node 
assumes a default value (0x40) for its local min priority. This value, 
potentially increased to account for the node's local constraints, is 
put in the options in the DIOs transmitted by the node to its children.

The main advantage of this approach is that the min priority value can 
be adjusted in a DODAG subtree. The approach thus offers much more 
flexibility in configuring the values: an entire subtree that is 
overloaded or experiences other problems can adopt a higher min priority 
values so as to deflect enrollment traffic to other parts of the DODAG. 
A disadvantage is in turn that the approach precisely defines the path 
along which a node has to learn its value.


PROBLEMS WITH IDEA 2 (AND A POSSIBLE SOLUTION)

However, because of the existence of just a single path for propagating 
min priority value to each node, FLEXIBLE, as presented hitherto, is wrong.

To explain, an important use-case, mentioned also in the present version 
of that draft, is disabling enrollment in an entire DODAG. This is done 
by the DODAG root setting its min priority value to 0x7f. Now suppose 
the DODAG root has done this and that there exists a node, let's call it 
X, in the DODAG that does not support the option. The children of node X 
would thus adopt values 0x40+delta (depending on their local 
constraints) as their min priority values. Since 0x40+delta need not be 
equal to 0x7f, an entire subtree of node X need not disable enrollment, 
which is invalid.

In general, in FLEXIBLE, nodes that do not support the option are a 
major problem, as their ancestors disregard any decisions of upstream 
nodes, including the root. The problem can be solved as follows.

- We use multiple paths for propagating min priority information but one 
of them is preferred by each node (the one through the node's preferred 
parent).

- To ensure consistency, we do employ the aforementioned OSN. Again, for 
simplicity let's assume that it is incremented whenever the DODAG root 
produces a new value of min priority but, like in GLOBAL, this condition 
can be relaxed.

- There is no default value (0x40) a node ever adopts for its min 
priority. (Apart perhaps from the value accompanying the initial OSN value.)

- Each node locally stores:
   * the last value of OSN
   * the accompanying value of min priority
   * a bit, let's call it PB, indicating whether the above values come 
from the node's preferred parent (1) or not (0)

- In contrast, to the present version of the draft, we maintain the 
following invariant:
     "For a given OSN value, the value of min priority at any node is 
greater than or equal to the value of min priority at the root node."
   This is to ensure that no node, including the children of a node that 
does not support the option, is able to override the root's setting of 
min priority down for a given value of OSN. In particular, the invariant 
ensures that if the root disables enrollment globally, then so will all 
nodes (under the same assumptions on connectivity as in GLOBAL).

Given these points, the specific rules for processing the option are as 
follows:

1. If a node receives an option with a greater value of OSN than its 
local one, then eventually it adopts the received values of OSN and min 
priority as local ones, and sets PB appropriately (i.e., to 1 if the 
option is received from its preferred parent or 0 otherwise). It does 
not have to do this immediately. In particular, it may wait for a while 
to receive the option with the greater OSN from its preferred parent. 
Nevertheless, eventually it MUST adopt the greater OSN (and an 
accompanying min priority).

2. If a node receives an option with the same value of OSN as its local 
one then:
   a. if the option is received from its preferred parent, then it 
adopts the value of min priority from the option and sets PB to 1.
   b. otherwise,
     i. if its local PB is 1, then it ignores the received option;
     ii. if its local PB is 0, then it sets its local min priority to 
the minimum of its local min priority and the value of min priority from 
the option

3. If a node receives an option with a smaller value of OSN than its 
local one, then it ignores the received option.

4. If a node changes its preferred parent, then it sets its PB to 0.

5. If a node sends the option in its own DIO, then it puts in the option 
its local value of min priority or a greater value (e.g., taking into 
account the node's local constraints). It can never sent the option with 
a lower value of min priority than its local one.

This should do what I would expect from FLEXIBLE. However, I wrote this 
up in a haste, so it would be great if somebody verified the above 
algorithm.

As a side note, the algorithm suggests that FLEXIBLE is indeed a bit 
more involved than GLOBAL, so a decision should be made, which of them 
to put in the draft.


FURTHER ISSUES UNCOVERED IN THE DRAFT OR TO BE DISCUSSED AT THE INTERIM

Irrespective of the decision whether to settle down on GLOBAL or 
FLEXIBLE, I believe that the following issues also have to be covered in 
the draft (and discussed during the interim).

1. Should DODAG_Size be part of the option?

I mentioned this in my previous review and there has been some 
discussion already. I would just like to add one observation to that 
discussion: whereas min priority can follow either GLOBAL or FLEXIBLE, I 
believe there is an agreement that DODAG_Size should follow GLOBAL when 
it comes to propagating its value in the network. This information may 
influence our decision on which of the approaches to adopt for min 
priority and whether to put DODAG_Size in the option at all or move it 
to another one.

2. Which counter to use as OSN?

I proposed a dedicated counter, which I believe is a clean solution. 
However, there are other possibilities. I also believe that we agreed 
that DTSN from DIO base is not the best choice. In my view, nor is 
DODAGVersion but we can discuss this.

3. How do changes to min priority (and OSN) affect DIO Trickle timers?

This is currently not covered in the draft. However, I would imagine 
that some decisions regarding min priority should be propagated fast in 
a DODAG, and hence require Trickle timer resets. In particular, I would 
expect that disabling enrollment globally should be disseminated as soon 
as possible. Therefore, if I were to suggest anything, I would say that 
a change by a node of min priority to the maximal value (0x7f) from a 
lower one MUST entail a Trickle timer reset. In turn, a change from the 
maximal value to a smaller one MAY/SHOULD entail a Trickle timer reset. 
Other changes are, at least in my view, not that important, but this can 
and should be discussed.

4. How does a (temporal) lack of a preferred parent affect the proxy 
priority of the node in EBs (and in general, the node's behavior)?

This is also ignored in the draft but it may happen that a node does not 
have any preferred parent for a while. In this case, it is unable to 
handle any enrollments. What should it do? I would expect that it would 
advertise the maximal proxy priority in EBs. However, should it also 
modify its local min priority? I would probably be against.

Plus there are smaller issues I mentioned earlier, and I probably forgot 
something. In any case, sorry again for such long a text but I hope it 
may help during the interim.

Best,
-- 
- Konrad Iwanicki.