Re: [Roll] do we need a dominating set?

Hi Stephen,

indeed, MPR is what comes to mind in this context. This mechanism is used to
identify and maintain connected dominating sets in RFC 5449, RFC 3626, and a
slew of soon-to-be RFCs such
as draft-ietf-manet-nhdp, draft-ietf-ospf-manet-or, draft-ietf-manet-olsrv2.

In order for nodes to see 2 neighbors in the dominating set, you just need
to set the value of the MPR_coverage parameter to 2.

Emmanuel

On Wed, Nov 18, 2009 at 9:07 AM, Pascal Thubert (pthubert) <
pthubert@cisco.com> wrote:

> Hi Stephen:
>
> I've seen evidence that " trickle performs fine (well)" for propagating
> network invariants.
> The state of a node being NOT a network invariant, I see strong evidence
> that we are using a very good hammer for pulling screws.
> The sequenceNb being a network invariant in an instance, my proposal seems
> to be using trickle for what it is good at.
>
> Pascal
>
> >-----Original Message-----
> >From: sdhags@gmail.com [mailto:sdhags@gmail.com] On Behalf Of Stephen
> Dawson-Haggerty
> >Sent: mardi 17 novembre 2009 19:15
> >To: Pascal Thubert (pthubert)
> >Cc: Philip Levis; roll@ietf.org
> >Subject: Re: [Roll] do we need a dominating set?
> >
> >We have lots of evidence that trickle performs fine (well) in lots of
> >settings, including dense ones, when used correctly.  This
> >"improvement" seems pretty speculative-- do we know that this is
> >necessary __in_addition_to_trickle_?  I'm only familiar with the MPRs
> >in OLSR which seem to perform this function, but there trickle is not
> >used.  We'd need strong evidence that trickle was insufficient to
> >include this.
> >
> >Steve
> >
> >On Tue, Nov 17, 2009 at 8:48 AM, Pascal Thubert (pthubert)
> ><pthubert@cisco.com> wrote:
> >> Hi Phil:
> >>
> >>>>
> >>>> The current RPL draft uses trickle to address density. Trickle has a
> >>>> number of fine properties to throttle the control when things are
> >>>> stable.
> >>>> Still, when an accident occurs, like a parent high in the DAG
> >>>> degrades its rank, possibly most of the nodes in the whole network
> >>>> will have to reassess their rank and reset their trickle timer.
> >>>> My understanding of that  process is that it can yield quite a bit
> >>>> of activity, that grows with the number of nodes acting as routers.
> >>>
> >>>Not really, if you have a small redundancy constant. Don't forget, the
> >>>number of messages scales logarithmically with density.
> >>
> >> I understand that the redundancy counter should eliminate redundancies.
> >> I can see how DIO options that contain network wide constants can be
> >> omitted one the
> >> But the fact that a node changes its rank is not a redundancy.
> >> Upon the accident up there, all nodes will have to advertise their new
> >> rank since they are being used wrongly if they don't.
> >>
> >>>> What I think is that even if we have trickle, we should be
> >>>> considering some control on the density of nodes that act as a
> >>>> router. To address that, there's already ample work and large WSN
> >>>> deployments that leverage the concept of dominating set.
> >>>>  A dominating set is a connected set of routers that enables
> >>>> connectivity for all
> >>>> , that is all nodes in the network is connected to at least one
> >>>> member of the dominating set.
> >>>>
> >>>
> >>>I don't think a dominating set is what you mean: a dominating set can
> >>>be disconnected. You're talking about a connected dominating set.
> >>
> >> :)
> >>
> >>>
> >>>> Because we have trickle, such a set does not need to be  shrink to
> >>>> minimal/optimal. In fact, we'd want that each node in the network
> >>>> sees at least 2 members of the dominating set.
> >>>>
> >>>> Can that be achieved simply? Possibly.
> >>>>
> >>>> Each time a new sequence is spread, nodes are entitled to reassess
> >>>> their need to be a router. When the sequence spreads, a form of
> >>>> trickle could be used to decide Not TO advertise self as a router
> >>>> and act as a host for the new sequence.
> >>>> Like if enough neighbor routers advertise the new sequence before T
> >>>> elapse, then there might be no need for self to act as a router.
> >>>
> >>>This is exactly what trickle is designed to do, with its redundancy
> >>>counter.
> >>
> >> I fail to see that we can do it in the example above. I see that if too
> >> many nodes act as router, we'll get many more paths to manage and many
> >> more DIOs generated in case of accident.
> >>
> >> I think we should trickle out the duplicate information in DIO (like DAG
> >> config) when many neighbors have already cried out loud that info.
> >> But we should also trickle out / redistribute the role of router when
> >> opportunity presents itself, that is upon a new sequence.
> >>
> >>
> >>>I thought the major design goal right now to make RPL *less*
> >>>complicated?
> >>
> >> Not having trickle would be a lot less complicated. But also a lot less
> >> efficient. So I'm not going there, see?
> >>
> >> Pascal
> >> _______________________________________________
> >> Roll mailing list
> >> Roll@ietf.org
> >> https://www.ietf.org/mailman/listinfo/roll
> >>
> >
> >
> >
> >--
> >stephen dawson-haggerty
> >http://cs.berkeley.edu/~stevedh
> >uc berkeley wireless and embedded systems lab
> >berkeley, ca 94720
> _______________________________________________
> Roll mailing list
> Roll@ietf.org
> https://www.ietf.org/mailman/listinfo/roll
>