Subject: Re: [DNA] Re: LinkID v.s. Landmark Prefix

From: Greg Daley <[email-masked]>
Date: Thu, 28 Jul 2005 12:03:41 +1000

Hi JinHyeock, 

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

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

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

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

A Host H, exists and moves around the Internet.

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

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

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

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

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

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

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

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

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

A Host H,  exists and moves around the Internet.

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

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

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

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

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

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

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

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

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

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

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

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

A Host H, exists and moves around the Internet.

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

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

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

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

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

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

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

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

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

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

----

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

Greg

---

From: Brett Pentland <[email-masked]>
Date: Thu, 28 Jul 2005 12:38:08 +1000

> Prefix Landmarks

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

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

Brett.

---

From: Subba Reddy <[email-masked]>
Date: Thu, 28 Jul 2005 09:54:01 +0530

Hi Greg,

<cut>

> Link Identifiers

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

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

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

Thanks & Regards,
Subba Reddy