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

["Pascal Thubert (pthubert)" <pthubert at cisco.com>]

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 at gmail.com [mailto:sdhags at gmail.com] On Behalf Of Stephen Dawson-Haggerty
>Sent: mardi 17 novembre 2009 19:15
>To: Pascal Thubert (pthubert)
>Cc: Philip Levis; roll at 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 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