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

From: "Kilian Weniger" <[email-masked]>
Date: Fri, 3 Feb 2006 10:14:38 +0100

Hi Christoph,

thanks for your comments. See my comments inline

> -----Original Message-----
> From: Christophe Jelger [mailto:[email-masked]] 
> Sent: Donnerstag, 2. Februar 2006 18:15
> To: Kilian Weniger
> Cc: [email-masked]
> Subject: Re: [Autoconf] The case for address uniqueness
> 
> 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.

Yes, I agree that a solution should be standardized quickly. I guess a
widely accepted approach is to develop a basic solution first and
optimizations (like the one I mentioned in my last bullet point)
later...

> 
> See my comments inline below.
> 
> Best regards,
> Christophe
> 
> Kilian Weniger wrote:
> > 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: 
> 
> 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.

we agree on that point.

> 
> > 
> > - Duplicate addresses have significant impacts on the 
> routing of data
> > 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.

Yes, I agree. 

> 
> > - 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 .

I guess you intended to say the charter focus on IPv6 ;)
Maybe the term "globally unique addressing" is mistakable. What I meant
with this term is the use of MANET-local IP addresses based on a
globally unique ID such as EUI-64. I was not talking about globally
routable addresses.

> 
> > - 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)
> 
> 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 !

I see. This signficantly reduces the probability of conflict, which
might make DAD dispensable.
Of course, users can still manually change the network interface IP
address...

> 
> > - Globally unique IDs may have negative implications on privacy (see
> > RFC3041)
> 
> 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).

Yes, I'm in favour of IPv6 addresses with random interface identifier as
well (BTW, I guess an EUI-64 cannot be random, right?).
With globally unique IDs I meant EUI-64-based (non-random) addresses.

> 
> > - Globally unique IDs must be long to be able to uniquely 
> identify all
> > 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 !).

What I meant is an optimization (used by PACMAN): The idea is that
signaling overhead can be significantly reduced if only a subset of the
bits are used. 
If, e.g., only 24 bits of the interface identifier are random and the
rest is set to zero, the IPv6 address can be compressed to a shorter ID,
which then is transmitted in routing protocol messages (instead of the
IPv6 address). Of course the probability of conflict increases, hence
you probably need some kind of DAD. But the savings in terms of routing
protocol overhead can be significant.

> 
> > 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).
> 
> I read it a while ago but will have a look asap.
> 
> > 
> > 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.
> 
> Still not sure what you mean by "globally" ... with respect to what ? 
> MANET or Internet ?

With globally unique ID I meant EUI-64-based addresses. With locally
unique ID I meant MANET-local addresses with a random
interface-identifier. Maybe Sorry, maybe this terminology is a bit
confusing...

Overall, I think your proposal of 72 random bits + EUI-64 (I prefer a
random interface identifier instead of EUI-64, mainly for privacy
reasons) may solve the network merging problem (without DAD) for many
scenarios from an engineering point of view, at least if we don't want
to consider that users may manually assign an IP address. It may be good
for a basic solution.
But I think we should at some point of time consider optimizations,
e.g., like the one I mentioned (use subset of bits to enable compression
of IPv6 addresses in routing protocol messages) in order to increase
scalability and support larger networks. Such an optimization requires
an efficient ongoing DAD.

Regards,

Kilian

> 
> > 
> > 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: Simone Ruffino <[email-masked]>
Date: Fri, 03 Feb 2006 12:12:20 +0100

Maybe address scoping could be addressed in the "MANET architecture" draft, which can be a starting point to reach an agreement on this. 

What do you think?

Regards,

Simone

> From: [email-masked] [mailto:[email-masked]] On Behalf
> Of Templin, Fred L
> Sent: giovedì 2 febbraio 2006 20.06
> To: Charles E. Perkins
> Cc: [email-masked]
> Subject: RE: [Autoconf] The case for address uniqueness
> 
> Charlie and others,
> 
> These discussions have been going on for so many years now that
> it seems they may never converge on a "one-size-fits-all" solution
> for MANET autoconfiguration. Is there a chance we could steer
> things toward a best current practices direction? If so, what
> would they look like, e.g.:
> 
>   - use IPv6 link-local for neighbor discovery
>   - use IPv6 Unique Local Addresses (ULAs) for intra-MANET comm's
>   - use DHCPv6 to get a globally unique address for Internet comm's
> 
> Is there a chance we will see some convergence soon or will the
> status remain quo for the forseeable future?
> 
> Fred
> [email-masked]
> 
> 
> > From: Charles E. Perkins [mailto:[email-masked]]
> > Sent: Thursday, February 02, 2006 10:17 AM
> > To: Christophe Jelger
> > Cc: [email-masked]
> > Hello Christophe,
> > I would like to support the view that we should
> > avoid requirements for a strong DAD mechanism.
> >
> > Christophe Jelger wrote:
> >
> > >
> > 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.
> >
> >
> >
> >

Gruppo Telecom Italia - Direzione e coordinamento di Telecom Italia S.p.A.

====================================================================
CONFIDENTIALITY NOTICE
This message and its attachments are addressed solely to the persons
above and may contain confidential information. If you have received
the message in error, be informed that any use of the content hereof
is prohibited. Please return it immediately to the sender and delete
the message. Should you have any questions, please send an e_mail to
[email-masked]. Thank you
====================================================================

---

From: "Green, David B RDECOM CERDEC STCD SRI" <[email-masked]>
Date: Fri, 3 Feb 2006 16:32:40 -0500

If the lower 64bit address identifiers in MANET AS router neodes are made with a guaranteed Unique IDentification (UID) numbers do we need DAD for IPv6 Unique Local Addresses (ULAs) and global addresses? 

David Green 
CERDEC Site Manager
SRI International
Office: (732) 532-6715
Mobile: (732) 693-6500

[Note: To reliably reach me with important, time-sensitive information, call my cell phone instead of e-mailing me.]  

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Templin, Fred L
Sent: Thursday, February 02, 2006 5:34 PM
To: Charles E. Perkins
Cc: [email-masked]
Subject: RE: [Autoconf] The case for address uniqueness

Charlie,

OK to most of what you said, but is there really such a thing as "stateless" address autoconfiguration without also requiring a robust DAD mechanism? DAD is hard in MANETs due to the reasons you gave in an earlier message (partitions and merges) and it won't be made easier when nodes start using interface ID generation mechanisms like CGA instead of assigning an interface's MAC address.
Can we rely on optimistic DAD and/or DAD avoidance?

Thanks - Fred

> Sent: Thursday, February 02, 2006 12:33 PM
> To: Templin, Fred L
> Cc: [email-masked]
> Hello Fred,
> ext Templin, Fred L wrote:
> 
> >These discussions have been going on for so many years now that it 
> >seems they may never converge on a "one-size-fits-all" solution for 
> >MANET autoconfiguration.
> >
> This may not be a good indicator, though, since autoconfiguration has 
> never been on the charter for MANET as far as I remember.
> 
> > Is there a chance we could steer
> >things toward a best current practices direction? If so, what would 
> >they look like, e.g.:
> >
> I would prefer not to make this constraint.  By doing so, the neighbor 
> discovery process is then required to suffer multiple rounds of 
> signaling just to get neighbors to know the node's useful IP address.
> 
> This sounds great for nodes that don't already have global addresses.
> 
> I would prefer a stateless approach whenever it's available.
> 
> I guess both are very possible.  It's up to us!  The fact that the 
> working group has been approved is a good sign, though.
> 
> Regards,
> Charlie P.
> 
> 
>

---

From: "Templin, Fred L" <[email-masked]>
Date: Fri, 3 Feb 2006 13:45:39 -0800

David, 

> From: Green, David B RDECOM CERDEC STCD SRI 
> If the lower 64bit address identifiers in MANET AS router 
> neodes are made with a guaranteed Unique IDentification (UID) 
> numbers do we need DAD for IPv6 Unique Local Addresses (ULAs) 
> and global addresses?

IMHO, the answer is no, you do not need DAD if you can
guarantee unique IDs in the lower 64bits of an IPv6
address simply because there are enough bits available
to ensure uniqueness to a high probability. But, if your
scheme is based on having lots of bits then does that
mean that you need to carry all of those bits in the
headers and address fields of all IPv6 packets you send?

Asked another way, does DAD avoidance through requiring
lots of bits for uniqueness purposes defeat IP header
and address field compression?

Fred
 
> David Green 
> CERDEC Site Manager
> SRI International
> Office: (732) 532-6715
> Mobile: (732) 693-6500
> 
> [Note: To reliably reach me with important, time-sensitive 
> information, call my cell phone instead of e-mailing me.]  
>   
> 
> [mailto:[email-masked]] On Behalf Of Templin, Fred L
> OK to most of what you said, but is there really such a thing 
> as "stateless" address autoconfiguration without also 
> requiring a robust DAD mechanism? DAD is hard in MANETs due 
> to the reasons you gave in an earlier message (partitions and 
> merges) and it won't be made easier when nodes start using 
> interface ID generation mechanisms like CGA instead of 
> assigning an interface's MAC address.

---

From: "Templin, Fred L" <[email-masked]>
Date: Fri, 3 Feb 2006 16:19:50 -0800

> and address field compression?

I am responding to my own post because I do not want to
create FUD. I do not know of any interaction between DAD
avoidance and IP header and address field compression,
but if anyone else does they are welcome to respond.

Fred