Subject: [Roll] implementation questions: sending DIOs for multiple DODAGs

From: Michael Richardson <[email-masked]>
Date: Wed, 25 Aug 2010 20:25:27 -0400

An RPL node which is participating in multiple DODAGs will have multiple
Trickle timers.   It will send out a DIO for each DODAG if necessary.

However, it seems that there is some advantage to transmitting multiple
packets at the same time --- you can be more sleepy, and it helps other
nodes be more sleepy.

As such it seems that whenever possible, if a node already has picked a
value "t" which is consistent with multiple DODAG's [I/2,I) ranges, that
it should use the same value t across all DODAGs.

For a machine with multiple interfaces (e.g. multiple radios on
different frequencies, or even different media types), that it should in
fact keep a DODAG Trickle Timer *per disjoint interface*.

Does this make sense?

-- 
]       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, 25 Aug 2010 19:04:26 -0700

> fact keep a DODAG Trickle Timer *per disjoint interface*.

Just to be sure -- you just suggesting the optimization that when a node transmits a DIO, it checks if the current time falls within the intervals of any of its other DODAG timers, and if so, assumes t is that value (still applies the suppression invariant)? One issue this raises is that if some nodes are members of more DODAGs than others, they will transmit more often: they're basically selecting the minimum t across their intervals.

The operating assumption here seems to be that sending multiple multicast messages back-to-back is less expensive than spacing them out over time. This isn't always true (depends on the link layer).

Phil

---

From: Michael Richardson <[email-masked]>
Date: Wed, 25 Aug 2010 22:18:46 -0400

>>>>> "Philip" == Philip Levis <[email-masked]> writes:
    >> An RPL node which is participating in multiple DODAGs will have
    >> multiple Trickle timers.  It will send out a DIO for each DODAG
    >> if necessary.
    >> 
    >> However, it seems that there is some advantage to transmitting
    >> multiple packets at the same time --- you can be more sleepy, and
    >> it helps other nodes be more sleepy.
    >> 
    >> As such it seems that whenever possible, if a node already has
    >> picked a value "t" which is consistent with multiple DODAG's
    >> [I/2,I) ranges, that it should use the same value t across all
    >> DODAGs.
    >> 
    >> different frequencies, or even different media types), that it
    >> should in fact keep a DODAG Trickle Timer *per disjoint
    >> interface*.
    >> 
    >> Does this make sense?

    Philip> Just to be sure -- you just suggesting the optimization that
    Philip> when a node transmits a DIO, it checks if the current time
    Philip> falls within the intervals of any of its other DODAG timers,
    Philip> and if so, assumes t is that value (still applies the
    Philip> suppression invariant)? One issue this raises is that if
    Philip> some nodes are members of more DODAGs than others, they will
    Philip> transmit more often: they're basically selecting the minimum
    Philip> t across their intervals.

That wasn't how I was thinking of implementing it.

Rather, instead of always picking a "random" t, I'd look at all the
existing t values for all the DODAGs that I'm a member of, and if one of
them satisfies [I/2,I), then I use that.  If not, then I pick it
randomly as before. 

    Philip> The operating assumption here seems to be that sending
    Philip> multiple multicast messages back-to-back is less expensive
    Philip> than spacing them out over time. This isn't always true
    Philip> (depends on the link layer).

yes, that's my assumption. 
It's certainly cheaper in terms of CPU power budget, as when you wake
up, it's best to get rid of as much work as possible and then go back to
sleep.  If it's not true of some link layers, I'd like to understand
this better.

---

From: Philip Levis <[email-masked]>
Date: Wed, 25 Aug 2010 19:56:26 -0700

> sleep.  If it's not true of some link layers, I'd like to understand

In most LLN devices I've seen/used/measured, under reasonable  
workloads, CPU energy costs are negligible. Sure, you can burn CPU  
energy by doing AES in software, but the cost of an interrupt is  
really insignificant. The dominant cost is networking.

Phil

---

From: Michael Richardson <[email-masked]>
Date: Thu, 26 Aug 2010 09:04:07 -0400

>>>>> "Michael" == Michael Richardson <[email-masked]> writes:

I wanted to repeat this (second) question.

---

From: Michael Richardson <[email-masked]>
Date: Thu, 26 Aug 2010 09:11:55 -0400

>> yes, that's my assumption.  It's certainly cheaper in terms of
    >> CPU power budget, as when you wake up, it's best to get rid of as
    >> much work as possible and then go back to sleep.  If it's not
    >> true of some link layers, I'd like to understand this better.

    Philip> In most LLN devices I've seen/used/measured, under
    Philip> reasonable workloads, CPU energy costs are negligible. Sure,
    Philip> you can burn CPU energy by doing AES in software, but the
    Philip> cost of an interrupt is really insignificant. The dominant
    Philip> cost is networking.

I'm not an expert, I'm going on heresay, mostly from the Linux and
Android discussions about how to write applications that do not drain
the battery.  

My reading is that this is not the experience on smartphones and
laptops: waking up the CPU hurts a lot.  Yes, Tx power certainly costs
--- and you want to reduce it, but there is also some wake up/shutdown
cost on the transmitter too.   

There were some people looking at whether the network stack on laptops 
should synchronize multiple TCP connections better, such that if a
message needs to go out, it happens while the system is awake, rather
than causing another resume from sleepy state.

So, let me ask the question a different way:
    is there a DOWNSIDE to sending out DIOs for different DODAGs at the
    same time?
    Is it something that the specification should discourage?

---

From: "Colin O'Flynn" <[email-masked]>
Date: Thu, 26 Aug 2010 15:37:46 +0100

Hello,

Philip I think you are absolutely correct here for embedded devices that RPL
is primarily concerned about. Waking up the CPU isn't a big issue. 

Larger devices (Linux/etc) are completely different in terms of both
hardware and software architecture. But the main concern should be the tiny
nodes IMHO.

Unless you are using synchronization between devices (which so far I don't
see happening in real networks), you have no option but to do "low power
listening" to receive the async transmission from other nodes. In this mode
you wake up frequently, switch on the transceiver, and listen for a brief
period. Since you've already waken up the CPU & radio, doing a radio
transmission at that time only "costs" you the extra time to do the actual
transmission. Thus probably most people would just synchronize DIO
transmissions to the nearest time the radio will be active anyway. This
could be every 10mS or more frequently.

A quick "reality check" on the actual costs of waking up:

Consider the time it takes to transmit a single message: 100 bytes at 250
kbits/second is 3.2 mS. That ignores time waiting for ACK, etc etc. At 16
MIPS you can do 51200 instructions. A micro such as the ATMega128RFA1 can
wake up in 6 cycles from standby, and 210 from total power down. 

The radio in that micro takes a little longer though: typically going from
sleep to transmitting takes in the vicinity of 0.5 mS (equiv to 8000 cycles
per my last example). Still, compared to actually doing the transmission
this isn't *that* long.

>    is there a DOWNSIDE to sending out DIOs for different DODAGs at the

There is situations where there could be. For example your power source
doesn't have low enough impedance to deliver the current to actually send a
bunch of data back-to-back. With coin cell batteries for example you run
into this problem.

But I'd say it really doesn't matter and RPL shouldn't try to specify if you
should or shouldn't do this optimization. It's a case of implementation
optimizations specific to your link-layer, processor, and network
architecture.

Regards,

  -Colin

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Michael Richardson
Sent: August 26, 2010 2:12 PM
To: Philip Levis
Cc: [email-masked]
Subject: Re: [Roll] implementation questions: sending DIOs for multiple
DODAGs

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

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

---

From: Philip Levis <[email-masked]>
Date: Thu, 26 Aug 2010 09:43:11 -0700

> cost on the transmitter too.

Sure, but that's not really the device class we're interested in. The issue you run into in CPUs (rather than MCUs) is typically wakeup latency, combined with a high power draw. I'm not sure why you'd have a laptop always in a deep sleep mode, running RPL. As for phones, the CPU is expensive yes, this is why there are separate wakeup circuits. Also, the energy behavior and profiles of mobile phone technologies is a lot different than LLNs: single-hop networks with centralized coordinators, etc.

Regardless, if the energy cost is on the wakeup at time t, the reception in interval I, or the transmission at time t, the key savings comes from how I increases. The CPU is going to wake up on packet reception, and probably spend more cycles than on a timer. Given all of the other things a RPL node may have to do, optimizing the number of interrupts it handles for time t is unlikely to be significant. I'd be really interested to see an application profile where an interrupt every few minutes/hours is a limiting energy cost.

>    is there a DOWNSIDE to sending out DIOs for different DODAGs at the

Yes -- it unevenly balances load based on the number of DODAGs a node is a member of. But I think this is the wrong way to go about this discussion: the onus should be to, through experimentation, *demonstrate* there isn't a downside. There are too many examples in wireless of thought experiments and convincing arguments being wrong.

>    Is it something that the specification should discourage?

Yes. The Trickle draft is actually explicit on this. The basic answer is that Trickle is a very carefully balanced algorithm that's been tested and evaluated for 5 or so years now. It's possible that there are ways to improve it, but the bar to demonstrate something is an improvement is an experimental demonstration, not a thought experiment.

Phil

---

From: Michael Richardson <[email-masked]>
Date: Thu, 26 Aug 2010 13:21:46 -0400

>>>>> "Philip" == Philip Levis <[email-masked]> writes:
    Philip> Regardless, if the energy cost is on the wakeup at time t,
    Philip> the reception in interval I, or the transmission at time t,
    Philip> the key savings comes from how I increases. The CPU is going

I agree.

    >> So, let me ask the question a different way: is there a DOWNSIDE
    >> to sending out DIOs for different DODAGs at the same time?

    Philip> Yes -- it unevenly balances load based on the number of
    Philip> DODAGs a node is a member of. But I think this is the wrong
    Philip> way to go about this discussion: the onus should be to,
    Philip> through experimentation, *demonstrate* there isn't a
    Philip> downside. There are too many examples in wireless of thought
    Philip> experiments and convincing arguments being wrong.

I accept this view.

    >> Is it something that the specification should discourage?

    Philip> Yes. The Trickle draft is actually explicit on this. The
    Philip> basic answer is that Trickle is a very carefully balanced
    Philip> algorithm that's been tested and evaluated for 5 or so years
    Philip> now. It's possible that there are ways to improve it, but
    Philip> the bar to demonstrate something is an improvement is an
    Philip> experimental demonstration, not a thought experiment.

I did not see anything in the Trickle draft that dealt with the question
of a node that participates in multiple Trickle timers.  It dealt with a
single instance of Trickle.

---

From: Michael Richardson <[email-masked]>
Date: Thu, 26 Aug 2010 13:26:05 -0400

>>>>> "Colin" == Colin O'Flynn <[email-masked]> writes:
    Colin> Hello,

Thanks for the well thought our reply.

    >> is there a DOWNSIDE to sending out DIOs for different DODAGs at
    >> the same time?

    Colin> There is situations where there could be. For example your
    Colin> power source doesn't have low enough impedance to deliver the
    Colin> current to actually send a bunch of data back-to-back. With
    Colin> coin cell batteries for example you run into this problem.

I agree that this is a problem for the transmitter, and the transmitter
needs to know how much (well, what intensity...) work it can do before
it needs to sleep again.

I should have asked:

    is there a DOWNSIDE for the receivers or the network stability
    if a sender who is a member of multiple DODAGs, decides to send out
    the DIOs for these different DODAGs at the same time?

---

From: Philip Levis <[email-masked]>
Date: Thu, 26 Aug 2010 13:19:09 -0700

> single instance of Trickle.

Section 6.7.

For the issues of multiple Trickle timers, DIP and DHV are two  
protocols that try to address this. They assume a specific  
consistency model, though, version numbers. I don't know of any work  
which has examined how to aggregate timers for routing protocol  
consistency.

Phil

---

From: Kris Pister <[email-masked]>
Date: Thu, 26 Aug 2010 17:58:07 -0700

On 8/26/2010 7:37 AM, Colin O'Flynn wrote:
> see happening in real networks),
Colin - if you live near a refinery, you can see a real 15.4 network 
running with mean time error across the entire network of less than 
0.1ms .  There aren't many refineries left that aren't deploying this 
technology (IEC62591, soon to be 802.15.4E).  If you're in SF or LA, you 
might get a parking ticket because of such a synchronized network (sorry 
- it's evil, but it's a living).  There's even open source code that 
runs on Atmel HW that you can use.

Your battery impedance argument is a good one, as are Phil's, both 
pushing to more spread out, or at least randomized, transmissions.  Phil 
- I agree with your anti-"thought experiment" bias.  At the same time 
though, we're combining a lot of good tested ideas into one largely 
untested standard at this point.  We're going to learn a lot, and some 
trickle-truths may turn out to be different in RPL than they are 
elsewhere.  So I lean toward Colin's final conclusion below: leave it to 
the individual implementations to optimize as they see fit.

ksjp
> you have no option but to do "low power
> period. Since you've already waken up the CPU&  radio, doing a radio

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 26 Aug 2010 21:08:15 -0700

On Aug 26, 2010, at 5:58 PM, Kris Pister wrote:

> Colin - if you live near a refinery, you can see a real 15.4 network running with mean time error across the entire network of less than 0.1ms .  There aren't many refineries left that aren't deploying this technology (IEC62591, soon to be 802.15.4E).  If you're in SF or LA, you might get a parking ticket because of such a synchronized network (sorry - it's evil, but it's a living).  There's even open source code that runs on Atmel HW that you can use.

I think it's fair to say that for most readily available radios today, any sizable network with reasonable traffic loads must use some form of synchronization for routers to last years on modest batteries.  Not to mention that regulations may require networks to utilize frequency hopping.

> Your battery impedance argument is a good one, as are Phil's, both pushing to more spread out, or at least randomized, transmissions.  Phil - I agree with your anti-"thought experiment" bias.  At the same time though, we're combining a lot of good tested ideas into one largely untested standard at this point.  We're going to learn a lot, and some trickle-truths may turn out to be different in RPL than they are elsewhere.  So I lean toward Colin's final conclusion below: leave it to the individual implementations to optimize as they see fit.

In general, I'm a big supporter of implementation-specific optimizations for a particular link-layer.  But I'd echo Phil's warning that you also don't want to change the behavior of an algorithm.  Trickle was designed to operate in isolation - combining Trickle timers in the abstract can be problematic.  The case where all nodes combine Trickle timers in the same way is tantamount to have a single Trickle timer, so that is not an issue.  But when different nodes combine Trickle timers in different ways, then you can run into issues with uneven transmission load, suppression, etc.

--
Jonathan Hui

---

From: "Colin O'Flynn" <[email-masked]>
Date: Fri, 27 Aug 2010 08:30:49 +0100

Hi Jonathan & Kris,

Alright, perhaps I was far too dismissive of synchronization ;-) But it
would be the same point as low power listening: the devices won't wake up
specifically to send a DIO, it will send the DIO when it's next awake. For
synchronization you would have to wait until the next sync cycle anyway for
anyone to hear you.

I do agree that any optimization shouldn't change the base design of
Trickle. 

Would it make sense to say that an implementation must specify the maximum
jitter allowed? Something along the lines of when Trickle says you must
transmit at time X, it means time X +/- Y. 

I have minimal experience with Trickle, so would be interested in learning
how much would be "allowed". Such a recommendation would put an upper limit
on any optimizations. This limit would also affect devices which do need to
sleep by effectively limiting their sleep cycles though, so not sure if it's
an overall good idea.

Regards,

  -Colin

-----Original Message-----
From: Jonathan Hui [mailto:[email-masked]] 
Sent: August 27, 2010 5:08 AM
To: Kris Pister
Cc: Colin O'Flynn; 'Philip Levis'; [email-masked]
Subject: Re: [Roll] implementation questions: sending DIOs for multiple
DODAGs

> Colin - if you live near a refinery, you can see a real 15.4 network
running with mean time error across the entire network of less than 0.1ms .
There aren't many refineries left that aren't deploying this technology
(IEC62591, soon to be 802.15.4E).  If you're in SF or LA, you might get a
parking ticket because of such a synchronized network (sorry - it's evil,
but it's a living).  There's even open source code that runs on Atmel HW
that you can use.

I think it's fair to say that for most readily available radios today, any
sizable network with reasonable traffic loads must use some form of
synchronization for routers to last years on modest batteries.  Not to
mention that regulations may require networks to utilize frequency hopping.

> Your battery impedance argument is a good one, as are Phil's, both pushing
to more spread out, or at least randomized, transmissions.  Phil - I agree
with your anti-"thought experiment" bias.  At the same time though, we're
combining a lot of good tested ideas into one largely untested standard at
this point.  We're going to learn a lot, and some trickle-truths may turn
out to be different in RPL than they are elsewhere.  So I lean toward
Colin's final conclusion below: leave it to the individual implementations
to optimize as they see fit.

In general, I'm a big supporter of implementation-specific optimizations for
a particular link-layer.  But I'd echo Phil's warning that you also don't
want to change the behavior of an algorithm.  Trickle was designed to
operate in isolation - combining Trickle timers in the abstract can be
problematic.  The case where all nodes combine Trickle timers in the same
way is tantamount to have a single Trickle timer, so that is not an issue.
But when different nodes combine Trickle timers in different ways, then you
can run into issues with uneven transmission load, suppression, etc.

--
Jonathan Hui

---

From: Michael Richardson <[email-masked]>
Date: Fri, 27 Aug 2010 09:05:36 -0400

>>>>> "Colin" == Colin O'Flynn <[email-masked]> writes:
    Colin> Alright, perhaps I was far too dismissive of synchronization
    Colin> ;-) But it would be the same point as low power listening:
    Colin> the devices won't wake up specifically to send a DIO, it will
    Colin> send the DIO when it's next awake. For synchronization you
    Colin> would have to wait until the next sync cycle anyway for
    Colin> anyone to hear you.

So, my understanding is that some link layers have a network wide
synchronization so that receivers wake up together so that they can hear
the transmissions?

That this cycle really quantizes the values of 't' that can be picked?

---

From: Philip Levis <[email-masked]>
Date: Fri, 27 Aug 2010 09:52:39 -0700

> transmit at time X, it means time X +/- Y. 

What purpose would this serve?

> sleep by effectively limiting their sleep cycles though, so not sure if it's

I don't think it matters. There are lots of reasons that a node might not actually be able to transmit at time t; there is MAC backoff, after all. As long as most Trickle intervals are much larger than the latency the link layer introduces, it won't really disrupt the algorithm. Since Trickle spends most of its time at large intervals (if the network is actually in low power operation), I don't think this is a big deal.

It does mean that, at very small intervals, transmitter selection may be affected by link layer latency. This could lead to uneven transmission loads. But since these intervals are comparatively rare, and this effect is generally less pronounced than the application-load variations caused by resets, I'm not sure how significant it is. Seems like a good thing to measure in a real system, so we can better understand the problem.

Phil

---

From: "Colin O'Flynn" <[email-masked]>
Date: Fri, 27 Aug 2010 18:10:54 +0100

Hi Phil,

> I don't think it matters.

Ah alright. I was trying to address the original question about
synchronizing multiple DIOs. 

Essentially say how far an implementation can push the Trickle timer w/o
"breaking" anything. Thus if it's preferable in a Linux implementation to
try and aggregate sending DIOs, the implementer knows they can do this as
long as you don't exceed the allowed jitter.

Regards,

  -Colin

-----Original Message-----
From: Philip Levis [mailto:[email-masked]] 
Sent: August 27, 2010 5:53 PM
To: Colin O'Flynn
Cc: 'Jonathan Hui'; 'Kris Pister'; [email-masked]
Subject: Re: [Roll] implementation questions: sending DIOs for multiple
DODAGs

> sleep by effectively limiting their sleep cycles though, so not sure if
it's

I don't think it matters. There are lots of reasons that a node might not
actually be able to transmit at time t; there is MAC backoff, after all. As
long as most Trickle intervals are much larger than the latency the link
layer introduces, it won't really disrupt the algorithm. Since Trickle
spends most of its time at large intervals (if the network is actually in
low power operation), I don't think this is a big deal.

It does mean that, at very small intervals, transmitter selection may be
affected by link layer latency. This could lead to uneven transmission
loads. But since these intervals are comparatively rare, and this effect is
generally less pronounced than the application-load variations caused by
resets, I'm not sure how significant it is. Seems like a good thing to
measure in a real system, so we can better understand the problem.

Phil

---

From: Philip Levis <[email-masked]>
Date: Fri, 27 Aug 2010 11:51:49 -0700

> long as you don't exceed the allowed jitter.

One well-understood and tested approach to aggregate Trickle  
transmissions is what DIP[1] and DHV[2] do. If you have two  
independent Trickle timers A and B which have the same interval I,  
then you can just select a single time t for both of them and send an  
aggregate at that t. Because it's a single value drawn from the  
uniform distribution, it doesn't suffer from the min() problem of on- 
the-fly aggregation. If A and B have different intervals then you  
treat them separately.

The one minor issue is that aggregating A and B in this way can  
induce a phase shift in the intervals; but given that Trickle is  
robust to in-phase and out-of-phase timers, this doesn't tend to  
cause a big problem.

Does that make sense?

Phil

[1] Lin, K. and P. Levis, "Data Discovery and Dissemination with  
DIP", Proceedings of the 7th international conference on Information  
processing in sensor networks IPSN 2008, April 2008.

[2] Dang, T., Bulusu, N., Feng, W., and S. Park, "DHV: A Code  
Consistency Maintenance Protocol for Multi-hop Wireless Networks",  
Wireless Sensor Networks: 6th European Conference Proceedings EWSN  
2009 Cork, February 2009.

---

From: Kris Pister <[email-masked]>
Date: Mon, 30 Aug 2010 11:48:05 -0700

On 8/27/2010 6:05 AM, Michael Richardson wrote:
> synchronization so that receivers wake up together so that they can hear the transmissions?
Not quite.  Having everyone wake up at the same time is (usually) 
extremely inefficient.  Those networks that have a "sync cycle" approach 
do not scale well.  What is being standardized in 15.4E (through several 
different mechanisms) is the ability to have pairwise synchronization, 
so when node A sends unicast to node B, only A and B are awake and on 
that channel at that time.  This is very efficient for, e.g., MP2P 
traffic up the DODAG.  For traffic down the DODAG, you may or may not 
want to have all of your children listening to a broadcast slot.  You 
may also want to have all nodes listening infrequently to a 
neighbor-discovery slot.
There is certainly some overhead for this approach, but as Jonathan 
pointed out, the benefits are substantial.
> That this cycle really quantizes the values of 't' that can be picked?
Yes, but at very fine granularity - in the range from hundreds of 
milliseconds down to single-digit milliseconds.  Much finer than 
(typical) trickle values.

ksjp