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

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

> >> Still, TreeDepth value on 8bit only?  Does this mean that only
> > 255levels of aggregation can be made?  This is not scalable.
> >
> > It means that you can not be deeper than 255 hops from the AR.
Enough
> >  considering TTL.
> 
> I see no relation between TTL and TreeDepth.  A moving network may
offer
> an AR that is not its MR, the moving network may introduce more hops
> within itself.  Do you have a form of AR-to-MR communication (AR and
MR
> of same moving network) such as to propagate consistently that TIO
> modifications.

A tree depth of 200 means 200 MRs to go through to get to the AR. A
default TTL of 64 will be dropped in the middle of such a tree.

By current standards, a depth of 200 is insane. We currently have a MAX
of 10. That's already 10 radio hops. Quite a radius. 

The AR question is a good one. We discussed that with Marcello on the
thread. There are option and I'd appreciate recommendations from the ML.
One option is for Mobile AR to propagate TIO and not to use legacy MAR
which could not do it.
 
> >> Why adding a CRC?  Why not a checksum with a virtual header, the
> > classic stuff?  Why is CRC needed?  Remark RA already has a checksum
> >> covering all RA options... This is not efficient.
> >>
> > That CRC is not there to validate the packet. It is the checksum of
> > the careofs to the outside. It is used to detect if the path to the
> > outside has changed.
> 
> Where does the draft say so?

PathDigest
    32-bit unsigned integer CRC, updated by each MR. This is the result
of a CRC-32c computation on a bit string obtained by appending the
received value and the MR Care of Address. Clusterheads use a 'previous
value' of zeroes to initially set the PathDigest

> 
> 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. 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. It may be used for various purposes
such as tree movement detection, multihop RH type2 validation etc. 

> 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. That may depend on the MR, so either VMRs may miss changes or
they may see it twice or something. 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. 

Pascal

---

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

Pascal Thubert (pthubert) wrote:
> By current standards, a depth of 200 is insane.

I was thinking you were looking at traffic jams, those may have more
than just 10 vehicles...

>  thread. There are option and I'd appreciate recommendations from the
>  ML. One option is for Mobile AR to propagate TIO and not to use 
> legacy MAR which could not do it.

When was the last time we discussed NEMO-related communication between
entities in a moving network and its MR, such to delegate security
powers and stuff...

>>> That CRC is not there to validate the packet. It is the checksum
>>>  of the careofs to the outside. It is used to detect if the path
>>>  to the outside has changed.
>> 
> PathDigest 32-bit unsigned integer CRC, updated by each MR. This is 
> the result of a CRC-32c computation on a bit string obtained by 
> appending the received value and the MR Care of Address. Clusterheads
>  use a 'previous value' of zeroes to initially set the PathDigest
> 
>>  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.

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.

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

Alex

---

From: Carlos Jesús Bernardos Cano <[email-masked]>
Date: Fri, 27 Aug 2004 19:21:19 +0200

Hi Pascal,

> One option is for Mobile AR to propagate TIO and not to use legacy MAR

	I agree with Marcelo and Alex, that the AR issue is important an that
we, IMHO, should look for options in order to not impose restrictions to
TD to work. I agree that there are several options. Actually, we thought
about some ones. If you are interested, we can discuss it.

	Kind regards,

	Carlos J.

(suppressed text)

-- 
Carlos Jesús Bernardos Cano - http://www.it.uc3m.es/cjbc/
GPG FP: 58C3 4227 AF8D 01D4 5A09  A617 E6F2 B23E DAD6 AA40

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 27 Aug 2004 19:58:07 +0200

Pascal Thubert (pthubert) wrote:
> a VMR received. That may depend on the MR, so either VMRs may miss 
> changes or they may see it twice or something. 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.

>>>>> Why adding a CRC?  Why not a checksum with a virtual header, 
>>>>> the classic stuff?  Why is CRC needed?  Remark RA already has
>>>>>  a checksum covering all RA options... This is not efficient.
>>>>> 
>>>> 
>>>>> That CRC is not there to validate the packet. It is the 
>>>>> checksum of the careofs to the outside. It is used to detect 
>>>>> if the path to the outside has changed.
>>> 

Pascal, let me bring more on the "something has changed" indicator.
You're basically proposing hashing some addresses and propagating the
result in TIO's down.  I've proposed using a single bit inverted by each
entity.

Imagine a sequence of routers: TLMR-MR1-M2-MR3.

The latter proposal has the inconvenient that if MR1 and MR2 disappear
at the same time, then MR3 will not notice (twice inverting is no
inverting).

But the former proposal has the inconvenient that if MR2 disappears and
a new MR4 takes its place immediately after, the PathDigest will change
inevitably (due to MAC addresses being unique) and so MR3 will see a
change in path when there is actually none (in terms of number of hops:
one MR replaced another).

So here we're with two proposals, none actually being able to reliably
signal to MR3 that something has changed.

To me this is a typical example of a solution that may work in a context
that one may imagine (I imagined that only unit changes need to be
indicated) but immediately after someone can build a physical movement
scenario that can not work.

(Maybe a total proposal is to actually distribute all lists of
  neighbours to everybody at every change, ressembling to multicast
  distribution of LS protocols.  And this has been looked into by many
  routing protocols...)

IMHO one can not ask the WG "are you interested in TD"; or maybe it's
only me, but I'm not interested in TD.  Maybe "are you interested in a
problem whose TD may be a solution".  So let's see the problem.  Looping
is not.

Alex