Subject: [Roll] Options in DIS

From: <[email-masked]>
Date: Fri, 19 Mar 2010 18:44:44 +0100

Hi all,

I have already expressed a desire for options in the DIS packet
http://www.ietf.org/mail-archive/web/roll/current/msg02765.html
Jerry and Mukul expressed their support to the request.
http://www.ietf.org/mail-archive/web/roll/current/msg02766.html
http://www.ietf.org/mail-archive/web/roll/current/msg02770.html

Then Phil asked for a justification for the request, which I admit I
haven't provided yet.
http://www.ietf.org/mail-archive/web/roll/current/msg02774.html

More recently, Tzeta suggested that DIS have security options
http://www.ietf.org/mail-archive/web/roll/current/msg03101.html

Independently, Yaov and Matteo both again expressed the need for DIS
option.
http://www.ietf.org/mail-archive/web/roll/current/msg03185.html
http://www.ietf.org/mail-archive/web/roll/current/msg03290.html

I do believe we have a serious point here.
Please find the justification below.
Can we please have a ticket to work on it ?
I volunteer to gather others contributors' opinions/requests and and
propose detailed text to be included in future revisions of the RPL
draft.
Best,

Dominique

-------------------------------------------
The following is extracted from a typical water/gas smart metering
infrastructure.
The utility company worker adds new metering points into the network as
meters are replaced or fitted with sensing/transmission  electronics. 
Before the worker leaves the premises, he/she is requested to check that
the meter has actually joined the network.
This cannot wait for a trickled-down DAO to arrive.
Therefore, the meter will send a DIS to collect information from the
network.
Without DIS options, all neighbor routers will respond, spending energy
for their own transmission and triggering energy expenditure in  all
neighbor nodes that overhear the responses.

Let's consider a "wheel" model for the network topology, with a sink at
the center and spokes connecting outward to ring-1 routers, ring-2
routers and periphery meters. The meters have routing capability
themselves, although I'll call them meters in the following text to
distinguish them from devices solely intended at providing connectivity,
which I'll call routers.
Let's consider a generic "pizza slice" of this wheel. Since there's
central symmetry in the network, there's no border effect in the slice
We typically have
- one mains-powered sink at the center,
- N severely energy-limited meters at the periphery, deeply burried into
basements or manholes
- N/20 fairly energy-limited ring-1 routers, located on high spots
- N/10 fairly energy-limited ring-2 routers, located on high spots
In RPL parlance, ring-1 routers would have a typical rank of 4, and
ring-2 routers would have a typical rank of 8
The N/10 and N/20 ratios above are dictated by energy/lifetime
considerations, not radio coverage.
A typical connectivity is the following
- each meter is in range of N/10 and N/20 routers, albeit with *very*
different link qualities
- each router is in range of N/10 and N/20 routers, with various link
qualities 
- each meter is in range of N/20 meters
The ratios and assumptions above hold for values of N in the [20..200]
range. 

**** Without DIS options, we have
NT0 = Number of DIS multicast transmission = 1
NR0 = Number of DIS active receptions = N/5 (due to N/20 meters and
(N/10+N/20) routeurs), 
NT1 = N/20 DIO transmissions from meters; each one being overheard by
N/20 meters and (N/10+N/20) routers
NT2 = N/10+N/20 DIO transmissions from routers; each one being overheard
by N meters and (N/10+N/20) routers
NR1 ~= NT1 * (3N/20 + N/20) = N^2/100 = 0.01 * N^2 receptions due to DIO
coming from meters
NR2 ~= NT2 * (N + N/20 + N/10) = N^2*69/400 = 0.17 * N^2 receptions due
to DIO coming from routers

We therefore have
Number of transmissions: NT = NT0 + NT1 + NT2 = 1 + N/20 + (N/10 + N/20)
= 24/20 * N = 1 + 0.2 * N
Number of receptions   : NR = NR0 + NR1 + NR2 = 0.2 * N + 0.18 * N^2

Total energy cost Etotal = NT * Et + NR * Er

If the network is asynchronous and uses basic preamble sampling, the
cost of overhearing Eo is the cost of receiving the expected duration
(half) of the preamble.
Since the DIS packet is small, its unit reception cost Er is about the
same as the overhearing cost Eo.
With a small (<1KB) DIO packet, the cost of transmission Et is
essentially the cost of sending the preamble.
Let's assume transmission cost Et is 6 times Eo (full preamble length
accounts for x2, power consumption for x3)

Etotal ~= Eo * ( 1 * 6 + N * (0.2 * 6 + 0.2) + 0.18 * N^2) ~= Eo * ( 6 +
1.4 * N + 0.18 * N^2) 

**** With DIS options
A typical protocol currently in use in widely deployed proprietary smart
metering networks is the following.
Newborn nodes send successive DIS'es with decreasing demands on rank and
link quality
- iteration 1: only sinks, LQI >= 0,75*maxLQI
- iteration 2: only sinks, LQI >= 0,5*maxLQI
- iteration 3: only sinks, LQI >= 0,25*maxLQI
- iteration 4: ring-1 routers, LQI >= 0,75*maxLQI,
- iteration 5: ring-1 routers, LQI >= 0,50*maxLQI,
- iteration 6: ring-1 routers, LQI >= 0,25*maxLQI,
- iteration 7: ring-2 routers, LQI >= 0,75*maxLQI,
- iteration 8: ring-2 routers, LQI >= 0,50*maxLQI,
- iteration 9: ring-2 routers, LQI >= 0,25*maxLQI,
- etc
The newborn node will usually send several DIS's instead of just one.
Its direct neighbors (N/20 meters, N/10+N/20 routers) will also incur
the cost of receiving these extra DIS'es.
Let's suppose iteration 7 is successful and prompts 25% of the neighbor
ring-2 routers to send their DIOs.
Number of DIS transmissions = 7
Number of DIS receptions = 7 * (N/20 + N/10 + N/20) = 7/5 * N
Number of DIO transmissions = 25% of N/10 = N/40, overheard by 23/20 * N
nodes (N meters and N/10+N/20 routers).
Number of DIOs overheard = 23/800 * N^2 = 0.029 * N^2
Etotal ~= Eo * ( 7*6 + N * ( 7/5 + 6/40) + 0.029 * N^2) ~= Eo * (42 +
1.6 * N + 0.029 * N^2)

In this case, the global energy cost of inserting a new node in the
network is reduced by a factor ranging from 2 to 5 depending on N in
[20..200]. Additional analysis shows that this saving affect both meters
and routers (specifically, we are not pushing the burden towards the
energy-critical meters).
Similar results are obtained with differents iterations numbers.

Just to re-inforce this calculation, it has been our experience that
node insertion into a dense low-power network, if done wrong, is a
significant energy drain. Please let us enhance RPL to do it right.

---

From: Bernard Tourancheau <[email-masked]>
Date: Mon, 22 Mar 2010 21:17:35 +0100

Dominique,
We are supporting your proposal as well.
Best regards,
Bernard.
Le 19 mars 2010 à 18:44, <[email-masked]> <[email-masked]> a écrit :

> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Laurent Toutain <[email-masked]>
Date: Mon, 22 Mar 2010 21:26:33 +0100

We also support the idea, it offers the possibility to make the standard
evolves.

Laurent

On Mon, Mar 22, 2010 at 21:17, Bernard Tourancheau <
[email-masked]> wrote:

> Le 19 mars 2010 à 18:44, <[email-masked]> <
> [email-masked]> a écrit :
>
> > Hi all,
> >

-- 
Laurent Toutain
Tel: +33 2 22 06 82 37

---

From: Philip Levis <[email-masked]>
Date: Mon, 22 Mar 2010 14:02:24 -0700

> propose detailed text to be included in future revisions of the RPL

Dominique:

This is an interesting problem; I think the basic question is the speed with which you generate a very good route. Make no mistake -- using Trickle timers for DIOs means that you can quickly find a route, but not necessarily the best one. The assumption is that, over time, nodes will hear DIOs from a larger set of possible next hops and continuously improve their routes. We see this in practice with CTP: a node joining the network can almost immediately find a route, but the route churns a little as it incrementally finds better ones.

DIOs currently have a mechanism to reduce transmission load: redundant packet suppression. For example, RPL can define "redundant" as a DIO whose Rank <= the local Rank. If you set a redundancy constant > 1, (e.g., 3), then the probability all nodes at the best possible Rank will be suppressed is amazingly low, and decreases exponentially with each Trickle interval. Why isn't this sufficient? Given all of the dangerous edge cases in wireless, randomized algorithms that converge tend to be much more reliable than deterministic ones which seek to find the optimal solution.

Phil

---

From: <[email-masked]>
Date: Tue, 23 Mar 2010 00:48:36 +0100

Hi Phil,

Thanks for your reply. Maybe I was not clear enough that we do understand the benefit of DIO trickle timers and of routing improvements over time, and we indeed intend to use them. The use of DIS, in my mind, was not substitute to DIOs.

As you mention, Trickle timers are so powerful that they will suppress many DIO transmissions and that's good for energy consumption.
Yet, relying solely on DIOs, the worker on the field might have to wait for a very long time for anything to happen on the node that he/she just installed. I already mentioned we don't want him/her to leave the premises until he/she has ascertained that decent minimal connectivity can be established: the node might need to be moved, or "coverage extenders" installed in the vicinity, which he/she needs to find during the same field trip.

In some networks I'm interested in, recuring background activity happens about every hour. If I want these networks to have a similar lifetime with RPL than they currently have with proprietary protocols, the max interval for Trickle timers should also be about an hour.
Trickle timers will, as you just mentioned, suppress most transmissions in a given radio neighborhood. Therefore, even in dense networks, my field worker will sit waiting for dozens of minutes, typically. Do you know any commercial company that will tolerate this? The mandate is more like less than a minute. Current proprietary procotols do achieve this through some router discovery protocol [Maleysson2005].
If we want to transition these networks to RPL, there needs to be a way for the new node to trigger its insertion into the network, and my understanding is that DIS are meant just for that.
Am I missing something here?
With best regards,

Dominique

[Maleysson2005] Maleysson, L. and Dugas, C. "Configuring and managing a large-scale monitoring
network solving real world challenges for ultra low powered and long-range wireless mesh networks",
in Proceedings of the 2005 Joint Conference on Smart Objects and Ambient intelligence: innovative
Context-Aware Services: Usages and Technologies (sOc-EUSAI '05), Grenoble,
France, October 12 - 14, 2005, vol. 121. ACM, New York, NY,
 
-----Message d'origine-----
De : Philip Levis [mailto:[email-masked]] 
Envoyé : lundi 22 mars 2010 14:02
À : BARTHEL Dominique RD-TECH-GRE
Cc : [email-masked]
Objet : Re: [Roll] Options in DIS

Dominique:

Phil

---

From: Philip Levis <[email-masked]>
Date: Mon, 22 Mar 2010 18:36:43 -0700

> Am I missing something here?

If a node sends a DIS, this will cause all node that receive the DIS to reset their Trickle timers. They will now have small transmission intervals for DIOs. However, these transmissions will suppress one another, such that you don't get an O(neighbors) response : Trickle's suppression will reduce the transmissions to k * log(neighbors). If the concern is that "bad" DIOs suppress "better" DIOs, this is a problem generally: we can define redundancy such that "bad" DIOs are not redundant to "better" DIOs.

Does that make sense? Am I understanding the problem correctly?

Phil

---

From: Matteo Paris <[email-masked]>
Date: Tue, 23 Mar 2010 09:35:06 -0400

Hi Phil,

The concern that I raised did not have to do with trying to further 
suppress DIO messages within a single DODAG beyond what is provided 
by Trickle.

Rather, I described the scenario in which there are multiple DODAGS 
(dozens) in a dense network (eg, hundreds of nodes within radio range 
of each other).  It is often the case that the node sending the DIS 
has specific information about which DODAG it is interested in, in 
the form of destination prefixes, dag ids, instance ids, etc.  If 
this information were contained in the DIS, the filtering could 
happen prior to transmission of DIOs, saving the network from 
significant unneccessary disruption.

What do you think?
Matteo

At 6:36 PM -0700 3/22/10, Philip Levis wrote:
>On Mar 22, 2010, at 4:48 PM, <[email-masked]> 
><[email-masked]> wrote:
>
>>  Hi Phil,
>>
>>  Thanks for your reply. Maybe I was not clear enough that we do 
>>understand the benefit of DIO trickle timers and of routing 
>>improvements over time, and we indeed intend to use them. The use 
>>of DIS, in my mind, was not substitute to DIOs.
>>
>>  As you mention, Trickle timers are so powerful that they will 
>>suppress many DIO transmissions and that's good for energy 
>>consumption.
>>  Yet, relying solely on DIOs, the worker on the field might have to 
>>wait for a very long time for anything to happen on the node that 
>>he/she just installed. I already mentioned we don't want him/her to 
>>leave the premises until he/she has ascertained that decent minimal 
>>connectivity can be established: the node might need to be moved, 
>>or "coverage extenders" installed in the vicinity, which he/she 
>>needs to find during the same field trip.
>>
>>  In some networks I'm interested in, recuring background activity 
>>happens about every hour. If I want these networks to have a 
>>similar lifetime with RPL than they currently have with proprietary 
>>protocols, the max interval for Trickle timers should also be about 
>>an hour.
>>  Trickle timers will, as you just mentioned, suppress most 
>>transmissions in a given radio neighborhood. Therefore, even in 
>>dense networks, my field worker will sit waiting for dozens of 
>>minutes, typically. Do you know any commercial company that will 
>>tolerate this? The mandate is more like less than a minute. Current 
>>proprietary procotols do achieve this through some router discovery 
>>protocol [Maleysson2005].
>>  If we want to transition these networks to RPL, there needs to be 
>>a way for the new node to trigger its insertion into the network, 
>>and my understanding is that DIS are meant just for that.
>If a node sends a DIS, this will cause all node that receive the DIS 
>to reset their Trickle timers. They will now have small transmission 
>intervals for DIOs. However, these transmissions will suppress one 
>another, such that you don't get an O(neighbors) response : 
>Trickle's suppression will reduce the transmissions to k * 
>log(neighbors). If the concern is that "bad" DIOs suppress "better" 
>DIOs, this is a problem generally: we can define redundancy such 
>that "bad" DIOs are not redundant to "better" DIOs.
>

---

From: Philip Levis <[email-masked]>
Date: Tue, 23 Mar 2010 08:08:41 -0700

On Mar 23, 2010, at 6:35 AM, Matteo Paris wrote:

> 
> Hi Phil,
> 
> The concern that I raised did not have to do with trying to further suppress DIO messages within a single DODAG beyond what is provided by Trickle.
> 
> Rather, I described the scenario in which there are multiple DODAGS (dozens) in a dense network (eg, hundreds of nodes within radio range of each other).  It is often the case that the node sending the DIS has specific information about which DODAG it is interested in, in the form of destination prefixes, dag ids, instance ids, etc.  If this information were contained in the DIS, the filtering could happen prior to transmission of DIOs, saving the network from significant unneccessary disruption.
> 
> What do you think?
> 

I think this makes total sense. But should it be a standard DIS field, or a DIS option? If a standard field there will need to be an all IDs/broadcast value.

Phil

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Sun, 28 Mar 2010 10:44:31 +0300

Hi,

To my understanding, DIS's are not so commonly used.
It could be that introducing the DIS fields to all packets would be the
simplest solution.

Thanks,
Yoav

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Philip Levis
Sent: Tuesday, March 23, 2010 5:09 PM
To: Matteo Paris
Cc: [email-masked]
Subject: Re: [Roll] Options in DIS

> The concern that I raised did not have to do with trying to further
suppress DIO messages within a single DODAG beyond what is provided by
Trickle.
> Rather, I described the scenario in which there are multiple DODAGS
(dozens) in a dense network (eg, hundreds of nodes within radio range of
each other).  It is often the case that the node sending the DIS has
specific information about which DODAG it is interested in, in the form of
destination prefixes, dag ids, instance ids, etc.  If this information
were contained in the DIS, the filtering could happen prior to
transmission of DIOs, saving the network from significant unneccessary
disruption.
> What do you think?

I think this makes total sense. But should it be a standard DIS field, or
a DIS option? If a standard field there will need to be an all
IDs/broadcast value.

Phil

---

From: JP Vasseur <[email-masked]>
Date: Mon, 29 Mar 2010 05:43:51 +0200

Dear all,

Since there is a consensus in adding the possibility to have TLVs in  
the future in the DIS
I opened a ticket. The idea would be to simply have an empty body with  
no TLV for the
moment but that could in the future carry TLVs.

Thanks.

JP.

---

From: Philip Levis <[email-masked]>
Date: Sun, 28 Mar 2010 21:50:08 -0700

On Mar 28, 2010, at 8:43 PM, JP Vasseur wrote:

> Dear all,
>
> Since there is a consensus in adding the possibility to have TLVs  
> in the future in the DIS
> I opened a ticket. The idea would be to simply have an empty body  
> with no TLV for the

Remember, code size is an issue: arbitrary options are a bad idea. We  
should concretely specify the expected common options (which seem to  
be basic predicates on whom should respond).

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 29 Mar 2010 07:16:14 +0200

I agree with this.

There are obvious fields that could be in the base, without even an
option.
For instance, root id, instance id, or OF, if either is known. 
If we can get a consensus on adding those in the base DIS, this can be
added in the 08 respin.

Cheers,

Pascal

> Sent: Tuesday, March 23, 2010 4:09 PM
> To: Matteo Paris
> Cc: [email-masked]
suppress
> DIO messages within a single DODAG beyond what is provided by Trickle.
> >
of
> each other).  It is often the case that the node sending the DIS has
specific
> information about which DODAG it is interested in, in the form of
destination
> prefixes, dag ids, instance ids, etc.  If this information were
contained in the
> DIS, the filtering could happen prior to transmission of DIOs, saving
the
> network from significant unneccessary disruption.
> >
> > What do you think?
> >
> 
> I think this makes total sense. But should it be a standard DIS field,
or a DIS
> option? If a standard field there will need to be an all IDs/broadcast
value.