Re: [DNA] Quick review of draft-jinchoi-dna-cpl-00.txt

[Greg Daley <greg.daley@eng.monash.edu.au>]

Hi JinHyeock,

JinHyeock Choi wrote:
> Dear Greg
> 
> Kindly fine my in line comments. 
> 
> [omitted]
> 
>>I think this is important to work through,
>>so please don't be offended if I speak plainly.
> 
> 
> Don't worry about it. It's my policy not to be offended by honest 
> and correct feedbacks. (This doesn't mean they don't hurt. :-))
> 
> Also I make the same request. I wish we disagree in an agreeable 
> way like gentlemen. :-)

Indeed :)

> [omitted]
> 
>>>In this case, a host waits additional RAs
>>>NOT to detect a link change when it actually moves to a new link
>>>BUT to prevent itself from falsely assuming a link change while it
>>>remains at the same link.
>>
>>I think it needs to be made clear that the reception of a
>>RA containing a prefix already in the list confirms that the
>>node is on the same link without waiting.
>>
>>As described below, when we've got a prefix list which we estimate
>>as complete, we should just use it, since we're sure to within
>>a small portion of a percent that we've seen router advertisements
>>from each router.
>>
>>The cost of waiting is too great in the case we've moved
>>(which is more likely than having missed a router's prefixes in
>>a CPL) to worry about whether or not we received hints.
> 
> 
> ok. Let me clarify it. 
> 
> While a host performs DNA procedure, if it receives a prefix in the 
> existing prefix list, that confirms that it still remains at the same link.  

OK.  Sorry it took a few rounds for me to understad that.
I'm currently removing the wood shavings from my head.

> 
>>> > second paragraph:
>>> >
>>> > "prefix list is complete if all the prefixes belong to it"
>>> > Could we add 'on-link' before prefixes?
>>> 
>>>No. We will also consider the prefixes whose on-link bit is not set. 
>>
>>The on-link prefixes are all the prefixes on the link,
>>not just those where all neighbours are on link (on-link flag set).
> 
> 
> Hmmm. Is this the official & widely accepted definition of on-link prefix? 
> I am afraid we encountered an another terminology ambiguity. Erik wrote 
> the following phrases and he is a co-author of RFC 2461. 
> 
>                                            this specification uses
>    both 'on-link' and 'addrconf' prefixes [4], that is, prefixes that
>    have either the 'on-link' flag set, the 'autonomous
>    address-autoconfiguration' flag set, or both flags set.  

Indeed, I was being loose with my terms.
Sorry again.

> 
>>Perhaps we need to say:
>>
>>"prefix list is complete if all prefixes on the link belong to it"
> 
> 
> ok. I agree that is more clear. 
>  
>
>>> > (3.1)
>>> >
>>> > Paragraph 4:
>>> >
>>> > The behaviour of sending all prefixes in solicited RAs is defined
>>> > in RFC2461, and is a SHOULD.
>>> > 'every router ... would receive the RS and reply with all the prefixes'
>>> > Is therefore not entirely correct, since routers may choose not
>>> > to send all prefixes.  changing 'would' to 'should' is better.
>>> > The second paragraph should therefore cite RFC 2461.
>>> >
>>> > If the citation is there, you could even say 'SHOULD'.
>>> 
>>>Hmmm. I tried to describe the way that routers generally operate.
>>>No mandating was intended.
>>>
>>
>>Well, the text is then wrong, since that's not how routers
>>work.
>>
>>It's how they should work, which is different.
> 
> 
> Kindly take notice of the word 'GENERALLY'. I think that's how 
> routers generally work, even though not always. Also even it is 
> 'SHOULD' instead of 'MUST', I can't imagine a case that a router 
> would send only a partial list of prefixes.  
> 
> But if that makes you still uncomfortable, I will change the above with 
> 'every router ... would receive the RS and USUALLY reply with all the
> prefixes'. I wish you think that this is rigorous enough. (You don't seem 
> like a person who is not afraid to be less rigourous. :-))
> 

I think this is rigourous enough.

You're right, I think in some cases it's OK
to be less rigourous ...

>>> > Paragraph 7
>>> >
>>> > The description of collection of additional groups of RA's from
>>> > a subsequent RS tends to give the idea that the RA sets are
>>> > compared after the end of a 4 second RS interval.
>>> 
>>>It is the unintended impression. I tried to describe the end result,
>>>the union of all prefix sets, not how the end result is achieved.
>>
>>Indeed, although we're able to recommend a process
>>to achieve a goal, since host performance is based on this.
> 
> 
> ok. 
>  
> [omitted]
> 
>>> > (3rd and second last paragraphs).
>>> >
>>> > Are we still talking about rapid movement?
>>> >
>>> > If we have a good prefix list which doesn't contain
>>> > superfluous prefixes, no link-up hint is required
>>> > to determine link change (since the newly received RA
>>> > comes from a different router/has no prefixes in common).
>>> 
>>>This is about how to prevent superfluous prefix list. Without link-up
>>>hint, it's difficult for a host to keep its prefix list including a 
>>>false prefix.
>>
>>Actually, it's not, as described below.
> 
> 
> Sorry I found typo errors. What I tried to say is 
> 
> Without a link-up hint, it's difficult for a host to keep its prefix list 
> from including a false prefix list with certainty. 
> 
> Do you disagree with that? 

Indeed I do.

I think that the same mechanism which is used to provide a
complete prefix list (namely RS) can be used to gather the list.

If we have RAs arriving in response to the RS, we know
that the probability of not hearing from a router which is
on-link (assuming independent losses in this case) is about:

p_loss ^ (N_goodrs).

The good rs in this case is an RS which is known to have
been received by at least one router.

If we solicit when we receive an RA from an unknown router,
but do not merge the unknown routers prefixes into the existing
prefix list, we can generate a new prefix list which contains 
(potentially) a separate set of prefixes.
If there were multiple routers providing the prefix list,
then they will respond within the RS retransmission period if
they hear RSs.

For M routers forming the contributing to the existing prefix
list, the chance that we will not hear their RA responses
is:

p_loss ^ (M*N_goodrs).

Which should be a fairly low number for M>1.
(so the chance that we'll leave out someone who belongs in
the set is low).

If any of the routers advertise a prefix from the list, then
we know that they are present from the link and are added
into the new set.
Set mergers will have to be done only with caution,
since otherwise, we'll get incorrect old routers popping into
the sets if we just merge blindly.

If we start this operation each time there is a new prefix
on the link, then we'll only keep the old prefix list entries
when they respond to the router advertisements.

If we have new prefixes coming in, we can actually keep
them in new lists (separate) each time, until we've had
a time overlap between RA reception of one prefix and an
older prefix.  Then we add them into the sets.

for example (and sorry about the ascii art):
Time
----------->

----P1---------------------P1-------------------------------------->
(P1 in set1)
-------------P2------------|--P2----------------------------------->
           (P2 in set2)  (P1,P2 in set2)

--------------------------------P3------P3-------------P3--------->
                              (P3 in set3)

---------------------------------------------P4---------|---P4----->
                                          (P4 in set4)  (P3,P4 in set4)

This only has a chance of building state if we transition
before the link change has occurred.

If we move to another link, then the last routers which
were in a set drop out.


> 
>>> > Since we cannot immediately identify if link change has occurred
>>> > after sending an RS (no llink-up hint), subsequent (n*RS)
>>> > retransmission can be used to can be used to identify if a
>>> > router is really part of the set (since if a router doesn't
>>> > respond the second and third time it may be on the old link).
>>> > If we're not sure, exclude them, and don't treat the prefix list
>>> > as complete.
>>> >
>>> > It makes sense to exclude routers from the list we're not sure about,
>>> > at the cost potential false positive attachment detection events,
>>> > since the cost is so much lower than the situation where we have a
>>> > false negative.
>>> 
>>>The above is not clear to me. The prefix list doesn't contain a router
>>>(address, I guess.) at all.
>>
>>We need to keep separate lists until we can determine if the lists
>>belong to the same link.
>>
>>Otherwise we'll get highly undesirable fake entries in the list.
>>
>>This doesn't preclude collecting the information without L2 Hints,
>>and just reconciling them after attempting to build a new prefix list.
> 
> 
> Kindly elaborate how a host can divide the collected prefixes into separate lists. 
> In other words, how a host can keep separate prefix lists such that each prefix 
> list contains only the prefixes on the same link? With what criterion a host can 
> classify prefixes?  
> 
> It takes time to collect the prefixes on the link. A host can't collect all 
> the prefixes instantly. So before the host completes the collecting process, 
> if it happens that it moves to a new link without its knowledge, and, it 
> will generate the prefix list containing the prefixes from two different links. 
>  
> 
>>I'm loathe to mandate requiring Link-layer hints to provide
>>basic DNA function.
> 
> 
> What do you mean by basic DNA function? BCP or Solution/ Extension 
> or others?
> 
> For me, it's ok to recommend link-layer hints to provide efficient 
> DNA schemes. 
> 

BCP is what I'm aiming at: no new bits on wire, widely accepted to
be applicable and useful.

>>> > (3.2)
>>> >
>>> > I think there's too much caution here regarding the identity
>>> > of a link when we have a CPL.
>>> >
>>> > If we're fairly sure (99.97% from section 4) that we know all
>>> > the prefixes on a link, reception of any single RA which
>>> > doesn't contain any prefixes in the CPL confirms movement
>>> > (except in about 00.03% of the cases)
>>> >
>>> > We shouldn't wait around sending out RS's and RAs unless
>>> > we need further information from this router.
>>> >
>>> > This is the case even if there is no link-up trigger
>>> > (although as mentioned in 3.1, building this list may
>>> > be more difficult if multicast RA is used).
>>> >
>>> > So long as we're fairly confident that we have a CPL,
>>> > we should accept the false positive as an attachment detection
>>> > event, because waiting 4 seconds to check takes too long, and
>>> > the cost of false positive is lower.
>>> 
>>>Right. When hosts can be sure of the completeness of the prefix list,
>>>it can base DNA decision on a single RA. The choice is theirs.
>>
>>Indeed.
>>
>>The draft should say so explicitly.
> 
> 
> Actually it does. Kindly look at the end of Sec 3. 
> 
>    In summary, first a host makes the complete prefix list.  When a hint
>    occurs, if the host decides that the prefix list is complete, it will
>    check for link change with just one RA (with a prefix).  Otherwise,
>    in case that the host can't be so sure, it will perform additional
>    RS/ RA exchanges to corroborate the decision.
> 
>    [omitted]
> 
>    In this way, we may provide a fast and robust solution.  If a host
>    can make the complete prefix list with certainty, it can check for
>    link change fast.  Otherwise, it can fall back on a slow but robust
>    scheme.  It is up to the host to decide which scheme to use.
> 
> [omitted] 

The problem is that the hint is required.

>>>Renumbering is a problem when a router starts advertising a new prefix
>>>that may cause hosts to falsely assume a link change. The paragraphs are
>>>about this problem. 
>>
>>Renumbering isn't a problem, since the old prefix will be advertised for
>>a period with 0 lifetime.
>>
>>These prefixes can't be assigned to another link in the mean time,
>>and so don't cause any harm.
>>
>>It is simple enough to change the CPL when the prefixes are
>>retracted.
> 
> 
> Renumbering is a problem when a router starts advertising a new prefix, 
> not when the old prefixes are retracted. 

It's not a problem, since it should be merged into the prefix list.
Routers going up and down is more likely than renumbering. They
should be merged (at an appropriate time) into the prefix list too.

Perhaps we are talking at cross purposes again.

We may need to chat about it in SanDiego, to get at the reasons
for this.

Renumbering isn't really the biggest priority for me, but there's
not much text to work through and understand (or change) that
we need to get bogged down in it.

[cut]
> 
>>
>>I believe CPL should provide a 'good enough' solution which
>>reduces the number of spurious handovers, and provides fast
>>link change detection.
>>
>>I think ensuring that prefix list state is complete (as opposed
>>to estimated as roughly complete) is actually damaging because
>>of the  duration and signalling required to ensure the completeness.
> 
> 
> I agree that it would be the solution work to enhance CPL to design 
> a way to efficiently generate the complete prefix list with certainty. 
> 
> Thanks for your detailed comments that make the draft more clear. 

That's OK.

I'm really interested in the draft.

Greg