Subject: Flash renumbering (was:Re: [DNA] DNA proposal issue 19 - was[Issue X] LinkID v.s. LandmarkPrefix)

From: Sathya Narayanan <[email-masked]>
Date: Mon, 25 Jul 2005 22:50:26 -0400

Erik -

I reordered the text in your email (and changed the subject line) with my comments inline.

> But the problem certainly isn't specific to any particular proposal, 
> since they all rely on prefixes for link identification. And I suspect 
> that we have the same choices in terms of solutions independent of which 
> proposal we apply this to.
FWIW, I completely agree with you on this. IMHO, the synchronization complexity/issue is same/similar for all of these schemes.

> We could decide this is the administrators fault, and not do anything. 
> Or we could add a mechanism to attempt to detect this and recover 
> in less than 7 days.

Having said that, I am going to try to solve this problem using the Landmark scheme. Be warned that this is me just thinking out loud and you should remember how lost I get when I do that ;-)

> The worst case would be when P1 and P2 are assigned to link1, and P2 is 
> immediately reassigned to link3 (which had prefix P3 before), at about 
> the same time that the a host moves from link1 to link3.
> 
> In that case, any prefix based scheme for link identification (CPL, landmark, linkid, or anything else we can invent) can get into trouble, 
> by the host assuming that P1, P2, and P3 are assigned to link3.
It can be argued that the semantics of landmark exchange is not to imply all those prefixes are on the link - if the host did a landmark question using 'P3', then a 'yes' answer just means P3 is on the link (link3 in this case). Does that make sense? 

The negative side is that when a host is on a link with P4, P5, P6, sends a landmark question with P6 and gets a 'yes' answer, the host cannot say anything about the availability of P4 or P5. The host will have to do separate landmark questions for each of them or hope for a complete RA to be received. The choice of the landmark on the host side becomes crucial in doing DNA. Now, since G1 in the goals document is
"G1: DNA schemes should detect the identity of the currently attached link to ascertain the validity of the existing IP configuration.", if the chosen landmark-prefix corresponds to a non-local IPv6 address of the host, its validity of atleast one address can be ascertained.

Such a change in the semantics, I think, restricts the host from making assumptions about prefixes on link unless explicitly seen in RA messages continuously and hence can address the flash renumbering and early assignment problem.

What do you think?

-Sathya

> 
> Should this happen, then the host will assume that P1 is usable until 
> the last valid/preferred lifetimes it saw has expired. Since RFC 
> 2461 
> suggests a default preferred lifetime of 7 days, the host will try 
> to 
> use P1 as a source address for 7 days, even though no packets 
> returned 
> to P1 will make it back to the link to which the host is attached.
>

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 25 Jul 2005 20:18:22 -0700

Sathya Narayanan wrote:

> It can be argued that the semantics of landmark exchange is not to
> imply all those prefixes are on the link - if the host did a landmark
> question using 'P2', then a 'yes' answer just means P2 is on the link
> (link3 in this case). Does that make sense?

I'm not sure it helps.
If P2 was retracted from link1 either silently (e.g., a single router 
was advertising P2, and that router was moved or decommissioned as part 
of the flash renumbering), or a few RAs were sent with valid lifetime=0, 
and, due to packet loss, some routers on link1 did not hear those RAs, 
then we'd still have an inconsistent state; a landmark query for P2 
would return "yes" even though the prefix isn't assigned to link1 any 
more. This will persist for the maximum time the learned prefixes are 
retained by a router on link1 (90 minutes).

> The negative side is that when a host is on a link with P4, P5, P6,
> sends a landmark question with P6 and gets a 'yes' answer, the host
> cannot say anything about the availability of P4 or P5. The host will
> have to do separate landmark questions for each of them or hope for a
> complete RA to be received.

Based on the comment above, we would also have to forbid the routers 
from using learned prefixes as part of the DNA solution.

That sounds like fairly severe restrictions, especially given the low 
probability of
  - flash renumbering
  - immediate reassignment of the prefix to a different link, and
  - a host moving from the old link to the new link at the same time as
    the flash renumbering and reassignment

Thus I'm more favorable to an approach which tries to recover from the 
problem in a reasonable way once it has occurred, but without impacting 
the performance of the main DNA operation.

A possible way to do this is exemplified by this sequence:
  - the host sees P1 and P2 on the link
  - the host gets a link up notification; sends a RS with a landmark 
question for P2
  - receives a landmark response with P2=yes
  - later receives a periodic RA with some prefixes (P2, P3 in the example)
  - 90 minutes after the link up it observes that it has not yet heard 
any RA with a subset of the prefixes it heard before the link up (P1 in 
the example); this is suspicious. In this case it could
	- drop those prefixes; basically assume that it has moves to a link 
with (P2, P3)
	- try to reverify whether P1 is on the link by sending a RS with P1 as 
the landmark.

The last thing would not need to be performed for each prefix; only one 
prefix which was heard before the link up but has not been heard after 
the link up should be sufficient.

    Erik

---

From: Sathya Narayanan <[email-masked]>
Date: Mon, 25 Jul 2005 23:43:23 -0400

Erik Nordmark wrote:

> was advertising P2, and that router was moved or decommissioned as
> part of the flash renumbering), or a few RAs were sent with valid
> lifetime=0, and, due to packet loss, some routers on link1 did not
> hear those RAs, then we'd still have an inconsistent state; a landmark
> query for P2 would return "yes" even though the prefix isn't assigned
> to link1 any more. This will persist for the maximum time the learned
> prefixes are retained by a router on link1 (90 minutes).
>
Agreed !!! But ...

> from using learned prefixes as part of the DNA solution.

... why? The problems becomes worse with wrong state for upto 7 days
only with reassignment. The above comment is only about flash
renumbering which will be corrected within 90 minutes and is not that
bad (A)

>    the flash renumbering and reassignment

Even without agreeing to the severe restriction, I agree with the
low-probability of this event and that it may not make sense to design
solution that avoids this possibility. My aim was just to start thinking
about a mechanism to address this ...

> problem in a reasonable way once it has occurred, but without
> impacting the performance of the main DNA operation.
>
> any RA with a subset of the prefixes it heard before the link up (P1
> in the example); this is suspicious.

By suggesting that this is suspicious, we are suggesting that the
prefix-lifetime being greater than 90 minutes is not necessarily right -
in effect putting an upper limit on the prefix-lifetime and overruling
2461. Right? Is it OK to do that?

> In this case it could
>     - drop those prefixes; basically assume that it has moves to a
> link with (P2, P3)
>     - try to reverify whether P1 is on the link by sending a RS with
> P1 as the landmark.
>
> The last thing would not need to be performed for each prefix; only
> one prefix which was heard before the link up but has not been heard
> after the link up should be sufficient.

In support of my argument above marked (A), this solution doesn't
address the flash renumbering problem - only flash renumbering with
early reassignment. But, I do agree that this simpler defensive scheme 
can handle the low-probability occurance of flash-renumbering with early
reassignment.

-Sathya

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 26 Jul 2005 06:31:22 -0700

> renumbering which will be corrected within 90 minutes and is not that

I guess we need to first agree what goals we are trying to satisfy. I 
see three possible levels:
1. do nothing special for flash renumbering and immediate reassignment 
(other than telling network admin to not immediately reassign prefixes)
2. do something so that a host can recover, but it might take a while 
(e.g., 90 minutes)
3. handle it without any delay

Which goal are you attempting for? (And we should ask the same of the 
whole WG.)

I was assuming you were trying for #3, since in some cases you'd recover 
in zero time. But in order to accomplish #3  we'd also have to remove 
any notion of using learned prefixes in the routers.

And if we want to reach #2 then I don't think we need to affect the 
efficiency of the normal DNA operations, but instead have some slower 
sanity check which can recover.

> 2461. Right? Is it OK to do that?

Good question. I wish I had a firm answer. We have an inherent conflict 
between RFC 2461, which was designed we long default lifetimes just so 
that a host wouldn't throw away its addresses and prefixes just because 
a router died for a short time.

But our need to quickly and reliably detect movement, if we combine it 
with the renumbering and reassignment issue, is in conflict. We can't 
solve both.

Hence the best I think we can do is to use the absence of a 'link up' as 
a way to tell the host to stay in the RFC 2461/62 "stability is 
important" mode.

Note that your suggestion to use a RS to reverify each prefix has the 
same issue as triggering a sanity check after 90 minutes, since it would 
also remove a prefix from aggressively than 2461 if the advertising 
router is temporarily down.

> can handle the low-probability occurance of flash-renumbering with early

Flash renumbering without any reassignment wouldn't cause any additional 
problems for DNA, would it? I think it is only an issue/feature of RFC 
2461/62.

   Erik

---

From: Sathya Narayanan <[email-masked]>
Date: Tue, 26 Jul 2005 11:33:05 -0400

> Which goal are you attempting for? (And we should ask the same of the

I believe I was going for #2 - not that I clearly thought about it like
this ;-)

I think leaving it as #1 is bad, #3 is too much and will put unnecessary
restrictions on normal operation to address a 'low-probability' problem,
hence we are left with #2.

> Good question. I wish I had a firm answer. We have an inherent
> conflict between RFC 2461, which was designed we long default
> lifetimes just so that a host wouldn't throw away its addresses and
> prefixes just because a router died for a short time.
>
> Hence the best I think we can do is to use the absence of a 'link up'
> as a way to tell the host to stay in the RFC 2461/62 "stability is
> important" mode.
>
> same issue as triggering a sanity check after 90 minutes, since it
> would also remove a prefix from aggressively than 2461 if the
> advertising router is temporarily down.

Agreed. Also, the periodic RA, if it is complete will not include P1 and
that can be used as indication also. If N CompleteRA messages are
received without the prefix, start getting suspicious.

In conclusion, I suggest we create some text based on your suggestion
from the previous email as a starting point.

>> early reassignment. But, I do agree that this simpler defensive
>> scheme can handle the low-probability occurance of flash-renumbering
>> with early
>> reassignment.
>
> Flash renumbering without any reassignment wouldn't cause any
> additional problems for DNA, would it? I think it is only an
> issue/feature of RFC 2461/62.

I am not sure what is a issue and what is a feature anymore ;-). But,
the 90 minute limitation on the learned prefixes will ensure that the
prefix (P2) is removed from the link (link 1). A host that is configured
with P2, but not using it as landmark prefix will continue to use the
address, until a completeRA gives it a 'hint' - while a host configured
with P2 and using P2 for its landmark prefix, will choose a different
prefix for its address after a landmark question/answer exchange. Does
that make sense?

Sathya

---

From: James Kempf <[email-masked]>
Date: Wed, 27 Jul 2005 07:54:02 -0700

Erik,

I agree with using absence of link up to detect renumbering. Also, I prefer
#1, unless one of the other solutions can be done without introducing
additional complexity into the protocol.

            jak

----- Original Message -----
From: "Erik Nordmark" <[email-masked]>
To: "Sathya Narayanan" <[email-masked]>
Cc: "JinHyeock Choi" <[email-masked]>; "Brett Pentland"
<[email-masked]>; <[email-masked]>; "Syam
Madanapalli" <[email-masked]>; "James Kempf"
<[email-masked]>; "Dna" <[email-masked]>
Sent: Tuesday, July 26, 2005 6:31 AM
Subject: Re: Flash renumbering

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 26 Jul 2005 16:40:26 -0700

> hence we are left with #2.

FWIW I'm of the same opinion.

> received without the prefix, start getting suspicious.

That is an interesting idea, because when there is intermittent 
connectivity and packet loss, it is more likely to occur for the hosts 
than for router-to-router communication (assuming the traditional 
deployment of routers on a wired network - a wireless mesh of routers 
would potentially change this).

Thus the router not hearing a prefix from another router for 1.5 hours 
is a more reasonable indication that the prefix can be dropped, than a 
host not hearing it for 1.5 hours.

But what would we do in the case when all the prefixes don't fit in one 
RA hence the complete bit can not be set?

> from the previous email as a starting point.

ok

    Erik

---

From: Sathya Narayanan <[email-masked]>
Date: Wed, 27 Jul 2005 14:03:13 -0400

Erik Nordmark wrote:

> But what would we do in the case when all the prefixes don't fit in
> one RA hence the complete bit can not be set?

I know this is always an issue. But, isn't it a general problem about
CompleteRA which we need to think about either way?

I don't remember why we decided to remove the #prefixes field from the
DNAO.  I thought most of us felt that this field will help out with
being able to send the prefixes in two or more RA if they don't fit in a
single RA.

So, let me bring #prefixes back instead of the complete bit, here is
what I propose when the prefixes don't fit in one RA:
1) Divide the prefixes into groups with atleast one common prefix so
that each group will fit in a single RA.
2) Set the #prefixes field in the DNAO to the total number of prefixes
(The semantics for this is "This is the number of prefixes on the link
*I* know of").

>> from the previous email as a starting point.

So, do you want me to write it? Brett?

- Sathya

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 28 Jul 2005 02:04:59 -0700

> CompleteRA which we need to think about either way?

In other cases we have the CPL logic ("wait for 4 seconds") to fall back 
on when the complete bit isn't set.

I suspect in you suggestion we can have the routers handle things 
without a complete bit; if a router hasn't heard a learned prefix from 
any other router, then after 1.5 hours it can drop it from the learned 
prefixes.

Thus the issue now becomes whether and how the router can communicate to 
the hosts that this is no longer a (learned) prefix on the link. We can 
overload the complete bit with this when the prefixes all fit in one RA, 
but we could perhaps also do some explicit "removal of learned prefix" 
type of option??

> being able to send the prefixes in two or more RA if they don't fit in a

Sure you can send them, but that doesn't mean we know what the semantics 
need to be on the receiver.

> (The semantics for this is "This is the number of prefixes on the link

I don't think #2 can work in a robust manner unless we apply normal 
fragmentation/reassembly to such large RAs. And I don't think we need 
this complexity.

   Erik