Subject: Re: [Roll] Informed move [was: A proposal for Traffic Loop

From: "Anders Jagd" <[email-masked]>
Date: Mon, 19 Oct 2009 12:24:43 -0400

Pascal,

This is in response to two related mails of yours. My comments/suggestions
are found below, but let me first set the context by quoting from your
mails:

Oct 9:  "A proposal for Traffic Loop avoidance, detection and recovery"
Oct 16: "Re: [Roll] Ew: RPL Design Questions

In the latter, you correctly note how some problems are of a global nature,
while some are local - this with regards to the discussion of "Sequence
number" vs. "Hold-up Timer" approaches:

>The protocol as will be complemented by a loop detection mechanism. A
>proposal was already posted "A proposal for Traffic Loop avoidance,
>detection and recovery". The loop detection is required even if we do
>not do A+B, to cover the window till DAG rebuilds, siblings loops and
>DAO loss loops.
>
>The local route poisoning and the global DAG rebuild provide really
>different services and operate at a very different level.

The "loop detection" that you mention was discussed in your other mail,
specifically addressing the following bits proposed for the flow label:

>Outwards    : 1 bit
>Sibling     : 1 bit
>Rank_error  : 1 bit
>DAO_Error   : 1 bit
>Rank        : 8 bit
>Instance ID : 8 bit

Now for my comments:

I completely agree on the "global vs. local" remark. We are aiming at a
protocol suiting networks with sizes varying within many orders of
magnitude. Even for one network, the DAG will be dynamic in nature, as well
as possibly quite asymmetric/"unbalanced".

I therefore believe the base protocol should allow for at least 3 different
methods related to loop avoidance and detection (since networks have
different requirements), and that this be "run-time" configurable (since
networks are dynamic and may be asymmetric):

1) Sequence number/heartbeat (as related to controlled merging of floating
DAGs)
2) Hold-up timer (as related to controlled merging of floating DAGs)
3) Count to infinity/"TTL"

I suggest that we allocate enable flags in the DIO for this - to allow for
root and other parent nodes to selectively enable sub-DAGs to use/assume
each of the above methods. 

The root would set the flags according to management plane configuration
and/or topological awareness (which may be dynamic as the network expands
and contracts).

Any parent node would be allowed to selectively disable (or maybe even
enable) features based on localized topological awareness.

With regards to your detection bits (flow label and others), I would like to
suggest:

----
Instance ID bits 
("Instance forwarding"): 

I don't think DAG "Instances" have been well enough defined to really
address this, but if you are saying that we should not route between DAGs
with different Instance IDs, and that we should use those bits to detect
inconsistencies, then I agree.
----
Outwards, Rank, and Rank_error bits 
("DAG inconsistency loop detection"): 

Let me first quote your mail:
>A node emitting a packet must reset the Rank_error bit and the Outwards
bit.
>A router MUST also reset the Outwards bit if it is using the default route
inwards, either via a sibling or a >parent, and set the bit if it is using a
DAO route, either via a sibling or a child.
>A receiver detects an inconsistency if it receives a packet going inwards
from a source with a lesser Rank, >or outwards with a higher rank.
>Upon inconsistency, if the Rank_error bit was not set then the Rank_error
bit is set. If it was set the packet >is discarded. This is done to cover a
rare re-sequencing of the DAG.

I agree, this would help when encountering temporary loops.
----
Sibling bit
("Sibling loop avoidance"):

I propose to generalize your "max 1 sibling forwarding" approach by
allocating N bits in the flow label (N somewhere between 1 and 4) for a
"horizontal TTL"/"sibling hop count". 

This would be initialized to some number (default 1) by any node first
forwarding through a sibling, and decremented by sibling nodes again
forwarding through a sibling. Upon reaching 0, packet must be either dropped
or sent up the tree (at which point nodes above can re-initialize the
horizontal TTL). 

This based on "Horizontal TTL" being enabled through the DIO. For this, I
thus suggest we consider having separate TTL configuration (DIO) and count
(individual packets) for "Vertical" (up or down the DAG) and "Horizontal"
(sibling) flows. DIO may also include configuration of max settings for
those. "Horizontal TTL = 0" possibly indicating not to route through
siblings and "Vertical TTL = 0" possibly indicating not to rely on vertical
TTL.

Again, this to address the dynamic and varied scope of network topologies we
are faced with.
---
DAO_Error bit
"DAO inconsistency loop detection":

Let me again quote your mail:
>In a general manner, a packet that goes outwards should never go inwards
again. 
> So rather than routing inwards a packet with the Outwards bit set, the
router MUST discard the packet.
>If DAO recovery is in place, then the router MAY send it back to the
source.

I suggest we some times allow for a packet which was initially sent up the
tree to "change direction" one (and only one time). This for P2P purposes.

I suggest that the source node of a packet initializes a  (1 bit) direction
shift counter ("UTurn") to 0 (no change allowed) or 1 (one change allowed). 

A node wishing to change direction may do so if the bit set, but must also
clear the bit.
----

In summary, I propose the following for the DIO and the flow label:

DIO:

  1 bit: Enable/disable "Sequence number/heartbeat" based merging
  1 bit: Enable/disable "Hold-up timer" based merging
  TBD bits: Vertical TTL initial setting (0 -> Don't assume TTL)  
  TBD bits: Horizontal TTL initial setting (0 -> Don't route through
siblings)

Could limit "Vertical TTL" bits to say 4 bits by using 1 to the power of the
value chosen. 
For "Horizontal TTL", 4 bits, maybe less, should suffice.
 
Flow label:

  1 bit: Outwards - based on direction of packet
  1 bit: Rank_error - set when detecting inconsistency of "Outwards bit" vs.
"Rank relationship"
  TBD bits: Horizontal (sibling) TTL
  1 bit: UTurn_count: - Number of remaining allowed changes of
inward/outward direction
  8 bit Instance ID - Pending more discussion
  8 bit: Rank -  To detect rank inconsistencies (pending discussion of
number of bits for Rank)

Best regards,
Anders