Erik Nordmark

JinHyeock Choi wrote:

> In linkid scheme, a prefix addition or deletion would not cause an incorrect decision, whereas there is such a possibility for Landmark/ CompleteRA.
> Allow me an example.
> Assume a link with a router R and host H. R advertises Prefix1.
> R1 happens to stop advertising Prefix1 and start advertising a new prefix Prefix2. 


But in this case, when all the prefixes are being removed and replaced with a completely new set of prefixes, there is little if no harm to incorrectly assume a link change (after all, all the addresses need to be reconfigured, etc).

A more realistic example is the one I included in my more recent email today.

> R announces it by sending an RA but H doesn't receive it.
> Then next time H receives CompleteRA with
> Prefix2, it will falsely assume a link change.   


Actually not; if will only assume a link change if it receives a link up event notification between the last time it heard a RA with Prefix1 and the first time it heard an RA with Prefix2.

   Erik

> Linkid scheme deal with such a temporary flapping by adopting extra techniques such as "Linkid Prefix List" or "LEAST_VALID_LIFETIME".
> I don't know how Landmark/ CompleteRA can make a correct decision
> under flapping without such an extra techniques.
> Thanks in advance for your kind consideration.
> Best Regards
>
> JinHyeock
>

JinHyock Choi

Erik


>>> > Allow me an example.
>>> >
>>> > Assume a link with a router R and host H.
>>> > R advertises Prefix1.
>>> >
>>> > R1 happens to stop advertising Prefix1 and
>>> > start advertising a new prefix Prefix2.
>
>> 
>> But in this case, when all the prefixes are being removed and replaced
>> with a completely new set of prefixes, there is little if no harm to
>> incorrectly assume a link change (after all, all the addresses need to
>> be reconfigured, etc).


By adding another router and a few more packet losses, we can make 
a pathological case with a problem. 


>> A more realistic example is the one I included in my more recent email
>> today.


We can discuss about how real such a problem is but my point is 
that linkid adopts extra techniques to survive even such an extreme 
pathologies. 


>>> > R announces it by sending an RA but H
>>> > doesn't receive it.
>>> >
>>> > Then next time H receives CompleteRA with
>>> > Prefix2, it will falsely assume a link change.
>
>> 
>> Actually not; if will only assume a link change if it receives a link up
>> event notification between the last time it heard a RA with Prefix1 and
>> the first time it heard an RA with Prefix2.


Is it so? Does that mean the hosts would not make a decision 
based on unsolicited CompleteRAs? Is it written in an I-D?

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

Erik Nordmark

JinHyeock Choi wrote:

> By adding another router and a few more packet losses, we can make a pathological case with a problem. 


Can you provide an example?

> Is it so? Does that mean the hosts would not make a decision based on unsolicited CompleteRAs? Is it written in an I-D?


I thought this was a working group trying to figure out how we'd like the solution to work; not some attempt to choose one out of a set of competing, and perhaps incomplete, internet-drafts.

   Erik 

Syam Madanapalli

Erik,



> JinHyeock Choi wrote:
>
>> In linkid scheme, a prefix addition or deletion would not cause an incorrect decision, whereas there is such a possibility for Landmark/ CompleteRA. Allow me an example. Assume a link with a router R and host H. R advertises Prefix1. R1 happens to stop advertising Prefix1 and start advertising a new prefix Prefix2.
>
>
> But in this case, when all the prefixes are being removed and replaced with a completely new set of prefixes, there is little if no harm to incorrectly assume a link change (after all, all the addresses need to be reconfigured, etc).
>
> A more realistic example is the one I included in my more recent email today.
>
>> R announces it by sending an RA but H doesn't receive it. Then next time H receives CompleteRA with
>> Prefix2, it will falsely assume a link change.
>
>
> Actually not; if will only assume a link change if it receives a link up event notification between the last time it heard a RA with Prefix1 and the first time it heard an RA with Prefix2.


Let us assume the host is rebooting on the same link or changing its
Layer 2 access, even in this case the current linkid scheme does not
make the wrong decision of link change.

Syam

>
>    Erik
>
>> Linkid scheme deal with such a temporary flapping by adopting extra techniques such as "Linkid Prefix List" or "LEAST_VALID_LIFETIME". I don't know how Landmark/ CompleteRA can make a correct decision
>> under flapping without such an extra techniques. Thanks in advance for your kind consideration. Best Regards
>>
>> JinHyeock

JinHyeock Choi

Erik


>>> > By adding another router and a few more packet losses, we can make
>>> > a pathological case with a problem.
>
>> 
>> Can you provide an example?


ok. I admit this is a crude one but all I can think of right now.  
(Because it's not clear to me how a host base its decision 
on CompleteRA, I switch to landmark one.) 

Assume a link with two routers R1 and R2 and a host H. 
R1 advertises Prefix1 and R2 Prefix2. 

R2 stops advertising Prefix2 and starts advertising Prefix3. 
R2 announces the prefix change by sending an RA but
both R1 and H don't receive it. 

Then H happens to change its AP in the same link 
and send an RS with landmark Prefix2. It also happens that 
R2 replies first and sends an RA with NO and Prefix3. 
H falsely assumes a link change. 


>>> > Is it so? Does that mean the hosts would not make a decision
>>> > based on unsolicited CompleteRAs? Is it written in an I-D?
>
>> 
>> I thought this was a working group trying to figure out how we'd like
>> the solution to work; not some attempt to choose one out of a set of
>> competing, and perhaps incomplete, internet-drafts.


ok. 


>>>> Then next time H receives CompleteRA with
>>>> Prefix2, it will falsely assume a link change.
>
>>
>> Actually not; if will only assume a link change if it receives a link up
>> event notification between the last time it heard a RA with Prefix1 and
>> the first time it heard an RA with Prefix2.


The above is not clear to me yet. Allow me a question to help 
my understanding.  

Assume a host moves to a different link but fails to receive a 
Link Up event Notification. Then the host will not assume a link 
change even if it receives a different unsolicted CompleteRA? 
 
Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

Syam Madanapalli

Hi Brett,


> Hi Syam,
>
> Syam Madanapalli wrote:
>
>> Hi Brett,
>>
>> [cut]
>>
>>>>
>>>> These are my line of thoughts. We can't avoid a temporary flapping for the related set, the set of
>>>> all prefixes
>>>> on a link. In linkid scheme, one item (linkid prefix) of the set matters for DNA
>>>> performance.
>>>> So we designed a few special schemes for the linkid prefix so that
>>>> linkid prefix(es)
>>>> won't give incorrect information about a link change, even under
>>>> temporary flapping.
>>>>
>>>> But for Complete RA or Landmark, IMO, we need to adopt similar schemes such as "Linkid Prefix List" or "Old linkid advertising rule" to all
>>>> prefixes because we
>>>> don't know which prefix will affect DNA decision.
>>>
>>>
>>>
>>> For Landmarks:
>>>
>>>    If a prefix is removed, the host will receive a "NO" answer, which
>>>    also include prefixes that are on the link and have been seen by the
>>>    host before so it can see there is no link change and yet will also
>>>    know that the prefix it was using as a landmark is no longer valid.
>>>    (I think we need text to clear that up)
>>
>>
>>
>> A host may get 'YES' answer from a Router (R2) before the 'NO' answer
>> from Router (R1) because the deletion of the prefix (P1) at R1 might not have
>> propagated to R2 at the time of answering the landmar query for P1.
>
>
> Yes, and as far as DNA goes that is the correct answer in that there is
> no link change.


What if you get answer 'NO' first?
Will you check with the prefixes received in the RA?
This looks better compared just depending on the
Landmark answer. Otherwise host makes wrong decision.

[cut]

>>
>> As we are not anyway interested in building the complete prefix list,
>> why cannot we just depend on CPL to build. I did not remember
>> the waiting time for building the CPL, but I am sure it will be in few
>> seconds. When a host sends RS with Landmark question, and answer
>> is 'NO' a host can buid the CPL (almost) from the resulting RAs which
>> is sufficient to detect the link change at the new link even if the node
>> moves within few seconds.
>
>
> Just relying on CPL instead of CompleteRA is a possibility.  Depends if
> folks are willing to have a window of 12 seconds (?) after each link
> change where another link change will not be able to be detect rapidly.
> When we wrote the proposal, we felt that we needed something more.


I think 12 seconds is very small considering mobility  :)

>
>>>
>>> LinkID has a much more complex technique for managing prefix change
>>> involving advertising prefixes for some length of time with short
>>> lifetimes before advertising them with zero lifetimes in order to
>>> avoid confusion.  I don't think this is needed for Landmark/CompleteRA.
>>
>>
>>
>> If we need to have the similar confidence in determining the link change with
>> graceful prefix addition/deletion, we need similar techniques for all of the
>> prefixes on the link incase of Landmark/CompleteRA.
>
>
> I think I've shown that those additional techniques are not needed for
> Landmark/CompleteRA.  It may be that they are not needed for LinkID
> either.  I think the LinkID proposal would need to be modified to allow
> hosts to use the other prefixes in the RA for link identification, not
> just those marked as LinkIDs.


Linkid does allows the checking for the other prefixes in RA, but it checks
with only the linkid list that host maintains.

>
> Brett.
>

JinHyeock Choi

Erik


>> Just to make it sure we are all talking about the same thing, by
>> "flapping" I assume we mean the following:
>> 
>> When the set of prefixes on a link changes, e.g., a prefix is being
>> added or a prefix is being removed, there is the possibility that a host
>> see more than one change (see things flapping back and forth) until the
>> routers have been synchronized.
>> For instance, if the prefix set is {P1, P2} and P3 is added, one would
>> ideally have the host see {P1, P2} and then see {P1, P2, P3}, but when
>> RAs come from different routers, there might be a small window when the
>> host sees RAs vary in a sequence like {P1, P2}, {P1, P2, P3}, {P1, P2},
>> {P1, P2, P3}. This is due to the third RA (with {P1, P2}) coming from a
>> router which hadn't seen P3 yet.
>> 
>> If there is no packet loss, the window during which this can happen is
>> very small (basically the propagation delay of the RA which carries the
>> new prefix from one router to another). With packet loss, the worst case
>> window is the time it takes to successfully retransmit the RA so that
>> the other routers see it.


I use flapping in more general case as below. 

When the set of prefixes on a link changes, 
there is the possibility of temporary lack of synchronization, i.e. 
the nodes on the link (such as routers and hosts) 
may have different set of prefixes (on the link) for the time being.  

For example, if the prefix set is {P1, P2} and P3 is added, one would
ideally have all the nodes on the link have the prefix set {P1, P2, P3} 
instantly. But due to packet loss, it is possible that one router has the
prefix set {P1, P2} and the other router has {P1, P2, P3} for some time.

If hosts check for link change with prefix information, such a lack of 
(temporary) synchronization may cause a false link identity detection. 


>> Yes, but linkid still has flapping issues; you just have a technique to
>> avoid this resulting in an incorrect result. (In the case of linkid the
>> flapping effects the linkID which each routers picks. Thus if P3 was the
>> numerically smallest prefix then the flapping in the prefix set would
>> result in flapping in the linkID prefix the host sees.) Handling this
>> requires some additional logic in linkID.


Exactly. I found it extremely difficult to abolishing flapping completely. 
So I took the approach to make hosts to make the right decision under
mild flapping. 


>>> > But for Complete RA or Landmark, IMO, we need to adopt similar schemes such
>>> > as "Linkid Prefix List" or "Old linkid advertising rule" to all
>>> > prefixes because we
>>> > don't know which prefix will affect DNA decision.
>
>> 
>> I don't think so. CompleteRA is basically the same as CPL in this
>> respect, in that the prefix sets are compared to see whether they are
>> disjoint. In the above example, there is overlap between {P1, P2} and
>> {P1, P2, P3} hence the host would correctly conclude that it didn't move.
>> 
>> Landmark is basically an optimization of completeRA, with a fallback to
>> completeRA/CPL prefix comparisons when there was no landmark response,
>> or no DNA capable router, respectively. Thus the completeRA/CPL
>> observation holds. This even takes care of the case when a host picks up
>> {P1, P2, P3}, selects P3 as its landmark, gets a new link up
>> notification, sends a RS, and get a response with "landmark P3 = NO,
>> PIO={P1, P2}, from a router which hasn't yet seen P3, since the host
>> would compare the prefix sets in that case as well. (I'm not sure that
>> is in the I-D, but I think it needs to be in the I-D to handle the
>> analogous case of moving to a link with no DNA routers.)


ok. Allow me to clarify this

In Landmark/ CompleteRA, 
when a host receives a solicited RA, 
the host check for link change with both 
1) Landmark option with YES/NO bit and
2) prefixes in the RA. 

If the (solicited) RA carries 1) NO answer and 2) a known prefix, 
the host would not assume a link change. 
(So in effect, "known prefix" would overrule "NO".)

Is this right? 


>>> > If all routers agree on the selection algorithm, it's almost automatical
>>> > to select the prefix among the set of prefixes. That's why I chose the
>>> > simplest selection scheme, picking the smallest prefix.
>
>> 
>> Sure. But my point is that a router needs to be prepared to receive a RA
>> where some other router, due to not having seen an RA, or being broken,
>> is claiming that some other prefix is the linkID. That's some added
>> complexity.


Routers don't pay attention what other routers advertise as a linkid. 
They generate the complete prefix set and pick the linkid prefix for 
themselves. You recommended this approach. 


>>> > I thought it simpler to make routers agree on the same selection
>>> > scheme but would like to hear your scheme when developed.
>
>> 
>> I think it would be isomorphic to linkid; just a different way of
>> thinking about the problem. (BTW: "simple" and "distributed agreement"
>> don't belong together in the same sentence.  :-) 


ok and agree.  :-) 

Best Regards

JinHyeock

Brett Pentland

Hi JinHyeock,

>>> By adding another router and a few more packet losses, we can make
>>> a pathological case with a problem.
>>
>>
>> Can you provide an example?
>
>
>
> ok. I admit this is a crude one but all I can think of right now.  (Because it's not clear to me how a host base its decision on CompleteRA, I switch to landmark one.)
> Assume a link with two routers R1 and R2 and a host H. R1 advertises Prefix1 and R2 Prefix2.
> R2 stops advertising Prefix2 and starts advertising Prefix3. R2 announces the prefix change by sending an RA but
> both R1 and H don't receive it.
> Then H happens to change its AP in the same link and send an RS with landmark Prefix2. It also happens that R2 replies first and sends an RA with NO and Prefix3. H falsely assumes a link change.  


I think you might have found one :)   Actually, there was some
discussion recently on whether a NO answer should only include
explcitly configured PIOs or should include a DNA option as well.
You may have found a good reason to include the DNA option.

In this case the DNAO in the NO answer would include P1 which would
allow the host to correctly recognise that there has been no change.

>>> Then next time H receives CompleteRA with
>>> Prefix2, it will falsely assume a link change.
>>
>>
>> Actually not; if will only assume a link change if it receives a link up
>> event notification between the last time it heard a RA with Prefix1 and
>> the first time it heard an RA with Prefix2.
>
>
>
> The above is not clear to me yet. Allow me a question to help my understanding. 
> Assume a host moves to a different link but fails to receive a Link Up event Notification. Then the host will not assume a link change even if it receives a different unsolicted CompleteRA? 


As written, I don't think the draft ties the decision making to a link
layer indication.  In the instance you brought up an incorrect decision
would be made.  However, this is the pathological case I mentioned the
other day and the fix is the same as for LinkID.  That is, to require
the router to advertise both prefixes (or in fact just some overlap in
the sets of prefixes) for some period of time.  There is nothing
fundamental about LinkID that lets it cope with this situation.  It's
just that the LinkID draft has a bit of text that says not to do that.

Brett. 

JinHyeock Choi

Dear Brett

Thanks for your summary. I assume Landmark/ CompleteRA will follow
the memo.  


>> For Landmarks:
>> 
>>    If a prefix is removed, the host will receive a "NO" answer, which
>>    also include prefixes that are on the link and have been seen by the
>>    host before so it can see there is no link change and yet will also
>>    know that the prefix it was using as a landmark is no longer valid.
>>    (I think we need text to clear that up)


So in this case, the known prefix in the RA overrules "NO" answer. 
Right? 


>> For CompleteRA (which is proposed as a fallback for when it is not
>> possible to use landmarks):
>> 
>>    By its nature it creates overlap between the sets of RAs advertised
>>    by the routers on a link.  It doesn't matter whether the sets
>>    agree completely or not, as long as there's overlap (because link-
>>    change is detected by receiving a RA with a set disjoint from the
>>    set of prefixes the host has seen on the link).  The pathological
>>    case that we may need to take action to avoid is where a router
>>    that is currently configured with all of the prefixes in use on a
>>    link, suddenly has all of them removed and replaced with a new
>>    disjoint set.  We need to add some text to say not to do that.


So I understand you try to assure that there always a overlapping 
prefix among CompleteRAs even under prefix change. Right?  

I admit that I don't look over Landmark/CompleteRA 01-draft but the 
above seems a little different from what I remember. I think it would
help to write those down lest there should be unnecessary confusion. 

Best Regards

JinHyeock

Tero Kauppinen

>Assume a link with two routers R1 and R2 and a host H.
>> R1 advertises Prefix1 and R2 Prefix2.
>> 
>> R2 stops advertising Prefix2 and starts advertising Prefix3.
>> R2 announces the prefix change by sending an RA but
>> both R1 and H don't receive it.
>> 
>> Then H happens to change its AP in the same link
>> and send an RS with landmark Prefix2. It also happens that
>> R2 replies first and sends an RA with NO and Prefix3.
>> H falsely assumes a link change.


But isn't it actually so that in this case the host shouldn't use an
address based on Prefix2 and thus reconfiguration is required (i.e. link
change from host H point of view)? After all, Prefix2 is not anymore
valid.

Tero

Ranjitsinh Wable

Hi Brett,

----- Original Message ----- From: "Brett Pentland" <brett.pentland@eng.monash.edu.au>
To: "JinHyeock Choi" <jinchoe@gmail.com>
Cc: "Erik Nordmark" <erik.nordmark@sun.com>; "Syam Madanapalli" <syam@samsung.com>; <greg.daley@eng.monash.edu.au>; "James Kempf" <Kempf@docomolabs-usa.com>; "Dna" <dna@eng.monash.edu.au>
Sent: Tuesday, July 26, 2005 10:26 AM
Subject: Re: [DNA] [Issue X] LinkID v.s. Landmark Prefix


> Hi JinHyeock,
>
>>>> By adding another router and a few more packet losses, we can make
>>>> a pathological case with a problem.
>>>
>>>
>>> Can you provide an example?
>>
>>
>>
>> ok. I admit this is a crude one but all I can think of right now. (Because it's not clear to me how a host base its decision on CompleteRA, I switch to landmark one.) Assume a link with two routers R1 and R2 and a host H. R1 advertises Prefix1 and R2 Prefix2. R2 stops advertising Prefix2 and starts advertising Prefix3. R2 announces the prefix change by sending an RA but
>> both R1 and H don't receive it. Then H happens to change its AP in the same link and send an RS with landmark Prefix2. It also happens that R2 replies first and sends an RA with NO and Prefix3. H falsely assumes a link change.
>
>
> I think you might have found one :)   Actually, there was some
> discussion recently on whether a NO answer should only include
> explcitly configured PIOs or should include a DNA option as well.
> You may have found a good reason to include the DNA option.
>
> In this case the DNAO in the NO answer would include P1 which would
> allow the host to correctly recognise that there has been no change.
>
So you mean to say that all the answers to the landmark questions will
have complete RA? Also how the P1 will help Host to decide that the
link is not changed? Host may not keep the list of all the prefixes on link,
which inturn makes it CPL.

>>>> Then next time H receives CompleteRA with
>>>> Prefix2, it will falsely assume a link change.
>>>
>>>
>>> Actually not; if will only assume a link change if it receives a link up
>>> event notification between the last time it heard a RA with Prefix1 and
>>> the first time it heard an RA with Prefix2.
>>
>>
>>
>> The above is not clear to me yet. Allow me a question to help my understanding.  Assume a host moves to a different link but fails to receive a Link Up event Notification. Then the host will not assume a link change even if it receives a different unsolicted CompleteRA?
>
>
> As written, I don't think the draft ties the decision making to a link
> layer indication.  In the instance you brought up an incorrect decision
> would be made.  However, this is the pathological case I mentioned the
> other day and the fix is the same as for LinkID.  That is, to require
> the router to advertise both prefixes (or in fact just some overlap in
> the sets of prefixes) for some period of time.  There is nothing
> fundamental about LinkID that lets it cope with this situation.  It's
> just that the LinkID draft has a bit of text that says not to do that.
>
If the decision in not made on the unsolicited CompleteRA and the
Link up indication is not the link to trigger the Landmark check.
Then what is must condition to achieve it. When you will trigger
the Landmark question? I think either both the cases has to be
there or it should just work with the link up indication.


Regards,

Wable R. U.

> Brett.
>

JinHyeock Choi

Brett


>> I think you might have found one  :)   


Thanks for your kind words.  :-) 

>> Actually, there was some
>> discussion recently on whether a NO answer should only include
>> explcitly configured PIOs or should include a DNA option as well.
>> You may have found a good reason to include the DNA option.
>> 
>> In this case the DNAO in the NO answer would include P1 which would
>> allow the host to correctly recognise that there has been no change.


ok. Then NO answer would include PIOs and a DNA option. Right? 
Then the RA is a CompleteRA, isn't it? 


>>> > The above is not clear to me yet. Allow me a question to help
>>> > my understanding.
>>> >
>>> > Assume a host moves to a different link but fails to receive a
>>> > Link Up event Notification. Then the host will not assume a link
>>> > change even if it receives a different unsolicted CompleteRA?
>
>> 
>> As written, I don't think the draft ties the decision making to a link
>> layer indication.  In the instance you brought up an incorrect decision
>> would be made.  


ok. But I am still confused. Kindly clarify in which way hosts
would make a decision.  

Best Regards

JinHyeock

JinHyeock Choi

Dear Tero


>>> > Assume a link with two routers R1 and R2 and a host H.
>>> > R1 advertises Prefix1 and R2 Prefix2.
>>> >
>>> > R2 stops advertising Prefix2 and starts advertising Prefix3.
>>> > R2 announces the prefix change by sending an RA but
>>> > both R1 and H don't receive it.
>>> >
>>> > Then H happens to change its AP in the same link
>>> > and send an RS with landmark Prefix2. It also happens that
>>> > R2 replies first and sends an RA with NO and Prefix3.
>>> > H falsely assumes a link change.
>
>> 
>> But isn't it actually so that in this case the host shouldn't use an
>> address based on Prefix2 and thus reconfiguration is required (i.e. link
>> change from host H point of view)? After all, Prefix2 is not anymore
>> valid.


Host may also have an address with Prefix1. While the address with
Prefix1 is valid, the host will throw it away because it thinks it is at 
a different link. 

Best Regards

JinHyeock

Brett Pentland

Hi Syam,

>>>>> These are my line of thoughts. We can't avoid a temporary flapping for the related set, the set of
>>>>> all prefixes
>>>>> on a link. In linkid scheme, one item (linkid prefix) of the set matters for DNA
>>>>> performance.
>>>>> So we designed a few special schemes for the linkid prefix so that
>>>>> linkid prefix(es)
>>>>> won't give incorrect information about a link change, even under
>>>>> temporary flapping.
>>>>>
>>>>> But for Complete RA or Landmark, IMO, we need to adopt similar schemes such as "Linkid Prefix List" or "Old linkid advertising rule" to all
>>>>> prefixes because we
>>>>> don't know which prefix will affect DNA decision.
>>>>
>>>>
>>>>
>>>>
>>>> For Landmarks:
>>>>
>>>>    If a prefix is removed, the host will receive a "NO" answer, which
>>>>    also include prefixes that are on the link and have been seen by the
>>>>    host before so it can see there is no link change and yet will also
>>>>    know that the prefix it was using as a landmark is no longer valid.
>>>>    (I think we need text to clear that up)
>>>
>>>
>>>
>>>
>>> A host may get 'YES' answer from a Router (R2) before the 'NO' answer
>>> from Router (R1) because the deletion of the prefix (P1) at R1 might not have
>>> propagated to R2 at the time of answering the landmar query for P1.
>>
>>
>>
>> Yes, and as far as DNA goes that is the correct answer in that there is
>> no link change.
>
>
>
> What if you get answer 'NO' first?
> Will you check with the prefixes received in the RA?
> This looks better compared just depending on the
> Landmark answer. Otherwise host makes wrong decision.
>
> [cut]


This question is one of the open issues (9).  My personal opinion is
that yes, the host should check the prefixes and if it sees overlap with
the prefixes it has already seen on the link, should decide that link
change has not taken place.

Brett. 

JinHyeock Choi

Dear Tero


>> I have been dead silence for quite a long time now. I haven't been able
>> to follow the WG progress and I feel somewhat lost. I spent a couple of
>> days last week trying to catch up with the work ... ~200 unread mails
>> and new drafts. Oh, dear...


I contributed some for that. Sorry. I ask your kind understanding.  :-) 

>>> > How do you think of FRD? We got a pretty nice result.  :-) 
>
>> 
>> I see it has potential. At a glance one concern which emerged to me was
>> possible security issues. Unfortunately I'm not much of a security
>> expert, and have some difficulties further analyzing the proposal from
>> that perspective.


ok. 


>>> > Maybe that's the way I'd better follow and FRD would better to be
>>> > content with informational RFC as a kind of auxiliary solution.
>
>> 
>> I'm sort of newbie when it comes to the IETF but I would assume that
>> some IETF people would have allergic reactions (much like I have with
>> politics) on solutions that have operator "connections" (couldn't find
>> any better English word right now). Taking that into account, I would
>> guess that the road of an informational RFC would be a bit less bumpy.


ok. 
 
Nowadays I barely keep myself afloat dealing with the volume of mailing 
list. (Am I already drowning?) To me, trying to process mailings feels like 
trying to swallow water directly out of high-pressure fire hose.  :-)  

See you soon in Paris, La Ville Luminaire, and let's have some fun together. 

Best Regards

JinHyeock

Brett Pentland

JinHyeock Choi wrote:

> Dear Brett
>
> Thanks for your summary. I assume Landmark/ CompleteRA will follow
> the memo. 
>
>> For Landmarks:
>>
>>   If a prefix is removed, the host will receive a "NO" answer, which
>>   also include prefixes that are on the link and have been seen by the
>>   host before so it can see there is no link change and yet will also
>>   know that the prefix it was using as a landmark is no longer valid.
>>   (I think we need text to clear that up)
>
>
>
> So in this case, the known prefix in the RA overrules "NO" answer. Right? 


See my answer to Syam.

>> For CompleteRA (which is proposed as a fallback for when it is not
>> possible to use landmarks):
>>
>>   By its nature it creates overlap between the sets of RAs advertised
>>   by the routers on a link.  It doesn't matter whether the sets
>>   agree completely or not, as long as there's overlap (because link-
>>   change is detected by receiving a RA with a set disjoint from the
>>   set of prefixes the host has seen on the link).  The pathological
>>   case that we may need to take action to avoid is where a router
>>   that is currently configured with all of the prefixes in use on a
>>   link, suddenly has all of them removed and replaced with a new
>>   disjoint set.  We need to add some text to say not to do that.
>
>
>
> So I understand you try to assure that there always a overlapping prefix among CompleteRAs even under prefix change. Right?  


Yes.

> I admit that I don't look over Landmark/CompleteRA 01-draft but the above seems a little different from what I remember. I think it would
> help to write those down lest there should be unnecessary confusion. 


OK.

Brett. 

Syam Madanapalli

Hi Brett,

[cut]


>>> >
>>> >
>>> > What if you get answer 'NO' first?
>>> > Will you check with the prefixes received in the RA?
>>> > This looks better compared just depending on the
>>> > Landmark answer. Otherwise host makes wrong decision.
>>> >
>>> > [cut]
>
>> 
>> This question is one of the open issues (9).  My personal opinion is
>> that yes, the host should check the prefixes and if it sees overlap with
>> the prefixes it has already seen on the link, should decide that link
>> change has not taken place.


I think it is definitely a good idea to check the prefixes in the RA
in case of NO answer.

-Syam



>> 
>> Brett.

Tero Kauppinen

I'm starting to get so confused in the middle of this LinkID v.s.
Landmark Prefix discussion that I'm afraid that I'm loosing my grasp
even with the basics.

I started wondering what will actually happen in the following scenario:


Let there be two routers, 'A' and 'B' and some access points. 'A'
advertises prefixes 1 and 2 whereas 'B' advertises prefix 3. After
connecting to an AP host, 'N', sends an RS and gets an RA (from 'A'),
and finally configures an address (basing on prefix 2). In the case of
LinkID 'N' gets the current link-id prefix from the RA, and in the case
of Landmark Prefix 'N' chooses a landmark prefix. Let's assume that
prefix 1 is both the smallest prefix and the prefix 'N' chooses to be
the landmark prefix. 

If we then say that 'A' stops advertising prefix 2 and zero-lifetime
messages disappear, what will be the outcome? I mean, 'N' could attach
to another AP, send an RA and learn that it's still in the same network.
However, even though 'N' still in the same network, the address 'N' is
using (prefix 2 based) is not valid anymore.

As I said, I'm so confused that I can't even be sure if this has already
been discussed on the list.

--
Tero 

Subba Reddy

Hi Tero,



>>
>
>>> > Assume a link with two routers R1 and R2 and a host H.
>>> > R1 advertises Prefix1 and R2 Prefix2.
>>> >
>>> > R2 stops advertising Prefix2 and starts advertising Prefix3.
>>> > R2 announces the prefix change by sending an RA but
>>> > both R1 and H don't receive it.
>>> >
>>> > Then H happens to change its AP in the same link
>>> > and send an RS with landmark Prefix2. It also happens that
>>> > R2 replies first and sends an RA with NO and Prefix3.
>>> > H falsely assumes a link change.
>
>>
>> But isn't it actually so that in this case the host shouldn't use an
>> address based on Prefix2 and thus reconfiguration is required (i.e. link
>> change from host H point of view)? After all, Prefix2 is not anymore
>> valid.


I think, host can not assume link change, if one of the prefixes is invalid.
In the case of link change, host deletes all its addresses, prefix table and
NC entries,
which is not the exact case if prefix changes.

In the above example, entries with Prefix1 are still valid.

Thanks & Regards,
Subba Reddy



>>
>> Tero
>>
>>
>>

Tero Kauppinen

Hello Subba,


>>>> > > Assume a link with two routers R1 and R2 and a host H.
>>>> > > R1 advertises Prefix1 and R2 Prefix2.
>>>> > >
>>>> > > R2 stops advertising Prefix2 and starts advertising Prefix3.
>>>> > > R2 announces the prefix change by sending an RA but
>>>> > > both R1 and H don't receive it.
>>>> > >
>>>> > > Then H happens to change its AP in the same link
>>>> > > and send an RS with landmark Prefix2. It also happens that
>>>> > > R2 replies first and sends an RA with NO and Prefix3.
>>>> > > H falsely assumes a link change.
>>
>>> >
>>> > But isn't it actually so that in this case the host shouldn't use an
>>> > address based on Prefix2 and thus reconfiguration is required (i.e.

link

>>> > change from host H point of view)? After all, Prefix2 is not anymore
>>> > valid.
>
>> 
>> I think, host can not assume link change, if one of the prefixes is
>> invalid.
>> In the case of link change, host deletes all its addresses, prefix

table

>> and
>> NC entries,
>> which is not the exact case if prefix changes.
>> 
>> In the above example, entries with Prefix1 are still valid.


True. Still, as in the mail I sent earlier, I started wondering how the
node knows to "switch" to use an address based on Prefix1?

/Tero

Syam Madanapalli

Hi Tero,


>> I'm starting to get so confused in the middle of this LinkID v.s.
>> Landmark Prefix discussion that I'm afraid that I'm loosing my grasp
>> even with the basics.
>> 
>> I started wondering what will actually happen in the following scenario:
>> 
>> 
>> Let there be two routers, 'A' and 'B' and some access points. 'A'
>> advertises prefixes 1 and 2 whereas 'B' advertises prefix 3. After
>> connecting to an AP host, 'N', sends an RS and gets an RA (from 'A'),
>> and finally configures an address (basing on prefix 2). In the case of
>> LinkID 'N' gets the current link-id prefix from the RA, and in the case
>> of Landmark Prefix 'N' chooses a landmark prefix. Let's assume that
>> prefix 1 is both the smallest prefix and the prefix 'N' chooses to be
>> the landmark prefix.
>> 
>> If we then say that 'A' stops advertising prefix 2 and zero-lifetime
>> messages disappear, what will be the outcome? I mean, 'N' could attach
>> to another AP, send an RA and learn that it's still in the same network.


Either Landmark or Linkid approaches detect that there is no link
change. I think, as far DNA is concerned the job is done. 


>> However, even though 'N' still in the same network, the address 'N' is
>> using (prefix 2 based) is not valid anymore.


This is the host problem and is same problem if the router suddenly
stops advertising prefix 2. I looked into 2462bis and found the following 
text: 

5.5.3  Router Advertisement Processing

---

d) If the prefix advertised is not equal to the prefix of an address
      configured by stateless autoconfiguration already in the list of
      addresses associated with the interface (where "equal" means the
      two prefix lengths are the same and the first prefix-length bits
      of the prefixes are identical), and the Valid Lifetime is not 0,
      form an address (and add it to the list) by combining the
      advertised prefix with the link's interface identifier

If the node did not configure the address based on prefix 1 then
it should either wait till the prefix 2 life time expiry or if the router 
does not support forwarding for the prefix 2, an intelligent host can
configure new address using prefix 1 based on packet loss. I am
not sure about choosing new address based on packet loss.



>> 
>> As I said, I'm so confused that I can't even be sure if this has already
>> been discussed on the list.
>> 
>> --
>> Tero

Subba Reddy

Hi Tero,

<cut>

>>>> > > But isn't it actually so that in this case the host shouldn't use an
>>>> > > address based on Prefix2 and thus reconfiguration is required (i.e.
>
>> link
>
>>>> > > change from host H point of view)? After all, Prefix2 is not anymore
>>>> > > valid.
>>
>>> > 
>>> > I think, host can not assume link change, if one of the prefixes is
>>> > invalid.
>>> > In the case of link change, host deletes all its addresses, prefix
>
>> table
>
>>> > and
>>> > NC entries,
>>> > which is not the exact case if prefix changes.
>>> > 
>>> > In the above example, entries with Prefix1 are still valid.
>
>> 
>> True. Still, as in the mail I sent earlier, I started wondering how the
>> node knows to "switch" to use an address based on Prefix1?


I think, after some time, H may get RA with Prefix2 lifetimes
set to 0 from R2. 


>> 
>> /Tero

Tero Kauppinen

>This is the host problem and is same problem if the router suddenly
>> stops advertising prefix 2. I looked into 2462bis and found the

following

>> text:
>> 
>> 5.5.3  Router Advertisement Processing
>> 
>> ---
>> 
>> d) If the prefix advertised is not equal to the prefix of an address
>>       configured by stateless autoconfiguration already in the list of
>>       addresses associated with the interface (where "equal" means the
>>       two prefix lengths are the same and the first prefix-length bits
>>       of the prefixes are identical), and the Valid Lifetime is not 0,
>>       form an address (and add it to the list) by combining the
>>       advertised prefix with the link's interface identifier
>> 
>> If the node did not configure the address based on prefix 1 then
>> it should either wait till the prefix 2 life time expiry or if the

router

>> does not support forwarding for the prefix 2, an intelligent host can
>> configure new address using prefix 1 based on packet loss. I am
>> not sure about choosing new address based on packet loss.


True. In the middle of this confusion I didn't think that the node could
indeed configure itself multiple addresses. It's then up to the source
address selection logic to decide which one to use.
 
Thanks,
Tero

Erik Nordmark

JinHyeock Choi wrote:

> I use flapping in more general case as below.
> When the set of prefixes on a link changes, there is the possibility of temporary lack of synchronization, i.e. the nodes on the link (such as routers and hosts) may have different set of prefixes (on the link) for the time being. 
> For example, if the prefix set is {P1, P2} and P3 is added, one would
> ideally have all the nodes on the link have the prefix set {P1, P2, P3} instantly. But due to packet loss, it is possible that one router has the
> prefix set {P1, P2} and the other router has {P1, P2, P3} for some time.


It isn't only packet loss that is the problem; in a distributed system the notion of "at the same time" isn't a useful concept. We've talked about this in the DT and I referred to the Lamport paper which I think is titled "time, clocks, and the ordering of events in a distributed system".

So we shouldn't require that DNA solve a known unsolvable problem :-)

Hence I postulated "flapping" as being the more specific case when a single host, instead of seeing a "clean" switch from one prefix set to another, sees the set of prefixes flap back and forth before settling down on the new set. Such flapping is unavoidable for the cases we are interested in (an unknown and changeable set of routers on the link, and a changeable set of prefixes being advertised.)

I think it is important that the DNA solution cope gracefully with such flapping.

> If hosts check for link change with prefix information, such a lack of (temporary) synchronization may cause a false link identity detection. 


From my understanding of CPL, completeRA, landmark, and linkID, none of them have this problem. So which solutions do you refer to with your "may"?


> ok. Allow me to clarify this
>
> In Landmark/ CompleteRA, when a host receives a solicited RA, the host check for link change with both 1) Landmark option with YES/NO bit and
> 2) prefixes in the RA.
> If the (solicited) RA carries 1) NO answer and 2) a known prefix, the host would not assume a link change. (So in effect, "known prefix" would overrule "NO".)
>
> Is this right? 


I think that makes sense.

> Routers don't pay attention what other routers advertise as a linkid. They generate the complete prefix set and pick the linkid prefix for themselves. You recommended this approach. 


Blush :-)

   Erik

Erik Nordmark

JinHyeock Choi wrote:

> ok. I admit this is a crude one but all I can think of right now.  (Because it's not clear to me how a host base its decision on CompleteRA, I switch to landmark one.)
> Assume a link with two routers R1 and R2 and a host H. R1 advertises Prefix1 and R2 Prefix2.
> R2 stops advertising Prefix2 and starts advertising Prefix3. R2 announces the prefix change by sending an RA but
> both R1 and H don't receive it.
> Then H happens to change its AP in the same link and send an RS with landmark Prefix2. It also happens that R2 replies first and sends an RA with NO and Prefix3. H falsely assumes a link change. 


I assumed that you'd found a case when a host would fail to detect a link change when there was one (which is the case we must avoid); I'm not too worried about there being some corner cases when the host interprets a change in the prefix set as a link change when in fact the host has stayed on the same link. (This would just result in some additional, e.g., MIPv6 signaling. And as Tero pointed out, this more rapid way to react to the prefix being removed might be viewed as a feature.)


> The above is not clear to me yet. Allow me a question to help my understanding. 
> Assume a host moves to a different link but fails to receive a Link Up event Notification. Then the host will not assume a link change even if it receives a different unsolicted CompleteRA? 


Let me explain my reasoning.

When we worked on CPL we concluded that if the implementation can't reliably deliver a 'link up' event notification from the link layer to the DNA module, then there are cases when the host would end up treating the prefixes from two links as being from one link.
Thus for CPL to work reliably, the 'link up' indication in the implementation must be present.

Given that we have this, then we have the choice to assume this notification even for the DNA solution, as a way to optimize things. Alternatively, we can try to make the DNA solution be more robust again a missing 'link up' notification.
I haven't thought through all the details, but the fact that landmark falls back on prefix comparisons, and linkID handles routers that temporarily disagree on the linkID, might imply that these schemes could be confused when the link up is missing. If that's the case we can't make the solution robust against a missing link up.

   Erik

Erik Nordmark

Tero Kauppinen (JO/LMF) wrote:

> Let there be two routers, 'A' and 'B' and some access points. 'A'
> advertises prefixes 1 and 2 whereas 'B' advertises prefix 3. After
> connecting to an AP host, 'N', sends an RS and gets an RA (from 'A'),
> and finally configures an address (basing on prefix 2). In the case of
> LinkID 'N' gets the current link-id prefix from the RA, and in the case
> of Landmark Prefix 'N' chooses a landmark prefix. Let's assume that
> prefix 1 is both the smallest prefix and the prefix 'N' chooses to be
> the landmark prefix.
> If we then say that 'A' stops advertising prefix 2 and zero-lifetime
> messages disappear, what will be the outcome? I mean, 'N' could attach
> to another AP, send an RA and learn that it's still in the same network.
> However, even though 'N' still in the same network, the address 'N' is
> using (prefix 2 based) is not valid anymore.
>
> As I said, I'm so confused that I can't even be sure if this has already
> been discussed on the list.


My tongue in cheek answer is that this is a feature of RFC 2461 :-)
Even if there was no DNA, or there was DNA and the host didn't move to a different AP, the host would continue to use prefix2 until it expired.
This could be viewed as a feature in RFC 2461 in that even if a router fails and stops advertising a prefix for some time, it will not upset the configuration of the hosts unnecessarily. So when the administrator wants to remove a prefix, she has to explicitly configure the routers to drop the lifetime to zero (either abruptly or gradually).

The narrow path I've tried to follow is to realize the above issue, but yet make sure that DNA doesn't get any more confused by this then a host would get that doesn't move. For instance, by looking at how a non-moving host would behave when it attaches to the network.

But I might be making the wrong call here, and that in the light of intermittently connected hosts and lossy (radio) links, we should make the reverification of being connected to the same "place" a lot less forgiving.

   Erik

James Kempf

ok. I admit this is a crude one but all I can think of right now.
(Because it's not clear to me how a host base its decision
on CompleteRA, I switch to landmark one.)

Assume a link with two routers R1 and R2 and a host H.
R1 advertises Prefix1 and R2 Prefix2.

R2 stops advertising Prefix2 and starts advertising Prefix3.
R2 announces the prefix change by sending an RA but
both R1 and H don't receive it.

Then H happens to change its AP in the same link
and send an RS with landmark Prefix2. It also happens that
R2 replies first and sends an RA with NO and Prefix3.
H falsely assumes a link change.

jak>> So what is the realistic probability of this actually happening? One
could use this same kind of search for corner cases to shoot down oDAD, yet
it is on the verge of becoming a PS RFC and we are planning on using it for
DNA.

            jak

JinHyeock Choi

Dear Erik


>>> > I use flapping in more general case as below.
>>> >
>>> > When the set of prefixes on a link changes,
>>> > there is the possibility of temporary lack of synchronization, i.e.
>>> > the nodes on the link (such as routers and hosts)
>>> > may have different set of prefixes (on the link) for the time being.
>>> >
>>> > For example, if the prefix set is {P1, P2} and P3 is added, one would
>>> > ideally have all the nodes on the link have the prefix set {P1, P2, P3}
>>> > instantly. But due to packet loss, it is possible that one router has the
>>> > prefix set {P1, P2} and the other router has {P1, P2, P3} for some time.
>
>> 
>> It isn't only packet loss that is the problem; in a distributed system
>> the notion of "at the same time" isn't a useful concept. We've talked
>> about this in the DT and I referred to the Lamport paper which I think
>> is titled "time, clocks, and the ordering of events in a distributed
>> system".
>> 
>> So we shouldn't require that DNA solve a known unsolvable problem  :-) 


ok. I don't think we can remove such a temporary "Lack of Synchronization" 
entirely. RA travels with the speed of light, so to deliver RA to all
the routers
"at the same time", we may need to study "Theory of Relativity".  :-) 

>> Hence I postulated "flapping" as being the more specific case when a
>> single host, instead of seeing a "clean" switch from one prefix set to
>> another, sees the set of prefixes flap back and forth before settling
>> down on the new set. 


ok. From now on, I will use the term "flapping" only in the sense you 
describes. 

For the more general case I presented, I will use the term 'LOS (Lack 
of Synchronization). Is it ok? 

(The term "link" gave me enough trouble already. I don't want another 
Jason problem arising from ambiguous terms.)  


>> Such flapping is unavoidable for the cases we are
>> interested in (an unknown and changeable set of routers on the link, and
>> a changeable set of prefixes being advertised.)
>> 
>> I think it is important that the DNA solution cope gracefully with such
>> flapping.


ok. I think it's also important that DNA solution cope gracefully with 
more general case of  temporary LOS (Lack of Synchronization). If 
DNA solution can deal with LOS, I think it can deal with flapping 
automatically. 


>>> > If hosts check for link change with prefix information, such a lack of
>>> > (temporary) synchronization may cause a false link identity detection.
>
>> 
>>  From my understanding of CPL, completeRA, landmark, and linkID, none of
>> them have this problem. So which solutions do you refer to with your "may"?


I guess I presented one problem with Landmark in the other mail.  :-)  


>>> > ok. Allow me to clarify this
>>> >
>>> > In Landmark/ CompleteRA,
>>> > when a host receives a solicited RA,
>>> > the host check for link change with both
>>> > 1) Landmark option with YES/NO bit and
>>> > 2) prefixes in the RA.
>>> >
>>> > If the (solicited) RA carries 1) NO answer and 2) a known prefix,
>>> > the host would not assume a link change.
>>> > (So in effect, "known prefix" would overrule "NO".)
>>> >
>>> > Is this right?
>
>> 
>> I think that makes sense.


ok. I think the above is a non-trivial change for Link Identification 
criteria, so needs to be reflected in the Landmark/ CompleteRA draft. 
 
Best Regards

JinHyeock

Greg Daley

Hi Erik, 

----- Original Message -----
From: Erik Nordmark <erik.nordmark@sun.com>
Date: Monday, July 25, 2005 10:24 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
Landmark Prefix

>> Greg Daley wrote:
>> 
>
>>> > In CPL which is host (only) based, the timers are on the host, 
>
>> and 
>
>>> > protect
>>> > the host from long term damage, by removing unupdated 
>
>> information 
>
>>> > at the host.
>>> > 
>>> > Even with the most broken readvartisement scheme for stale 
>
>> information,> the damage could only occur for a maximum:
>
>>> > (Router out-of-date timer + Host out-of-date timer)
>
>> 
>> Are you talking about RFC 2461, or are you talking about a 
>> proposal for 
>> how CPL could work?


Sorry I think I changed topics in mid e-mail, and referred
to CPL as an example of particular behaviour, before
going back to my main topic.

The inequality refers to modified advertisement schemes
(those which readvertise learnt information), rather than
CPL.

Greg

JinHyeock Choi

Erik


>>> > The above is not clear to me yet. Allow me a question to help 
>>> > my understanding.  
>>> > 
>>> > Assume a host moves to a different link but fails to receive a 
>>> > Link Up event Notification. Then the host will not assume a link 
>>> > change even if it receives a different unsolicted CompleteRA? 
>
>> 
>> Let me explain my reasoning.
>> 
>> When we worked on CPL we concluded that if the implementation can't 
>> reliably deliver a 'link up' event notification from the link layer to 
>> the DNA module, then there are cases when the host would end up treating 
>> the prefixes from two links as being from one link.
>> Thus for CPL to work reliably, the 'link up' indication in the 
>> implementation must be present.
>> 
>> Given that we have this, then we have the choice to assume this 
>> notification even for the DNA solution, as a way to optimize things. 
>> Alternatively, we can try to make the DNA solution be more robust again 
>> a missing 'link up' notification.


I took the latter approach. (that may be the road less traveled. :-))  
Allow me to explain my reasoning too. 

In the previous CPL draft, we wrote that 

   Thus we think the prefix-based approach has a stronger assumption
   here than the Link Identifier-based approach, because the latter can
   operate reliably without any link-layer event notifications [14].

though the current version omits this.

So I tried to build 'linkid prefix' scheme as independent of Link UP
event notification as possible. I avoided to rely on Link UP. 
 
For example, with Link UP notification, Linkid scheme may work 
to detect link change from non-supporting link to supporting one 
as below. 

Assume a host is at a non-supporting link. Then it doesn't have 
a linkid prefix. When it moves to a supporting link, it will see a 
new linkid. 

The host may assume a link change upon receiving this new linkid.
But the current draft mandates that the host doesn't make any 
decision becuase there is the other possibility that the host is at 
the same link but a router on the link becomes a DNA router and
starts advertising the linkid. 

I contemplated the idea to distinguish the above two cases with 
Link UP indication but gave it up because I thought the simplicity
and less assumption is better. 


>> I haven't thought through all the details, but the fact that landmark 
>> falls back on prefix comparisons, and linkID handles routers that 
>> temporarily disagree on the linkID, might imply that these schemes could 
>> be confused when the link up is missing. If that's the case we can't 
>> make the solution robust against a missing link up.

 
We intended Linkid scheme not to depend on Link UP and the 
scheme is supposed to work rubustly even without any Link UP 
notificaiton. We can't deny the possibility of confusion (even Titanic
sank in its maiden voyage :-)) but can't find the example yet. 

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

Greg Daley

Hi JinHyeock, 

Please don't be shocked, I may agree with
you in this e-mail.

----- Original Message -----
[cut]

>>> > I haven't thought through all the details, but the fact that 
>
>> landmark 
>
>>> > falls back on prefix comparisons, and linkID handles routers 
>
>> that 
>
>>> > temporarily disagree on the linkID, might imply that these 
>
>> schemes could 
>
>>> > be confused when the link up is missing. If that's the case we 
>
>> can't 
>
>>> > make the solution robust against a missing link up.
>
>> 
>> We intended Linkid scheme not to depend on Link UP and the 
>> scheme is supposed to work rubustly even without any Link UP 
>> notificaiton.


I'd prefer something which could work even if the host's
driver wasn't able to provide Link Up indications.

While my host implementation basically assumes them, 
not all drivers and operating systems do (or even will)
support them.

In some media (for example, CDMA-like media) it may be
difficult to distinguish when one base station is "UP"
or not, since multiple base-stations are visible.

So understanding if the schemes would work without
indications is useful, if this is a goal.


>> We can't deny the possibility of confusion (even Titanic
>> sank in its maiden voyage :-)) but can't find the example yet. 


I've got a case where all 3 (CompleteRA, Landmark, LinkID)
schemes fail, and I've written it out 3 times, with just
the names of the schemes changed (It is a corner case though).

At the moment I'm not able to connect my own computer to 
my visited network, but will post it for everyone, when able.
It's not meant to prove any scheme is better than another,
just that all the schemes are fallible.

Some of the simple safety measures proposed would recover
any of the solutions (Aim #2 from the other thread), and some
would limit the possibility of it occurring (Recommendations
for flash renumbering).

These may be sufficient, with or without advertisement of 
the old LinkID.

Greg

JinHyeock Choi

Dear Greg


>> Please don't be shocked, I may agree with
>> you in this e-mail.


What a nice shock! I hope to have such a surprise many many 
more times that it won't be a surprise any longer.  :-) 

>>> > We intended Linkid scheme not to depend on Link UP and the
>>> > scheme is supposed to work rubustly even without any Link UP
>>> > notificaiton.
>
>> 
>> I'd prefer something which could work even if the host's
>> driver wasn't able to provide Link Up indications.
>> 
>> While my host implementation basically assumes them,
>> not all drivers and operating systems do (or even will)
>> support them.
>> 
>> In some media (for example, CDMA-like media) it may be
>> difficult to distinguish when one base station is "UP"
>> or not, since multiple base-stations are visible.
>> 
>> So understanding if the schemes would work without
>> indications is useful, if this is a goal.


ok. 


>>> > We can't deny the possibility of confusion (even Titanic
>>> > sank in its maiden voyage :-)) but can't find the example yet.
>
>> 
>> I've got a case where all 3 (CompleteRA, Landmark, LinkID)
>> schemes fail, and I've written it out 3 times, with just
>> the names of the schemes changed (It is a corner case though).
>>
>> At the moment I'm not able to connect my own computer to
>> my visited network, but will post it for everyone, when able.


ok. We'd like to see the case. It may show us the way for 
improvement. 

Thanks for your kind consideration. 

Best Regards

JinHyeock

Greg Daley

Hi JinHyeock, 

----- Original Message -----
[cut]

>> 
>
>>>> > > We can't deny the possibility of confusion (even Titanic
>>>> > > sank in its maiden voyage :-)) but can't find the example yet.
>>
>>> > 
>>> > I've got a case where all 3 (CompleteRA, Landmark, LinkID)
>>> > schemes fail, and I've written it out 3 times, with just
>>> > the names of the schemes changed (It is a corner case though).
>>> >
>>> > At the moment I'm not able to connect my own computer to
>>> > my visited network, but will post it for everyone, when able.
>
>> 
>> ok. We'd like to see the case. It may show us the way for 
>> improvement. 


Here's the case, written out three times (once for each scheme).
There may yet be mistakes, but I think it's a valid case.

I think that this is incorrect change detection for all cases,
although there are assumptions about the ordering of packet arrivals.


Link Identifiers
---------------------

A Host H, exists and moves around the Internet.

On an link unvisited by the host, Link L, a prefix, P is
retracted by one of the routers Router1. Subsequent to this,
the actual lowest prefix on the link is Prefix Q.


Another router, Router2 fails to see the prefix retraction.
(Perhaps RAs are lost, or Router1 didn't comply with 
section 6.2.6 of RFC2461).

The prefix is then reassigned within its previous 
lifetime to another link, link M, whose lowest prefix
was prefix T.  Link M, has also not been visited by
host H.

Link Identifiers are in use on both Link L and
Link M.  On Link M, all routers advertise Prefix P
as current LinkID and Prefix T as OldLinkID.

On Link L, Router2 advertises prefix P as Current LinkID.

If the host H arrives on Link L, it may receive 
Prefix P as LinkID even though it is no longer present
on-link.  The host would configure Prefix Q (or a higher prefix)
which is advertised in a PIO.

If the LinkID is not contradicted, for example if there are
no other advertising routers left on the link, when the host
moves to Link M, it will also receive an RA with prefix P as
the Current LinkID.  The Old LinkID will be ignored (it hasn't
been seen before).


In this case, no change will be detected upon arrival to 
link M, and the previous prefix will remain configured.



Complete RA
-----------

A Host H,  exists and moves around the Internet.


On an link unvisited by the host, Link L, a prefix, P is
retracted by one of the routers Router1. Subsequent to this,
the actual lowest prefix on the link is Prefix Q.


Another router, Router2 fails to see the prefix retraction.
(Perhaps RAs are lost, or Router1 didn't comply with 
section 6.2.6 of RFC2461).

The prefix is then reassigned within its previous 
lifetime to another link, link M, whose lowest prefix
was prefix T.  Link M, has also not been visited by
host H.

CompleteRA is in use on both Link L and
Link M.  On Link M, all routers advertise Prefix P
and Prefix T (and any higher prefixes).

On Link L, Router2 advertises prefix P as well as prefix
R.


If the host H arrives on Link L, it will receive the 
prefix set {P, Q, ...}, even though P is no longer on the link.
The host would configure Prefix Q (or a higher prefix)
which is advertised in a PIO.

If the CompleteRA is not contradicted by another well configured
router, for example if there are no other advertising routers
left on the link, when the host moves to Link M, it will also
receive an RA with prefix P.

If the RA received only advertises P and is not a CompleteRA
it is impossible to tell if the link has changed (The prefixes
from the received RA and previous prefix set overlap).

If the received RA is a CompleteRA, the host will receive
a prefix set {P, T, ...} which overlaps but does not match
the old prefix list {P, Q, ...}.   Since the prefix lists 
overlap, it may be possible that these are the same link
(according to CPL, for instance).

In either of these cases, no change will be detected upon arrival
to link M, and the previous prefix will remain configured.


It is possible to define that received CompleteRAs override
previous Link Identification, as they represent a complete
view of the information of a link (This is not done by default
in the current draft).  In that case, a received CompleteRA
may then invalidate address prefixes - doesn't work with the
reassigned prefix though (which will remain configured if moves back).




Prefix Landmarks
----------------


A Host H, exists and moves around the Internet.

On an link unvisited by the host, Link L, a prefix, P is
retracted by one of the routers Router1. Subsequent to this,
the actual lowest prefix on the link is Prefix Q.


Another router, Router2 fails to see the prefix retraction.
(Perhaps RAs are lost, or Router1 didn't comply with 
section 6.2.6 of RFC2461).

The prefix is then reassigned within its previous 
lifetime to another link, link M, whose lowest prefix
was prefix T.  Link M, has also not been visited by
host H.

Prefix Landmarking is in use on both Link L and
Link M.  On Link M, routers advertise either P or T 
but are aware of both prefixes' presence.


On Link L, Router2 advertises prefix Q, but also
believes prefix P is on-link.

The host H arrives on Link L, and learns that link's 
prefixes  (for example, configuring an address from Q).
The host then moves to Link M and solicits
the routers and asks if one of the previous link's
prefixes is available here.

If it asks about P - 'Is P on this Link?', then 
the routers will answer (correctly) 'Yes'.
In this case, no change will be detected upon arrival to 
link M, and the previous prefix will remain configured.

If the host asks 'Is Q on this Link?', then it would
receive a 'No' answer, and would detect change.



Alternatively, if the host instead visited Link M and then
Link L, the host would similarly have had problems if 
it asked (on Link L) 

'Is P on this link?" but not if it asked 'Is T on this link?'
Querying the moved prefix will be unsuccessful, even though 
on link M, the prefix is advertised natively in PIOs.

----

I'm not sure what it means we should be doing, but more
knowledge has been emerging about the issue, and we may
be able to move closer to agreement soon (Lets hope).

Greg

Brett Pentland

> Prefix Landmarks
> ----------------
>
>
> A Host H, exists and moves around the Internet.
>
> On an link unvisited by the host, Link L, a prefix, P is
> retracted by one of the routers Router1. Subsequent to this,
> the actual lowest prefix on the link is Prefix Q.
>
>
> Another router, Router2 fails to see the prefix retraction.
> (Perhaps RAs are lost, or Router1 didn't comply with section 6.2.6 of RFC2461).
>
> The prefix is then reassigned within its previous lifetime to another link, link M, whose lowest prefix
> was prefix T.  Link M, has also not been visited by
> host H.
>
> Prefix Landmarking is in use on both Link L and
> Link M.  On Link M, routers advertise either P or T but are aware of both prefixes' presence.
>
>
> On Link L, Router2 advertises prefix Q, but also
> believes prefix P is on-link.
>
> The host H arrives on Link L, and learns that link's prefixes  (for example, configuring an address from Q).
> The host then moves to Link M and solicits
> the routers and asks if one of the previous link's
> prefixes is available here.
>
> If it asks about P - 'Is P on this Link?', then the routers will answer (correctly) 'Yes'.
> In this case, no change will be detected upon arrival to link M, and the previous prefix will remain configured.
>
> If the host asks 'Is Q on this Link?', then it would
> receive a 'No' answer, and would detect change.


This case couldn't actually happen, because the draft requires
that the landmark be a prefix that the host has an address
configured with.  It couldn't get this from link L.

This is only a minor point though, because the following case
could occur because the host might configure an address with
prefix P when it visited link M and then router 2 would answer
yes if it asked about prefix P when it moved to link L.

Brett.

>
> Alternatively, if the host instead visited Link M and then
> Link L, the host would similarly have had problems if it asked (on Link L)
> 'Is P on this link?" but not if it asked 'Is T on this link?'
> Querying the moved prefix will be unsuccessful, even though on link M, the prefix is advertised natively in PIOs. 

Subba Reddy

Hi Greg,

<cut>

>> Link Identifiers
>> ---------------------
>>
>> A Host H, exists and moves around the Internet.
>>
>> On an link unvisited by the host, Link L, a prefix, P is
>> retracted by one of the routers Router1. Subsequent to this,
>> the actual lowest prefix on the link is Prefix Q.
>>
>>
>> Another router, Router2 fails to see the prefix retraction.
>> (Perhaps RAs are lost, or Router1 didn't comply with
>> section 6.2.6 of RFC2461).
>>
>> The prefix is then reassigned within its previous
>> lifetime to another link, link M, whose lowest prefix
>> was prefix T.  Link M, has also not been visited by
>> host H.
>>
>> Link Identifiers are in use on both Link L and
>> Link M.  On Link M, all routers advertise Prefix P
>> as current LinkID and Prefix T as OldLinkID.
>>
>> On Link L, Router2 advertises prefix P as Current LinkID.
>>
>> If the host H arrives on Link L, it may receive
>> Prefix P as LinkID even though it is no longer present
>> on-link.  The host would configure Prefix Q (or a higher prefix)
>> which is advertised in a PIO.
>>
>> If the LinkID is not contradicted, for example if there are
>> no other advertising routers left on the link, when the host
>> moves to Link M, it will also receive an RA with prefix P as
>> the Current LinkID.  The Old LinkID will be ignored (it hasn't
>> been seen before).
>>
>>
>> In this case, no change will be detected upon arrival to
>> link M, and the previous prefix will remain configured.
>>


I am just giving one example, where H may not take wrong decision.

If the H stays for atleast 3 hours (worst case) in the Link L, H will
delete that linkid from list and will not make wrong decision when
it is moved to Link M.

In detail,
Let us say life time of P is 10 hrs when the P is removed from L and
assigned to M.
Sice Router2 don't know the removal of P, it will be advertising P as
linkid.
After 1.5hrs, Router2 will stop advertising as linkid (since the prefix is
not updated
by any router, in this case Router1). Let us say H has received the last RA
from Router2
with P as linkid (exactly after 1.5hrs after P is removed). After 1.5 hrs
from this point of
time H also will remove P from linkid list, since it is not updated in the
last 1.5hrs.
So after 3 hrs, P will be removed from linkid list of H.

Thanks & Regards,
Subba Reddy

Greg Daley

Hi Subba, 

----- Original Message -----
[cut]

>>> >
>>> > In this case, no change will be detected upon arrival to
>>> > link M, and the previous prefix will remain configured.
>>> >
>
>> 
>> I am just giving one example, where H may not take wrong decision.

[cut]

I understand that LinkID is quite robust against change.

The point I originally was making was that while it is robust,
All of the schemes are flawed to some extent.

Some of the strategies described in LinkID (timers, etc)
are applicable to all schemes, and would probably be adopted
in any of the schemes now.

So the question is: Is the problem big enough that the 
advantage of advertising oldLinkID, gains significantly
over the other schemes (when timeouts and prefix retraction
advertisement are recommended)? 

Are the other schemes good enough?

I don't expect there are clear answers which everyone agrees
with, but it may be possible to discuss things until
we agree about the comparison.

Greg 

Tero Kauppinen

Hi Brett,

I'm having this endless LinkID v.s. Landmark battle in my head while trying to grasp what has been said and written. 

Anyway, I started think the following naïve example:

 R1 : advertising P1               R2 : adverstining P2
      thus {adv:P1, learned:P2}         thus {adv:P2, learned: P1}

 node H: knows P1, P2 and has chosen P1 as the landmark prefix

Let's assume that R1 stops advertising P1 and starts advertising a new prefix P3. The host doesn't receive RAs and is unaware of the change. The node moves to another AP and gets a "no" answer. The landmark approach indicates wrongly a link change, but CPL will show that there is actually no link change. If I have been able to follow the discussion, it has been said that the CPL decision should overwrite Landmark's decision in this case. 

I agree but I guess a lot of fuzz is because this is not clearly stated in the draft -- should it or is it still an open issue? This would practically mean that every time a "no" answer is received, the current list of all known prefixes on the link is checked in order to confirm that the RA doesn't contain a prefix which is already known to be on the link.

...or am I just once again completely lost?  :) 

Might also be that we should write down something about the case when a node changes the landmark prefix. If the node received a zero-lifetime advertisement for the current landmark prefix, it should pick another prefix. On the other hand, "5.2.3. The prefix MUST have a non-zero valid lifetime" is a way to say it.

--
Tero 


>> -----Original Message-----
>> From: owner-dna@ecselists.eng.monash.edu.au [mailto:owner-
>> dna@ecselists.eng.monash.edu.au] On Behalf Of Greg Daley
>> Sent: 28. heinäkuuta 2005 9:18
>> To: Subba Reddy
>> Cc: JinHyeock Choi; Erik Nordmark; Syam Madanapalli; Brett Pentland;
>> greg.daley@eng.monash.edu.au; James Kempf; Dna
>> Subject: Re: [DNA] Re: LinkID v.s. Landmark Prefix
>> 
>> Hi Subba,
>> 
>> ----- Original Message -----
>> [cut]
>
>>>> > >
>>>> > > In this case, no change will be detected upon arrival to
>>>> > > link M, and the previous prefix will remain configured.
>>>> > >
>>
>>> >
>>> > I am just giving one example, where H may not take wrong decision.
>
>> [cut]
>> 
>> I understand that LinkID is quite robust against change.
>> 
>> The point I originally was making was that while it is robust,
>> All of the schemes are flawed to some extent.
>> 
>> Some of the strategies described in LinkID (timers, etc)
>> are applicable to all schemes, and would probably be adopted
>> in any of the schemes now.
>> 
>> So the question is: Is the problem big enough that the
>> advantage of advertising oldLinkID, gains significantly
>> over the other schemes (when timeouts and prefix retraction
>> advertisement are recommended)?
>> 
>> Are the other schemes good enough?
>> 
>> I don't expect there are clear answers which everyone agrees
>> with, but it may be possible to discuss things until
>> we agree about the comparison.
>> 
>> Greg

Erik Normark

JinHyeock Choi wrote:

> ok. From now on, I will use the term "flapping" only in the sense you describes.
> For the more general case I presented, I will use the term 'LOS (Lack of Synchronization). Is it ok? 


ok, but see below.
Also, I don't think "out of synch" can be determined in a distributed system, since there is always a non-zero delay. Hence if R1 sends a RA and R2 and R3 receives it, an observer can't tell which or R2 and R3 updated the prefix list first (or whether they did it at exactly the same time).

> (The term "link" gave me enough trouble already. I don't want another Jason problem arising from ambiguous terms.) 
>
>> Such flapping is unavoidable for the cases we are
>> interested in (an unknown and changeable set of routers on the link, and
>> a changeable set of prefixes being advertised.)
>>
>> I think it is important that the DNA solution cope gracefully with such
>> flapping.
>
>
>
> ok. I think it's also important that DNA solution cope gracefully with more general case of  temporary LOS (Lack of Synchronization). If DNA solution can deal with LOS, I think it can deal with flapping automatically. 


I don't see using the LOS term as helpful here.
LOS captures the case when router1's list of prefixes is out of date with router2's two list of prefixes, even if only for a nanosecond.

What matters is the sequence of events that are observable.


>>> If the (solicited) RA carries 1) NO answer and 2) a known prefix,
>>> the host would not assume a link change.
>>> (So in effect, "known prefix" would overrule "NO".)
>>>
>>> Is this right?
>>
>>
>> I think that makes sense.
>
>
>
> ok. I think the above is a non-trivial change for Link Identification criteria, so needs to be reflected in the Landmark/ CompleteRA draft. 


Agreed.

   Erik 

Erik Nordmark

JinHyeock Choi wrote:

>> Given that we have this, then we have the choice to assume this notification even for the DNA solution, as a way to optimize things. Alternatively, we can try to make the DNA solution be more robust again a missing 'link up' notification.
>
>
>
> I took the latter approach. (that may be the road less traveled. :-))  Allow me to explain my reasoning too. 


ok
But when taking that draft, what guarantees can you provide when you need to use a combination of linkID and CPL/completeRA?
You end up with these combinations when
1. Some but not all routers on the link are new (i.e., are doing linkID)
2. The host moves to/from a link where not all routers on the link are new

My gut feel is that there are many places where you have to defer to prefix comparisons, and if the prefix list you are comparing against is based on CPL, then you have the CPL problem of needing reliably 'link up' indications. But I haven't worked through all the cases to see if this is indeed the case, or whether we can do better.


> For example, with Link UP notification, Linkid scheme may work to detect link change from non-supporting link to supporting one as below.
> Assume a host is at a non-supporting link. Then it doesn't have a linkid prefix. When it moves to a supporting link, it will see a new linkid.
> The host may assume a link change upon receiving this new linkid.
> But the current draft mandates that the host doesn't make any decision becuase there is the other possibility that the host is at the same link but a router on the link becomes a DNA router and
> starts advertising the linkid.
> I contemplated the idea to distinguish the above two cases with Link UP indication but gave it up because I thought the simplicity
> and less assumption is better. 


So assume that linkA has R1 which uses linkID, and R2 which does not.
linkB has R3 which does not implement linkID.

A host H is on linkB and moves to linkA.
Assume H receives the RA from R2 before the RA from R1. How can it tell whether it should assume that R2 is on the same link as R3, or not?
When it receives the RA from R2, the only thing it can rely on is the link up notification (R3 and R3 do not advertise any common prefixes), since R2 and R3 could be two old routers that are on the same link and announce disjoint prefixes.

Thus link up is at least needed "temporarily"; once the RA from R1 arrives (which includes all the prefixes for linkA I assume), then the host can tell that the prefixes it got from R3 are really not on the new link; but until that RA is receives the host needs to rely on the link up.

Do you see a way around this?

   Erik 

Greg Daley

Hi, 

Here's my time/space requirement analysis of the Link Identification
methods.  Based on my analysis, none of them seems to be terribly
difficult to support.

Greg

Parameters: 
-----------

P   number of distinct prefixes on a link
p_r number of distinct prefixes received in pios from router r
l_r number 0of learned prefixes received in pios from router r
N   number of links visited recently.



Discussion of issues and assumptions:
-------------------------------------

Schemes are described with individual sub components,
as well as when combined in compound solutions (as proposed
in drafts).  This made building the analysis easier.

Proposed schemes from the drafts are marked as: **** (Proposed Scheme)

Ignores number of routers on link

None of the schemes: LinkID, CompleteRA, Landmarks require sorted storage,

LinkID requires Minimum selection comparison

Hash tables work fine for DNAPrefixList in completeRA and
Prefix Landmark, so long as hash table traversal for
CompleteRA generation is linear: O(P).

Additional Storage indicates storage for learned information on 
routers, and ignores storage requirements for the RFC2461 AdvPrefixList.

Additional comparison of host side requirements for schemes when also
using Complete Prefix Lists is provided for context.

Time calculations ignore signature generation and verification times
(which are affected by the overall length of the message).

In order to be robust against prefix departures, O(P) prefixes may need
to be stored for LinkID, but the minimum is O(1).





Router Side storage and processing requirements.
================================================

CompleteRA:
-----------
Additional Storage: O(P) keep DNAPrefixList

RA build time: O(P) traverse DNAPrefixList.

RA processing: O(p_r) insertion of prefixes into hash table.

Timers: 1 Expiry timer (callback or operation based)
       

Prefix Landmarks:
-----------------
Additional Storage: O(P) keep DNAprefixlist

RA build time: O(1) comparison of landmark with DNAPrefixList.

RA processing: O(p_r) insertion of prefixes into hash table.

Timers: 1 Expiry timer (callback or operation based)


CompleteRA+PrefixLandmarks **** (Proposed Scheme)
-------------------------------------------------
Additional Storage: O(P) keep DNAprefixlist

RA build time: O(1) comparison of landmark with DNAPrefixList.
               OR
               O(P) traverse DNAPrefixList.


RA processing: O(p_r) insertion of prefixes into hash table.

Timers: 1 Expiry timer (callback or operation based)



Prefix LinkID  **** (Proposed Scheme):
---------------------------------------
Additional Storage: O(1) keep LinkID and Old LinkID

RA Build time: O(1) selection of LinkID and Old LinkID


RA Processing: O(p_r) comparison of each prefix with LinkID

Timers: 1 expiry timer (callback or operation based)


Unmodified RFC 2461 Routers:
----------------------------
Additional Storage: zero

RA Build time: O(1) (add pio processing time for own prefixes)

RA processing: O(1) (RA consistency checks)
               OR
               zero

Timers: 0 or 1 expiry timer (prefix retraction)








Host Side storage and processing requirements.
==============================================

CompleteRA:
-----------
Storage: O(P) Prefix List of distinct prefixes on link

RA Processing: O(P) = O(p_r+l_r) storage of prefixes in prefix list.

RS build time: O(1), normal RS.  
               OR
               zero, no RS.

Learning time: 1 message


Prefix Landmark:
----------------
Storage: O(1) landmark prefix (minimum)
         O(P) prefix list (maximum/robust).

RA Processing: O(1) landmark inpsection

RS build time: O(1), normal RS + selected landmark.

Learning time: 1 message


CompleteRA+Prefix Landmark **** (Proposed Scheme  -- see below for CPL):
--------------------------------------------------
Storage: O(P) Prefix List of distinct prefixes on link

RA Processing: O(1)landmark inspection
               or
               O(P) storage of prefixes in prefix list.

RS build time: O(1), normal RS.
               OR
               O(1), normal RS + selected landmark  
               OR
               zero, no RS.

Learning time: 1 message ( more if Landmark:"NO" is incomplete)




Prefix LinkID **** (Proposed Scheme  -- see below for CPL):
-------------------------------------
Storage: O(1) Prefix LinkID (minimum)
         O(N) set of linkIDs received recently on different IP links.


RA Processing: O(1) LinkID inspection, comparison to recent LinkIDs.

RS build time: O(1), normal RS.
               OR
               zero, no RS.

Learning time: 1 message.




Complete Prefix Lists:
----------------------
Storage: O(P + P') Current link object + Candidate Link Object.

RA processing: O(p_r) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS.


Learning time: NUM_RS_RA_COMPLETE (1..3) * 4 seconds.




CompleteRA + Complete Prefix Lists:
-----------------------------------
Storage: O(P + P') Current link object + Candidate Link Object.

RA processing: O(P) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS.


Learning time: 1 message.




Landmark + Complete Prefix Lists:
-----------------------------------
Storage: O(P + P') Current link object + Candidate Link Object.

RA processing: O(1) Landmark inspection
               OR
               O(P) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS + selected landmark


Learning time: 1 message (Landmark)
               NUM_RS_RA_COMPLETE (1..3) * 4 seconds (Complete Prefix List).




CompleteRA + Landmark + Complete Prefix Lists **** (Proposed Scheme):
---------------------------------------------------------------------
Storage: O(P + P') Current link object + Candidate Link Object.

RA processing: O(1) Landmark inspection
               OR
               O(P) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS + selected landmark
               OR
               O(1), normal RS.
               OR
               zero.

Learning time: 1 message




LinkID + Complete Prefix Lists  **** (Proposed Scheme):
-------------------------------------------------------
Storage: O(P + P') Current link object + Candidate Link Object.
         Maybe + O(N) set of linkIDs received recently on different IP
links.

RA processing: O(1) LinkID inspection, comparison to recent LinkIDs.
               OR
               O(P) insertion of prefixes into candidate link object,
               + comparison with current link object.

RS build time: O(1), normal RS.
               OR
               zero, no RS.


Learning time: 1 message
               OR
               NUM_RS_RA_COMPLETE (1..3) * 4 seconds (Complete Prefix List).

Brett Pentland

Tero Kauppinen (JO/LMF) wrote:

> Hi Brett,
>
> I'm having this endless LinkID v.s. Landmark battle in my head while
> trying to grasp what has been said and written.
>
> Anyway, I started think the following naïve example:
>
> R1 : advertising P1               R2 : adverstining P2 thus {adv:P1,
> learned:P2}         thus {adv:P2, learned: P1}
>
> node H: knows P1, P2 and has chosen P1 as the landmark prefix
>
> Let's assume that R1 stops advertising P1 and starts advertising a
> new prefix P3. The host doesn't receive RAs and is unaware of the
> change. The node moves to another AP and gets a "no" answer. The
> landmark approach indicates wrongly a link change, but CPL will show
> that there is actually no link change. If I have been able to follow
> the discussion, it has been said that the CPL decision should
> overwrite Landmark's decision in this case.


It doesn't have to be CPL, but the presence of prefixes in the RA that
the host has seen before are a strong indication that link change has
not taken place.  The draft is not clear on this because we still have
it as an open issue (issue 9 - actually dates back to when we had the
"landmark not on link option" but the concept is the same).  I
definitely think that matching prefixes should overrule a "NO" answer.
There were some concerns that the inconsistancy should mean that we
fall back to another means of identifying the link (CPL?) but I think
that means we'll end up with the same result.

>
> I agree but I guess a lot of fuzz is because this is not clearly
> stated in the draft -- should it or is it still an open issue? This
> would practically mean that every time a "no" answer is received, the
> current list of all known prefixes on the link is checked in order to
> confirm that the RA doesn't contain a prefix which is already known
> to be on the link.
>
> ...or am I just once again completely lost? :)


No, I think you've pretty much got it.  See above re: the open issue.

>
> Might also be that we should write down something about the case when
> a node changes the landmark prefix. If the node received a
> zero-lifetime advertisement for the current landmark prefix, it
> should pick another prefix. On the other hand, "5.2.3. The prefix
> MUST have a non-zero valid lifetime" is a way to say it.


I think so.  :)

Cheers,
Brett. 

JinHyeock Choi

Greg
 

>> Link Identifiers
>> ---------------------
>> 
>> A Host H, exists and moves around the Internet.
>> 
>> On an link unvisited by the host, Link L, a prefix, P is
>> retracted by one of the routers Router1. Subsequent to this,
>> the actual lowest prefix on the link is Prefix Q.
>> 
>> 
>> Another router, Router2 fails to see the prefix retraction.
>> (Perhaps RAs are lost, or Router1 didn't comply with
>> section 6.2.6 of RFC2461).
>> 
>> The prefix is then reassigned within its previous
>> lifetime to another link, link M, whose lowest prefix
>> was prefix T.  Link M, has also not been visited by
>> host H.
>> 
>> Link Identifiers are in use on both Link L and
>> Link M.  On Link M, all routers advertise Prefix P
>> as current LinkID and Prefix T as OldLinkID.
>> 
>> On Link L, Router2 advertises prefix P as Current LinkID.
>> 
>> If the host H arrives on Link L, it may receive
>> Prefix P as LinkID even though it is no longer present
>> on-link.  The host would configure Prefix Q (or a higher prefix)
>> which is advertised in a PIO.
>> 
>> If the LinkID is not contradicted, for example if there are
>> no other advertising routers left on the link, when the host
>> moves to Link M, it will also receive an RA with prefix P as
>> the Current LinkID.  The Old LinkID will be ignored (it hasn't
>> been seen before).
>> 
>> In this case, no change will be detected upon arrival to
>> link M, and the previous prefix will remain configured.


The above example gives a problem because a linkid prefix is 
reassigned to the other link within 3 hours. 

The draft recommends that a linkid prefix should not be reassigned
to other link within 3 hours. 

If network administrator follows the recommendation, such
a problem won't happen. So I don't think we need to worry about 
this problem.  


>> I understand that LinkID is quite robust against change.
>> 
>> The point I originally was making was that while it is robust,
>> All of the schemes are flawed to some extent.


I can't deny the possibility but don't think your example
showed such a flaw. The false detection comes from 
human error. 

Best Regards

JinHyeock

Greg Daley

Dear JinHyeock,

----- Original Message -----
[cut]

>>> > 
>>> > In this case, no change will be detected upon arrival to
>>> > link M, and the previous prefix will remain configured.
>
>> 
>> The above example gives a problem because a linkid prefix is 
>> reassigned to the other link within 3 hours. 
>> 
>> The draft recommends that a linkid prefix should not be reassigned
>> to other link within 3 hours. 
>> 
>> If network administrator follows the recommendation, such
>> a problem won't happen. So I don't think we need to worry about 
>> this problem.  


In None of the cases, is there an error unless there is
reassignment of the prefix within the lifetime of the 
RA, and the timeout of information over an interval
(?? don't know if it is 3 hours) has been previously 
described as a minor modification to both CompleteRA and
Landmarks. 

These were all assumed to apply the same technique.

So if we wait 3 hours, they are all equally robust
(perfectly so).  This is the common case with all
the examples presented thus far.

What has been discussed recently on list was precisely 
the issue of operators reassigning prefixes without
following recommendations.

If you believe this is not an important issue, we can
check if others think so too, and avoid inventing
cases for it.

Thanks for your help,

Greg

JinHyeock Choi

Greg 


>> In None of the cases, is there an error unless there is
>> reassignment of the prefix within the lifetime of the
>> RA, and the timeout of information over an interval
>> (?? don't know if it is 3 hours) has been previously
>> described as a minor modification to both CompleteRA and
>> Landmarks.
>> 
>> These were all assumed to apply the same technique.
>> 
>> So if we wait 3 hours, they are all equally robust
>> (perfectly so).  This is the common case with all
>> the examples presented thus far.


No, the above technique concerns only for "flash renumbering 
and early reassignment" but there were examples which were
not related to "flash renumbering and early reassignment".   


>> What has been discussed recently on list was precisely
>> the issue of operators reassigning prefixes without
>> following recommendations.


The example I gave Erik has nothing to do with 
reassignment. 

I think you have a misconception. The synchronization issues 
raised so far don't concerns only "flash renubmering and early 
reassignment". They also deal with "flassping" or "Temporary 
lack of synchronization." 

Best Regards

JinHyeock

Greg Daley

Hi JinHyeock,

I'll try to have a look back through the thread
at the other issues described (and particularly
the example mentioned below).  I may not respond
quickly due to the large number of messages on
this topic...

It would be good to see what the most critical
subset of issues regarding synchronization
are still contentious.  Hopefully it is smaller
than we originally thought.

If that's the case, we may be ablem to start a new
thread with just what is left (and make it easier
for people to see the remnant issues).

Does that sound like a plan?

Greg

----- Original Message -----
From: JinHyeock Choi <jinchoe@gmail.com>
Date: Friday, July 29, 2005 3:13 pm
Subject: Re: [DNA] Re: LinkID v.s. Landmark Prefix

>> Greg 
>> 
>
>>> > In None of the cases, is there an error unless there is
>>> > reassignment of the prefix within the lifetime of the
>>> > RA, and the timeout of information over an interval
>>> > (?? don't know if it is 3 hours) has been previously
>>> > described as a minor modification to both CompleteRA and
>>> > Landmarks.
>>> > 
>>> > These were all assumed to apply the same technique.
>>> > 
>>> > So if we wait 3 hours, they are all equally robust
>>> > (perfectly so).  This is the common case with all
>>> > the examples presented thus far.
>
>> 
>> No, the above technique concerns only for "flash renumbering 
>> and early reassignment" but there were examples which were
>> not related to "flash renumbering and early reassignment".   
>> 
>
>>> > What has been discussed recently on list was precisely
>>> > the issue of operators reassigning prefixes without
>>> > following recommendations.
>
>> 
>> The example I gave Erik has nothing to do with 
>> reassignment. 
>> 
>> I think you have a misconception. The synchronization issues 
>> raised so far don't concerns only "flash renubmering and early 
>> reassignment". They also deal with "flassping" or "Temporary 
>> lack of synchronization." 
>> 
>> Best Regards
>> 
>> JinHyeock

Greg Daley

Hi, 

Here is a comparison of the different Link Identification features
available in draft-pentland-dna-protocol and draft-jinchoi-dna-
protocol2

It's aimed at providing a feature distinction, although there are
also a couple of outstanding issues to be considered separately.

http://www.ctie.monash.edu.au/dna/DNASolnComparison_28July2005.ppt

Greg

JinHyeock Choi

Dear Erik


>>> > ok. From now on, I will use the term "flapping" only in the sense you
>>> > describes.
>>> >
>>> > For the more general case I presented, I will use the term 'LOS (Lack
>>> > of Synchronization). Is it ok?
>
>> 
>> ok, but see below.
>> Also, I don't think "out of synch" can be determined in a distributed
>> system, since there is always a non-zero delay. Hence if R1 sends a RA
>> and R2 and R3 receives it, an observer can't tell which or R2 and R3
>> updated the prefix list first (or whether they did it at exactly the
>> same time).


This is intriguing. I didn't think "out of synch" in a distributed system 
point of view. Rather I naively assumed Newtonian absolute time and  
an omniscient observer. Let me think it over more. 


>>> > ok. I think it's also important that DNA solution cope gracefully with
>>> > more general case of  temporary LOS (Lack of Synchronization). If
>>> > DNA solution can deal with LOS, I think it can deal with flapping
>>> > automatically.
>
>> 
>> I don't see using the LOS term as helpful here.
>> LOS captures the case when router1's list of prefixes is out of date
>> with router2's two list of prefixes, even if only for a nanosecond.
>> 
>> What matters is the sequence of events that are observable.


I am wondering whether LOS (at least the ones which cause problems)
always entails flapping. This also let me think over more.  

Best Regards

JinHyeock

JinHyeock Choi

Erik 


>> ok
>> But when taking that draft, what guarantees can you provide when you 
>> need to use a combination of linkID and CPL/completeRA?
>> You end up with these combinations when
>> 1. Some but not all routers on the link are new (i.e., are doing linkID)
>> 2. The host moves to/from a link where not all routers on the link are new
>> My gut feel is that there are many places where you have to defer to 
>> prefix comparisons, and if the prefix list you are comparing against is 
>> based on CPL, then you have the CPL problem of needing reliably 'link 
>> up' indications. But I haven't worked through all the cases to see if 
>> this is indeed the case, or whether we can do better. 


If a host has 1) a linkid and 2) receives an RA with the prefix with I-bit set, 
it can make a decision properly. So even in the above two cases, hosts
may satisfy these two conditions to properly check for link change without 
resorting to prefix comparison. 

But if either of two conditions is not satisfied, the host need to fall back
on CPL. In this case, we need reliable "Link UP" indication.  


>> So assume that linkA has R1 which uses linkID, and R2 which does not.
>> linkB has R3 which does not implement linkID.
>> 
>> A host H is on linkB and moves to linkA.
>> Assume H receives the RA from R2 before the RA from R1. How can it tell 
>> whether it should assume that R2 is on the same link as R3, or not? 

 
H should use CPL because it doesn't have any linkid prefix. 


>> When it receives the RA from R2, the only thing it can rely on is the 
>> link up notification (R3 and R3 do not advertise any common prefixes), 
>> since R2 and R3 could be two old routers that are on the same link and 
>> announce disjoint prefixes.


It's not clear to me. What can Link UP say to host H? It can't 
say anything definite about whether link change happens or not. 


>> Thus link up is at least needed "temporarily"; once the RA from R1 
>> arrives (which includes all the prefixes for linkA I assume), then the 
>> host can tell that the prefixes it got from R3 are really not on the new 
>> link; but until that RA is receives the host needs to rely on the link up.


I still don't understand what kind of information can Link Up 
can provide to H. 


>> Do you see a way around this?


Sorry, I still don't catch the problem clearly. 

This is what I have in mind. 

After H moves from LinkB to LinkA, it receives a hint for 
a possible link change. 

To make Link UP presence the smallest, I assume H used 
the lack of RA from R3 as a hint. H missed 3 RAs from R3
and came to suspect a link change. 

Because H doesn't have a linkid prefix, it needs to use CPL. 
So H activates CPL module and sends an RS. 

Because H relies on CPL in this case, it needs Link UP. 

Best Regards

JinHyeock

JinHyeock Choi

Greg 


>> It would be good to see what the most critical
>> subset of issues regarding synchronization
>> are still contentious.  Hopefully it is smaller
>> than we originally thought.
>> 
>> If that's the case, we may be ablem to start a new
>> thread with just what is left (and make it easier
>> for people to see the remnant issues).


ok. Also I wish we make it clear how Landmark/ CompleteRA 
checks for link change. For example, Erik proposed that 
a known prefix in an RA would overrule the NO in Landmark
option. But that is not reflected in the draft. 

Thanks for your kind consideration. 

Best Regards

JinHyeock

Subba Reddy

Hi Greg,

It is good to see all the time/space requirements at one place.

I have few questions and comments.


>>
>> Greg
>>
>> Parameters:
>> -----------
>>
>> P   number of distinct prefixes on a link
>> p_r number of distinct prefixes received in pios from router r
>> l_r number 0of learned prefixes received in pios from router r
>> N   number of links visited recently.
>>
>>
>>
>> Discussion of issues and assumptions:
>> -------------------------------------
>>
>> Schemes are described with individual sub components,
>> as well as when combined in compound solutions (as proposed
>> in drafts).  This made building the analysis easier.
>>
>> Proposed schemes from the drafts are marked as: **** (Proposed Scheme)
>>
>> Ignores number of routers on link


I think, if we consider no. of routers on link, then for each RS
1. In Landmark method, all the routers in the link needs to compare the
landmark prefix
    with the DNAPrefix List.
2. In LinkID method, routers just sends RAs, so no comaprision is required
at the router side.


<cut>

>>
>>
>>
>> Router Side storage and processing requirements.
>> ================================================
>>
>> CompleteRA:
>> -----------
>> Additional Storage: O(P) keep DNAPrefixList
>>
>> RA build time: O(P) traverse DNAPrefixList.
>>
>> RA processing: O(p_r) insertion of prefixes into hash table.
>>
>> Timers: 1 Expiry timer (callback or operation based)
>>
>>
>> Prefix Landmarks:
>> -----------------
>> Additional Storage: O(P) keep DNAprefixlist
>>
>> RA build time: O(1) comparison of landmark with DNAPrefixList.


I don't know, which complexity (best case or average case or worst case?)
you have considered.
As per my understanding,
        Best case complexity is O(1) as you have mentioned.
        Average and Worst case complexities are O(P).

Please correct me, if anything is wrong.


>>
>> RA processing: O(p_r) insertion of prefixes into hash table.
>>
>> Timers: 1 Expiry timer (callback or operation based)
>>
>>
>> CompleteRA+PrefixLandmarks **** (Proposed Scheme)
>> -------------------------------------------------
>> Additional Storage: O(P) keep DNAprefixlist
>>
>> RA build time: O(1) comparison of landmark with DNAPrefixList.
>>                OR
>>                O(P) traverse DNAPrefixList.
>>
>>
>> RA processing: O(p_r) insertion of prefixes into hash table.
>>
>> Timers: 1 Expiry timer (callback or operation based)
>>
>>
>>
>> Prefix LinkID  **** (Proposed Scheme):
>> ---------------------------------------
>> Additional Storage: O(1) keep LinkID and Old LinkID


I think storage requirement is O(P). If LinkID prefix is removed from
the link, routers need to select the next smaller prefix from prefix list.

I think, here also, if you have considered only the cases, where LinkID
will not change, O(1) is fine.


>>
>> RA Build time: O(1) selection of LinkID and Old LinkID
>>
>>
>> RA Processing: O(p_r) comparison of each prefix with LinkID
>>


I think, this is O(1) because, only linkID in the RA needs to be compared
with the LinkID at the host.


>> Timers: 1 expiry timer (callback or operation based)
>>
>>
>> Unmodified RFC 2461 Routers:
>> ----------------------------
>> Additional Storage: zero
>>
>> RA Build time: O(1) (add pio processing time for own prefixes)
>>
>> RA processing: O(1) (RA consistency checks)
>>                OR
>>                zero
>>
>> Timers: 0 or 1 expiry timer (prefix retraction)
>>
>>
>>
>>
>>
>>
>>
>>
>> Host Side storage and processing requirements.
>> ==============================================
>>
>> CompleteRA:
>> -----------
>> Storage: O(P) Prefix List of distinct prefixes on link
>>
>> RA Processing: O(P) = O(p_r+l_r) storage of prefixes in prefix list.
>>
>> RS build time: O(1), normal RS.
>>                OR
>>                zero, no RS.
>>
>> Learning time: 1 message
>>
>>
>> Prefix Landmark:
>> ----------------
>> Storage: O(1) landmark prefix (minimum)
>>          O(P) prefix list (maximum/robust).
>>
>> RA Processing: O(1) landmark inpsection
>>
>> RS build time: O(1), normal RS + selected landmark.
>>
>> Learning time: 1 message
>>
>>
>> CompleteRA+Prefix Landmark **** (Proposed Scheme  -- see below for CPL):
>> --------------------------------------------------
>> Storage: O(P) Prefix List of distinct prefixes on link
>>
>> RA Processing: O(1)landmark inspection
>>                or
>>                O(P) storage of prefixes in prefix list.
>>
>> RS build time: O(1), normal RS.
>>                OR
>>                O(1), normal RS + selected landmark
>>                OR
>>                zero, no RS.
>>
>> Learning time: 1 message ( more if Landmark:"NO" is incomplete)
>>
>>
>>
>>
>> Prefix LinkID **** (Proposed Scheme  -- see below for CPL):
>> -------------------------------------
>> Storage: O(1) Prefix LinkID (minimum)
>>          O(N) set of linkIDs received recently on different IP links.
>>


I think, here N is the number of different LinkIDs (if at all) advertised in
the last 1.5hrs
on the link.


>>
>> RA Processing: O(1) LinkID inspection, comparison to recent LinkIDs.
>>
>> RS build time: O(1), normal RS.
>>                OR
>>                zero, no RS.
>>
>> Learning time: 1 message.
>>


<cut>

Thanks & Regards,
Subba Reddy

Greg Daley

Hi Subba,

Thanks for your analysis.  I've asked the draft authors
for further clarification on the points you've raised.

If you've got a reference to the text which indicates what
you meant, we may be able to clear it up ourselves.

----- Original Message -----
[cut]

>> 
>> I think, if we consider no. of routers on link, then for each RS
>> 1. In Landmark method, all the routers in the link needs to 
>> compare the
>> landmark prefix
>>    with the DNAPrefix List.
>> 2. In LinkID method, routers just sends RAs, so no comaprision is 
>> requiredat the router side.


Yes, this is the O(1) operation - hash table lookup for 
Landmark and for CompleteRA.  This is constant time.

It is also constant time to just send the RA in LinkID,
as it has to lookup the LinkID (one operartion or two
operations, if you include OldLinkID).


[cut]

>>> > Prefix Landmarks:
>>> > -----------------
>>> > Additional Storage: O(P) keep DNAprefixlist
>>> >
>>> > RA build time: O(1) comparison of landmark with DNAPrefixList.
>
>> 
>> I don't know, which complexity (best case or average case or worst 
>> case?)you have considered.
>> As per my understanding,
>>        Best case complexity is O(1) as you have mentioned.
>>        Average and Worst case complexities are O(P).


I'm looking at average case complexity.  With a fair sized hash
table, this is what you get.  Of course there are pathological
cases with badly built hashes, or small tables which are worse. 
Worst case therefore degenerates to linear, but you'd practically
never get it if there was a well distributed hash, and the
collision probabilities for a particular value were low enough.

This is fairly well known for hash tables.

[cut]

>>> >
>>> > Prefix LinkID  **** (Proposed Scheme):
>>> > ---------------------------------------
>>> > Additional Storage: O(1) keep LinkID and Old LinkID
>
>> 
>> I think storage requirement is O(P). If LinkID prefix is removed from
>> the link, routers need to select the next smaller prefix from 
>> prefix list.
>> 
>> I think, here also, if you have considered only the cases, where 
>> LinkIDwill not change, O(1) is fine.


This is mentioned in the assumptions at the top.  I guess
that if there's only going to be one prefix removed in a period,
the next smaller prefix is all that's required. In the general
case though, O(P) is correct.


>>> >
>>> > RA Build time: O(1) selection of LinkID and Old LinkID
>>> >
>>> >
>>> > RA Processing: O(p_r) comparison of each prefix with LinkID
>>> >
>
>> 
>> I think, this is O(1) because, only linkID in the RA needs to be 
>> comparedwith the LinkID at the host.


No actually, the learned component of the RA isn't inspected,
for robustness sake (described in the draft: Syam or JinHyeock may
also correct me on this).  This means all the PIOs need to be checked.


[cut]

>>> >
>>> > Prefix LinkID **** (Proposed Scheme  -- see below for CPL):
>>> > -------------------------------------
>>> > Storage: O(1) Prefix LinkID (minimum)
>>> >          O(N) set of linkIDs received recently on different IP 
>
>> links.>
>> 
>> I think, here N is the number of different LinkIDs (if at all) 
>> advertised in the last 1.5hrs on the link.



Actually, I think this is the number of prefixes known on the 
host:

From section 1.3:

Paragraph4:
"...the hosts track the list of linkid prefixes they've
   received in the last 1.5 hours to generate "the linkid prefix list
   (LinkidPrefixList)".

Perhaps, there is confusion, because in most cases, the 
LinkIDPrefixList
is cleared out by the host each time it moves link

Is this the current thinking?

In that case, then the maximum size is P, but the mean size
is much lower (typically 1).





I'll update the description of the assumptions  with the ideas
mentioned here.

Greg

Erik Nordmark

JinHyeock Choi wrote:

> If a host has 1) a linkid and 2) receives an RA with the prefix with I-bit set, it can make a decision properly. So even in the above two cases, hosts
> may satisfy these two conditions to properly check for link change without resorting to prefix comparison.
> But if either of two conditions is not satisfied, the host need to fall back
> on CPL. In this case, we need reliable "Link UP" indication.  


ok

>> When it receives the RA from R2, the only thing it can rely on is the link up notification (R3 and R3 do not advertise any common prefixes), since R2 and R3 could be two old routers that are on the same link and announce disjoint prefixes.
>
>
>
> It's not clear to me. What can Link UP say to host H? It can't say anything definite about whether link change happens or not. 


Link UP indicates to the host that the RA from R3 and R2 could come from different links.
If we want something which doesn't rely on link UP, the host has to always treat each RA as potentially being from a different link, which would be problematic when
1) the routers don't have a common prefix, and
2) the routers don't support DNA
because in the absence of relying on a link UP in this case, the host will end up assuming that each time it receives a RA, it has moved to a different link.

> After H moves from LinkB to LinkA, it receives a hint for a possible link change.
> To make Link UP presence the smallest, I assume H used the lack of RA from R3 as a hint. H missed 3 RAs from R3
> and came to suspect a link change. 


But that would take 90 minutes by default, since the periodic RAs arrive with 30 minute average interval.

Or are you suggesting that the host should always send 3 RSes when it receives a link UP, so that it can use this to retire any old prefixes?
In any case, I think that is orthogonal to whether or not we can come up with a scheme which works reliably even when there are no link UP notifications, for mixed links as well as links with no DNA capable routers.

> Because H doesn't have a linkid prefix, it needs to use CPL. So H activates CPL module and sends an RS.
> Because H relies on CPL in this case, it needs Link UP. 


So it seems like until every link in the Internet supports DNA (it isn't clear to me whether all routers on every link needs to support DNA, or whether it is sufficient to have one per link support it), then the hosts MUST rely on a reliable link up notification in order to always be able to detect movement. Is that correct?

   Erik

Sathya Narayanan

Erik -


>> So it seems like until every link in the Internet supports DNA (it isn't 
>> clear to me whether all routers on every link needs to support DNA, or 
>> whether it is sufficient to have one per link support it),

It isn't clear to me either. But, IMHO, we should select a solution which works well in a link with both DNA and non-DNA routers.


>> then the hosts MUST rely on a reliable link up notification in order to always be 
>> able to detect movement. Is that correct?

We discussed this when the comparison slide sent by Greg was prepared. A CompleteRA message from the DNA router can tie all the prefixes on the link together and hence the host need not depend on link-up notification. Also, with prefix-landmark, if the host sends an RS with a prefix advertised by a non-DNA router, a DNA router will still confirm the prefix's presence on the link.

- Sathya 

Subba Reddy

Hi Greg,



>> [cut]
>
>>> >
>>> > I think, if we consider no. of routers on link, then for each RS
>>> > 1. In Landmark method, all the routers in the link needs to
>>> > compare the
>>> > landmark prefix
>>> >    with the DNAPrefix List.
>>> > 2. In LinkID method, routers just sends RAs, so no comaprision is
>>> > requiredat the router side.
>
>>
>> Yes, this is the O(1) operation - hash table lookup for
>> Landmark and for CompleteRA.  This is constant time.
>>
>> It is also constant time to just send the RA in LinkID,
>> as it has to lookup the LinkID (one operartion or two
>> operations, if you include OldLinkID).
>>


ok.


>>
>> [cut]
>
>>>> > > Prefix Landmarks:
>>>> > > -----------------
>>>> > > Additional Storage: O(P) keep DNAprefixlist
>>>> > >
>>>> > > RA build time: O(1) comparison of landmark with DNAPrefixList.
>>
>>> >
>>> > I don't know, which complexity (best case or average case or worst
>>> > case?)you have considered.
>>> > As per my understanding,
>>> >        Best case complexity is O(1) as you have mentioned.
>>> >        Average and Worst case complexities are O(P).
>
>>
>> I'm looking at average case complexity.  With a fair sized hash
>> table, this is what you get.  Of course there are pathological
>> cases with badly built hashes, or small tables which are worse.
>> Worst case therefore degenerates to linear, but you'd practically
>> never get it if there was a well distributed hash, and the
>> collision probabilities for a particular value were low enough.
>>
>> This is fairly well known for hash tables.
>>


True. For a well distributed hash, O(1) is fine.


>> [cut]
>
>>>> > >
>>>> > > Prefix LinkID  **** (Proposed Scheme):
>>>> > > ---------------------------------------
>>>> > > Additional Storage: O(1) keep LinkID and Old LinkID
>>
>>> >
>>> > I think storage requirement is O(P). If LinkID prefix is removed from
>>> > the link, routers need to select the next smaller prefix from
>>> > prefix list.
>>> >
>>> > I think, here also, if you have considered only the cases, where
>>> > LinkIDwill not change, O(1) is fine.
>
>>
>> This is mentioned in the assumptions at the top.  I guess
>> that if there's only going to be one prefix removed in a period,
>> the next smaller prefix is all that's required. In the general
>> case though, O(P) is correct.
>>


fine.


>>>> > >
>>>> > > RA Build time: O(1) selection of LinkID and Old LinkID
>>>> > >
>>>> > >
>>>> > > RA Processing: O(p_r) comparison of each prefix with LinkID
>>>> > >
>>
>>> >
>>> > I think, this is O(1) because, only linkID in the RA needs to be
>>> > comparedwith the LinkID at the host.


From Section 4.2 (4th paragraph) of the LinkID draft(00/01)

"
   When a host with a linkid prefix receives an RA, whether solicited or
   unsolicited, that includes a prefix with I-bit set, the host compares
   its LinkidPrefixList with the set of prefixes in the RA.
"

Host compares, its LinkID (stored in LinkIDPrefixList) with the LinkID
advertised in RA (i.e, the prefix with I bit set. This prefix can be
learned prefix or router's own prefix).
So, only one comarision is required if the LinkIDPrefixList consists of
only one prefix (Most of the time LinkIDPrefixList consists of only one
prefix).

So, I think it is O(1).


>>
>> No actually, the learned component of the RA isn't inspected,
>> for robustness sake (described in the draft: Syam or JinHyeock may
>> also correct me on this).  This means all the PIOs need to be checked.
>>


Routers will not consider the learned prefixes for the robustness sake, but
not the hosts.

From Section 3.2 (4th paragraph) of the LinkID draft(01),

"
   From the received RAs, the router extracts only the valid prefixes in
   PIO and generate the "learned prefix list (LearnedPrefixList)".
"

From Section 3.2 (last paragraph) of the LinkID draft(01),

"
   Take notice that, for prefix list generation, a router only takes the
   prefixes in PIO into consideratoin.
"


>>
>> [cut]
>
>>>> > >
>>>> > > Prefix LinkID **** (Proposed Scheme  -- see below for CPL):
>>>> > > -------------------------------------
>>>> > > Storage: O(1) Prefix LinkID (minimum)
>>>> > >          O(N) set of linkIDs received recently on different IP
>>
>>> > links.>
>>> >
>>> > I think, here N is the number of different LinkIDs (if at all)
>>> > advertised in the last 1.5hrs on the link.
>
>>
>>
>> Actually, I think this is the number of prefixes known on the
>> host:
>>


Most of the time LinkIDPrefixList consists of only one prefix i.e, LinkID.
If LinkID of the link changes, because of addition/deletion of prefixes,
then
LinkIDPrefixList can contain more than 1 prefix.


>> From section 1.3:
>>
>> Paragraph4:
>> "...the hosts track the list of linkid prefixes they've
>>    received in the last 1.5 hours to generate "the linkid prefix list
>>    (LinkidPrefixList)".
>>
>> Perhaps, there is confusion, because in most cases, the
>> LinkIDPrefixList
>> is cleared out by the host each time it moves link
>>
>> Is this the current thinking?


True. If a host changes its link, it will clear the LinkIDPrefixList.


>>
>> In that case, then the maximum size is P, but the mean size
>> is much lower (typically 1).


True. I also think O(1) is fine.

Thanks & Regards,
Subba Reddy

Subba Reddy

Hi Greg,


>>
>> I think we're oscillating towards resolution.


True.


>>
>> ----- Original Message ----- 
>
>>>>>> > > > >
>>>>>> > > > > RA Build time: O(1) selection of LinkID and Old LinkID
>>>>>> > > > >
>>>>>> > > > >
>>>>>> > > > > RA Processing: O(p_r) comparison of each prefix with LinkID
>>>>>> > > > >
>>>>
>>>>> > > >
>>>>> > > > I think, this is O(1) because, only linkID in the RA needs to be
>>>>> > > > comparedwith the LinkID at the host.
>>
>>> >
>>> > From Section 4.2 (4th paragraph) of the LinkID draft(00/01)
>>> >
>>> > "
>>> >   When a host with a linkid prefix receives an RA, whether
>>> >   solicited or unsolicited, that includes a prefix with
>>> >   I-bit set, the host compares its LinkidPrefixList with the
>>> >   set of prefixes in the RA.
>>> > "
>>> >
>>> > Host compares, its LinkID (stored in LinkIDPrefixList) with the
>
>> LinkID
>
>>> > advertised in RA (i.e, the prefix with I bit set. This prefix can be
>>> > learned prefix or router's own prefix).
>>> > So, only one comarision is required if the LinkIDPrefixList
>>> > consists of only one prefix (Most of the time LinkIDPrefixList
>>> > consists of only one prefix).
>>> >
>>> > So, I think it is O(1).
>
>>
>> OK. I get your point.
>>
>> Thinking about it another way though, each PIO and LPIO has to be
>> checked for the LinkID flag, and then that LinkID has to be compared
>> with the stored LinkID.
>>


If the first prefix in the RA is LinkID prefix (if any), then only one
comparision is enough.
I feel, routers can maintain the LinkID prefix as the first prefix, in their
prefix list.
Because of this, routers can easily check (with O(1) complexity) the
validity of LinkID
at various point of times (like prefix life time changes, new prefix is
added, LinkID prefix
is a learned prefix and it has not been advertised in the last 1.5hrs). So,
routers can easily
include LinkID prefix as the first prefix in the RA. Also, maintaining the
LinkID prefix as the first
entry in the prefix list will not add any additional complexity (It is
constant O(1)).

Though, whatever I have mentioned is more implementation specific, IMHO O(1)
is fine.


>>>> > >
>>>> > > No actually, the learned component of the RA isn't inspected,
>>>> > > for robustness sake (described in the draft: Syam or JinHyeock may
>>>> > > also correct me on this).  This means all the PIOs need to be
>>
>>> > checked.>
>>> >
>>> > Routers will not consider the learned prefixes for the robustness
>>> > sake, but not the hosts.
>>> >
>>> > From Section 3.2 (4th paragraph) of the LinkID draft(01),
>>> >
>>> > "
>>> >   From the received RAs, the router extracts only the valid
>>> >   prefixes in PIO and generate the "learned prefix list
>>> >   (LearnedPrefixList).
>>> > "
>>> >
>>> >
>>> > From Section 3.2 (last paragraph) of the LinkID draft(01),
>>> >
>>> > "
>>> >   Take notice that, for prefix list generation, a router only
>>> >   takes the prefixes in PIO into consideratoin.
>>> > "
>
>>
>> Thanks for the references. I'll check this out further.
>>
>
>>>> > >
>>>> > > [cut]
>>>
>>>>>> > > > >
>>>>>> > > > > Prefix LinkID **** (Proposed Scheme  -- see below for CPL):
>>>>>> > > > > -------------------------------------
>>>>>> > > > > Storage: O(1) Prefix LinkID (minimum)
>>>>>> > > > >          O(N) set of linkIDs received recently on different IP
>>>>
>>>>> > > > links.>
>>>>> > > >
>>>>> > > > I think, here N is the number of different LinkIDs (if at all)
>>>>> > > > advertised in the last 1.5hrs on the link.
>>>
>>>> > >
>>>> > >
>>>> > > Actually, I think this is the number of prefixes known on the
>>>> > > host:
>>>> > >
>>
>>> >
>>> > Most of the time LinkIDPrefixList consists of only one prefix i.e,
>>> > LinkID.If LinkID of the link changes, because of addition/deletion
>>> > of prefixes, then LinkIDPrefixList can contain more than 1 prefix.
>
>>
>> OK this is worth noting in the assumptions.
>>
>>
>
>>>> > > From section 1.3:
>>>> > >
>>>> > > Paragraph4:
>>>> > > "...the hosts track the list of linkid prefixes they've
>>>> > >    received in the last 1.5 hours to generate "the linkid prefix
>>
>>> > list>    (LinkidPrefixList)".
>>
>>>> > >
>>>> > > Perhaps, there is confusion, because in most cases, the
>>>> > > LinkIDPrefixList
>>>> > > is cleared out by the host each time it moves link
>>>> > >
>>>> > > Is this the current thinking?
>>
>>> >
>>> > True. If a host changes its link, it will clear the LinkIDPrefixList.
>>> >
>>
>>>> > >
>>>> > > In that case, then the maximum size is P, but the mean size
>>>> > > is much lower (typically 1).
>>
>>> >
>>> > True. I also think O(1) is fine.
>
>>
>> OK, I'll mention O(1), but also note the assumption as described above.


OK.


>>
>> Greg
>>


Thanks & Regards,
Subba Reddy

Jim Bound

I have tried to pereceive implementation pain and advantage from both
Landmark and Link-ID views, and the complexity of the code and
extensions required.  I think this gets into the time vs. space issues
we faced looking at OSI ES-IS vs ARP when defining ND years ago, only a
much harder technical problem (I think its up there with SHIM6 work).  I
see similar positions and debates.  Most of the mail for me has not been
helpful to sway me one way or the other yet.  It has shown me neither is
complete yet. What I like about Landmark it is a pure extension to ND
for IPv6, but what I don't like nor can support at least right now is
modifying the current RA.  Doing that is not good and I would at least
like to see means to enhance or form new RA for particpating Landmark
hosts and routers.  What I like about the Link-ID is I believe it will
converge quickly for one of my hot buttons for mobility and that is mesh
networks (note not MANETs and I can get into the diff offline "only"
with others, per Greg's mail to keep the focus here).  I intend to do in
depth technical review of both and ask some folks I know out of the IETF
building mobile networks now for products with MIPv6 who want to be
anonymous to help me review it as ghost persons, and I am building some
to of course, so I have a bias clearly.  Possibly there is a compromise
and integration of ideas here.

What I empatically do not agree with is James K's statement that we
should stop work on Link-ID because it may use up a bit more time and
white paper space than Landmark.  That is not an engineering argument or
technical rationale, but false bravado at this point I will assume for
time-to-market reasons.  I agree with need to ship something, but this
is serious stuff, and unless Greg tells me we don't have more time I
assume we can get this right?

I am assuming on both sides of the architectures is that there is no IPR
from any company as authors on either of these solutions?  If there is
and I missed it in the specs, and I will check again, please speak up
now and tell us you have patents on what your proposing.  This has to
stop in the IETF and will probably kill CGA and other ideas that may
never get widely used in the market.  Most of us are quite sick of it
and I consider it dishonorable if not presented up front immediately.

/jim

James Kempf

Jim


>> What I empatically do not agree with is James K's statement that we
>> should stop work on Link-ID because it may use up a bit more time and
>> white paper space than Landmark.  That is not an engineering argument or
>> technical rationale, but false bravado at this point I will assume for
>> time-to-market reasons.  I agree with need to ship something, but this
>> is serious stuff, and unless Greg tells me we don't have more time I
>> assume we can get this right?
>>


I think I might not have been clear. What I intended to say was that I think
backward compatibility is more important than whether one or another
protocol has a few extra bytes. It sounds like that is what you are
concerned with too.
 Or are you saying that you think size/time is more important?

            jak

Jim Bound

James, I do agree backwards compatibility is important and unless
something is awfully good then I cannot see breaking code.  Ergo both do
that too currently.

thanks
/jim