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

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 17 Nov 2009 08:13:06 +0100

Hi:

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.

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.

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.

Thoughts?

Pascal

---

From: Maxence Dalmais <[email-masked]>
Date: Tue, 17 Nov 2009 09:25:49 +0100

Hi Pascal,

the idea seems good to me but I got a question :
-How nodes act during the sequence spreading ?
I mean : Does a node which acted as a router and currently does not
advertise as it continue to route during the T time ?
Moreover, does the fact to change his status of router or not does not
increase packets lost or the number of sent ICMP Destination Unreachable
packet ?

Maxence.

---

From: Philip Levis <[email-masked]>
Date: Tue, 17 Nov 2009 08:10:57 -0800

On Nov 16, 2009, at 11:13 PM, Pascal Thubert (pthubert) wrote:

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

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

> minimal/optimal. In fact, we’d want that each node in the network  
> sees at least 2 members of the dominating set.
>
> 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.

This is exactly what trickle is designed to do, with its redundancy  
counter.

I thought the major design goal right now to make RPL *less*  
complicated?

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 17 Nov 2009 17:37:42 +0100

Hi Matteo:

An orphan can issue a DIS, and that could trigger nodes to switch back
to hosts.
Non orphan becoming orphan would keep sending packets along the previous
sequence.

Upon that, the node that turned off routing might either poison so the
child becomes orphan, 
or switch back to routing with the new sequence.

To be designed :)

Pascal

>-----Original Message-----
>From: Matteo Paris [mailto:[email-masked]]
>Sent: mardi 17 novembre 2009 17:10
>To: Pascal Thubert (pthubert); [email-masked]
>Subject: Re: [Roll] do we need a dominating set?
>
>
>Hi Pascal,
>
>>  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.
>>
>>  Thoughts?
>
>It is a nice idea and seems like it would work well in a network of
>uniform density, so that the k-connectivity of the associated graph
>is high.  My concern is for the case when the graph contains a
>cut-vertex.  If the node at the cut-vertex hears many DIOs and
>decides not to be a router, the graph becomes disconnected.
>
>Can this issue be avoided without requiring a lot of computational
resources?
>Matteo

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 17 Nov 2009 17:37:30 +0100

Hello Maxence

During a sequence transition, the draft says that a child using the
older sequence can use a 'future' parent with the newer sequence.

To avoid false positive in the loop detection mechanism, the rank is the
Flow Label must be reset so the child appears as a host to its parent.

With what we discuss here,  say a  node that was router for sequence N-1
becomes non-router for sequence N. So the node never advertises N and
all its children that see N should migrate over a transition period and
stop using that parent.

Over the transition period, the node should still perform as a N-1
router, acting as prescribed in the draft today, that is resetting the
rank in the flow label for all packets it issues or forwards.

Pascal

From: Maxence Dalmais [mailto:[email-masked]] 
Sent: mardi 17 novembre 2009 09:26
To: Pascal Thubert (pthubert); roll ROLL
Subject: Re: [Roll] do we need a dominating set?

Hi Pascal,

Maxence.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 17 Nov 2009 17:48:16 +0100

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

>> router. To address that, there's already ample work and large WSN

:)

>> minimal/optimal. In fact, we'd want that each node in the network

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*

Not having trickle would be a lot less complicated. But also a lot less
efficient. So I'm not going there, see?

Pascal

---

From: Stephen Dawson-Haggerty <[email-masked]>
Date: Tue, 17 Nov 2009 10:15:25 -0800

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)
<[email-masked]> wrote:
> _______________________________________________
> Roll mailing list
> [email-masked]
> 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

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 18 Nov 2009 09:07:36 +0100

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

>From: [email-masked] [mailto:[email-masked]] On Behalf Of Stephen Dawson-Haggerty
>Sent: mardi 17 novembre 2009 19:15
>To: Pascal Thubert (pthubert)
>Cc: Philip Levis; [email-masked]

---

From: Emmanuel Baccelli <[email-masked]>
Date: Wed, 18 Nov 2009 11:05:54 +0100

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) <
[email-masked]> wrote:

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

---

From: Philip Levis <[email-masked]>
Date: Wed, 18 Nov 2009 09:20:41 -0800

On Nov 18, 2009, at 2:05 AM, Emmanuel Baccelli wrote:

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

Of course, RPL is a distance vector protocol, while OLSR/OSPF are link  
state protocols; that state makes connected dominating sets straight- 
forward to compute. Are there examples of connected dominating sets  
(or variants thereof) being used in a distance vector protocol? It  
seems like there would be a lot of complications.

Phil

---

From: Philip Levis <[email-masked]>
Date: Wed, 18 Nov 2009 09:30:15 -0800

On Nov 18, 2009, at 12:07 AM, Pascal Thubert (pthubert) wrote:

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

"Propagating" is probably the wrong word here, as Trickle's events can  
be local (e.g. local repair).

Generally, Trickle's mechanisms each have advantages for a variety of  
uses:

   1) The exponential timer makes it efficiently maintaining eventual  
consistency
   2) The suppression constant makes it efficiently support broadcast  
operations.
   3) Its randomization helps it support broadcasts, and also evenly  
distributes load.

Etc.

There is always a tension between maintenance and discovery. You want  
to get more information from the active parents/routes/etc., yet do  
not want this to preclude getting information from other nodes who may  
happen to be better options.

It seems to me that the protocol specification allows this already. If  
some higher-level dominating set algorithm (which *clearly* should not  
be in the draft) can improve the protocol, then the fact that  
transmissions MAY increment C is the way to handle this. If a node  
that is a member of this hypothetical dominating set doesn't increment  
C when it hears messages, it isn't suppressed. So  I don't see why the  
specification needs to change.

Phil

---

From: Michael Richardson <[email-masked]>
Date: Wed, 18 Nov 2009 13:40:05 -0500

>>>>> "Pascal" == Pascal Thubert <(pthubert)" <[email-masked]>> writes:
    Pascal>  A dominating set is a connected set of routers that enables
    Pascal> connectivity for all, that is all nodes in the network is
    Pascal> connected to at least one member of the dominating set.

So, in a straight tree arrangement, the dominating set is the non-leaf
nodes.  In a linear arrangement, the dominating set is all the nodes,
except for the last one.
Is this correct?
 
    Pascal> Each time a new sequence is spread, nodes are entitled to
    Pascal> reassess their need to be a router. When the sequence
    Pascal> spreads, a form of trickle could be used to decide Not TO
    Pascal> advertise self as a router and act as a host for the new
    Pascal> sequence.

    Pascal> Like if enough neighbor routers advertise the new sequence
    Pascal> before T elapse, then there might be no need for self to act
    Pascal> as a router.

It sounds like it needs some pseudo-random delays to avoid races.
If the delays are truly random, then the dominating set might flap quite
a lot.  I don't think that's good.

-- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.

---

From: Philip Levis <[email-masked]>
Date: Wed, 18 Nov 2009 13:32:36 -0800

> nodes.  In a linear arrangement, the dominating set is all the nodes,

No. Unfortunately, that's not the definition of a dominating set.  
Dominating set is a precise term that's been used for decades in graph  
algorithms. It helps to not try to redefine such terms, as all it does  
is lead to confusion.

Here's the wikipedia page for dominating set:

http://en.wikipedia.org/wiki/Dominating_set

Note that neither example (a) nor (b) satisfy Pascal's description.  
Pascal is referring to something else, similar to a spanning tree  
where the edges to leaf nodes are not included.

Sorry to be a stickler on this, but if we start misusing well defined  
terminology now, it will just make everything harder to understand  
further along in the process.

Phil

---

From: Michael Richardson <[email-masked]>
Date: Wed, 18 Nov 2009 17:08:07 -0500

>>>>> "Philip" == Philip Levis <[email-masked]> writes:

    >> So, in a straight tree arrangement, the dominating set is the
    >> non-leaf nodes.  In a linear arrangement, the dominating set is
    >> all the nodes, except for the last one.  Is this correct?

    Philip> No. Unfortunately, that's not the definition of a dominating
    Philip> set.  Dominating set is a precise term that's been used for
    Philip> decades in graph algorithms. It helps to not try to redefine
    Philip> such terms, as all it does is lead to confusion.

    Philip> Here's the wikipedia page for dominating set:

    Philip> http://en.wikipedia.org/wiki/Dominating_set

  So my examples are correct interpretations of Pascal's definition, but
what we've defined does not go by that term. :-)

---

From: Philip Levis <[email-masked]>
Date: Wed, 18 Nov 2009 14:11:05 -0800

> what we've defined does not go by that term. :-)

Yes. :)

What Pascal defined is called a "connected dominating set."

Phil

---

From: JP Vasseur <[email-masked]>
Date: Thu, 19 Nov 2009 10:02:09 +0100

Hi Pascal,

On Nov 17, 2009, at 8:13 AM, Pascal Thubert (pthubert) wrote:

> connectivity for all, that is all nodes in the network is connected  
> to at least one member of the dominating set.
>

I do see your reasoning and that notion is indeed used in other  
protocols but the issue here is that you need to determined who you  
put in the set since they need to have connectivity. If you use C and  
set it low enough, isn't it sufficient ?

Cheers.

JP.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 19 Nov 2009 11:19:48 +0100

Hi JP:

What we end up with at the moment is too many routers and then blind
suppression of routing updates. 

I'd rather have less routers and less-to-no suppression. IOW suppress
the role of routers as opposed to the control messages. 

Same "trickle" thinking though, but applied on a different level (router
role as opposed to control message).

Loss of control messages is the source of all evils in DV. That's what
cause count to infinity in RIP in the first place. 

The way we use it, C is equivalent to forcing control packet loss.

CTP copes by having reactive detection. Detection causes the message to
be resent so at the end of the day it is not saved. In the meantime,
convergence was delayed and risk of CTI increased.

In the meantime, packets are lost which might be acceptable in some
environment and not in other. Same reasoning as poisoning.

The thing that helps a bit is that amongst the many routers that are not
needed as routers, a good number is actually not used as routers, so no
detection, and thus no retrigger.

But: 

*         Those guys still issue useless DIOs

*         We end up with more routers and more fine grained paths than
necessary

*         Those paths all need to be maintained thus more control
messages etc...

I'm advocating that the graph should have less (and larger) branches,
and that those branches could be reevaluated at each new sequence, for
instance to adapt to the battery level of the active routers. That's
good for control overhead and that's good for multicast.

I'm claiming that we can do that using trickle, for all the great
properties that Phil has listed in many places. Once we are at that we
can discuss the algorithm but there's enough info in this thread for
people to figure out how.

I still see the value of trickling the control packets because of the
exponential backoff piece but wish to limit the suppression of routing
information as much as possible.

Pascal

From: JP Vasseur (jvasseur) 
Sent: jeudi 19 novembre 2009 10:02
To: Pascal Thubert (pthubert)
Cc: [email-masked]
Subject: Re: [Roll] do we need a dominating set?

Hi Pascal,

Hi:

Thoughts?

I do see your reasoning and that notion is indeed used in other
protocols but the issue here is that you need to determined who you put
in the set since they need to have connectivity. If you use C and set it
low enough, isn't it sufficient ?

Cheers.

JP.

Pascal

---

From: Philip Levis <[email-masked]>
Date: Thu, 19 Nov 2009 06:06:55 -0800

On Nov 19, 2009, at 2:19 AM, Pascal Thubert (pthubert) wrote:

> I still see the value of trickling the control packets because of  
> the exponential backoff piece but wish to limit the suppression of  
> routing information as much as possible.

Then you cannot scale to dense networks. This is not a decision the  
specification should make unilaterally.

I don't see what the big deal is: the specification already allows  
this flexibility by saying MAY increment C.

Phil