Subject: Re: [DNA] draft-ietf-dna-cpl-02.txt

From: JinHyeock Choi <[email-masked]>
Date: Wed, 01 Feb 2006 18:46:30 +0900

Dear Thomas

Thanks for your helpful and detailed feedback.

In the draft, mainly we try to present a way for a host to check for
link change, whether it remains at the same link or not, upon
receiving a single RA (with prefixes).

> I have some questions/comments/concerns on this draft.
>
> General: I think the overall direction of this draft is OK (i.e.,
> using prefixes to identify links), but I have some concerns about the
> specifics of what is described in this document.
>
> First, if I understand correctly, this is roughly what I think this
> document should be doing:
>
> Summary:
>
> This document assume routers implement RFC 2461/2462 and have not been
> upgraded with any DNA extensions. In addition, we assume that a node
> may move back-and-forth between networks it has previously
> visited. This could be be due to movement among a small set of links,
> or because of network "hiccups" that cause one to momentarily loose
> connectivity and then (re)connect to the same link again. This
> document describes how a host keeps configuration information about
> the links it has previously visited, attempting to reuse pre-existing
> configuration information (when it is safe to do so) rather than wait
> for the longer delay of going through the normal configuration steps.
>
> A host should maintain IP configuration info about "previous links"
> that it has connected to. That is, for each "previous link", it
> maintains the list of default routers, list of prefixes, MTU info,
> etc., as well as any relevant lifetime info. When connecting to a link
> (any link), a node always assumes it is connecting to a "new" link and
> starts the normal 2461/2462 procedures. In _parallel_, it also
> attempts to determine whether it is connected to a link it has
> connected to previously. When it get back an RA containing a prefix,
> it looks for that prefix in its "previous links" cache, and if it
> finds a match, it assumes it is rejoining that link.

The draft proposes that the node also assumes it is rejoining a new
link, if it doesn't find a match. To make such an assumption, the node
needs to keep the information of all the prefixes on a link.

> But, the current document includes a number of things that I am not
> sure are needed at all, and some that I think are backwards.
>
> 1) the document is rather long and verbose. I actually find the text
>   somewhat hard to follow, since the discussions seems fairly lengthy
>   given what I understand to be a fairly simple algorithm.
>
>   For example, it talks about numbers of times to transmit things,
>   etc. I think this is all covered in 2461/2462 and shouldn't be
>   mentioned here (I find it confusing to read about it because I'm
>   not sure what is "new" to DNA vs. what is just being taken from
>   other documents and should already be existing practice).

We try to make a host correctly declare a link change when it receives
an RA with only unknown prefixes. Without maintaining the Complete
Prefix List, that would be difficult.

> 2)
>
> >    If the host implementation does not provide any link-layer event
> >    notifications [9], and in particular, a link UP notification, the
> >    host needs additional logic to try to decide whether a received RA
> >    applies to the "old" link or a "new" link.
>
> IMO, we shouldn't bother with this case. Indeed, 2461/2462 don't have
> any text about this, and so to the degree that this is a problem for
> DNA, its also a problem generally. If anything needs to be said, it
> should simply be:
>
>    This document assumes that upon movement from one link to another,
>    a "link-up" event of some sort will be generated, so that the IP
>    layer is informed that a change of attachment point may have
>    occurred.
>
> Most if not all of Section 5 could safely be deleted.

It's ok for me to remove Section 5 unless WG objects it.

> 3) The entire discussion/text surrounding building a "complete prefix
>    list" seems unnecessary and from what I can tell, doesn't really
>    matter. That is, if you go back to the summary algorithm at the
>    top, it doesn't matter whether a node has a "complete prefix list"
>    or not; the algorithm works the same in either case. If you get a
>    prefix in an RA, and it matches one in your cache, voila, you have
>    found a link you were previously connected to. I don't see why it
>    matters whether you are 90% certain you have a complete prefix
>    list or not.
>
>    I wonder if all of section 3.1 could be removed.

The Complete Prefix List is to enable a node to correctly declare a
link change when the node get a prefix in an RA and it matches none in
its cache. Without the Complete Prefix List, the fact an RA includes
only unknown prefixes doesn't imply that the node is moved to a new
link.

> 4)  3.2  Erroneous Prefix Lists
>
> >    The host may generate either 1) the Incomplete Prefix List, i.e. the
> >    prefix list that does not include all the prefixes that are assigned
> >    to the link or 2) the Superfluous Prefix List, i.e. the prefix list
> >    that contains some prefix that is not assigned to the link.
>
> How does this happen? why should we worry about this case? 2461/2462
> doesn't...

The Incomplete Prefix List may result from packet losses and the
Superfluous Prefix List may result from the node mistakenly combines
the prefixes from different links to produce a single list. The first
may make a node mistakenly assume it has moved to a different link,
whereas the second may make a node mistakenly assume it remains at the
same link.

> >    work.  Thus the host needs to create a new Candidate Link object
> >    based on the received RA, and make this object the CCL.  However, it
> >    does not yet treat this as a new link; it is merely a candidate.
> >    Thus it MUST NOT perform the actions in Section 4.6 at this point in
> >    time.  Instead, the host should wait for MAX_RA_WAIT seconds, and all
> >    RAs that are received during that time interval are processed as
> >    specified above.
>
> Again, I think this logic is wrong (and too complex). You always
> assume a link is new as a starting point...
>
> or:
>
> >    Subject to local policy, and perhaps also the host's knowledge of the
> >    packet loss characteristics of the interface or type of L2
> >    technology, the host can try harder than just waiting for MAX_RA_WAIT
> >    seconds, by sending additional Router Solicitations.  It is allowed
> >    to multicast up to MAX_RTR_SOLICITATIONS [1] RS messages spaced
> >    RTR_SOLICITATION_INTERVAL apart.  In the most conservative approach
> >    this means a 12 second delay until the host will declare that is has
> >    moved to a new link.  Just as above, this process should be
> >    terminated should a new link UP notification arrive during the 12
> >    seconds.
>
> this seems overkill, as it doesn't take 12 seconds to configure a link
> in the first place... so why are we making this so detailed/complex?
> (and again why not just assume we are attaching to a new link, unless
> we learn otherwise?)

We present this as the most conservative approach and doesn't
recommend it. Even without the Complete Prefix List, it will take 4
secs to finish DNA according to our recommendation.

> 6)
>
> > 3.4  Renumbering
> >
> >    When the host is sure that the prefix list is complete, a false
> >    movement assumption may happen due to renumbering when a new prefix
> >    is introduced in RAs at about the same time as the host handles the
> >    'link UP' event.  We may solve the renumbering problem with minor
> >    modification like below.
>
> This will only happen if the RA is "weird' and includes only the one
> new prefix... In practice, it should carry more than one prefix. Why
> do we need to worry about this case?

We try to prevent weird cases from happening by explicitly writing
down its pitfall. :-)

> 7)
>
> 4.1: seems overly complicated to me.
>
> Whenever you get a link up, you assume you are at a new
> link. period. You then get RAs, and go from there, looking if they
> match anything in the "recently visited" set. If you find a match, use
> it. If not, you just continue doing normal ND/addrconf..

With our proposal, if you doesn't find a match, you can immediately
detect that you have moved to a new link and substitute existing
configuration information with new one. (It's also possible for you to
save the existing on for the future use.)

Thanks for your kind consideration.

Best Regards

JinHyeock

---

From: Thomas Narten <[email-masked]>
Date: Wed, 01 Feb 2006 09:23:40 -0500

> Prefix List, that would be difficult.

rereading section 4.5:  Receiving valid Router Advertisements,

I'm (generally) fine with the first part of this section. I.e., it
says that when a host receives the first RA (after a link up event):

1) if it contains a prefix in the CCL, assume no link change.

2) if it contains a prefix in retained Candidate Link Object, assume
   host has moved back to that link.

The interesting case is where one receives an RA containing only
prefixes that one has not seen before. It is this case that makes use
of the "complete" state. I.e., if the CCL is complete, one assumes
that learning a new prefix means an immediate move. But if the CCL is
not complete, one doesn't assume one has moved (yet). Specifically:

>  However, it does not yet treat this as a new link; it is merely a
>  candidate.  Thus it MUST NOT perform the actions in Section 4.6 at
>  this point in time.  Instead, the host should wait for MAX_RA_WAIT
>  seconds, and all RAs that are received during that time interval are
>  processed as specified above.

>    This processing might result in finding a prefix in common between a
>    Candidate Link object and the CCL, in which case the host knows
>    whether and to which link it has moved.  But should the MAX_RA_WAIT
>    seconds expire without any common prefix, then it will conclude that
>    it has moved to a new link and inform the rest of the host of the
>    movement (Section 4.6.) 

Could you clarify for me how the above relates to normal 2461/2462
processing? I.e., I would assume that the new prefix should be
configured on the link immediately. Is this the case?

Also, I'm not sure it's worth the complexity of waiting another 4
seconds to gather additional RAs before declaring a move.

Or maybe I don't understand what it means to "declare a move" and what
impact that has on the addresses configured on the interface. This
goes back to my message yesterday asking what processing we are
assuming happens upon a "link down" event.

Given that as far as we know,  most RAs include complete information,
why go to so much trouble to handle the case where this is not the
case, and where the cached information is "incomplete" (which also is
probably not the normal case), etc.

I agree that having a Complete Prefix List would be good, in the sense
that upon receipt of an RA, one is more likely to make a correct
determination about whether one has rejoined an existing link.

However, the current document formalizes this too much, including
algorithms that are used to (in some sense) "declare" when one has a
complete list as opposed to maybe not having a complete list. I'm just
not convinced (yet) that this complexity has sufficient benefit in
practice.

> secs to finish DNA according to our recommendation.

So, it takes 4 seconds to complete  DNA? I thought the whole point was
for DNA to complete quickly. Recall, using normal 2461/2462 in _MOST_
cases, a single RS will trigger the transmission of RAs from _all_
routers, and this will complete within .5 seconds. Thus, having DNA
operate for 4 seconds seems to miss the bigger picture.

Thomas

---

From: Syam Madanapalli <[email-masked]>
Date: Wed, 01 Feb 2006 21:11:19 +0530

> operate for 4 seconds seems to miss the bigger picture.

draft-ietf-dna-cpl-02 is for unmodified routers. Actual DNAv6 draft
can be found at

http://www.ctie.monash.edu.au/dna-dt/draft-pentland-dna-protocol3-pre02.txt

This protocol requires the modifications to both Routers (at least one
on the link)
and Hosts.

With this protocol, the host can make a link change decision with one
RS/RA exchange. This draft also defines Fast RA, which ensures that
two routers will not respond at exactly the same time while allowing
one of the routers on the link to respond immediately.

From the draft-ietf-dna-cpl-02
...
   MIN_DELAY_BETWEEN_RAS (3 Sec) + MAX_RA_DELAY_TIME (0.5 Sec)
   + network propagation delay is the maximum delay between an RS and
   the resulting RAs [1]. 4 seconds would be a safe number for the host
   to wait for the solicited RAs.  Assuming no packet loss, within 4
   seconds, the host would receive all the RAs and know all the
   prefixes.  Thus we pick 4 seconds as the value for MAX_RA_WAIT.
...

An implementation, may choose to compare the prefixes as and when
it receives an RA, if there is a common prefix, host can make the
decision that it is at the same link and need not wait for 4 sec.
4 sec wait may be required for the cases where there is a link change.

In most cases if the RA contains all the prefixes, the receipt of first
RA is sufficient to check for link change. In such cases a host can
wait for 4 sec to receive an RA, at that time the host can resend
the RS (the first RS might not have reached the router).

- Syam

---

From: Thomas Narten <[email-masked]>
Date: Wed, 01 Feb 2006 10:55:26 -0500

> draft-ietf-dna-cpl-02 is for unmodified routers. Actual DNAv6 draft

Yes, I understand this. My previous note was entirely within the
specific context of receiving an RA (that contained a prefix we didn't
know about) and how to handle that case.

BTW, I think it is useful to divide the problem space up three ways:

1) host recommendations for interacting with non-upgraded routers
   (i.e., those implementing 2461/2462)

2) hosts/routers that can BOTH be upgraded with DNA extensions (the
   protocol3 document)

3) changes to routers that would benefit unmodified hosts. (also
   contained in protocol3). I view this third category as "fixes" to
   2461/2462 that all routers should do and as small improvements on
   2461/2462.

while it may be OK to tackle cases 2&3 in the same document, I think
it would be good to make it more clear that case 3 is something we
want all routers to implement, and not just "if they want to support
DNA".

> RA is sufficient to check for link change.

Right. And since I expect this case to be common, its not at all clear
to me that we need to make the DNA algorith more complicated to deal
with cases that are not expected to happen much in practice.

Thomas

---

From: JinHyeock Choi <[email-masked]>
Date: Thu, 02 Feb 2006 18:33:24 +0900

Dear Thomas

> configured on the link immediately. Is this the case?

The new prefix is immediately assumed to be assigned on the currently
attached link (which is obvious). Main issue is what we will do with
the existing prefix list.

In case the host remains at the same link, the new prefix is added to
the existing prefix list. In case of a link change, the host makes a
new prefix list with the new prefix.

> assuming happens upon a "link down" event.

When a host declare a move, it should discard current IP configuration
information such as IP address. Declaring a move implies not only the
host's existing link is down but also the host  is attached to a
different link. So on the currently attached link, the host can't use
its existing configuration information and needs new one. The host
should configure a new IP address and re-establish its TCP connections
(assuming no MIPv6).

> not convinced (yet) that this complexity has sufficient benefit in

Usually a host will keep the Complete Prefix List and check for link
change with just one RA. Most complexity is from maintaining Complete
Prefix List to make DNA more precise/ stable.

> So, it takes 4 seconds to complete  DNA?

This is the worst case, an upper bound. In general DNA will be
completed upon the receipt of the first RA.

> I thought the whole point was

I agree that DNA is to complete quickly but think it also is to decide
correctly. We aimed both Speed and Precision (sounds like a NIKE ad.
:-))

Usually Speed and Precision is in a kind of trade off, the quicker you
decide, the less precise the decision. We try to strike a healthy
balance between them.

To increase the speed, we may make the policy that the host makes a
decision upon receiving the first RA (even without the Complete Prefix
List). But that will decrease the precision and may result in falsely
declaring a move. When a host declare a move, it should discard its IP
address and tear down TCP connections. Hence we recommend a different
policy for the host to wait up till 4 secs (this is upper bound) to
enhance the precision. It may worthwhile to wait a few additional
seconds instead of instantly jumping to the conclusion and tearing
down all TCP connections.

Best Regards

JinHyeock

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 02 Feb 2006 17:40:36 -0800

Thomas Narten wrote:

> [...]

We tried to make it clear that the host needs to separately track the 
prefixes it received before the link up and those that were received 
after, so that no matter what it does on the reception on the RA it can 
do the right thing should it later determine that it indeed moved to a 
different link.

Thus an implementation could immediately add the prefix to the current 
set of prefixes. But then should it determine that it did move to a 
different link it needs to remove that prefix from the old candidate 
link object, and only use that prefix in the new candidate link object.

Alternatively, an implementation could defer doing anything with the new 
prefix until DNA has completed. Then, if the host didn't move to a new 
link, it would add the prefix to the current list of prefixes. And if it 
did move to a different link it would know to only use the new prefix as 
the initial prefix list for that link.

> seconds to gather additional RAs before declaring a move.

Yes, but this is an unfortunate side effect of the generality of how 
prefixes can be advertised in RFC 2461/62. We know who to blame for that 
generality ;-)

> probably not the normal case), etc.

FWIW this observation was what lead to one of the early proposals by 
JinHyeock for how to make DNA better - just including a "this RA is 
complete" bit in the Router Advertisement.

> not convinced (yet) that this complexity has sufficient benefit in

The notion is really more probabilistic than "know for sure" vs. "don't 
know yet". But in terms of the resulting behavior, there is a point 
where the host behaves as if it knows all the prefixes for a link, hence 
the "declare" aspect seemed to help when describing the behavior. If it 
doesn't help, we can certainly revisit the description.

> operate for 4 seconds seems to miss the bigger picture.

If we want reasonably robust and fast DNA, we do need some changes in 
the routers behavior.

If we had a time machine and could go back and mandate in RFC 2461/62 
that the list of prefixes each router advertises on the link MUST be 
identical, and that all prefixes for the link MUST fit in a single 1280 
byte RA, then we could assume that every RA is complete.

But given that 2461/62 doesn't mandate that, we sort of have to deal 
with what's might be out there.

    Erik

---

From: Thomas Narten <[email-masked]>
Date: Wed, 08 Feb 2006 16:31:34 -0500

Here's a much longer attempt at describing the DNA landscape at a
high-level. My goals in writing this down include to be sure I
understand the current thinking in the WG, and to have it in text form
so that others can (hopefully) come up to speed more quickly. It may
also be useful to have some or all of this text appear in the
documents being worked on, to make them easier to understand. Finally,
I hope this allows us to break the problem space down better in a way
that allows us to talk about components individually and more
constructively.

At the end, I have a number of questions.

RFC 2461/2462 defines the IPv6 behavior for configuring a link with
IPv6 information such as addresses, MTU, on-link prefixes, etc. When a
link comes up for the first time, a host relies on RAs to provide the
needed configuration information. At the time 2461/2462 were written,
little thought was given to the details of how to process a "link
down" event (when one is available), or how to handle a "link up"
event for an interface that was previously up, perhaps only a few
seconds ago. With the increased proliferation of wireless networks, it
is now common to receive "link up" indications that may (or may not)
indicate that a configuration change has occurred at the IP layer
(i.e., one has moved from one link to another). DNA is the process of
(quickly) determining whether one is attached to a previously visited
link, in order to minimize service disruptions upon attaching to a
link.

DNA requires that a host keep track of the links to which it has
recently attached. For each known link, information about that link,
such as default router addresses, prefix information, MTU, Lifetimes,
etc. are kept in what are called Link Instances (aka Candidate Link
Objects in dna-cpl). Link Instances are identified by the set of
on-link global prefixes that have been advertised on that link, as no
prefix may be assigned to different links simultaneously. At any given
time, one LI is considered the Current LI, and the parameters
associated with the CLI are what are actually configured on the link
as defined in 2461/2462.

When a "link up" event is detected, a host will need to determine what
IP configuration parameters should be used. A simple (but naive)
approach would be to discard all associated information and initiate
the normal startup procedure as described in 2461/2462.  However, this
has the downside of causing upper-layer protocols using the (just
discarded) addresses to possibly receive "hard errors" and terminate
connections using those addresses.  In the common case where a link
goes away momentarily and then comes back up connected to the same
link (with the same associated config information) this is obviously
undesirable.

DNA takes the approach that upon reciept of a "link up" event, the
most-recently used configuration information should continue to be
used, and that DNA should be initiated to (quickly) determine whether
one is attached to a new link, or one to which one has been previously
attached.  In the simple case, DNA will quickly determine whether one
has reattached to the current link or to another known link.
Specifically, it will do so by sending a single RS and receiving a
single RA, one containing a prefix that it has seen before, thereby
identifying the link. In such cases, DNA can declare its work done,
and any new prefixes in the received RA are added to the CLI.

In some scenarios, however, things are more complex. Specifically, DNA
may receive an RA that contains only prefixes it has never seen
before. When this happens, it may not be sure whether the prefixes
correspond to a new link (i.e., one not visited before), or a
previously-visited link, but for which it has not yet seen all the
advertised prefixes. While it might be simplest to assume that receipt
of such an RA indicated attachment to a new link, that can lead to
(incorrectly) invalidating other configuration information for that
link. To handle this case, DNA takes extra steps. First, it
distinguishes between "complete" and "incomplete" LIs. Complete LIs
are those for which there is a high probability of having recieved all
prefixes being advertised on that link. Incomplete LIs are those for
which insufficient time has elapsed to conclude with reasonable
certainty that it is likely that all advertised prefixes have been
seen.

When DNA receives an RA advertising (only) unknown prefixes, and the
CLI is not "complete", DNA waits for additional RAs before deciding
whether the link is new or not.

The DNA procedure is tightly coupled with the use of 2461/2462, since
DNA uses the same messages. 

There are two variants of DNA. In the first variant, hosts interact
with routers that have implemented 2461/2462, but have not implemented
any DNA extensions. One of the key limitations in this case is that
RAs are not required to include all prefixes, so reciept of an RA from
a router is not sufficient to learn all the prefixes that (or other)
routers might be advertising. The DNA approach for handling this case
has been described above.  In the second variant, both hosts and
routers can be upgraded with DNA extensions. The proposed DNA
extensions in this case include:

a) routers are permitted to respond more quickly to received RSs, by
   having all routers on the link keep track of each other, and then
   stagger their responses so that if there are N routers present, one
   router responds during interval Time/N, the next during 2*Time/N,
   etc. [pentland-protocol3]

b) allow hosts to include a prefix in the RS that the router echos
   back in the RA, if the prefix is still valid on the link. That way
   the host can learn immediately if it is reconnecting to a
   previously visited link. [landmark option in pentland-protocol3]

c) have RAs include a "complete" bit, that routers set to indicate
   that the RA includes all the known RAs it is configured to
   advertise (plus the Learned Prefix Option described in d). This
   allows a host to quickly learn if any prefixes are being omitted
   from a particular RA.

d) Definition of a Learned Prefix option that routers use to proxy
   prefixes that they do not themselves advertise, but that they have
   observed other routers advertising. Hosts do not use those prefixes
   to autoconfigure addresses; they do use them to learn (in a single
   RA) all prefixes believed to be in use on that link. With this
   information, the host can definitively determine whether it is
   connecting to a new link or revisiting an old one.

Some key questions for DNA. 

1) when reusing "old" config, do we need to do anything special? E.g.,
   change state of ND entries to STALE? Put addresses in Optimistic
   state? Take into account how much time has elapsed since we were
   last attached (or just assume this happens as part of normal ND
   timers?)

   What harm can occur from continuing to use the same information?
   how does this compare with the harm of delaying the configuration
   of an interface until one is more certain?

2) Upon "link up", does DNA need to delay sending an RS per the
   2461/2462 rule? Are there ways to relax this that are consistent
   with the original concerns that led to the existing wording in
   2461/2462?

3) Upon "link up", what messages can host send that would help it to
   quickly determine if on same link? Is it just an RS? what about
   unicast? what about an NS (e.g., perhaps including a Landmark
   option)?

   Are there other messages that can be sent that could help? Like NS
   queries unicast to known routers?

   Note: on some links, like wireless ethernet, multicast is
   (relatively) "expensive". Would it be better to just send a few
   immediate unicast NS (or RS) messages to the routers we know about?
   and send a multicast RS only if the unicast fails? Or do both in
   parallel?

4) When one gets an RA containing prefixes that one has not seen
   before, is the algorithm in CPA sufficient or ideal? Are there
   other probes one could send? E.g., upon indication that a new prefix
   is available, send additional probes quickly to try and flush out
   things more quickly? Or, should the host keep additional info in
   LIs, e.g., keeping track of which router advertised what prefixes,
   so that it can distingish "prefix from previously unknown router"
   vs. "new prefix from router we've received RAs from before"?

5) When DNA determines that one is no longer connected to the same
   link as before, one swaps configs. Care must be taken to apply
   information learned from RAs received since last "link up" get
   applied to correct LI.

6) if DNA determines that was has reconnected to the same link, what
   else needs to be done? Rerun DAD? Do nothing? Does the answer
   depend on how long it has been since one was previously connected
   to that link?
   
7) Is there ever a time when one should discard still-valid prefix
   information on a link? That is, suppose a bogus router shows up and
   sends out an RA with prefix information with a long Lifetime. This
   information may stay associated with a link for weeks, because no
   router ever advertises the prefix with a Lifetime of 0. Pre-DNA,
   that info would presumably get discarded more quickly because one
   doesn't keep old LI information around. But with DNA, we may find
   this happens and causes problems. For robustness, it seems like it
   might be desirable to discard prefix information in the _absence_
   of RAs containing that prefix, in the case where other RAs continue
   to be received with other prefix information. I.e., if one knows
   that one has missed (say) N RAs, time out the info if one is
   receiving other info from other routers.  (note: the situation is
   further aggrevated by having routers cache RAs learned from other
   routers.)

Thomas

---

From: Bernard Aboba <[email-masked]>
Date: Wed, 08 Feb 2006 21:28:28 -0800

\>    Are there other messages that can be sent that could help? Like NS
>    queries unicast to known routers?

This is what DNAv4 does (via unicast ARP), because this enables a 
determination of whether the host has connected to a previously encountered 
router, without ambiguity.

>    and send a multicast RS only if the unicast fails? Or do both in

DNAv4 does both DHCP and DNA in parallel.  DNAv4 is handled solely via 
unicast ARP, because on some links multicast not only is sent to many more 
hosts, but also is sent at much lower  rate.   For example, with IEEE 
802.11n, it would be possible to send *a hundred*  unicast packets at 100 
Mbps at the same cost in expended slots as  one multicast packet at 1 Mbps.  
This means that in practice a single multicast RS will cost more than 
sending unicast RS or NS messages to all previous routers.

---

From: Thomas Narten <[email-masked]>
Date: Thu, 09 Feb 2006 08:31:00 -0500

> router, without ambiguity.

Indeed, the DNAv4 approach is what led me to ask that question.

DNAv4 uses ARP. Shouldn't we think about using an NS? It's unicast,
and already includes the "R" bit, so we know whether the node is a
default router or not. Perhaps it make sense to add some options that
benefit DNA. (The same options could be used in RSs too, if that makes
sense.)

One issue that seems to be carrying a lot of weight on the DNAv6 side
is that with RS/RAs, one (only) learns the router's link-local and
link-layer addresses. But these two together are insufficient to
uniquely identify a link, since both can be used on different links at
the same time.

Why not allow inclusion of a landmark option in an NS/NA? One benefit
of an NS is that we presumably don't have to delay sending one, and
the responder doesn't delay in responding. So this can be very fast.

Another thought I have. When one gets a "link up" event, one wants to
know if one is reattaching to a previously known link. The
pentland-protocol3 draft assumes that the best way do do that is by
including all prefixes in RAs.

However, this has the disadvantage that routers have to listen to
other RAs and (effectively) do a proxy advertisement for prefixes it
itself is not advertising. I have some fairly strong qualms about that
approach...

On the other hand, a lower overhead mechanism would be to be able to
ask "are you the same router on link Foo that I was talking to
previously?" If the answer is yes, one can conclude that one is on the
same link as earlier. One way to do this might be to define a new
option, called (say) the Link/Interface Identifier option, that serves
as a sort of globally unique identifer for an interface on a specific
link. The router could generate the identifier by (say) hashing its
link-local address, internal serial number, internal interface
identifier, and time of reboot. The idea is that even if a router used
the same LL address (and link-layer address) on multiple interfaces,
the Link/Interface Identifier would be different on the different
interfaces.

One benefit of an approach like this is that a router can generate the
identifier using only local information, without coordinating with
other routers.

A host could then (say) send an NS, and ask the responder to include
that Link/Interface Identifier option.

> sending unicast RS or NS messages to all previous routers.

I'm also a bit worried that one time DNA will get used a lot is at,
say, IETFs where the network is barely functioning. That seems like
the wrong time to have a bunch of nodes invoke DNA at the same time
and all send out multicast RSs...

Thomas

---

From: Greg Daley <[email-masked]>
Date: Thu, 09 Feb 2006 09:40:58 -0500

Bernard Aboba wrote:
> determination of whether the host has connected to a previously
> encountered router, without ambiguity.
> 
> unicast ARP, because on some links multicast not only is sent to many
> more hosts, but also is sent at much lower  rate.   For example, with
> IEEE 802.11n, it would be possible to send *a hundred*  unicast packets
> at 100 Mbps at the same cost in expended slots as  one multicast packet
> at 1 Mbps.  This means that in practice a single multicast RS will cost
> more than sending unicast RS or NS messages to all previous routers.

Actually, if the switches monitor multicast groups, the packet will
be sent toward the AP as unicast with the toDS bit set, and won't be
retransmitted over the wireless LAN.  The wireless transmission
therefore can operate at a higher rate available to 802.11n.

Greg

---

From: Bernard Aboba <[email-masked]>
Date: Thu, 09 Feb 2006 07:52:24 -0800

>DNAv4 uses ARP. Shouldn't we think about using an NS?

Personally, I think it makes sense.  In fact, I believe that DNAv4 
implementers are already considering this, if they haven't implemented it 
already.

>uniquely identify a link, since both can be used on different links at

Right.   DNAv4 does not use link-local addresses, so this problem does not 
arise.

>the responder doesn't delay in responding. So this can be very fast.

Right.  Not only can the packets be sent without delay, but sending them via 
unicast also reduces delays due to frame loss on links such as 802.11 which 
do not retransmit multicast packets (from STA to AP) at the link layer.

>itself is not advertising. I have some fairly strong qualms about that

Yes, I also have reservations about it.

>same link as earlier.

Yup.

>and all send out multicast RSs...

Yes.  As part of the DNAv4 work, we did an analysis and discovered that 
sending multicast packets was *much* more likely to result in a network 
meltdown than using unicast.  This was not only because of the multicasting, 
but also because of the link layer interactions, such as much lower rates, 
lack of link layer retransmission, etc.

In fact, the effects are so strong that sending multiple unicast frames in 
parallel is more efficient than a single multicast.

---

From: Greg Daley <[email-masked]>
Date: Thu, 09 Feb 2006 10:51:52 -0500

Hi Thomas,

I like your description.

I'll go down to the questions section and see if there's
something I can add.

>    last attached (or just assume this happens as part of normal ND

I don't think you should change the ND cache state unless the 2461
timers indicate you should (Except if you're no longer on a link).
It's an exposure of about 30 seconds (+DELAY+PROBE).

With regard to addresses, even if you return to the same link, any
period of absence is one where you may have missed a DAD NS
(albeit with low probability).

If you arrive back within a second, you would probably see the
NA O=1 to all nodes from the node which started DAD while you were
away.   Placing the addresses in Optimistic state makes sense here,
but it may not be necessary to send an NS (opinions welcome).

If you've been away for an entire second, the host may arrive back
after DAD has completed on a peer node.  A full optimistic DAD would
be required.

>    of an interface until one is more certain?

RT Voice transfer is out of the picture if you cannot configure the
interface quickly (few 10s of ms).

If the time to configure the addresses is greater than approx 1/2 RTT,
TCP timeout is likely to occur.

Depending on how using the same information occurs, return in under a
second is unlikely to damage anyone who isn't doing optimistic DAD
themselves (There are warnings in opti-dad about potential for failure).

If the host doesn't watch for NAs, then it may be unaware of the
competing nodes .

>    with the original concerns that led to the existing wording in

There's new text in RFC2461bis, saying that if the link-layer indicates
you may have moved, it is possible to send an RS immediately, if the
link-layer is likely to serialize devices coming onto the medium.
draft-ietf-dna-hosts provides guidance on what to do with hints,
especially from link-layer and indicates when it is not possible
to immediately solicit (S 5.5).

>    and send a multicast RS only if the unicast fails? Or do both in

Please note that the main problem in DNA is when the host has moved.
When the host has not moved, we don't really need to do much.

Therefore the additional packet to check "are we here?" to a known
destination doesn't help us achieve rapid change detection in the
important case.

When a host has moved, it is not possible to identify a unicast
destination for a querying packet a-priori.

This is why we've used multicast.   Perhaps there is a way for all
links to have the same (MAC) unicast destination for a serving router,
which would avoid the issue of the multicast RS leaking back onto a
wireless LAN.  There are other ways of dealing with this issue
today though (e.g. group filtering).

Ideas like special destinations have been discussed previously off-list,
but have the issue that they require modification to routers.

RS/RA has the advantage that it is always there, and if people
wish to improve its performance in scheduling or efficiency,
it is possible to upgrade it (or potentially the network it is on??).

>    vs. "new prefix from router we've received RAs from before"?

I think the distinction you make about added prefixes is
interesting, but without a PIO (perhaps with the Router Address (R)
flag set) in common it's really too difficult to identify if this
is really the same router because the addressing is link-local --
I mean you can guess, but it may be a different link.

As the router address flag isn't in wide use, this isn't so easy,
unless there was a common prefix between the RAs -- in which case
CPL works anyway.

>    information learned from RAs received since last "link up" get

Yes.  This is relatively easily done (in the implementation) by
moving aside the LI when the link-indication is received, and
testing received packets until either:

the expiry of the New LI build (if the existing LI was not complete).

amalgamation of the LIs, due to a common prefix

or replacement due to disjoint prefixes (if the existing LI was complete)

>    depend on how long it has been since one was previously connected

As we discussed above, my guess is that immediate (<1s?) return has some
potential danger (low probability) due to duplicate addresses.
I don't think additional packets are warranted though.

Longer disconnections should have a complete DAD, whether original or
optimistic.  Group joins and ND cache state should be governed by
existing timers, AFAICS.

>    further aggrevated by having routers cache RAs learned from other

Well, I don't think it's really that useful to keep cached information
for a long time after you have departed a link.

In draft-ietf-dna-hosts  Section 4.1, a maximum cache time is
described which tackles out of date information such as this,
and may be used to limit the effective lifetime of stored information.

This doesn't actually reduce the valid lifetime of the prefix,
though, but may age out the router state quickly.
Perhaps we should have a look at this further if you think
it's moving in the right direction.

In that case it may be necessary to attempt to tie the RA to
the PIO as in (Q3), although this would be to compare within
the same link and not between links for the purpose of
link-determination.

I hope this helps.

Greg

---

From: JinHyeock Choi <[email-masked]>
Date: Mon, 13 Feb 2006 23:46:40 +0900

Dear Thomas

Thanks for a clear and neat summary. Except a few minor points, I am
of the same opinion. Also I think that we'd better write down a bird's
eye view on DNA in some place.

> attached.

I'd like to make a clarification. IMO, upon "link up" event,
though a host can keep the existing configuration information,
it should not use the information until DNA procedure confirms
that the host remains at the same link.

For example, a host can retain its current IP address but should not send
a packet with the address as a source address till DNA comletes.

We'd better make this clear and explcitly write it down.

>   of an interface until one is more certain?

It may cause address conflict if a host continues to use the existing
'IP address' without DAD. While the host is away from the link, it's
possible that another node happens to configure the host's IP address,
because there was nobody to defend the address.

Also during the absence, a router/prefix may be removed from the link
with the RA/PIO with explicit indicaiton. Since the host didn't
receive the explict indication such as PIO with lifetime=0, it may
falsely assume that router/ prefix is still there.

>   with the original concerns that led to the existing wording in

I think 2461bis allows an immideate RS for mobile nodes.

>   and send a multicast RS only if the unicast fails? Or do both in

With RS/ RA, I think DNA performs better in case of actual link change.

In case a host moves to a new link, it needs an RA for new
configuration anyway, so it seems reasonable to send RS in
anticipation of a link change. Also if you use unicast meessage to
known destinations, no reply will come when you have moved to a new
link. This will result in delay since you can't but rely on timeout to
detect a link change.

For your concern about multicast, I am happy to say that you may use
FRD (draft-ietf-dna-frd-01) to remove multicast packets entirely from
the air. :-) In brief, AP keeps a suitable RA and forward it to the
host upon a new attachment.

>   depend on how long it has been since one was previously connected

Right now, DAD seems to be the main problem but we may need to think this more.

>   further aggrevated by having routers cache RAs learned from other

This also needs more thoughts. Within Design Team, there were some
arguments over the dormant node awakening case. If a prefix is removed
while a node is dormant, upon awakening, the node mistakenly assume
the prefix is valid until it's lifetime, which may be quite long,
expires.

Best Regards

JinHyeock

---

From: JinHyeock Choi <[email-masked]>
Date: Mon, 13 Feb 2006 23:57:49 +0900

Dear Greg

> after DAD has completed on a peer node.  A full optimistic DAD would

It make sense to differentiate host's behavior according to the time
of absence. The longer a host is absent, the more care it should take.
BTW how a host can measure its time of detachment? Shall this require
a precise link-down event notification?

> destination for a querying packet a-priori.

agree.

> it is possible to upgrade it (or potentially the network it is on??).

Kindly be aware that we can avoid multicast in the air with FRD. :-)

Best Regards

JinHyeock

---

From: Greg Daley <[email-masked]>
Date: Mon, 13 Feb 2006 10:05:35 -0500

JinHyeock Choi wrote:
[cut]
> a precise link-down event notification?

I'd guess that link-down indications could be used to allow for
more selective behaviour, if there's knowledge of detachment time.

[cut]
> Kindly be aware that we can avoid multicast in the air with FRD. :-)

Indeed.

Greg

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 14 Feb 2006 00:06:45 +0900

Dear Bernard

> do not retransmit multicast packets (from STA to AP) at the link layer.

In case a host remains at the same link, the response can be fast
without trouble. However, in case a host moves to a new link, nobody
will respond and I can see no way for the host to realize a link
change except time expiry. That would take some time. Am I missing
something?

Best Regards

JinHyeock

---

From: Thomas Narten <[email-masked]>
Date: Mon, 13 Feb 2006 10:09:38 -0500

> a packet with the address as a source address till DNA comletes.

Why?

I've thought about this some, and the question I ask is "what breaks
if a host does send such packets?" If that answer is "nothing", then
no harm done.

It may be that sending such packets is useless, but that's not a
problem. If it actually causes things to break or bad things to
happen, then yes, we should think about disallowing such behavior. But
lets evaluate the cost/benefit explicitly.

Thomas

---

From: Thomas Narten <[email-masked]>
Date: Mon, 13 Feb 2006 10:16:20 -0500

> falsely assume that router/ prefix is still there.

I think we need to think hard about how much we are going to
complicate DNA to deal with "broken renumbering attempts", which are
not supposed to happen in the first place. The IPv6 protocols do not
really support taking away a prefix prematurely, and when this
happens, things aren't guarnteed to work. Thus, this is not advisable
in general.

So we should explicitely discuss to what degree DNA needs to support
such events, especially if they are not expected to be common.

Thomas

---

From: Thomas Narten <[email-masked]>
Date: Mon, 13 Feb 2006 10:12:21 -0500

> because there was nobody to defend the address.

IMO, we may want to think about having a separate discussion about
"when to run DAD". The blanket "rerun DAD at all times there is some
doubt" strikes me as overkill. For example, why rerun DAD if one has
been disconnected only 10 seconds? or 30? Maybe we should if we've
been disconnected for an hour (but then, do we need to bother with
DNA?).  Also, why rerun DAD if one has generated an address using the
IEEE Identifier (and one has run DAD on it before)? That is, different
types of addresses have different "probability of possible collision"
risks in terms of other hosts attempting to use such addresses.

Thomas

---

From: Greg Daley <[email-masked]>
Date: Mon, 13 Feb 2006 10:20:01 -0500

Hi Thomas,

Thomas Narten wrote:
[cut]
> lets evaluate the cost/benefit explicitly.

I agree.

This was actually one of the first topics on the mailing list a _long_
time ago.  There's no need to specify that packets can't be sent until
DNA completes, as globally addressed packets (except ND) can't interfere
with packet streams when sent from another link.

There may be problems for TCP if these packets are wasted, but I
don't think that's necessarily DNA's direct responsibility at
this stage (we don't even have the base protocol standardized).

Greg

---

From: Thomas Narten <[email-masked]>
Date: Mon, 13 Feb 2006 10:20:29 -0500

> I think 2461bis allows an immideate RS for mobile nodes.

Can you cite text? And I hope they don't make an exception just for
"mobile nodes".

> link. This will result in delay since you can't but rely on timeout to

But one can also imagine parallel approaches. E.g, for the default
routers on the list, measure the actual observed RTTs during NS/NA
exchanges. Then, for DNA, send out an NS, using that RTT as an
estimate of how long you are willing to wait (and I'd expect this to
be very short, like 10ms or less). If that doesn't work, then fall
back to RS. One can imagine other optimizations.

> host upon a new attachment.

This is the IETF; we work at the IP layer. We don't know about
link-layer specific things like "access points". (I'm actually fairly
serious here.)

Thomas

---

From: Greg Daley <[email-masked]>
Date: Mon, 13 Feb 2006 10:30:18 -0500

Hi Thomas,

Thomas Narten wrote:
[cut]
> such events, especially if they are not expected to be common.

This is an issue which is addressed in the draft-pentland-dna-protocol3
document (accepted as WG draft), and was resolved by the DT.

The DNA protocol describes how existing ND timers are used, and also
places a time limit on the retention of inappropriate prefix
information.

Additionally, if a trusted Complete Router Advertisement is sent,
DNA systems will discard any prefix information regarding a
disused address prefix, regardless of whether the host saw the
prefix advertised with decreased lifetime.

(It's done already - and not too complicated).

Greg

---

From: Greg Daley <[email-masked]>
Date: Mon, 13 Feb 2006 11:00:39 -0500

Hi Thomas,

> risks in terms of other hosts attempting to use such addresses.

Personally, I'm really loathe to introduce any situation where DAD
is neglected, as it's really an all nodes or none approach.

That said, we can certainly be a lot more clever about DAD and
not sending DAD-NS packets inappropriately.

I think it may be worthwhile to RECOMMEND that hosts do optimistic
DAD if they have been away longer than a second, on the understanding
that this shouldn't necessarily result in packets being sent
to the link.  In fact, explicitly rate-limiting active DAD NSs
may be a good idea.

It's notable that the collision rates for pseudo-random variables
produce as low as 1 in 2^62 chance that collisions occur.

Ideally with IEEE identifiers, multiple devices can't have the same
address.  I've worked for an organization where (in the early days) an
entire box of NICs had the same MAC address.  Additionally, MAC
addresses may be programmed into cards (0x00FEEDABBA01) without
the Layer 3 necessarily knowing.

So the probability of collision is potentially higher than that
for (say) CGA addresses which use SHA-1, or 3041 addresses which
actually follow the recommendations of RFC1750.

That said, neither of these are guaranteed either.

Optimistic DAD may be useful as a passive system as it ensures that
the re-arriving node doesn't displace the state held by a router.
So assuming that no DAD NS is sent, the DNA host has to remain
optimistic until it has performed the operation (which could be
strongly rate limited, when remaining in the same link).

A host which doesn't need to talk directly to neighbours (but can
learn addresses of routers through RA) can still operate effectively
even though it can't send multicast NS's and cannot send an NA,O=1.

If the router isn't sending you packets for a while, and if the
host's NCE for the router goes to PROBE (haven't worked this part
out yet), the host will send a unicast NS, but won't be able to
get back a response from the router, if there's an existing NCE for
another device. In the case of no response, it's time to send DAD
NS, if DNA still indicates the router is available.

If there's no existing NCE, the router will resolve the host, which
will NA O=0 to the router, and the router can send the NA based on the
new NCE.

If the router already had the NCE of this device, DAD NS can be delayed
further until Neighbour Resolution is required, or a timer expires.

So if a host is prepared to accept optimistic operation, and not send
a DAD NS, it's possible to reduce the rate of messages without
necessarily impinging on DAD.

Greg

---

From: Greg Daley <[email-masked]>
Date: Mon, 13 Feb 2006 11:44:23 -0500

Hi Thomas,

> Can you cite text? And I hope they don't make an exception just for

S6.3.7 draft-ietf-ipv6-2461bis-05.txt

   In some cases, the random delay MAY be omitted if necessary. For
   instance, a mobile node, using [MIPv6], moving to a new link would
   need to discover such movement as soon as possible to minimize the
   amount of packet losses resulting from the change in its topological
   movement. Router Solicitations provide a useful tool for movement
   detection in Mobile IPv6 as they allow mobile nodes to determine
   movement to new links. Hence, if a mobile node received link layer
   information indicating that movement might have taken place, it MAY
   send a Router Solicitation immediately, without random delays. The
   strength of such indications should be assessed by the mobile node's
   implementation depending on the level of certainty of the link layer
   hints and is outside the scope of this specification. Note that using
   this mechanism inappropriately (e.g. based on weak or transient
   indications) may result in Router Solicitation storms. Furthermore,
   simultaneous mobility of a large number of mobile nodes that use this
   mechanism can result in a large number of solicitations sent
   simultaneously.

[cut]
> back to RS. One can imagine other optimizations.

Such an optimization may work, but its effectiveness is dependent
on topology (single cell links would experience longer delays),
and the amount of time available to upper-layer applications (for
example, voip).

It makes sense to mention this idea as an optimization to reduce
the effect of multicasts on the link-layer.  I'd suggest inclusion
of a tentative link-layer address option, as the source
address of the NS is likely to be considered optimistic for DAD
purposes (it may not help, but may avoid the reverse NS/NA exchange
if the router doesn't have the host in the NCE).

How about:

"...
Multicast transmission has been shown to increase bandwidth
consumption on certain wireless media at a rate much greater
than that caused by unicast transmission.   On such media,
it MAY be useful to send a unicast NS transmission
to the global address of one of the configured routers upon
reception of a link-layer hint.  This would avoid transmission
of a multicast Router Solicitation if the router was available.
The RS could then be delayed for an interval corresponding to
the duration required to receive the unicast NA, if the router
is still reachable.

This optimization is dependent on topology, and increases delay
and packet transmission if the link is composed of a single cell.
Additionally, hosts with applications that are not able to delay
for the lost NA in case of link-change SHOULD use RS instead.
..."

Sending to the link-local address is insufficient, as some
devices have been known to share a MAC address across different
NICs, and CGAs with common public keys will be the same for
two interfaces on one router, as the link-local prefix and key
are the same.

Actually, if the NS contained a landmark option and the router
was a known DNA router, you could send to any address.

Greg

---

From: Bernard Aboba <[email-masked]>
Date: Mon, 13 Feb 2006 11:20:22 -0800

>doubt" strikes me as overkill.

Right.  DNAv4 does not require rerunning DAD.  In fact, doing this every 
time will cause scalability problems particularly in the case of a power 
failure where many hosts simultaneously reboot.

---

From: Bernard Aboba <[email-masked]>
Date: Mon, 13 Feb 2006 11:22:27 -0800

>happens, things aren't guarnteed to work. Thus, this is not advisable

Right.  DNAv4 assumes that a DHCP lease, once given out, is valid until it 
expires.  I agree that trying to take this into account adds needless 
complexity to DNAv6.

---

From: Bernard Aboba <[email-masked]>
Date: Mon, 13 Feb 2006 11:26:46 -0800

>back to RS. One can imagine other optimizations.

DNAv4 does both DHCP and ARP in parallel -- so that the DNAv4 procedure is 
never slower than DHCP.

---

From: Bernard Aboba <[email-masked]>
Date: Mon, 13 Feb 2006 11:18:47 -0800

>if a host does send such packets?" If that answer is "nothing", then

In DNAv4, there is a potential issue with private addresses (e.g. a host 
could move from one private network to another one, resulting in an address 
conflict), but I don't think there is an analog here.

>lets evaluate the cost/benefit explicitly.

At worst the host will send some packets with the wrong address, then the 
address will change.

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 14 Feb 2006 18:25:10 +0900

Dear Thomas

> lets evaluate the cost/benefit explicitly.

If a host has moved, such a packets are useless and wasting up
wireless bandwidth. But 'should not' may be a too strong word and
'would better not' would be better.

Also I should have picked a better example. How about neighbor
information? If a host immediately sends packets with the existing
link-layer addresses from cache, those packets would be lost in case
the host moved to a new link.

In cost/ benefit comparison, what will be the benefit for a host to
use the information which may not be valid?

DNA will be completed just after 1 RS/ RA exchange and that will not
take much time. So I think it may be better to wait for DNA
completion, just a few MSs, rather than risking using the invalid
information to waste up bandwidth.

Best Regards

JinHyeock

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 14 Feb 2006 18:29:29 +0900

Dear Thomas

> Can you cite text? And I hope they don't make an exception just for

9th bullet of APPENDIX F: CHANGES FROM RFC 2461 from 2461 bis

    o Allowed mobile nodes to be exempt from adding random delays before
      sending an RS during a handover.

> back to RS. One can imagine other optimizations.

Allow me to clarify the above. I understand that, according to your suggestion,

Upon receiving link-up indication, an MN sends an unicast NS to a
known router (or routers) and waits for a certain amount of time
(based on measured RTT value). Upon the time expiration, the MN sends
an RS to get an RA.

Am I right?

If so, this will certainly save packets in case the MN stays at the
same link. But in case of a link change, there will be an additional
delay for NS/ NA exchange and we need to measure RTT which may vary
drastically in wireless environment.

Best Regards

JinHyeock

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 14 Feb 2006 18:31:06 +0900

Dear Greg

> for the lost NA in case of link-change SHOULD use RS instead.

The above changes the existing DNA solution procedure, so I think we'd
better investigate it from the various angles. I am concerned about
relying on RTT value which may be volatile in wireless environment.

Best Regards

JinHyeock

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 14 Feb 2006 18:32:23 +0900

Thomas

> doubt" strikes me as overkill.

ok.

> For example, why rerun DAD if one has
> DNA?).

ok but we need to measure actual detachment time with some precision,
which may be complicated. For example, exactly when an L2 link is
becoming down? In 802.11 case, upon completing association procedure,
we can say that an L2 link is up. But a wireless link can be down
without any formal procedure (such as de-association) because of
deteriorating channel condition.

Best Regards

JinHyeock

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Feb 2006 09:52:34 -0800

> associated with the CLI are what are actually configured on the link

I'm not sure all the information about the link needs to be retained 
(default router address, MTU above). What is strictly necessary is the 
information to tell which link it is, i.e. the prefixes and their 
lifetimes. In particular, the list of default routers for a particular 
link might change a lot more frequently than the set of prefixes 
assigned to the link.

I think "on-link global prefixes" above would be a bad idea; we don't 
want to restrict this to the case when on-link prefixes are advertised, 
because for media where multicast is expensive (IEEE .15.4 and .16) 
folks are discussing ways to avoid multicast NSes; one way to do this is 
to not advertise any on-link prefixes (but advertise prefixes with the A 
bit set) which results in the packets being unicast to the default 
router per standard RFC 2461.
So I think DNA should operate using prefixes that have either the L 
(on-link), or the A (addrconf), or both bits set.

> link (with the same associated config information) this is obviously

The last sentence seems to say that a link is connected to a link (the 
link goes away and then comes back up connected to the same link).
If we want to be more careful about terminology we would state that the 
'link up' and 'link down' events do not signal anything about the link 
itself; they merely signal something about the attachment point to the 
link. Thus it makes sense to say the attachment point goes down ('link 
down' event) and them comes back up and is connected to the same link.

> and any new prefixes in the received RA are added to the CLI.

In the above description it isn't clear to me whether you are discussion
  - how CPL works
  - how dna-protocol works
  - some fundamental statement which spans the two

It is clearly highly desirable to handle this with the receipt of a 
single RA, and that RA should arrive as soon as possible. But the "as 
soon as possible" requires changes to the router as specified in 
dna-protocol.

> whether the link is new or not.

In the above paragraphs by "DNA" you appear to mean "CPL", right?

If you want to give an overview of the combination of dna-protocol* and 
CPL, then you need to modify the text. And the "two variants" below 
makes me believe that is what you are trying to accomplish.

> any DNA extensions. 

I actually don't think they are variants.
I'd expect a host to send a single RS that is capable of doing the best 
possible whether the routers support just 2461 or support the DNA 
extensions.
We don't want the host to have to guess which form of routers there are 
on a potentially new link before it sends the first RS!

But due to having two separate documents, the combination isn't written 
down anywhere, so it isn't unreasonable for folks to think there are two 
variants.

>    last attached (or just assume this happens as part of normal ND

Good questions.
For DAD I think it makes sense to always switch to optimistic state even 
for a short link down or when a link up arrives without a preceding link 
down. This is ok since doing that, and not sending any DAD probe, is not 
expensive.
Once a RA arrives indicating that the host did not move, then the 
optimistic mode can be turned off.

For ND state of STALE the situation is similar to the default router 
list and other cached information. If the host has been disconnected 
from the link for a fraction of a section or a few seconds, it might 
have missed some important packet (such as an unsolicited NA telling it 
that the L2 address of a neighbor has changed, or an unsolicited RA 
telling it that a router is going away.) But it could have missed such a 
packet due to bit errors even if it was connected to the link. And we 
have NUD as a way to recover from those cases, so why not use unmodified 
NUD to recover from the case when the host was disconnected for a while.
Of course, if the host determines that it has moved to a different link, 
then the information in the neighbor cache isn't useful any more.

I don't think we need extra timers for this; the existing timers (for 
default router list entries, NUD probing, etc) are ok, since they are 
(supposed to be ;-) ok when the host remains attached to the link. Thus 
the argument about packet loss caused by bit errors vs. packet loss 
caused by being detached from the link apply here as well.

>    with the original concerns that led to the existing wording in

What is important is that DNA doesn't cause a flood of packets that 
makes things worse.
I think somebody sent a reference to a paper on a study of 802.11 using 
a bunch of stations moving together (think of a vehicle with many 
devices) and found that the L2 association meant that the 'link up' 
events were already spread over time.

>    unicast? what about an NS (e.g., perhaps including a Landmark

The WG has talked about NS in the past, in particular an NS to the old 
default router(s).
This is an extra packet (a RS plus an NS instead of just an NS).
And since neither the routers L2 address nor the routers link-local 
address need to be globally unique, the fact that the NS gets a response 
doesn't mean the host is still attached to the same link.

>    queries unicast to known routers?

The host would have to know a global IPv6 address of the router, and the 
router MUST NOT respond on interface 1 for a NS addressed to it's global 
address assigned to interface 2, for the resulting NA to be a fool-proof 
indication that the host didn't move.

>    and send a multicast RS only if the unicast fails? Or do both in

Two things:
  - first sending a NS and waiting for an answer (how long?), perhaps 
retransmitting the NS, before sending the RS means that DNA in the case 
when the host did move to a different link will take a lot longer than 
in dna-protocol3. Note that in this case the NS would not elicit a 
response. (But I don't know if we've talked about sending the same RS as 
in dna-protocol3, but unicasting it at L2 to an old router address. That 
would require some tweaks to get an immediate response instead of a 
delayed response.)

  - The problem of expensive multicast/broadcast isn't unique to DNA. 
IEEE 15.4 will see this when I initially power on devices that do RFC 
2461, since each multicasts an RS. A solution to that might be some 
combination of L2 and 2461 optimizations. At the recent 6lowpan interim 
meeting we talked about the possibility of having the 15.4 coordinator 
be an IPv6 router, in which case packets sent to the "all routers IPv6 
multicast address" can be unicast to the coordinator's L2 address. Such 
things can presumably be covered in an IPv6-over-foo document that gets 
some careful review.

>    vs. "new prefix from router we've received RAs from before"?

It the routers don't have the DNA extensions, then such probes would 
serve to purpose since the multicast RAs they trigger are rate limited 
to one every 3 seconds.
And if the routers do implement the DNA extensions, then the host can 
always tell from the first RA whether it has moved or not.

>    information learned from RAs received since last "link up" get

Yes, the documents might need to be more explicit about this.
CPL tries to be explicit in its rules for the candidate link objects.

>    depend on how long it has been since one was previously connected

I think the reruning of DAD needs to be a function of how long the host 
has been disconnected and the normal packet loss on the link.
If the host is always connected to the link, DAD might still fail to 
find duplicates due to normal packet loss. Thus we don't need to do 
better than this when it comes to DNA handling being disconnected and 
later reconnected.

In reality though, with wireless links there is a floating boundary 
between being disconnected and "normal" packet loss; the further away 
from the AP the station is, the higher packet loss. And when going even 
further, after some time the host NIC determines that the AP is 
unreachable. But I don't know if there is an upper bound on the time 
between the host having a 90, 99, or 100% packet loss until it declares 
the AP gone and the link down.

So I think it is time to pull a number out of a hat. How about 30 seconds?

>    information on a link? That is, suppose a bogus router shows up and

You mean it sets the "bogus" bit in the RA?
The host has no way, unless we run SEND, to tell apart the good, bad, 
and ugly routers.

>    this happens and causes problems. 

You seem to say DNA would make this worse, and I don't understand how.
If a host remains attached to the same link forever, then the bad 
information will stay in its prefix list until it times out.
Clearly DNA can't be worse than that; the information is only used when 
attached to the link where the bogus router lives.

> For robustness, it seems like it

The DNA WG talked about this in the context of flash renumbering and 
immediate reassignment, but is is a bit problematic even in that context 
because we are making prefixes disappear faster than RFC 2461 intended. 
Thus things might become more brittle.

We can't guard against malicious routers unless we run SEND, right?
If we run SEND and still have a problem with bogus prefixes being 
advertised, the operator's setup is broken AFAIK.
(When shim6 is deployed it would probably "route around" such 
brokenness, by discovering that the prefix/address doesn't work 
end-to-end, which would given some higher robustness, but still, this 
doesn't get any worse with DNA AFAIK.)

    Erik

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Feb 2006 09:58:25 -0800

> encountered router, without ambiguity.

Does this work if you have a router which
  - uses the same IEEE 802 MAC address on multiple ports (which is 
compliant with the IEEE specifications AFAIK)
  - also does NAT so that the router's IP address on multiple ports is 
10.0.0.1

In that case you'd get an ARP response even though the host had moved to 
a different link.

Because IPv6 has link-local addresses the corresponding situation can be 
quite common even though there is no NAT.

    Erik

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Feb 2006 10:27:03 -0800

> the responder doesn't delay in responding. So this can be very fast.

But an NS is ignored if the target doesn't match.
Are you talking about some hybrid between a RS and a NS which other 
routers can respond to immediately?

Or are you just trying to solve the case when the link-local address of 
the router isn't globally unique and that's why you want to add the 
landmark?

We want reasonable behavior both when the host has moved and when it 
stays on the same link.
In the case when it moves, dna-protocol* has explored the optimal 
solutions (a single RS and a single RA), and unless we have some clue 
from L2 the RS must be multicast to all-routers. (As Greg pointed out, 
this doesn't mean it needs to go everywhere.)

In the case when a host hasn't moved then (if one already know it didn't 
move ;-) then a unicast packet can be used to verify this.

But given that the host has to work efficiently whether it has moved or 
not, the choices are hard.
We could unicast 3 packets (and wait for 1 second after each) before 
sending the RS to all-routers. But that means that the case when the 
host moved now takes 3 more seconds.

We could send a RS to all-routers, which is fast in both cases, but 
causes extra traffic if multicast to all-routers isn't implemented 
efficiently in the network (MLD snooping?)

But there is no middle point: sending the RS to all-routers in parallel 
with the unicast NS doesn't reduce the multicast traffic.

> including all prefixes in RAs.

We've discussed various ways, and I still think that the single landmark 
is simpler. But handling the case when a most might move between a link 
with DNA capable routers and a link without such routers (as well as 
links that have some of each) is tricky.

> itself is not advertising. I have some fairly strong qualms about that

Because of the prefixes or something else?
These prefixes are only used for DNA; they do not effect the 2461/62 
operation.

The routers have to keep track of each other in any case to be able to 
have one of them immediately respond to an all-routers RS.

> previously?" 

But that approach optimizes only for the case of non-movement. We need a 
balance that also optimizes for the case of movement.

> and all send out multicast RSs...

I thought it was the 802.11 associate frames that were problematic on 
Monday's at the IETF ;-)

Seriously, it is hard to optimize for the case of flaky infrastructure 
(like IETF on Monday morning), and at the same time also optimize for
non-movement as well as movement.

I think that would be an over-constrained problem.

    Erik

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Feb 2006 10:46:56 -0800

> risks in terms of other hosts attempting to use such addresses.

There are two things related things in this space, and I think you touch 
on the one that needs discussion.
But for completeness...

When DNA receives a link up event, then it doesn't know whether it is 
re-attaching to the same link or attaching to a different link.
Thus it makes sense to be conservative and mark the addresses as 
optimistic, and send any RS with the TSLLAO option.
Should the host determine from the RA that it has moved, then it should 
proceed with the optimistic DAD logic to send the DAD NS and wait for 1 
second.

The reason for the above is that if we require that a host do DAD when 
it powers up the first time due to some feel for the probability of 
collisions, then moving to a different link has the same probability of 
collisions. Thus we can revise this part of DNA/DAD interaction *if* we 
find that the probability of collisions is different in the non-DNA case 
of powering up the device.

The case (which I think is what you have above) of reconnecting to the 
same link is actually tricker, and is part of the (wireless) continuing 
from low packet loss to high packet loss and then loosing the attachment 
to the link.
But independently of how long such an outage is, and whether we take 
packet loss percentage into account or not, we can do a first order 
approximation that other hosts (with potentially conflicting addresses) 
are unlikely to arrive at the link and do their DAD while the host 
doesn't receive the DAD probes. (This is different than in the movement 
case, when there might be a very large population of hosts on the new 
link, any one of which could have a duplicate.)

Thus I think the time, when re-attaching to a different link, that needs 
to pass before the host should send a new DAD probe can be longer than 1 
second.

I wonder if we could benefit from some practical experiments (e.g., on 
802.11) for how long it takes from the host seeing 100% packet loss 
until it declares the link down. If this time is commonly 10-30 seconds 
with current implementations we presumably need to take this into account.

    Erik

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Feb 2006 11:05:14 -0800

> such events, especially if they are not expected to be common.

Do read what dna-protocol3 proposes.

But this is actually a case where DNA potentially could make things a 
lot worse if we didn't do anything, because DNAv6 relies on prefixes 
comparisons, which means it uses the prefix lifetimes *even though it is 
not connected to the link*. (And DNAv4 doesn't rely on prefix 
comparisons - it just reverifies things with the DHCP server - so it 
doesn't have this issue AFAIK.)

Without DNA one can do reasonable flash renumbering.
Assume the prefix is advertised with the default 7/30 day 
preferred/valid lifetimes.

Somebody decides that the prefix needs to be forcibly removed from the 
link. Starts advertising the prefix with 0/o preferred/valid lifetimes 
in every RA. All the hosts will notice this - and if the prefix 
continues to be advertised with zero lifetimes for 30 days then even 
hosts that were dormant will never be confused.

Such an event will be disruptive, because some connections will die, if 
not immediately then after the 2 hour limit in RFC 2462.

Thus there might be emergency cases when this will be done.
It might also be possible that somebody decides to immediately reassign 
that prefix to another link, and we should recommend that this is bad 
operational practice. But it might happen with any additional harm.

Enter DNA.

It is possible (but very unlikely) that a host would move from link A 
(which has prefix P1, P2) to link B (with prefix P3) at the same time as
  - P1 is forcibly removed from link A, and P1 is reassigned to link B

If we didn't do anything, then the host would be confused for 30 days, 
because it would think
  - it didn't move to a different link because it hears P1 after reattaching
  - the prefixes assigned to the link are P1, P2, and P3

Thus the host will continue to use it's address in the P2 prefix, which 
will not work.

The above description is longer than the fix; dna-protocol3 says to not 
use information that is older than 1.5 hours.

    Erik

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Feb 2006 11:09:13 -0800

> back to RS. One can imagine other optimizations.

Yes, but that one clearly doesn't satisfy the Monday morning IETF 
criteria. I think I saw rtt's to the router fluctuate a lot in 
Vancouver; up to several seconds.

If that's the case, we'd see more packets with this "optimization" - 
first some unicast NSs from each host then a RS to all-routers.

    Erik

---

From: Bernard Aboba <[email-masked]>
Date: Tue, 14 Feb 2006 14:31:40 -0800

>compliant with the IEEE specifications AFAIK)

Using the same IEEE 802 MAC address on multiple router ports will cause 
problems with VLAN learning operation (e.g. same MAC address would be in 
multiple VLANs so the interface will receive traffic on VLANs it doesn't 
belong to), so this is not a good idea (which is why routers or bridges do 
not do this).

>In that case you'd get an ARP response even though the host had moved to a 
>different link.

This wouldn't cause a problem because DHCP runs in parallel and if a 
different address were assigned it would over-ride.

---

From: Bernard Aboba <[email-masked]>
Date: Tue, 14 Feb 2006 14:41:36 -0800

>with the unicast NS doesn't reduce the multicast traffic.

I don't think the issue is multicast traffic reduction per se.  The issue is 
the *timing* of multicast traffic.  To avoid multicast storms it is 
necessary for multicast to involve delays and backoffs. Sending both NS and 
RS in parallel would remove potential ambiguities while not requiring that 
multicast RS be sent *immediately* as has been proposed, which would create 
severe scaling problems in the event of a power failure.

>balance that also optimizes for the case of movement.

Actually, I'd argue that the important thing is to make sure that 
performance is not impacted negatively in any scenario.  Since DNA is an 
optimization, it is not useful unless it actually improves performance.

>I thought it was the 802.11 associate frames that were problematic on 

Actually, IETF 802.11 usage shows evidence of congestive collapse due to 
inappropriate rate negotiation behavior.  That kind of problem can be made 
considerably worse by multicast traffic without appropriate jittering and 
backoff.

>non-movement as well as movement.

I believe that the effects we see at the IETF are real and occur regularly 
in high density 802.11 environments.  They are not anomalies, since they 
show up in test environments regardless of the equipment that was being 
used.

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Feb 2006 15:38:52 -0800

Bernard Aboba wrote:

> belong to), so this is not a good idea (which is why routers or bridges 
> do not do this).

That might be a problem on the bridges themselves, but it can't be true 
for hosts attaching to those VLANs because if it was, we'd have a 
serious security problem. (Where a host which is on VLAN x can disrupt 
packet flow on VLAN y by choosing the source MAC address to be the 
same.) Come to think of it, this might have been part of the security 
bugs in the pre-standard VLAN bridges that some vendors shipped.

>> In that case you'd get an ARP response even though the host had moved 
>> to a different link.
> 

Correct for DNAv4. But for DNAv6 we have no all-knowing entity like a 
DHCP server which can verify the addresses; we have to cope with what 
the RFC 2461 conformant routers will hand us.

    Erik

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 14 Feb 2006 16:05:22 -0800

Bernard Aboba wrote:
>> But there is no middle point: sending the RS to all-routers in 
>> parallel with the unicast NS doesn't reduce the multicast traffic.
> 
> I don't think the issue is multicast traffic reduction per se.  The 
> issue is the *timing* of multicast traffic.  To avoid multicast storms 
> it is necessary for multicast to involve delays and backoffs. Sending 
> both NS and RS in parallel would remove potential ambiguities while not 
> requiring that multicast RS be sent *immediately* as has been proposed, 
> which would create severe scaling problems in the event of a power failure.

Are you assuming that some event would cause N stations to try to 
multicast at the same time? (Recall, this is a single multicast packet 
and not somebody streaming UDP video over multicast.)

How does DNAv4 handle this? The draft says to do the ARP validation and 
DHCPREQUEST in parallel, and explicitly says to broadcast the 
DHCPREQUEST. Seems like DNAv4 as specified has as much of a problem with 
broadcast/multicast load...

>> But that approach optimizes only for the case of non-movement. We need 
>> a balance that also optimizes for the case of movement.
> 

But in the above case you are saying that we can detect non-movement in 
a roundtrip time (the NS/NA exchange), but that detecting movement 
requires some random delay (how much? how much will VoIP cope with?) 
plus a RS/RA exchange.

I don't think such an approach satisfies the DNA goals (RFC 4135). FWIW 
that document does not say that we should avoid using multicast; if 
multicast is so evil we should have had that discussion from the start 
instead of in the 11th hour. And as I said elsewhere, there is plenty of 
network technology where multicast is expensive (.15.4 .16) but is 
expensive even for the RS when the device boots. So the multicast 
avoidance issue isn't specific to DNA.

> I believe that the effects we see at the IETF are real and occur 
> regularly in high density 802.11 environments.  They are not anomalies, 
> since they show up in test environments regardless of the equipment that 
> was being used.

Yes, but *Monday morning* at IETF is a bit special, since it is often in 
a place that hasn't seen that density deployment before. Thus it is 
quite a bit different ramp-up than some hotspot that sees a lot of 
traffic, because of the arrival rate in a completely new infrastructure.

The rest of the week is more normal, with the usual plethora of 
operating systems that try to be too helpful to automagically switching 
to ad-hoc mode (and in some cases using the same ESSID as before they 
lost the AP. ;-)

    Erik

---

From: Christian Vogt <[email-masked]>
Date: Mon, 20 Feb 2006 12:09:43 +0100

Hi Thomas, hi Greg.

>  mechanism can result in a large number of solicitations sent 

Unfortunately, there is some inconsistency with respect to exceptions
for "mobile nodes" in RFC2461/2462bis.  Specifically, mobile nodes
should still wait for up to 1 second before they send an MLD Report
message prior to DAD.  RFC2462bis specifies this in section 5.4.2:

   If the Neighbor Solicitation is going to be the first message to be
   sent from an interface after interface (re)initialization, the node
   SHOULD delay joining the solicited-node multicast address by a random
   delay between 0 and MAX_RTR_SOLICITATION_DELAY as specified in
   [I-D.ietf-ipv6-2461bis].  This serves to alleviate congestion when
   many nodes start up on the link at the same time, such as after a
   power failure, and may help to avoid race conditions when more than
   one node is trying to solicit for the same address at the same time.

   Even if the Neighbor Solicitation is not going to be the first
   message to be sent, the node SHOULD delay joining the solicited-node
   multicast address by a random delay between 0 and
   MAX_RTR_SOLICITATION_DELAY if the address being checked is configured
   by a router advertisement message sent to a multicast address.  The
   delay will avoid similar congestion when multiple nodes are going to
   configure addresses by receiving the same single multicast router
   advertisement.

There was quite a long discussion about this on the IPv6 mailing list
[1].  The conclusion was eventually to leave "real" mobility
optimizations to DNA.

Regards,
- Christian

[1]  "Comment on RFCs 2461bis and 2462bis",
http://www1.ietf.org/mail-archive/web/ipv6/current/msg05084.html

-- 
Christian Vogt, Institute of Telematics, University of Karlsruhe
www.tm.uka.de/~chvogt/pubkey/

Greg Daley wrote:
>>>>  2461/2462 rule? Are there ways to relax this that are
>>>> consistent with the original concerns that led to the existing
>>>> wording in 2461/2462?
>> 
>>> anticipation of a link change. Also if you use unicast meessage
>>> to known destinations, no reply will come when you have moved to
>>> a new link. This will result in delay since you can't but rely on
>>> timeout to detect a link change.
>> 
>> estimate of how long you are willing to wait (and I'd expect this
>> to be very short, like 10ms or less). If that doesn't work, then
>> fall back to RS. One can imagine other optimizations.
>> 
> 
> 
> Such an optimization may work, but its effectiveness is dependent on
> topology (single cell links would experience longer delays), and the
> amount of time available to upper-layer applications (for example,
> voip).
> 
> It makes sense to mention this idea as an optimization to reduce the
> effect of multicasts on the link-layer.  I'd suggest inclusion of a
> tentative link-layer address option, as the source address of the NS
> is likely to be considered optimistic for DAD purposes (it may not
> help, but may avoid the reverse NS/NA exchange if the router doesn't
> have the host in the NCE).
> 
> How about:
> 
> "... Multicast transmission has been shown to increase bandwidth 
> consumption on certain wireless media at a rate much greater than
> that caused by unicast transmission.   On such media, it MAY be
> useful to send a unicast NS transmission to the global address of one
> of the configured routers upon reception of a link-layer hint.  This
> would avoid transmission of a multicast Router Solicitation if the
> router was available. The RS could then be delayed for an interval
> corresponding to the duration required to receive the unicast NA, if
> the router is still reachable.
> 
> This optimization is dependent on topology, and increases delay and
> packet transmission if the link is composed of a single cell. 
> Additionally, hosts with applications that are not able to delay for
> the lost NA in case of link-change SHOULD use RS instead. ..."
> 
> 
> Sending to the link-local address is insufficient, as some devices
> have been known to share a MAC address across different NICs, and
> CGAs with common public keys will be the same for two interfaces on
> one router, as the link-local prefix and key are the same.
> 
> Actually, if the NS contained a landmark option and the router was a
> known DNA router, you could send to any address.
> 
> Greg