Subject: Re: [DNA] Info: Computation Time/Space requirements for Link Identification schemes

From: Greg Daley <[email-masked]>
Date: Sun, 31 Jul 2005 23:38:12 +1000

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

---

From: Subba Reddy <[email-masked]>
Date: Mon, 01 Aug 2005 09:06:25 +0530

Hi Greg,

> I think we're oscillating towards resolution.

True.

> checked for the LinkID flag, and then that LinkID has to be compared

If the first prefix in the RA is LinkID prefix (if any), then only one
comparision is enough.
I feel, routers can maintain the LinkID prefix as the first prefix, in their
prefix list.
Because of this, routers can easily check (with O(1) complexity) the
validity of LinkID
at various point of times (like prefix life time changes, new prefix is
added, LinkID prefix
is a learned prefix and it has not been advertised in the last 1.5hrs). So,
routers can easily
include LinkID prefix as the first prefix in the RA. Also, maintaining the
LinkID prefix as the first
entry in the prefix list will not add any additional complexity (It is
constant O(1)).

Though, whatever I have mentioned is more implementation specific, IMHO O(1)
is fine.

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

OK.

> Greg

Thanks & Regards,
Subba Reddy