Subject: [Roll] Partial review of draft-dt-roll-rpl-00.txt

From: Alexandru Petrescu <[email-masked]>
Date: Wed, 01 Jul 2009 15:52:25 +0200

Dear ROLLers,

I've reviewed draft-dt-roll-rpl-00.txt up to section 5.3 "Trickle Timer
for RA."

It is a 60-pages long document, out of which 50 pages are effective
descriptions.  It is roughly divided in 3 conceptual parts: the
DAG-oriented protocol (supposedly inherited from the Thubert Tree
Discovery protocol), the Trickle timer part (probably inherited from
Levis Trickle works) and the 3rd part that I haven't read.

Reading the document requires concentration and exposes consistency
between various parts.  Some times it is incosistent.

The document is in its infancy (00) and I expect many changes to occur
to it later.  Because of this I doubt a detail review is of any use
right now.

The document describes examples at several places, and this is very 
useful for understanding the intention.

However, there are a few questions which can't be answered obviously by 
reading the draft:
-why DAG?
-how many interfaces does a node have?
-how are the addresses and prefixes configured on the nodes?
-and some nits.

Title:

I find "RPL" to risk clashing with other uses of the same abbreviation
at IETF, e.g. Rendez-vous Point Link RFC 5015.  This could make the
conversation difficult when we will probably try to add an RPL to RPL.
I suggest ROLL instead.

> Because those requirements are heterogeneous and sometimes 
> incompatible in nature, the approach is first taken to design a 
> protocol capable of supporting a core set of functionalities 
> corresponding to the intersection of the requirements.  (Note: it is 
> intended that as this design evolves optional features may be added 
> to address some application specific requirements).  All "MUST" 
> application requirements that cannot be satisfied by RPL will be 
> specifically listed in the Appendix A, accompanied by a 
> justification.

In the current 00 version, this is not the case: there is no stated list
of requirements which are satisfied by the protocol 'RPL'.  Probably it
will come later.  If not, we may have a big problem: working without
requirements.

> Autonomous:  Refers to the ability of a routing protocol to 
> independently function without requiring any external influence or 
> guidance.  Includes self-configuration and self-organization 
> capabilities.

Self-configuration of what?  Does each node self-configure an address
for itself?  How?  Does it self-configure a prefix for itself?  How?
Does it self-configure some routes?  How?

> DAG:  Directed Acyclic Graph- A directed graph having the property 
> that all edges are oriented in such a way that no cycles exist. In 
> the RPL context, all edges are contained in paths oriented toward and
>  terminating at a root node (a DAG root, or sink- typically a LBR).

The DAG theory is clear.  But what does DAG mean in the context of a
network?  A link between siblings is obviously bidirectional: this makes
for a loop.  But it's said no loop.

I have very strong doubts about the use of DAG theory in this draft.  I
will not go as far as to say it is useless, but I'm tempted to.

LBR: throughout the document the terms LBR, Sink and DAG Root are used
interchangeably: why three terms when one is sufficient?

DAG: in theory, a DAG can be made of two separate disconnected acyclic
graphs: it's still one DAG.  The definitions above don't mention it.
Later in the text the terms 'parallel' DAGs are used: are two parallel
DAGs a single DAG?  Are two parallel DAGs connected?  It is not clear.

> DAG Sibling:  A sibling of a node within a DAG is defined to be any 
> neighboring node node which is located at the same depth, or rank, 
> within a DAG.

The 'sibling' as I understand it has sense in a tree only.  Here we have
DAGs.  'Neighbor' is not defined.  So, can there be two siblings which
are not neighbors?  I guess yes, but the definition says no.  Depends
what a 'neighbor' is.  What is a neighbor?

> DAG Root:  A DAG root is a sink within the DAG graph.  All paths in 
> the DAG terminate at a DAG root, and all DAG edges shared with nodes
>  adjacent to a DAG root are oriented toward the DAG root.

What does 'adjacent' mean?  Is it a neighbor?  A sibling?

> In many use cases, source- sink represents the foremost traffic flow,

'Foremost' or 'inward'?  I think it is meant 'inward', by the later
definition of 'inward'.

> Maintaining default routing towards DAG roots is therefore a primary 
> functionality for RPL.

Well I agree mostly.  But I would have liked the primary functionality
to be to maintain consistent routes for all destinations within the
network, not just a default route to the Internet.

> Inward:  In the context of RPL, inward refers to the direction from 
> leaf nodes towards DAG roots, following the orientation of the edges
>  within the DAG.

What is a 'leaf' node?  Is it the deepest node?  Is it any node except
the DAG Roots?

> MP2P: Multipoint-to-Point; used to describe a particular traffic 
> pattern.  A common RPL use case involves MP2P flows collecting 
> information from many nodes in the DAG, flowing inwards towards DAG 
> roots.  Note that a DAG root may not be the ultimate destination of 
> the information, but it is a common transit node.

I agree with this term, MP2P, and with the fact that it is probably the
main type of traffic pattern, because it corresponds to the activity of
querying a set of sensors.

However, I think there may be an issue with saying just what is said
above.  If I think TCP: the TCP is a three-way handshake.  If the query
and responses are TCP then the traffic doesn't correspond precisely to a
simple MP2P traffic: there are acks from querier to queried nodes which
are not MP2P but P2P.

I think MP2P as described above is ok only when we talk about the
queried data sent by sensors to the querier, and when that traffic is
UDP only (or ICMP responses, or similar, but not TCP nor HTTP).

> The aim of this section is to describe RPL in the spirit of 
> [RFC4101].

This is excellent initiative!  RFC4101 says at some point that the model
should feature a diagram of the major communicating parties and their
inter-relationships.  I think the Figures 1 and 2 of this drat try to
play this role.

But these figures don't show messages between entities, just links and
too many nodes, maybe.

I would have preferred to see entities and messages between them.

> Note that in this document, the terms `node' and `LLN router' are 
> used interchangeably.

Why not just one?  It would ease reading.

> RPL is strictly compliant with layered IPv6 architecture.

What does this mean?  What is the layered IPv6 architecture?

> usually low bandwidth with low packet success rate
                                                ^delivery

> 3.2.4.  Autonomous Operation
> 
> Nodes running RPL are thus able independently and autonomously 
> discover a network topology and compute and install routes, without 
> requiring further administrative interaction.

I don't understand the 'thus' above?  There's no preceding text making
one conclude that RPL nodes discover network topology without further
administrative interaction.  It is not said anywhere how are the
addresses and prefixes assigned to nodes in the first place.  They must
come from somewhere but it's not said where from.  What is the starting
point?  An admin?

> As DAGs are organized, RPL will use a Destination Advertisement 
> mechanism to build up routing state in support of outward P2MP 
> traffic flows.  Traffic directed from one node to another may flow 
> inward along the DAG until a common parent is reached capable of 
> directing the traffic along the outward path.

Traffic between two siblings being forced through a parent, despite the
existence of a straight link is sub-optimal routing, and it is not good.
  The text says 'may' but it is not capitalized.  I am afraid this may
become a MUST later, and I oppose it.

> RPL constructs one or more base routing topologies, in the form of 
> DAGs, over gradients rooted at designated nodes.

What is a gradient?

Also, I assume a topology is a set of physical links.  These links can't
be put up/down by some protocol but by human intervention.  I thought
the protocol builds a set of paths over some links which must be up.

I think we may have a misunderstanding between what is a 'topology' and
a 'path'.  We could define it better.

> increases path diversity

(yes, this is too short citation, but what is 'path diversity'? I think
  it appears 5 times; is it the 'multipath'?)

> As nodes join the DAG they are able advertise the fact by beginning 
> to multicast the DAG information in Router Advertisements.

I agree.  This makes me think you have a precise idea about the link
layer having multicast features. (RA multicast is link-layer multicast).
  Is it so that you assume the link-layer has multicast features?  I
agree if yes.

> node may be unfairly unable to become a DAG parent

Hmmm... does this mean the node is fairly able to become a DAG parent?
(double negation).

> When receiving traffic forwarded from a sibling, the traffic should 
> not be forwarded back to the same sibling in order to avoid a 2-node
>  loop.

Oki.  But the node receiving should have a means to know where is the
traffic coming from, and the src field is not useful because it's the
original source.  So the MAC address?  What kind of MAC addresses are
used?  Some links don't have MAC addresses.

> By employing this procedure, the LLN is able to set up a path- 
> constrained DAG, rooted at designated nodes, with other nodes 
> radiating outward from the DAG root in an orderly fashion.

'outward' is from DAG root to other nodes, ok.  But other nodes
radiating outward?  What do they radiate?  Or are they just placed as
radiuses around the the DAG root?

> MP2P traffic intended for the default destination flows inward along 
> the DAG towards the root, and transit nodes are able to leverage the 
> path diversity of the DAG as necessary.

Ok, but what are the transit nodes?

> the DAG may is not offering a default route.

Nit: may is not.

> A DAG, or a sub-DAG, may also become isolated because of a network 
> element failure.

What is an 'isolated' DAG?  There's no definition in the draft.

Another DAG definition from theory shows a DAG can be made of
disconnected acyclic graphs.  Such a graph could be considered
'isolated'.  But is this the meaning in this draft?

> maintain parallel DAGs

Also, what is a 'parallel' DAG?  A topology with the same number of
vertices and same edges as the parallel topology?

> o  A DAGID used to uniquely identify the DAG.  Typically the 
> (potentially compressed) IPv6 address of the DAG root.  May be tested
>  for equality.

There are at least two means of compressing IPv6 addresses I've seen in
the MANET WG and elsewhere.

What is the test for equality?  Longest-prefix match?  Exact match?  How
are compressed addresses compared?

> [DIO contains]... o  Indications for the DAG, e.g. grounded or 
> floating.

But this information could come from other existing fields in the RA,
i.e. the default route.  Default route is the only distinction between
grounded or floating, so why not reusing the default route (a lifetime
field) in the existing RA.

> In addition to periodic RAs, each LLN node will respond to Router 
> Solicitation messages according to [RFC4861].

Will each LLN node join the corresponding multicast group?  RFC4861
requires it so.  So I think it is worth mentioning it joins that group
before responding to RS.

> marking within the IPv6 header

Nit: missing dot at end of phrase.

> o  Is the neighboring node heard reliably enough

How is the test performed to decide whether a neighbor (what is a
neighbor?) is heard reliably enough?

> are the metrics stable enough

How would one test for stable metrics?  What is a stable metric?

> When the node inserts the first DAG parent into the empty DAG parent 
> set, it is able to join the DAG.  The node will join the DAG at a 
> depth deeper than that of its deepest DAG parent.

This begs the question: what is the deepest DAG parent when the DAG
parent set is empty?

> 3.3.1.4.1.  Example

Thanks for the example.  This is very good to understand what is all about.

> 3.3.3.  Destination Advertisement
> 
> As RPL constructs DAGs, nodes are able to learn a set of default 
> routes in order to send traffic to the sink.

How do the nodes learn the default routes?  What does a default route
look like?  Is it ::/0 and a link-local gateway address?  Where does it
come from?

> [DAO contains]... o  A lifetime and sequence counter to determine the
>  freshness of the Destination Advertisement.

Is this sequence counter the same as the Sequence Number in the DIO base
option pp. 26?

> o  Reverse Route information to record the reverse route when the 
> intermediate nodes along the path cannot support storing state for 
> Hop-By-Hop routing.

What is 'hop-by-hop' routing?

What is the 'reverse route'?

> At this time the node may perform route aggregation if it is able, 
> thus reducing the overall number of DAOs.

I am  pretty sure we don't have a common understanding of what route
aggregation is and how could it be performed.

> 3.3.4.  Examples
> 
> Consider the example LLN physical topology in Figure 1.  In this 
> example the links depicted are all usable L2 links.

First, I wanted to say thank you for the examples.  All examples and
figures are paramount for understanding what is meant.

And the question: in figure 1 node 32 has 7 links: is this a node with 7
interfaces?

> 3.4.2.  Loop Avoidance
> 
> The goal of a guaranteed consistent global routing solution for an 
> LLN may not be practically achieved given the real behavior and 
> volatility of the underlying metrics.  The trade offs to achieve a 
> stable approximation of global convergence may be too restrictive 
> with respect to the need of the LLN to react quickly in response to 
> the lossy environment.  Globally the LLN may achieve a weak 
> convergence, in particular as link changes are able to be handled 
> locally and result in minimal changes to global topology.
> 
> RPL does not aim to guarantee loop free path selection, or strong 
> global convergence.  RPL includes mechanisms to detect and break 
> loops, and to try to avoid the creation of loops when undergoing 
> topology changes.  When RPL parameters are properly configured, in 
> particular with respect to metric reporting and route update 
> intervals, it should be possible for RPL to achieve a weak global 
> convergence while still responding and reacting to changes in the LLN
>  environment.

Sorry, this section is a declaration of intention, it is ok, but it is
not a mechanism for loop avoidance.

> 4.1.  Routing Metrics

This section does not mention the routing metric most used: the number
of IP hops.  I think it should.  It is the 8bit field named 'metric' in
RIPng RTE, and some of the 'Metric' fields in OSPF Database Description
(only some).

> The key design point is that each node is solely responsible for 
> setting the vector that it sources in the gradient, which is achieved
>  by selecting its preferred parent.

What is a 'vector' and what is a 'gradient'?

> As a result, the gradient is not broken if another node makes its
> decisions in as antagonistic fashion, though an end-to-end path might
> not fully achieve any of the optimizations that nodes along the way
> expect.

Sorry?

> 5.1.  DAG Information Option
> 
>    The DAG Information Option carries a number of metrics and other
>    information that allows a node to discover a DAG, select its DAG
>    parents, and identify its siblings while employing loop avoidance
>    strategies.

I am happy the protocol has a means to encode different metrics.

>    BootTimeRandom:  A random value computed at boot time and recomputed
>          in case of a duplication with another node.

How is the random value computed?  Is it really random?  Is there a risk 
that we assume it random but it may actually be not so random when all 
sensors perform same algorithm for randomness computing?  RFC4086 has 
some requirements around this.

>    DAGDelay:  16-bit unsigned integer set by the DAG root indicating the
>          delay before changing the DAG configuration, in TBD-units.  A
>          default value is TBD.  It is expected to be an order of
>          magnitude smaller than the RA-interval.  It is also expected to
>          be an order of magnitude longer than the typical propagation
>          delay inside the LLN.

DAGDelay expressed in what?  Seconds?  Mili-seconds?

What is an RA-interval?

What is an order of magnitude when things are encoded in binary (and not 
decimal)?  Is it still 10 or is it 2^10?

If DAGDelay is 2^16 then does this mean the max propagation delay 
through the LLN is 2^6?  Is there such a link layer with such delays?

> RA-DIO should be send

Nit: sent.

>    DIOIntervalMin:  24-bit unsigned integer.  Used to configure the
>          trickle timer governing when RA-DIO should be sent within the
>          DAG.  DIOIntervalMin is the minimum configured interval for the
>          RA-DIO trickle timer expressed in units of 10ms.  For example,
>          a DIOIntervalMin value of 10ms is expressed as 0x000001.

This is a field difficult to deal with programattically.  I mean there 
are standard uint8_t, uint16_t, uint32_t, etc. but there's no uint24_t. 
   Programmer needs to shift bits around to manage this field.  Why not 
making it uint32_t?

Besides, the max DIOIntervalMin on 24bit tens of milliseconds makes for 
almost two days.  Why not making it longer, like a whole month.  A month 
is what an airplane blackbox seems to last emitting, to not cite recent 
news.

>    PathDigest:  32-bit unsigned integer CRC, updated by each LLN Node.
>          This is the result of a CRC-32c computation on a bit string
>          obtained by[...]

What is CRC?  What is CRC-32c and how is it computed?  Why not the 
Internet checksum (used by UDP and ICMP at least) which are standardized 
at rfc1071 "Computing the Internet Checksum", I think.  The details of 
computing are mentioned at least in the ICMPv6 RFC and it is 
straightforward guidance for implementation.

>   DAGID:  128-bit unsigned integer which uniquely identify a DAG.  This
>          value is set by the DAG root.  The global IPv6 home address of
>          the DAG root can be used.

The IPv6 home address?  In this case the rfc3963 at least should be 
cited because it talks mobile routers and IPv6 home addresses.

>    Suboption Type:  8-bit identifier of the type of suboption.  When
>          processing a DIO containing a suboption for which the Suboption
>          Type value is not recognized by the receiver, the receiver MUST
>          silently ignore and skip over the suboption, correctly handling
>          any remaining options in the message.

This sounds as we want it to be TBA and request IANA assignment.

> 5.1.1.1.4.  DAG Metric Container
> 
>    The DAG Metric Container suboption may be aligned as necessary to
>    support its contents.  Its format is as follows:
> 
> 
>         0                   1
>         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -
>        |   Type = 2  

TBA with IANA.

>   The DAG Metric Container is used to report aggregated path metrics
>    along the DAG.

What does it mean aggregated path metrics?  IS it that there are several 
metrics listed in the container?  Or just a sort of "aggregation" of 
them all?  I prefer the former.

The ContainerLen field is on 8bits, and expresses number of octets. 
This makes for a Metric Container of maximum 255 octets.  This limits 
the number of metrics it could hold.

If we consider the energy metric for link to be e.g.:

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |      Type     |    Length     |            Reserved           |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          Max Link Energy                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          Min Link Energy                      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

This makes for 12 octets and represents only energy for one link.  If we 
want to send several links then it grows substantially.

>         0                   1                   2                   3
>         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>        |   Type = 3    |    Length     | Prefix Length |Resvd|Prf|Resvd|
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>        |             Destination Prefix (Variable Length)              |
>        .                                                               .
>        .                                                               .
>        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

I think this Destination Prefix is not variable length.  It is length 
128bits and the dots on the left and right columns should disappear and 
"(Variable Length)" should disappear too.

Alex