Subject: [Roll] [RPL]About Nodes subscribing to multiple DAGs

From: [email-masked]
Date: Fri, 03 Jul 2009 18:33:39 +0200

Hi everyone,

RPL specifies that a node can subscribe to more than one DAG.

Is it the intention to allow nodes to forward packets received from one
DAG to another one?

If so, is there any mechanism that we could think of to prevent
cross-DAGS loops?

If a packet arrives at a node which knows that the root is no longer
reachable, forwarding accross DAGs might be useful...

Thanks for your comments,

Quentin Lampin

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Sat, 4 Jul 2009 15:04:32 +0200

Salut Quentin:

If DAGs expose different prefixes then the longest match rule applies
all the way to follow the graph that advertise that longest match
prefix. You can use that to implement a power utility gateway that would
get specific traffic but not default.

If DAGs expose a same prefix (default) then packets must be tagged
(colored) to indicate which one of the topologies they are supposed to
follow, otherwise loops will occur (your point I guess).

Finally, it is always possible to leave a topology to a strictly lower
one, if you have structured your set of topologies as a tree. Like a
default spanning topology would be the lowest (root) topology, and
constrained control topologies would be the highest (leaves).

Will you be in Stockholm?

Pascal

From: [email-masked] [mailto:[email-masked]] On Behalf Of
[email-masked]
Sent: vendredi 3 juillet 2009 18:34
To: [email-masked]
Subject: [Roll] [RPL]About Nodes subscribing to multiple DAGs

Hi everyone,

Quentin Lampin

---

From: [email-masked]
Date: Tue, 07 Jul 2009 15:41:39 +0200

Pascal Thubert (pthubert) wrote:

Salut
Quentin:

Salut Pascal,

If
DAGs expose different prefixes then the longest match rule
applies all the way to follow the graph that advertise that longest
match
prefix. You can use that to implement a power utility gateway that
would get
specific traffic but not default.

ok.

If
DAGs expose a same prefix (default) then packets must be
tagged (colored) to indicate which one of the topologies they are
supposed to
follow, otherwise loops will occur (your point I guess).

If I understand well, in the case of multiple DAGs advertising the same
prefix, packet originators have to specify which DAG the packets must
follow. I also understand that the intention is to tailor DAGs to
address specific constraints/metrics so that it makes little sense, in
general, to forward packets accross DAGs. But I can see cases where
this would be useful. For example, when a node in a frozen sub-DAG
receives a packet tagged with this DAGID. If  it's allowed, it could
decide, according to the advertised traffic class, to forward the
packet to another DAG such that the packet is not dropped. We could
think of a per prefix "default" (kind of emergency) DAG.

A simple way to ensure loops avoidance would be to forbid nodes to
forward packets tagged "default" outside of the default DAG.

Another (more generic and thus more powerful) way would be to add a Hop
by Hop option to the packet specifying visited DAGs and depths of
nodes  which made the cross DAGs forward moves. Ensuring that a node
cannot be re-forwarded to a node in a visited DAG at a depth higher
(deeper) or
equal to the depth corresponding to the visited DAG should be
sufficient to avoid most probable loops.

Moreover, the last option would allow us to handle complex packet
constraints such as { Tdeliver < Tref (weight w1), Nhop < Nref
(weigth w2)}. A node receiving such a packet could evaluate if the
major constraint (higher weight) is likely to be respected and, in this
case, forward the packet accross another DAG to address the other
constraints.

This would permit to build "multi-dimensional" QoS based forwarding
engines.

Finally,
it is always possible to leave a topology to a strictly
lower one, if you have structured your set of topologies as a tree.
Like a
default spanning topology would be the lowest (root) topology, and
constrained
control topologies would be the highest (leaves).

This is the start point of the last proposition ;)

Will
you be in Stockholm?

Unfortunately not, but Dominique Barthel will be there. You can discuss
about this with him.

Pascal

From:
[email-masked]
[mailto:[email-masked]] On Behalf Of [email-masked]

To: [email-masked]

Hi everyone,

DAG to
another one?

cross-DAGS
loops?

If a packet arrives at a node which knows that the root is no longer
reachable,
forwarding accross DAGs might be useful...

Quentin Lampin

Quentin

---

From: JP Vasseur <[email-masked]>
Date: Wed, 8 Jul 2009 16:24:47 +0200

Hi Quentin,

On Jul 7, 2009, at 3:41 PM, [email-masked] wrote:

>> If DAGs expose different prefixes then the longest match rule  
>> match prefix. You can use that to implement a power utility gateway  
>> that would get specific traffic but not default.
> ok.
>>
>>
>> (colored) to indicate which one of the topologies they are supposed  
>> to follow, otherwise loops will occur (your point I guess).
> If I understand well, in the case of multiple DAGs advertising the  
> same prefix, packet originators have to specify which DAG the  
> packets must follow.

Right, similarly to what is done with MTR.

> I also understand that the intention is to tailor DAGs to address  
> specific constraints/metrics so that it makes little sense, in  
> packet to another DAG such that the packet is not dropped.

Yes, which is also an existing notion consisting of using a "default"  
DAG as a fall back option. But then you must not "re-color" the packet  
to avoid loops.

> We could think of a per prefix "default" (kind of emergency) DAG.

Right.

> Another (more generic and thus more powerful) way would be to add a  
> Hop by Hop option to the packet specifying visited DAGs and depths  
> of nodes  which made the cross DAGs forward moves.

Route Record option would be extremely expensive in term of overhead  
though.

> Ensuring that a node cannot be re-forwarded to a node in a visited  
> DAG at a depth higher (deeper) or equal to the depth corresponding  
> to the visited DAG should be sufficient to avoid most probable loops.
> major constraint (higher weight) is likely to be respected and, in  
> this case, forward the packet accross another DAG to address the  
> other constraints.

This can actually be achieved with the current RPL proposal ... that  
said, this brings several additional issues and complexity ... We  
probably need to evaluate if that requires such a level of complexity  
in practice.

>>
>> Finally, it is always possible to leave a topology to a strictly  
>> Like a default spanning topology would be the lowest (root)  
>> topology, and constrained control topologies would be the highest  
>> (leaves).
> Unfortunately not, but Dominique Barthel will be there. You can  
> discuss about this with him.
>>
>> Pascal
>> From: [email-masked] [mailto:[email-masked]] On  
>> Behalf Of [email-masked]
>> Is it the intention to allow nodes to forward packets received from  
>> one DAG to another one?
>> If a packet arrives at a node which knows that the root is no  
>> longer reachable, forwarding accross DAGs might be useful...
>>
>>
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: [email-masked]
Date: Wed, 15 Jul 2009 12:06:06 +0200

Hi JP, Rollers,

JP Vasseur wrote:
>> same prefix, packet originators have to specify which DAG the packets 
>> must follow.
>
>> Hop by Hop option to the packet specifying visited DAGs and depths of 
>> nodes  which made the cross DAGs forward moves.
>
Well, the intention was not to memorize all traversed nodes but only
nodes which forward packets accross DAGs. We can assume that there will
be only a few of these nodes compared to the number of traversed nodes,
thus we can expect the overhead to be small(see the discussion below
the options format proposition).
By the way, there is no Route Record for IPv6. Thus, if we want to 
support forwarding accross multiple DAGS, we need to specify a new HbH 
option.

We could think of something similar to this:

      0               7              15              23               31
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |Type TBD (HR)  |  Opt Data Len |      Rsvd     |     Depth     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      +                                                               +
      |                             DAGID                             |
      +                                                               +
      |                                                               |
      +                                                               +
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      +                                                               +
      |                         Node address                          |
      +                                                               +
      |                                                               |
      +                                                               +
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Or if we follow the suggestion made in the discussion on Multiple roots 
in DAG and differentiate the DAGID from the DAG Root address and reduce 
the DAGID field size to a more reasonable one, say 8bits:

      0               7              15              23               31
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |Type TBD (HR)  |  Opt Data Len |     DAGID     |     Depth     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                                                               |
      +                                                               +
      |                         Node address                          |
      +                                                               +
      |                                                               |
      +                                                               +
      |                                                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Some points would still need to be investigated if we want to use such 
an option.
First, can we add an HbH header en-route? It would mean that 
intermediate nodes can change the packet payload size. Similarly, can we 
add options to the HbH Header en-route (thus changing the HbH Header 
Extension Length).
This may break the IPv6 full compliance but would allow powerful, 
scalable and extensible usages of ROLL.

The fallback option would be to add a fix-sized HbH to every packet that
may be routed over DAGs, leading to huge overhead (I guess this is what 
you were referring to)...

>> DAG at a depth higher (deeper) or equal to the depth corresponding to 
>> the visited DAG should be sufficient to avoid most probable loops.
The way we can achieve this with the current RPL proposal is not obvious
to us. The obvious solution to inter-DAG loops is to not forward packets
across DAGs, as suggested by Pascal. We are interested in studying
mechanisms to forward across DAGS while still avoiding loops.
We understand this may be a long shot compared to other more immediates
issues at hand. However, at your leisure, would you care elaborating how
the current proposal can do this?

Quentin & Dominique

---

From: Bernard Tourancheau <[email-masked]>
Date: Wed, 15 Jul 2009 13:49:22 +0200

>>> This would permit to build "multi-dimensional" QoS based  
>>> forwarding engines.
>>
>> This can actually be achieved with the current RPL proposal ...  
>> that said, this brings several additional issues and complexity ...  
>> We probably need to evaluate if that requires such a level of  
>> complexity in practice.
>>

Hi,
Assuming there is an ordering of DAGs' numbers, you can avoid loops if  
a packet goes from DAG to DAG following a strict progression in that  
ordering (direction < or >).
This can be implemented by a bit giving the direction and the DAG  
number represented on a fixed number of bits (which gives the max  
number of DAGs). Hence,  the operation of passing a packet to another  
DAG without any loop  is possible if and only if :

new DAG #  > [respectively <] (current DAG # + my DAG # ) % max number  
of DAGs

This implies to keep "direction bit", "my DAG #" and "current DAG #",  
no recording of the nodes traversed.
In the best case you got max number of DAGs possibilities of changing  
DAG, in the worst case, you choose to go from my DAG # to my DAG # -  
1, leading to only one DAG hop. As this operation seems to be rare a  
good ordering of DAGs should ensure several possibilities for a very  
small number of bits.

My2cents,
Bernard.