Subject: [Roll] Fwd: Re: DAO fan out

From: Thomas Watteyne <[email-masked]>
Date: Wed, 28 Apr 2010 19:02:04 -0700

Roger,

Having a single byte for fan-out control and prioritization of 
downstream paths is elegant. It reminds me of the (academic) GRAdient 
Broadcast protocol. I have a couple of questions, though.

1) Is this a technique you (or others on the list) have experience with? 
If it's a proven technique, I'm glad to learn about it, and the WG will 
have more confidence adopting it.

2) I have some questions related to path convergence, which relates to 
the following paragraph in your text:

"An intermediate node may receive DAO messages from multiple children nodes
that advertise reachability to a given Destination Address. Where the total
number of set Path Control bits is greater than the number of DAO 
Parents the
bitmaps for the DAO messages will be merged. This merging of set bits will
allow for subsequent fan out at subsequent ancestor nodes."

This is, if I receive DAOs with [00000110] and [00000001] from two of my 
children, I have [00000111] to play with, which I can redistribute (or 
re-"fan out" if you want) across my DAO Parents. Does that mean that, 
every time I receive a DAO, I buffer it for some time in case I can 
merge it with a later one? If yes, how do I choose the duration to wait? 
If I decide to retransmit DAO's ASAP, and never merge them, what are the 
implications? As you may understand, I'm not a very big fan of the idea 
of "buffering for some time"...

I have taken a few minutes to verify that during fan-out, you should 
control the parent selection 
(http://www.eecs.berkeley.edu/~watteyne/disjointness.pdf). It tells you 
that, if two DAOs copies are sent towards the LBR, and each node 
en-route can select its DAO parent randomly, the two obtained routes 
will not be disjoint. That is, if one path fails, changes are the second 
will also as they share many links.

3) Similar to Fig.5, consider fan-out and convergence causes the LBR to 
receive two routes [00000001] and [00000110]. Which one will is prefer? 
Sure, [00000001] has traveled through all the best DAO parents, but 
wouldn't [00000110] offer me path diversity?

Similarly, what happens if the LBR has only one link to the rest of the 
network? If I read you text correctly, it will receive one packet with 
[111111111]. If I am missing something, please do tell me.

Thomas

On 4/27/2010 2:11 PM, Roger Alexander wrote:
> Hi Pascal,
>
> Please find attached an expanded note on the DAO fan out control and path
> prioritization mechanism.
>
> Roger
>
>    
>> -----Original Message-----
>> From: Pascal Thubert (pthubert) [mailto:[email-masked]]
>> Sent: Monday, April 19, 2010 11:35 AM
>> To: Roger Alexander; Navneet Agarwal (navagar); JP Vasseur;
>> [email-masked]
>> Cc: ROLL WG
>> Subject: RE: [Roll] DAO fan out
>>
>> Hi Roger:
>>
>> At high level I'm very positive on the mechanism .
>>
>> What I'd wish to see from the list is more people:
>> - agreeing that the fan out MUST be solved
>>      
> For large scale networks it is important to have some mechanism to bound
> downward paths once nodes can maintain multiple DAO parents. It will be up
> to the WG of course but after having introduced multiple DAO parents,
> leaving paths unconstrained introduces a potentially uncontrolled element of
> the protocol that can affect scalability; as networks become larger the
> potential vulnerability increases. What is being recommended is a 1-byte
> information element per DAO Destination Address. While incurring some
> additional overhead path control can be disabled (bitmap set to all zeros)
> for networks in which only a single DAO parent per node is maintained or
> that not wish to implement constraints on path fan out or to differentiate
> preferred downward paths.
>
>    
>> - that this is a simple and efficient solution
>>      
> Yes it would be good to get feedback from others on any concerns they may
> have.
>
>    
>> - that the solution can be incorporated in 08
>>
>> Maybe what would help from you Roger is:
>> - a visual example on the mechanism as work (if you have a pdf
>> illustrating it?)
>>      
> Note plus a few examples attached (pdf and MS Word).
>
>    
>> - some more explanation on the source route case (how the root can play
>> the same game recursively and obtain a good result as well)
>>      
> Based on the current -07 source route specification, non-storing nodes will
> follow the same operation as storing nodes in using the Path Control byte to
> determine the number and selection of DAO parents through which the reverse
> route stack is built.
>
> If the source route specification is changed to the more recent proposal
> from Richard, the Path Control byte can still apply to the advertised DAO
> Destination Address and will be associated with each of the selected DAO
> Parents communicated to the root. As in the case of storing nodes, each DAO
> Destination Address will have a different Path Control byte for each
> selected DAO Parent. For the source route case the root will be able to use
> the Path Control preference associated with each selected DAO Parent to
> recursively determine the preferred downward path to a given target address.
> That is, at the root, the preferred downward path to a given target address
> begins with the target's preferred DAO parent as given by the Path Control
> byte. From that preferred DAO Parent the link to the next preferred DAO
> ancestor is added until the complete preferred path is derived. The root
> will also be capable of deriving all the potential path combinations to a
> target node.
>
> As I currently understand the new proposal it is not clear that non storing
> nodes have any ability to control path fan out (and the consequently
> increased reverse route processing at the root) when nodes maintain multiple
> DAO Parents.
>
>    
>> Could you please so that for us?
>>
>> Thanks a bunch,
>>
>> Pascal
>>
>>
>>      
>>> -----Original Message-----
>>> From: Roger Alexander [mailto:[email-masked]]
>>> Sent: Friday, April 16, 2010 11:32 PM
>>> To: Pascal Thubert (pthubert); Navneet Agarwal (navagar); 'JP
>>>        
>> Vasseur';
>>      
>>> [email-masked]
>>> Cc: 'ROLL WG'
>>> Subject: RE: [Roll] DAO fan out (was:] IPSO Interop event - Feed-back
>>> welcome)
>>>
>>> Below is a quick summary aligned to Tim's concept of how the Path
>>>        
>> Control
>>      
>>> bitmap associated with the DAO destination address can be used to
>>>        
>> limit fan
>>      
>>> out and to identify the preferred path when nodes maintain multiple
>>>        
>> DAO
>>      
>>> Parents.
>>>
>>> Further details and examples can be provided as part of an larger
>>> application domain note.
>>>
>>> Roger
>>>
>>>        
>>>> -----Original Message-----
>>>> From: Pascal Thubert (pthubert) [mailto:[email-masked]]
>>>> Sent: Tuesday, April 13, 2010 3:47 AM
>>>> To: Roger Alexander; Navneet Agarwal (navagar); JP Vasseur;
>>>> [email-masked]
>>>> Cc: ROLL WG
>>>> Subject: DAO fan out (was:] IPSO Interop event - Feed-back welcome)
>>>>
>>>>
>>>>
>>>> Pascal
>>>>
>>>>          
>>>>> One consequence of maintaining multiple DAO parents is the
>>>>>            
>> potential
>>      
>>>> fan
>>>>          
>>>>> out of routing paths. With path fan out a node may have multiple
>>>>>            
>>>> downward
>>>>          
>>>>> next hop addresses for a given target destination address.
>>>>>            
>> Without
>>      
>>>> some
>>>>          
>>>>> path preference indication there is no information available if a
>>>>>            
>>>> storing node
>>>>          
>>>>> (including the root) wishes to limit the number of downward next
>>>>>            
>> hops
>>      
>>>>> maintained for a given address. It is thus desirable to have some
>>>>>            
>>>> means of
>>>>          
>>>>> path control to limit fan out as well as a preference indication
>>>>>            
>> that
>>      
>>>> can work in
>>>>          
>>>>> conjunction with the hop-by-hop DAO exchanges.
>>>>>
>>>>> See the Figure below for an example in which nodes maintain two
>>>>>            
>> DAO
>>      
>>>>> Parents each, where in the worst case the fan out that occurs
>>>>>            
>> after
>>      
>>>> three
>>>>          
>>>>> hops results in eight next hop downward paths from the DODAG root
>>>>>            
>>>> (LBR)
>>>>          
>>>>> to a target node (41). Even with the hop-by-hop DAO mechanism it
>>>>>            
>>>> would
>>>> be
>>>>          
>>>>> desirable to be able to limit fan out as well as to identify path
>>>>>            
>>>> preference and
>>>>          
>>>>> diversity at the root or other intermediate storing node.
>>>>>
>>>>>                      (------------LBR------------)
>>>>>                      /    /   / |     | \    \   \
>>>>>                     /    /   /  |     |  \    \   \
>>>>>                    /    /   /   |     |   \    \   \
>>>>>                   /    /   /    |     |    \    \   \
>>>>>                (11) (12) (13) (14)   (15) (16) (17) (18)
>>>>>                   \   |    |    /     \    |    |   /
>>>>>                    \  |    |   /       \   |    |  /
>>>>>                     \ |    |  /         \  |    | /
>>>>>                    (21)   (22)           (23)  (24)
>>>>>                        \    |            |    /
>>>>>                         \   |            |   /
>>>>>                          \  |            |  /
>>>>>                           (31)          (32)
>>>>>                               \        /
>>>>>                                \      /
>>>>>                                 \    /
>>>>>                                  (41)
>>>>>
>>>>>            
>>>> [Pascal] Your schema illustrates clearly that even if we fan out a
>>>>          
>> lot,
>>      
>>>> it does not mean that a router on the way down will have more
>>>>          
>> feasible
>>      
>>>> successors.
>>>>
>>>> That's one thing that's important to remember, the properties of
>>>>          
>> the
>>      
>>>> DAG
>>>> are not symmetrical, so even if we build it to get multiple
>>>>          
>> feasible
>>      
>>>> successors on the way up, that does not mean that on the reverse
>>>>          
>> DAG
>> to
>>      
>>>> a target there are multiple successors at each hop towards that
>>>>          
>> target.
>>      
>>>> In other words, the ROI of fanning out is not guaranteed if we do
>>>>          
>> it
>>      
>>>> blindly.
>>>>
>>>>          
>>>>> A simple path control bitmap associated with the advertised
>>>>>            
>>>> Destination
>>>>          
>>>>> Address can be included within the DAO to address the issue of
>>>>>            
>> path
>>      
>>>>> preference as well as control of fan out. For a network of
>>>>>            
>>>> 'non-storing'
>>>>          
>>>>> nodes the preference indication would be processed only at the
>>>>>            
>> root.
>>      
>>>> [Pascal] so far so good, but that will give you a blind mechanism.
>>>>
>>>>          
>>>>> With the path control byte associated with each DAO destination
>>>>>            
>>>> address, a
>>>>          
>>>>> node will be able to specify preference among DAO parent paths
>>>>>            
>> and
>>      
>>>> can
>>>>          
>>>>> convey limits on the number of downward paths. This is an
>>>>>            
>> opportunity
>>      
>>>> for
>>>>          
>>>>> nodes to further influence the downward paths that are
>>>>>            
>> established
>>      
>>>> and
>>>>          
>>>>> maintained. Consistent with the DV-based RPL operation this DAO
>>>>>            
>> path
>>      
>>>>> control mechanism must operate hop-by-hop avoiding any
>>>>>            
>> requirement
>>      
>>>> for
>>>>          
>>>>> end-to-end path coordination. To avoid overloading this email
>>>>>            
>> thread
>>      
>>>> I
>>>> will
>>>>          
>>>>> initiate a separate discussion on how a path control element may
>>>>>            
>> be
>>      
>>>> included
>>>>          
>>>>> within the DAO.
>>>>>
>>>>>            
>>>> [Pascal] Too late, I just did :)
>>>>
>>>> And if I remember, Tim's idea was to control the stretch of the
>>>>          
>> fanout,
>>      
>>>> by decrementing a counter as the path loses preference point.
>>>> At the moment, we have a parent preference 0-lowest to 3 highest.
>>>>          
>> So
>> it
>>      
>>>> is easy to decrement a counter by (3-pref) and not fan out when the
>>>> counter reaches 0.
>>>> Tim, could you elaborate on this?
>>>>          
>>> A Path Control bit map will achieve an equivalent control mechanism
>>> whereby
>>> at each node the number of bits that are set will determine the
>>>        
>> extent
>> to
>>      
>>> which the associated DAO Destination Address can be advertised to
>>>        
>> multiple
>>      
>>> DAO Parents. If a DAO message destination address Path Control bitmap
>>>        
>> has
>>      
>>> 4
>>> set bits, that address can be send along a maximum of 4 paths. For
>>>        
>> example,
>>      
>>> at the originating node the DAO can be sent to two DAO Parents where
>>>        
>> the
>>      
>>> Path Control bit map in the message sent to each DAO Parent will have
>>>        
>> two
>>      
>>> set bits. If each parent then advertises to two DAO Parents a single
>>>        
>> bit is
>>      
>>> set for each DAO message. Eventually with a single bit set in the
>>>        
>> Path
>>      
>>> Control bit map, the DAO message can be advertised only to a single
>>>        
>> DAO
>>      
>>> Parent. This mechanism achieves the effect of limiting the stretch of
>>>        
>> the
>>      
>>> path fan out. Where multiple DAO messages are received at a common
>>> ancestor
>>> the number of set bits in the respective Path Control fields are
>>>        
>> recombined
>>      
>>> allowing for renewed advertising of the DAO message destination
>>>        
>> address to
>>      
>>> multiple DAO Parents along the path.
>>>
>>> As the set Path Control bits are split and recombined as the DAO
>>>        
>> messages
>>      
>>> are transferred to the root, their bit positions are maintained. This
>>>        
>> allows
>>      
>>> bit positions to be ordered from low to high in terms of path
>>>        
>> preference.
>>      
>>> Therefore when a DAO message is received in which the Path Control
>>>        
>> bitmap
>>      
>>> has the highest preference bit set, that DAO message destination
>>>        
>> address is
>>      
>>> always advertised to the preferred DAO Parent. Similarly, when a
>>>        
>> message is
>>      
>>> received with multiple Path Control bits set, the DAO messages can be
>>> distributed to DAO Parents according to parent preference. This will
>>>        
>> ensure
>>      
>>> that at any common ancestor, including the root, a node is always
>>>        
>> able
>> to
>>      
>>> distinguish the preferred downward path. The ability to determine the
>>> preferred downward path as well as to obtain an indication of path
>>>        
>> diversity
>>      
>>> will allow the Path Control field to be used when resource
>>>        
>> limitations
>> at a
>>      
>>> node require a truncation of the number of downward paths that the
>>>        
>> node
>>      
>>> maintain for a given destination address.
>>>
>>>        
>>>> Pascal
>>>>          
>> >
>>
>>
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 29 Apr 2010 14:37:47 +0300

Just a quick question to the group:

Would it make sense to add path diversity to the OF – or is it already
implicitly included?

Perhaps we should define bit-wise OR-ing operation for the A-Field (to
propagate the diversity values along the path)? Though it would be a shame
to cross the 2 bits allocated for this field.

Regards,

Yoav

*From:* [email-masked] [mailto:[email-masked]] *On
Behalf Of *Thomas
Watteyne
*Sent:* Thursday, April 29, 2010 5:02 AM
*To:* [email-masked]
*Subject:* [Roll] Fwd: Re: DAO fan out

Roger,

Having a single byte for fan-out control and prioritization of downstream
paths is elegant. It reminds me of the (academic) GRAdient Broadcast
protocol. I have a couple of questions, though.

1) Is this a technique you (or others on the list) have experience with? If
it's a proven technique, I'm glad to learn about it, and the WG will have
more confidence adopting it.

2) I have some questions related to path convergence, which relates to the
following paragraph in your text:

number of set Path Control bits is greater than the number of DAO Parents

This is, if I receive DAOs with [00000110] and [00000001] from two of my
children, I have [00000111] to play with, which I can redistribute (or
re-"fan out" if you want) across my DAO Parents. Does that mean that, every
time I receive a DAO, I buffer it for some time in case I can merge it with
a later one? If yes, how do I choose the duration to wait? If I decide to
retransmit DAO's ASAP, and never merge them, what are the implications? As
you may understand, I'm not a very big fan of the idea of "buffering for
some time"...

I have taken a few minutes to verify that during fan-out, you should control
the parent selection (
http://www.eecs.berkeley.edu/~watteyne/disjointness.pdf). It tells you that,
if two DAOs copies are sent towards the LBR, and each node en-route can
select its DAO parent randomly, the two obtained routes will not be
disjoint. That is, if one path fails, changes are the second will also as
they share many links.

3) Similar to Fig.5, consider fan-out and convergence causes the LBR to
receive two routes [00000001] and [00000110]. Which one will is prefer?
Sure, [00000001] has traveled through all the best DAO parents, but wouldn't
[00000110] offer me path diversity?

Thomas

Hi Pascal,

Roger

-----Original Message-----

From: Pascal Thubert (pthubert) [mailto:[email-masked] <[email-masked]>]

[email-masked]

Cc: ROLL WG

Hi Roger:

have.

illustrating it?)

route stack is built.

target node.

DAO Parents.

Thanks a bunch,

Pascal

-----Original Message-----

From: Roger Alexander [mailto:[email-masked]
<[email-masked]>]

Vasseur';

[email-masked]

Cc: 'ROLL WG'

welcome)

Control

limit fan

DAO

Parents.

application domain note.

Roger

-----Original Message-----

From: Pascal Thubert (pthubert) [mailto:[email-masked] <[email-masked]>]

[email-masked]

Cc: ROLL WG

Pascal

 potential

 fan

downward

 Without

 some

storing node

 hops

means of

 that

 can work in

 DAO

 after

 three

(LBR)

would

be

preference and

                    /    /   / |     | \    \   \

                   /    /   /  |     |  \    \   \

                  /    /   /   |     |   \    \   \

                 /    /   /    |     |    \    \   \

                 \   |    |    /     \    |    |   /

                  \  |    |   /       \   |    |  /

                   \ |    |  /         \  |    | /

                  (21)   (22)           (23)  (24)

                      \    |            |    /

                       \   |            |   /

                        \  |            |  /

                         (31)          (32)

                             \        /

                              \      /

                               \    /

                                (41)

 lot,

 feasible

 successors.

 the

 DAG

 feasible

 DAG

to

 target.

 it

 blindly.

Destination

 path

'non-storing'

 root.

address, a

 and

 can

 opportunity

 for

 established

 and

 path

 requirement

 for

 thread

 I

will

 be

 included

within the DAO.

 fanout,

 So

it

counter reaches 0.

whereby

extent

to

multiple

has

4

example,

the

two

bit is

Path

DAO

the

ancestor

recombined

address to

messages

allows

preference.

bitmap

address is

message is

ensure

able

to

diversity

limitations

at a

node

Pascal

Roll mailing list

[email-masked]

---

From: "Roger Alexander" <[email-masked]>
Date: Thu, 29 Apr 2010 13:40:03 -0400

Hi Thomas,

Thanks for the feedback and the simulation results.

From: [email-masked] [mailto:[email-masked]] On Behalf Of
Thomas Watteyne
Sent: Wednesday, April 28, 2010 10:02 PM
To: [email-masked]
Subject: [Roll] Fwd: Re: DAO fan out

Roger,

[RA] No this is not a proven or deployed technique. The proposal is based on
a concern that arises from our deployed networks where single root nodes do
support a network of thousands of nodes. Once multiple DAO parents are
entertained for downward routing availability, routing scalability can be
affected if DAO exchanges are left  unbounded. Furthermore, there will need
to be a means of extracting the preferred downward path and selecting from
the many alternatives that can result.

[RA] The note was written from the perspective of a network with all storing
nodes. For storing nodes, DAO advertisements and made and updated based on
the validity period of the received Destination Address routing updates. It
that context the issue of buffering is well defined. There is however an
issue of dealing with the sequence of DAO advertisements that will be
received at different intervals that may require subsequent change in the
selected DAO Parent. To maintain the requirement that the preferred path can
always be determined, there may be periods during which fewer DAO Parents
are selected than may be otherwise available at a given intermediate node
(future consideration required).

[RA] For non storing nodes, based on my understanding of the currently
discussed proposal, the situation is simpler in that the originating owner
of the Destination Address establishes the preference and includes the
applicable Path Control setting with the different DAO Parents selected.
Each node selects its DAO Parents and indicates the preference of each. Each
node's information needs only to be available at the root which then
computes all downward paths. The onus for scalability in processing the
downward path routing is placed on the root node - with processing
requirements increasing with the number of DAO Parents. However, all the
information is available for global determination of preferred, as well as
secondary downward paths. 

I have taken a few minutes to verify that during fan-out, you should control
the parent selection
(http://www.eecs.berkeley.edu/~watteyne/disjointness.pdf). It tells you
that, if two DAOs copies are sent towards the LBR, and each node en-route
can select its DAO parent randomly, the two obtained routes will not be
disjoint. That is, if one path fails, changes are the second will also as
they share many links.

[RA] Thanks. This is an interesting result, caveats notwithstanding. I would
like to digest a bit further and get back to you. The benefit of multiple
DAO Parents is predicated on the downward diversity that it provides. The
cost of multiple DAO Parents and fan out is that it can negate some of RPL's
routing scalability benefits (for storing nodes). If as the results suggest
multiple DAO Parents does not provide a meaningful path availability gain
then its utility is somewhat diminished. 

[RA] Yes, diversity information may be derived from the path Control and can
be used as a selection criteria when making a choice of downward path. That
would be an implementation choice. 

[RA] If that were the case the LBR would indeed receive one packet with
[11111111].  However the collective path information would be available to
the single node that connects to the LBR. That node, and all other
intermediate (storing) nodes, use the available path control information to
support downward path selection. In the case of non-storing nodes the root
would calculate the downward paths that would diverge not from the root but
a node(s) further down the tree.

Thomas

Hi Pascal,

Roger

-----Original Message-----
From: Pascal Thubert (pthubert) [mailto:[email-masked]]
Sent: Monday, April 19, 2010 11:35 AM
To: Roger Alexander; Navneet Agarwal (navagar); JP Vasseur;
[email-masked]
Cc: ROLL WG
 
Hi Roger:

 

 

 
Thanks a bunch,
 
Pascal

-----Original Message-----
From: Roger Alexander [mailto:[email-masked]]
Sent: Friday, April 16, 2010 11:32 PM
To: Pascal Thubert (pthubert); Navneet Agarwal (navagar); 'JP

Vasseur';

[email-masked]
Cc: 'ROLL WG'

Control

limit fan

DAO

Parents.

Roger

-----Original Message-----
From: Pascal Thubert (pthubert) [mailto:[email-masked]]
Sent: Tuesday, April 13, 2010 3:47 AM
To: Roger Alexander; Navneet Agarwal (navagar); JP Vasseur;
[email-masked]
Cc: ROLL WG

Pascal

potential

fan

downward

Without

some

storing node

hops

means of

that

can work in

DAO

after

three

(LBR)

would
be

preference and

lot,

feasible

successors.

the

DAG

feasible

DAG
to

target.

it

blindly.

Destination

path

'non-storing'

root.

address, a

and

can

opportunity

for

established

and

path

requirement

for

thread

I
will

be

included

within the DAO.

fanout,

So
it

extent
to

multiple

has

4

example,

the

two

bit is

Path

DAO

the

recombined

address to

messages

allows

preference.

bitmap

address is

message is

ensure

able
to

diversity

limitations
at a

node

Pascal

---

From: Thomas Watteyne <[email-masked]>
Date: Thu, 29 Apr 2010 11:25:34 -0700

Hi Roger,
Thanks for the clear answers. I'm eager to see what people on the list 
think.
Thomas

On 4/29/2010 10:40 AM, Roger Alexander wrote:
> Behalf Of *Thomas Watteyne
> *Sent:* Wednesday, April 28, 2010 10:02 PM
> *To:* [email-masked]
> 1) Is this a technique you (or others on the list) have experience 
> with? If it's a proven technique, I'm glad to learn about it, and the 
> WG will have more confidence adopting it.
>
> [RA] No this is not a proven or deployed technique. The proposal is 
> based on a concern that arises from our deployed networks where single 
> root nodes do support a network of thousands of nodes. Once multiple 
> DAO parents are entertained for downward routing availability, routing 
> scalability can be affected if DAO exchanges are left  unbounded. 
> Furthermore, there will need to be a means of extracting the preferred 
> downward path and selecting from the many alternatives that can result.
>
>
>
> This is, if I receive DAOs with [00000110] and [00000001] from two of 
> my children, I have [00000111] to play with, which I can redistribute 
> (or re-"fan out" if you want) across my DAO Parents. Does that mean 
> that, every time I receive a DAO, I buffer it for some time in case I 
> can merge it with a later one? If yes, how do I choose the duration to 
> wait? If I decide to retransmit DAO's ASAP, and never merge them, what 
> are the implications? As you may understand, I'm not a very big fan of 
> the idea of "buffering for some time"...
>
> [RA] The note was written from the perspective of a network with all 
> storing nodes. For storing nodes, DAO advertisements and made and 
> updated based on the validity period of the received Destination 
> Address routing updates. It that context the issue of buffering is 
> well defined. There is however an issue of dealing with the sequence 
> of DAO advertisements that will be received at different intervals 
> that may require subsequent change in the selected DAO Parent. To 
> maintain the requirement that the preferred path can always be 
> determined, there may be periods during which fewer DAO Parents are 
> selected than may be otherwise available at a given intermediate node 
> discussed proposal, the situation is simpler in that the originating 
> owner of the Destination Address establishes the preference and 
> includes the applicable Path Control setting with the different DAO 
> Parents selected. Each node selects its DAO Parents and indicates the 
> preference of each. Each node's information needs only to be available 
> at the root which then computes all downward paths. The onus for 
> scalability in processing the downward path routing is placed on the 
> root node -- with processing requirements increasing with the number 
> of DAO Parents. However, all the information is available for global 
> determination of preferred, as well as secondary downward paths.
>
>
>
> (http://www.eecs.berkeley.edu/~watteyne/disjointness.pdf 
> <http://www.eecs.berkeley.edu/%7Ewatteyne/disjointness.pdf>). It tells 
> you that, if two DAOs copies are sent towards the LBR, and each node 
> will not be disjoint. That is, if one path fails, changes are the 
> second will also as they share many links.
>
> [RA] Thanks. This is an interesting result, caveats notwithstanding. I 
> would like to digest a bit further and get back to you. The benefit of 
> multiple DAO Parents is predicated on the downward diversity that it 
> provides. The cost of multiple DAO Parents and fan out is that it can 
> negate some of RPL's routing scalability benefits (for storing nodes). 
> If as the results suggest multiple DAO Parents does not provide a 
> meaningful path availability gain then its utility is somewhat 
> diminished.
>
>
>
> 3) Similar to Fig.5, consider fan-out and convergence causes the LBR 
> to receive two routes [00000001] and [00000110]. Which one will is 
> prefer? Sure, [00000001] has traveled through all the best DAO 
> parents, but wouldn't [00000110] offer me path diversity?
>
> [RA] Yes, diversity information may be derived from the path Control 
> and can be used as a selection criteria when making a choice of 
> downward path. That would be an implementation choice.
>
>
>
> Similarly, what happens if the LBR has only one link to the rest of 
> the network? If I read you text correctly, it will receive one packet 
> with [111111111]. If I am missing something, please do tell me.
>
> [RA] If that were the case the LBR would indeed receive one packet 
> with [11111111].  However the collective path information would be 
> available to the single node that connects to the LBR. That node, and 
> all other intermediate (storing) nodes, use the available path control 
> information to support downward path selection. In the case of 
> non-storing nodes the root would calculate the downward paths that 
> would diverge not from the root but a node(s) further down the tree.
>
>
>
> Thomas
>
>     [email-masked]  <mailto:[email-masked]>
>
>     Cc: ROLL WG
>
>         [email-masked]  <mailto:[email-masked]>
>
>         Cc: 'ROLL WG'
>
>             [email-masked]  <mailto:[email-masked]>
>
>             Cc: ROLL WG
>
>     [email-masked]  <mailto:[email-masked]>
>

---

From: "Roger Alexander" <[email-masked]>
Date: Thu, 29 Apr 2010 18:16:26 -0400

Hi Thomas,

Still mulling the interesting results of your simulation and the potential
implications. A couple further thoughts, particularly as it relates to the
'disjointness' measure.

1.       While 'disjointness' as you have defined it does capture some
measure of the independence of paths, it may not be adequately reflecting
the increased path availability that results from multiple DAO Parents. That
is, it is possible for disjointedness to remain the same or even fall while
the end-to-end path availability goes up. See a simple example below. This
raises the question of whether it would be better to more directly capture
path availability in the simulated data.

2.       An artifact of the network model is that the node degree is the
same for all nodes including the root. This means that regardless of
fan-out, the paths to/from the root will converge based on node degree. More
importantly, paths from the target node all converge according to the number
of assumed DAO Parents. The way disjointness is calculated, each new fanout
path adds a common link count based on the node-DAO Parent link from which
the path emerged. This is not a problem in itself, but the node-parent links
and a common ancestor-root link get counted in the number of common links
for each link fan out occurring in between. This may be having some effect
on compressing the resulting disjointness measure.

A simple example to try to clarify these thoughts. Consider a downward path
between an LBR root node and a node A given by A-B-C-LBR. Disjointness is of
course 1 (3/3). Add a second completely independent path given by A-E-F-LBR.
Here the disjointness of the two paths is again 1 (6/6, all links remain
disjoint). However the path availability to node A has increased (all links
equally available, it has doubled). If a third path is added via a third DAO
Parent given by A-H-F-LBR. The disjointed measure has fallen to (7/9) even
though the availability of the connection from A to the LBR has increased.
If a fourth DAO parent is added to offer a path given by A-J-B-C-LBR, the
disjointed measure falls further to (7/13) even as the path availability
from the LBR root to node A has improved due to the additional diversity
along the path from B-A. What this seems to be implying is that even as
disjointness is capturing some measure of reduced path independence, it may
not be adequately capturing the improved path availability potential. Let me
know if I have accurately characterized the measure.

 What we will try to do as well in the coming weeks is to analyze some
sample field network data to see how additional DAO parents would affect
downward path availability.

Roger

From: [email-masked] [mailto:[email-masked]] On Behalf Of
Thomas Watteyne
Sent: Thursday, April 29, 2010 2:26 PM
To: [email-masked]
Subject: Re: [Roll] Fwd: Re: DAO fan out

Hi Roger,

Hi Thomas,

Roger,

<http://www.eecs.berkeley.edu/%7Ewatteyne/disjointness.pdf> ). It tells you

Thomas

Hi Pascal,

Roger

-----Original Message-----
From: Pascal Thubert (pthubert) [mailto:[email-masked]]
Sent: Monday, April 19, 2010 11:35 AM
To: Roger Alexander; Navneet Agarwal (navagar); JP Vasseur;
[email-masked]
Cc: ROLL WG
 
Hi Roger:

 

 

 
Thanks a bunch,
 
Pascal

-----Original Message-----
From: Roger Alexander [mailto:[email-masked]]
Sent: Friday, April 16, 2010 11:32 PM
To: Pascal Thubert (pthubert); Navneet Agarwal (navagar); 'JP

Vasseur';

[email-masked]
Cc: 'ROLL WG'

Control

limit fan

DAO

Parents.

Roger

-----Original Message-----
From: Pascal Thubert (pthubert) [mailto:[email-masked]]
Sent: Tuesday, April 13, 2010 3:47 AM
To: Roger Alexander; Navneet Agarwal (navagar); JP Vasseur;
[email-masked]
Cc: ROLL WG

Pascal

potential

fan

downward

Without

some

storing node

hops

means of

that

can work in

DAO

after

three

(LBR)

would
be

preference and

lot,

feasible

successors.

the

DAG

feasible

DAG
to

target.

it

blindly.

Destination

path

'non-storing'

root.

address, a

and

can

opportunity

for

established

and

path

requirement

for

thread

I
will

be

included

within the DAO.

fanout,

So
it

extent
to

multiple

has

4

example,

the

two

bit is

Path

DAO

the

recombined

address to

messages

allows

preference.

bitmap

address is

message is

ensure

able
to

diversity

limitations
at a

node

Pascal

---

From: "M. B. Anand" <[email-masked]>
Date: Fri, 30 Apr 2010 00:36:33 -0400

Roger,

> 1.       While ‘disjointness’ as you have defined it does capture some
> is, it is possible

There are both overall path concerns and local concerns here. The
availability of a lot of alternatives at a given node along the path says
nothing about the overall path since there may be no edge-disjoint paths and
everything may go through a single edge, so there are no independent paths
at all. On the other hand, you might argue that you do want to capture the
high availability of edges at a given node .

If you wish to get a measure of the overall situation over the whole
network, you might perhaps consider the formal notion of edge connectivity -
defined as the minimal number of edges that separates the graph, and
evaluate it for the whole graph with multiple parent situations and see if
it makes an overall difference. Would depend completely on the topology.

You could also do the same exercise on a per node basis, with a subgraph
consisting of all edges and included nodes in the LBR - x paths, where x is
each node, and evaluate the minimal number of edges that separates x from
LBR.

For example, in the first step you give in the example below, for LBR - A
paths, that number would 1. In the second step, it would be 2. In the third
step it would still be 2 (LBR - C and LBR - F still separates A from LBR.
Also, a useful graph theorem is that the minimal number of edges that
separates a vertex s from t is equal to the maximal number of edge-disjoint
s-t paths and clearly there are still only two edge-disjoint paths). In the
fourth step, it is still 2 - same as above.

This would be the situation for the overall A - LBR path.

If you wish to capture something about the fact that A has a lot of next hop
choices by step 4 in your example, regardless of the A - LBR path, then you
could repeat the above exercise for each A - z path where z is each node in
the A - LBR paths, and arrive at a range of values. For example, 1 edge
separates A from F in step 2, but 2 edges separate it from F in step 3,
although the addition of A - H - F didn't do anything to improve the A - LBR
path. Thus, if you added several A - Hi - F, with i going from 1 to 50, then
51 edges will separate A from F, thus capturing the high availability
between A and F, but again contributing nothing to the A - LBR path.

Regards,
Anand.

> know if I have accurately characterized the measure.

Regards,
Anand.

---

From: Roger Alexander <[email-masked]>
Date: Fri, 30 Apr 2010 18:33:13 -0400

Hi Anand,

Thanks.

Roger

On Apr 30, 2010, at 12:36 AM, "M. B. Anand" <[email-masked]>  
wrote:

> Roger,
> 1.       While ‘disjointness’ as you have defined it does capture  
> some measure of the independence of paths, it may not be adequately  
> reflecting the increased path availability that results from multipl 
> e DAO Parents. That is, it is possible
>
>
> availability of a lot of alternatives at a given node along the path  
> says nothing about the overall path since there may be no edge- 
> disjoint paths and everything may go through a single edge, so there  
> are no independent paths at all. On the other hand, you might argue  
> that you do want to capture the high availability of edges at a  
> given node .
>
> network, you might perhaps consider the formal notion of edge  
> connectivity - defined as the minimal number of edges that separates  
> the graph, and evaluate it for the whole graph with multiple parent  
> situations and see if it makes an overall difference. Would depend  
> completely on the topology.
>
> You could also do the same exercise on a per node basis, with a  
> subgraph consisting of all edges and included nodes in the LBR - x  
> paths, where x is each node, and evaluate the minimal number of  
> edges that separates x from LBR.
>
> For example, in the first step you give in the example below, for  
> LBR - A paths, that number would 1. In the second step, it would be  
> 2. In the third step it would still be 2 (LBR - C and LBR - F still  
> separates A from LBR. Also, a useful graph theorem is that the  
> minimal number of edges that separates a vertex s from t is equal to  
> the maximal number of edge-disjoint s-t paths and clearly there are  
> still only two edge-disjoint paths). In the fourth step, it is still  
> 2 - same as above.
>
> If you wish to capture something about the fact that A has a lot of  
> next hop choices by step 4 in your example, regardless of the A -  
> LBR path, then you could repeat the above exercise for each A - z  
> path where z is each node in the A - LBR paths, and arrive at a  
> range of values. For example, 1 edge separates A from F in step 2,  
> but 2 edges separate it from F in step 3, although the addition of A  
> - H - F didn't do anything to improve the A - LBR path. Thus, if you  
> added several A - Hi - F, with i going from 1 to 50, then 51 edges  
> will separate A from F, thus capturing the high availability between  
> A and F, but again contributing nothing to the A - LBR path.
>
> Regards,
> Anand.
>
>
> A simple example to try to clarify these thoughts. Consider a  
> downward path between an LBR root node and a node A given by A-B-C- 
> LBR. Disjointness is of course 1 (3/3). Add a second completely  
> independent path given by A-E-F-LBR. Here the disjointness of the  
> two paths is again 1 (6/6, all links remain disjoint). However the  
> path availability to node A has increased (all links equally  
> available, it has doubled). If a third path is added via a third DAO  
> Parent given by A-H-F-LBR. The disjointed measure has fallen to  
> (7/9) even though the availability of the connection from A to the  
> LBR has increased. If a fourth DAO parent is added to offer a path  
> given by A-J-B-C-LBR, the disjointed measure falls further to (7/13)  
> even as the path availability from the LBR root to node A has  
> improved due to the additional diversity along the path from B-A.  
> What this seems to be implying is that even as disjointness is  
> capturing some measure of reduced path independence, it may not be  
> adequately capturing the improved path availability potential. Let  
> me know if I have accurately characterized the measure.
>
>
>
>
> Regards,
> Anand.