Subject: [6lowpan] Fundamental assumptions of 6lowpan-nd-06: (1) Address resolution is a waste of energy

From: Carsten Bormann <[email-masked]>
Date: Wed, 14 Oct 2009 00:30:57 +0200

I'll try to untangle this thread.
I think we need to revisit the Dublin assumptions, one by one.
So here is assumption number one:

(1) Address resolution is a waste of energy

IPv4 needed address resolution for Ethernet to map a 32-bit address  
space, n<32 bits of which were a host number within a network, to a 48- 
bit MAC address.  IPv6 continued to follow that model for Ethernet  
even if that strong need no longer was there, with a likely default  
mapping but a possibility for manual assignment (or DHCP), so address  
resolution (AR) was still needed.

In 6lowpans, the congruence of MAC and IP addresses is a prerequisite  
to efficient header compression.

Also, we actually have a way to assign *MAC addresses* the way DHCP  
did this for *IP addresses*: 16-bit addresses are not owned by a  
device but can be assigned (using NR/NC in 6lowpan-nd-06), so if there  
is a need to assign a functional IP address to a device this can be  
done by assigning it the equivalent 16-bit MAC address.

In 6lowpans, address resolution requires the establishment (using  
energy-wasting packets) and maintenance (using precious memory) of  
state that no longer serves a useful purpose.
Using anything but the default mapping causes additional header  
overhead, wasting energy.
The need for assigned addresses can easily be covered by assigning 16- 
bit addresses.

Hence, the decision was to get rid of address resolution and hardwire  
the (IID part of the) mapping.

I would like to hear arguments why the above reasoning was incorrect.

(Tomorrow I will follow up with another assumption, but please let's  
beat this horse for today.)

Gruesse, Carsten

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 13 Oct 2009 16:00:30 -0700

On Oct 13, 2009, at 3:30 PM, Carsten Bormann wrote:

> space, n<32 bits of which were a host number within a network, to a  
> 48-bit MAC address.  IPv6 continued to follow that model for  
> Ethernet even if that strong need no longer was there, with a likely  
> default mapping but a possibility for manual assignment (or DHCP),  
> so address resolution (AR) was still needed.
>
> In 6lowpans, the congruence of MAC and IP addresses is a  
> prerequisite to efficient header compression.
>
> device but can be assigned (using NR/NC in 6lowpan-nd-06), so if  
> there is a need to assign a functional IP address to a device this  
> can be done by assigning it the equivalent 16-bit MAC address.
>
> The need for assigned addresses can easily be covered by assigning  
> 16-bit addresses.
>
> Hence, the decision was to get rid of address resolution and  
> hardwire the (IID part of the) mapping.
>

Being a part of the discussion in Dublin, I wouldn't say that the  
above reasoning was incorrect, just incomplete in thinking through the  
architectural implications.  Playing devil's advocate here, some  
points on the flip side:

- This limits IIDs to one 64-bit and one 16-bit value at a time, is  
this OK?  It limits the number of addresses.  It limits the ability to  
assign multiple addresses from different pools possibly from different  
administrative domains.  It limits games one might play with  
addressing for various purposes.
- The improvement in header compression is limited to the first and  
last IP hops.  Assuming 14-byte prefix is compressible, the added cost  
is 2 bytes for each address (a total of 4 bytes) overhead when both  
IIDs do not map directly to their respective link addresses.  When  
communicating outside the network, one of the addresses is either  
always compressible or not, so the compression argument is even less.

I agree with the primary concern about energy of sending extra packets  
to resolve and address.  This is not a code complexity issue.  I would  
prefer a mechanism to know if a link address can be computed from an  
IID, if not then perform AR.  But I'm not sure there is a feasible way  
to get there.  There are ways to reduce the frequency by including  
LLAOs wherever possible, but doesn't eliminate the need for NS/NA in  
the most general case.

--
Jonathan Hui

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 14 Oct 2009 11:14:22 +0200

Hi Jonathan and Carsten:

I concur with the Dublin agreement that RFC 4861 based address
resolution is not desirable.

Looking back, we used till 02 to use the white board for address
resolution and redirect.
 
But as we generalized the protocol to any mesh under technology, we
found that the whiteboard could not necessarily help there:
* If the mesh is only partial, the white board cannot know if there is a
direct path between the 2.
* If the mesh is based on virtual circuits, then the white board cannot
know the OD of the virtual circuit between the 2 even if such a circuit
exists.
So we stopped using address resolution and redirects through the white
board.

What beats me is your wording that we depend on the encoding of the L2
address in the L3 address.
And to be honest there's some text added in 03 and still present to this
day that seems to imply this:

"
1.1. Goals & Assumptions
...
      o Link-local IPv6 addresses are derived from a unique identifier
      (e.g.  EUI-64).

      o There is a direct mapping between the IPv6 address IID and the
      link-layer address (as in e.g.  [RFC4944]), thus address
      resolution is not required.
"

"
   Address Resolution:  Not performed as there is a direct mapping
      between the IID and the link-layer address.
"

This is not correct. do agree that IF there is such a thing as this tie
between the LLA and the IPv6 IID then there can be local optimizations,
just like there is a way to do stateless compression. But we do not need
this in general and the spec works without it. And BTW, the new HC is
designed to enable stateful compression and thus works with any address,
whether it is formed from MAC or not.

The real reason for which we do not need resolution in the LoWPAN is
that we can always go through the router. No NUD but ICMP unreachable.
No redirect. This makes full sense in route-over and it still enables
connectivity in mesh-under via the edge router.

This might lead to non-optimal path in the latter case, but in practice
there is no way to generalize mesh-under, that's just too diverse. Some
are proactive whereas others can and will create a path on-demand. Some
are fully meshed whereas others are only partial (which is probably more
economical and thus favored in sensor space). And a mesh-under coverage
does not need to match the group of nodes attached to a given edge
router.

At the end of the day, if there is or there can be a mesh-under path
between two end-nodes that is better than the path via the routers, then
an additional mesh dependent mechanism must be put in place that is out
of scope for 6LoWPAN-ND. Examples of such additional mechanisms can be
found in Classical IP over ATM (NHRP) and Inverse ND. 

We could have a small additional draft that would describe the use of
the white board for the purpose of address resolution in 802.15.4 from
version prior to 03 of this draft, and the optimizations that can derive
from the LLA/IID tying assumptions if they are enforced in a given
deployment. But that should not be in the main 6LoWPAN ND draft that
aims at the larger problem of ND over non-transitive links.

If you agree with this reasoning then we should really rework the text
above. The assumptions should go away. The second excerpt should become:

"
   Address Resolution:  Not performed. Nodes only forward via routers
with which they have a NR/NC relationship.
  	                  Any optimization for direct host to host
connectivity is out of scope.
"

What do you think?

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On
Behalf Of Jonathan Hui
>Sent: mercredi 14 octobre 2009 01:01
>To: Carsten Bormann
>Cc: 6lowpan
>Subject: Re: [6lowpan] Fundamental assumptions of 6lowpan-nd-06: (1)
Addressresolution is a waste of energy
>_______________________________________________
>6lowpan mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/6lowpan

---

From: Zach Shelby <[email-masked]>
Date: Wed, 14 Oct 2009 14:09:13 +0300

> connectivity is out of scope.

Right. 6lowpan-nd-06 is already saying this, but some of the  
assumptions do need to be cleaned up (although they had been relaxed).  
In Stockholm we relaxed the IID-MAC mapping, and included the  
capability to deal with address resolution through the host-router  
relationship set up by NR/NC. As Jonathan pointed out, that AR  
capability is pretty limited.

What you are proposing is that we don't do AR, and only optimize for  
the host-router relationship. Of course host-to-host connectivity is  
not prevented, you can contact any node within radio range using its  
link-local address.

[Editor hat off]
Personally, I agree with your approach, this is all that is needed in  
real applications I have seen so far. I also agree any more general AR  
mechanisms should be left for more general future work. This is  
optimization at its best - if you don't need it - leave it out.
[Editor hat on]

The other approach people are suggesting is that you do need AR  
between all nodes within radio range and that the NR/NC AR approach is  
not sufficient.

Now this should be brought back to Carsten's question of the day - Do  
we need AR at all, and if so to what extent? Once the WG agrees on  
that goal - I am sure we can figure out a way to achieve it.

- Zach

-- 
http://www.sensinode.com
http://zachshelby.org - My blog “On the Internet of Things”
Mobile: +358 40 7796297

Zach Shelby
Head of Research
Sensinode Ltd.
Kidekuja 2
88610 Vuokatti, FINLAND

This e-mail and all attached material are confidential and may contain  
legally privileged information. If you are not the intended recipient,  
please contact the sender and delete the e-mail from your system  
without producing, distributing or retaining copies thereof.

---

From: Zach Shelby <[email-masked]>
Date: Wed, 14 Oct 2009 14:48:27 +0300

On Oct 14, 2009, at 1:30 , Carsten Bormann wrote:

> I'll try to untangle this thread

[Editor hat off]

In my opinion this assumption (and reasoning) is still valid (I  
know... this was supposed to be for arguments against...). Let me add  
in a commercial viewpoint.

I know of no commercially deployed 6LoWPAN networks where address  
resolution is being performed. We have experience working with 6LoWPAN  
on a wide range of link-layer technologies and an even wider range of  
applications - and AR has not been a requirement so far.

If there is no real (not imaginary) need for it, then it is a waste of  
energy. And yes, having to be able to send and process NS/NA messages,  
LLOAs as well as the caches involved does take both ROM and RAM.

I do agree with Jonathan that ideally it would be great to know if an  
IID has been derived from a link-layer address - but that is a  
shortcoming of IPv6 in general...

Zach

> beat this horse for today.)

Argh, how many days are we going to be at this? ;-(

Zach Shelby
Head of Research
Sensinode Ltd.
Kidekuja 2
88610 Vuokatti, FINLAND

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 14 Oct 2009 14:16:14 +0200

>that goal - I am sure we can figure out a way to achieve it.

I'm with you as usual. This is a 2 step discussion. 
* First step is to clean up the remnant assumptions on LLA/IID tyings so
that the current spec holds together without it.
  There's still text like in 3.4 that needs cleaning up and I'd think
that this work is needed right now. 
  Great thing that Carsten woke us up on this.

* Then talk about the line of sight direct communication. 
  The requirement for that has been expressed at ROLL, in particular in
the context of home and building automation.

In any case, a path is supposed to exist via the router if the target is
reachable at all over IP. So there is no emergency to locate what is
only a shortcut - that may or may not exist over one hop - and a simple
beacon would suffice in a constrained node. IOW we do not need full
fledge discovery as in 4861 though it would be good to be able to use it
if it is available. 

RPL proposes that a host MAY multicast an NA-DAO to advertise itself
over one hop. That is certainly a beginning and probably the only thing
that can be done simply and generically because it can be broadcasted on
a broadcast medium (ala ND), or copied to all circuits on statically or
dynamically allocated circuits such as P2P time slots (ala InvND). 

Whether a better or more suited discovery can apply depends on the
medium and the deployment. To be honest I think that this text does not
belong to RPL but to ND and  I'd be fine to include the capability to do
that, but certainly that should be controlled by policy / application
needs.

For instance, one could use 6LowPAN-ND on Ethernet to enforce source
address validation. 
In a given deployment this could be done for packets going outside the
subnet in which case 4861 could still be used within. 
In another, we'd want any packet to be validated and thus 4861 would be
disabled and all packets would be forced to go via a router that would
validate the registration and thus the right to use the address.

In another instance, a sensor and an actuator would be placed in line of
sight expecting that most of the time they can see each other. In a
given deployment, some provisioning might be involved to setup a one-hop
Time Slotted circuit between the 2 hosts. As part of that provisioning,
they would be instructed to advertise themselves to one another. But if
the circuit is between 2 routers, there might be no point in sending the
NA.

What do you think?

Pascal
>http://zachshelby.org - My blog "On the Internet of Things"
>Mobile: +358 40 7796297
>
>Zach Shelby
>Head of Research
>Sensinode Ltd.
>Kidekuja 2
>88610 Vuokatti, FINLAND
>

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 14 Oct 2009 14:54:48 +0200

Hi Carsten,

It looks like the approach is to remove as much as possible, with the
view of what current applications need 
The approach I guess we are defending is
- do existing protocols work on this medium (/media)?
- if not can we make them work transparently to IP?
- if not what do we need to change to IP/ND/..., and in which WG (does
it concern only 6lowpan, 802.15.4, or others?)

This was the RFC2491 approach for NBMA:
"A number of key advantages are claimed for this approach. These are:
      The IPv6 stacks on hosts do not implement separate ND protocols
      for each link layer technology."

What is the percentage of IPv6-over-foo RFC that decided to define a
totally new ND for their medium (which was not an optional extension)?

If we go down the way of doing a custom ND, we could also ask the
questions:
"are IP addresses needed?" I am sure we can twick specs to do without in
the lowpan.
"is transport needed?"...
Is layering needed?

So regarding address resolution, the balance between what we gain (less
NS, though there are not many as Jonathan mentions, and there are less
if you send RAs) and what we loose (one ND stack for all mediums, one
RPL for all mediums, one SeND, one MIPv6, ...? ) is for me in favor of
trying to redefine as little as we can.

Julien

> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Carsten Bormann
> Sent: mercredi 14 octobre 2009 00:31
> To: 6lowpan
> Subject: [6lowpan] Fundamental assumptions of 6lowpan-nd-06: 
> (1) Addressresolution is a waste of energy
> 
> IPv4 needed address resolution for Ethernet to map a 32-bit 
> address space, n<32 bits of which were a host number within a 
> network, to a 48- bit MAC address.  IPv6 continued to follow 
> that model for Ethernet even if that strong need no longer 
> was there, with a likely default mapping but a possibility 
> for manual assignment (or DHCP), so address resolution (AR) 
> was still needed.
> 
> Also, we actually have a way to assign *MAC addresses* the 
> way DHCP did this for *IP addresses*: 16-bit addresses are 
> not owned by a device but can be assigned (using NR/NC in 
> 6lowpan-nd-06), so if there is a need to assign a functional 
> IP address to a device this can be done by assigning it the 
> equivalent 16-bit MAC address.
> 
> In 6lowpans, address resolution requires the establishment 
> (using energy-wasting packets) and maintenance (using 
> precious memory) of state that no longer serves a useful purpose.
> Using anything but the default mapping causes additional 
> header overhead, wasting energy.
> The need for assigned addresses can easily be covered by 
> assigning 16- bit addresses.
> 
> (Tomorrow I will follow up with another assumption, but 
> please let's beat this horse for today.)
> 
> Gruesse, Carsten
>

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 14 Oct 2009 15:33:46 +0200

On Oct 14, 2009, at 14:54, Julien Abeille (jabeille) wrote:

> redefine as little as we can

Julien,

discussing this in generalities doesn't help.

4861-style address resolution does not work in a LoWPAN.
So what do we do?
"Redefine as little as we can" would clearly guide us to leave it out,  
because that's the minimum redesign.
("Design is done when there is nothing left to remove"...)

But I'm not interested in design that is just based on general items  
of philosophy.
I also care little about general points regarding what ATM did --  
LoWPAN nodes are not $50k, but $.50 systems, so some tradeoffs are  
likely to be extremely different.
These are resource-constrained systems, so we shouldn't design  
something new that just wastes resources.

I want to know whether we *need* address resolution.

Pascal gave one very good data point here: It's mostly not needed.
I would like to know when it's still needed, and where the static IID- 
LLA mapping does not cover those needs.

Once I know that, I'd like to know what are good, *working* (and  
reasonably efficient) ways of meeting those requirements.
Hijacking messages from 4861 and giving them different semantics does  
not qualify; we should be upfront where we design new protocol  
(although we may be able to reuse formats, as we did in 6lowpan-ND-06).

Gruesse, Carsten

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 14 Oct 2009 16:25:18 +0200

Hi Carsten,

> From: Carsten Bormann [mailto:[email-masked]] 
> Sent: mercredi 14 octobre 2009 15:34
> To: Julien Abeille (jabeille)
> Cc: 6lowpan
> Subject: Re: [6lowpan] Fundamental assumptions of 
> 6lowpan-nd-06: (1) Addressresolution is a waste of energy
> 
it does. We also need to understand, what IP advantages we keep with
6lowpan-ND, what we loose, in terms of reusability, simlicity, cost... 
Asking questions solely in terms of protocol efficiency does not work,
as these are not the only parameters to take into account. If it was
only about protocol efficiency in the lowpan, I would personaly not use
IP at all.

So trying to detail both sides: 
- In a number of scenarios, people are fine with mandating the IID to be
forged on the MAC
- not sending NS saves power

What we lose: 
- complexity: we end up implementing one ND per link type
- reusability: we reevent protocols per link type. This one can get
important when it comes to education, network management...

We also have major disagreement on assumptions, which I try to
summarize:
A. one camp assumes although nodes are sleeping, well known and deployed
duty cycling techniques makes nodes appear always on. The other camp
thinks there are always nodes that cannot be reached 100% of the time. 
B. we agree on the non transitive aspect
C. one camp considers the link asymetric. IP applications will not work
in this scenario either. I do not think we are in a UDLR environment
D. we all agree we are considering a route over scenario

For those who think duty cycling solves the sleeping nodes issues:
- only DAD fails. Do we agree on this?

For those who sleeping nodes are a problem:
- AR, NUD, DAD fails

Is the summary fair?

Best,
Julien

> "Redefine as little as we can" would clearly guide us to 
> leave it out, because that's the minimum redesign.
> But I'm not interested in design that is just based on 
> general items of philosophy.
> I also care little about general points regarding what ATM 
> did -- LoWPAN nodes are not $50k, but $.50 systems, so some 
> tradeoffs are likely to be extremely different.
> These are resource-constrained systems, so we shouldn't 
> design something new that just wastes resources.
> 
> I would like to know when it's still needed, and where the 
> static IID- LLA mapping does not cover those needs.
> 
> Once I know that, I'd like to know what are good, *working* 
> (and reasonably efficient) ways of meeting those requirements.
> Hijacking messages from 4861 and giving them different 
> semantics does not qualify; we should be upfront where we 
> design new protocol (although we may be able to reuse 
> formats, as we did in 6lowpan-ND-06).
> 
> Gruesse, Carsten
> 
>

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 14 Oct 2009 16:49:57 +0200

> 6lowpan-ND, what we loose, in terms of reusability, simlicity, cost...

There is no change to IP.

> important when it comes to education, network management...

It's much better to have a new protocol than to misuse an old protocol  
in ways it never was designed for.

> thinks there are always nodes that cannot be reached 100% of the time.

I think 6lowpan-ND must cope with both kinds of nodes.
In general, that makes all protocol mechanisms that expect hosts to  
react to unsolicited messages somewhat difficult.

> in this scenario either. I do not think we are in a UDLR environment

Well, there is no assurance of symmetry, but I'm not sure what you  
mean here.

> D. we all agree we are considering a route over scenario

I don't agree with that.
6lowpan-ND should work for mesh-under as well, and should not require  
LoWPAN-wide multicast for that.
6lowpan-ND should also work in a minimal "star network".

> - only DAD fails. Do we agree on this?

4861 DAD (and everything else that would require multicasting NS  
throughout a LoWPAN) fails independent of sleeping nodes.

> For those who sleeping nodes are a problem:

4861 AR (and everything else that would require multicasting NS  
throughout a LoWPAN) fails independent of sleeping nodes.
Wait, 4861 does not even *specify* AR for NBMAs, so nothing is  
failing, it's just not there.
(To return to the subject of this thread: Losing AR apparently is not  
a problem.)

NUD is interesting, because 4861 uses it for a number of things.   
Maybe we can return to this later.

Gruesse, Carsten

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 14 Oct 2009 17:05:14 +0200

Hi Carsten, 

I got the mesh under point.
Do we agree that
- in route over
- considering duty cycled nodes with efficient duty cycling techniques
(smapled listening, centralized scheduling)
(RFC4861) AR works (I can resolve addresses of one hop neighbors), NUD
works, router and prefix discovery... Work
DAD fails
In other terms features related to reachability of one hop neighbors,
resolution of their address, router/parameter/prefix discovery work?
Addressing related features fail?

Julien

> Sent: mercredi 14 octobre 2009 16:50
> It's much better to have a new protocol than to misuse an old 
> protocol in ways it never was designed for.
> 
> > A. one camp assumes although nodes are sleeping, well known and 
> > deployed duty cycling techniques makes nodes appear always on. The 
> > other camp thinks there are always nodes that cannot be 
> reached 100% 
> > of the time.
> 
> In general, that makes all protocol mechanisms that expect 
> hosts to react to unsolicited messages somewhat difficult.
> 
> > C. one camp considers the link asymetric. IP applications will not 
> > work in this scenario either. I do not think we are in a UDLR 
> > environment
> 
> Well, there is no assurance of symmetry, but I'm not sure 
> what you mean here.
> 
Got it.
> 6lowpan-ND should work for mesh-under as well, and should not 
> require LoWPAN-wide multicast for that.
> 4861 DAD (and everything else that would require multicasting 
> NS throughout a LoWPAN) fails independent of sleeping nodes.
> 
> 4861 AR (and everything else that would require multicasting 
> NS throughout a LoWPAN) fails independent of sleeping nodes.
> Wait, 4861 does not even *specify* AR for NBMAs, so nothing 
> is failing, it's just not there.
> (To return to the subject of this thread: Losing AR 
> apparently is not a problem.)
I'll stop on semantics

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 14 Oct 2009 18:00:30 +0200

On Oct 14, 2009, at 17:05, Julien Abeille (jabeille) wrote:

> (RFC4861) AR works (I can resolve addresses of one hop neighbors),

Well, 4861 explicitly says that it does not specify AR for NBMAs.
If you want to use the NS/NA pair of messages anyway, you first have  
to make an on-link determination.
You would use an NHDP for that, and that could also carry the LLA  
(possibly implicitly), so there is never a *need* for AR.
Then, of course, you could run the NHDP using messages that look like  
4861 NS/NA messages, but they wouldn't have the same semantics;  You  
still have to specify the *protocol* of your NHDP, and that would best  
be done in the context of the routing protocol.
(I don't mind a routing protocol using ND messages, in particular if  
there are piggy-backing opportunities; it just complicates things a  
bit.)

> NUD works,

I'd like to discuss NUD separately, as the term is used for a number  
of things in 4861, some of which are really about routing.  (Also,  
with 802.15.4 ACKs, there is a bit less of a need for NUD than on  
Ethernet.)

> router and prefix discovery... Work

Yes.
(In a LoWPAN, you would add context dissemination here, see section  
4.3 and 4.5.2/4.5.3.)
A remaining problem is that the lifetime of the RA may not be useful,  
as the router may go out of the node's radio range earlier.
You may call the part of the NHDP that detects this NUD, but see above.

> DAD fails

Yes, because DAD is not a one-hop feature in a LoWPAN.

> Addressing related features fail?

See above.

Gruesse, Carsten

---

From: Zach Shelby <[email-masked]>
Date: Wed, 14 Oct 2009 21:45:07 +0300

On Oct 14, 2009, at 18:05 , Julien Abeille (jabeille) wrote:

> works,

AR and NUD initiated by an RFC4861 interface on an Edge Router will  
fail in route-over configurations for any destinations outside of  
radio range. This is the result of the non-transient link:

ER ---- A ---- B ----- C
    ++++++

As you concluded, NS/NA is only useful within radio range. Let's  
assume ER and A are within radio range. ER attempts to send to C. What  
happens to the NS? Fails. This is why I don't see RFC4861 without any  
adaptation as a solution on a LoWPAN interface. It expects that NS/NA  
messages reach the whole subset of nodes on the link, but that is not  
the case.

This is the reason why we have a whiteboard with entries for all  
LoWPAN nodes (A, B, C). For all AR, NUD and DAD requests coming from  
the ER side it is able to answer them immediately (without any  
overhead to the LoWPAN!). The whiteboard also enables DAD for NRs  
coming from the LoWPAN side.

I agree that within the LoWPAN some kind of 1-hop NUD may be useful,  
and that should be discussed.

Zach

Zach Shelby
Head of Research
Sensinode Ltd.
Kidekuja 2
88610 Vuokatti, FINLAND

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 14 Oct 2009 21:30:26 +0200

> and that should be discussed.

A couple of thoughts about that:

For route-over (where IP hop = MAC hop), much of that need is filled  
by 802.15.4 ACKs.
(If there are no actual data, just a probe, it might be beneficial to  
add a NOP dispatch type to 4944 at some point...)
One disadvantage of 802.15.4-2006 ACKs is that they are not secure.   
15.4e is scheduled to fix this, but we may not want to wait for that.
This and mesh-under (where the ACK only covers the first mesh hop)  
might motivate having some reachability probe message, but it would be  
somewhat rarely used.

Using NS/NA for reachability is somewhat unfortunate, as these packets  
are not small.  Then, of course, if you want to derive arrival  
probability estimations and have nothing else to go by, these are more  
accurate if the packets are large.

The part I don't like about carrying over NS/NA just for NUD is that  
the processing rules attached to these are more complex than needed  
(cf. the ROLL discussion), and they can carry options, exacerbating  
this.

With 4861 processing rules, many UDP-based applications would  
regularly trigger NUD exchanges (as often as once per packet).
I don't think we want these when we have MAC-layer ACKs.
I don't like the last sentence of section 7 of 4861 here, even though  
I understand that its desire for robustness is a reflection of some  
real-world scars.

Gruesse, Carsten

PS.: Yes, I changed the subject line for tomorrow to be just about NUD.

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 14 Oct 2009 17:24:25 -0400

From: Carsten Bormann <[email-masked]>
   Date: Wed, 14 Oct 2009 21:30:26 +0200

I have generally found 802.15.4 ACKs unhelpful for NUD.
There a lots of ways in which an ACKed packet can fail to
reach the higher layers.  For example, any kind of MAC
security confusion can cause packets to be ACKed but
otherwise ignored.

What has worked for NUD, between routers at least, is
relying on link quality measurements.  In the systems that I
have used each router periodically informs its neighbors of
its own link quality estimates in order to detect asymmetric
links.  This has the side effect of removing any need for
NUD above the link layer.

In summary, I think that 1-hop NUD is important, but that
it doesn't necessarily have to be done at layer 3.

                                 -Richard Kelsey

---

From: Geoff Mulligan <[email-masked]>
Date: Wed, 14 Oct 2009 16:40:20 -0600

> optimization at its best - if you don't need it - leave it out.

I am really concerned about statement.  I have seen plenty of real
applications that require P2P and not just host to router
communications.

If AR is required for P2P then we cannot leave it out.

	geoff

---

From: Geoff Mulligan <[email-masked]>
Date: Wed, 14 Oct 2009 16:52:52 -0600

> applications - and AR has not been a requirement so far.

Personally I don't know of ANY commercially deployed 6lowpan networks,
though some are on the horizon.

I do know of some pilots and prototypes where we used AR to find short
addresses so that we didn't need to use 64 bit addresses.

	geoff

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 14 Oct 2009 21:56:48 -0700

> security confusion can cause packets to be ACKed but

Same experience here.

> it doesn't necessarily have to be done at layer 3.

I don't see an appreciable cost difference in utilizing raw link,  
6lowpan, or IP messages - especially for link-local communication.

Changing the semantics of an 'ack' will certainly help NUD if you use  
unicast probing to achieve it.

--
Jonathan Hui

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 15 Oct 2009 07:18:05 +0200

Hi Carsten:

We have one hop NUD in the draft. Any node that wants to pass a packet
to a next-hop router must first register to that router using NR/NC. If
the router is not a whiteboard then it will relay. 

NR/NC serves a number of purposes:

1) the edge router handles DAD and transparent mobility. It May generate
the address on behalf of the node.
2) the edge router validates address ownership and the right to use it
if the node is a host
3) the edge router validates the right to forward packet from below if
the node is a router
4) the next-hop router implements the Source address validation
accordingly  
5) the next-hop router validates that it has the resources to serve the
node (simple call admission control, can be augmented by additional
options)
6) NR/NC confirms liveliness and bidirectional reachability
7) NR/NC can carry additional information such as RPL DAO and MIP
registration

As opposed to NDP, this form of NUD is not symmetrical. Traffic from the
router does not trigger our NR/NC. 
This helps conserve energy for low power nodes.
 
Pascal

>From: [email-masked] [mailto:[email-masked]] On
Behalf Of Zach Shelby
>Sent: mercredi 14 octobre 2009 20:45
>Cc: Carsten Bormann; 6lowpan
>Subject: Re: [6lowpan] Fundamental assumptions of 6lowpan-nd-06:
(1)Addressresolution is a waste of energy
>> (RFC4861) AR works (I can resolve addresses of one hop neighbors),
NUD

---

From: Zach Shelby <[email-masked]>
Date: Thu, 15 Oct 2009 09:53:15 +0300

> If AR is required for P2P then we cannot leave it out.

That is not what I said. There is nothing stopping you from doing P2P,  
which is of course a very important feature for me as well. AR is not  
a prerequisite for P2P.

Zach

Zach Shelby
Head of Research
Sensinode Ltd.
Kidekuja 2
88610 Vuokatti, FINLAND

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 15 Oct 2009 09:34:02 +0200

> router does not trigger our NR/NC.

Right.

So what kinds of NUD might one need?

Host->Router is indeed best handled by the NR/NC process, and could  
also benefit from NUD-like upper-layer indications of liveness.

Router->Host?  4861 NUD is about finding out when a node is gone or  
has changed its MAC address.
In a wireless network, nodes are obscured, going away and coming back  
all the time.
Using NUD as the carrier for a reachability protocol between routers  
and hosts is a distinct possibility, but may simply have the wrong  
granularity.
I'd like to understand the requirements for such a reachability  
protocol a bit better.
And, again, I see a much stronger link to reachability protocols used  
by the routing system than to ND.
(I still believe MAC-layer ACKs are good for quickly handling  
*changes* in radio range reachability, even if they don't always  
detect all non-radio issues.  Oh, should NR/NC maybe be a three-way  
handshake?)

Host->Host?  Much of the same.  This is also about reachability, and  
in contrast to Ethernet ND the on-link decision is gated on  
reachability as well.  And, again, (the lack of) MAC-layer ACKs  
provides the quickest possible feedback that there might be a need to  
switch back to a router.
But it also would be useful to occasionally get a "end-to-end  
confirmation between neighboring IP layers" as in the last sentence of  
section 7 of 4861.
(And, back to question 1, there also is a need to find one or more MAC- 
layer addresses of the other host -- whatever you use to know it's  
there will also reveal at least one.)

My current take is that we are looking for something almost, but not  
entirely unlike NS/NA.

(Fixed the subject line; this is about subject 2.)

Gruesse, Carsten

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Thu, 15 Oct 2009 09:44:56 +0200

Hi Zach, 

> From: Zach Shelby [mailto:[email-masked]] 
> AR and NUD initiated by an RFC4861 interface on an Edge 
> Router will fail in route-over configurations for any 
> destinations outside of radio range. This is the result of 
> the non-transient link:
Yes, this is the point. In route over you do not want to resolve two hop
neighbors. Otherwise you will use their MAC as L2 destination of any
message, and it will not reach them. You want to resolve and confirm
reachability of one hop neighbors only. It works and is more power
efficient than a multihop unicast to the sink if  
- average number of neighbors + 1 < 2 x average number of hops to the
sink.

Julien

> 
> ER ---- A ---- B ----- C
>     ++++++
>
> As you concluded, NS/NA is only useful within radio range. 
> Let's assume ER and A are within radio range. ER attempts to 
> send to C. What happens to the NS? Fails. This is why I don't 
> see RFC4861 without any adaptation as a solution on a LoWPAN 
> interface. It expects that NS/NA messages reach the whole 
> subset of nodes on the link, but that is not the case.
> 
> This is the reason why we have a whiteboard with entries for 
> all LoWPAN nodes (A, B, C). For all AR, NUD and DAD requests 
> coming from the ER side it is able to answer them immediately 
> (without any overhead to the LoWPAN!). The whiteboard also 
> enables DAD for NRs coming from the LoWPAN side.
> 
> I agree that within the LoWPAN some kind of 1-hop NUD may be 
> useful, and that should be discussed.
> 
> Zach
> 
> 
> hosts to 
> This e-mail and all attached material are confidential and 
> may contain legally privileged information. If you are not 
> the intended recipient, please contact the sender and delete 
> the e-mail from your system without producing, distributing 
> or retaining copies thereof.
> 
> 
> 
>

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Fri, 16 Oct 2009 09:54:46 +0200

Hi all,

By assume I mean require.

Best,
Julien

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 16 Oct 2009 12:39:08 +0200

Great question.

I would like to extend it to "which procedures from which IPv6 RFCs  
assume link transitivity and/or high-delivery-probability subnet-wide  
multicast", as these are the assumptions violated by a LoWPAN (in most  
configurations, excepting two-node and full-multicast mesh-under).

Just one example for the former: RFC 4861 redirect assumes that a  
router can tell a host that it can reach another host via the same  
link.  Not true in LoWPANs.

The obvious RFC 4861 example for the problems caused by the latter,  
i.e. (deliberate) lack of high-delivery-probability subnet-wide  
multicast, is DAD.  But there may be a lot of other protocols hit by  
this.  Is this a problem?
It would be if these protocols were likely to show up in LoWPANs.  One  
important assumption behind 6LoWPAN is that it is not so likely that  
LoWPANs will be freely substituted for Ethernet (in the sense that  
802.11 was essentially employed as an Ersatz Ethernet).  Example:  
People are not going to open their laptops and see, oh there is a  
LoWPAN, and start using that for their normal Internet access  
activities such as E-Mail and Web access (although these two actually  
would pretty much work).

6LoWPAN started out by saying "let's build an IPv6 link out of  
802.15.4", with the assumption it would then be like any other IPv6  
link.  It took a couple of years to readjust that assumption.  People  
newly coming in from high-power IPv6 may now also need some time to  
readjust theirs.

Gruesse, Carsten

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Fri, 16 Oct 2009 14:08:03 +0200

Hi Carsten, 

> Sent: vendredi 16 octobre 2009 12:39
> Cc: Zach Shelby; 6lowpan
> 6lowpan-nd-06: which procedures from which RFCs assume link 
> transitivity
> 
> Great question.
> 
Thank you
> I would like to extend it to "which procedures from which 
> IPv6 RFCs assume link transitivity and/or 
> high-delivery-probability subnet-wide multicast",
I would prefer asking questions individually before merging.
Regarding the second question, we still have two disalignments: 
- "subnet wide" (this is a tough one as we have not discussed addressing
yet) vs "one hop radio wide" . E.g. in route over for link local address
resolution of 2+ hop neighors make no sense to me. Same with off link
prefixes (which we are talking about I think)
- some of us advocate that duty cycling techniques ensure high delivery
probability one hop away: see Jonathan ("The whole discussion around
sleepy nodes is problematic for me as well.  The link is either up or
down, not sort-of kind-of"), Adam's emails. Kris, can you give your TSCH
view?
> as these 
> are the assumptions violated by a LoWPAN (in most 
> Just one example for the former: RFC 4861 redirect assumes 
> that a router can tell a host that it can reach another host 
> via the same link.  Not true in LoWPANs.
> 
> The obvious RFC 4861 example for the problems caused by the 
> latter, i.e. (deliberate) lack of high-delivery-probability 
> subnet-wide multicast, is DAD.  But there may be a lot of 
> other protocols hit by this.  Is this a problem?
> It would be if these protocols were likely to show up in 
> LoWPANs.  One important assumption behind 6LoWPAN is that it 
> is not so likely that LoWPANs will be freely substituted for 
> Ethernet (in the sense that
> People are not going to open their laptops and see, oh there 
> is a LoWPAN, and start using that for their normal Internet 
> access activities such as E-Mail and Web access (although 
> these two actually would pretty much work).
> 
Agreed (just considering non transitivity), DAD and redirect fail.

> 6LoWPAN started out by saying "let's build an IPv6 link out 
> of 802.15.4", with the assumption it would then be like any 
> other IPv6 link.  It took a couple of years to readjust that 
> assumption.  People newly coming in from high-power IPv6 may 
> now also need some time to readjust theirs.
> 
> Gruesse, Carsten
> 
>

---

From: Kris Pister <[email-masked]>
Date: Wed, 21 Oct 2009 21:13:51 -0700

Julien Abeille (jabeille) wrote:
> [...]
Julien - I'm not sure that I would say that it's the duty cycling 
techniques themselves that ensure high delivery, but I would say that 
those people who have taken the time to develop deeply-duty-cycled link 
layers have also worked very hard to make sure that they are also 
reliable.  802.15.4E in particular provides channel hopping mechanisms 
that make links very stable in time.  With channel hopping and static 
node locations, if the link works today then the probability that it 
will disappear tomorrow is almost zero (maybe 0.1%?), even in the 
presence of a lot of human activity.  The quality may change - for the 
most volatile decile ETX can vary by many 10s of percent over a period 
of hours, but it's very rare that it will go from ~1 to 2, let alone 2 
to 5 or infinity.

ksjp