TWiki > DNA > DNASolution1 > DNASoln1Issue019 TWiki webs:
Main | TWiki | Know | Sandbox
DNA . { History of Changes | DNA Documents | Search | Go }
Back to DNA Solution1 Issue Tracker

LinkID vs. Landmark Prefix

The draft currently uses Landmark Prefixes for link identification.  That is,
hosts send a prefix in the router solicitation that asks, "is this prefix
on this link?" and the routers can answer yes or no in their advertisement.
There is an alternative proposal using prefixes as LinkIDs to identify the
link.  That is, the routers choose one of the prefixes on the link by
algorithmic means to use as the link identifier and all routers advertise
that prefix with a flag to mark it.
Which scheme should the DNA group choose to move forward with?


Discussion


James Kempf

I am in favor of Landmark Prefix and not LinkID. I could go through a list
of problems I have with draft-jinchoi but I'm sure JinHyeock could up with
reasonable responses, and I'm not interested in getting into a long email
conversation about specific details of LinkID, because it would only result
in more text getting added to the draft to handle problems and special cases
with the protocol.

My basic objection is that LinkID is considerably more more complex than
Landmark Prefix. draft-jinchoi requires 22 pages just to describe the link
identification protocol, whereas the latest draft of draft-pentland covers
link identification, fast RA delivery, link configuration, address state
machine management, and more in 25 pages. Essentially, the draft to describe
the entire DNA protocol using Landmark Prefix is only 3 pages more than the
draft to describe just the link identification part using LinkID. Page count
is a kind of crude measure of complexity, but I think this analysis would
hold up if one went through in more detail. There's a lot of special case
language, extra timers, and extra data structures in LinkID that aren't
needed for Landmark Prefix.

I support selecting Landmark Prefix for the WG draft for DNA.

            jak

Brett Pentland

I created an issue page for this topic.  See:

http://ctieware.eng.monash.edu.au/twiki/bin/view/DNA/DNASoln1Issue019

I'm also in favour of the landmark approach.

Amongst other things, I think it integrates more easily with non-DNA
devices.  A host that comes from a non-DNA link to a DNA link gets a
positive confirmation of link change.  I don't think this is the case
with LinkID which relies on detecting change in the LinkID (which there
won't be on a non-DNA link).

Brett.

Greg Daley

Hi Brett,

Thanks for creating the issue.

I'm taking my hat off for this e-mail.

Brett Pentland wrote:

> I created an issue page for this topic.  See:
>
> http://ctieware.eng.monash.edu.au/twiki/bin/view/DNA/DNASoln1Issue019
>
> I'm also in favour of the landmark approach.
>
> Amongst other things, I think it integrates more easily with non-DNA
> devices.  A host that comes from a non-DNA link to a DNA link gets a
> positive confirmation of link change.  I don't think this is the case
> with LinkID which relies on detecting change in the LinkID (which there
> won't be on a non-DNA link).



I'd like to point out that protocol-00/protocol-01 have two Link
Identification mechanisms which interact.

The draft has the prefix landmark scheme (Request in RS, Response in RA)
which is able to answer questions regardless of which link a prefix was
previously on.

It also contains a specification of CompleteRA, which contains an
augmented RA (like Prefix LinkID) in even unsolicited RAs.
Rightly, comparisons should initially be made between CompleteRA
and Prefix LinkID,  rather than between Prefix LinkID and
Prefix Landmarks, since the augmented RA schemes have so much in common.

I'd guess that the desirable solution for me is either:

Prefix Landmark + CompleteRA

Prefix Landmark + Prefix LinkID

rather than argument for removal of prefix landmarks (which serve a
purpose wherever RSs are required for DNA).

This below represents my current (personal) leanings:

Personally, while the cost of CompleteRA is potentially higher if the
prefixes advertised by routers aren't the same, I still believe that it
has strong advantages in being able to immediately help construct a
complete list of prefixes on the link, which can be used in RA matching
if a link-hint is received again (even if the host moves to a non-DNA
link).

CompleteRA and Prefix Landmarks also both work well even if they share
a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
router is able to answer questions about the prefixes in use by the
legacy routers (CompleteRA readvertises these in the DNAO, and a
Landmark query can be answered easily, regardless of the original
advertisor's DNA status).

Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
link's identity.

Greg 

Sathya Narayanan

Greg -

I agree with your preference: I too prefer Prefix Landmark + CompleteRA
, among other things, CompleteRA helps with building of the CPL if the
host moves out to a non-DNA link.

Prefix Landmark provides a way for the router to know whether the host
with the 'landmark question' has changed link or not and build its
(unicast-)RA accordingly, which I think will be very efficient in terms
of bandwidth utilization as 'no link change' is more likely than not. I
quote from "-01.txt"

   "In the case when the host is still attached to the same link, which
   might occur when the host has changed from using one layer 2 access
   point to another, but the access points are on the same link, the
   Router Advertisement(s) it receives will contain a "yes, that prefix
   is on this link" answer, and no other information.  Thus, such RA
   messages are quite small.

   In the case when the landmark prefix is unknown to the responding
   router, the host will receive a "No" answer to its landmark question,
   and also the information it needs to configure itself for the new
   link.  The routers try to include as much information as possible in
   such messages, so that the host can be informed of all the prefixes
   assigned to the new link as soon as possible."


- Sathya


>> Hi Brett,
>>
>> Thanks for creating the issue.
>>
>> I'm taking my hat off for this e-mail.
>>
>> Brett Pentland wrote:
>>
>
>>>> I created an issue page for this topic.  See:
>>>>
>>>> http://ctieware.eng.monash.edu.au/twiki/bin/view/DNA/DNASoln1Issue019
>>>>
>>>> I'm also in favour of the landmark approach.
>>>>
>>>> Amongst other things, I think it integrates more easily with non-DNA
>>>> devices.  A host that comes from a non-DNA link to a DNA link gets a
>>>> positive confirmation of link change.  I don't think this is the case
>>>> with LinkID which relies on detecting change in the LinkID (which there
>>>> won't be on a non-DNA link).
>
>>
>>
>>
>> I'd like to point out that protocol-00/protocol-01 have two Link
>> Identification mechanisms which interact.
>>
>> The draft has the prefix landmark scheme (Request in RS, Response in RA)
>> which is able to answer questions regardless of which link a prefix was
>> previously on.
>>
>> It also contains a specification of CompleteRA, which contains an
>> augmented RA (like Prefix LinkID) in even unsolicited RAs.
>> Rightly, comparisons should initially be made between CompleteRA
>> and Prefix LinkID,  rather than between Prefix LinkID and
>> Prefix Landmarks, since the augmented RA schemes have so much in common.
>>
>> I'd guess that the desirable solution for me is either:
>>
>> Prefix Landmark + CompleteRA
>>
>> Prefix Landmark + Prefix LinkID
>>
>> rather than argument for removal of prefix landmarks (which serve a
>> purpose wherever RSs are required for DNA).
>>
>> This below represents my current (personal) leanings:
>>
>> Personally, while the cost of CompleteRA is potentially higher if the
>> prefixes advertised by routers aren't the same, I still believe that it
>> has strong advantages in being able to immediately help construct a
>> complete list of prefixes on the link, which can be used in RA matching
>> if a link-hint is received again (even if the host moves to a non-DNA
>> link).
>>
>> CompleteRA and Prefix Landmarks also both work well even if they share
>> a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
>> router is able to answer questions about the prefixes in use by the
>> legacy routers (CompleteRA readvertises these in the DNAO, and a
>> Landmark query can be answered easily, regardless of the original
>> advertisor's DNA status).
>>
>> Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
>> link's identity.
>>
>> Greg

James Kempf

Greg,

I agree that CompleteRA is preferable to PrefixID, for the reasons you've
stated.

            jak

----- Original Message -----
From: "Greg Daley" <greg.daley@eng.monash.edu.au>
To: "Brett Pentland" <brett.pentland@eng.monash.edu.au>
Cc: "James Kempf" <Kempf@docomolabs-usa.com>; "Dna" <dna@eng.monash.edu.au>
Sent: Tuesday, July 19, 2005 12:31 AM
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s.
Landmark Prefix



>> Hi Brett,
>>
>> Thanks for creating the issue.
>>
>> I'm taking my hat off for this e-mail.
>>
>> Brett Pentland wrote:
>
>>> > I created an issue page for this topic.  See:
>>> >
>>> > http://ctieware.eng.monash.edu.au/twiki/bin/view/DNA/DNASoln1Issue019
>>> >
>>> > I'm also in favour of the landmark approach.
>>> >
>>> > Amongst other things, I think it integrates more easily with non-DNA
>>> > devices.  A host that comes from a non-DNA link to a DNA link gets a
>>> > positive confirmation of link change.  I don't think this is the case
>>> > with LinkID which relies on detecting change in the LinkID (which there
>>> > won't be on a non-DNA link).
>
>>
>>
>> I'd like to point out that protocol-00/protocol-01 have two Link
>> Identification mechanisms which interact.
>>
>> The draft has the prefix landmark scheme (Request in RS, Response in RA)
>> which is able to answer questions regardless of which link a prefix was
>> previously on.
>>
>> It also contains a specification of CompleteRA, which contains an
>> augmented RA (like Prefix LinkID) in even unsolicited RAs.
>> Rightly, comparisons should initially be made between CompleteRA
>> and Prefix LinkID,  rather than between Prefix LinkID and
>> Prefix Landmarks, since the augmented RA schemes have so much in common.
>>
>> I'd guess that the desirable solution for me is either:
>>
>> Prefix Landmark + CompleteRA
>>
>> Prefix Landmark + Prefix LinkID
>>
>> rather than argument for removal of prefix landmarks (which serve a
>> purpose wherever RSs are required for DNA).
>>
>> This below represents my current (personal) leanings:
>>
>> Personally, while the cost of CompleteRA is potentially higher if the
>> prefixes advertised by routers aren't the same, I still believe that it
>> has strong advantages in being able to immediately help construct a
>> complete list of prefixes on the link, which can be used in RA matching
>> if a link-hint is received again (even if the host moves to a non-DNA
>> link).
>>
>> CompleteRA and Prefix Landmarks also both work well even if they share
>> a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
>> router is able to answer questions about the prefixes in use by the
>> legacy routers (CompleteRA readvertises these in the DNAO, and a
>> Landmark query can be answered easily, regardless of the original
>> advertisor's DNA status).
>>
>> Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
>> link's identity.
>>
>> Greg

JinHyeock Choi

Dear Brett


>> I'm also in favour of the landmark approach.
>> 
>> Amongst other things, I think it integrates more easily with non-DNA
>> devices.  A host that comes from a non-DNA link to a DNA link gets a
>> positive confirmation of link change.  I don't think this is the case
>> with LinkID which relies on detecting change in the LinkID (which there
>> won't be on a non-DNA link).


You are right but I think CPL will step in such a case. I think it would 
help if we write down 'other things' to compare two in whole.  

Best Regards

JinHyeock

JinHyeock Choi

Dear Greg
 

>> I'd like to point out that protocol-00/protocol-01 have two Link
>> Identification mechanisms which interact.
>> 
>> The draft has the prefix landmark scheme (Request in RS, Response in RA)
>> which is able to answer questions regardless of which link a prefix was
>> previously on.
>> 
>> It also contains a specification of CompleteRA, which contains an
>> augmented RA (like Prefix LinkID) in even unsolicited RAs.
>> Rightly, comparisons should initially be made between CompleteRA
>> and Prefix LinkID,  rather than between Prefix LinkID and
>> Prefix Landmarks, since the augmented RA schemes have so much in common.
>> 
>> I'd guess that the desirable solution for me is either:
>> 
>> Prefix Landmark + CompleteRA
>> 
>> Prefix Landmark + Prefix LinkID
>> 
>> rather than argument for removal of prefix landmarks (which serve a
>> purpose wherever RSs are required for DNA).


I don't think the comparison is exactly right. 

Right now Linkid draft is complete by itself. It doesn't need either landmark 
or CompleteRA. Whereas Landarmk needs CompleteRA to be able to 
check for link change with unsolicted RA. 

I don't rule out the possibility of Linkid + landmark but would like to see 
the tangible benefits which can match up the added complexity to 
Linkid alone. 

I think the comparison would better be as it is. 

Linkid between Landmark/ CompleteRA


>> This below represents my current (personal) leanings:
>> 
>> Personally, while the cost of CompleteRA is potentially higher if the


>> prefixes advertised by routers aren't the same, I still believe that it
>> has strong advantages in being able to immediately help construct a
>> complete list of prefixes on the link, which can be used in RA matching
>> if a link-hint is received again (even if the host moves to a non-DNA
>> link).


As DT may knows, I worked on Comlete RA for long. But it's more
difficult to synchronize, consume more bandwidth and there is a 
possibility that it can't be made. 
 

>> CompleteRA and Prefix Landmarks also both work well even if they share
>> a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
>> router is able to answer questions about the prefixes in use by the
>> legacy routers (CompleteRA readvertises these in the DNAO, and a
>> Landmark query can be answered easily, regardless of the original
>> advertisor's DNA status).
>> 
>> Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
>> link's identity.


It can. It will simply pick the smallest prefix. 

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

JinHyeock

Dear Sathya


>> I agree with your preference: I too prefer Prefix Landmark + CompleteRA
>> , among other things, CompleteRA helps with building of the CPL if the
>> host moves out to a non-DNA link.
>> 
>> Prefix Landmark provides a way for the router to know whether the host
>> with the 'landmark question' has changed link or not and build its
>> (unicast-)RA accordingly, which I think will be very efficient in terms
>> of bandwidth utilization as 'no link change' is more likely than not. I
>> quote from "-01.txt"


Kindly see the Issue 007 of Linkid-01 draft. With Linkid prefix option 
for RS message, Linkid can achieve the same bandwidth saving. 
(But I can't be sure that it's worthwhile.)

Best Regards

JinHyeock

Sathya Narayanan

JinHyeock Choi wrote:


>> <snip>
>>
>
>>>>This below represents my current (personal) leanings:
>>>>
>>>>Personally, while the cost of CompleteRA is potentially higher if the
>>>>prefixes advertised by routers aren't the same, I still believe that it
>>>>has strong advantages in being able to immediately help construct a
>>>>complete list of prefixes on the link, which can be used in RA matching
>>>>if a link-hint is received again (even if the host moves to a non-DNA
>>>>link).
>>>>    
>>>>
>
>>
>>As DT may knows, I worked on Comlete RA for long. But it's more
>>difficult to synchronize, consume more bandwidth and there is a 
>>possibility that it can't be made. 
>>  
>>

I don't think this is accurate in comparison to synchronizing for
prefix-LinkID. Prefix LinkID requires the completeRA list to be
synchronized in each of the routers so that the least prefix can be
selected from the list as LinkID. So the synchronization/bandwidth
requirements are the same for both CompleteRA and Prefix LinkID. The
difference between LinkID and CompleteRA is only in terms of what is
included in the RA messages - i.e. the debate is only what will be the
information included in the RA message. I think it is better to include
the whole list of prefixes rather one representative - because chosing a
representative adds additional requirement of synchronization in terms
of the timing when the representative is chosen at each router.



- Sathya


>> 
>>  
>>
>
>>>>CompleteRA and Prefix Landmarks also both work well even if they share
>>>>a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
>>>>router is able to answer questions about the prefixes in use by the
>>>>legacy routers (CompleteRA readvertises these in the DNAO, and a
>>>>Landmark query can be answered easily, regardless of the original
>>>>advertisor's DNA status).
>>>>
>>>>Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
>>>>link's identity.
>>>>    
>>>>
>
>>
>>It can. It will simply pick the smallest prefix. 
>>
>>Thanks in advance for your kind consideration. 
>>
>>Best Regards
>>
>>JinHyeock

Sathya Narayanan

Dear JinHyeock -


>>Dear Sathya
>>  
>>
>
>>>>I agree with your preference: I too prefer Prefix Landmark + CompleteRA
>>>>, among other things, CompleteRA helps with building of the CPL if the
>>>>host moves out to a non-DNA link.
>>>>
>>>>Prefix Landmark provides a way for the router to know whether the host
>>>>with the 'landmark question' has changed link or not and build its
>>>>(unicast-)RA accordingly, which I think will be very efficient in terms
>>>>of bandwidth utilization as 'no link change' is more likely than not. I
>>>>quote from "-01.txt"
>>>>    
>>>>
>
>>
>>Kindly see the Issue 007 of Linkid-01 draft. With Linkid prefix option 
>>for RS message, Linkid can achieve the same bandwidth saving. 
>>(But I can't be sure that it's worthwhile.)
>>  
>>

I am surprised - this issue is basically suggesting the adoption of
prefix landmark into the prefix LinkID solution. If this change is made
to LinkID, then the second proposal becomes Prefix Landmark + Prefix
LinkID, as Greg suggested. But, your response to Greg's email seem to
suggest that you don't like that combination.

Anyhow, I think the first step is to agree which particular concepts are
worth pursuing and then we can worry about which particular solution
draft is proposing it.

If what is said in Issue 007 of Linkid-01 draft is agreed by you, I
think there is consensus to adopt the 'concept of landmark'. Whether the
'prefix-LinkID ' chosen by the routers must be used as landmark by the
hosts or whether each host choses its own landmark needs to be resolved
- I (obviously  ;-)  prefer the later.

And the second component needing consensus is, as Greg suggested,
whether to include the complete list of prefixes (CompleteRA) or a
representative for each set (LinkID). As I mentioned in the earlier
email, LinkID requires the synchronization of the complete list of
prefixes so that it can choose the least prefix - but LinkID needs
additional synchronization among the routers as to when they chose the
LinkID.

All the other components like oDAD, TSLLAO etc., AFAIK, we already have
consensus on how to address them.

- Sathya

Syam Madanapalli

Hi Greg, 

<cut>

>> 
>> I'd like to point out that protocol-00/protocol-01 have two Link
>> Identification mechanisms which interact.
>> 
>> The draft has the prefix landmark scheme (Request in RS, Response in RA)
>> which is able to answer questions regardless of which link a prefix was
>> previously on.
>> 
>> It also contains a specification of CompleteRA, which contains an
>> augmented RA (like Prefix LinkID) in even unsolicited RAs.
>> Rightly, comparisons should initially be made between CompleteRA
>> and Prefix LinkID,  rather than between Prefix LinkID and
>> Prefix Landmarks, since the augmented RA schemes have so much in common.
>> 
>> I'd guess that the desirable solution for me is either:
>> 
>> Prefix Landmark + CompleteRA
>> 
>> Prefix Landmark + Prefix LinkID
>> 
>> rather than argument for removal of prefix landmarks (which serve a
>> purpose wherever RSs are required for DNA).


Linkid scheme also works with RS as well as without RS if the node
was on a DNA capable link previously. Definitely I see the advantage
of Landmark if the node is moving from non-DNA link.


>> 
>> This below represents my current (personal) leanings:
>> 
>> Personally, while the cost of CompleteRA is potentially higher if the
>> prefixes advertised by routers aren't the same, I still believe that it
>> has strong advantages in being able to immediately help construct a
>> complete list of prefixes on the link, which can be used in RA matching
>> if a link-hint is received again (even if the host moves to a non-DNA
>> link).


As a host can build the complete prefix list on its own without explicit 
support for complete RA, we may need to carefully evaluate it's benefits 
against the bandwidth consumption on the link as well as synchronization
complexity. A host may need to be at the link for less than a minute to 
acquire the complete prefix list, the chances of a node moving away from
the link within few seconds may be less.



>> 
>> CompleteRA and Prefix Landmarks also both work well even if they share
>> a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
>> router is able to answer questions about the prefixes in use by the
>> legacy routers (CompleteRA readvertises these in the DNAO, and a
>> Landmark query can be answered easily, regardless of the original
>> advertisor's DNA status).


Did you see any problems with linkid scheme in case non-DNA router
present on the link? I think Linkid scheme also works with non-DNA routers.


>> 
>> Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
>> link's identity.


As we have implemented the linkid scheme, we did not find any such problems.
For landmark also all the Routers need know about all other prefixes, otherwie
the host may get conflict answers.


>> 
>> Greg
>> 


And I think it is worth to provide the complete comparison list
between Landmark and Linkid Schemes, so that the non DT members can
uderstand and will be able to participate in the selection process for
the link identification method. I hope this is not a
burden for the DT as they already know how each schecme works  :) 

Thank you,
Syam

Syam Madanapalli

Hi Sathya,


<cut>

>> As I mentioned in the earlier
>> email, LinkID requires the synchronization of the complete list of
>> prefixes so that it can choose the least prefix - but LinkID needs
>> additional synchronization among the routers as to when they chose the
>> LinkID.
>> 


To the extent of my knowledge even Landmark method requires the
synchronization among routers, otherwise one router may say 'no'
and other may say 'yes' for the landmark question.

-Syam

Sathya Narayanan

Syam -


>>Hi Sathya,
>>
>><cut>
>>
>
>>>>As I mentioned in the earlier
>>>>email, LinkID requires the synchronization of the complete list of
>>>>prefixes so that it can choose the least prefix - but LinkID needs
>>>>additional synchronization among the routers as to when they chose the
>>>>LinkID.
>>>>
>>>>    
>>>>
>
>>To the extent of my knowledge even Landmark method requires the
>>synchronization among routers, otherwise one router may say 'no'
>>and other may say 'yes' for the landmark question.
>>  
>>

Yes - I am sorry I wasn't clear - LinkID, CompleteRA and Landmark
require the synchronization of the complete list of prefixes by the
routers - but LinkID MAY need additional synchronization in terms of the
timing when the LinkID is chosen at each routers. What I mean is that, a
clear indication that the complete list is collected is needed in the
LinkID case before the routers can chose the LinkID, while in Landmark
and CompleteRA -  'as far as I know' these are the prefixes will work
reasonably well at each router, even when the complete list is a little
bit off. Some hosts may get conflicting answers with Landmark, but if
two routers chose different LinkIDs all the hosts in the link will
receive RA messages with two different LinkIDs and keep changing
configuration until the synchronization is complete - i.e. the
synchronization requirement is stronger in the case of LinkID, IMHO.

- Sathya

James Kempf

And I think it is worth to provide the complete comparison list
between Landmark and Linkid Schemes, so that the non DT members can
uderstand and will be able to participate in the selection process for
the link identification method. I hope this is not a
burden for the DT as they already know how each schecme works  :) 


jak>> I've got no objection if someone wants to do this, but I really don't
think it is necessary. People just need to read the drafts and decide for
themselves which one they like.

            jak

Daniel Park

And I think it is worth to provide the complete comparison list
between Landmark and Linkid Schemes, so that the non DT members can
uderstand and will be able to participate in the selection process for
the link identification method. I hope this is not a
burden for the DT as they already know how each schecme works :)


jak>> I've got no objection if someone wants to do this, but I really don't
think it is necessary. People just need to read the drafts and decide for
themselves which one they like.

 

Daniel> Strongly disagreed, in my understanding, DNA will decide

which one  would be more valuable method and it will be accepted

as WG item, then another one will be dead.  (I don't think we need

both) Rather just reading a draft, specific comparison and evaluation

would be more good effort on adopting any protocols within each WG

if available.  So it is definitely necessary at this stage.

 

 

Regards

 

Daniel (Soohong Daniel Park)

Mobile Platform Laboratory. SAMSUNG Electronics

Greg Daley

Hi JinHyeock,


JinHyeock Choi wrote:
[cut]

>>
>> I'd guess that the desirable solution for me is either:
>>
>> Prefix Landmark + CompleteRA
>>
>> Prefix Landmark + Prefix LinkID
>>
>> rather than argument for removal of prefix landmarks (which serve a
>> purpose wherever RSs are required for DNA).
>
>
>
> I don't think the comparison is exactly right.
> Right now Linkid draft is complete by itself. It doesn't need either landmark or CompleteRA. Whereas Landarmk needs CompleteRA to be able to check for link change with unsolicted RA.
> I don't rule out the possibility of Linkid + landmark but would like to see the tangible benefits which can match up the added complexity to Linkid alone.
> I think the comparison would better be as it is.
> Linkid between Landmark/ CompleteRA


OK.  That's a fair opinion.


[cut]

>
>
> As DT may knows, I worked on Comlete RA for long. But it's more
> difficult to synchronize, consume more bandwidth and there is a possibility that it can't be made. 



CompleteRA isn't difficult to synchronize at all.

All routers immediately update their DNAPrefixList with a
prefix as soon as it is seen.

The next RAs all contain the prefix.

The prefix lifetime timers (and last seen timers) count down in
real-time on the routers (exactly like CPL).

The (re-)advertised prefixes are only advertised so long as their
original prefixes are valid.   This is available in the distributed
source code.

>> CompleteRA and Prefix Landmarks also both work well even if they share
>> a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
>> router is able to answer questions about the prefixes in use by the
>> legacy routers (CompleteRA readvertises these in the DNAO, and a
>> Landmark query can be answered easily, regardless of the original
>> advertisor's DNA status).
>>
>> Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
>> link's identity.
>
>
>
> It can. It will simply pick the smallest prefix. 


Except if the non-DNA routers do not have the smallest prefix
configured (which was my point).

The RAs received from non-DNA routers aren't guaranteed to have
any prefixes in common with the DNA (LinkID) routers.
CompleteRA has this at potentially greater prefix advertisement cost.

Greg 

Greg Daley

Hi Syam,

Once again, I'm expressing personal opionions only.

Syam Madanapalli wrote:
[cut]

>
>
> Linkid scheme also works with RS as well as without RS if the node
> was on a DNA capable link previously. Definitely I see the advantage
> of Landmark if the node is moving from non-DNA link.


The same can be said of CompleteRA (which has [provably] exactly
the same properties as LinkID of being able to detect link change
with DNA routers).

The omission of RS only works in constrained environments
where one already has the right link information (FMIPv6
predictive handover), or the Network infrastructure
can be known beforehand to provide RA information (conceivably
FastRD in a constrained environment).

Neither of these scenarios is under consideration for the
main DNA solution (FMIPv6 because it works without RA, FastRD
because it isn't generally applicable), which needs to work
correctly and quickly in generic IPv6 environments.

So I don't think we can champion one particular technology based
on the fact that it works (slowly in general) with unsolicited RA.

>> This below represents my current (personal) leanings:
>>
>> Personally, while the cost of CompleteRA is potentially higher if the
>> prefixes advertised by routers aren't the same, I still believe that it
>> has strong advantages in being able to immediately help construct a
>> complete list of prefixes on the link, which can be used in RA matching
>> if a link-hint is received again (even if the host moves to a non-DNA
>> link).
>
>
>
> As a host can build the complete prefix list on its own without explicit support for complete RA, we may need to carefully evaluate it's benefits against the bandwidth consumption on the link as well as synchronization
> complexity. A host may need to be at the link for less than a minute to acquire the complete prefix list, the chances of a node moving away from
> the link within few seconds may be less.


But we already have CPL, and we know what its limitations are.

The time to build sufficient information to Detect change is the
critical issue:  Otherwise we wouldn't have any link
identification mechanism in the DNA solution.   CPL is good
enough if you've got the time and energy to probe for RAs.

If we want to support (potentially) rapidly changing attachment,
the state on the host needs to be as up to date as possible, whether
using a landmark, a link-id or CompleteRA.

CompleteRA has the potential to create a CPL immediately, which
is better for the "movement to non-DNA" link case.


>> CompleteRA and Prefix Landmarks also both work well even if they share
>> a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
>> router is able to answer questions about the prefixes in use by the
>> legacy routers (CompleteRA readvertises these in the DNAO, and a
>> Landmark query can be answered easily, regardless of the original
>> advertisor's DNA status).
>
>
>
> Did you see any problems with linkid scheme in case non-DNA router
> present on the link? I think Linkid scheme also works with non-DNA routers.



Except if the non-DNA routers don't happen to advertise the lowest
numeric prefix...


>> Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
>> link's identity.
>
>
>
> As we have implemented the linkid scheme, we did not find any such problems.
> For landmark also all the Routers need know about all other prefixes, otherwie
> the host may get conflict answers.


It doesn't need to know all the prefixes (as described in a previous
thread).  It needs to know what prefixes it definitely has locally.

In that case, it can answer "Yes" immediately.  Answering "No" takes
definitive knowledge and synchronization.   A prefix which answers
"Yes" will supercede a "No" if it is received first.

The chance that a router will answer "No" when another answers "Yes"
is the chance that a prefix's advertisement has not been received
on the "No" router before the RS with a landmark query is sent.

This is bounded by the delay of the original RA to cross the network,
and any robustness factors affecting delivery between pairs of routers.

As the solicitor would have to have received the landmark prefix in
an RA before it can send the landmark RS, the chances are really
quite small that any remaining router would be not be updated
before answering the landmark query.

Greg

Syam Madanapalli

Hi Sathya,

>> <cut>
>>
>>> As I mentioned in the earlier
>>> email, LinkID requires the synchronization of the complete list of
>>> prefixes so that it can choose the least prefix - but LinkID needs
>>> additional synchronization among the routers as to when they chose the
>>> LinkID.
>>>
>>>
>>>
>> To the extent of my knowledge even Landmark method requires the
>> synchronization among routers, otherwise one router may say 'no'
>> and other may say 'yes' for the landmark question.
>>
>>
> Yes - I am sorry I wasn't clear - LinkID, CompleteRA and Landmark
> require the synchronization of the complete list of prefixes by the
> routers - but LinkID MAY need additional synchronization in terms of the
> timing when the LinkID is chosen at each routers. What I mean is that, a
> clear indication that the complete list is collected is needed in the
> LinkID case before the routers can chose the LinkID, while in Landmark
> and CompleteRA -  'as far as I know' these are the prefixes will work
> reasonably well at each router, even when the complete list is a little
> bit off. Some hosts may get conflicting answers with Landmark, but if
> two routers chose different LinkIDs all the hosts in the link will
> receive RA messages with two different LinkIDs and keep changing
> configuration until the synchronization is complete - i.e. the
> synchronization requirement is stronger in the case of LinkID, IMHO.


This is incorrect. The linkid works perfectly with the scenario you described.
In the linkid, the host maintains the list of previous linkids which will be used
to check if any of one of these was a linkid on the link. So change in linkid
does not mean that the host requires reconfiguration.

My current understanding is that the landmark need to synchronize all the
time.

Also linkid does not really require the synchronization all the time if router
agree to have same linkid as long as possible. e.g. Router can pick one
with longer valid life time and can continue to have the same linkid till the
life time expires. If the prefix lifetime is not renewed then router can start
synchronization to select new linkid.

However, I am not saying the linkid is the only perfect solution, rather we
may need to define criteria for the evaluation and then compare the two
schemes against the defined criteria and we need to pick the best solution.

- Syam 

Subba Reddy

Hi Greg,

<cut>

>>>> >>CompleteRA and Prefix Landmarks also both work well even if they share
>>>> >>a link with RFC 2461 (non-DNA) routers.  In either case, the DNA
>>>> >>router is able to answer questions about the prefixes in use by the
>>>> >>legacy routers (CompleteRA readvertises these in the DNAO, and a
>>>> >>Landmark query can be answered easily, regardless of the original
>>>> >>advertisor's DNA status).
>>>> >>
>>>> >>Prefix LinkIDs cannot agree easily with existing non-DNA routers on the
>>>> >>link's identity.
>>
>>> >
>>> >
>>> > It can. It will simply pick the smallest prefix.
>
>>
>> Except if the non-DNA routers do not have the smallest prefix
>> configured (which was my point).


I think, this is not a problem in linkid scheme. Because hosts will not
consider the RAs
sent by non-DNA routers in finding the link change (if they are using linkid
scheme).
Such RAs will not contain linkid option.


>>
>> The RAs received from non-DNA routers aren't guaranteed to have
>> any prefixes in common with the DNA (LinkID) routers.
>> CompleteRA has this at potentially greater prefix advertisement cost.
>>
>> Greg
>>
>>


Thanks & Regards,
Subba Reddy

Subba Reddy

Hi Greg,


>> Subba Reddy wrote:
>> [cut]
>
>>> >
>>> > I think, this is not a problem in linkid scheme. Because hosts will not
>>> > consider the RAs
>>> > sent by non-DNA routers in finding the link change (if they are using

linkid

>>> > scheme).
>>> > Such RAs will not contain linkid option.
>
>>
>> If the first RA received after link up is a non DNA router,
>> false change detection will occur.
>>


Such RA will not contain linkid option. So host will not make any decision
based on that RA (in linkid scheme).


>> Greg
>>
>>


Thanks & Regards,
Subba Reddy

Greg Daley

Hi Subba,

Subba Reddy wrote:
[cut]

>
> I think, this is not a problem in linkid scheme. Because hosts will not
> consider the RAs
> sent by non-DNA routers in finding the link change (if they are using linkid
> scheme).
> Such RAs will not contain linkid option.


If the first RA received after link up is a non DNA router,
false change detection will occur.

Greg 

Greg Daley

Hi Subba,

These are some fairly fast exchanges, but may be getting somewhere...
Please excuse my terseness.

Subba Reddy wrote:

> Hi Greg,
>
>
>> Subba Reddy wrote:
>> [cut]
>>
>>> I think, this is not a problem in linkid scheme. Because hosts will not
>>> consider the RAs
>>> sent by non-DNA routers in finding the link change (if they are using
>
>
> linkid
>
>>> scheme).
>>> Such RAs will not contain linkid option.
>>
>>
>> If the first RA received after link up is a non DNA router,
>> false change detection will occur.
>>
>
>
> Such RA will not contain linkid option. So host will not make any decision
> based on that RA (in linkid scheme).


So how does LinkID work when transiting to networks with non-DNA
routers?  Does it rely on building CPL in the period where
the host remained on the previous link?

Greg 

Subba Reddy

Hi Greg,


>>
>> These are some fairly fast exchanges, but may be getting somewhere...
>> Please excuse my terseness.


I can understand. No problem.


>>
>> Subba Reddy wrote:
>
>>> > Hi Greg,
>>> >
>>> >
>>
>>>> >>Subba Reddy wrote:
>>>> >>[cut]
>>>> >>
>>>
>>>>> >>>I think, this is not a problem in linkid scheme. Because hosts will not
>>>>> >>>consider the RAs
>>>>> >>>sent by non-DNA routers in finding the link change (if they are using
>>
>>> >
>>> > linkid
>>> >
>>
>>>>> >>>scheme).
>>>>> >>>Such RAs will not contain linkid option.
>>>
>>>> >>
>>>> >>If the first RA received after link up is a non DNA router,
>>>> >>false change detection will occur.
>>>> >>
>>
>>> >
>>> >
>>> > Such RA will not contain linkid option. So host will not make any

decision

>>> > based on that RA (in linkid scheme).
>
>>
>> So how does LinkID work when transiting to networks with non-DNA
>> routers?  Does it rely on building CPL in the period where
>> the host remained on the previous link?
>>


Yes.

Section 4.2 of the linkid draft (version 00/01) says

"...
   After one RS/ RA exchange, i.e. 4 secs after RS transmission, if no
   RA with a linkid prefix arrives, the host assumes it is at a non DNA
   link and falls back on CPL [9].
..."



>> Greg
>>


Thanks & Regards,
Subba Reddy

Syam Madanapelli


----- Original Message ----- From: "Greg Daley" <greg.daley@eng.monash.edu.au>
To: "Subba Reddy" <subbareddy@samsung.com>
Cc: "JinHyeock Choi" <jinchoe@gmail.com>; "Brett Pentland" <brett.pentland@eng.monash.edu.au>; "James Kempf" <Kempf@docomolabs-usa.com>; "Dna" <dna@eng.monash.edu.au>
Sent: Wednesday, July 20, 2005 10:24 AM
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. Landmark Prefix


> Hi Subba,
>
> These are some fairly fast exchanges, but may be getting somewhere...
> Please excuse my terseness.
>
> Subba Reddy wrote:
>
>> Hi Greg,
>>
>>
>>> Subba Reddy wrote:
>>> [cut]
>>>
>>>> I think, this is not a problem in linkid scheme. Because hosts will not
>>>> consider the RAs
>>>> sent by non-DNA routers in finding the link change (if they are using
>>
>>
>> linkid
>>
>>>> scheme).
>>>> Such RAs will not contain linkid option.
>>>
>>>
>>> If the first RA received after link up is a non DNA router,
>>> false change detection will occur.
>>>
>>
>>
>> Such RA will not contain linkid option. So host will not make any decision
>> based on that RA (in linkid scheme).
>
>
> So how does LinkID work when transiting to networks with non-DNA
> routers?  Does it rely on building CPL in the period where
> the host remained on the previous link?


Yes, it has to fall back to CPL if it is a non-DNA link without
any DNA routers. I think this is also true with the Landmark
approach.

>
> Greg

Greg Daley

Hi Subba,

Subba Reddy wrote:
[cut]

>>
>> So how does LinkID work when transiting to networks with non-DNA
>> routers?  Does it rely on building CPL in the period where
>> the host remained on the previous link?
>>
>
>
> Yes.
>
> Section 4.2 of the linkid draft (version 00/01) says
>
> "...
>    After one RS/ RA exchange, i.e. 4 secs after RS transmission, if no
>    RA with a linkid prefix arrives, the host assumes it is at a non DNA
>    link and falls back on CPL [9].
> ..."
>
Thanks,

Greg 

Greg Daley

Hi Syam,

Syam Madanapalli wrote:
[cut]

>
>
> Yes, it has to fall back to CPL if it is a non-DNA link without
> any DNA routers. I think this is also true with the Landmark
> approach.


But only if the original landmark system didn't include a CompleteRA,
which was the point of my comparison.

(I've been mainly been comparing CompleteRA and LinkID because
of their similar properties).

Greg

Sathya Narayanan

Hi Syam -

Even though I still feel that the synchronization requirement for the
LinkID scheme is stronger, I will concede that the difference is not
very high. So, in conclusion, the synchronization requirement and
complexity for Landmark, CompleteRA and LinkID are the same - all three
of them require that all the routers on the link know about all the
prefixes on the link within a reasonable time - the difference is only
in the content of the RS/RA messages. Do you agree?

- Sathya


>> Hi Sathya,
>>
>
>>>>>> <cut>
>>>>>>
>>>
>>>>>>>> As I mentioned in the earlier
>>>>>>>> email, LinkID requires the synchronization of the complete list of
>>>>>>>> prefixes so that it can choose the least prefix - but LinkID needs
>>>>>>>> additional synchronization among the routers as to when they chose the
>>>>>>>> LinkID.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>
>>>>>> To the extent of my knowledge even Landmark method requires the
>>>>>> synchronization among routers, otherwise one router may say 'no'
>>>>>> and other may say 'yes' for the landmark question.
>>>>>>
>>>>>>
>>
>>>> Yes - I am sorry I wasn't clear - LinkID, CompleteRA and Landmark
>>>> require the synchronization of the complete list of prefixes by the
>>>> routers - but LinkID MAY need additional synchronization in terms of the
>>>> timing when the LinkID is chosen at each routers. What I mean is that, a
>>>> clear indication that the complete list is collected is needed in the
>>>> LinkID case before the routers can chose the LinkID, while in Landmark
>>>> and CompleteRA -  'as far as I know' these are the prefixes will work
>>>> reasonably well at each router, even when the complete list is a little
>>>> bit off. Some hosts may get conflicting answers with Landmark, but if
>>>> two routers chose different LinkIDs all the hosts in the link will
>>>> receive RA messages with two different LinkIDs and keep changing
>>>> configuration until the synchronization is complete - i.e. the
>>>> synchronization requirement is stronger in the case of LinkID, IMHO.
>
>>
>>
>> This is incorrect. The linkid works perfectly with the scenario you
>> described.
>> In the linkid, the host maintains the list of previous linkids which
>> will be used
>> to check if any of one of these was a linkid on the link. So change in
>> linkid
>> does not mean that the host requires reconfiguration.
>>
>> My current understanding is that the landmark need to synchronize all the
>> time.
>>
>> Also linkid does not really require the synchronization all the time
>> if router
>> agree to have same linkid as long as possible. e.g. Router can pick one
>> with longer valid life time and can continue to have the same linkid
>> till the
>> life time expires. If the prefix lifetime is not renewed then router
>> can start
>> synchronization to select new linkid.
>>
>> However, I am not saying the linkid is the only perfect solution,
>> rather we
>> may need to define criteria for the evaluation and then compare the two
>> schemes against the defined criteria and we need to pick the best
>> solution.
>>
>> - Syam
>>

JinHyeock Choi

Sathya

Sorry for a late reply. After FRD completeion, I am still busy 
catching up baglog mails. 


>> I don't think this is accurate in comparison to synchronizing for
>> prefix-LinkID. Prefix LinkID requires the completeRA list to be
>> synchronized in each of the routers so that the least prefix can be
>> selected from the list as LinkID. So the synchronization/bandwidth
>> requirements are the same for both CompleteRA and Prefix LinkID. 


I may not be clear. 

The difficulty in synchronization lies in when a prefix is added or 
removed. There is a scheme for graceful linkid change in Linkid but, 
correct me wrong, nothing like that in Landmark/ CompleteRA. 

I remember that DT discussed much about the flapping 
probmem in CompleteRA synchronization difficulty (w.r.t the prefix 
number) in 'CompleteRA Polished' thread. 

Best Regards

JinHyeock

JinHyeock Choi

Sathya


>>> >Kindly see the Issue 007 of Linkid-01 draft. With Linkid prefix option 
>>> >for RS message, Linkid can achieve the same bandwidth saving. 
>>> >(But I can't be sure that it's worthwhile.)
>>> >  
>
>> I am surprised - this issue is basically suggesting the adoption of
>> prefix landmark into the prefix LinkID solution. If this change is made
>> to LinkID, then the second proposal becomes Prefix Landmark + Prefix
>> LinkID, as Greg suggested. But, your response to Greg's email seem to
>> suggest that you don't like that combination.


My mail doesn't seem to be as clear as I had expected. I ask your 
kind understanding.  

I introduced Linkid prefix option only to reduce bandwidth. The answer 
will be always a RA with LinkID and Linkid + Landmark was not intended. 

I'd like to say Linkid is a complete solution by itself and can work without 
Landmark. If LinkID + Landmark brings forth benefits exceeding the added 
complexity, it's ok for me but such a benefits are not clear to me yet. 

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

JinHyeock Choi

I'd like to clarify the previous mail. 

"The answer will be always a RA with LinkID" 

means

"Upon solicited, routers always reply an RA with LinkID 
and don't use Yes/No indicaiton." 

Best Regards

JinHyeock

Greg Daley

Hi JinHyeock,

JinHyeock Choi wrote:

> Sathya
>
> Sorry for a late reply. After FRD completeion, I am still busy catching up baglog mails.
>
>> I don't think this is accurate in comparison to synchronizing for
>> prefix-LinkID. Prefix LinkID requires the completeRA list to be
>> synchronized in each of the routers so that the least prefix can be
>> selected from the list as LinkID. So the synchronization/bandwidth
>> requirements are the same for both CompleteRA and Prefix LinkID. 
>
>
>
> I may not be clear.
> The difficulty in synchronization lies in when a prefix is added or removed. There is a scheme for graceful linkid change in Linkid but, correct me wrong, nothing like that in Landmark/ CompleteRA. 


I think that there's no scheme defined in Landmark/CompleteRA,
but (in my guess) the choice of the scheme itself will significantly
affect whether particular "config" change management (rather than link
change management) schemes are needed.

> I remember that DT discussed much about the flapping probmem in CompleteRA synchronization difficulty (w.r.t the prefix number) in 'CompleteRA Polished' thread. 


Thanks for the pointer to this thread.

I think there are two or three related threads:

Complete RA Polished
http://www.ctie.monash.edu.au/warchive/dna-dt/2005-03/msg00157.html

Complete RA Re-polished
http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/msg00009.html

LinkID Polished
http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/msg00097.html
and
http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/threads.html


It's good to know that there's been so much work on this (and
that everyone can read it).

There were a lot of differences between individual schemes
as portrayed before (in April) and now though.  This may
affect the way prefix addition or subtraction works.

Given the individual current schemes though, let's try to characterise
the effects of addition or substraction of prefixes on each protocol
as configured today.

Does that sound reasonable?

I guess that if the state + processing requirements for
Landmark/CompleteRA and LinkID are comparable (which I've
indicated may be the case), implementation experiences are
qualitative, and in the normal case
(and non-DNA case) all schemes act sensibly, the
main issues will probably be:

* Synchronization/How the schemes react to change of prefixes.

* Packet Sizes

Does this sound like the right criteria to compare
the schemes on?

There may not be a clear winner with any of these, and
it may be that the WG just chooses a particular
scheme it likes.

The comparison is likely to help with forming that opinion,
and may actually highlight a winner.

Should we go ahead?

It may mean some in-depth description of how the schemes
currently handle change (which may take some discussion).

I think that we need to compare packet sizes for:

RS/RA exchange for each scheme (or set of schemes) as described
      in current drafts.

Where:

a) 1 prefix is shared by all routers

b) 1 distinct prefix is configured on each router.

c) 1 prefix is shared by all routers and one additional prefix is
               advertised by one router (big or small prefix).

We should probably do this for 1,2 routers (though the third
test may be a bit simple with 1 router - one router 2 prefixes).

We should sum the sizes of the response RAs for all routers.

Does this sound OK with people?

Greg 

Brett Pentland

> I guess that if the state + processing requirements for
> Landmark/CompleteRA and LinkID are comparable (which I've
> indicated may be the case), implementation experiences are
> qualitative, and in the normal case
> (and non-DNA case) all schemes act sensibly, the
> main issues will probably be:
>
> * Synchronization/How the schemes react to change of prefixes.
>
> * Packet Sizes
>
> Does this sound like the right criteria to compare
> the schemes on?


It would be good to also consider how the schemes interact with
non-DNA nodes.

Brett. 

Sathya Narayanan

JinHyeock -


>>I'd like to clarify the previous mail. 
>>
>>"The answer will be always a RA with LinkID" 
>>
>>means
>>
>>"Upon solicited, routers always reply an RA with LinkID 
>>and don't use Yes/No indicaiton." 
>>  
>>

This is just an issue of syntax - in your proposal if the RS contains
LinkID_1 and if the RA comes back with LinkID_1 it means 'Yes' and if
the RA comes back with LinkID_X (X != 1) then it means 'No'.
Conceptually the main design issue behing the idea of 'Landmark', is to
include a question in the RS and get a response for it in the RA.
Obviously, the two protocols will use different syntax to achieve this -
but if you agree to include some kinda question in the RS by including
the LinkID, then we are in agreement  ;-)  as to the choice of including a
'Landmark like' component. We can move on to the specific
syntax/mechanism by which we acheive it - where we do disagree, as of now.

Sathya

Syam Madanapalli

Hi Sathya,


On 7/21/05, Sathya Narayanan <sathya@research.panasonic.com> wrote:

>> JinHyeock -
>> 
>
>>> >I'd like to clarify the previous mail.
>>> >
>>> >"The answer will be always a RA with LinkID"
>>> >
>>> >means
>>> >
>>> >"Upon solicited, routers always reply an RA with LinkID
>>> >and don't use Yes/No indicaiton."
>>> >
>>> >
>
>> This is just an issue of syntax - in your proposal if the RS contains
>> LinkID_1 and if the RA comes back with LinkID_1 it means 'Yes' and if
>> the RA comes back with LinkID_X (X != 1) then it means 'No'.
>> Conceptually the main design issue behing the idea of 'Landmark', is to
>> include a question in the RS and get a response for it in the RA.
>> Obviously, the two protocols will use different syntax to achieve this -
>> but if you agree to include some kinda question in the RS by including
>> the LinkID, then we are in agreement  ;-)  as to the choice of including a
>> 'Landmark like' component. We can move on to the specific
>> syntax/mechanism by which we acheive it - where we do disagree, as of now.
>> 
>> Sathya
>> 



The difference MAY be more than what you have mentioned.
MN sends the linkid in RS not any prefix (which is the case in
Landmark approach), as the routers treat the (old) linkid prefixes 
differently from the normal prefixes for graceful change in linkid.
Please see the section 3.5  Graceful linkid prefix change.
So the routers can give the correct answer compared to Landmark
where there is a posibility of conflicting answers. However the linkid
approach does not carry yes/no bit, instead hosts make decision
based on the linkid carried in RA.

-Syam

Greg Daley

Hi Brett,

Brett Pentland wrote:

>> I guess that if the state + processing requirements for
>> Landmark/CompleteRA and LinkID are comparable (which I've
>> indicated may be the case), implementation experiences are
>> qualitative, and in the normal case
>> (and non-DNA case) all schemes act sensibly, the
>> main issues will probably be:
>>
>> * Synchronization/How the schemes react to change of prefixes.
>>
>> * Packet Sizes
>>
>> Does this sound like the right criteria to compare
>> the schemes on?
>
>
>
> It would be good to also consider how the schemes interact with
> non-DNA nodes.


OK,

Greg 

Greg Daley

Hi Syam,

Syam Madanapalli wrote:
[cut]

>
>
>
> The difference MAY be more than what you have mentioned.
> MN sends the linkid in RS not any prefix (which is the case in
> Landmark approach), as the routers treat the (old) linkid prefixes differently from the normal prefixes for graceful change in linkid.
> Please see the section 3.5  Graceful linkid prefix change.
> So the routers can give the correct answer compared to Landmark
> where there is a posibility of conflicting answers. However the linkid
> approach does not carry yes/no bit, instead hosts make decision
> based on the linkid carried in RA.


Careful choice of the landmark prefix will avoid problems like this
in most cases.

For example, using a "recently seen" landmark prefix which is known
to be Preferred will limit the chance that the prefix is no longer
known on-link (due to reconfiguration).

For intermittently connected hosts, the choice of landmark may be
poor, but then again, so would that host's knowledge of valid
Prefix LinkIDs.

So I think that it's possible to get around this potential difference
with a line or two of text.

Greg. 

JinHyeock Choi

Dear Greg

Kindly understand my belated and un-chronological reply.


>> CompleteRA isn't difficult to synchronize at all.
>> 
>> All routers immediately update their DNAPrefixList with a
>> prefix as soon as it is seen.
>> 
>> The next RAs all contain the prefix.
>> 
>> The prefix lifetime timers (and last seen timers) count down in
>> real-time on the routers (exactly like CPL).
>> 
>> The (re-)advertised prefixes are only advertised so long as their
>> original prefixes are valid.   This is available in the distributed
>> source code.


I assume the above doesn't deal with the case of prefix addition or
removal in which, I think, the real difficulty of synchronization lies. 


>>> > It can. It will simply pick the smallest prefix.
>
>> 
>> Except if the non-DNA routers do not have the smallest prefix
>> configured (which was my point).


I have difficulty understanding your concern.  


>> The RAs received from non-DNA routers aren't guaranteed to have
>> any prefixes in common with the DNA (LinkID) routers.


Linkid host doesn't make a decision based on RA without linkid prefix. 

Best Regards

JinHyeock

JinHyeock Choi

Greg


>>> > Linkid scheme also works with RS as well as without RS if the node
>>> > was on a DNA capable link previously. Definitely I see the advantage
>>> > of Landmark if the node is moving from non-DNA link.
>
>> 
>> The same can be said of CompleteRA (which has [provably] exactly
>> the same properties as LinkID of being able to detect link change
>> with DNA routers).
>>
>> The omission of RS only works in constrained environments
>> where one already has the right link information (FMIPv6
>> predictive handover), or the Network infrastructure
>> can be known beforehand to provide RA information (conceivably
>> FastRD in a constrained environment).


I don't think this is correct. 

For example, FRD works with current 2461 standard. Upon network 
attachment, a host will perform random delay before sending RS 
(average 500ms). During which, the host will receive an RA optimized 
for DNA to complete DNA. 

Also we can't say FMIPv6 and FRD are the only ways to perform 
DNA without RS. There is a possibility of other schemes.  


>> Neither of these scenarios is under consideration for the
>> main DNA solution (FMIPv6 because it works without RA, FastRD
>> because it isn't generally applicable), 


As of my memory, WG didn't made such a decision. 

Also I don't think that the above description is exactly correct. I talked 
with mobile/cellular operators and in such a environment, FRD is generally 
very well applicable. 


>> So I don't think we can champion one particular technology based
>> on the fact that it works (slowly in general) with unsolicited RA.


Disagree. This may be a serious concern for moible/ceullar operators.

DNA is rather about optimization, quickly checking for link change to support 
seamless handoff. So I think main (at least substantial part of) customers for 
DNA will be mobile operators

It's my opinion that if one scheme can perform DNA without RS involvement, 
that's the pro for the scheme we need to take into consideration.


>>> > As a host can build the complete prefix list on its own without explicit
>>> > support for complete RA, we may need to carefully evaluate it's benefits
>>> > against the bandwidth consumption on the link as well as synchronization
>>> > complexity. A host may need to be at the link for less than a minute to
>>> > acquire the complete prefix list, the chances of a node moving away from
>>> > the link within few seconds may be less.
>
>> 
>> But we already have CPL, and we know what its limitations are.
>> 
>> The time to build sufficient information to Detect change is the
>> critical issue:  Otherwise we wouldn't have any link
>> identification mechanism in the DNA solution.   CPL is good
>> enough if you've got the time and energy to probe for RAs.
>>
>> If we want to support (potentially) rapidly changing attachment,
>> the state on the host needs to be as up to date as possible, whether
>> using a landmark, a link-id or CompleteRA.


According to the current CPL recommendation, it will take 4 secs for
a host to generate the complete prefix list. I think it's rather an 
exceptional case for a host to change attachment within 4 secs 
after network attachment.  


>> CompleteRA has the potential to create a CPL immediately, which
>> is better for the "movement to non-DNA" link case.


I may add "with added synchronization cost".  


>>> > As we have implemented the linkid scheme, we did not find any such problems.
>>> > For landmark also all the Routers need know about all other prefixes, otherwie
>>> > the host may get conflict answers.
>
>> 
>> It doesn't need to know all the prefixes (as described in a previous
>> thread).  It needs to know what prefixes it definitely has locally.
>> 
>> In that case, it can answer "Yes" immediately.  Answering "No" takes
>> definitive knowledge and synchronization.   


Answering "Yes" also takes definite knowledge and synchronization. 

Allow me an example. Assume a link with two routers R1 and R2. 
R1 advertises Prefix1 and R2 advertise Prefix2 and Prefix3. 
R1 and R2 gathers the prefixes to make the complete prefix list
{Prefix1, Prefix2, Prefix3}.

Then R2 removes Prefix3 but the RA advertising the removal 
was lost and R1 doesn't receive it. So afterwards, if a (dormant) 
host send an RS with Prefix3 to R1, it will falsely answer "YES", 
i.e. Prefix3 is in this link. 

Am I missing something? 


>> A prefix which answers
>> "Yes" will supercede a "No" if it is received first.


I guess the same applies for "NO". 

"NO" will supercede a "YES", if it is received first, right? 
 

>> The chance that a router will answer "No" when another answers "Yes"
>> is the chance that a prefix's advertisement has not been received
>> on the "No" router before the RS with a landmark query is sent.
>>
>> This is bounded by the delay of the original RA to cross the network,
>> and any robustness factors affecting delivery between pairs of routers.
>> 
>> As the solicitor would have to have received the landmark prefix in
>> an RA before it can send the landmark RS, the chances are really
>> quite small that any remaining router would be not be updated
>> before answering the landmark query.


In the example I present the above, "NO" is the correct one and
doesn't result from "that a prefix's advertisement has not been received
on the "No" router before the RS with a landmark query is sent."

Correct me wrong but when I looked through Landmark/ CompleteRA 
last time, I don't see any mechanism to deal with the case two routers
give conflicting answers, one yes and the other no. Such a case can 
arise from a lack of synchronization. 

Best Regards

JinHyeock

Greg Daley

Hi JinHyeock,

JinHyeock Choi wrote:

> Dear Greg
>
> Kindly understand my belated and un-chronological reply.
>
>
>> CompleteRA isn't difficult to synchronize at all.
>>
>> All routers immediately update their DNAPrefixList with a
>> prefix as soon as it is seen.
>>
>> The next RAs all contain the prefix.
>>
>> The prefix lifetime timers (and last seen timers) count down in
>> real-time on the routers (exactly like CPL).
>>
>> The (re-)advertised prefixes are only advertised so long as their
>> original prefixes are valid.   This is available in the distributed
>> source code.
>
>
>
> I assume the above doesn't deal with the case of prefix addition or
> removal in which, I think, the real difficulty of synchronization lies. 


Actually, I think it does cover this.

Since the routers don't go to sleep, and are likely to see each others'
advertisements within a finite (MaxRtrAdvInterval < 30s) period of time,
They will see also advertisements with retracted prefixes (0 lifetime)
with high probability.  Routers can immediately stop advertising a
prefix.

Advertisements of the CompleteRA therefore can exclude particular
prefixes which are no-longer on link, and this information can be
taken as authoritative by hosts:  The router thinks the current
prefix list is complete, even though it doesn't contain the prefix
(the host dumps the prefix).  This works since the completeRA will also
contain any other prefixes on the link, and no change detection will
occur (as the prefixes shouldn't be disjoint).


New prefixes are much easier, since as CompleteRAs overlap (only differ
by the new prefixes), no change detection occurs.  It is possible that
the routers do not agree about all of the prefixes available on a link,
but the routers will have some information in common before the prefix
is added,

>
>>> It can. It will simply pick the smallest prefix.
>>
>>
>> Except if the non-DNA routers do not have the smallest prefix
>> configured (which was my point).
>
>
>
> I have difficulty understanding your concern.  


CompleteRA routers  contain all (A=1,L=1) prefixes on the
link. So even if the non-DNA router has (originally) disjoint prefixes
any RA from either a non-DNA or DNA router will share information in
common (the non-DNA router's own prefix).

Therefore any reception of an RA from a DNA or non DNA source can
immediately be identified as a change or no change.

This is a lot faster than moving to a network that doesn't support
DNA, if the DNA solution uses a LinkID instead.   It's necessary
to fall back to RS/RA exchanges.

We encountered this problem with numeric LinkIDs a long time ago before
CPL was around (CPL improves things).

>> The RAs received from non-DNA routers aren't guaranteed to have
>> any prefixes in common with the DNA (LinkID) routers.
>
>
>
> Linkid host doesn't make a decision based on RA without linkid prefix. 


That makes sense.

On the DNA link the host will still need to do RS/RA exchanges to
build its CPL though, otherwise CPL logic won't work immediately either.

Greg 

JinHyeock Choi

Dear Sathya


>> So, in conclusion, the synchronization requirement and
>> complexity for Landmark, CompleteRA and LinkID are the same - all three
>> of them require that all the routers on the link know about all the
>> prefixes on the link within a reasonable time - the difference is only
>> in the content of the RS/RA messages. Do you agree?


No. Linkid draft deals with synchronization problem by taking extra 
care of linkid prefix with such schemes as "linkid prefix list" or "linkid 
prefix lifetime". It's my guess that, for CompleteRA or Landamrk, such 
extra cares need to be be applied to all the prefixes. 

Best Regards

JinHyeock

Greg Daley

Hi JinHyeock,

Right at the bottom is a proposal for a "Graceful"
means of surviving flash renumbering with Prefix Landmarks.

It's not really necessary in the general case if routers
retract prefixes with lifetime=0 advertisements, if they
wish to assign the prefix elsewhere before normal
lifetime expiry.

JinHyeock Choi wrote:

> Greg
>
>
>>> Linkid scheme also works with RS as well as without RS if the node
>>> was on a DNA capable link previously. Definitely I see the advantage
>>> of Landmark if the node is moving from non-DNA link.
>>
>>
>> The same can be said of CompleteRA (which has [provably] exactly
>> the same properties as LinkID of being able to detect link change
>> with DNA routers).
>>
>> The omission of RS only works in constrained environments
>> where one already has the right link information (FMIPv6
>> predictive handover), or the Network infrastructure
>> can be known beforehand to provide RA information (conceivably
>> FastRD in a constrained environment).
>
>
>
> I don't think this is correct.
> For example, FRD works with current 2461 standard. Upon network attachment, a host will perform random delay before sending RS (average 500ms). During which, the host will receive an RA optimized for DNA to complete DNA. 


You are right only if the DNA host _knows_ FastRD is present.
Then it can defer sending an RS.

If it doesn't know of FastRD's presence, it cannot afford to
wait before sending RS (500ms is so much longer than a VoIP
session can hide, and potentially longer than a TCP window
transmission).

RFC2461bis already describes removal of the 0-1000ms delay on
reception of link-layer indication.  I don't think hosts need
to defer RS transmission if they're unaware of the fact that
FastRD is available on the link.

Remember the goal G2 for DNA:

 G2 DNA schemes should detect the identity of an attached link with
      minimal latency lest there should be service disruption.

If there's no knowledge that FastRD is available in a domain, there
can be no deferral of DNA to potentially save one RS.

> Also we can't say FMIPv6 and FRD are the only ways to perform DNA without RS. There is a possibility of other schemes.  


But we're not standardizing those unnamed schemes:

As in RFC 1958 section 3.7, we have an almost complete solution,
we're not likely to defer making a decision about something to
support future (unmentioned) solutions.

>> Neither of these scenarios is under consideration for the
>> main DNA solution (FMIPv6 because it works without RA, FastRD
>> because it isn't generally applicable), 
>
>
>
> As of my memory, WG didn't made such a decision. 


It made the decision at the same time it discarded Numeric LinkIDs,
Deterministic FastRA etc: when it agreed to focus on 0ne or Two
potential solutions (with specific properties) at the last IETF.

> Also I don't think that the above description is exactly correct. I talked with mobile/cellular operators and in such a environment, FRD is generally very well applicable. 


But it's not the basic DNA solution: it's an optimization which cannot
be applied to every network.

>> So I don't think we can champion one particular technology based
>> on the fact that it works (slowly in general) with unsolicited RA.
>
>
>
> Disagree. This may be a serious concern for moible/ceullar operators.

>

> DNA is rather about optimization, quickly checking for link change to support seamless handoff. So I think main (at least substantial part of) customers for DNA will be mobile operators


Not every network is to be run by cellular operators.
Almost every network will need DNA.

Cellular operators are likely to deploy further infrastructure
such as FMIPv6 to support fast handovers.  In that case,
queuing an RA upon attachment to a new cell only induces delay.

> It's my opinion that if one scheme can perform DNA without RS involvement, that's the pro for the scheme we need to take into consideration.


It's no more a pro for LinkID than for CompleteRA.

If we have a FastRD scheme, it doesn't really matter which of those
is deployed.

>>> As a host can build the complete prefix list on its own without explicit
>>> support for complete RA, we may need to carefully evaluate it's benefits
>>> against the bandwidth consumption on the link as well as synchronization
>>> complexity. A host may need to be at the link for less than a minute to
>>> acquire the complete prefix list, the chances of a node moving away from
>>> the link within few seconds may be less.
>>
>>
>> But we already have CPL, and we know what its limitations are.
>>
>> The time to build sufficient information to Detect change is the
>> critical issue:  Otherwise we wouldn't have any link
>> identification mechanism in the DNA solution.   CPL is good
>> enough if you've got the time and energy to probe for RAs.
>>
>> If we want to support (potentially) rapidly changing attachment,
>> the state on the host needs to be as up to date as possible, whether
>> using a landmark, a link-id or CompleteRA.
>
>
>
> According to the current CPL recommendation, it will take 4 secs for
> a host to generate the complete prefix list. I think it's rather an exceptional case for a host to change attachment within 4 secs after network attachment.  



It's not that hard to change attachment points quickly with ping-pong.
This is a well known problem.

I'm not in strict agreement with the single RS for CPL,
since RA messages can be lost, and you can end up with half a CPL.

If you transit outside the cell within 4 seconds, false link change
detection occurs.

I'd prefer "At least 1" or "Defaults to 1" x 4 seconds.

>> CompleteRA has the potential to create a CPL immediately, which
>> is better for the "movement to non-DNA" link case.
>
>
>
> I may add "with added synchronization cost".  


That's not really true, if you've read the other posts in this thread.

CompleteRA is more reliable than CPL, since routers don't go to sleep
often (routers build better lists than hosts).

>>> As we have implemented the linkid scheme, we did not find any such problems.
>>> For landmark also all the Routers need know about all other prefixes, otherwie
>>> the host may get conflict answers.
>>
>>
>> It doesn't need to know all the prefixes (as described in a previous
>> thread).  It needs to know what prefixes it definitely has locally.
>>
>> In that case, it can answer "Yes" immediately.  Answering "No" takes
>> definitive knowledge and synchronization.   
>
>
>
> Answering "Yes" also takes definite knowledge and synchronization. 

>

> Allow me an example. Assume a link with two routers R1 and R2. R1 advertises Prefix1 and R2 advertise Prefix2 and Prefix3. R1 and R2 gathers the prefixes to make the complete prefix list
> {Prefix1, Prefix2, Prefix3}.
>
> Then R2 removes Prefix3 but the RA advertising the removal was lost and R1 doesn't receive it. So afterwards, if a (dormant) host send an RS with Prefix3 to R1, it will falsely answer "YES", i.e. Prefix3 is in this link.
>  Am I missing something?


Yes.

The same thing happens with LinkID

In this case, the Router1 will not identify that the LinkID has changed
either, if the smallest prefix disappears (for example if Prefix3 is
actually the smallest prefix).

Responses for LinkID will therefore also conflict, Router1 will
have a LinkID of prefix Prefix3, even if that prefix has been
assigned to an adjacent link.

For Prefix Landmarking:

If any RAs by received by R1 indicating that the lifetime is
diminished, this will time out the entries.  Any single reception
of a lifetime zero advertisement from the owning router will
remove the prefix.

This is the same as LinkID.

So if Prefix Landmarking believes the prefix is still on-link
(and Prefix Landmarking has similar timers for lifetimes that
LinkID does) then the incorrect state will last about as long
for either.

The assumption is that prefixes retracted without (effective)
zero lifetime advertisement and assigned to another link cause
problems for up to 90 minutes or so:

This is the same for Prefix Landmarks, CompleteRA, LinkID and
(in hosts' view) CPL.

This is a very tight corner case, since routers listen to RAs
in DNA, don't sleep, and routers should retract prefixes.

At least with CompleteRA, you can ignore learned DNAO contents
since the rest of the CompleteRA will not match the existing
Complete Prefix List.

>> A prefix which answers
>> "Yes" will supercede a "No" if it is received first.
>
>
>
> I guess the same applies for "NO".
> "NO" will supercede a "YES", if it is received first, right? 


Yes, but a false movement detection is actually better than a false
non-movement detection, since the host recovers in milliseconds, not
minutes.

>> The chance that a router will answer "No" when another answers "Yes"
>> is the chance that a prefix's advertisement has not been received
>> on the "No" router before the RS with a landmark query is sent.
>>
>> This is bounded by the delay of the original RA to cross the network,
>> and any robustness factors affecting delivery between pairs of routers.
>>
>> As the solicitor would have to have received the landmark prefix in
>> an RA before it can send the landmark RS, the chances are really
>> quite small that any remaining router would be not be updated
>> before answering the landmark query. 
>
>
> In the example I present the above, "NO" is the correct one and
> doesn't result from "that a prefix's advertisement has not been received
> on the "No" router before the RS with a landmark query is sent."


I see your point: the most up-to-date router could respond "NO" based on
updated information.

In that case though, it can also update the other routers with
the appropriate RA (prefix lifetime=0).

The window in that case is still fairly small.

> Correct me wrong but when I looked through Landmark/ CompleteRA last time, I don't see any mechanism to deal with the case two routers
> give conflicting answers, one yes and the other no. Such a case can arise from a lack of synchronization. 


Indeed, this is the same as LinkID, where the out-of-date LinkID is
still used by a router which has not seen the PIO with the prefix
retracted.

While Prefix Landmarks can conceivably answer "Yes" incorrectly
in this case, so would some of the LinkID routers.

A practical solution for Prefix Landmarks may be to partly
ignore "Yes" answers - since they don't require much action: that
is keep the DNA process open if there's a non-movement indication.

The DNA addressing mechanism may be re-normalized (and packet flow can
occur with the global addresses), but subsequent reception of a
trusted "No" RA within (say 500ms) could be used as a hint to re-build
a CPL - which may be a cause to detect change in a few seconds.

Greg 

James Kempf

Greg,

I think there is also the backward compatibility issue, which you raised.

            jak

----- Original Message -----
From: "Greg Daley" <greg.daley@eng.monash.edu.au>
To: "JinHyeock Choi" <jinchoe@gmail.com>
Cc: "Sathya Narayanan" <sathya@research.panasonic.com>; "Brett Pentland"
<brett.pentland@eng.monash.edu.au>; "James Kempf"
<Kempf@docomolabs-usa.com>; "Dna" <dna@eng.monash.edu.au>
Sent: Wednesday, July 20, 2005 11:52 PM
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s.
LandmarkPrefix



>> Hi JinHyeock,
>>
>> JinHyeock Choi wrote:
>
>>> > Sathya
>>> >
>>> > Sorry for a late reply. After FRD completeion, I am still busy
>>> > catching up baglog mails.
>>> >
>>> >
>>
>>>> >>I don't think this is accurate in comparison to synchronizing for
>>>> >>prefix-LinkID. Prefix LinkID requires the completeRA list to be
>>>> >>synchronized in each of the routers so that the least prefix can be
>>>> >>selected from the list as LinkID. So the synchronization/bandwidth
>>>> >>requirements are the same for both CompleteRA and Prefix LinkID.
>>
>>> >
>>> >
>>> > I may not be clear.
>>> >
>>> > The difficulty in synchronization lies in when a prefix is added or
>>> > removed. There is a scheme for graceful linkid change in Linkid but,
>>> > correct me wrong, nothing like that in Landmark/ CompleteRA.
>
>>
>> I think that there's no scheme defined in Landmark/CompleteRA,
>> but (in my guess) the choice of the scheme itself will significantly
>> affect whether particular "config" change management (rather than link
>> change management) schemes are needed.
>>
>
>>> > I remember that DT discussed much about the flapping
>>> > probmem in CompleteRA synchronization difficulty (w.r.t the prefix
>>> > number) in 'CompleteRA Polished' thread.
>
>>
>> Thanks for the pointer to this thread.
>>
>> I think there are two or three related threads:
>>
>> Complete RA Polished
>> http://www.ctie.monash.edu.au/warchive/dna-dt/2005-03/msg00157.html
>>
>> Complete RA Re-polished
>> http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/msg00009.html
>>
>> LinkID Polished
>> http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/msg00097.html
>> and
>> http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/threads.html
>>
>>
>> It's good to know that there's been so much work on this (and
>> that everyone can read it).
>>
>> There were a lot of differences between individual schemes
>> as portrayed before (in April) and now though.  This may
>> affect the way prefix addition or subtraction works.
>>
>> Given the individual current schemes though, let's try to characterise
>> the effects of addition or substraction of prefixes on each protocol
>> as configured today.
>>
>> Does that sound reasonable?
>>
>> I guess that if the state + processing requirements for
>> Landmark/CompleteRA and LinkID are comparable (which I've
>> indicated may be the case), implementation experiences are
>> qualitative, and in the normal case
>> (and non-DNA case) all schemes act sensibly, the
>> main issues will probably be:
>>
>> * Synchronization/How the schemes react to change of prefixes.
>>
>> * Packet Sizes
>>
>> Does this sound like the right criteria to compare
>> the schemes on?
>>
>> There may not be a clear winner with any of these, and
>> it may be that the WG just chooses a particular
>> scheme it likes.
>>
>> The comparison is likely to help with forming that opinion,
>> and may actually highlight a winner.
>>
>> Should we go ahead?
>>
>> It may mean some in-depth description of how the schemes
>> currently handle change (which may take some discussion).
>>
>> I think that we need to compare packet sizes for:
>>
>> RS/RA exchange for each scheme (or set of schemes) as described
>>        in current drafts.
>>
>> Where:
>>
>> a) 1 prefix is shared by all routers
>>
>> b) 1 distinct prefix is configured on each router.
>>
>> c) 1 prefix is shared by all routers and one additional prefix is
>>                 advertised by one router (big or small prefix).
>>
>> We should probably do this for 1,2 routers (though the third
>> test may be a bit simple with 1 router - one router 2 prefixes).
>>
>> We should sum the sizes of the response RAs for all routers.
>>
>> Does this sound OK with people?
>>
>> Greg
>>

Brett Pentland

Hi JinHyeock,

>>> As we have implemented the linkid scheme, we did not find any such problems.
>>> For landmark also all the Routers need know about all other prefixes, otherwie
>>> the host may get conflict answers.
>>
>>
>> It doesn't need to know all the prefixes (as described in a previous
>> thread).  It needs to know what prefixes it definitely has locally.
>>
>> In that case, it can answer "Yes" immediately.  Answering "No" takes
>> definitive knowledge and synchronization.   
>
>
>
> Answering "Yes" also takes definite knowledge and synchronization.
> Allow me an example. Assume a link with two routers R1 and R2. R1 advertises Prefix1 and R2 advertise Prefix2 and Prefix3. R1 and R2 gathers the prefixes to make the complete prefix list
> {Prefix1, Prefix2, Prefix3}.
>
> Then R2 removes Prefix3 but the RA advertising the removal was lost and R1 doesn't receive it. So afterwards, if a (dormant) host send an RS with Prefix3 to R1, it will falsely answer "YES", i.e. Prefix3 is in this link.
> Am I missing something? 


Well, "YES" is the answer that LinkID would give too.  The LinkID would
not have changed on R1 and the host would correctly recognise that it is
NOT a link change.  So how is it better?

With Landmarks, when the subsequent advertisement from R2 came in it
would say NO, and list the available prefixes. This list would have some
overlap with the prefixes that the host has seen and so it would again
realise that there is no link change, and yet would be able to see that
Prefix3's lifetime is zero and it had better use a different Landmark
next time.

You say that LinkID has a method to deal with changing prefixes.  Hosts
keep a record previously seen LinkIDs so that they can recognise
changes. Isn't this implicit in the CompleteRA aspect of the landmark
proposal?  Each of the prefixes can be thought of as a LinkID, and any
overlap between the prefixes in a CompleteRA and the prefixes that the
host has seen implies non-movement.

Putting aside, for the moment, cases where a prefix is moved to a new
link before its lifetime advertised on the old link has expired, your
own example shows how the Landmark part deals with changes effectively.
A YES answer will only occur if the prefix has been used on the link and
so will not be wrong in the sense that the current link is the same one
where the Landmark came from.  If that prefix is in the process of being removed, then very soon a NO answer will arrive from the applicable
router informing the host of this and providing the prefixes that are
available.  Note also that the window of oportunity for this to happen
is quite small as the router that removed the prefix should advertise
this fact several times in a fairly short space of time so that all
of the routers on the link are aware of the change.

Returning to cases where prefixes can be reasigned to a new link before
the expiry of a previously advertised valid lifetime on another link,
both of the proposals face the same issue and need to deal with it by
placing rules about how the reassignment is done.  If a host sees a
LinkID or a Landmark on one link, fails to see advertisements that the
valid lifetime has been shortened, and then sees the same LinkID /
Landmark on another link, they will fail to detect the link change.

Cheers,
Brett. 

Subba Reddy

Hi Satya,


>>
>
>>> > So, in conclusion, the synchronization requirement and
>>> > complexity for Landmark, CompleteRA and LinkID are the same - all three
>>> > of them require that all the routers on the link know about all the
>>> > prefixes on the link within a reasonable time - the difference is only
>>> > in the content of the RS/RA messages. Do you agree?
>
>>
>> No. Linkid draft deals with synchronization problem by taking extra
>> care of linkid prefix with such schemes as "linkid prefix list" or "linkid
>> prefix lifetime".


In linkid sceme ,Even if some routers misses some RAs (containing changed
prefix information), because of which, these routers will be advertising old
linkid,
hosts will not make wrong decision by looking at different linkids
advertised
by different routers.

If the routers can learn change in prefixes in 1.5 hours, it is not a
problem in linkid.
I think 1.5 hours (i.e, atleast 3 RAs will be transmitted) is fairly good
enough.

Thanks & Regards,
Subba Reddy


>>It's my guess that, for CompleteRA or Landamrk, such
>> extra cares need to be be applied to all the prefixes.
>>
>> Best Regards
>>
>> JinHyeock

JinHyeock Choi

Greg


>> I think there are two or three related threads:
>> 
>> Complete RA Polished
>> http://www.ctie.monash.edu.au/warchive/dna-dt/2005-03/msg00157.html
>> 
>> Complete RA Re-polished
>> http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/msg00009.html
>> 
>> LinkID Polished
>> http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/msg00097.html
>> and
>> http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/threads.html
>> 
>> It's good to know that there's been so much work on this (and
>> that everyone can read it).


It will be nice if the above threads are of help. 


>> There were a lot of differences between individual schemes
>> as portrayed before (in April) and now though.  This may
>> affect the way prefix addition or subtraction works.


Actually the main changes results from the synchronization
difficulties. 


>> Given the individual current schemes though, let's try to characterise
>> the effects of addition or substraction of prefixes on each protocol
>> as configured today.
>> 
>> Does that sound reasonable?
>> 
>> I guess that if the state + processing requirements for
>> Landmark/CompleteRA and LinkID are comparable (which I've
>> indicated may be the case), implementation experiences are
>> qualitative, and in the normal case
>> (and non-DNA case) all schemes act sensibly, the
>> main issues will probably be:
>> 
>> * Synchronization/How the schemes react to change of prefixes.
>> 
>> * Packet Sizes
>> 
>> Does this sound like the right criteria to compare
>> the schemes on?


It's my opinion that just the above two are too narrow a criteria,
(though I agree that both of them good). I think other criteria such 
as 'complexity (as Jak mentioned)' need to be considered. Kindly 
allow me some time to contemplate other criteria. 
 

>> There may not be a clear winner with any of these, and
>> it may be that the WG just chooses a particular
>> scheme it likes.


ok. 


>> The comparison is likely to help with forming that opinion,
>> and may actually highlight a winner.
>> 
>> Should we go ahead?


I think the comparison list is of help. 


>> It may mean some in-depth description of how the schemes
>> currently handle change (which may take some discussion).
>> 
>> I think that we need to compare packet sizes for:
>> 
>> RS/RA exchange for each scheme (or set of schemes) as described
>>       in current drafts.


I think we should compare the general bandwidth consumption 
between two schemes (including unsolicited RAs). 

Best Regards

JinHyeock

JinHyeock Choi

Greg 


>> Right at the bottom is a proposal for a "Graceful"
>> means of surviving flash renumbering with Prefix Landmarks.
>> 
>> It's not really necessary in the general case if routers
>> retract prefixes with lifetime=0 advertisements, if they
>> wish to assign the prefix elsewhere before normal
>> lifetime expiry.


I have difficulty understanding that. Does that take into consideration 
packet loss?  


>>> > As of my memory, WG didn't made such a decision.
>
>> 
>> It made the decision at the same time it discarded Numeric LinkIDs,
>> Deterministic FastRA etc: when it agreed to focus on 0ne or Two
>> potential solutions (with specific properties) at the last IETF.


No, it didn't make such a decision. (It's strange that it was claimed
that Linkid had been decided to be removed when I presented it. )

At the time of Minneapolis meeting, as possible DNA solution candidates, 
I had in mind 'CompleteRA', 'Prefix based Linkid' and 'FRD'. So I took 
extra and intentional care that WG would not throw away those 3 schemes. 

As of my memory, only "ruling out" process happened during DT 
discussion at Wednesday morning and neither one of three schemes 
was ruled out at the meeting. 

I cc Brett's mail after the meeting to back up my memory. 

----------------------------------------------------------
   Hi guys,

   Yesterday we agreed that several of the techniques that we have
   discussed are probably not worth pursuing.  Those are:

   Explicit LinkID - random
   Explicit LinkID - hash of prefixes
   Priority Landmark
   Simple FastRA
   Deterministic FastRA

   That leaves us with the following:

   Link detection:
       Explicit LinkID - agreed prefix
       CompleteRA
       Requested Landmark
       Hybrid Landmark

   Fast advertisement:
       Fast Router Discovery
       Hash-ordered FastRA (is that a bit easier to say?   :)  )
       Probabilistic FastRA

   Cheers,
   Brett.

----------------------------------------------------------


>>> > It's my opinion that if one scheme can perform DNA without RS involvement,
>>> > that's the pro for the scheme we need to take into consideration.
>
>> 
>> It's no more a pro for LinkID than for CompleteRA.


ok. At this point, my assertion is only that 

the above is a worthy criterion to consider when we evaluate schemes. 


>>> > According to the current CPL recommendation, it will take 4 secs for
>>> > a host to generate the complete prefix list. I think it's rather an
>>> > exceptional case for a host to change attachment within 4 secs
>>> > after network attachment.
>
>> 
>> It's not that hard to change attachment points quickly with ping-pong.
>> This is a well known problem.
>> 
>> I'm not in strict agreement with the single RS for CPL,
>> since RA messages can be lost, and you can end up with half a CPL.
>> 
>> If you transit outside the cell within 4 seconds, false link change
>> detection occurs.
>>
>> I'd prefer "At least 1" or "Defaults to 1" x 4 seconds.


Right but I am not arguing that such a case is impossible. I am 
talking only that such a case seems to be rather an exception. 

Also this is why we think that it is ok for a host to
send 1 RS and waits for 4 secs to collect (solicited) RAs
and declare CCL complete.

Without a packet loss, the host will generate the complete prefix list.

Even some packet loss may cause an incomplete prefix list,
there is a further chance for the host to get the missing prefixes
before it receives link UP notification, i.e. moves to another AP.

Even the host moves to another AP with incomplete prefix list,
the first RA may contain the prefix in its prefix list.

Considering all those above, even if the host performs only one
RS/ RA exchange, it will be very rare for the host to falsely
assume a link change. So I think that occasional additional
signaling  is acceptable.


>>>>> >>>As we have implemented the linkid scheme, we did not find any such problems.
>>>>> >>>For landmark also all the Routers need know about all other prefixes, otherwie
>>>>> >>>the host may get conflict answers.
>>>
>>>> >>
>>>> >>It doesn't need to know all the prefixes (as described in a previous
>>>> >>thread).  It needs to know what prefixes it definitely has locally.
>>>> >>
>>>> >>In that case, it can answer "Yes" immediately.  Answering "No" takes
>>>> >>definitive knowledge and synchronization.
>>
>>> >
>>> >
>>> > Answering "Yes" also takes definite knowledge and synchronization.
>
>>  >
>
>>> > Allow me an example. Assume a link with two routers R1 and R2.
>>> > R1 advertises Prefix1 and R2 advertise Prefix2 and Prefix3.
>>> > R1 and R2 gathers the prefixes to make the complete prefix list
>>> > {Prefix1, Prefix2, Prefix3}.
>>> >
>>> > Then R2 removes Prefix3 but the RA advertising the removal
>>> > was lost and R1 doesn't receive it. So afterwards, if a (dormant)
>>> > host send an RS with Prefix3 to R1, it will falsely answer "YES",
>>> > i.e. Prefix3 is in this link.
>>> >
>>> >  Am I missing something?
>
>> 
>> Yes.
>> 
>> The same thing happens with LinkID
>> 
>> In this case, the Router1 will not identify that the LinkID has changed
>> either, if the smallest prefix disappears (for example if Prefix3 is
>> actually the smallest prefix).
>> 
>> Responses for LinkID will therefore also conflict, Router1 will
>> have a LinkID of prefix Prefix3, even if that prefix has been
>> assigned to an adjacent link.


Linkid is designed to deal with such a pathological case with 
linkid prefix list.  Kindly check Sec 3 and 4. 


>> For Prefix Landmarking:
>> 
>> If any RAs by received by R1 indicating that the lifetime is
>> diminished, this will time out the entries.  Any single reception
>> of a lifetime zero advertisement from the owning router will
>> remove the prefix.
>> 
>> This is the same as LinkID.
>> 
>> So if Prefix Landmarking believes the prefix is still on-link
>> (and Prefix Landmarking has similar timers for lifetimes that
>> LinkID does) then the incorrect state will last about as long
>> for either.
>> 
>> The assumption is that prefixes retracted without (effective)
>> zero lifetime advertisement and assigned to another link cause
>> problems for up to 90 minutes or so:
>> 
>> This is the same for Prefix Landmarks, CompleteRA, LinkID and
>> (in hosts' view) CPL.
>>
>> This is a very tight corner case, since routers listen to RAs
>> in DNA, don't sleep, and routers should retract prefixes.
>> 
>> At least with CompleteRA, you can ignore learned DNAO contents
>> since the rest of the CompleteRA will not match the existing
>> Complete Prefix List.


I have difficulty following the above. 


>>>> >>A prefix which answers
>>>> >>"Yes" will supercede a "No" if it is received first.
>>
>>> >
>>> >
>>> > I guess the same applies for "NO".
>>> >
>>> > "NO" will supercede a "YES", if it is received first, right?
>
>> 
>> Yes, but a false movement detection is actually better than a false
>> non-movement detection, since the host recovers in milliseconds, not
>> minutes.


Does the above mean "NO" will always supercede "YES", because 
a false movement detection is actually better than a false non-movement 
detection?


>>> > In the example I present the above, "NO" is the correct one and
>>> > doesn't result from "that a prefix's advertisement has not been received
>>> > on the "No" router before the RS with a landmark query is sent."
>
>> 
>> I see your point: the most up-to-date router could respond "NO" based on
>> updated information.
>> 
>> In that case though, it can also update the other routers with
>> the appropriate RA (prefix lifetime=0).


Yes, but it needs additional mechanism to ensure every routers 
will receive the appropriate RA. 


>>> > Correct me wrong but when I looked through Landmark/ CompleteRA
>>> > last time, I don't see any mechanism to deal with the case two routers
>>> > give conflicting answers, one yes and the other no. Such a case can
>>> > arise from a lack of synchronization.
>
>> 
>> Indeed, this is the same as LinkID, where the out-of-date LinkID is
>> still used by a router which has not seen the PIO with the prefix
>> retracted.
>>
>> While Prefix Landmarks can conceivably answer "Yes" incorrectly
>> in this case, so would some of the LinkID routers.


As I wrote above, it will not affect DNA performance for Linkid. 
Kindly look over the draft. 


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


Maybe, but the scheme seems to become more complicated. At least, I
come to have difficulty following your arguments. 

Best Regards

JinHyeock

Greg Daley

Hi JinHyeock,

I'm not added much, but this time, not removed much
either.


----- Original Message -----
From: JinHyeock Choi <jinchoe@gmail.com>
Date: Friday, July 22, 2005 6:33 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
LandmarkPrefix

>> Greg
>> 
>
>>> > I think there are two or three related threads:
>>> > 
>>> > Complete RA Polished
>>> > http://www.ctie.monash.edu.au/warchive/dna-dt/2005-03/msg00157.html
>>> > 
>>> > Complete RA Re-polished
>>> > http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/msg00009.html
>>> > 
>>> > LinkID Polished
>>> > http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/msg00097.html
>>> > and
>>> > http://www.ctie.monash.edu.au/warchive/dna-dt/2005-04/threads.html
>>> > 
>>> > It's good to know that there's been so much work on this (and
>>> > that everyone can read it).
>
>> 
>> It will be nice if the above threads are of help. 
>> 
>
>>> > There were a lot of differences between individual schemes
>>> > as portrayed before (in April) and now though.  This may
>>> > affect the way prefix addition or subtraction works.
>
>> 
>> Actually the main changes results from the synchronization
>> difficulties. 
>> 
>
>>> > Given the individual current schemes though, let's try to 
>
>> characterise> the effects of addition or substraction of prefixes 
>> on each protocol
>
>>> > as configured today.
>>> > 
>>> > Does that sound reasonable?
>>> > 
>>> > I guess that if the state + processing requirements for
>>> > Landmark/CompleteRA and LinkID are comparable (which I've
>>> > indicated may be the case), implementation experiences are
>>> > qualitative, and in the normal case
>>> > (and non-DNA case) all schemes act sensibly, the
>>> > main issues will probably be:
>>> > 
>>> > * Synchronization/How the schemes react to change of prefixes.
>>> > 
>>> > * Packet Sizes
>>> > 
>>> > Does this sound like the right criteria to compare
>>> > the schemes on?
>
>> 
>> It's my opinion that just the above two are too narrow a criteria,
>> (though I agree that both of them good). I think other criteria 
>> such 
>> as 'complexity (as Jak mentioned)' need to be considered. Kindly 
>> allow me some time to contemplate other criteria. 



Computational/Storage Complexity is simple to calculate.

Comparison of text or implementation LOCs doesn't help unless
direct comparison of complete schemes is possible though.

Please consider criteria though. We can work on the simple comparisons
first if need be.


>>> > There may not be a clear winner with any of these, and
>>> > it may be that the WG just chooses a particular
>>> > scheme it likes.
>
>> 
>> ok. 
>> 
>
>>> > The comparison is likely to help with forming that opinion,
>>> > and may actually highlight a winner.
>>> > 
>>> > Should we go ahead?
>
>> 
>> I think the comparison list is of help. 
>> 
>
>>> > It may mean some in-depth description of how the schemes
>>> > currently handle change (which may take some discussion).
>>> > 
>>> > I think that we need to compare packet sizes for:
>>> > 
>>> > RS/RA exchange for each scheme (or set of schemes) as described
>>> >       in current drafts.
>
>> 
>> I think we should compare the general bandwidth consumption 
>> between two schemes (including unsolicited RAs). 



Oh Yes:   I guess that the LinkID and CompleteRA schemes
consume additional bandwidth with ongoing advertisements,
so it's relevant.

Brett had done some work on that previously for the early DT work,
so we may see if it's still applicable

I'll be travelling over the weekend, so that may slow things down.
Greg

Sathya Narayanan

----- Original Message -----
From: JinHyeock Choi <jinchoe@gmail.com>
Date: Friday, July 22, 2005 1:53 am
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue   X]LinkIDv.s.LandmarkPrefix


>> Dear Sathya
>> 
>
>>> > So, in conclusion, the synchronization requirement and
>>> > complexity for Landmark, CompleteRA and LinkID are the same - 
>
>> all three
>
>>> > of them require that all the routers on the link know about all the
>>> > prefixes on the link within a reasonable time - the difference 
>
>> is only
>
>>> > in the content of the RS/RA messages. Do you agree?
>
>> 
>> No. Linkid draft deals with synchronization problem by taking 
>> extra 
>> care of linkid prefix with such schemes as "linkid prefix list" or 
>> "linkid 
>> prefix lifetime". It's my guess that, for CompleteRA or Landamrk, 

>> such 
>> extra cares need to be be applied to all the prefixes. 
>> 

If the LinkID is being chosen based on some rule (the smallest prefix in the Complete Prefix List) applied to the complete prefix list, then LinkID solution must also make sure that all the routers have the same list. I understand that the hosts maintain a LinkID list, but that doesn't make it OK to have routers in the same link to be advertising different LinkID.  (as an aside, it is more accurate to refer to this solution as LinkIDList - because AFAIK, the host, the router and the RA will contain a LinkIDList - the list may contain one or more entries - right?).

Sathya

Greg Daley

Hi JinHyeock, 

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

----- Original Message -----
From: JinHyeock Choi <jinchoe@gmail.com>
Date: Friday, July 22, 2005 6:49 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
Landmark Prefix

>> Greg 
>> 
>
>>> > Right at the bottom is a proposal for a "Graceful"
>>> > means of surviving flash renumbering with Prefix Landmarks.
>>> > 
>>> > It's not really necessary in the general case if routers
>>> > retract prefixes with lifetime=0 advertisements, if they
>>> > wish to assign the prefix elsewhere before normal
>>> > lifetime expiry.
>
>> 
>> I have difficulty understanding that. Does that take into 
>> consideration packet loss?  


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


 

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


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


>> At the time of Minneapolis meeting, as possible DNA solution 
>> candidates,  I had in mind 'CompleteRA', 'Prefix based Linkid' and
>> 'FRD'. So I took extra and intentional care that WG would not
>> throw away those 3 schemes. 
>> 
>> As of my memory, only "ruling out" process happened during DT 
>> discussion at Wednesday morning and neither one of three schemes 
>> was ruled out at the meeting. 
>>
>> I cc Brett's mail after the meeting to back up my memory. 

[cut]

>> 
>>   Fast advertisement:
>>       Fast Router Discovery
>>       Hash-ordered FastRA (is that a bit easier to say?   :)  )
>>       Probabilistic FastRA

[cut]

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

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

Optimizations beyond this would have to be specified separately.


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




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

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


[cut]

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



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

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

[cut]

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


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

It looks like it is.

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

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



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

 
[cut]

>>>> > > "NO" will supercede a "YES", if it is received first, right?
>>
>>> > 
>>> > Yes, but a false movement detection is actually better than a false
>>> > non-movement detection, since the host recovers in milliseconds, not
>>> > minutes.
>
>> 
>> Does the above mean "NO" will always supercede "YES", because 
>> a false movement detection is actually better than a false non-
>> movement detection?


If it is received first, yes.

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

This is the same as for LinkID.

[cut]

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


I'ts already defined.

6.2.4.  Sending Unsolicited Router Advertisements

Especially the section describing advertising changes

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

[cut]

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


It's not particularly complicated:

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

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

Did we need to do anything anyway?

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

This is a lot less complicated...


Greg

James Kempf

I think we should compare the general bandwidth consumption
between two schemes (including unsolicited RAs).


jak>> Why is this so important? I believe 802.16 (which I think you are
interested in) has bandwidths between 1 - 5 Mbps, and 3.9 G is up to 20
Mbps. 9.6 kbps links aren't really that important anymore.

            jak

James Kempf

JinHyeok,

The minutes of the IETF 62 meeting show that I proposed taking FastRA out of
contention, because it is very link specific (it would not work for 3.9G for
example), and referring it to the proper link standardization group
(probably 802.21). Unfortuantely, there is no record of a consensus call on
this proposal in the minutes. I'd like to renew my proposal and suggest to
the chairs that a consensus call be done at a convenient time.

We cannot make progress on getting this standard complete if discussion
never results in any decisions being made.

            jak

----- Original Message -----
From: "JinHyeock Choi" <jinchoe@gmail.com>
To: <greg.daley@eng.monash.edu.au>
Cc: "Syam Madanapalli" <smadanapalli@gmail.com>; "Brett Pentland"
<brett.pentland@eng.monash.edu.au>; "James Kempf"
<Kempf@docomolabs-usa.com>; "Dna" <dna@eng.monash.edu.au>
Sent: Friday, July 22, 2005 1:49 AM
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s.
Landmark Prefix



>> Greg
>>
>
>>> > Right at the bottom is a proposal for a "Graceful"
>>> > means of surviving flash renumbering with Prefix Landmarks.
>>> >
>>> > It's not really necessary in the general case if routers
>>> > retract prefixes with lifetime=0 advertisements, if they
>>> > wish to assign the prefix elsewhere before normal
>>> > lifetime expiry.
>
>>
>> I have difficulty understanding that. Does that take into consideration
>> packet loss?
>>
>
>>>> > > As of my memory, WG didn't made such a decision.
>>
>>> >
>>> > It made the decision at the same time it discarded Numeric LinkIDs,
>>> > Deterministic FastRA etc: when it agreed to focus on 0ne or Two
>>> > potential solutions (with specific properties) at the last IETF.
>
>>
>> No, it didn't make such a decision. (It's strange that it was claimed
>> that Linkid had been decided to be removed when I presented it. )
>>
>> At the time of Minneapolis meeting, as possible DNA solution candidates,
>> I had in mind 'CompleteRA', 'Prefix based Linkid' and 'FRD'. So I took
>> extra and intentional care that WG would not throw away those 3 schemes.
>>
>> As of my memory, only "ruling out" process happened during DT
>> discussion at Wednesday morning and neither one of three schemes
>> was ruled out at the meeting.
>>
>> I cc Brett's mail after the meeting to back up my memory.
>>
>> ----------------------------------------------------------
>>    Hi guys,
>>
>>    Yesterday we agreed that several of the techniques that we have
>>    discussed are probably not worth pursuing.  Those are:
>>
>>    Explicit LinkID - random
>>    Explicit LinkID - hash of prefixes
>>    Priority Landmark
>>    Simple FastRA
>>    Deterministic FastRA
>>
>>    That leaves us with the following:
>>
>>    Link detection:
>>        Explicit LinkID - agreed prefix
>>        CompleteRA
>>        Requested Landmark
>>        Hybrid Landmark
>>
>>    Fast advertisement:
>>        Fast Router Discovery
>>        Hash-ordered FastRA (is that a bit easier to say?   :)  )
>>        Probabilistic FastRA
>>
>>    Cheers,
>>    Brett.
>>
>> ----------------------------------------------------------
>>
>
>>>> > > It's my opinion that if one scheme can perform DNA without RS

involvement,

>>>> > > that's the pro for the scheme we need to take into consideration.
>>
>>> >
>>> > It's no more a pro for LinkID than for CompleteRA.
>
>>
>> ok. At this point, my assertion is only that
>>
>> the above is a worthy criterion to consider when we evaluate schemes.
>>
>
>>>> > > According to the current CPL recommendation, it will take 4 secs for
>>>> > > a host to generate the complete prefix list. I think it's rather an
>>>> > > exceptional case for a host to change attachment within 4 secs
>>>> > > after network attachment.
>>
>>> >
>>> > It's not that hard to change attachment points quickly with ping-pong.
>>> > This is a well known problem.
>>> >
>>> > I'm not in strict agreement with the single RS for CPL,
>>> > since RA messages can be lost, and you can end up with half a CPL.
>>> >
>>> > If you transit outside the cell within 4 seconds, false link change
>>> > detection occurs.
>>> >
>>> > I'd prefer "At least 1" or "Defaults to 1" x 4 seconds.
>
>>
>> Right but I am not arguing that such a case is impossible. I am
>> talking only that such a case seems to be rather an exception.
>>
>> Also this is why we think that it is ok for a host to
>> send 1 RS and waits for 4 secs to collect (solicited) RAs
>> and declare CCL complete.
>>
>> Without a packet loss, the host will generate the complete prefix list.
>>
>> Even some packet loss may cause an incomplete prefix list,
>> there is a further chance for the host to get the missing prefixes
>> before it receives link UP notification, i.e. moves to another AP.
>>
>> Even the host moves to another AP with incomplete prefix list,
>> the first RA may contain the prefix in its prefix list.
>>
>> Considering all those above, even if the host performs only one
>> RS/ RA exchange, it will be very rare for the host to falsely
>> assume a link change. So I think that occasional additional
>> signaling  is acceptable.
>>
>
>>>>>> > >>>As we have implemented the linkid scheme, we did not find any such

problems.

>>>>>> > >>>For landmark also all the Routers need know about all other prefixes,

otherwie

>>>>>> > >>>the host may get conflict answers.
>>>>
>>>>> > >>
>>>>> > >>It doesn't need to know all the prefixes (as described in a previous
>>>>> > >>thread).  It needs to know what prefixes it definitely has locally.
>>>>> > >>
>>>>> > >>In that case, it can answer "Yes" immediately.  Answering "No" takes
>>>>> > >>definitive knowledge and synchronization.
>>>
>>>> > >
>>>> > >
>>>> > > Answering "Yes" also takes definite knowledge and synchronization.
>>
>>> >  >
>>
>>>> > > Allow me an example. Assume a link with two routers R1 and R2.
>>>> > > R1 advertises Prefix1 and R2 advertise Prefix2 and Prefix3.
>>>> > > R1 and R2 gathers the prefixes to make the complete prefix list
>>>> > > {Prefix1, Prefix2, Prefix3}.
>>>> > >
>>>> > > Then R2 removes Prefix3 but the RA advertising the removal
>>>> > > was lost and R1 doesn't receive it. So afterwards, if a (dormant)
>>>> > > host send an RS with Prefix3 to R1, it will falsely answer "YES",
>>>> > > i.e. Prefix3 is in this link.
>>>> > >
>>>> > >  Am I missing something?
>>
>>> >
>>> > Yes.
>>> >
>>> > The same thing happens with LinkID
>>> >
>>> > In this case, the Router1 will not identify that the LinkID has changed
>>> > either, if the smallest prefix disappears (for example if Prefix3 is
>>> > actually the smallest prefix).
>>> >
>>> > Responses for LinkID will therefore also conflict, Router1 will
>>> > have a LinkID of prefix Prefix3, even if that prefix has been
>>> > assigned to an adjacent link.
>
>>
>> Linkid is designed to deal with such a pathological case with
>> linkid prefix list.  Kindly check Sec 3 and 4.
>>
>
>>> > For Prefix Landmarking:
>>> >
>>> > If any RAs by received by R1 indicating that the lifetime is
>>> > diminished, this will time out the entries.  Any single reception
>>> > of a lifetime zero advertisement from the owning router will
>>> > remove the prefix.
>>> >
>>> > This is the same as LinkID.
>>> >
>>> > So if Prefix Landmarking believes the prefix is still on-link
>>> > (and Prefix Landmarking has similar timers for lifetimes that
>>> > LinkID does) then the incorrect state will last about as long
>>> > for either.
>>> >
>>> > The assumption is that prefixes retracted without (effective)
>>> > zero lifetime advertisement and assigned to another link cause
>>> > problems for up to 90 minutes or so:
>>> >
>>> > This is the same for Prefix Landmarks, CompleteRA, LinkID and
>>> > (in hosts' view) CPL.
>>> >
>>> > This is a very tight corner case, since routers listen to RAs
>>> > in DNA, don't sleep, and routers should retract prefixes.
>>> >
>>> > At least with CompleteRA, you can ignore learned DNAO contents
>>> > since the rest of the CompleteRA will not match the existing
>>> > Complete Prefix List.
>
>>
>> I have difficulty following the above.
>>
>
>>>>> > >>A prefix which answers
>>>>> > >>"Yes" will supercede a "No" if it is received first.
>>>
>>>> > >
>>>> > >
>>>> > > I guess the same applies for "NO".
>>>> > >
>>>> > > "NO" will supercede a "YES", if it is received first, right?
>>
>>> >
>>> > Yes, but a false movement detection is actually better than a false
>>> > non-movement detection, since the host recovers in milliseconds, not
>>> > minutes.
>
>>
>> Does the above mean "NO" will always supercede "YES", because
>> a false movement detection is actually better than a false non-movement
>> detection?

>>
>
>>>> > > In the example I present the above, "NO" is the correct one and
>>>> > > doesn't result from "that a prefix's advertisement has not been

received

>>>> > > on the "No" router before the RS with a landmark query is sent."
>>
>>> >
>>> > I see your point: the most up-to-date router could respond "NO" based on
>>> > updated information.
>>> >
>>> > In that case though, it can also update the other routers with
>>> > the appropriate RA (prefix lifetime=0).
>
>>
>> Yes, but it needs additional mechanism to ensure every routers
>> will receive the appropriate RA.
>>
>
>>>> > > Correct me wrong but when I looked through Landmark/ CompleteRA
>>>> > > last time, I don't see any mechanism to deal with the case two routers
>>>> > > give conflicting answers, one yes and the other no. Such a case can
>>>> > > arise from a lack of synchronization.
>>
>>> >
>>> > Indeed, this is the same as LinkID, where the out-of-date LinkID is
>>> > still used by a router which has not seen the PIO with the prefix
>>> > retracted.
>>> >
>>> > While Prefix Landmarks can conceivably answer "Yes" incorrectly
>>> > in this case, so would some of the LinkID routers.
>
>>
>> As I wrote above, it will not affect DNA performance for Linkid.
>> Kindly look over the draft.
>>
>
>>> > A practical solution for Prefix Landmarks may be to partly
>>> > ignore "Yes" answers - since they don't require much action: that
>>> > is keep the DNA process open if there's a non-movement indication.
>>> >
>>> > The DNA addressing mechanism may be re-normalized (and packet flow can
>>> > occur with the global addresses), but subsequent reception of a
>>> > trusted "No" RA within (say 500ms) could be used as a hint to re-build
>>> > a CPL - which may be a cause to detect change in a few seconds.
>
>>
>> Maybe, but the scheme seems to become more complicated. At least, I
>> come to have difficulty following your arguments.
>>
>> Best Regards
>>
>> JinHyeock

JinHyeock Choi

Dear Brett


>>> > Answering "Yes" also takes definite knowledge and synchronization.
>>> >
>>> > Allow me an example. Assume a link with two routers R1 and R2.
>>> > R1 advertises Prefix1 and R2 advertise Prefix2 and Prefix3.
>>> > R1 and R2 gathers the prefixes to make the complete prefix list
>>> > {Prefix1, Prefix2, Prefix3}.
>>> >
>>> > Then R2 removes Prefix3 but the RA advertising the removal
>>> > was lost and R1 doesn't receive it. So afterwards, if a (dormant)
>>> > host send an RS with Prefix3 to R1, it will falsely answer "YES",
>>> > i.e. Prefix3 is in this link.
>>> >
>>> > Am I missing something?
>
>> 
>> Well, "YES" is the answer that LinkID would give too.  The LinkID would
>> not have changed on R1 and the host would correctly recognise that it is
>> NOT a link change.  So how is it better?


I gave the above example only to show that both "YES" and "NO" need
"definite knowledge and synchronization". I didn't give it to show linkid's 
superiority. (I'll prepare a better one. Just wait. :-)) 


>> You say that LinkID has a method to deal with changing prefixes.  Hosts
>> keep a record previously seen LinkIDs so that they can recognise
>> changes. Isn't this implicit in the CompleteRA aspect of the landmark
>> proposal?  Each of the prefixes can be thought of as a LinkID, and any
>> overlap between the prefixes in a CompleteRA and the prefixes that the
>> host has seen implies non-movement.


The problem is that such a overlapping prefix may not exist. 
For the CompleteRA or Landmark, there is no MOI (Message 
Order Independence) property. (Greg wrote a related draft.  
 http://www.ctie.monash.edu.au/dna/mmoi-draft-dont-distrib.pdf  )
 
In linkid scheme, when a linkid is changed, I take extra care 
to make it sure that there is at least one (old) linkid prefix 
that assures the hosts that this is linkid change without link change. 
(I was tempted to call such a prefix as a linking prefix, but 
dared not for the fear of confusion.  :-)  ) 

Correct me wrong, but in ComplteRA or Landmark, there is no 
mechanism which ensures that always such a linking (or overlapping) 
prefix exists.  
 

>> Putting aside, for the moment, cases where a prefix is moved to a new
>> link before its lifetime advertised on the old link has expired, your
>> own example shows how the Landmark part deals with changes effectively.
>> A YES answer will only occur if the prefix has been used on the link and
>> so will not be wrong in the sense that the current link is the same one
>> where the Landmark came from.  If that prefix is in the process of being
>> removed, then very soon a NO answer will arrive from the applicable
>> router informing the host of this and providing the prefixes that are
>> available.  Note also that the window of oportunity for this to happen
>> is quite small as the router that removed the prefix should advertise
>> this fact several times in a fairly short space of time so that all
>> of the routers on the link are aware of the change.


I can think of more pathological example easily by cut and paste from 
old DT ML.   

Assume a host having two prefix A and B, and making one address with
A and the other with B. Assume prefix A goes through prefix renumbering
and early reassignment and the host follows it. Then it will not perceive 
that it can't no longer use the address with prefix B:. 


>> Returning to cases where prefixes can be reasigned to a new link before
>> the expiry of a previously advertised valid lifetime on another link,
>> both of the proposals face the same issue and need to deal with it by
>> placing rules about how the reassignment is done.  If a host sees a
>> LinkID or a Landmark on one link, fails to see advertisements that the
>> valid lifetime has been shortened, and then sees the same LinkID /
>> Landmark on another link, they will fail to detect the link change.


Linkid draft sets the rule to prevent such a case. So I may say that 
Linkid is safe from flash renumbering and early reassignment, unless 
there is a human error, (from which no scheme can be safe 100 %.)  . 

Best Regards

JinHyeock.

JinHteock Choi

Dear Greg


>>> > It's my opinion that just the above two are too narrow a criteria,
>>> > (though I agree that both of them good). I think other criteria
>>> > such
>>> > as 'complexity (as Jak mentioned)' need to be considered. Kindly
>>> > allow me some time to contemplate other criteria.
>
>> 
>> Computational/Storage Complexity is simple to calculate.
>> 
>> Comparison of text or implementation LOCs doesn't help unless
>> direct comparison of complete schemes is possible though.
>> 
>> Please consider criteria though. We can work on the simple comparisons
>> first if need be.


I think that comparison needs to be made in whole aspect of schemes 
so that we can properly contemplate pro & con. Complexity may be 
a difficult one to measure (in number) but nevertheless an important factor
just like 'robustness'. 


>> I'll be travelling over the weekend, so that may slow things down.


I wish you have a nice trip. 

Best Regards

JinHyeock

JinHyeock Choi

Dear Jak


>> jak>> Why is this so important? I believe 802.16 (which I think you are
>> interested in) 


You know I do very much so.  :-)  


>> has bandwidths between 1 - 5 Mbps, and 3.9 G is up to 20
>> Mbps. 9.6 kbps links aren't really that important anymore.


My point is that, if we are to compare packet size as Greg suggested, 
we need to compare all the packet size coming from each scheme, 
not only the packet size of one RS/ RA exchange.  

Also I talked with WiBro/ 802.16 developers here and they don't like
spending bandwidth on Neighbor Discovery signaling messages. (maybe
that's because those messages use up broadcast bandwidth.)  

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

JinHyeock Choi

Jak


>> The minutes of the IETF 62 meeting show that I proposed taking FastRA out of
>> contention, because it is very link specific (it would not work for 3.9G for
>> example), and referring it to the proper link standardization group
>> (probably 802.21). 


I remember very well of it. You also kindly proposed to make 
an Informational RFC out of it. Also it was of much help for 
you to point out 802.21. 


>> Unfortuantely, there is no record of a consensus call on
>> this proposal in the minutes.  


Unfortunately, no action was taken.  :-( 

>> I'd like to renew my proposal and suggest to
>> the chairs that a consensus call be done at a convenient time.


ok. But before the decision is made, I expect a chance to present 
the scheme properly.  


>> We cannot make progress on getting this standard complete if discussion
>> never results in any decisions being made.


agree. It took us 3 meetings to make a decision on CPL.  :-( 

Best Regards

JinHyeock

JinHyeock Choi

Dear Sathya


>> If the LinkID is being chosen based on some rule (the smallest prefix in the Complete 
>> Prefix List) applied to the complete prefix list, then LinkID solution must also make sure 
>> that all the routers have the same list. I understand that the hosts maintain a LinkID list, 
>> but that doesn't make it OK to have routers in the same link to be advertising different LinkID.  


Actually it's ok. I designed Linkid such that hosts make a correct decision 
even under such a temporary asynchornization.   


>> (as an aside, it is more accurate to refer to this solution as LinkIDList - 
>> because AFAIK, the host, the router and the RA will contain a LinkIDList - 
>> the list may contain one or more entries - right?).


No, the routers use a single linkid prefix at any given time, 
but due to the possibility that the linkid prefix changing, 
the hosts track the set of linkid prefixes. You may check 
"Comments on linkid draft" thread in DT ML. (Actually this 
is the confusion I was afraid when Erik suggested the 
Linkid List idea.  :-(  )

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

JinHyeock Choi

Greg


>>> > No, it didn't make such a decision. (It's strange that it was claimed
>>> > that Linkid had been decided to be removed when I presented it. )
>
>> 
>> I'm referring to draft-pentland-mobileip-linkid-03.txt (which was on
>> the quoted list too).


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


>> [cut]
>
>>> >
>>> >   Fast advertisement:
>>> >       Fast Router Discovery
>>> >       Hash-ordered FastRA (is that a bit easier to say?   :)  )
>>> >       Probabilistic FastRA
>
>> [cut]
>> 
>> I think you miss the point.  FastRD was left in because it's
>> possible to apply, but it's not capable of being _the_ general
>> solution for DNA in all cases.
>>
>> Modification of Link-Layer devices is not an option for many
>> environments, so we need to rely upon a base solution which
>> only changes hosts and routers.
>> 
>> Optimizations beyond this would have to be specified separately.


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

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

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

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


>>> > ok. At this point, my assertion is only that
>>> > the above is a worthy criterion to consider when we evaluate
>>> > schemes.
>
>> 
>> Well, it's the same for both schemes, and therefore shouldn't
>> take up our highest priority (or any if we're pressed for time)...


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

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


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


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


>> From 4.2 it's not clear if the first RA received on the link
>> (if it advertises the old LinkID) is taken as non-movement, if the
>> host arrives from  the link to which this prefix has been
>> assigned (and is LinkID).
>> 
>> It looks like it is.
>> 
>> The host hasn't seen the other LinkID before, and when the next
>> RA arrives indicating the NewLinkID and OldLinkID, it could easily be
>> taken as a change of LinkID on the previously visited link.
>>
>> AFAICS, this is the exact same danger as described for Landmarks
>> (but not completeRA, due to the redundant information).


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


>>> > Yes, but it needs additional mechanism to ensure every routers
>>> > will receive the appropriate RA.
>
>> 
>> I'ts already defined.
>> 
>> 6.2.4.  Sending Unsolicited Router Advertisements
>> 
>> Especially the section describing advertising changes
>> 
>> It's optional but has been around for a long time, and
>> doesn't require additional text in DNA...


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


>>> > Maybe, but the scheme seems to become more complicated. At least, I
>>> > come to have difficulty following your arguments.
>
>> 
>> It's not particularly complicated:
>> 
>> If you receive an indication that no change is needed:
>> Don't change anything and start communicating again.
>> If you then receive an indication that change is needed,
>> it may be needed.
>> 
>> This is all to handle the concept of "Flash renumbering"
>> (still to be debated if it's a real issue (See section 12 of
>> RFC2461)) under "packet loss" of three packets or where routers
>> haven't followed the recommendation of RFC2461 section 6.2.6
>> 
>> Did we need to do anything anyway?
>> 
>> If we assume that routers follow RFC2461 6.2.6 if they're
>> flash renumbering (and we recommend it), then no live router
>> could advertise the wrong prefix with Landmarks, CompleteRA
>> or LinkID.


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

Thanks for your kind consideration. 

Best Regards

JinHyeock

Subba Reddy

Hi Satya,



>>
>>
>> ----- Original Message -----
>> From: JinHyeock Choi <jinchoe@gmail.com>
>> Date: Friday, July 22, 2005 1:53 am
>> Subject: Re: [DNA] DNA proposal issue 19 - was [Issue

X]LinkIDv.s.LandmarkPrefix

>>
>
>>> > Dear Sathya
>>> >
>>
>>>> > > So, in conclusion, the synchronization requirement and
>>>> > > complexity for Landmark, CompleteRA and LinkID are the same -
>>
>>> > all three
>>
>>>> > > of them require that all the routers on the link know about all the
>>>> > > prefixes on the link within a reasonable time - the difference
>>
>>> > is only
>>
>>>> > > in the content of the RS/RA messages. Do you agree?
>>
>>> >
>>> > No. Linkid draft deals with synchronization problem by taking
>>> > extra
>>> > care of linkid prefix with such schemes as "linkid prefix list" or
>>> > "linkid
>>> > prefix lifetime". It's my guess that, for CompleteRA or Landamrk,
>>> > such
>>> > extra cares need to be be applied to all the prefixes.
>>> >
>
>> If the LinkID is being chosen based on some rule
>> (the smallest prefix in the Complete Prefix List) applied to the complete

prefix list,

>> then LinkID solution must also make sure that all the routers have the

same list.

The prefix list can differ for sometime (1.5 hrs) because of additiion or
change in
prefix life time (i.e, if lifetime goes less than 3 hrs).


>> I understand that the hosts maintain a LinkID list, but that doesn't make

it OK

>> to have routers in the same link to be advertising different LinkID.


Routers can be advertising different LinkIDs at a given point of time.
But hosts will not make wrong decision because of LinkID list maintained at
host side.


>>(as an aside, it is more accurate to refer to this solution as LinkIDList -
>> because AFAIK, the host, the router and the RA will contain a LinkIDList -
>>the list may contain one or more entries - right?).
>>


This may not be correct. Most of the time only one LinkID will be there in
the LinkID
list. If the prefix list changes, which causes change in LinkID, only then
more than
one prefix will present in LinkID list. And this is a very rare case.


>> Sathya
>>
>>
>>


Thanks & Regards,
Subba Reddy

James Kempf

>has bandwidths between 1 - 5 Mbps, and 3.9 G is up to 20
>> Mbps. 9.6 kbps links aren't really that important anymore.


My point is that, if we are to compare packet size as Greg suggested,
we need to compare all the packet size coming from each scheme,
not only the packet size of one RS/ RA exchange.

jak>> But how often will this signaling take place? I think one must be
realistic about the critera. If the signaling only takes place every
handover, then I think that the size isn't really relevant, within reason of
course. We're not talking about a periodic beacon in that case.

jak>> To compare, 802.21 is talking about providing a way whereby, on each
handover, a mobile terminal could obtain information on wireless networks.
These information element laden messages are likely to be large. But the
frequency, AFICT, is exactly the same as for RS/RA. Noboby is worried about
reducing the size of these messages.

Also I talked with WiBro/ 802.16 developers here and they don't like
spending bandwidth on Neighbor Discovery signaling messages. (maybe
that's because those messages use up broadcast bandwidth.)

jak>> So it seems like there is an assumption that this signaling will take
place on the broadcast channel? Is that right? Has WiMax Forum already
decided to do IP signaling on the broadcast channel?

jak>> I think there are more important criteria, like backward
compatibility. How would each of these methods handle having a nonDNA router
on the link, or handover between a DNA link and a nonDNA link? These are the
kinds of issues that will negatively or positively impact deployment
potential, not whether one or the other technique has a couple fewer bytes
in the best case.

            jak

Greg Daley

Hi JinHyeock, 

----- Original Message -----
From: JinHyeock Choi <jinchoe@gmail.com>
Date: Saturday, July 23, 2005 1:19 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
LandmarkPrefix

>> Dear Greg
>> 
>
>>>> > > It's my opinion that just the above two are too narrow a 

criteria,

>>>> > > (though I agree that both of them good). I think other criteria
>>>> > > such
>>>> > > as 'complexity (as Jak mentioned)' need to be considered. Kindly
>>>> > > allow me some time to contemplate other criteria.
>>
>>> > 
>>> > Computational/Storage Complexity is simple to calculate.
>>> > 
>>> > Comparison of text or implementation LOCs doesn't help unless
>>> > direct comparison of complete schemes is possible though.
>>> > 
>>> > Please consider criteria though. We can work on the simple 
>>> > comparisons first if need be.
>
>> 
>> I think that comparison needs to be made in whole aspect of 
>> schemes so that we can properly contemplate pro & con.
>> Complexity may be a difficult one to measure (in number) but
>> nevertheless an important factor just like 'robustness'. 


I've made a first pass at complexity analysis (on all the schemes),
based on assumptions from computer science.  I'll pass these to 
you for comment.

These aren't based on the implementations, only on what is 
required for the drafts.

Does this sound like a good idea?

Greg

Greg Daley

Hi James, 

There are responses to the top and bottom of your e-mail.

Don't be too despondent until you read the last lines...

----- Original Message -----
From: James Kempf <Kempf@docomolabs-usa.com>
Date: Saturday, July 23, 2005 4:54 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
LandmarkPrefix

>>> > has bandwidths between 1 - 5 Mbps, and 3.9 G is up to 20
>>> > Mbps. 9.6 kbps links aren't really that important anymore.
>
>> 
>> My point is that, if we are to compare packet size as Greg suggested,
>> we need to compare all the packet size coming from each scheme,
>> not only the packet size of one RS/ RA exchange.
>> 
>> jak>> But how often will this signaling take place? I think one 
>> must be realistic about the critera. If the signaling only takes
>> place every handover, then I think that the size isn't really
>> relevant, within reason of course. We're not talking about a
>> periodic beacon in that case.


You're right that the burden isn't too great, but one thing touted
as an advantage for Landmarks is their smaller size (with a Yes reply).
So it's a legitimate factor (though not necessarily a big one).

Also, the background cost of LinkID and CompleteRA are relevant,
since there are BNEP bridges available...   

If we compare unsolicited RA overheads we need to stress that with
DNA, the unsolicited rate can be decreased and still receive good 
performance.  We can present the rates for default RFC2461 RA,
with default MinRtrAdvInterval and MaxRtrAdvInterval (in bps), 
given the sample scenarios.

The minimum RA interval values can be presented for comparison, 
with a disclaimer that these values may not be needed.

Does this sound reasonable? (regardless of its necessity??)

I'll see if I can do this for the agreed criteria, in order to
make this available to the list.  My aim here is to provide
enough information for the WG to make its own decision.

In this case, I guess there may not be much difference, but
removing the uncertainty may help the decision process.

[cut]

>> jak>> I think there are more important criteria, like backward
>> compatibility. How would each of these methods handle having a 
>> nonDNA router on the link, or handover between a DNA link and
>> a nonDNA link?  These are the kinds of issues that will
>> negatively or positively impact deployment potential, not whether
>> one or the other technique has a couple fewer bytes in the best case.


Your point is well taken.

I'll elicit help from others to facilitate this.

Greg

Greg Daley

Hi JinHyeock,

There are two parts to this e-mail.

one is related to procedures and FastRD, which I think is
fairly close to ending.

The other is answered partially, and should be answered
fully when I start a new thread on the topic.

----- Original Message -----
From: JinHyeock Choi <jinchoe@gmail.com>
Date: Saturday, July 23, 2005 3:46 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
Landmark Prefix
[cut]

>>> > [cut]
>>
>>>> > >
>>>> > >   Fast advertisement:
>>>> > >       Fast Router Discovery
>>>> > >       Hash-ordered FastRA (is that a bit easier to say?   :)  )
>>>> > >       Probabilistic FastRA
>>
>>> > [cut]
>>> > 
>>> > I think you miss the point.  FastRD was left in because it's
>>> > possible to apply, but it's not capable of being _the_ general
>>> > solution for DNA in all cases.
>>> >
>>> > Modification of Link-Layer devices is not an option for many
>>> > environments, so we need to rely upon a base solution which
>>> > only changes hosts and routers.
>>> > 
>>> > Optimizations beyond this would have to be specified separately.
>
>> 
>> As of my memory, in DT meeting, no such agreement (about why 
>> FRD is left) is made.   


It was left _in_, not _out_.

So it is still under consideration, but it is important to 
note (as I said above) that the scheme relies on
modified link-layer devices on the network side, so it
is important (IMO) to have a Base DNA protocol scheme which 
doesn't explicitly rely on the presence of FastRD to get
useful performance.

If the WG desires that FastRD is included in another document,
then that's OK.


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


You've received my (public) apology on that count (and my
statement that I was of good, if misguided intention), and my 
undertaking that I'll not interfere in any presentation or
decision making by the WG.


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


Yes.


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


I never did. Your own quotation of the e-mails describes this.

My only statements of FastRD's capabilities and reliances are those
of fact.
 

>>>> > > ok. At this point, my assertion is only that
>>>> > > the above is a worthy criterion to consider when we evaluate
>>>> > > schemes.
>>
>>> > 
>>> > Well, it's the same for both schemes, and therefore shouldn't
>>> > take up our highest priority (or any if we're pressed for time)...
>
>> 
>> This the the conclusion I can't be sure of. There may be a link 
>> in which CompleteRA can't be made as mentioned in Brett's draft
>> below,  
>> 
>>   It may not be possible to include all of the prefixes in use on the
>>   link due to MTU or administrative limitations.


Please let me make this clear then:

This is handled by falling back to CPL, and the RAs do not contain
completeness indications (i.e it is not a CompleteRA).
This is described in the draft (2nd paragraph of page 7, and 
fourth Paragraph of page 20).

Please notice that in the usual case, CompleteRA has the same
per-packet overhead as Prefix LinkIDs: none.  So in the usual case
the comments aren't applicable.

The MTU argument isn't useful for today's RAs and is present
mainly for future protection: 

For most deployments of routers:  say 4 distinct prefixes/link, the
maximum overheads for CompleteRA and LinkID aren't very different:

CompleteRA :- maximum 56 octets Max overhead/RA
LinkID:-  32 (64 transition) octets Max overhead/RA.

This assumes that each router advertises at least one prefix. 

Since SEND will add less than 632 octets (320 CGA option,
280 octets Signature option, 16 timestamp, 16 Nonce) even
with 2048bit RSA keys, there will still be 648 octets
left for the IPv6 header, RA header and options, if we
limit the RA to even the minimum IPv6 MTU (1280 octets).

With the headers, SLLAO and MIPv6 Advertisement Interval,
there are still 576 octets left for PIOs and DNAO or
LinkID LPIO options.

So the limitations have to be administrative today (due to 
storage or transmission limitations).

It's not going to take much/any text to describe
the tradeoff, if it's needed.


So, getting back to my main point:

The schemes (CompleteRA and LinkID) are the same for
unsolicited RA (disregarding co-existance and
synchronization issues).   So we really don't need
to identify one scheme as being better for 
unsolicited RAs.



[Beyond this point, most of the response will be dealt with
in a new thread.]

[cut]

>>> > 
>>> > 6.2.4.  Sending Unsolicited Router Advertisements
>>> > 
>>> > Especially the section describing advertising changes
>>> > 
>>> > It's optional but has been around for a long time, and
>>> > doesn't require additional text in DNA...
>
>> 
>> I meant to make it extra-sure that all routers have received the 
>> appropriate RA even under the packet loss. 6.2.4 is rather a UDP 
>> like and I meant a TCP like assurance. 


That's worth discussing as part of the comparison criteria.
(will start off-list).

[cut]

>>> > If we assume that routers follow RFC2461 6.2.6 if they're
>>> > flash renumbering (and we recommend it), then no live router
>>> > could advertise the wrong prefix with Landmarks, CompleteRA
>>> > or LinkID.
>
>> 
>> I have difficulty following your thoughts on the synchronization
>> issue for Landmark/ CompleteRA because new arguments pops 
>> up in each mail. It would help me a lot, if you summarize your 
>> thoughts in whole. 


When I've had all my thoughts on the subject, it will be December.
Certainly, new ideas of mine make it into the e-mails.

Sometimes, I think of an idea which is clearly better later.
I apologize if this makes things confusing.  I'll try to summarize
my current thoughts, so that we can make progress.

I'll do this in another mail though (for clarity).
It may have to wait until this evening though.

Greg

Brett Pentland


> I gave the above example only to show that both "YES" and "NO" need
> "definite knowledge and synchronization". I didn't give it to show linkid's superiority. (I'll prepare a better one. Just wait. :-)) 


:)

> Correct me wrong, but in ComplteRA or Landmark, there is no mechanism which ensures that always such a linking (or overlapping) prefix exists.  


That's almost the definition of Complete RA.  All routers should be
advertising the same set of prefixes so that pretty much ensures
overlap.  The only way for there not to be is for a router which has
no learned prefixes (ie. all of the prefixes it is advertising are
explicitly configured on it) to instantly stop advertising those
prefixes and start advertising a new set.  It's trivial to add a rule
to say don't do that.

>> Putting aside, for the moment, cases where a prefix is moved to a new
>> link before its lifetime advertised on the old link has expired, your
>> own example shows how the Landmark part deals with changes effectively.
>> A YES answer will only occur if the prefix has been used on the link and
>> so will not be wrong in the sense that the current link is the same one
>> where the Landmark came from.  If that prefix is in the process of being
>> removed, then very soon a NO answer will arrive from the applicable
>> router informing the host of this and providing the prefixes that are
>> available.  Note also that the window of oportunity for this to happen
>> is quite small as the router that removed the prefix should advertise
>> this fact several times in a fairly short space of time so that all
>> of the routers on the link are aware of the change.
>
>
>
> I can think of more pathological example easily by cut and paste from old DT ML.  
> Assume a host having two prefix A and B, and making one address with
> A and the other with B. Assume prefix A goes through prefix renumbering
> and early reassignment and the host follows it. Then it will not perceive that it can't no longer use the address with prefix B:. 


True, but LinkID doesn't prevent that either.  Both methods need to
manage that through the imposition of rules for renumbering, and the
setting of timeouts on DNA information.

>
>
>> Returning to cases where prefixes can be reasigned to a new link before
>> the expiry of a previously advertised valid lifetime on another link,
>> both of the proposals face the same issue and need to deal with it by
>> placing rules about how the reassignment is done.  If a host sees a
>> LinkID or a Landmark on one link, fails to see advertisements that the
>> valid lifetime has been shortened, and then sees the same LinkID /
>> Landmark on another link, they will fail to detect the link change.
>
>
>
> Linkid draft sets the rule to prevent such a case. So I may say that Linkid is safe from flash renumbering and early reassignment, unless there is a human error, (from which no scheme can be safe 100 %.)  . 


And those same rules apply equally well to Landmark/CompleteRA.

Brett. 

JinHyeock Choi

Dear Jak


>> My point is that, if we are to compare packet size as Greg suggested,
>> we need to compare all the packet size coming from each scheme,
>> not only the packet size of one RS/ RA exchange.
>> 
>> jak>> But how often will this signaling take place? I think one must be
>> realistic about the critera. If the signaling only takes place every
>> handover, then I think that the size isn't really relevant, within reason of
>> course. We're not talking about a periodic beacon in that case.


If we take into consideration unsolicted RA, we may need to talk about 
periodic beacon. 


>> jak>> So it seems like there is an assumption that this signaling will take
>> place on the broadcast channel? Is that right? Has WiMax Forum already
>> decided to do IP signaling on the broadcast channel?


It is not decided on yet. But if a node is to send, for example, an Neighbor
Solicitation message for DAD, broadcast channel seems to be needed. 
 

>> jak>> I think there are more important criteria, like backward
>> compatibility. How would each of these methods handle having a nonDNA router
>> on the link, or handover between a DNA link and a nonDNA link? These are the
>> kinds of issues that will negatively or positively impact deployment
>> potential, not whether one or the other technique has a couple fewer bytes
>> in the best case.


I see your point. Kindly allow me a question. 

Sathya asserted that efficient bandwidth utilization is a pro of 
Landmark/ CompleteRA over Linkid as below. 

   Prefix Landmark provides a way for the router to know whether the host
   with the 'landmark question' has changed link or not and build its
   (unicast-)RA accordingly, which I think will be very efficient in terms
   of bandwidth utilization as 'no link change' is more likely than not.  

From your stand toward packet size, I understand that you think 
the above is irrelevant for comparison. Right?

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

JinHyeock Choi

Dear Brett


>>> > Correct me wrong, but in ComplteRA or Landmark, there is no
>>> > mechanism which ensures that always such a linking (or overlapping)
>>> > prefix exists.
>
>> 
>> That's almost the definition of Complete RA.  All routers should be
>> advertising the same set of prefixes so that pretty much ensures
>> overlap.  The only way for there not to be is for a router which has
>> no learned prefixes (ie. all of the prefixes it is advertising are
>> explicitly configured on it) to instantly stop advertising those
>> prefixes and start advertising a new set.  It's trivial to add a rule
>> to say don't do that.


ok. Kindly add that rule and then we may resume this discussion. 


>>> > Assume a host having two prefix A and B, and making one address with
>>> > A and the other with B. Assume prefix A goes through prefix renumbering
>>> > and early reassignment and the host follows it. Then it will not perceive
>>> > that it can't no longer use the address with prefix B:.
>
>> 
>> True, but LinkID doesn't prevent that either.  Both methods need to
>> manage that through the imposition of rules for renumbering, and the
>> setting of timeouts on DNA information.


No, Linkid has a rule to prevent "Renumbering and Early reassignment." 


>>> > Linkid draft sets the rule to prevent such a case. So I may say that
>>> > Linkid is safe from flash renumbering and early reassignment, unless
>>> > there is a human error, (from which no scheme can be safe 100 %.)  .
>
>> 
>> And those same rules apply equally well to Landmark/CompleteRA.


Maybe. Then kindly also write down those rules in the draft. I will be 
happy if you also adopt the similar rule for Landmark/ CompleteRA. 

Best Regards

JinHyeock

JinHyeock Choi

Dear Greg


>>> > As of my memory, in DT meeting, no such agreement (about why
>>> > FRD is left) is made.
>
>> 
>> It was left _in_, not _out_.
>> 
>> So it is still under consideration, but it is important to
>> note (as I said above) that the scheme relies on
>> modified link-layer devices on the network side, so it
>> is important (IMO) to have a Base DNA protocol scheme which
>> doesn't explicitly rely on the presence of FastRD to get
>> useful performance.
>> 
>> If the WG desires that FastRD is included in another document,
>> then that's OK.
>> 
>
>>> > An unfortunate incident in D.C. made a paranoid out of me, so
>>> > I took keen notice about FRD treatment.
>
>> 
>> You've received my (public) apology on that count (and my
>> statement that I was of good, if misguided intention), and my
>> undertaking that I'll not interfere in any presentation or
>> decision making by the WG.
>> 
>
>>> > About the FRD applicability, that's the decision for WG. If WG
>>> > chooses FRD for its high performance in spite of L2 reliance,
>>> > it's WG's call.
>
>> 
>> Yes.
>> 
>
>>> > It's ok for you have an opinion about FRD and its treatment but
>>> > I ask you NOT to assume it as an official agreement before going
>>> > through a proper decision procedure.
>
>> 
>> I never did. Your own quotation of the e-mails describes this.


Unfortunately I got the impression you did. When I mentioned that WG didn't 
make a decision that FRD is not under consideration for the main DNA solution, 
you wrote that WG decided at Minneapolis. If that impression was not intended,  
we agreed that WG didn't make a decision on FRD yet, right? In case, I wish
we close this not-so-pleasant issue here. 


>>>> > > Well, it's the same for both schemes, and therefore shouldn't
>>>> > > take up our highest priority (or any if we're pressed for time)...
>>
>>> >
>>> > This the the conclusion I can't be sure of. There may be a link
>>> > in which CompleteRA can't be made as mentioned in Brett's draft
>>> > below,
>>> >
>>> >   It may not be possible to include all of the prefixes in use on the
>>> >   link due to MTU or administrative limitations.
>
>> 
>> Please let me make this clear then:
>> 
>> This is handled by falling back to CPL, and the RAs do not contain
>> completeness indications (i.e it is not a CompleteRA).
>> This is described in the draft (2nd paragraph of page 7, and
>> fourth Paragraph of page 20).
>> 
>> Please notice that in the usual case, CompleteRA has the same
>> per-packet overhead as Prefix LinkIDs: none.  So in the usual case
>> the comments aren't applicable.
>> 
>> The MTU argument isn't useful for today's RAs and is present
>> mainly for future protection:
>> 
>> For most deployments of routers:  say 4 distinct prefixes/link, the
>> maximum overheads for CompleteRA and LinkID aren't very different:
>> 
>> CompleteRA :- maximum 56 octets Max overhead/RA
>> LinkID:-  32 (64 transition) octets Max overhead/RA.
>> 
>> This assumes that each router advertises at least one prefix.
>> 
>> Since SEND will add less than 632 octets (320 CGA option,
>> 280 octets Signature option, 16 timestamp, 16 Nonce) even
>> with 2048bit RSA keys, there will still be 648 octets
>> left for the IPv6 header, RA header and options, if we
>> limit the RA to even the minimum IPv6 MTU (1280 octets).
>> 
>> With the headers, SLLAO and MIPv6 Advertisement Interval,
>> there are still 576 octets left for PIOs and DNAO or
>> LinkID LPIO options.
>> 
>> So the limitations have to be administrative today (due to
>> storage or transmission limitations).
>> 
>> It's not going to take much/any text to describe
>> the tradeoff, if it's needed.
>> 
>> So, getting back to my main point:
>> 
>> The schemes (CompleteRA and LinkID) are the same for
>> unsolicited RA (disregarding co-existance and
>> synchronization issues).   So we really don't need
>> to identify one scheme as being better for
>> unsolicited RAs.


The above analysis is dependent on # prefixes on a link. When I worked 
on CompleteRA, some DT members showed concern for the link with 
high # prefixes. 

Also I think we'd better have this kind of discussion to investigate whether 
unsoilcted RA differentiates or not first, before jumping to the conclusion
that unsolicited RA is irrelevant. 

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

JinHyeock Choi

Dear Erik


>>> > Linkid deals with this problem with special schemes as as Linkid prefix
>>> > list and a few advertisement rules, such as keep advertising old linkid
>>> > after a linkid change for the time being. But for CompleteRA (also for
>>> > Landmark), as of my knowledge, no such mechanism is devised yet,
>>> > though I myself had worked on it before I switched to linkid. My thought
>>> > is that it's easier to synchronize one prefix rather than synchronize all
>>> > the prefixes on the link.
>
>> 
>> I'm not sure it is conceptually simpler to synchronize one item chosen
>> from a set, than forming the set.


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. 


>> In the latter case each router forms the union of its own advertised
>> prefixes and the prefixes it receives in RAs. Thus there can be no
>> conflict; there is no selection of a prefix.
>> 
>> In the former case, there can be transients when the sending and
>> receiving router have a different idea of what the selected linkID
>> prefix should be, thus one needs to worry about how such transients are
>> handled. 


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. 


>> (One can avoid that complexity by not trying to form a single
>> linkID all the time, but instead let each router picks its own linkID
>> prefix and tell the other routers. I haven't worked out the details of
>> such a scheme though.)


I thought it simpler to make routers agree on the same selection
scheme but would like to hear your scheme when developed. 

Thanks for your kind consideration. 

Best Regards

JinHyeock

Brett Pentland

JinHyeock Choi wrote:

> Dear Erik
>
>
>>> Linkid deals with this problem with special schemes as as Linkid prefix
>>> list and a few advertisement rules, such as keep advertising old linkid
>>> after a linkid change for the time being. But for CompleteRA (also for
>>> Landmark), as of my knowledge, no such mechanism is devised yet,
>>> though I myself had worked on it before I switched to linkid. My thought
>>> is that it's easier to synchronize one prefix rather than synchronize all
>>> the prefixes on the link.
>>
>>
>> I'm not sure it is conceptually simpler to synchronize one item chosen
>> from a set, than forming the set.
>
>
>
> 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)

   If a prefix is added the host will have no knowledge of it and so
   it won't be involved in the decision making process at all.

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.

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.

I hope I've got that right.  Can you see any faults?
Cheers,
Brett. 

Syam Madanapalli

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.

>
>    If a prefix is added the host will have no knowledge of it and so
>    it won't be involved in the decision making process at all.
>
> 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.


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.

>
> 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 hope I've got that right.  Can you see any faults?
> Cheers,
> Brett.

Erik Nordmark

JinHyeock Choi wrote:

> No, Linkid has a rule to prevent "Renumbering and Early reassignment." 


I agree that Linkid (as well as CPL I think) has a recommendation to the administrator to not reassign a prefix to another link in less than 3 hours.
I'm not sure the same text is in the landmark draft yet, but it would be trivial to add.

But my concern is what happens should the administrator not follow this recommendation.

The worst case would be when P1 and P2 are assigned to link1, and P2 is immediately reassigned to link3 (which had prefix P3 before), at about the same time that the a host moves from link1 to link3.

In that case, any prefix based scheme for link identification (CPL, landmark, linkid, or anything else we can invent) can get into trouble, by the host assuming that P1, P2, and P3 are assigned to link3.

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

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

But the problem certainly isn't specific to any particular proposal, since they all rely on prefixes for link identification. And I suspect that we have the same choices in terms of solutions independent of which proposal we apply this to.

   Erik 

Tero Kauppinen

>But the problem certainly isn't specific to any particular proposal,
>> since they all rely on prefixes for link identification. And I suspect
>> that we have the same choices in terms of solutions independent of

which

>> proposal we apply this to.
>> 
>>     Erik


Erik is absolutely right. I now remember faintly discussing this matter
with Jari and Pekka a long time ago. I think we were wondering and
playing with the idea that maybe the DNA process should consider using
hints from different entities (e.g. TCP timeout, MobileIPv6) in addition
to the link layer. The problem, I guess, in such an approach would be
how to prevent the solution from not being too vague or abstract.

Tero

Erik Nordmark

Syam Madanapalli wrote:

> 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.


Syam,
You keep making this statement, but I think it is factually incorrect. See my other email responding to JinHyoeck.

  Erik

Greg Daley

Hi Erik, 

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

>> JinHyeock Choi wrote:
>> 
>
>>> > No, Linkid has a rule to prevent "Renumbering and Early 
>
>> reassignment." 
>> 
>> I agree that Linkid (as well as CPL I think) has a recommendation 
>> to the administrator to not reassign a prefix to another link in 

less 

>> than 3 hours.
>> I'm not sure the same text is in the landmark draft yet, but it 
>> would be trivial to add.
>> 
>> But my concern is what happens should the administrator not follow 
>> this recommendation.
>> 
>> The worst case would be when P1 and P2 are assigned to link1, and 
>> P2 is immediately reassigned to link3 (which had prefix P3 before), 

at 

>> about the same time that the a host moves from link1 to link3.
>> 
>> In that case, any prefix based scheme for link identification 
>> (CPL, landmark, linkid, or anything else we can invent) can get into 
>> trouble, by the host assuming that P1, P2, and P3 are assigned to 

link3.

>> 
>> Should this happen, then the host will assume that P1 is usable 
>> until the last valid/preferred lifetimes it saw has expired. Since 

RFC 

>> 2461 suggests a default preferred lifetime of 7 days, the host will 

try 

>> to use P1 as a source address for 7 days, even though no packets 
>> returned to P1 will make it back to the link to which the host is
>> attached.


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)

If the readvertisement schemes for routers override bad state
for the hosts, The lifetime for bad information is less than:

(Router out-of-date timer) + (MaxRtrAdvInterval * ROBUSTNESS)

By this time, the host should be updated, with fresh state.
This time is actually related to the readvertising router's actual
configuration timers (rather than defaults, etc), so it may be 
significantly lower than the previous cost.

So if Router out-of-date timer = 1800s (MAXRA) and Host out-of-date 
timer=3600s
(2x MAXRA).  This assumes fairly reliable transmission between routers
(potentially 2 x MAXRA for routers though)).

Overall the possibility for out of date information is reduced to 2 
hours
after change (in that situation, and potentially, 1 hour and a very 
few seconds
if the override mechanism is possible).

Greg

Greg Daley

Hi JinHyeock,

----- Original Message -----
From: JinHyeock Choi <jinchoe@gmail.com>
Date: Monday, July 25, 2005 3:11 pm
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
Landmark Prefix

>> Dear Greg
>> 
>
>>>> > > As of my memory, in DT meeting, no such agreement (about why
>>>> > > FRD is left) is made.
>>
>>> > 
>>> > It was left _in_, not _out_.
>>> > 
>>> > So it is still under consideration, but it is important to
>>> > note (as I said above) that the scheme relies on
>>> > modified link-layer devices on the network side, so it
>>> > is important (IMO) to have a Base DNA protocol scheme which
>>> > doesn't explicitly rely on the presence of FastRD to get
>>> > useful performance.
>>> > 
>>> > If the WG desires that FastRD is included in another document,
>>> > then that's OK.
>>> > 
>>
>>>> > > An unfortunate incident in D.C. made a paranoid out of me, so
>>>> > > I took keen notice about FRD treatment.
>>
>>> > 
>>> > You've received my (public) apology on that count (and my
>>> > statement that I was of good, if misguided intention), and my
>>> > undertaking that I'll not interfere in any presentation or
>>> > decision making by the WG.
>>> > 
>>
>>>> > > About the FRD applicability, that's the decision for WG. If WG
>>>> > > chooses FRD for its high performance in spite of L2 reliance,
>>>> > > it's WG's call.
>>
>>> > 
>>> > Yes.
>>> > 
>>
>>>> > > It's ok for you have an opinion about FRD and its treatment but
>>>> > > I ask you NOT to assume it as an official agreement before going
>>>> > > through a proper decision procedure.
>>
>>> > 
>>> > I never did. Your own quotation of the e-mails describes this.
>
>> 
>> Unfortunately I got the impression you did. When I mentioned that 
>> WG didn't make a decision that FRD is not under consideration for
>> the main DNA solution, you wrote that WG decided at Minneapolis.
>> If that impression was not intended, we agreed that WG didn't make
>> a decision on FRD yet, right? In case, I wish
>> we close this not-so-pleasant issue here. 


OK.


[cut]

>>> > So, getting back to my main point:
>>> > 
>>> > The schemes (CompleteRA and LinkID) are the same for
>>> > unsolicited RA (disregarding co-existance and
>>> > synchronization issues).   So we really don't need
>>> > to identify one scheme as being better for
>>> > unsolicited RAs.
>
>> 
>> The above analysis is dependent on # prefixes on a link. When I 
>> worked on CompleteRA, some DT members showed concern for the
>> link with high # prefixes. 


Certainly, but the fallback case is also described with CPL.
Each router is able to make an assessment if it can support the
complete number of Prefixes.  Any single router which can take
the load can send the RA as complete.  This will work so long as the 
prefixes are advertised by at least one router on the link.

Advertisement of a subset of the prefixes is even possible
(without coordination) if the cost of completeRA is too high

At the moment DNAO costs floor( ((#prefix * 17)+ 2+7)/ 8) octets.
for all additional prefixes advertised.   That's pretty
efficient compared to PIO.

Even more efficient schemes have been described - 
floor (((#prefix *9)+3+7)/8) octets)
- variant 2.

Given the size of the packets available in IPv6, the larger
option ( even with 6 native PIO prefixes) that can fit 
22 learned prefixes in the DNAO, even with the nastiest SEND
scenario I could describe.

That's a big # of prefixes.

As described before, this is not going to happen on any
well designed network.  We can even add 2 lines to help 
describe network configurations which are bad for this.


>> Also I think we'd better have this kind of discussion to 
>> investigate whether unsoilcted RA differentiates or not
>> first, before jumping to the conclusion that unsolicited
>> RA is irrelevant. 


OK, but except in never deployed pathological cases, 
CompleteRA is able to provide the same function as LinkID 
(with additional completeness for CPL).

Greg

Brett Pentland

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.  When the subsequent NO answer arrives, the accompanying
prefixes will also show that there has been no link change and the
NO on that particular prefix gives the _additional information_ that it
is no longer valid (though the extra information is not necessary
because the second RA will have that expressed with a P1 PIO with zero
lifetime).  LinkID gives the same result.

>> 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.
>
>
>
> 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.

>>
>> 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.

Brett. 

Erik Nordmark

JinHyeock Choi wrote:

> We can't avoid a temporary flapping for the related set, the set of
> all prefixes
> on a link. 


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.

> 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.


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.

> 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.)

> 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.

> 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. :-)

   Erik 

Erik Nordmark

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?

   Erik

> If the readvertisement schemes for routers override bad state
> for the hosts, The lifetime for bad information is less than:
>
> (Router out-of-date timer) + (MaxRtrAdvInterval * ROBUSTNESS)
>
> By this time, the host should be updated, with fresh state.
> This time is actually related to the readvertising router's actual
> configuration timers (rather than defaults, etc), so it may be significantly lower than the previous cost.
>
> So if Router out-of-date timer = 1800s (MAXRA) and Host out-of-date timer=3600s
> (2x MAXRA).  This assumes fairly reliable transmission between routers
> (potentially 2 x MAXRA for routers though)).
>
> Overall the possibility for out of date information is reduced to 2 hours
> after change (in that situation, and potentially, 1 hour and a very few seconds
> if the override mechanism is possible).
>
> Greg

JinHyeock Choi

Dear Erik


>>> > 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.
>
>> 
>> Syam,
>> You keep making this statement, but I think it is factually incorrect.
>> See my other email responding to JinHyoeck.


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. 

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.   

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

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 


>> -----Original Message-----
>> From: James Kempf [mailto:Kempf@docomolabs-usa.com] 
>> Sent: Sunday, July 31, 2005 1:16 PM
>> To: Bound, Jim; dna@eng.monash.edu.au
>> Subject: Re: [DNA] Landmark vs Link-ID prefix solution
>> 
>> 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

Greg Daley

Hi Jim,

Bound, Jim wrote:
[cut]

> 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.


Actually, I see things differently.

In my personal opinion, most of the e-mails have been trying
very hard to differentiate the protocols.  Possibly we've been
trying too hard - and that doesn't help people reading the threads.

I guess this gives the impression that the protocol work is incomplete.
Rather, I think the solutions may end up being over-engineered if
we try to handle each of the smallest corner cases (just to show
one as better than another).

Given that we have two protocols which achieve primarily the same
outcome (both have running code), what I think we need now
is to generate a quick comparison (currently under development),
show the WG the solutions and their summarized properties, and
make a consensus call.

[cut]
> 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.

Yes there's a compromise possible, but I think we should look at
whether either is acceptable to the WG.  Your review would be
particularly welcome.  Thursday may help clarify which document to
review (but it may take a couple of weeks to get the consensus call
comleted, if there's no clear sense of the room).

> 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?


Personally, I'd like to get the WG document drafted in the coming
month, so we've got a chance to get the documents finished this year.


> 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.


From my knowledge no contributor to the discussion of Link
Identification has IPR.  That doesn't mean someone
else couldn't though (same as everything).

People are reminded of the IETF Note Well statement regarding IPR:

http://www.ietf.org/overview.html

Greg 

JinHyeock Choi

Dear Jim

Thanks for your detailed feedback. 


>> 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.


It would be very nice to have feedback from people building mobile networks. 
I guess mobile operators (and mobile equipment vendors) would be an important 
(maybe the most important) customers for DNA solution, so their opinions 
would be of much value.  


>> 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.


There is no IPR attached to LinkID. 

Thanks for your kind consideration. 

Best Regards

JinHyeock

JinHyeock Choi

Dear Erik


>>>> >>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.


I see. The "lack of Link UP" can tell host that there is no link change. 


>>> > 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.


Yes, this is possible. I meant it to reduce Link UP dependece and 
assumed there would be more frequent RAs as defined in MIPv6. 


>>> > 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?


Yes. Link UP is needed for legacy links. 

Thanks for your kind consideration. 

Best Regards

JinHyeock

Greg Daley

Hi Subba,

I think we've got one issue left.

[cut]

>> 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.


RFC 2461 doesn't place any ordering requirements on options in transmitted
RAs.  This is deliberately stated in that document.  I'm not sure
existing implementations would necessarily be well served in requiring such ordering.

Additionally, the existing LinkID draft doesn't have this assumption.
So if an issue is adopted for LinkID, and there's agreement that this
transmission is required, it will be O(1).

Currently it is O(p_r), I think.  The difference is very small,
considering the number of advertised prefixes in any RA will be low.

Greg 

Subba Reddy

Hi Greg,


>> I think we've got one issue left.


Yes.


>>
>> [cut]
>
>>>> >>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.
>
>>
>> RFC 2461 doesn't place any ordering requirements on options in transmitted
>> RAs.  This is deliberately stated in that document.  I'm not sure
>> existing implementations would necessarily be well served in requiring
>> such ordering.
>>
>> Additionally, the existing LinkID draft doesn't have this assumption.
>> So if an issue is adopted for LinkID, and there's agreement that this
>> transmission is required, it will be O(1).


I agree with your point that there is no ordering requirements for options.
I feel it as more implementation specific. I think, optimistic way is
considered
in the analysis (like hash list for DNAPrefixList, one LinkID in the
LinkIDPrefixList).
Please correct me, if wrong.

So, it may be better to consider this also in the similar way.


>>
>> Currently it is O(p_r), I think.


Yes.


>> The difference is very small,
>> considering the number of advertised prefixes in any RA will be low.
>>


Difference is small, but when we consider the complexity analysis, we feel
like
there is a difference between constant time and linear time.

Thanks & Regards,
Subba Reddy

Brett Pentland

Hi Jim,

Thanks very much for your feedback.  I think that part of the difficulty
with the discussion on the list is that we are comparing solutions
that are really very similar (and in fact there are others that could
be made to work fairly well too).

For both of the proposals, the routers on a link need to monitor what
the other routers are doing, and for compatibility with non-DNA-enhanced
routers both proposals, rely on CPL which requires the hosts to monitor
all of the prefixes as well.  The differences are in which bits of the
information get exchanged.

Because the differences are not dramatic the discussion has focussed
on a search for corner cases where one does better than the other and
maybe this focus on minutae has muddied the waters more than clearing
them.

I've got a couple of questions for you below.

Thanks again for your review.
Brett.

PS.  I'm not aware of any IPR encumberences on any of these ideas.

Bound, Jim wrote:

> 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.


I'm not sure I understand the comment about modifying the current RA.
Are you referring to the addition of the Landmark Option, the suggestion
that PIOs, etc. need not be included if the answer to the landmark
question is "yes", or something else?

>  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"


Can you say what it is about mesh networks that Link-ID serves well?
Maybe it's something that we haven't fully considered and it would be
useful to know more about it.


Greg Daley

Hi Subba,

[cut]

> I agree with your point that there is no ordering requirements for options.
> I feel it as more implementation specific. I think, optimistic way is
> considered in the analysis (like hash list for DNAPrefixList, one LinkID

> in the LinkIDPrefixList).

> Please correct me, if wrong.
>
> So, it may be better to consider this also in the similar way.


You're not wrong.

Previously with hashing, that was the mean case - O(1), as based on
several existing hashing algorithms.   If there is no known ordering
on a list of options, then there has to be traversal of the list in
general.

While it is on average O(p_r/2), O(p_r/2) is also conventionally noted
O(p_r).

That's why I said it was linear...

>> Currently it is O(p_r), I think.
>
>
>
> Yes.


Greg

Subba Reddy

Hi Greg,

<cut>

>> Previously with hashing, that was the mean case - O(1), as based on
>> several existing hashing algorithms.   If there is no known ordering
>> on a list of options, then there has to be traversal of the list in
>> general.
>> 
>> While it is on average O(p_r/2), O(p_r/2) is also conventionally noted
>> O(p_r).
>> 
>> That's why I said it was linear...
>> 


If traversal is required, I agree with linear. 
What I am saying is, if implementations 
(router side, anyway they are changing RA) can take
advantage by putting LinkID as the first prefix, complexity will come 
down to constant. 
For general case, linear is fine.

Thanks & Regards,
Subba Reddy






















Back to DNA Solution1 Issue Tracker

Topic DNASoln1Issue019 . { Edit | Attach | Ref-By | Printable | Diffs | r1.10 | > | r1.9 | > | r1.8 | More }
Revision r1.10 - 03 Aug 2005 - 10:34 GMT - Main.BrettPentland
Parents: WebHome > DNASolution1
Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.