Subject: [Roll] loops due to membership in multiple DAGs

From: Michael Richardson <[email-masked]>
Date: Fri, 02 Oct 2009 16:50:05 -0400

On the jabber during Wednesday's meeting (I was listening on the voice
bridge), Tim Winter asked something, and a light went on in my head.

(Probably, my observation is not news to many, but I suspect that it may
be a source of some mis-understanding)

I heard many people on the list suggest that having multiple DAGs could
cause loops.  Tim's comments made me understand how this could happen,
so let me start by presenting a diagram. (I copied it from someone
else's email) [Outlook people, use a fixed font]

   DAG-A (OCP=1)     DAG-B (OCP=2)
  
       X                   
       |	           
       A	       A   
      / \	      / 
      B-C	      B
     / \	       \   
     D E	       E   
     \ /	       /   
      F		      F    
                      |
                      Y
   (arrows        (arrows 
    point up)      all point down)

Let's assume that DAG-A has X as the root, and provides general service,
while DAG-B has Y as the root, and provides "mains-power only,
low-latency" service.

Node D has a packet to send. It didn't join the DAG-B because it didn't
need that service.  It sends a packet out, and it goes along the link to
B.  B sees the packet, is sure that it knows a better way along DAG-B,
and sends it to E.  E sends to F, and F does what?
  
F is part of DAG-A and DAG-B. If it sends with DAG-A, it goes back to D
(and there is a loop).  If it sends with DAG-B, then it's okay, but, we
have the same situation on A as well.

(My example is probably not designed right to explain things well
enough, perhaps someone can improve the example)

** My assumption up to now was that if you want to use DAG-A, that D would
** have put something into the IPv6 flow label, to indicate things, but I
** don't see anything in any document that says this.

(Does not have to be flow label. It could also be done with a per-hop
routing options: a source route, or could be MPLS stack, or could be
ethernet VLAN tags even...)

- -- 
]       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[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 5 Oct 2009 07:34:19 +0200

Hi Richard:

I think we're on the same line. If you look up the 'MTR' in this list
you might find additional discussion on this.
My understanding is that the group decided to go to multiple instances
operated as ship in the night.

What the RPL spec describes is what happens within one instance and
should be enough for a simple operation. An extension spec will describe
the multiple instances - that should not be too thick.

RPL will be written so as to enable a node that implements only one
instance to cooperate with nodes implementing multiple instances. We'll
have to describe how a packet is marked to follow that instance so as to
be compatible with multiple instances. 

DAGs within one instance are mutually exclusive, IOW A node can only
belong to one DAG for one instance.
DAGs from different instances are not exclusive and nodes can
participate to multiple instance.

Whether a packet can leave an instance to join another one will be a
policy decision. The policy must be loopless, for instance by making a
strict hierarchy of instances. Multiple Instances will probably require
quite a bit of administration, to match the flows and instance ID, and
distribute the policies.

More in "My notes from the meeting"

Cheers,

Pascal
>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Michael Richardson
>Sent: vendredi 2 octobre 2009 22:50
>To: roll WG
>Subject: [Roll] loops due to membership in multiple DAGs
>
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>
>   Kyoto Plus: watch the video
<http://www.youtube.com/watch?v=kzx1ycLXQSE>
>	               then sign the petition.
>
>
>
>
>
>
>
>
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: GnuPG v1.4.9 (GNU/Linux)
>Comment: Finger me for keys
>
>iQEVAwUBSsZneICLcPvd0N1lAQKTwwf9HZpFyNDRQoie1ZwC2FKtAvbeFz+QYAf4
>mtsGDlpCRxBAX8+ZGe5xUo6aNfay3FsTW76tjKapiPuKNQOYaNKd4hL6r12JkEqE
>re4vlUo7wf6t0W4VWXTHA17TegtxgMJCxqWxZQupiylzthcbNAy+jcTBHZKqJS8x
>YFy6gjBRZNXIebMMjZ/RNOD3GIAub2rNj6Z/uZgj6Km9sHCRUFuorL8wRtwJEEUD
>Mrnav5UTnonqDY9fYi+OJb8sV4gsd1TUWhNLv6kvGXk0J0cRjOecxSmYqBGW3Qf5
>2WXE/aKjkfhNIwGn3GOQxgQ3ycUN5bxq4e+Ek8kOAMZDYET/jm70TQ==
>=b2yD
>-----END PGP SIGNATURE-----
>_______________________________________________
>Roll mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/roll