Subject: [Roll] acknowledgements from parents

From: Michael Richardson <[email-masked]>
Date: Thu, 01 Apr 2010 09:19:03 -0400

I wrote:
mcr> This is a VERY HARD problem to solve, because really, if the attacker
mcr> just installed a high-gain antenna in one part of the building, a coax
mcr> cable, and another antenna in another part of the building, it's really
mcr> the same thing!  The difference is perhaps that the totally passive
mcr> system will relay packets usefully. 

In another thread, Kris Pister <[email-masked]> wrote:
Kris> This is a nice example, in that it's akin to the sort of weird RF
Kris> behavior that occurs naturally.  Nodes far apart in the network
Kris> suddenly hear each other quite well for some period of time, and
Kris> then just as mysteriously don't hear each other anymore.  RPL had
Kris> better be able to deal with this, or we're in deep trouble. 

And then Philip Levis <[email-masked]> replies:

Philip> It does not seem an undue burden to me for a node to send a
Philip> request/response that demonstrates another node's real presence
Philip> before making that node its preferred parent. Or are there
Philip> simpler mechanisms? 

I wondered if the ACK from the parent could not simply be the fact that
the parent sends an DAO to it's parent.  If that DAO is multicast rather
than unicast, and it contains a list of children nodes that it is
serving, then it serves as an ACK that the parent has seen, and accepted
the child's DAO.

This is a group ACK, piggy backed on a packet that the parent already
has to send.  As it's now multicast, it needs to actually now contain an
indication of which parent it was really for.

The downside is that many children have to wake up to hear this
multicast, but they might also have to listen for the unicast ACK.

Alternatively, if one wants to keep the DAO unicast, then the subsequent
DIO could contain that list, but this is data that otherwise does not
need to be transmitted.

- -- 
]       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: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 1 Apr 2010 16:32:16 +0200

Hi Michael:

This sort of promiscuous ack inference has been proposed in a number of
papers on the 802.11 mesh world. 
It implies a number of things like the fact that the child can listen to
a packet from Pa to Grand Pa.
This is not always the case. The Pa to Gpa link might be 802.11 while
child to Pa could be 802.15.4.
Or a different crypto could be in place. Or the time slots might be
affected in such a fashion that child is sleeping when Pa send to Grand
Pa.
In any fashion, this can hardly be generalized at L3...

Pascal

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> Michael Richardson
> Sent: Thursday, April 01, 2010 3:19 PM
> To: 'roll'
> Subject: [Roll] acknowledgements from parents
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> 
> I wrote:
> mcr> This is a VERY HARD problem to solve, because really, if the
> mcr> attacker just installed a high-gain antenna in one part of the
> mcr> building, a coax cable, and another antenna in another part of
the
> mcr> building, it's really the same thing!  The difference is perhaps
> mcr> that the totally passive system will relay packets usefully.
> 
> I wondered if the ACK from the parent could not simply be the fact
that the
> parent sends an DAO to it's parent.  If that DAO is multicast rather
than
> unicast, and it contains a list of children nodes that it is serving,
then it serves
> as an ACK that the parent has seen, and accepted the child's DAO.
> 
has to
> send.  As it's now multicast, it needs to actually now contain an
indication of
> which parent it was really for.
> 
multicast,
> but they might also have to listen for the unicast ACK.
> 
need to be
> transmitted.
>    Kyoto Plus: watch the video
> <http://www.youtube.com/watch?v=kzx1ycLXQSE>
> 	               then sign the petition.
> 
> 
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
> Comment: Finger me for keys
> 
> iQEVAwUBS7SdRYCLcPvd0N1lAQIyJwf8DmixOJJwK8SnUS/7oHocEH5SggAr46
> qO
> V+4XSIZqwqqBzW5iJSb7WD671PTIysXJ5JZc0/MKe9YmqSqhyqsO0XHyofwnC
> QlK
> yBp8yGRNSLC09yzLgyASHb1M2RWC8uGAbMESsSwZrhkZ/hNgK5IFQNlzEhUg
> zvzT
> H2QRu9bfxOJRFNpmiiR4X3UKclJFOIvJbb+lwyOivp4/L4HUXoumELpi0jprW0u4
> wNewVqfthIOfdZUkf/NAm1b9iQB2XY97NgHEPmlaavejoYECbHNU8JljEpoElZp
> x
> FZfNhDjOjQSxA+gPeYWlns7ZzqLW3Pyk43To2wpLanJaTqYbM1+dIQ==
> =J0qH
> -----END PGP SIGNATURE-----
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 1 Apr 2010 08:38:02 -0700

I agree with Pascal here.

Even if we could assume operation on the same link, another difficulty  
is dealing with the widely varying properties of multicast.  As you  
mentioned, multicast can be expensive especially in duty-cycled  
networks.  The cost of delivering a message via multicast can easily  
vary by 1-2 orders of magnitude depending on whether or not routers  
duty-cycle their radios.  Even DIO transmissions should be as slow a  
process as possible.  For deeply duty-cycled networks, I much prefer  
to rely on unicast whenever possible and multicast only for basic  
discovery.

--
Jonathan Hui

---

From: "Pete St. Pierre" <[email-masked]>
Date: Thu, 1 Apr 2010 08:40:36 -0700

Additionally, I would also be concerned about the intended parent having a greater chance of missing the RPL ACK due to using multicast over unicast.  For some L2s (like 15.4), unicast traffic benefits from an L2 ACK, which is not present when using multicast (or broadcast in the case of 15.4).

I'm hesitant to optimize this if it lowers reliability of the message getting through to the intended recipient.
...Pete

--
Pete St. Pierre
[email-masked]
Sun Labs
Oracle 
16 Network Circle
Menlo Park, CA 94025

---

From: Michael Richardson <[email-masked]>
Date: Thu, 01 Apr 2010 15:09:31 -0400

>>>>> "Pascal" == Pascal Thubert <(pthubert)" <[email-masked]>> writes:
    Pascal> This sort of promiscuous ack inference has been proposed in
    Pascal> a number of papers on the 802.11 mesh world. It implies a
    Pascal> number of things like the fact that the child can listen to
    Pascal> a packet from Pa to Grand Pa.  This is not always the
    Pascal> case. The Pa to Gpa link might be 802.11 while child to Pa
    Pascal> could be 802.15.4.  Or a different crypto could be in
    Pascal> place. Or the time slots might be affected in such a fashion
    Pascal> that child is sleeping when Pa send to Grand Pa.  In any
    Pascal> fashion, this can hardly be generalized at L3...

So the alternative is what?
In the case you mention, where the links are the not the same, then I'd
say just gratuitously send the multicast on both networks.

Isn't that still cheaper than sending individual ACKs?
Do you ACK every DAO?   Or just the first?  

The alternative seems to Unicast ACK of every single message, right?
Isn't that at least as costly to the intermediate node as a link-local
multicast? 

It's true --- the child might be asleep.  Why should we think the child
is awake to get the unicast ACK?

Hey --- the parent might be asleep when the child unicasts it's DAO!

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 1 Apr 2010 19:09:49 -0700

> Isn't that at least as costly to the intermediate node as a link-local

This really depends on the properties of the link layer.  A link-local  
multicast really maps to a broadcast operation for most low-power  
radio networks.  For links that idle-listen all the time, broadcast is  
no more expensive than a unicast but does lack a synchronous  
acknowledgement as Pete pointed out.  For duty-cycled networks that  
attempt to eliminate idle listening, supporting broadcast either  
requires (i) all nodes to be on at the same time and scheduling a  
broadcast slot or (ii) sending a long preamble to wakeup all  
neighboring nodes for a data packet.  For these duty-cycled networks,  
both options are *very* costly and should be used as sparingly as  
possible.  Hence the use of Trickle within RPL.

--
Jonathan Hui