Subject: RE: Summary Re: [nemo] comments on "Tree Discovery" draft

From: "Pascal Thubert \(pthubert\)" <[email-masked]>
Date: Fri, 27 Aug 2004 18:16:53 +0200

> >> First, where does the MR CoA come from?  It's not in the TIO.  It's
> >>  not in the src field of the RA.  The TreeID is the Home Address
> >> initially, not the CoA.
> >
> > A MR is expected to know it's CoA.
> 
> Yeah, once it's formed based on information from the same RA (prefix).
> 
> I really don't get it.

Seems not. I'll have to be more verbose for version 01. 

> 
> Whenever an MR receives a TIO that has a PathDigest different than the
> TIO it received previously it looks at the previously received
> PathDigest from the same router ll address and finds different.  No
need
> to compute its own PathDigest based on the newly-received PathDigest
to
> realize that.

MR receives digest in RA-TIO from AR over egress and saves it. MR
computes newdigest =  CRC32(digest, CoA) and puts that in the RA-TIO it
sends over ingress. 

Next time MR gets RA-TIO, it compares the consecutive digest and if they
are different, something changed in the chain of MRs to the outside.

The computation of CRC is not done for itself but for the guys below so
that the digest has all the CoAs within it. I hope you understand that,
or someone else has to try using different words.

> 
> Thus, it is sufficient that every MR that establishes for itself a new
> dfeault route will set the "has changed" bit in its TIO's and MR's
below
> to retransmit this bit and everybody notices something has changed, no
> need for digests and checksums.  As simple as that.  Why wouldn't it
work.
> 
> > The tree ID is an ID of the root-MR file the CareOf is that of the
MR
> >  that propagates the TIO.
> >
> >> Second, does CRC-32c algorithm guarantee a unique output for a
> >> unique set of Care-of Addresses?  Not even MD5 does.  This is not
> >> efficient.
> >
> > Its' a hint, but the chances of being wrong are
> > veeeeeeeeeeeerrrrrrrrrrryyyyy low.
> 
> Depends what you call ve12r11y5 low.  An intermediate MR may wish to
> fool the MR's below and tell them that nothing has changed.  Hence TD
> has security issues.
> 
> > It may be used for various purposes such as tree movement detection,
> > multihop RH type2 validation etc.
> 
> Wasn't RH type 2 reserved for BU's and such?  What's multihop RH type
2?
> 
> >> Third, if one wants to say that something has changed why not
> >> simply sending a bit in the TIO that says "something has changed".
> >>  This is less expensive than computing CRC's...
> >
> > Could work in a P2P environment. But... for a MR for force the bit
> > you propose in its RA-TIO, it must know what was in the last RA that
> >  a VMR received.
> 
> Yep, it must know the prefix in the received RA and the ll address of
> the router who sent it.  Both are present.
> 
> > That may depend on the MR, so either VMRs may miss changes or they
> > may see it twice or something.
> 
> A TD MR is not an MR, it's just a TD MR.
> 
> > So it can not be done that way. Each MR has to maintain its own
state
> >  for what it saw last time. Also, the CRC computation is not that
> > complex. It's done on 2*Ipv6 addresses so it compares with the
> > validation on an IPv4 header.
> 
> The TD MR's CRC computation is something that should be done _in
> addition_ to the ICMP checksum; the CRC is more expensive than just a
> comparison to the previous values (by all accounts).  Thus the more
> efficient solution is the bit solution.  Could you modify the draft
> accordingly please?

I explained it does not work. Try again: the fact that something changed
is not from the view of the emitter but from the different viewpoints of
all the receivers. If a MR sets a bit in TIO saying there's a change,
and one of 10 visitors misses the RA. Should the sending MR repeat the
bit next time? 

Pascal

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 27 Aug 2004 18:50:18 +0200

> Seems not. I'll have to be more verbose for version 01.

I don't think being more verbose helps.  I think that helping to define
a problem before offering a solution may help.

>> addition_ to the ICMP checksum; the CRC is more expensive than just
>>  a comparison to the previous values (by all accounts).  Thus the 
>> more efficient solution is the bit solution.  Could you modify the 
>> draft accordingly please?
> 
> I explained it does not work. Try again: the fact that something 
> changed is not from the view of the emitter but from the different 
> viewpoints of all the receivers. If a MR sets a bit in TIO saying 
> there's a change, and one of 10 visitors misses the RA. Should the 
> sending MR repeat the bit next time?

See it the other way around.  If a receiving MR misses any one RA TIO in
any order of RA TIOs, it has no way of being sure of a path being
changed or not at any point in time.

If the logic of "path has changed" works with CRC's it also works with
1-bit only, that's a fact.

By the current draft, the receiving MR hasn't all the information to
compute a correct CRC, it just looks at whether it changed or not.  This
is against the fundamentals of using a CRC.  A CRC is computed on some
received data to see it fits the CRC-field it actually receives (the
intelligent stuff actually compares to 0).  This gives a hint, as you
say, to whether the received data is corrupted or not.

In fact, what do you assume "CRC-32c" to be more exactly, if I'm not too
ignorant.  I'd suppose it to be "Cyclic Redundancy Check (CRC) codes
[Peterson] are shortened cyclic codes used for error detection."  But
what is the "32c" part?  Two's complement or something on 32bit?  Which
CRC code more exactly?

Note CRC's are for checking message integrity for error correction not
for checking a path has changed.

Note "Digest" in "PathDigest" invites to think of message digest (like
in "MD5"); digests are also used to check for integrity, but not for
"path has changed".

I doubt that combining "Digest" with "CRC" makes a good tool for "path
has changed".

For "path has changed" I'd use 1 bit.

I doubt there's any need for transmitting information of paths being
changed.  This is usually done different.  Receive new path, internally
compute new better destinations, and so on.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 27 Aug 2004 18:57:01 +0200

Pascal Thubert (pthubert) wrote:
> computes newdigest =  CRC32(digest, CoA) and puts that in the RA-TIO
>  it sends over ingress.
> 
> Next time MR gets RA-TIO, it compares the consecutive digest and if 
> they are different, something changed in the chain of MRs to the 
> outside.
> 
> The computation of CRC is not done for itself but for the guys below
>  so that the digest has all the CoAs within it. I hope you understand
>  that, or someone else has to try using different words.

Ok, how about this substitution of "bit" for "CRC":

  MR receives bit in RA-TIO from AR over egress and saves it.  MR
  computes new bit = not-bit and puts that in the RA-TIO it sends over
  ingress.

  Next time MR gets RA-TIO it compares the consecutive bits and if they
  are different, something has changed in the chain of MR's to the
  outside.

  The computation of the bit is not done for itself but for the guys
  below so that the bit has all the previous MR's bits within it.

I think it can work with one-bit only, no?

Alex