Subject: Re: [Roll] FW: New Version Notification for draft-thubert-roll-fundamentals-01

From: Omprakash Gnawali <[email-masked]>
Date: Fri, 8 May 2009 17:52:02 -0700

On Tue, Apr 14, 2009 at 4:52 PM, Philip Levis <[email-masked]> wrote:
>
> On Apr 13, 2009, at 3:04 AM, Richard Kelsey wrote:
>
>>  Date: Sat, 11 Apr 2009 10:07:14 +0300
>>  From: Zach Shelby <[email-masked]>
>>
>>  Richard Kelsey wrote:
>>>
>>>  From: Philip Levis <[email-masked]>
>>>  Date: Fri, 10 Apr 2009 06:52:04 -0700
>>>
>>>  On Apr 9, 2009, at 1:59 AM, Pascal Thubert (pthubert) wrote:
>>>
>>>> Basically, since we have a depth, we have feasible parents (of
>>>> lesser depth) and siblings (of same depth). The draft suggests that
>>>> we can select any parent to forward on a per packet basis using the
>>>> best metric or more advanced load balancing functionality; if that
>>>> fails then we can use a sibling with some basic loop avoidance like
>>>> poison return or more advanced path vector (for hydrophiles).
>>>
>>>  Here's a URL to a paper that describes one way to solve this problem,
>>>  using the techniques I mentioned a few weeks ago and touched on in my
>>>  talk in SF:
>>>
>>>  http://sing.stanford.edu/pubs/ctp.pdf
>>>
>>> Good stuff.  Relating this back to the Routing Fundamentals
>>> draft, it seems clear that ROLL will most likely use trees
>>> for at least some routing, and while Router Advertisements
>>> can be used to build trees, it will be good if tree
>>> building and/or maintenance can be performed independently
>>> of Router Advertisements.  They add too much overhead
>>> to make it easy to react quickly to changing conditions.
>>
>>  Don't think of router advertisements as overhead - as we
>>  are working with IP networks you will always have RAs as
>>  they are an integral part of network bootstrapping and
>>  maintenance (Neighbor Discovery).  As you have RAs
>>  anyways, you might as well piggyback some tree
>>  information.
>>
>> To be pedantic, they aren't application payload, so they are
>> overhead.  That wasn't the point I was making, though.
>
> Even if it isn't the point you were trying to make, I'd agree with it. :)
> It's hard to say that a routing protocol is efficient if it sends 1000 RAs
> for every data packet. At the most abstract level, a protocol's overhead is
> (total bytes - data bytes)/data bytes. That being said, the presence of
> energy as a critical metric means that there can and are situations where
> higher overhead can lead to greater efficiency. For example, a header field
> that gives some sort of rendezvous timing as in Jonathan's IP stack.
>
>> The piggybacking only works if there happens to be an RA
>> going out around the time that new tree information needs to
>> be sent.  Am I missing a connection between the two that
>> makes this likely?  The Collection Tree Protocol mentioned
>> above reacts to topology changes within a second or two.
>
> Even faster -- one experiment we did on this saw 10-15 packet times, which
> was 200-300ms. It turns out that, for 802.15.4 at least, in tough
> environments links tend to have a coherence time around 500ms, so you'd like
> to be able to either react much faster or much slower than that. Faster so
> you don't keep on hammering a bad link, or slower so that the next
> transmission is a random coin toss.
>
>
>>  I
>> don't know if that low a response time is necessary, but it
>> does seem clear that tree topology will sometimes be
>> changing much faster than the data in the RAs.  If new tree
>> information needs to be sent, but new RA information does
>> not, then the RA data is overhead.
>
> I agree with this: it's the exact problem that adaptive beaconing tries to
> solve. Any periodic RA mechanism introduces a tough tradeoff: beacon faster
> for fast adaptation but high cost, or beacon slower for efficiency but slow
> adaptation.  Hence the point of borrowing and extending Trickle -- send just
> enough RAs for nodes to discover each other and verify that the tree is
> still consistent. Data path validation allows the protocol to verify the
> tree's consistency without introducing additional (RA) overhead.
>
>
>> I am not suggesting that we not piggyback tree information
>> on RAs, just that it would be good to also be able to
>> piggyback it on other messages or send it independently.
>
> The design question here is *what* information to piggyback. One interesting
> way that the paper I sent out differs from Jonathan's IP stack is his stack
> includes hop count in data packets (Section 8.1.4 of the SenSys 2008 paper).
> From an academic standpoint, it would be an interesting evaluation to see
> whether the cost of this field is less than the cost of false positives on
> CTP's loop detection (the case where a node's ETX goes up but its children
> don't know yet, so it thinks there might be a loop). I say it's academic
> because my guess is that it's a comparatively small difference either way,
> compared to other, more important issues.
>
> Om -- this might be a nice experiment to look at from the traces, just
> compute how often CTP beacon resets are false positives on loop detection.

I did a quick analysis of logs from two experiments - one on channel
16 and one on 26 on a 91-node network. In general, a large number of
detections are false positives -- thats a good thing. A node can
generate a number of loop detection events after a single loop is
detected because there might be a stream of incoming packets failing
the consistency check while topology maintenance is triggered.

Here are graphs for ch 16 (98% delivery ratio, 4k seconds):
http://enl.usc.edu/~om_p/net2/ch16-loops1.gif
(almost all nodes report loop detection events, max of 460 detections
in a single node, gap between green and blue shows beacon timer resets
due to true loops [node saw the same pkt twice])

http://enl.usc.edu/~om_p/net2/ch16-loops2.gif
(significant fraction are false detections, most beacons are sent due
to false detections)

Here are graphs for ch 26 (99.997%, 10.8k seconds):
http://enl.usc.edu/~om_p/net2/ch26-loops1.gif
(shows 4 nodes reported loop detection events, max of 6 detection in a
single node)

http://enl.usc.edu/~om_p/net2/ch26-loops2.gif
(all detections, loops -- false positives)

- om_p