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

[Stephen Dawson-Haggerty <stevedh at eecs.berkeley.edu>]

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