Re: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q2..4

["Pascal Thubert (pthubert)" <[e-mail]>]

Hi Alex:

The links to parents form a DAG. If you include the sibling links it is no more a DAG.

Yet the resulting graph has some properties since there is no orientation that leads deeper; so it is not a general network. The difference between what we are doing and more classical routing is that we REALLY want multipath. So we are ready to forward not only along a classical DAG but also via siblings. 

The decision to pass a given packet to a given sibling is taken on a per packet basis when:
- the DAG does not help, none of the parents is usable at this time (e.g. retries failed)
- per packet loop avoidance allows that sibling for that packet

So the whole question is how do we perform per packet loop avoidance. In a very rich world we could actual use a source route header that traces all the hops along a sibling path and try all possibilities. I guess we cannot afford that. We could also build a DAG between siblings but again that would reduce our opportunities. With the current draft, we resolve the most probable loops and let TTL finish the job.

Basically if:
- nodes prefer parents over siblings, sibling path should be real short, and mostly 1 hop.
- nodes do not give a packet back to a sibling, or there's a tie break there, 1 hop loops would be avoided
- TTL is decremented aggressively along sibling path (Like minus N instead of minus 1), loops should not cost too much

The last option is not in the draft yet. It is on the table for discussion. It is a way to adapt the up*down* to IPv6 that has a single counter, hop limit. So we would allow an outward packet to make up to Hop Limit hops along the DAG, but only up to Hop Limit/N hops along siblings, and disallow going outward.

Makes sense?

Pascal

>-----Original Message-----
>From: Alexandru Petrescu [mailto:[e-mail]]
>Sent: mercredi 1 juillet 2009 11:08
>To: Pascal Thubert (pthubert)
>Cc: Goindi, Manhar; JP Vasseur (jvasseur); ROLL WG
>Subject: Re: [Roll] Fwd: I-D Action:draft-dt-roll-rpl-00.txt Q2..4
>
>Pascal, as I wrote in private, I doubt the necessity of using the term
>DAG and the associated DAG theory.  Picturing a DAG without arrows makes
>doubtful sense (figure 1).  A link between siblings would use bidir
>arrows, which would make for a 'loop', which we would try to avoid.
>
>Besides, what would an arrow between two nodes mean actually: is it that
>a node can send a packet to another node but not the other way around?
>Makes little sense to have all edges so unidirectional.
>
>Pascal Thubert (pthubert) a écrit :
>[...]
>> Q: Can siblings hear each other as it is not evident from Figure 2:
>> Example DAG?
>>
>> R: Figure 1 represents connectivity and you can see siblings hearing
>>  each other. Figure 2 represents the DAG so it does not include the
>> sibling links.
>
>It should be clear whether or not the siblings can be linked together by
>links and direct routes or not.  At some point  in the draft this is
>explicitely forbidden (it says traffic from node a to node b deep in the
>network must pass through the DAG root) - this is not good.
>
>> Sibling links are bidirectional at the graph level though
>> unidirectional for a given packet.
>
>I don't understand.  Do you mean that all links in the network (the DAG
>is the network) are _uni_directional?
>
>> We're missing the term to indicate the DAG+sibling_links.
>
>We should call it a network.  A graph of paths hopefully loop-free, not
>necessarily guaranteed.  But not a DAG.
>
>> Gradient is fine when you talk about pointing to the preferred
>> parent, but this is also a term that was overloaded in the past. What
>>  else?
>
>A network.  A net.   A set of paths.  A topology and the associated
>paths.  A conceptual picture stemming from the set of routes present in
>each node's routing table.
>
>I don't understand the word gradient in this context, throughout the
>document.  Is it a derivative of something?  A differential of something?
>
>Alex
>