Subject: [Roll] DAO fan out (was:] IPSO Interop event - Feed-back welcome)

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 13 Apr 2010 09:47:08 +0200

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?

Pascal

---

From: "Roger Alexander" <[email-masked]>
Date: Fri, 16 Apr 2010 17:31:46 -0400

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
> 

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.