Subject: Re: [Roll] DAO fan out

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 19 Apr 2010 17:35:04 +0200

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
- that this is a simple and efficient solution 
- 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?)
- some more explanation on the source route case (how the root can play
the same game recursively and obtain a good result as well)

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
>

---

From: "Roger Alexander" <[email-masked]>
Date: Tue, 27 Apr 2010 17:11:00 -0400

Hi Pascal,

Please find attached an expanded note on the DAO fan out control and path
prioritization mechanism.

Roger

> Sent: Monday, April 19, 2010 11:35 AM
> Subject: RE: [Roll] DAO fan out
> 
> Hi Roger:
> 

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.

> - a visual example on the mechanism as work (if you have a pdf

Note plus a few examples attached (pdf and MS Word).

> 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.