Subject: [Efficientnd-dt] DAD problems

From: Ole Troan <[email-masked]>
Date: Thu, 20 Mar 2014 12:35:31 +0000

I tried to list the number of problems with DAD as currently specified in RFC4861/4862:

Doesn’t detect duplicate L2 addresses
Unreliable - fails at detecting actual duplicates in several cases:
- Blocked L2 ports
- Unreliable multicast (collision detection requires two multicast messages to pass through)
  (with default DAD attempts = 1
- False positives in case of looped interfaces (solved by enhanced-dad)
Delays use of address until DAD is finished (rfc4429)
Doesn’t deal with partition and joining
Doesn’t specify what to do in case of collision
Requires all nodes to be awake to defend their address
Unclear on what a node should do after L2 events / waking up from sleep
Vendor sauce: May be used as a signalling message from network to host that it cannot use an address
Vendor sauce: Used by the network to build state

anything else?

cheers,
Ole

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 20 Mar 2014 07:01:43 -0700

> Doesn’t detect duplicate L2 addresses
Sometimes it does, but under rather limited cases.
> Doesn’t specify what to do in case of collision
We don't have a generic specification - but things like temporary and 
CGA do specify it.

> Vendor sauce: Used by the network to build state
Can't think of any.

Erik

>
> cheers,
> Ole
>
>
> _______________________________________________
> Efficientnd-dt mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/efficientnd-dt

---

From: "Eric Levy- Abegnoli (elevyabe)" <[email-masked]>
Date: Fri, 21 Mar 2014 09:06:36 +0000

Vendor sauce is mostly rfc6620: (Used by the network to build state).
You can add:
rfc6620: used by switches to poll devices for checking an address in use.
DAD is used because this is the only query that does not need a source
address (unlike NUD or NS-lokkup). This is problematic because it can get
confused by the the target as "my address is a duplicate.
Eric 

On 20/03/14 13:35, "Ole Troan" <[email-masked]> wrote:

>Doesn¹t detect duplicate L2 addresses
>Doesn¹t deal with partition and joining
>Doesn¹t specify what to do in case of collision

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 21 Mar 2014 10:01:56 +0000

Hello Eric and Ole

1) DAD will not discriminate between self-inflicted and real duplication.

There are multiple use cases when a DAD can come back though it's not classical Ethernet. 
Note: I'm not saying that we need to care about duplicate MAC, this is a separate debate.
I'm saying that layer 3 should take care of its own regardless of the weirdness of L2.
-> It could seem relevant that DAD uniquely identify the requester like DHCP does.

2) The DAD behavior when the node moves needs to be improved and unified to support ND proxies.

In RFC 4389, RFC 6275, and 6TiSCH, we define proxies that will do DAD on behalf of not-onlink devices. In some cases a node may move onto the link where the proxy is defending its address(es), and the proxy may (will in RFC6275) prevent the node from inserting the address unless a proper deregistration has taken place. In Eric's case the proxy polls the device using DAD and if that happens in TENTATIVE, then again the device loses it address.
-> It could be relevant to reaffirm the role of the A bit in conjunction with the unique ID above.

3) As in 1) there is a need to determine which is the node behind a proxy. And If that is the case and finally 2 proxies contend for a same address for a same owner, we cannot sort out which of the proxies (if any) has a stale state.

In the duocast model, which is used in industrial wireless, both proxies could actually reach the device at the same time so they would not be exclusive. To support that model we need to have allow for asynchronous registrations that are not mutually exclusive.
In the traditional model with a unique proxy, one proxy did not see the wireless device move away (yet).  In that model, a notion of time or sequence of events would do.
-> A simple sequence number covers both cases. In duocast, the 2 registrations would come with a same sequence.

Cheers,

Cheers,

Pascal

> -----Original Message-----
> From: Efficientnd-dt [mailto:[email-masked]] On Behalf Of Eric
> Levy- Abegnoli (elevyabe)
> Sent: vendredi 21 mars 2014 10:07
> To: Ole Troan; [email-masked]
> Subject: Re: [Efficientnd-dt] DAD problems
> 
> DAD is used because this is the only query that does not need a source address
> (unlike NUD or NS-lokkup). This is problematic because it can get confused by
> the the target as "my address is a duplicate.
> Eric
> 
> >I tried to list the number of problems with DAD as currently specified
> >in
> >RFC4861/4862:
> >
> >Delays use of address until DAD is finished (rfc4429) Doesn¹t deal with
> >partition and joining Doesn¹t specify what to do in case of collision
> >Requires all nodes to be awake to defend their address Unclear on what
> >a node should do after L2 events / waking up from sleep Vendor sauce:
> >May be used as a signalling message from network to host that it cannot
> >use an address Vendor sauce: Used by the network to build state
> >
> >anything else?
> >
> >cheers,
> >Ole
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 21 Mar 2014 10:52:06 +0000

Hello Eric and Ole

(fixed typos)

In RFC 4389, RFC 6275, and 6TiSCH, we define proxies that will do DAD on behalf of not-onlink devices. In some cases a node may move onto the link where the proxy is defending its address(es), and the proxy may (will in RFC6275) prevent the node from inserting the address unless a proper deregistration has taken place. In Eric's case the proxy polls the device using DAD and if that happens in TENTATIVE, then again the device loses it address.
-> It could be relevant to reaffirm the role of the Override bit in NA in conjunction with the unique ID above, and maybe define the bit in NS as well.

3) As for hosts in 1) there is a need to determine which is the node behind a proxy. If that is in place and 2 proxies contend for a same address for a same owner, the additional problem is to determine which of the proxies (or none or both) has a stale state.

In the duocast model, which is used in industrial wireless, both proxies could actually serve the device at the same time. To support that model we need to have allow for asynchronous registrations that are not mutually exclusive.

In the traditional model with a unique proxy, we end up in a contention if one proxy did not see the wireless device move away (yet).  In that model, a notion of time or sequence of events would do.

-> PTP (1588) is complex, requires specific hardware, does not help in duocast and is complete overkill for the case.  
-> A simple sequence number covers both cases. In duocast, the 2 registrations would come with a same sequence.

Cheers,

Pascal

Cheers,

Pascal

> From: Efficientnd-dt [mailto:[email-masked]] On Behalf Of
> Pascal Thubert (pthubert)
> Sent: vendredi 21 mars 2014 11:02
> To: Eric Levy- Abegnoli (elevyabe); Ole Troan; [email-masked]
> In RFC 4389, RFC 6275, and 6TiSCH, we define proxies that will do DAD on behalf
> of not-onlink devices. In some cases a node may move onto the link where the
> proxy is defending its address(es), and the proxy may (will in RFC6275) prevent
> the node from inserting the address unless a proper deregistration has taken
> place. In Eric's case the proxy polls the device using DAD and if that happens in
> TENTATIVE, then again the device loses it address.
> 3) As in 1) there is a need to determine which is the node behind a proxy. And If
> that is the case and finally 2 proxies contend for a same address for a same
> owner, we cannot sort out which of the proxies (if any) has a stale state.
> 
> In the duocast model, which is used in industrial wireless, both proxies could
> actually reach the device at the same time so they would not be exclusive. To
> support that model we need to have allow for asynchronous registrations that
> are not mutually exclusive.
> In the traditional model with a unique proxy, one proxy did not see the wireless
> device move away (yet).  In that model, a notion of time or sequence of events
> would do.
> > address (unlike NUD or NS-lokkup). This is problematic because it can
> > get confused by the the target as "my address is a duplicate.
> > Eric
> >
> > >I tried to list the number of problems with DAD as currently
> > >specified in
> > >RFC4861/4862:
> > >
> > >Doesn¹t detect duplicate L2 addresses Unreliable - fails at detecting
> > >actual duplicates in several cases:
> > >- Blocked L2 ports
> > >- False positives in case of looped interfaces (solved by
> > >enhanced-dad) Delays use of address until DAD is finished (rfc4429)
> > >Doesn¹t deal with partition and joining Doesn¹t specify what to do in
> > >case of collision Requires all nodes to be awake to defend their
> > >address Unclear on what a node should do after L2 events / waking up from
> sleep Vendor sauce:
> > >May be used as a signalling message from network to host that it
> > >cannot use an address Vendor sauce: Used by the network to build
> > >state
> > >
> > >anything else?
> > >
> > >cheers,
> > >Ole
> >

---

From: Ole Troan <[email-masked]>
Date: Fri, 21 Mar 2014 16:52:42 +0000

Pascal,

> -> It could seem relevant that DAD uniquely identify the requester like DHCP does.

indeed. I already had that under:
"- False positives in case of looped interfaces (solved by enhanced-dad)"

> -> It could be relevant to reaffirm the role of the A bit in conjunction with the unique ID above.

here we are talking about a use of DAD that it was never designed for. I don't think we can classify this as a problem with DAD as specified in 4861/4862.

> -> A simple sequence number covers both cases. In duocast, the 2 registrations would come with a same sequence.

again, I don't see how this is a problem with DAD.

with regards to multi-link subnets; there is an IETF consensus that multilink-subnets had so many issues that work on it should be abandoned. with regards to ND proxies, that's experimental. what are the results of the experiment?
it is unclear to me what bearing multi-link subnets / ND proxies should have on this work in general and on the thread of DAD problems specifically.

cheers,
Ole

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 21 Mar 2014 17:30:15 +0000

Hello Ole:

I agree that DAD in 4862 was not designed with those use cases in mind - I'll buy the not_a_bug - but the use cases are out there (MIP, DAD proxy) and if we are to revamp DAD, my suggestion is to make it work at least to the expectation of existing RFCs...

Cheers,

Pascal

> From: Efficientnd-dt [mailto:[email-masked]] On Behalf Of Ole
> Troan
> Sent: vendredi 21 mars 2014 17:53
> To: Pascal Thubert (pthubert)
> Cc: Eric Levy- Abegnoli (elevyabe); [email-masked]
> > In RFC 4389, RFC 6275, and 6TiSCH, we define proxies that will do DAD on
> behalf of not-onlink devices. In some cases a node may move onto the link
> where the proxy is defending its address(es), and the proxy may (will in RFC6275)
> prevent the node from inserting the address unless a proper deregistration has
> taken place. In Eric's case the proxy polls the device using DAD and if that
> happens in TENTATIVE, then again the device loses it address.
> here we are talking about a use of DAD that it was never designed for. I don't
> think we can classify this as a problem with DAD as specified in 4861/4862.
> 
> > In the traditional model with a unique proxy, one proxy did not see the
> wireless device move away (yet).  In that model, a notion of time or sequence of
> events would do.
> with regards to multi-link subnets; there is an IETF consensus that multilink-
> subnets had so many issues that work on it should be abandoned. with regards
> to ND proxies, that's experimental. what are the results of the experiment?
> it is unclear to me what bearing multi-link subnets / ND proxies should have on
> this work in general and on the thread of DAD problems specifically.
> 
> cheers,
> Ole
>

---

From: Ole Troan <[email-masked]>
Date: Fri, 21 Mar 2014 17:40:23 +0000

Pascal,

> I agree that DAD in 4862 was not designed with those use cases in mind - I'll buy the not_a_bug - but the use cases are out there (MIP, DAD proxy) and if we are to revamp DAD, my suggestion is to m…

if the actual use case isn't duplicate address detection, then there may be better solutions out there than abusing DAD.
I'm all for getting a good understanding of 'creative uses' of DAD as well as understanding the problems that you are looking at solving. do you have a simple text explaining the problem you want to solve?

cheers,
Ole

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 21 Mar 2014 18:23:21 +0000

I see what you're saying, Ole, and would agree on the case you describe. 

But the issue here is that existing DAD is fooled by those configuration and provides a false positive... that's different.

On the side, I do agree with Ran (on the 6MAN ML today) on the fact that efficient ND should be innocuous to non E-ND devices, and that it should not enter in the certification of devices that have no use of it. If there was a misunderstanding there, just making it clear; I answered on the ML a few minutes ago.

For DAD to detect the anomalies that we are talking about, all we need is a device unique ID and a sequence counter in a new option. Devices implementing this new option can perfectly cohabit with other devices that do not implement the option as long as the latter devices do not misbehave when receiving the option. The support of the option would only be recommended  for devices that move or may use a proxy. 

Cheers,

Pascal

> From: Ole Troan [mailto:[email-masked]]
> Sent: vendredi 21 mars 2014 18:40
> > I agree that DAD in 4862 was not designed with those use cases in mind - I'll
> buy the not_a_bug - but the use cases are out there (MIP, DAD proxy) and if we
> are to revamp DAD, my suggestion is to make it work at least to the expectation
> of existing RFCs...
> 
> I'm all for getting a good understanding of 'creative uses' of DAD as well as
> understanding the problems that you are looking at solving. do you have a
> simple text explaining the problem you want to solve?
> 
> cheers,
> Ole

---

From: Ole Troan <[email-masked]>
Date: Fri, 21 Mar 2014 20:30:02 +0000

Pascal,

> For DAD to detect the anomalies that we are talking about, all we need is a device unique ID and a sequence counter in a new option. Devices implementing this new option can perfectly cohabit with…

for the looped link/receiving your own multicast we do have:
http://tools.ietf.org/html/draft-ietf-6man-enhanced-dad-04

that's about to go working group last call. does that also cover the cases you have in mind?

cheers,
Ole

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Sat, 22 Mar 2014 07:44:58 +0000

Hello Ole:

The nonce is not a UID; the draft helps for the immediate loopback problem but not for the delayed one, e.g. a proxy.

The difference is that the UID:
* has a longer life. The node must be able to save it or reconstruct it as long as it exists as a state in the network.
* is expected to have more properties than a nonce, e.g. more likely to be unique or harder to forge (CGA).

Same problem as 4862: the solution works but the problem space that is envisioned is too narrow, so it will need more patching soon. How many steps do we want to take?

I understand that we cannot work on problems that we imagine we may have, but here we are talking about clear and present issues in existing RFCs and deployments. 

This time I'll follow Lorenzo's wisdom. Overloading the nonce option can only take use so far, as opposed to designing a new option that covers the needs that are identified today. We know that those needs can be covered by a UID and a TID.

Cheers,

Pascal

> Sent: vendredi 21 mars 2014 21:30
> > But the issue here is that existing DAD is fooled by those configuration and
> provides a false positive... that's different.
> >
> > On the side, I do agree with Ran (on the 6MAN ML today) on the fact that
> efficient ND should be innocuous to non E-ND devices, and that it should not
> enter in the certification of devices that have no use of it. If there was a
> misunderstanding there, just making it clear; I answered on the ML a few
> minutes ago.
> >
> > For DAD to detect the anomalies that we are talking about, all we need is a
> device unique ID and a sequence counter in a new option. Devices implementing
> this new option can perfectly cohabit with other devices that do not implement
> the option as long as the latter devices do not misbehave when receiving the
> option. The support of the option would only be recommended  for devices that
> move or may use a proxy.
>

---

From: Ole Troan <[email-masked]>
Date: Sun, 23 Mar 2014 11:37:20 +0100

Pascal,

I've created a new thread for this discussion as it isn't directly related to immediate problems with DAD.

> * is expected to have more properties than a nonce, e.g. more likely to be unique or harder to forge (CGA).

the nonce is defined in rfc3971

> Same problem as 4862: the solution works but the problem space that is envisioned is too narrow, so it will need more patching soon. How many steps do we want to take?

Pascal, you are many steps ahead of us (at least me :-)). I wouldn't be surprised to learn that your solution is the correct one, but I would dearly like to understand the logical steps that took you to it.
 - what problems are you trying to solve?
 - what led you t conclude that you need multilink-subnets?
 - what are you thinking of using DAD for? that doesn't appear to be directly related to detection of duplicate addresses?
 - what are the purpose and benefits for "classic" IPv6 hosts?

> This time I'll follow Lorenzo's wisdom. Overloading the nonce option can only take use so far, as opposed to designing a new option that covers the needs that are identified today. We know that tho…

I'm not against working on multi-link subnets or solving the problem of duplicate address detection in multi-link subnets. there are other more pressing problems with multi-link subnets than DAD though. the DAD problem can be simply solved. if every node picks a random iid out of a 2^64 space, I'm happy to take all the support calls myself for the cases of actual duplicates. ;-)

cheers,
Ole

---

From: Ole Troan <[email-masked]>
Date: Sun, 23 Mar 2014 14:55:42 +0100

Eric,

> confused by the the target as "my address is a duplicate.

I've tried to read RFC6620, but I'm still far from understanding the implications of how 6620 uses ND.
e.g. if a FCFS switch misses the DAD message, what happens? does it build state based on DAD?

cheers,
Ole

---

From: Erik Nordmark <[email-masked]>
Date: Sun, 23 Mar 2014 22:25:03 -0700

> e.g. if a FCFS switch misses the DAD message, what happens? does it build state based on DAD?
In that case the SAVI is triggered by receiving any IPv6 packet with an 
unknown IPv6 source address.

    Erik

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 24 Mar 2014 13:57:02 +0000

Hello Ole:

Basically the multilink subnet approach that we have in large scale WSN is dictated by the use case we cover. 

We use ND proxy, which is an interesting technique when:
- the direct L2 connectivity is not at all possible, e.g. MAC64 to Ethernet, 
- or not *always* possible, e.g. mobile or sleeping device. 

In an architecture with a federating backbone we found that:
- ND as it stands is effectively a great protocol for adhoc node/address discovery over one hop iff multicast is affordable over the backbone
- ND's operation compares to that of AODV if used in similar circumstances - but for the mobile aspect
- ND lacks the capability to handle movement, just like non MANET routing protocols (say BGP, ISIS, OSPF) would if used as alternate, no magic there.

The problems we found show up as soon as you have a state in the network that might interact with the DAD operation, IOW that also uses DAD flows for its own purpose asynchronously to the device itself:
- the device may be misled when receiving a DAD from a proxy. Is that 2 nodes fighting for a same address or 2 messages that are ultimately about the same node?
- Exclusive state owner cannot resolve a collision. Which is the SAVI switch/proxy that the device is effectively attached to / relying  upon?
We have such state in the network in DAD proxy, MIPv6/NEMO, SAVI, LISP... Practice has gone way beyond experimental.

In summary, when it appears through DAD that there are 2 states in the network, ND as it stands cannot determinate: 
a) if the states are about the same node or not, and 
b) if states are exclusive, which is the correct one. 
It seems to me that the loopback DAD is a subset of a). 

We found  we can solve with a) and b) with a quick and simple logic if we add simple option in ND with 
1) a UID ala DHCP and 
2) a sequence counter ala RPL/AODV 

This approach conserves the ND flows over the backbone and appears a lot simpler to implement and deploy than adding to the picture a limitation like non-onlink or an alternate routing protocol (a MANET or a modified routing protocol) that would have to be deployed on the backbone.

When I consider your long list of DAD problems, it seems to me that these are not necessarily the problems per se, but sometimes environments or use cases where DAD as it stands does not fully and efficiently perform its task. My lists boils down to:

a) and b) above plus
c) sensitive to frame loss multicast / lossy environment 
d) expensive in environments where multicast is not efficient eg 802.11 
e) unfeasible in constrained environments with no multicast support, e.g. 802.15.4
f) incompatible with non-persistent connectivity e.g. sleeping or mobile devices

a) and b) drive the content of the ARO option, and e) lead to RFC 6775 but can be leveraged for c), d) and f) .
All in all, it appears to me that WiND (efficient ND) is a rather low cost extension to ND WRT the problems that it solves...

Cheers,

Pascal

> Sent: dimanche 23 mars 2014 11:37
> Subject: The larger problem (was Re: [Efficientnd-dt] DAD problems)
> 
> Pascal,
> 
> > The nonce is not a UID; the draft helps for the immediate loopback problem
> but not for the delayed one, e.g. a proxy.
> >
> > Same problem as 4862: the solution works but the problem space that is
> envisioned is too narrow, so it will need more patching soon. How many steps
> do we want to take?
> 
> Pascal, you are many steps ahead of us (at least me :-)). I wouldn't be surprised
> to learn that your solution is the correct one, but I would dearly like to
> understand the logical steps that took you to it.
>  - what are you thinking of using DAD for? that doesn't appear to be directly
> related to detection of duplicate addresses?
> > I understand that we cannot work on problems that we imagine we may have,
> but here we are talking about clear and present issues in existing RFCs and
> deployments.
> >
> > This time I'll follow Lorenzo's wisdom. Overloading the nonce option can only
> take use so far, as opposed to designing a new option that covers the needs that
> are identified today. We know that those needs can be covered by a UID and a
> TID.
> 
> I'm not against working on multi-link subnets or solving the problem of duplicate
> address detection in multi-link subnets. there are other more pressing problems
> with multi-link subnets than DAD though. the DAD problem can be simply solved.
> if every node picks a random iid out of a 2^64 space, I'm happy to take all the
> support calls myself for the cases of actual duplicates. ;-)
> 
> cheers,
> Ole

---

From: Ole Troan <[email-masked]>
Date: Tue, 25 Mar 2014 10:08:17 +0100

Pascal,

> - or not *always* possible, e.g. mobile or sleeping device. 

I'm still not sure I understand the use case for MLSR / ND proxy?
could you elaborate? why MLSR instead of normal subnets?

the RFC4389 ND proxy only works in very specific cases, I don't think we want to restrict all IPv6 subnets to those very limited topologies. or are you talking about a different ND proxy?

> It seems to me that the loopback DAD is a subset of a). 

I take it you aren't talking about DAD as for "duplicate address detection", but DAD as a mechanism to generate and maintain state in the network?

I think DAD is particularly poorly suited for that... and I'm not sure that's a practice we should continue.
what happens in your cases when the DAD message is lost?

> All in all, it appears to me that WiND (efficient ND) is a rather low cost extension to ND WRT the problems that it solves...

I still don't understand the applicability of what you say to classic IPv6.
if I'm the only one lost here I'll shut up, but otherwise I'd really like you to explain the complete problem (or point to documents).

cheers,
Ole