Subject: RE: [Autoconf] The case for address uniqueness

From: "Kilian Weniger" <[email-masked]>
Date: Thu, 2 Feb 2006 17:09:43 +0100

Hi Christoph, all,

I agree that the probability of collision is very low in case of
EUI-64-based IPv6 addresses (especially with the measures you mentioned
in your mail), but I want to raise awareness of the following related
issues: 

- Duplicate addresses have significant impacts on the routing of data
packets and may lead to permanent packet loss
- Globally unique addressing is only possible with IPv6, not with IPv4
- Those IDs are not 100\% globally unique, e.g., a IEEE MAC address
configured at a specific network interface may be changed by the user,
known instances of devices with duplicate MAC addresses exist on the
market (e.g., non-registered or erroneous manufacturing), and some
devices may not have globally unique hardware IDs at all (e.g., sensors)
- Globally unique IDs may have negative implications on privacy (see
RFC3041)
- Globally unique IDs must be long to be able to uniquely identify all
existing devices and hence significantly increase signaling traffic.
This has negative implications on the scalability of, e.g., the routing
protocol. Locally unique IDs can be much more efficient, since such
addresses may very short (depending on the size of the network) or can
easily be compressed to short addresses. Our simulations have shown that
80-90% of routing protocol overhead can be saved with locally unique IDs
(see PACMAN paper referenced in my last mail).

Especially for larger networks, I'm in favour of locally unique IDs,
which implies that some kind of DAD scheme is needed. If globally unique
IDs are used in the entire network (how does a node know that?), I'm
fine with an optional DAD, but still prefer at least a SHOULD or MUST if
the DAD is efficient in terms of ressource consumption.

Regards,

Kilian

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Christophe Jelger
> Sent: Donnerstag, 2. Februar 2006 16:10
> To: Jari Arkko
> Cc: [email-masked]
> Subject: [Autoconf] The case for address uniqueness
> 
> Hi all,
> 
> Well we have already had quite a lot of discussions related 
> to address 
> uniqueness and I strongly support Jari's point to make DAD optional 
> (especially if RFC2462 allows to do so). Actually I am in favor of 
> getting rid of DAD, only maintaining a minimal scheme to detect and 
> resolve address collisions when they occur.
> 
> Going back to discussions with Bob Hinden (on this list in 
> Feb. 2005 !) 
> about the possible use of unique local IPv6 addresses (now 
> RFC 4193) as 
> MANET-local addresses, Bob agreed (email dated 02/24/2005) that each 
> node could generate its own Global ID + subnet ID (56 bits), 
> to be added 
> to the EUI-64 (with 48 bits supposed to be unique from the 
> MAC address). 
> Moreover to make it even better, one could replace the ff:fe 
> pattern of 
> the EUI-64 with a random 16 bits pattern.
> 
> This leads to a total of 120 bits, with 80 random bits and a 
> sequence of 
> 48 bits which has a very high probability of being unique. 
> Additionaly 
> the 80 bits pattern could include machine-specific data that would 
> strongly increase the uniqueness of the generated address. 
> For example, 
> one could include the local date (in unix style, seconds 
> elapsed since 
> Jan. 1st 1970) when the address is generated: this is only 32 
> bits, but 
> is a very strong anti-collision feature. Indeed 2 machines having the 
> same MAC address, having generated the same random 48 bits (80-32), 
> would have an address collision if they created their 
> addresses at the 
> very same (local) date !... do we really need a strong DAD 
> mechanism to 
> handle such highly improbable event ?
> 
> Now if global connectivity is required, I personaly think that using 
> EUI-64 with the ff:fe pattern replaced with random bits is enough to 
> guaranty address uniqueness.
> 
> Just my 2 cents ... ;-)
> 
> Regards,
> Christophe
> 
> Jari Arkko wrote:
> > Simone Ruffino wrote:
> > 
> >> Anyway, my personal understanding was that AUTOCONF must 
> necessarily
> >> take address uniqueness into account, for two reasons: 
> Primarily, to 
> >> address specific problems of MANETs: for example, if two
> >> nodes have the same address, routing in the *whole* MANET 
> could possibly
> >> be compromised.
> >>  
> >>
> > Right. Yes, I think I understand this, now. Will this
> > happen always, or is this danger specific to some
> > MANET routing mechanisms?
> > 
> >> As a matter of fact, rfc2462 says also that DAD can be
> >> disabled in cases when its overhead outweighs its benefits.  
> >>
> > Right. I wouldn't use compliance with RFC 2462 as the
> > main reason for performing duplicate detection.
> > 
> >> My conclusion was that a uniqueness check must be defined 
> for MANETs,
> >> but that can possibly be disabled. For this reason, I 
> would like to have
> >> a solution which check uniqueness using an "optimistic" approach
> >> (something similar to optimistic DAD).  
> >>
> > Optional optimistic DAD is one approach. But that
> > still leaves some questions to decide. For instance, are
> > the manet-internal addresses and globally reachable
> > addresses the same or different? If they are different,
> > will they be allocated by the same or different mechanisms.
> > For instance, you could use something PACMAN-like
> > for the internal addresses, and then have the globally
> > reachable addresses allocated centrally from the gateway
> > (because obviously you need to be able to reach the
> > gateway or else these addresses aren't useful).
> > 
> > --Jari
> > 
> > 
> > _______________________________________________
> > Autoconf mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/autoconf
> > 
> 
> _______________________________________________
> Autoconf mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/autoconf
> 
> 

_______________________________________________
Autoconf mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/autoconf

---

From: Christophe Jelger <[email-masked]>
Date: Thu, 02 Feb 2006 18:14:33 +0100

Hi Kilian,

Thanks for your answer. Actually I understand your points, and such 
things have already been discussed on the list and *all these comments 
make sense*. Now I think it's time to get rid of our researchers' hats, 
and put on the engineers' hats: what's the easiest solution, and how can 
we quickly standardize a solution that works ? Everybody knows the IETF 
standardization is a very slow process, but it would be nice to converge 
to some solutions before it's too late for mass people to widely use 
MANET technologies.

See my comments inline below.

Best regards,
Christophe

> in your mail), but I want to raise awareness of the following related

Good start... in a very sarcastic way I realize that most people on the 
list agrees on this but still there is quite a strong human resistance 
against the simplicity of randomly-generated addresses. Just to be 
clear, I do not advocate the blind use of randomly-generated addresses, 
but rather want to stress the fact that DAD should be as lightweight as 
possible because the probability of collisions is extremely low.

> packets and may lead to permanent packet loss

I agree, but whatever solution one designs there can always be cases of 
address collisions (network merges, manually configured addresses). Thus 
I think the focus should be on address collision detection+repair.

> - Globally unique addressing is only possible with IPv6, not with IPv4

I am not sure what you mean by globally here: MANET globally or Internet 
  globally ? Just to make sure we are on the same wavelength, unique 
local IPv6 addresses are "site-local" and are not globally routeable. 
Now considering IPv4, if say I use private 10.0.0.0 class A addresses 
inside the MANET, I still have 2^24 different addresses (16 millions) so 
that's quite a low probability of collisions. Also note that the 
AUTOCONF charter is focused on IPv4 so I have to admit I don't really 
consider IPv4 .

> devices may not have globally unique hardware IDs at all (e.g., sensors)

Yes but as I said in my email, I still have another 72 bits (not 80 as 
wrongly written in my previous email) to make the difference !

> - Globally unique IDs may have negative implications on privacy (see

Great, so you're in favor of generating random EUI-64 ? ;-) So am I, and 
we now have 120 random bits to play with (note that unique local ipv6 
addresses are not global: they are not globally routeable so an address 
only needs to be unique inside the MANET).

> existing devices and hence significantly increase signaling traffic.

hmm .. not sure what you mean here but the main goal of using randomly 
generated addresses is to avoid signalling (i.e. to avoid DAD). Do you 
mean overhead of the routing protocol ? If yes, just note that whatever 
solution is designed for IPv6 the overhead is the same (howthe IPv6 
address is derived makes no difference: it's always 128 bits !).

> (see PACMAN paper referenced in my last mail).

I read it a while ago but will have a look asap.

> the DAD is efficient in terms of ressource consumption.

Still not sure what you mean by "globally" ... with respect to what ? 
MANET or Internet ?

---

From: "Charles E. Perkins" <[email-masked]>
Date: Thu, 02 Feb 2006 10:17:00 -0800

Hello Christophe,

I would like to support the view that we should
avoid requirements for a strong DAD mechanism.

Christophe Jelger wrote:

>
> I agree, but whatever solution one designs there can always be cases 
> of address collisions (network merges, manually configured addresses). 
> Thus I think the focus should be on address collision detection+repair.
>

I have two thought experiments that lead me to believe that duplicate
address detection is properly the responsibility for the nodes that own
the duplicated address.

(1): What if a node moves so fast between two parts of the network
       that it "seems" to be in two places?   One could easily imagine that
       such movement would fit within the time periods defined by local
       "hello" messages, depending on the range of radio transmission.

(2) What if one node leaves the network, and later rejoins?  This is
      certainly a network partition.  If each such event causes the network
      to initiate global signaling for DAD, then a meltdown is almost
      guaranteed eventually.  How can we distinguish between a reboot
      and a temporary node departure?  Is there any real difference as
      far as the network is concerned?

If the node itself detects duplication by any of several heuristics,
then it can (a) borrow a new temporary address and (b) take
corrective action.

Regards,
Charlie P.