Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. Landmark Prefix

From: Greg Daley <[email-masked]>
Date: Fri, 22 Jul 2005 23:55:26 +1000

Hi JinHyeock, 

There are too many topics in this e-mail, so if we need to
discuss all of the topics further it may be good to split
the threads.

----- Original Message -----
From: JinHyeock Choi <[email-masked]>
Date: Friday, July 22, 2005 6:49 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
Landmark Prefix
> Greg 
> 
> > Right at the bottom is a proposal for a "Graceful"
> > means of surviving flash renumbering with Prefix Landmarks.
> > 
> > It's not really necessary in the general case if routers
> > retract prefixes with lifetime=0 advertisements, if they
> > wish to assign the prefix elsewhere before normal
> > lifetime expiry.
> 
> I have difficulty understanding that. Does that take into 
> consideration packet loss?  

It does, if the prefixes are retracted for multiple RA intervals,
or if changes are advertised as defined in RFC 2461 section 6.2.4.

> > > As of my memory, WG didn't made such a decision.
> > 
> > It made the decision at the same time it discarded Numeric LinkIDs,
> > Deterministic FastRA etc: when it agreed to focus on 0ne or Two
> > potential solutions (with specific propeFrom [email-masked] Sun Jul 24 23:36:09 2005
Date: Fri, 22 Jul 2005 23:55:26 +1000
From: Greg Daley <[email-masked]>
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. Landmark
 Prefix
Sender: [email-masked]
To: JinHyeock Choi <[email-masked]>
Cc: [email-masked], Syam Madanapalli <[email-masked]>,
        Brett Pentland <[email-masked]>,
        James Kempf <[email-masked]>, Dna <[email-masked]>

Hi JinHyeock, 

There are too many topics in this e-mail, so if we need to
discuss all of the topics further it may be good to split
the threads.

----- Original Message -----
From: JinHyeock Choi <[email-masked]>
Date: Friday, July 22, 2005 6:49 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
Landmark Prefix
> Greg 
> 
> > Right at the bottom is a proposal for a "Graceful"
> > means of surviving flash renumbering with Prefix Landmarks.
> > 
> > It's not really necessary in the general case if routers
> > retract prefixes with lifetime=0 advertisements, if they
> > wish to assign the prefix elsewhere before normal
> > lifetime expiry.
> 
> I have difficulty understanding that. Does that take into 
> consideration packet loss?  

It does, if the prefixes are retracted for multiple RA intervals,
or if changes are advertised as defined in RFC 2461 section 6.2.4.

> > > As of my memory, WG didn't made such a decision.
> > 
> > It made the decision at the same time it discarded Numeric LinkIDs,
> > Deterministic FastRA etc: when it agreed to focus on 0ne or Two
> > potential solutions (with specific properties) at the last IETF.
> 
> No, it didn't make such a decision. (It's strange that it was claimed
> that Linkid had been decided to be removed when I presented it. )

I'm referring to draft-pentland-mobileip-linkid-03.txt (which was on
the quoted list too).

> At the time of Minneapolis meeting, as possible DNA solution 
> candidates,  I had in mind 'CompleteRA', 'Prefix based Linkid' and
> 'FRD'. So I took extra and intentional care that WG would not
> throw away those 3 schemes. 
> 
> As of my memory, only "ruling out" process happened during DT 
> discussion at Wednesday morning and neither one of three schemes 
> was ruled out at the meeting. 
>
> I cc Brett's mail after the meeting to back up my memory. 
[cut]
> 
>   Fast advertisement:
>       Fast Router Discovery
>       Hash-ordered FastRA (is that a bit easier to say?  :) )
>       Probabilistic FastRA
[cut]

I think you miss the point.  FastRD was left in because it's
possible to apply, but it's not capable of being _the_ general
solution for DNA in all cases.

Modification of Link-Layer devices is not an option for many
environments, so we need to rely upon a base solution which
only changes hosts and routers.

Optimizations beyond this would have to be specified separately.

> > > It's my opinion that if one scheme can perform DNA without
> > > RS involvement, that's the pro for the scheme we need to
> > > take into consideration. 
> > It's no more a pro for LinkID than for CompleteRA.
> 
> ok. At this point, my assertion is only that 
> the above is a worthy criterion to consider when we evaluate 
> schemes. 

Well, it's the same for both schemes, and therefore shouldn't
take up our highest priority (or any if we're pressed for time)...

Please consider spending time on issues which help to differentiate
the solutions.

[cut]
> > I'd prefer "At least 1" or "Defaults to 1" x 4 seconds.
> 
> Right but I am not arguing that such a case is impossible. I am 
> talking only that such a case seems to be rather an exception. 
> 
> Also this is why we think that it is ok for a host to
> send 1 RS and waits for 4 secs to collect (solicited) RAs
> and declare CCL complete.
> 
> Without a packet loss, the host will generate the complete prefix 
> list. Even some packet loss may cause an incomplete prefix list,
> there is a further chance for the host to get the missing prefixes
> before it receives link UP notification, i.e. moves to another AP.
> 
> Even the host moves to another AP with incomplete prefix list,
> the first RA may contain the prefix in its prefix list.
> 
> Considering all those above, even if the host performs only one
> RS/ RA exchange, it will be very rare for the host to falsely
> assume a link change. So I think that occasional additional
> signaling  is acceptable.

I guess that's a point of difference in our opinions.

My belief in immediate construction of CPL with completeRA is based
on how useful I've seen it to be in implementation.

[cut]
> > > Answering "Yes" also takes definite knowledge and synchronization.
> > >
> > > Allow me an example. Assume a link with two routers R1 and R2.
> > > R1 advertises Prefix1 and R2 advertise Prefix2 and Prefix3.
> > > R1 and R2 gathers the prefixes to make the complete prefix list
> > > {Prefix1, Prefix2, Prefix3}.
> > >
> > > Then R2 removes Prefix3 but the RA advertising the removal
> > > was lost and R1 doesn't receive it. So afterwards, if a (dormant)
> > > host send an RS with Prefix3 to R1, it will falsely answer "YES",
> > > i.e. Prefix3 is in this link.
> > >
> > > Am I missing something?
> > 
> > Yes.
> > 
> > The same thing happens with LinkID
> > 
> > In this case, the Router1 will not identify that the LinkID
> > has changed either, if the smallest prefix disappears (for
> > example if Prefix3 is actually the smallest prefix).
> > 
> > Responses for LinkID will therefore also conflict, Router1 will
> > have a LinkID of prefix Prefix3, even if that prefix has been
> > assigned to an adjacent link.
> 
> Linkid is designed to deal with such a pathological case with 
> linkid prefix list.  rties) at the last IETF.
> 
> No, it didn't make such a decision. (It's strange that it was claimed
> that Linkid had been decided to be removed when I presented it. )

I'm referring to draft-pentland-mobileip-linkid-03.txt (which was on
the quoted list too).

> At the time of Minneapolis meeting, as possible DNA solution 
> candidates,  I had in mind 'CompleteRA', 'Prefix based Linkid' and
> 'FRD'. So I took extra and intentional care that WG would not
> throw away those 3 schemes. 
> 
> As of my memory, only "ruling out" process happened during DT 
> discussion at Wednesday morning and neither one of three schemes 
> was ruled out at the meeting. 
>
> I cc Brett's mail after the meeting to back up my memory. 
[cut]
> 
>   Fast advertisement:
>       Fast Router Discovery
>       Hash-ordered FastRA (is that a bit easier to say?  :) )
>       Probabilistic FastRA
[cut]

I think you miss the point.  FastRD was left in because it's
possible to apply, but it's not capable of being _the_ general
solution for DNA in all cases.

Modification of Link-Layer devices is not an option for many
environments, so we need to rely upon a base solution which
only changes hosts and routers.

Optimizations beyond this would have to be specified separately.

> > > It's my opinion that if one scheme can perform DNA without
> > > RS involvement, that's the pro for the scheme we need to
> > > take into consideration. 
> > It's no more a pro for LinkID than for CompleteRA.
> 
> ok. At this point, my assertion is only that 
> the above is a worthy criterion to consider when we evaluate 
> schemes. 

Well, it's the same for both schemes, and therefore shouldn't
take up our highest priority (or any if we're pressed for time)...

Please consider spending time on issues which help to differentiate
the solutions.

[cut]
> > I'd prefer "At least 1" or "Defaults to 1" x 4 seconds.
> 
> Right but I am not arguing that such a case is impossible. I am 
> talking only that such a case seems to be rather an exception. 
> 
> Also this is why we think that it is ok for a host to
> send 1 RS and waits for 4 secs to collect (solicited) RAs
> and declare CCL complete.
> 
> Without a packet loss, the host will generate the complete prefix 
> list. Even some packet loss may cause an incomplete prefix list,
> there is a further chance for the host to get the missing prefixes
> before it receives link UP notification, i.e. moves to another AP.
> 
> Even the host moves to another AP with incomplete prefix list,
> the first RA may contain the prefix in its prefix list.
> 
> Considering all those above, even if the host performs only one
> RS/ RA exchange, it will be very rare for the host to falsely
> assume a link change. So I think that occasional additional
> signaling  is acceptable.

I guess that's a point of difference in our opinions.

My belief in immediate construction of CPL with completeRA is based
on how useful I've seen it to be in implementation.

[cut]
> > > Answering "Yes" also takes definite knowledge and synchronization.
> > >
> > > Allow me an example. Assume a link with two routers R1 and R2.
> > > R1 advertises Prefix1 and R2 advertise Prefix2 and Prefix3.
> > > R1 and R2 gathers the prefixes to make the complete prefix list
> > > {Prefix1, Prefix2, Prefix3}.
> > >
> > > Then R2 removes Prefix3 but the RA advertising the removal
> > > was lost and R1 doesn't receive it. So afterwards, if a (dormant)
> > > host send an RS with Prefix3 to R1, it will falsely answer "YES",
> > > i.e. Prefix3 is in this link.
> > >
> > > Am I missing something?
> > 
> > Yes.
> > 
> > The same thing happens with LinkID
> > 
> > In this case, the Router1 will not identify that the LinkID
> > has changed either, if the smallest prefix disappears (for
> > example if Prefix3 is actually the smallest prefix).
> > 
> > Responses for LinkID will therefore also conflict, Router1 will
> > have a LinkID of prefix Prefix3, even if that prefix has been
> > assigned to an adjacent link.
> 
> Linkid is designed to deal with such a pathological case with 
> linkid prefix list.  Kindly check Sec 3 and 4. 

From 4.2 it's not clear if the first RA received on the link
(if it advertises the old LinkID) is taken as non-movement, if the
host arrives from  the link to which this prefix has been
assigned (and is LinkID).

It looks like it is.

The host hasn't seen the other LinkID before, and when the next
RA arrives indicating the NewLinkID and OldLinkID, it could easily be
taken as a change of LinkID on the previously visited link.

AFAICS, this is the exact same danger as described for Landmarks
(but not completeRA, due to the redundant information).

> > For Prefix Landmarking:
> > 
> > If any RAs by received by R1 indicating that the lifetime is
> > diminished, this will time out the entries.  Any single reception
> > of a lifetime zero advertisement from the owning router will
> > remove the prefix.
> > 
> > This is the same as LinkID.
> > 
> > So if Prefix Landmarking believes the prefix is still on-link
> > (and Prefix Landmarking has similar timers for lifetimes that
> > LinkID does) then the incorrect state will last about as long
> > for either.
> > 
> > The assumption is that prefixes retracted without (effective)
> > zero lifetime advertisement and assigned to another link cause
> > problems for up to 90 minutes or so:
> > 
> > This is the same for Prefix Landmarks, CompleteRA, LinkID and
> > (in hosts' view) CPL.
> >
> > This is a very tight corner case, since routers listen to RAs
> > in DNA, don't sleep, and routers should retract prefixes.
> > 
> > At least with CompleteRA, you can ignore learned DNAO contents
> > since the rest of the CompleteRA will not match the existing
> > Complete Prefix List.
> 
> I have difficulty following the above. 
 
[cut]
> > > "NO" will supercede a "YES", if it is received first, right?
> > 
> > Yes, but a false movement detection is actually better than a false
> > non-movement detection, since the host recovers in milliseconds, not
> > minutes.
> 
> Does the above mean "NO" will always supercede "YES", because 
> a false movement detection is actually better than a false non-
> movement detection?

If it is received first, yes.

If it isn't it's only because a router believes a prefix exists on-link,
where it hasn't recveived appropriate preefix information options to 
update it.

This is the same as for LinkID.

[cut]
> > In that case though, it can also update the other routers with
> > the appropriate RA (prefix lifetime=0).
> 
> Yes, but it needs additional mechanism to ensure every routers 
> will receive the appropriate RA. 

I'ts already defined.

6.2.4.  Sending Unsolicited Router Advertisements

Especially the section describing advertising changes

It's optional but has been around for a long time, and
doesn't require additional text in DNA...

[cut]
> 
> > A practical solution for Prefix Landmarks may be to partly
> > ignore "Yes" answers - since they don't require much action: that
> > is keep the DNA process open if there's a non-movement indication.
> > 
> > The DNA addressing mechanism may be re-normalized (and packet 
> > flow can occur with the global addresses), but subsequent
> > reception of a trusted "No" RA within (say 500ms) could be used
> > as a hint to re-build a CPL - which may be a cause to detect
> > change in a few seconds.
> 
> Maybe, but the scheme seems to become more complicated. At least, I
> come to have difficulty following your arguments. 

It's not particularly complicated:

If you receive an indication that no change is needed:
Don't change anything and start communicating again.
If you then receive an indication that change is needed,
it may be needed.

This is all to handle the concept of "Flash renumbering"
(still to be debated if it's a real issue (See section 12 of
RFC2461)) under "packet loss" of three packets or where routers
haven't followed the recommendation of RFC2461 section 6.2.6

Did we need to do anything anyway?

If we assume that routers follow RFC2461 6.2.6 if they're 
flash renumbering (and we recommend it), then no live router
could advertise the wrong prefix with Landmarks, CompleteRA
or LinkKindly check Sec 3 and 4. 

From 4.2 it's not clear if the first RA received on the link
(if it advertises the old LinkID) is taken as non-movement, if the
host arrives from  the link to which this prefix has been
assigned (and is LinkID).

It looks like it is.

The host hasn't seen the other LinkID before, and when the next
RA arrives indicating the NewLinkID and OldLinkID, it could easily be
taken as a change of LinkID on the previously visited link.

AFAICS, this is the exact same danger as described for Landmarks
(but not completeRA, due to the redundant information).

> > For Prefix Landmarking:
> > 
> > If any RAs by received by R1 indicating that the lifetime is
> > diminished, this will time out the entries.  Any single reception
> > of a lifetime zero advertisement from the owning router will
> > remove the prefix.
> > 
> > This is the same as LinkID.
> > 
> > So if Prefix Landmarking believes the prefix is still on-link
> > (and Prefix Landmarking has similar timers for lifetimes that
> > LinkID does) then the incorrect state will last about as long
> > for either.
> > 
> > The assumption is that prefixes retracted without (effective)
> > zero lifetime advertisement and assigned to another link cause
> > problems for up to 90 minutes or so:
> > 
> > This is the same for Prefix Landmarks, CompleteRA, LinkID and
> > (in hosts' view) CPL.
> >
> > This is a very tight corner case, since routers listen to RAs
> > in DNA, don't sleep, and routers should retract prefixes.
> > 
> > At least with CompleteRA, you can ignore learned DNAO contents
> > since the rest of the CompleteRA will not match the existing
> > Complete Prefix List.
> 
> I have difficulty following the above. 
 
[cut]
> > > "NO" will supercede a "YES", if it is received first, right?
> > 
> > Yes, but a false movement detection is actually better than a false
> > non-movement detection, since the host recovers in milliseconds, not
> > minutes.
> 
> Does the above mean "NO" will always supercede "YES", because 
> a false movement detection is actually better than a false non-
> movement detection?

If it is received first, yes.

If it isn't it's only because a router believes a prefix exists on-link,
where it hasn't recveived appropriate preefix information options to 
update it.

This is the same as for LinkID.

[cut]
> > In that case though, it can also update the other routers with
> > the appropriate RA (prefix lifetime=0).
> 
> Yes, but it needs additional mechanism to ensure every routers 
> will receive the appropriate RA. 

I'ts already defined.

6.2.4.  Sending Unsolicited Router Advertisements

Especially the section describing advertising changes

It's optional but has been around for a long time, and
doesn't require additional text in DNA...

[cut]
> 
> > A practical solution for Prefix Landmarks may be to partly
> > ignore "Yes" answers - since they don't require much action: that
> > is keep the DNA process open if there's a non-movement indication.
> > 
> > The DNA addressing mechanism may be re-normalized (and packet 
> > flow can occur with the global addresses), but subsequent
> > reception of a trusted "No" RA within (say 500ms) could be used
> > as a hint to re-build a CPL - which may be a cause to detect
> > change in a few seconds.
> 
> Maybe, but the scheme seems to become more complicated. At least, I
> come to have difficulty following your arguments. 

It's not particularly complicated:

If you receive an indication that no change is needed:
Don't change anything and start communicating again.
If you then receive an indication that change is needed,
it may be needed.

This is all to handle the concept of "Flash renumbering"
(still to be debated if it's a real issue (See section 12 of
RFC2461)) under "packet loss" of three packets or where routers
haven't followed the recommendation of RFC2461 section 6.2.6

Did we need to do anything anyway?

If we assume that routers follow RFC2461 6.2.6 if they're 
flash renumbering (and we recommend it), then no live router
could advertise the wrong prefix with Landmarks, CompleteRA
or LinkID.

This is a lot less complicated...

Greg

---

From: JinHyeock Choi <[email-masked]>
Date: Sat, 23 Jul 2005 14:46:38 +0900

Greg

> I'm referring to draft-pentland-mobileip-linkid-03.txt (which was on

I meant the claim made by other person, not by you. 

> Optimizations beyond this would have to be specified separately.

As of my memory, in DT meeting, no such agreement (about why 
FRD is left) is made.   

An unfortunate incident in D.C. made a paranoid out of me, so 
I took keen notice about FRD treatment.  

About the FRD applicability, that's the decision for WG. If WG 
chooses FRD for its high performance in spite of L2 reliance, 
it's WG's call. 

It's ok for you have an opinion about FRD and its treatment but 
I ask you NOT to assume it as an official agreement before going 
through a proper decision procedure. 

> take up our highest priority (or any if we're pressed for time)...

This the the conclusion I can't be sure of. There may be a link 
in which CompleteRA can't be made as mentioned in Brett's draft
below,  

   It may not be possible to include all of the prefixes in use on the
   link due to MTU or administrative limitations.  

> Please consider spending time on issues which help to differentiate

ok. I guess we are in agreement that unsolicited RA concern is 
a worthy criterion, so let's investigate how it differentiate two schemes. 

> (but not completeRA, due to the redundant information).

I have difficulty understanding the above example. Kindly clarify 
more. 

> doesn't require additional text in DNA...

I meant to make it extra-sure that all routers have received the 
appropriate RA even under the packet loss. 6.2.4 is rather a UDP 
like and I meant a TCP like assurance. 

> could advertise the wrong prefix with Landmarks, CompleteRA

I have difficulty following your thoughts on the synchronization
issue for Landmark/ CompleteRA because new arguments pops 
up in each mail. It would help me a lot, if you summarize your 
thoughts in whole. 

Thanks for your kind consideration. 

Best Regards

JinHyeock