Subject: [mobile-ip] Optimistic DAD for Fast Handovers

From: "Nick 'Sharkey' Moore" <[email-masked]>
Date: Fri, 6 Sep 2002 08:40:54 +1000

G'day all,

        As part of an attempt to put together a minimal
specification / implementation of Fast Handovers for IPv6
over 802.11, I've been working on eliminating DAD delays
by using Optimistic DAD.

        There is some precedent for this based on 
draft-koodli-fastv6-00 and comments by Eric Nordmark in
the WG at IETF-54 in Yokohama, however this work is
really intended as a research rather than a standards-
setting effort :-)

        So far I've put together the beginnings of a 
spec and tweaked a Linux kernel to implement these
changes.  In initial tests, the modifications seem to 
be effective.  I've also made some modifications to 
_increase_ the likelihood of collision, in order to 
be able to test these cases.

        The modifications I'm experimenting with are:

* Always using randomized suffixes, as per RFC 3041.
    If there is a collision, pick a new random suffix and
    start again.

* Requiring the node to send unsolicited NAs:
        + When DAD commences, with Override = 0;
        + When DAD completes successfully, with Override = 1.
    This allows communication to start immediately if 
    there is no collision.

* Allowing the node to communicate while Tentative,
    which allows Binding Updates, etc to be sent.

* Allowing the node to respond to NSs while Tentative, but
    requiring that the reply NA Override flag is 0.

        Hopefully these changes allow a very fast handover 
while maintaining interoperation with normal nodes.

        I'm interested to hear your opinions!

-----N
-- 
Nick 'Sharkey' Moore                    <[email-masked]>
Research Fellow, CTIE                   Tel: +61 3 9905 3707
Monash University,  Australia           Fax: +61 3 9905 5358

---

From: "Alper E. YEGIN" <[email-masked]>
Date: Thu, 5 Sep 2002 16:56:08 -0700

>         Hopefully these changes allow a very fast handover 

It'll be faster, though it'll run the risk of breaking this node's own
communication and another node's communication when things
go bad. If this risk was only affecting the node using this "optimization",
we could say it's this node's choice (i.e., a tradeoff). But when this 
"aggressive" behavior costs some other innocent node its connectivity,
then a node's individual decision won't be sufficient. Maybe it should
be network operator's decision, by allowing/disallowing all nodes use
this optimization at the expense of risking other on-link nodes??

alper

---

From: "Nick 'Sharkey' Moore" <[email-masked]>
Date: Fri, 6 Sep 2002 12:40:40 +1000

G'day Alper ...

On Thu, Sep 05, 2002 at 04:56:08PM -0700, Alper E. YEGIN wrote:
> go bad.

I've tried to minimise this risk throughout, to make sure
that the risks for a third party running normal DAD are
no worse than a collision with a new node running normal DAD.

> If this risk was only affecting the node using this "optimization",
> then a node's individual decision won't be sufficient.

We're being Optimistic rather than Aggressive, I hope! 

The NA Override flag, as defined in RFC 2461 4.4, is always
cleared during the tentative phase.  So if we imagine the
following situation:

* OriginalNode, running normal DAD, has established an address
	and is corresponding via Router

* OptimisticNode appears on the network, and attempts to
	configure the address already used by OriginalNode
	1. Sends a Neighbour Solicitation
	2. Sends a Neighbour Advertisement with O=0

* Router sees the NA, but because it already has a neighbour
	cache entry for that address it ignores it as
	per RFC 2461.

* OriginalNode sees the NS, and responds with an NA
	with O=1, causing OptimisticNode to reconfigure
	with a new address.

* Any nodes on the local subnet which did not previously
	have a neighbour cache entry for OriginalNode
	and which see both NAs will end up with the
	entry for OriginalNode (since it's O=1)

The cases where two nodes, one Optimistic and one 
normal, try to configure the same address at overlapping
times may give preference to the Optimistic node,
however these cases are really quite unlikely to occur.

-----N
-- 
Nick 'Sharkey' Moore			<[email-masked]>
Research Fellow, CTIE			Tel: +61 3 9905 3707
Monash University,  Australia		Fax: +61 3 9905 5358

---

From: Francis Dupont <[email-masked]>
Date: Sun, 08 Sep 2002 21:18:19 +0200

=> I fully agree: the decision must be in the hands of the network operator,
i.e., the person who should have to cleanup the mess if the unlikely
problem happens...

Thanks

[email-masked]

PS: if you don't worry about privacy stuff, an EUI-64 based IID is
far better.

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 9 Sep 2002 23:58:59 +0200 (CEST)

> this optimization at the expense of risking other on-link nodes??

From the half-baked idea department:

Perhaps it would be better to explore "router/agent assisted DAD"
than optimistic DAD. In the assisted DAD case there would be an agent
which would somehow reliably know the IP addresses and link-layer
address of everybody on the link. Then it could send an "ok to use it"
response to DAD queries if the address isn't in its table or
if it is in the table with the same link-layer address.

The trick is how to reliably have the agent build the tables.
One way would be to add a new RA option "please periodically send a packet
to X" where X is the address of the agent, which would cause all hosts
to send a packet with a given period.
This requires changes in all hosts on the link, and it causes additional
background traffic for the benefit of shortening the DAD query.

  Erik

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 10 Sep 2002 00:04:31 +0200 (CEST)

> 	entry for OriginalNode (since it's O=1)

When happens when OptimisticNode, before seeing the NA from OriginalNode,
decides to communicate with PeerNode and sends a NS to PeerNode?
Wouldn't that cause PeerNode to overwrite whatever neighbor cache entry
it has for the IP address?

  Erik

---

From: "James Kempf" <[email-masked]>
Date: Tue, 10 Sep 2002 08:14:38 -0700

Erik,

> background traffic for the benefit of shortening the DAD query.

From a wireless spectrum standpoint, this is not a particularly good use of
spectrum. For free spectrum, the issue isn't the cost, but it can increase
congestion, since the wireless link can be viewed as always oversubscribed.

I've seen some other possible approaches to shortening DAD that I think might be
better to explore.

            jak

---

From: "Alper E. YEGIN" <[email-masked]>
Date: Tue, 10 Sep 2002 14:27:19 -0700

> background traffic for the benefit of shortening the DAD query.

Actually I have a draft in the works along this line. The basic idea is
to turn distributed (i.e., peer2peer) address resolution process into
a centralized one. First hop routers keep track of all of the hosts
on link, effectively turning their neighbor cache into a neighbor table
(NT),
and hosts consulting routers for neighbor solicitations and duplicate
address detection (now can be called duplicate address check - DAC).

There is obviously neighbor table maintenance with neighbor advertisements
with lifetimes.

The benefits of this scheme is not limited to DAD only. The DoS attack
I had identified in section 3.8 of draft-kempf-ipng-netaccess-threats-02.txt
can also be solved by relying on this mechanism. Even when it's not an
attack, awakening of dormant nodes and delays caused by a ND when
an entry may or may not be in the "cache" of a router are other issues that
can benefit from NT approach. Delays get more significant and bandwidth
gets more precious in cellular environments. Also a multicast message likely
to cause one unicast per each host.

alper

---

From: Greg Daley <[email-masked]>
Date: Wed, 11 Sep 2002 08:40:57 +1000

Hi James,

Since MLD has to be performed to listen to the
solicited nodes multicast, these messages will be
sent anyway.

The only additional packet (or overhead, since
the MLD request for response is embedded in the
original MLD Report) is if the router responds.

This is only if No other nodes exist on this address.
If the multicast group exists, the router leaves
the nodes to DAD defend their own addresses.

Plus, you don't have to send all the packets to
the nodes for free...

Greg

---

From: Greg Daley <[email-masked]>
Date: Wed, 11 Sep 2002 10:07:14 +1000

Hi Alper,

I for one would be very interested in seeing how
an ND or NT approach can be used to provide this
service.

Is it possible to have a rundown on some of
the features you mentioned :

neighbor table refreshing,
reaching full state,
how multicasting is avoided?

Greg

---

From: "Nick 'Sharkey' Moore" <[email-masked]>
Date: Wed, 11 Sep 2002 10:29:04 +1000

> it has for the IP address?

Good point, and one I'd completely missed!  There isn't an
equivalent to the Override bit for the NS and RS link-layer
options.

RFC 2461 3.:
| 
| A single request-response pair of packets is sufficient for
| both the initiator and the target to resolve each other's link-layer
| addresses; the initiator includes its link-layer address in the
| Neighbor Solicitation.

Happily, the requirements to sent a link-layer address option 
with NSs and RSs are only SHOULDs, so I think I can get around
this by requiring for Optimistic DAD that:

* Nodes MUST NOT send link-layer address options with their 
	NSs and RSs while Tentative.

This means that setting up communications with peers will
be slightly clumsier (eg: more messages sent) if they ignore
the unsolicited O=0 NAs, but I think it solves the critical
cases.

Thanks for your comments!

-----Nick

---

From: "Alper E. YEGIN" <[email-masked]>
Date: Tue, 10 Sep 2002 18:11:37 -0700

Hi Greg,

> how multicasting is avoided?

Basically, at any time first hop router has a table (NT)
of all the hosts connected to the link. If a host is not
in this table, we can conclude that it's not on the link. Therefore
instead of a host multicasting its DAD packets, it can directly
ask (send extended NA with lifetime field, or NS) the router and wait 
for a response (receive NA-ack, or proxy NA). Only after this response 
the host can conclude whether its safe to use an IP address 
or not. 

The received NA-ack has "granted lifetime", which
host keeps track of to make sure the NT entry on the router
is refreshed before it expires. (or we can give this
responsibility to the router to send a NS before the entry
expires).

alper

---

From: Greg Daley <[email-masked]>
Date: Wed, 11 Sep 2002 12:53:35 +1000

Hi Alper,

This sounds interesting.
How do you see that this has advantages
over only using DHCPv6 on a network?

Greg

---

From: Francis Dupont <[email-masked]>
Date: Wed, 11 Sep 2002 08:35:57 +0200

=> if this has no consequences for RSs this is NOT the case for NSs:
a NS sent without a link-layer address option on a link with addresses
has to be sent from the unspecified address and the answer is multicasted
to all nodes. It works well BUT it is a DAD probe for the peer address,
i.e., not exactly what you'd like to do in not-desperate situations.
Look at the discussion about the MN returning at home without the knowledge
of the link-layer address of the HA...

Regards

---

From: Greg Daley <[email-masked]>
Date: Wed, 11 Sep 2002 16:49:55 +1000

Hi Alper,

I missed the section with the NS from the router.

That sounds like a good idea, since even nodes which
do not support the fast DAD would support NA responses
to NS's.

A flag or option in the NS could allow sending of a timer
in the response, otherwise the lifetimes from the
RA could be used.

Greg

---

From: Rajeev Koodli <[email-masked]>
Date: Wed, 11 Sep 2002 10:53:44 -0700

Hello Nick,

This is an interesting problem (research problem for sure!)

I had sent out a note to the list last year (March 13, 2001)
in which I attempted an analysis of fastv6 handover. [I can't
get the URL of the posting, but it's in the archive]
The following text from that note may be relevant to this
discussion. I think the method will work, but I have been
away at Yosemite for little too long!

Regards,

-Rajeev

......

NAR = New AR

c> after L2 establishment with NAR, NA message could incorrectly
update the ND cache entries.

The MN sends a Neighbor Advertisement (NA) message after attaching to
NAR. What type of NA is sent is unclear. Typically, unsolicited NA
messages are sent to  all-nodes multicast address to propagate new
information to all the nodes. Since there  is no solicitation message
described, we assume that unsolicited NA is sent. In such a message,
the O-flag SHOULD be set to indicate that the receiving nodes should
override their cache entries with the information supplied in this
message. The source IP address in this message is "an address assigned
to the interface from which the advertisement is sent [RFC 2461]",
which means it could be a link-local address or a global IPv6 address.
Anyway, there are two cases to consider here. First, assuming that the
NAR is proxying new CoA and has sent proxy NA message(s) before the MN
attaches to NAR, the NA sent by the MN correctly updates ND cache
entries in all the nodes. On the other hand, if the NAR was not
succesful in being able to proxy the new CoA, e.g, due to the address
being in use already, then the NA  message sent by the MN would
incorrectly update ND cache entries in all the nodes. This latter
situation must be avoided. Even though the draft attempts to ensure
that the MN does not use a new address until a confirmation is
received (i.e., BAck message approves the use of new CoA), the use of
NA in this fashion contradicts the objective.

Suggestion for handling scenario c>
-----------------------------------

We propose to include a new 'T' bit in the NA message that the MN
sends after attaching to NAR. This bit MUST be set to one only by the
MN undergoing fast handover. When the 'T' bit is set, it indicates
that the sender is trying to propagate its information to all the
nodes on-link providing that its IP address is tentative. The nodes
trying to propagate their new information when their IP addresses are
confirmed, MUST NOT set the 'T' bit to one. Thus, if a node receives
an NA message with 'T' bit set to one, it MUST NOT override an already
existing corresponding ND cache entry. If a node has a proxy ND cache
entry, the presence of a 'T' bit set to one indicates that the node
SHOULD override the entry if the entry corresponds to the sender of
the NA. If a node is proxying an address that does not belong to the
MN, the 'T' bit  would disallow overriding the ND cache entry.

Note that this solution would not work when two MNs participating in
fast handovers simultaneously try to acquire the same address and
simultaneously try to  announce their presence via NA messages both
setting the 'T' bit.

Although the 'T' bit extension can be used in multicast NA messages as
well, limiting the message to unicast only to the NAR would ensure
that other nodes on-link would observe transparency. Thus, we
recommend that the proposed extension be carried in a unicast NA
message to NAR. Once the MN confirms its new IP address, it may send a
mulicast NA message with the 'T' bit set to zero.

The following cases sumamrize the process.

i> another node on the link is using new CoA.
   Note that NAR has fairly recent information about this, since it
   would have failed to defend the address for the MN. NAR MUST NOT
   overide its cache and report
   the error with possible recourse back to the MN.

ii> NAR is proxying the address for the MN.
   NAR SHOULD overide its cache entry with the information in the NA
   message providing that the 'T' bit is set.

iii> NAR is proxying new CoA for some other node (off-link or on-link).
   Any node whose legitimate (meaning its address is known to be not
   tentative) IP address is currently being proxied by NAR, MUST NOT
   set the 'T' bit when it sends NA message. This allows NAR to
   override the entry when necessary. If NAR receives a NA message
   with 'T' bit set, the 'T' bit allows NAR to distinguish that the
   request arrived from a node for which it is not proxying the
   address.

Whereas the above extension addresses the incorrect update to ND cache
entries when there is address conflict, it does not the address the
problem that it takes an RTT-air delay before the MN can use a new IP
address. The solution to this problem in the next e-mail.

........

---

From: "James Kempf" <[email-masked]>
Date: Wed, 11 Sep 2002 13:31:11 -0700

,
> over only using DHCPv6 on a network?

One advantage is that the host can use RFC 3041 address privacy.

            jak

---

From: Greg Daley <[email-masked]>
Date: Thu, 12 Sep 2002 08:55:45 +1000

Hi James,

the DHCPv6 draft now supports IA_TA for
temporary RFC 3041 address assignments.
(section 12)

Greg

---

From: "Alper E. YEGIN" <[email-masked]>
Date: Wed, 11 Sep 2002 16:44:28 -0700

Hi Greg,

> over only using DHCPv6 on a network?

This is more of a "keeping track" of what
IP addresses are being used, instead of "fully managing"
them. I believe that first hop routers keeping track of
all nodes' IP addresses will be a common feature especially
in wireless networks (due to the potential problems, optimizations 
I outlined earlier), keeping the same information on the dhcp
server would be redundant. Also note that the nodes still have 
the control over what IP address they choose.

This method can be made to work even when some of the
nodes don't support the extended protocol. This can be achived
by loading more responsibility on the routers (e.g., they can keep
track of regular DADs). But I'm afraid the same cannot be said 
when dhcp is used for this purpose. All nodes have to support 
dhcp and use it to remedy the effects of DAD.

alper

---

From: "Nick 'Sharkey' Moore" <[email-masked]>
Date: Thu, 12 Sep 2002 11:38:00 +1000

> This is an interesting problem (research problem for sure!)

G'day Rajeev, it's a dirty job but someone said they'd pay me to do it :-)

> I had sent out a note to the list last year (March 13, 2001)

Yep, I don't seem to be able to find the original post but 
is this all of it?:
<http://playground.sun.com/pub/mobile-ip/FH-archive/frm01112.html>

As you've no doubt noticed, my suggestions are very similar
to your original draft-koodle-mobileip-fastv6-00.txt ...
in fact, they come about because when I started to look
at implementing your "'O'ptimistic" flag, I realised that
its behaviour could be handled using the "'O'verride" 
flag ... thus allowing non-modified hosts and routers to
interoperate correctly.

I'll have to study your more recent post more carefully
and get back to you ... in what cases is 'T' not equivalent
to 'not O'?

-----Nick

---

From: Rajeev Koodli <[email-masked]>
Date: Wed, 11 Sep 2002 19:37:46 -0700

> G'day Rajeev, it's a dirty job but someone said they'd pay me to do it :-)

Oh, I didn't imply it that way. Hope you don't put research
and "dirty job" in the same equivalence class :-)

> <http://playground.sun.com/pub/mobile-ip/FH-archive/frm01112.html>

I guess Yes.

> and get back to you ... in what cases is 'T' not equivalent

One thing is that the OppNode should respond to any NS
with T bit set. Since solicited NAs have the effect of updating
the ND cache, setting the T bit when the address is unconfirmed
allows to prevent the update. Changes to ND for each node is
a concern; however, it should be possible to restrict the changes
to the AR and the OppNode.
Also, if the AR is proxying the address for some other node, which
is one of the issues considered in the note, then sending NA with
O=1 would incorrectly update the cache again. Here, you would
like to set T=1 also.

In any case, It would be nice to arrive at a good solution.

Regards,

-Rajeev

---

From: "James Kempf" <[email-masked]>
Date: Wed, 11 Sep 2002 22:26:14 -0700

But does the host have to return to the DHCP server re-initialize? If so, then
RFC 3041 may still have an advantage for wireless: less over the air traffic,
if, of course, DAD can be optimized to require fewer messages than DHCP.

            jak

----- Original Message -----
From: "Greg Daley" <[email-masked]>
To: "James Kempf" <[email-masked]>
Cc: "Alper E. YEGIN" <[email-masked]>; "Erik Nordmark"
<[email-masked]>; <[email-masked]>
Sent: Wednesday, September 11, 2002 3:55 PM
Subject: Re: [mobile-ip] Optimistic DAD for Fast Handovers

---

From: "Nick 'Sharkey' Moore" <[email-masked]>
Date: Wed, 18 Sep 2002 16:46:04 +1000

On Wed, Sep 11, 2002 at 08:35:57AM +0200, Francis Dupont wrote:
> [Nick Moore wrote:]

Aha! After a weekend away (and reading your further explanation ...)
I now understand!

The situation is messy for talking to peers while tentative ...
but there's an out: if I send a NS to the peers multicast, with my
tentative address as my IP source but no LL option, it should
attempt to reply directly, thus sending an NS ... and giving
us a chance to send our O=0 advertisement.  This breaks rfc2461
for the optimistic node, but a compliant peer should behave
correctly I think ...

This is admittedly inefficient, but for fast handovers I'm
more interested in communications via the router, which 
should work correctly (after all, the RA is what starts all
this prefix business anyway)

-----Nick