Subject: [DNA] [Issue X] LinkID v.s. Landmark Prefix

From: James Kempf <[email-masked]>
Date: Mon, 18 Jul 2005 14:33:53 -0700

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

---

From: Brett Pentland <[email-masked]>
Date: Tue, 19 Jul 2005 17:08:32 +1000

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.

---

From: Greg Daley <[email-masked]>
Date: Tue, 19 Jul 2005 17:31:15 +1000

Hi Brett,

Thanks for creating the issue.

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

> 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

---

From: Sathya Narayanan <[email-masked]>
Date: Tue, 19 Jul 2005 11:10:25 -0400

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

---

From: James Kempf <[email-masked]>
Date: Tue, 19 Jul 2005 09:30:34 -0700

Greg,

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

            jak

----- Original Message -----
From: "Greg Daley" <[email-masked]>
To: "Brett Pentland" <[email-masked]>
Cc: "James Kempf" <[email-masked]>; "Dna" <[email-masked]>
Sent: Tuesday, July 19, 2005 12:31 AM
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s.
Landmark Prefix

---

From: JinHyeock Choi <[email-masked]>
Date: Wed, 20 Jul 2005 01:50:46 +0900

Dear Jak

Thanks for your detailed comments. 

> reasonable responses, 
> and I'm not interested in getting into a long email

I think you may overestimate me. I am prepared to yield to the case 
which LinkId can't handle reasonably. 

> Landmark Prefix. 

We are in disagreement here. 

draft-pentland relies not only landmark but also CompleteRA. (I guess
Landmark/ CompleteRA may be the more proper term.)

I think CompleteRA by itself is more complex than LinkID. (That's 
why I switched to Linkid.  As you may know, I've played with CompleteRA 
quite long in DT)

> draft-jinchoi requires 22 pages just to describe the link
> hold up if one went through in more detail. 

I don't think page count is a proper measure of complexity. It may 
result from either my poor English composition or more mature 
protocol specification. 

Also I point out the scheme is implemented with the code size 
390 lines for router & 160 lines for host, which, I think, is not 
too much complicated. We may count code lines instead. 

> There's a lot of special case

Kindly designate in more detail.  Many new notions in LinkID is also 
needed in Landmark/ CompleteRA (though in different language). 
For the case of Linkid lifetime, Landmark/ CompleteRA also adopts
a similar notion like below. 

   Prefix information entry MUST be removed from the DNAPrefixList when
   its valid lifetime expires or if the entry has not been refreshed in
   the last 1.5 hours.

Moreover I point out Landmark/ CompleteRA needs more new 
messages.  

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

Though I am in favor of Linkid, I don't think we have made 
a proper comparison yet.  

Thanks in advance for your kind consideration. 

Best Regards

JinHyeock

---

From: JinHyeock Choi <[email-masked]>
Date: Wed, 20 Jul 2005 01:51:39 +0900

Dear Sathya

> of bandwidth utilization as 'no link change' is more likely than not. I

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

---

From: JinHyeock Choi <[email-masked]>
Date: Wed, 20 Jul 2005 01:51:22 +0900

Dear Greg
 
> 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

> if a link-hint is received again (even if the host moves to a non-DNA

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. 
 
> Prefix LinkIDs cannot agree easily with existing non-DNA routers on the

It can. It will simply pick the smallest prefix. 

Best Regards

JinHyeock

---

From: JinHyeock Choi <[email-masked]>
Date: Wed, 20 Jul 2005 01:51:02 +0900

Dear Brett

> 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

---

From: Sathya Narayanan <[email-masked]>
Date: Tue, 19 Jul 2005 13:15:45 -0400

JinHyeock Choi wrote:

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

---

From: Sathya Narayanan <[email-masked]>
Date: Tue, 19 Jul 2005 13:34:24 -0400

Dear JinHyeock -

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

---

From: Syam Madanapalli <[email-masked]>
Date: Tue, 19 Jul 2005 23:35:59 +0530

Hi Greg, 

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

> if a link-hint is received again (even if the host moves to a non-DNA

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.

> 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

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

---

From: Syam Madanapalli <[email-masked]>
Date: Tue, 19 Jul 2005 23:44:17 +0530

Hi Sathya,

<cut>

> As I mentioned in the earlier

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

---

From: Sathya Narayanan <[email-masked]>
Date: Tue, 19 Jul 2005 14:45:44 -0400

Syam -

>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

---

From: James Kempf <[email-masked]>
Date: Tue, 19 Jul 2005 12:54:17 -0700

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

---

From: Greg Daley <[email-masked]>
Date: Wed, 20 Jul 2005 09:12:52 +1000

Hi JinHyeock,

JinHyeock Choi wrote:
[cut]
> Linkid between Landmark/ CompleteRA

OK.  That's a fair opinion.

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

> 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

---

From: Greg Daley <[email-masked]>
Date: Wed, 20 Jul 2005 09:43:05 +1000

Hi Syam,

Once again, I'm expressing personal opionions only.

Syam Madanapalli wrote:
[cut]
> 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.

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

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

> 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

---

From: Greg Daley <[email-masked]>
Date: Wed, 20 Jul 2005 10:59:59 +1000

Dear JinHyeock,

> why I switched to Linkid.  As you may know, I've played with CompleteRA 

CompleteRA is not significantly more difficult.

The only difference between storage of information in either CompleteRA
or LinkID is that routers have to keep (at least) the two smallest
Prefixes with LinkID, and that CompleteRA has to keep all prefixes
(on the router side).

The storage and comparison requirements are quite similar,
especially on the host, where the CPL (+CCL) must be kept anyway.

In fact, the Landmark and CompleteRA have exactly the same state
requirements, and share space and implementation code in my RADVD patch.

So overall, the cost of storage for the combined Landmark+CompleteRA
solution is comparable to the LinkID solution.

> too much complicated. We may count code lines instead. 

Please don't count code lines, I've not got the time to program
succinctly :)

Please also be aware that my code contains CPL (on the host side - the
most complicated part), event processing, router solicitation etc...

On the router side, I've implemented FastRA, CompleteRA+Landmarks,
token bucket schemes, new scheduling algorithms for RAs.

It's not an apples-to-apples comparison (although you're free
to peruse the code).

If the text length isn't valid for comparison, and the code lines
aren't either, we'll have to work on the properties exhibited by
the proposals.

> Moreover I point out Landmark/ CompleteRA needs more new 

Neither needs more messages. Both define new options and flags.

Protocol-01 only needs an additional option for landmarking.

I've previously described an alternative to the protocol-00, which
used the same option format for DNAO and Landmark option.
This was discussed on the ML and rejected since it unnecessarily
overloaded the function of the DNA and Landmark options.

So while there is an additional option, the agreement on-list
was that things were made simpler by having separate options.
Now having implemented this, I tend to agree (there wasn't
significant additional cost with 2 options - and I'd implemented
both ways).

It's worth mentioning that protocol2-01's issue 007 recommends
adding a LinkID prefix option, anyway.

The DNAO is equivalent to the LPIO, since all native (not learned)
prefixes in PrefixLinkID and CompleteRA are sent in their original
PIO (with a flag for LinkID).

The only difference between LPIO and DNAO is that it is possible
to have up to two fixed sized LPIOs in LinkID, and up to one
variable sized DNAO (only for learned prefixes).  Neither scheme
advertises LPIO or DNAO if the RA already contains all relevant
prefixes.

Arguing that one is more complicated than the other is likely
to be inaccurate, as you're able to ascertain yourself from the
published code.

> Though I am in favor of Linkid, I don't think we have made 

Fair enough.  I think we've got some time to process this still.

Greg

---

From: Syam Madanapalli <[email-masked]>
Date: Wed, 20 Jul 2005 09:12:20 +0530

Hi Sathya,

> 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

---

From: Subba Reddy <[email-masked]>
Date: Wed, 20 Jul 2005 10:05:02 +0530

Hi Greg,

<cut>

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

> CompleteRA has this at potentially greater prefix advertisement cost.

Thanks & Regards,
Subba Reddy

---

From: Greg Daley <[email-masked]>
Date: Wed, 20 Jul 2005 14:43:53 +1000

Hi Subba,

Subba Reddy wrote:
[cut]
> 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

---

From: Subba Reddy <[email-masked]>
Date: Wed, 20 Jul 2005 10:12:56 +0530

Hi Greg,

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

Thanks & Regards,
Subba Reddy

---

From: Greg Daley <[email-masked]>
Date: Wed, 20 Jul 2005 14:54:39 +1000

Hi Subba,

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

Subba Reddy wrote:
>>>sent by non-DNA routers in finding the link change (if they are using
> 
> 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

---

From: Subba Reddy <[email-masked]>
Date: Wed, 20 Jul 2005 11:20:10 +0530

Hi Greg,

> Please excuse my terseness.

I can understand. No problem.

> 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 & Regards,
Subba Reddy

---

From: Syam Madanapalli <[email-masked]>
Date: Wed, 20 Jul 2005 11:27:51 +0530

----- Original Message ----- 
From: "Greg Daley" <[email-masked]>
To: "Subba Reddy" <[email-masked]>
Cc: "JinHyeock Choi" <[email-masked]>; "Brett Pentland" 
<[email-masked]>; "James Kempf" 
<[email-masked]>; "Dna" <[email-masked]>
Sent: Wednesday, July 20, 2005 10:24 AM
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s. 
Landmark Prefix

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

---

From: Greg Daley <[email-masked]>
Date: Wed, 20 Jul 2005 16:02:22 +1000

Hi Subba,

Subba Reddy wrote:
[cut]
>    link and falls back on CPL [9].
Thanks,

Greg

---

From: Greg Daley <[email-masked]>
Date: Wed, 20 Jul 2005 16:11:01 +1000

Hi Syam,

Syam Madanapalli wrote:
[cut]
> any DNA routers. I think this is also true with the Landmark

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

---

From: Sathya Narayanan <[email-masked]>
Date: Wed, 20 Jul 2005 13:45:59 -0400

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

> In the linkid, the host maintains the list of previous linkids which
> will be used
> Also linkid does not really require the synchronization all the time
> if router
> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Thu, 21 Jul 2005 14:09:39 +0900

Sathya

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

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Thu, 21 Jul 2005 14:15:10 +0900

Sathya

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

Best Regards

JinHyeock

---

From: JinHyeock Choi <[email-masked]>
Date: Thu, 21 Jul 2005 14:18:30 +0900

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

---

From: Greg Daley <[email-masked]>
Date: Thu, 21 Jul 2005 16:52:50 +1000

Hi JinHyeock,

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

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Thu, 21 Jul 2005 16:09:59 +0900

Dear Greg

> solution is comparable to the LinkID solution.

As I told to Sathya, the main difficulty for CompleteRA is to synchronize 
all the routers on the link to have the same CompleteRA all the time. 

For example, when a prefix is added, removed or prefix lifetime expires, 
the routers need to update there CompleteRA in time to advertise the 
same one. But this is hard. 

(Cut and pasting from DT ML),  

  But with packet loss and a potential for the set of routers changing, I
  don't see how we can guarantee such synchronicity.
  For a known and fixed set of routers that never fail, then a two-face
  commit protocol can ensure that they all switch in concert, but the
  protocol needs to work when routers fail as well as the set of routers
  being dynamic.

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. 

Best Regards

JinHyeock

---

From: Brett Pentland <[email-masked]>
Date: Thu, 21 Jul 2005 17:55:21 +1000

> Does this sound like the right criteria to compare

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

Brett.

---

From: Sathya Narayanan <[email-masked]>
Date: Thu, 21 Jul 2005 10:20:03 -0400

JinHyeock -

>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

---

From: Syam Madanapalli <[email-masked]>
Date: Thu, 21 Jul 2005 23:30:59 +0530

Hi Sathya,

> syntax/mechanism by which we acheive it - where we do disagree, as of now.

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

---

From: Greg Daley <[email-masked]>
Date: Fri, 22 Jul 2005 09:08:33 +1000

Hi Syam,

Syam Madanapalli wrote:
[cut]
> 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.

---

From: Greg Daley <[email-masked]>
Date: Fri, 22 Jul 2005 09:03:36 +1000

Hi Brett,

> It would be good to also consider how the schemes interact with

OK,

Greg

---

From: JinHyeock Choi <[email-masked]>
Date: Fri, 22 Jul 2005 13:14:50 +0900

Dear Greg

Kindly understand my belated and un-chronological reply.

> original prefixes are valid.   This is available in the distributed

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. 

> configured (which was my point).

I have difficulty understanding your concern.  

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Fri, 22 Jul 2005 13:55:47 +0900

Greg

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

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

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

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

> is better for the "movement to non-DNA" link case.

I may add "with added synchronization cost".  

> 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

I guess the same applies for "NO". 

"NO" will supercede a "YES", if it is received first, right? 
 
> 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

---

From: Greg Daley <[email-masked]>
Date: Fri, 22 Jul 2005 15:44:29 +1000

Hi JinHyeock,

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

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

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Fri, 22 Jul 2005 14:53:28 +0900

Dear Sathya

> So, in conclusion, the synchronization requirement and

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

---

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

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.

> (average 500ms). During which, the host will receive an RA optimized 

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.

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

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

> with mobile/cellular operators and in such a environment, FRD is generally 

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

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

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

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

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

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.

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

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

> 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

---

From: James Kempf <[email-masked]>
Date: Fri, 22 Jul 2005 00:18:36 -0700

Greg,

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

            jak

----- Original Message -----
From: "Greg Daley" <[email-masked]>
To: "JinHyeock Choi" <[email-masked]>
Cc: "Sathya Narayanan" <[email-masked]>; "Brett Pentland"
<[email-masked]>; "James Kempf"
<[email-masked]>; "Dna" <[email-masked]>
Sent: Wednesday, July 20, 2005 11:52 PM
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s.
LandmarkPrefix

---

From: Brett Pentland <[email-masked]>
Date: Fri, 22 Jul 2005 17:51:29 +1000

Hi JinHyeock,

> i.e. Prefix3 is in this link. 

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.

---

From: Subba Reddy <[email-masked]>
Date: Fri, 22 Jul 2005 13:41:25 +0530

Hi Satya,

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Fri, 22 Jul 2005 17:33:41 +0900

Greg

> that everyone can read it).

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

> affect the way prefix addition or subtraction works.

Actually the main changes results from the synchronization
difficulties. 

> Does this sound like the right criteria to compare

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. 
 
> it may be that the WG just chooses a particular

ok. 

> and may actually highlight a winner.

I think the comparison list is of help. 

> RS/RA exchange for each scheme (or set of schemes) as described

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

Best Regards

JinHyeock

---

From: JinHyeock Choi <[email-masked]>
Date: Fri, 22 Jul 2005 17:49:23 +0900

Greg 

> wish to assign the prefix elsewhere before normal

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

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

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

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

> since the rest of the CompleteRA will not match the existing

I have difficulty following the above. 

> non-movement detection, since the host recovers in milliseconds, not

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

> the appropriate RA (prefix lifetime=0).

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

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

---

From: Erik Nordmark <[email-masked]>
Date: Sun, 24 Jul 2005 12:09:05 -0700

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

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

    Erik

---

From: JinHyeock Choi <[email-masked]>
Date: Sat, 23 Jul 2005 13:12:49 +0900

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

Best Regards

JinHyeock

---

From: James Kempf <[email-masked]>
Date: Fri, 22 Jul 2005 23:54:20 -0700

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.

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

---

From: Brett Pentland <[email-masked]>
Date: Mon, 25 Jul 2005 11:57:49 +1000

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

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

---

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

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

---

From: James Kempf <[email-masked]>
Date: Fri, 22 Jul 2005 08:39:12 -0700

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

---

From: JinHyeock Choi <[email-masked]>
Date: Sat, 23 Jul 2005 12:19:16 +0900

Dear Brett

> > R1 and R2 gathers the prefixes to make the cID.

This is a lot less complicated...

Greg

---

From: JinHyeock Choi <[email-masked]>
Date: Sat, 23 Jul 2005 12:19:16 +0900

Dear Brett

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

Best Regards

JinHyeock.

omplete prefix list

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

Best Regards

JinHyeock.

---

From: James Kempf <[email-masked]>
Date: Fri, 22 Jul 2005 08:58:47 -0700

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.

            jak

----- Original Message -----
From: "JinHyeock Choi" <[email-masked]>
To: <[email-masked]>
Cc: "Syam Madanapalli" <[email-masked]>; "Brett Pentland"
<[email-masked]>; "James Kempf"
<[email-masked]>; "Dna" <[email-masked]>
Sent: Friday, July 22, 2005 1:49 AM
Subject: Re: [DNA] DNA proposal issue 19 - was [Issue X] LinkID v.s.
Landmark Prefix

---

From: JinHyeock Choi <[email-masked]>
Date: Mon, 25 Jul 2005 14:09:19 +0900

Dear Brett

> prefixes and start advertising a new set.  It's trivial to add a rule

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

> setting of timeouts on DNA information.

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

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Mon, 25 Jul 2005 14:08:39 +0900

Dear Jak

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

> 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. 
 
> potential, not whether one or the other technique has a couple fewer bytes

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?

Best Regards

JinHyeock

---

From: Brett Pentland <[email-masked]>
Date: Mon, 25 Jul 2005 16:49:09 +1000

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

I'll add this to the discussion on issue 12 which was about this point.
We had more or less decided to just describe the consequences of
flash reassignment.  It's trivial to say "don't reassign a prefix to
a new link before it's old lifetime has expired" and that solves this
problem, but maybe that's too strict a requirement (or maybe it's not).
I'm not sure how this fits in with DHCPv6 prefix delegation, for
example.  It sounds like this needs further investigation.

Brett.

---

From: JinHyeock Choi <[email-masked]>
Date: Mon, 25 Jul 2005 16:54:21 +0900

Dear Erik

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

> 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

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

---

From: Brett Pentland <[email-masked]>
Date: Mon, 25 Jul 2005 18:18:03 +1000

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

---

From: Syam Madanapalli <[email-masked]>
Date: Mon, 25 Jul 2005 14:34:05 +0530

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

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.

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

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

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 25 Jul 2005 03:51:00 -0700

> 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

---

From: Brett Pentland <[email-masked]>
Date: Tue, 26 Jul 2005 11:26:11 +1000

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

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.

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

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

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 25 Jul 2005 04:56:24 -0700

> 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

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 25 Jul 2005 19:10:25 -0700

> We can't avoid a temporary flapping for the related set, the set of

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.

> won't give incorrect information about a link change, even under

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.

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

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

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 26 Jul 2005 11:44:28 +0900

Dear Erik

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

Best Regards

JinHyeock

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 25 Jul 2005 19:51:12 -0700

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

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 26 Jul 2005 12:04:24 +0900

Erik

> incorrectly assume a link change (after all, all the addresses need to

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

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. 

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

Best Regards

JinHyeock

---

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

> a pathological case with a problem. 

Can you provide an example?

> 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

---

From: Syam Madanapalli <[email-masked]>
Date: Tue, 26 Jul 2005 09:45:34 +0530

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.
>
> incorrectly assume a link change (after all, all the addresses need to be 
> reconfigured, etc).
>
>> R announces it by sending an RA but H doesn't receive it. Then next time 
>> H receives CompleteRA with

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

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 26 Jul 2005 13:22:11 +0900

Erik

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

ok. 

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

Best Regards

JinHyeock

---

From: Syam Madanapalli <[email-masked]>
Date: Tue, 26 Jul 2005 09:56:37 +0530

Hi Brett,

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

> When we wrote the proposal, we felt that we needed something more.

I think 12 seconds is very small considering mobility  :)

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

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 26 Jul 2005 13:53:01 +0900

Erik

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

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

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

> is claiming that some other prefix is the linkID. That's some added

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. 

> don't belong together in the same sentence. :-)

ok and agree. :-)

Best Regards

JinHyeock

---

From: Brett Pentland <[email-masked]>
Date: Tue, 26 Jul 2005 14:56:42 +1000

Hi JinHyeock,

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

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

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 26 Jul 2005 14:25:43 +0900

Dear Brett

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

>    (I think we need text to clear that up)

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

>    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

---

From: JinHyeock Choi <[email-masked]>
Date: Tue, 26 Jul 2005 14:37:02 +0900

Brett

> I think you might have found one :)  

Thanks for your kind words. :-)

> Actually, there was some

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

> would be made.  

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

Best Regards

JinHyeock

---

From: Ranjitsinh Wable <[email-masked]>
Date: Tue, 26 Jul 2005 11:03:16 +0530

Hi Brett,

----- Original Message ----- 
From: "Brett Pentland" <[email-masked]>
To: "JinHyeock Choi" <[email-masked]>
Cc: "Erik Nordmark" <[email-masked]>; "Syam Madanapalli" 
<[email-masked]>; <[email-masked]>; "James Kempf" 
<[email-masked]>; "Dna" <[email-masked]>
Sent: Tuesday, July 26, 2005 10:26 AM
Subject: Re: [DNA] [Issue X] LinkID v.s. Landmark Prefix

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

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

---

From: Brett Pentland <[email-masked]>
Date: Tue, 26 Jul 2005 16:00:14 +1000

Hi Syam,

>>>>> schemes such as "Linkid Prefix List" or "Old linkid advertising 
>>>>> rule" to all
>>>>> prefixes because we
>>> from Router (R1) because the deletion of the prefix (P1) at R1 might 
>>> not have

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.

---

From: Brett Pentland <[email-masked]>
Date: Tue, 26 Jul 2005 16:07:48 +1000

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

See my answer to Syam.

Yes.

> help to write those down lest there should be unnecessary confusion. 

OK.

Brett.

---

From: Syam Madanapalli <[email-masked]>
Date: Tue, 26 Jul 2005 11:50:12 +0530

Hi Brett,

[cut]

> 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

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 26 Jul 2005 05:55:49 -0700

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

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

> (So in effect, "known prefix" would overrule "NO".)

I think that makes sense.

> themselves. You recommended this approach. 

Blush :-)

    Erik

---

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

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

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Wed, 27 Jul 2005 16:42:47 +0900

Dear Erik

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

> 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

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. 

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

> 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

---

From: James Kempf <[email-masked]>
Date: Tue, 26 Jul 2005 12:12:40 -0700

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

---

From: JinHyeock Choi <[email-masked]>
Date: Thu, 28 Jul 2005 00:15:46 +0900

Erik

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

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

Best Regards

JinHyeock

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 28 Jul 2005 08:42:44 -0700

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

> DNA solution can deal with LOS, I think it can deal with flapping 

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.

> criteria, so needs to be reflected in the Landmark/ CompleteRA draft. 

Agreed.

    Erik

---

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

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

> 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

---

From: JinHyeock Choi <[email-masked]>
Date: Sat, 30 Jul 2005 05:21:12 +0900

Erik 

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

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

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

---

From: JinHyeock Choi <[email-masked]>
Date: Sat, 30 Jul 2005 05:20:56 +0900

Dear Erik

> updated the prefix list first (or whether they did it at exactly the

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. 

> 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

---

From: Erik Nordmark <[email-masked]>
Date: Sat, 30 Jul 2005 09:55:32 -0700

ok

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

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