Subject: [Roll] parent ordering

From: Thomas Watteyne <[email-masked]>
Date: Tue, 22 Sep 2009 13:14:28 -0700

Dear ROLLers,

There is a concept that keeps coming back, which I think needs to be 
discussed:
- in the -01 draft, section 3.3.1.5: "A node must maintain its DAG 
Parent set such that its most preferred parent from the OCP goals also 
has the greatest rank value in the DAG parent set."
- in the -01 draft, section 3.3.1.5: "No nodes of greater rank than the 
most preferred parent may be in the DAG Parent set;"
- in the -01 draft, section 3.4.1: "For a node N, and its most preferred 
parent M, [...] all parents in the DAG parent set must be of a rank less 
than or equal to DAGRank(M)."
- Dominique Barthel started a similar discussion last month 
(http://www.ietf.org/mail-archive/web/roll/current/msg01757.html), yet 
the answers given at the time have not convinced me.
- "The rule should now say that we derive our own depth from the 
preferred parent + link cost, and then an acceptable parent is anyone 
that's inwards from us, in your case A, B and C." in Pascal Thubert's 
e-mail http://www.ietf.org/mail-archive/web/roll/current/msg01778.html 
[note that Pascal's comment is exactly in line with the discussion 
below, yet this is not what is stated in the draft]

My view of DAG routing is the following. Let's say I am a node. When I 
participate in a network, I discover my neighbors, their rank (which 
they tell me in their DIO's), and the cost of the links connecting us 
(e.g. which L2 tells me, or whatever metric the OCP states). I then 
calculate, for each neighbor, what my potential rank would be if I chose 
him as my preferred parent (e.g. by adding his rank to the cost of the 
link connecting us, or whatever function the OCP states). I end up 
choosing the minimal potential rank, which I announce as my rank in my 
DIOs. When asked to forward a message, I look at my neighbor list, 
discard the ones which have a larger rank than myself, and try sending 
the packet to the neighbor which has the lowest rank among all neighbors 
(my preferred parent). If L2 tells me that failed, I work my way down 
the list, sending to the neighbor with the second-lowest rank, etc. Of 
course, every time I hear a DIOs, I update my neighbor's rank 
accordingly, and recompute mine, if needed.

To exemplify this idea, we have taken connectivity traces gathered by 
Jorge Ortiz and David Culler, and computed the DAG with ETX is used as a 
metric. Please take a look at 
http://wsn.eecs.berkeley.edu/connectivity/network_gradient.php?dataset=soda&sink=141&run=1&frequency_diversity=channel&channel=11 
<http://wsn.eecs.berkeley.edu/connectivity/network_gradient.php?dataset=soda&sink=141&run=1&frequency_diversity=channel&channel=11>. 
In the upper graph, the link ETX is color-coded, and each node is 
attached an identifier and its rank. Node 141 (upper right) is the LBR, 
at rank 0. The ETX metric causes the rank of the nodes to increase while 
moving away from the sink. In particular, node 119 (center) ends up with 
a rank 2.19, which it has obtained by adding 1.14 (the ETX of link 
119-146) to the rank of node 146 (1.05). The lower graph depicts the 
same topology, with links connecting each node with its preferred 
parent. Node 119's preferred parent is [email-masked], yet it has a number of 
alternate parents ([email-masked], [email-masked], [email-masked]) and other neighbors of 
higher rank. When forwarding, 119 will try 146 first, then 142, then 
410, then 116.

To prove the functionality of this approach, we have deployed an 86-node 
“urban” network, running single DAG network with hop count as a gradient 
metric, and two distinct sinks. 
http://senseandsensitivity.rd.francetelecom.com/ provides an interface 
to the database filled with the data collected and shows the topology, 
path length and many other performance measurements. I have an 
open-source implementation of the same protocol stack which runs on 1kB 
RAM eZ430-RF2500 motes, proving the extreme simplicity of this approach.

The simple DAG maintenance and forwarding algorithm described above has 
shown to work by simulation and experimentally. As a result, I have a 
hard time understanding the advantages of the (more complex) concepts 
developed in -01. Is there anything I am missing, or could the draft be 
further simplified? All comments are welcome!

Kind regards from sunny Berkeley,
Thomas

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 23 Sep 2009 15:42:21 +0200

Hi Thomas

There are 2 questions here:

One is whether we should differentiate parents that could become
preferred because they do not cause the rank of this node to augment vs.
parents that are inwards from us - this usable to fwd packet - but could
not become preferred without leaving first.

The other is whether we could agree to a limited greediness to get
siblings. We'd actually use an initial rank that could be slightly
bigger than based on preferred parent to get at least one alternate.
There are pros and cons.

Ideas?

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Thomas Watteyne
>Sent: mardi 22 septembre 2009 22:14
>To: IETF ROLL
>Subject: [Roll] parent ordering
>
>Dear ROLLers,
>
>http://wsn.eecs.berkeley.edu/connectivity/network_gradient.php?dataset=
soda&sink=141&run=1&frequency_diversity
>=channel&channel=11
><http://wsn.eecs.berkeley.edu/connectivity/network_gradient.php?dataset
=soda&sink=141&run=1&frequency_diversit
>y=channel&channel=11>.
>"urban" network, running single DAG network with hop count as a
gradient
>_______________________________________________
>Roll mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/roll

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 23 Sep 2009 12:15:39 -0400

Pascal,

   Date: Wed, 23 Sep 2009 15:42:21 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

We discussed these questions in early July without coming to
any resolution that I can find.  I think that the only
concrete result was determining that 'sibling' was not the
technically correct term and that the RPL draft would switch
to 'node of the same rank'.  How about using 'peer' in place
of 'sibling'?  Using an incorrect term tends to muddle the
discussion.

A node of rank R can divide its neighbors into four classes:

  parents         (rank + link cost <= R)
  subparents      (rank < R, rank + link cost > R)
  peers/siblings  (rank = R)
  ignored         (rank > R)

'Parents' are neighbors that can be unilaterally used as a
new preferred parent and potentially decrease R.
'Subparents' are neighbors that can safely be routed through
without creating a potential loop.

We do not currently have any loop-free way of routing
through siblings.  If we had such, it might make sense to
quantize ranks into buckets in order to increase the number
of siblings.  Link quality and other measurments are
unlikely to be all that accurate in practice, so a minor
difference in rank is unlikely to represent a significant
practical difference.

Absent an effective way of routing through siblings, we
are better off having as of them as possible.  Minor
differences in rank can be considered as tie-breakers to
increase the number of known loop-free next hops.

Perhaps we should first come up with a practical way of
making use of peers/siblings and then work out how many we
would like there to be.
                              -Richard Kelsey

---

From: Michael Richardson <[email-masked]>
Date: Wed, 23 Sep 2009 13:14:58 -0400

>>>>> "Richard" == Richard Kelsey <[email-masked]> writes:
    Richard> We discussed these questions in early July without coming
    Richard> to any resolution that I can find.  I think that the only
    Richard> concrete result was determining that 'sibling' was not the
    Richard> technically correct term and that the RPL draft would
    Richard> switch to 'node of the same rank'.  How about using 'peer'
    Richard> in place of 'sibling'?  Using an incorrect term tends to
    Richard> muddle the discussion.

  I agree that another term is necessary.
  I think that peer is wrong, as it will be confusing when talking about
RPL in the context of other other routing protocols ("BGP peering",
link-layer things)

  How about "cousin".

-- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
] panic("Just another Debian GNU/Linux using, kernel hacking, security guy"); [

---

From: Thomas Watteyne <[email-masked]>
Date: Wed, 23 Sep 2009 17:07:18 -0700

Dear Richard, Pascal, WG,

Thanks a lot for your feedback. I think it is profitable for the WG and 
RPL to discuss the important concepts or DAG 
construction/maintenance/forwarding. From the ML, I feel like we all 
have slightly different ideas in mind. For the sake of discussion, I 
have compiled the few slides at 
http://www.eecs.berkeley.edu/~watteyne/rpl_example_topology.ppt 
<http://www.eecs.berkeley.edu/%7Ewatteyne/rpl_example_topology.ppt>, 
which show an example of DAG constructions/maintenance/forwarding we 
have been implementing it.

Could you mentally run RPL -02 on the connectivity graph presented in 
slide 2, and write down the differences? I don't think it is a good idea 
to throw is more ideas at this point, but rather to simplify the draft 
at hand.

Thomas

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 24 Sep 2009 13:54:05 +0200

Hi Richard and all:

One that is critical is the one that the goal calls preferred parent.
That is the reference for the rank computation. 

What about "reference parent" then? Or "reference attachment" router?

Then there's the concept of feasible successors. This is about
forwarding, not forming DAGs. From a DV perspective, siblings are not
but from this DAG, they are lesser but still acceptable successors. Do
we wish to use the term feasible successor? IF so, what do we mean?

>  subparents      (rank < R, rank + link cost > R)

I like parent for all of them; we need a name for that. The there would
be the distinction between feasible and unfeasible parents. Or
selectable and unselectable parents. Augmenting the rank to have 2
selectable parents vs one parent and something else would already be too
greedy, right?

>  peers/siblings  (rank = R)

Obviously, sibling is an interesting one. So we have peer, cousin,
same-rank. We could also use isometric or equidistant.
Or we could invent equi-or-iso ranked, and then we could use underranked
== inwards and overranked == outwards.

>  ignored         (rank > R) anything like over... to mean out of
scope, below the event horizon, something like that?

cheers

Pascal
>From: Richard Kelsey [mailto:[email-masked]]
>Sent: mercredi 23 septembre 2009 18:16
>To: Pascal Thubert (pthubert)
>Cc: [email-masked]; [email-masked]
>Subject: Re: [Roll] parent ordering
>
>Pascal,
>

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 24 Sep 2009 09:52:03 -0400

From: Michael Richardson <[email-masked]>
   Date: Wed, 23 Sep 2009 13:14:58 -0400

Fair enough.  

     How about "cousin".

I think that is the best so far.  I'll vote for it.

                                    -Richard Kelsey
----------------
This message and the information it contains are the proprietary
and confidential property of Ember Corporation and may be privileged.
If you are not the intended recipient, please do not read, copy,
disclose or distribute its contents to any party, and notify the
sender immediately.

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 24 Sep 2009 10:47:48 -0400

Pascal,

   Date: Thu, 24 Sep 2009 13:54:05 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>
   Cc: <[email-masked]>, <[email-masked]>

The choice of rank is critical, but I don't see why the
choice of preferred parent is.  As an example, if a node has
two parents of the same rank, does it matter which one is
the preferred parent?

Rather than picking a preferred parent, a node could
equivalently pick a set of parents and then choose any rank
that was greater than the maximum of the parents' ranks.
The node is free to add and remove parents from the set and
to change its own rank, so long as its rank is higher than
any of its parents and its own rank doesn't increase (unless
the DAG sequence number changes at the same time).

My understanding is that typically a OCP would require that
there be at least one parent such that the node's rank is
that parent's rank plus some the cost for the link to the
parent, but I don't think that RPL needs to require this.

                                -Richard Kelsey