Subject: [Roll] [ROLL] RPL applicability statement for AMI networks

From: "Popa, Daniel" <[email-masked]>
Date: Mon, 25 Jul 2011 08:34:27 -0700

Hi all,

I want to bring to your attention the submission of the draft-popa-roll-applicability-ami-00 describing the applicability statement for the Routing Protocol for Low Power and Lossy Networks (RPL) in Advanced Metering Infrastructure (AMI) networks. 

Please look at this draft and share your views. We will be presenting the draft at the ROLL f2f meeting.

Thanks.
Daniel

---

From: Philip Levis <[email-masked]>
Date: Mon, 25 Jul 2011 09:32:00 -0700

On Jul 25, 2011, at 8:34 AM, Popa, Daniel wrote:

> draft-popa-roll-applicability-ami-00

Daniel,

Can you explain the reasoning for this statement:

  o  AMI deployments SHOULD set DIORedundancyConstant to a value of 10
      or more.

This basically gives up one of the very valuable properties of Trickle, its ability to scale well to high densities while maintaining a low communication/energy cost.

Thanks!

Phil

---

From: "Popa, Daniel" <[email-masked]>
Date: Tue, 26 Jul 2011 11:48:16 -0700

Dear Phil, 

I think that setting DIORedundancyConstant to a value of 10 or more is not necessarily giving up of Trickle ability to suppress messages, while in the same time being able to facilitate a significant reduction of transmissions. 

I believe you will agree that there is a tradeoff between the redundancy count and how quickly one can find good paths. You will probably also agree that the application space you have in mind when speaking about low communication/energy cost is the battery powered devices. Or in AMI space, many (metering) devices are not energy constrained (being connected to the powerline).   

This being said, this is a typical feature we would to hear different opinions/feedbacks and so I thank you for your question.

Regards, 
Daniel

> -----Original Message-----
> From: Philip Levis [mailto:[email-masked]]
> Sent: Monday, July 25, 2011 12:32 PM
> To: Popa, Daniel
> Cc: [email-masked]
> Subject: Re: [Roll] [ROLL] RPL applicability statement for AMI networks
> 
> 
> This basically gives up one of the very valuable properties of Trickle,
> its ability to scale well to high densities while maintaining a low
> communication/energy cost.
> 
> Thanks!
> 
> Phil

---

From: Philip Levis <[email-masked]>
Date: Tue, 26 Jul 2011 11:57:54 -0700

> This being said, this is a typical feature we would to hear different opinions/feedbacks and so I thank you for your question.

My major concern is that this is a SHOULD on a magic constant which doesn't really have any evidence behind it. Why 10? Why not 5? Why not 20? In practice, I've seen a constant of 2 be sufficient to find good paths. It might be that the first interval doesn't find the best path, but since there are multiple intervals nodes do tend to reasonable ones quickly and the best ones within a reasonable latency.

The major issue is that as DIORedundancyConstant grows, so does the minimum interval size. If you have a DIORedundancyConstant of 10, then you need to pick a minimum interval size large enough to accommodate 10 log(n) transmissions. This reduces the speed with which RPL can repair problems in a sparse network.

Phil

---

From: Jay Ramasastry <[email-masked]>
Date: Tue, 26 Jul 2011 12:04:03 -0700

There are many other issues that influence the routing protocol for smart-grid wireless networks beyond that described in this ROLL contribution. Such issues are being addressed at the IEEE802 and TIA. It is useful if this contribution is referred to those for a rather than addressed in isolation.

Jay R

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Popa, Daniel
Sent: Tuesday, July 26, 2011 11:48 AM
To: Philip Levis
Cc: [email-masked]
Subject: Re: [Roll] [ROLL] RPL applicability statement for AMI networks

Dear Phil, 

Regards,
Daniel

> This basically gives up one of the very valuable properties of 
> Trickle, its ability to scale well to high densities while maintaining 
> a low communication/energy cost.
> 
> Thanks!
> 
> Phil
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: "Popa, Daniel" <[email-masked]>
Date: Tue, 26 Jul 2011 12:34:15 -0700

Phil,

> Sent: Tuesday, July 26, 2011 2:58 PM
> To: Popa, Daniel
> Cc: [email-masked]
> > I think that setting DIORedundancyConstant to a value of 10 or more
> is not necessarily giving up of Trickle ability to suppress messages,
> while in the same time being able to facilitate a significant reduction
> of transmissions.
> >
> > I believe you will agree that there is a tradeoff between the
> redundancy count and how quickly one can find good paths. You will
> probably also agree that the application space you have in mind when
> speaking about low communication/energy cost is the battery powered
> devices. Or in AMI space, many (metering) devices are not energy
> constrained (being connected to the powerline).
> >
> > This being said, this is a typical feature we would to hear different
> opinions/feedbacks and so I thank you for your question.
> >
> > Regards,
> > Daniel
> 
> My major concern is that this is a SHOULD on a magic constant which
> doesn't really have any evidence behind it. Why 10? Why not 5? Why not
> 20? 

DP> You have a good point! Why 2 is better than 10, or 5, or 20? Let explore and see what is the "best" value.

>In practice, I've seen a constant of 2 be sufficient to find good  
> paths. It might be that the first interval doesn't find the best path,
> but since there are multiple intervals nodes do tend to reasonable ones
> quickly and the best ones within a reasonable latency.

DP> I see.... Can you PLS provide details on simulations/deployments that allowed you to conclude that that a constant of 2 is sufficient (or better than...)?

> The major issue is that as DIORedundancyConstant grows, so does the
> minimum interval size. If you have a DIORedundancyConstant of 10, then
> you need to pick a minimum interval size large enough to accommodate 10
> log(n) transmissions. This reduces the speed with which RPL can repair
> problems in a sparse network.

DP> A trade-off should be find but without giving bigger advantage to one scenario (e.g., sparse) over another.

---

From: "Popa, Daniel" <[email-masked]>
Date: Tue, 26 Jul 2011 12:37:40 -0700

Hi Jay, 

Thank you for your feedback. 

Can you please point us to the documents you mention?

Daniel   

> From: Jay Ramasastry [mailto:[email-masked]]
> Sent: Tuesday, July 26, 2011 3:04 PM
> To: Popa, Daniel; Philip Levis
> Cc: [email-masked]
> Subject: RE: [Roll] [ROLL] RPL applicability statement for AMI networks
> 
> There are many other issues that influence the routing protocol for
> smart-grid wireless networks beyond that described in this ROLL
> contribution. Such issues are being addressed at the IEEE802 and TIA.
> It is useful if this contribution is referred to those for a rather
> than addressed in isolation.
> 
> Jay R
> 
> I think that setting DIORedundancyConstant to a value of 10 or more is
> not necessarily giving up of Trickle ability to suppress messages,

---

From: Philip Levis <[email-masked]>
Date: Tue, 26 Jul 2011 15:08:48 -0700

> DP> You have a good point! Why 2 is better than 10, or 5, or 20? Let explore and see what is the "best" value.

Sure. Just trying to point out some of these experiments have been done, and the results have been posted to this list by Om on April 29, 2010 (link below).

> DP> I see.... Can you PLS provide details on simulations/deployments that allowed you to conclude that that a constant of 2 is sufficient (or better than...)?

General conclusion: setting a k=10 (DIORedundancyConstant=10) increases control overhead but does not improve path quality:

http://stuff.stanford.edu/~om_p/ctp/beaconsuppression.html

The way to think of it is this: what's important is that a node find a "usable" route almost immediately, a "reasonable" route quickly, and something within an epsilon of the best route within a reasonable time frame. Because Trickle is a continuous process, this is what generally happens. By accepting the eventual nature of the algorithm and its use in routing maintenance, you can find routes faster yet still converge to near-optimal routes pretty quickly. The tiny overhead in that "lost" optimality over a couple of Trickle intervals really is in the noise.

Phil

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 26 Jul 2011 15:36:41 -0700

Phil,

Om's results seem to focus on networks that are relatively sparse compared to what we have in mind.  Could you provide some insight into how dense these testbeds are under the different setups?

We are dealing with networks where nodes can have order hundreds of neighbors (yes, a single node can have more neighbors than all nodes in Tutornet and Motelab combined).  From our experiments, increasing the min interval helps deal with increased density because it reduces the likelihood of collisions.  Of course, the side effect of that is that the overall responsiveness of the protocol becomes slower.  To find good routes within a reasonable time scale, it also helps to increase the redundancy constant.  Note that a value of 10 still allows significant suppression ratios when the density is high.

I recognize that the Trickle parameters will vary for different deployment scenarios (sparse vs. dense, energy-constrained vs. mains-powered, etc) and application requirements (capacity allocated to control traffic, response time, etc.).  The draft does not currently provide any discussion on that but should.

--
Jonathan Hui

---

From: "Alvaro A. Cardenas" <[email-masked]>
Date: Tue, 26 Jul 2011 15:43:36 -0700

Jonathan,

> We are dealing with networks where nodes can have order hundreds of neighbors (yes, a single node can have more neighbors than all nodes in Tutornet and Motelab combined).  From our experiments, increasing the min interval helps deal with increased
There has been a lot of work regarding the density of AMI networks in
the Priority Action Plan 2 (PAP 2) of the SGIP (and also the Open SG
networking groups) and several considerations for rural, suburban and
urban environments under different PHY layers and power used for
reception and transmission.  Is the draft taking into consideration this
work and how the parameters will change depending on the specific
deployment?

Regards,
Alvaro

> density because it reduces the likelihood of collisions.  Of course, the side effect of that is that the overall responsiveness of the protocol becomes slower.  To find good routes within a reasonable time scale, it also helps to increase the redundancy constant.  Note that a value of 10 still allows significant suppression ratios when the density is high.
>

---

From: "Popa, Daniel" <[email-masked]>
Date: Tue, 26 Jul 2011 17:11:40 -0700

Alvaro, 

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Alvaro A. Cardenas
> Sent: Tuesday, July 26, 2011 6:44 PM
> To: Jonathan Hui
> Cc: [email-masked]
> > We are dealing with networks where nodes can have order hundreds of
> neighbors (yes, a single node can have more neighbors than all nodes in
> Tutornet and Motelab combined).  From our experiments, increasing the
> min interval helps deal with increased

Can you be more specific PLS and point us to some documents? A lot of work has been done within PAP2, SGIP or OpenSG 
on wireless PHY and MAC performance versus channel characteristics & density.

> Regards,
> Alvaro
> 
> > density because it reduces the likelihood of collisions.  Of course,
> the side effect of that is that the overall responsiveness of the
> protocol becomes slower.  To find good routes within a reasonable time
> scale, it also helps to increase the redundancy constant.  Note that a
> value of 10 still allows significant suppression ratios when the
> density is high.
> >
> > I recognize that the Trickle parameters will vary for different
> deployment scenarios (sparse vs. dense, energy-constrained vs. mains-
> powered, etc) and application requirements (capacity allocated to
> control traffic, response time, etc.).  The draft does not currently
> provide any discussion on that but should.
> >
> > --
> > Jonathan Hui
> >

---

From: Philip Levis <[email-masked]>
Date: Tue, 26 Jul 2011 17:40:01 -0700

> I recognize that the Trickle parameters will vary for different deployment scenarios (sparse vs. dense, energy-constrained vs. mains-powered, etc) and application requirements (capacity allocated t…

Let me try to summarize, please tell me if/how I'm wrong: in very dense AMI deployments, MAC collisions on short intervals are a real problem, so you need significant additional random backoff from a higher layer to avoid these collisions. 

If this is the case, then I'd recommend describing this as a more conservative value than what is specified in 6.6 of RFC6206. I.e., AMI networks have super-high density, so recommend that Imin be XX times the packet transmission time, and use a larger k to increase the communication rate. 

It's useful to note that, in the case of synchronized intervals, these k may be clustered early in the interval. So you can have bursts of control traffic.

Phil

---

From: "Alvaro A. Cardenas" <[email-masked]>
Date: Tue, 26 Jul 2011 22:51:29 -0700

Hi Daniel,

I am talking about the main (only?) document of PAP2: NIST-IR 7761.  There
are many examples where the average number of neighbors can range between a
dozen or so for rural deployments to thousands of nodes (depending on the
transmission and reception power).

http://collaborate.nist.gov/twiki-sggrid/pub/SmartGrid/PAP02Objective3/NISTI
R7761.pdf

OpenSG is doing follow up work on PAP 2.

In our experience, even in the same AMI network deployment, the node
connectivity can range from 1 neighbor to hundreds of neighbors.

Regards,
Alvaro

-----Original Message-----
From: Popa, Daniel [mailto:[email-masked]]
Sent: Tuesday, July 26, 2011 5:12 PM
To: Alvaro A. Cardenas
Cc: [email-masked]; Jonathan Hui
Subject: RE: [Roll] [ROLL] RPL applicability statement for AMI networks

Alvaro,

> work and how the parameters will change depending on the specific

Can you be more specific PLS and point us to some documents? A lot of work
has been done within PAP2, SGIP or OpenSG
on wireless PHY and MAC performance versus channel characteristics &
density.

---

From: Don Sturek <[email-masked]>
Date: Wed, 27 Jul 2011 12:46:30 -0700

Hi Alvaro,

The PAP 2 NISTIR 7761 is probably not the document you want.

There is ongoing work in PAP 2 to model density, foliage and distance in
addition to the requirements presented in NISTIR 7761.  Have a look at
this ongoing PAP 2 work as the modeling is just now being discussed and
there should be some important density/distance information forthcoming by
the end of this year.

Don

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 28 Jul 2011 06:46:27 -0700

> Let me try to summarize, please tell me if/how I'm wrong: in very dense AMI deployments, MAC collisions on short intervals are a real problem, so you need significant additional random backoff from…

That's a good summary.

> If this is the case, then I'd recommend describing this as a more conservative value than what is specified in 6.6 of RFC6206. I.e., AMI networks have super-high density, so recommend that Imin be…

Right.  The draft should do a better job discussing the tradeoffs and the particular choice of suggested parameters.

> It's useful to note that, in the case of synchronized intervals, these k may be clustered early in the interval. So you can have bursts of control traffic.

Yes, another side effect of a relatively small Imin.

--
Jonathan Hui

---

From: Philip Levis <[email-masked]>
Date: Thu, 28 Jul 2011 08:32:08 -0700

> Right.  The draft should do a better job discussing the tradeoffs and the particular choice of suggested parameters.

With my engineering hat on, I think I'm arguing something a bit stronger. Rather than say that k should be large, it should say that Imin should be large to deal with high densities, and that k can be scaled up to lead to better responsiveness.

With my research hat on, I'm not sure doing this is the right answer. One of the original motivations for exponentially increasing I was this exact problem, that too small an I can lead to MAC layer collisions. By exponentially increasing I, one should be able to find the first "good" I value (let's call it Igood) within Igood; all of the intervals before Igood sum to Igood/2, and the silence period adds another Igood/2. This requires no configuration, and will work for any Igood (as long as it is smaller than Imax). One can of course tune k and Imin to a particular density, but wireless networks typically have highly variable density, so good settings in one part of the network might not be good in others. 

The research question would be, for networks with highly variable density, whether it's better to select a suitable large Imin and k or to choose a small Imin and k. If you have some results which sheds light on the question, I'd appreciate it. I've always thought it was the latter, but I could imagine all kinds of nitty gritty details (such as MAC backoff behavior) could affect the result.

> Yes, another side effect of a relatively small Imin.

You mean *large* Imin, right? A small Imin would spread, over the same time duration, transmissions over intervals of exponentially increasing length.

Phil

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 28 Jul 2011 09:32:44 -0700

> With my engineering hat on, I think I'm arguing something a bit stronger. Rather than say that k should be large, it should say that Imin should be large to deal with high densities, and that k can…

Yes, I had that in mind as well.

> The research question would be, for networks with highly variable density, whether it's better to select a suitable large Imin and k or to choose a small Imin and k. If you have some results which…

While I agree that AMI networks can have highly variable density, it's also important to consider the actual magnitudes of that range.  In this particular case, the minimum density for many urban deployments are typically more dense that the Tutor and Motelab testbeds.

Part of the answer in choosing an appropriate Imin depends on the level of peak congestion you are willing to accept.  One could argue that it's the MAC's job of appropriately handling congestion, but that reduces down to rate-limiting what upper layers can send and removes the need for Imin.

We've found that too small an Imin can lead to excessive congestion and packet loss, causing updated Trickle information to propagate less reliably for some period of time.  During this inconsistent period, devices continue to reset their Trickle timers and the interval stays at Imin.

Also, RFC6206 makes the following statement:

   Finally, a protocol SHOULD set k and Imin such that Imin is at least
   two to three times as long as it takes to transmit k packets.
   Otherwise, if more than k nodes reset their intervals to Imin, the
   resulting communication will lead to congestion and significant
   packet loss.

To me, that statement conveys that an appropriate "Imin" value is dependent on density.

> You mean *large* Imin, right? A small Imin would spread, over the same time duration, transmissions over intervals of exponentially increasing length.

I guess we are talking about different scenarios.  I was addressing the case of many devices resetting their Trickle timer in response to receiving a single inconsistent message.  With a small Imin, all those devices would choose a new t within a small window.

--
Jonathan Hui

---

From: Philip Levis <[email-masked]>
Date: Thu, 28 Jul 2011 12:59:37 -0700

> While I agree that AMI networks can have highly variable density, it's also important to consider the actual magnitudes of that range.  In this particular case, the minimum density for many urban d…

To be fair, we have tested Trickle's use in CTP in networks with a density ~300 neighbors. 

> To me, that statement conveys that an appropriate "Imin" value is dependent on density.

That implication wasn't intended. There's a reason why it says "at least."

> I guess we are talking about different scenarios.  I was addressing the case of many devices resetting their Trickle timer in response to receiving a single inconsistent message.  With a small Imin…

Ah, right. I was talking about the fact that you'll see a transmission just after Imin/2, followed by another, followed by another, until you reach k, then the rest of the interval will be mostly quiet. When looking at transmissions across a longer time scale, you'll see distinct bursts of packets where I/2 falls. This isn't necessarily good or bad, was just an observation.

Phil