Re: [DNA] Info: Computation Time/Space requirements for LinkIdentification schemes

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

Hi Subba,

I think we're oscillating towards resolution.

----- Original Message ----- 
> > > >
> > > > RA Build time: O(1) selection of LinkID and Old LinkID
> > > >
> > > >
> > > > RA Processing: O(p_r) comparison of each prefix with LinkID
> > > >
> > >
> > > I think, this is O(1) because, only linkID in the RA needs to be
> > > comparedwith the LinkID at the host.
> 
> From Section 4.2 (4th paragraph) of the LinkID draft(00/01)
> 
> "
>   When a host with a linkid prefix receives an RA, whether 
>   solicited or unsolicited, that includes a prefix with
>   I-bit set, the host compares its LinkidPrefixList with the
>   set of prefixes in the RA.
> "
> 
> Host compares, its LinkID (stored in LinkIDPrefixList) with the 
LinkID
> advertised in RA (i.e, the prefix with I bit set. This prefix can be
> learned prefix or router's own prefix).
> So, only one comarision is required if the LinkIDPrefixList 
> consists of only one prefix (Most of the time LinkIDPrefixList
> consists of only one prefix).
> 
> So, I think it is O(1).

OK. I get your point.

Thinking about it another way though, each PIO and LPIO has to be
checked for the LinkID flag, and then that LinkID has to be compared
with the stored LinkID.

> >
> > No actually, the learned component of the RA isn't inspected,
> > for robustness sake (described in the draft: Syam or JinHyeock may
> > also correct me on this).  This means all the PIOs need to be 
> checked.>
> 
> Routers will not consider the learned prefixes for the robustness 
> sake, but not the hosts.
> 
> From Section 3.2 (4th paragraph) of the LinkID draft(01),
> 
> "
>   From the received RAs, the router extracts only the valid 
>   prefixes in PIO and generate the "learned prefix list
>   (LearnedPrefixList).
> "
>
>
> From Section 3.2 (last paragraph) of the LinkID draft(01),
> 
> "
>   Take notice that, for prefix list generation, a router only 
>   takes the prefixes in PIO into consideratoin.
> "

Thanks for the references. I'll check this out further.

> >
> > [cut]
> > > >
> > > > Prefix LinkID **** (Proposed Scheme  -- see below for CPL):
> > > > -------------------------------------
> > > > Storage: O(1) Prefix LinkID (minimum)
> > > >          O(N) set of linkIDs received recently on different IP
> > > links.>
> > >
> > > I think, here N is the number of different LinkIDs (if at all)
> > > advertised in the last 1.5hrs on the link.
> >
> >
> > Actually, I think this is the number of prefixes known on the
> > host:
> >
> 
> Most of the time LinkIDPrefixList consists of only one prefix i.e, 
> LinkID.If LinkID of the link changes, because of addition/deletion 
> of prefixes, then LinkIDPrefixList can contain more than 1 prefix.

OK this is worth noting in the assumptions.


> > From section 1.3:
> >
> > Paragraph4:
> > "...the hosts track the list of linkid prefixes they've
> >    received in the last 1.5 hours to generate "the linkid prefix 
> list>    (LinkidPrefixList)".
> >
> > Perhaps, there is confusion, because in most cases, the
> > LinkIDPrefixList
> > is cleared out by the host each time it moves link
> >
> > Is this the current thinking?
> 
> True. If a host changes its link, it will clear the LinkIDPrefixList.
> 
> >
> > In that case, then the maximum size is P, but the mean size
> > is much lower (typically 1).
> 
> True. I also think O(1) is fine.

OK, I'll mention O(1), but also note the assumption as described above.

Greg