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

[Subba Reddy <subbareddy@samsung.com>]

Hi Greg,

> I think we've got one issue left.

Yes.

>
> [cut]
> >>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.
> >>
> >
> >
> > 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.
>
> RFC 2461 doesn't place any ordering requirements on options in transmitted
> RAs.  This is deliberately stated in that document.  I'm not sure
> existing implementations would necessarily be well served in requiring
> such ordering.
>
> Additionally, the existing LinkID draft doesn't have this assumption.
> So if an issue is adopted for LinkID, and there's agreement that this
> transmission is required, it will be O(1).

I agree with your point that there is no ordering requirements for options.
I feel it as more implementation specific. I think, optimistic way is
considered
in the analysis (like hash list for DNAPrefixList, one LinkID in the
LinkIDPrefixList).
Please correct me, if wrong.

So, it may be better to consider this also in the similar way.

>
> Currently it is O(p_r), I think.

Yes.

> The difference is very small,
> considering the number of advertised prefixes in any RA will be low.
>

Difference is small, but when we consider the complexity analysis, we feel
like
there is a difference between constant time and linear time.

Thanks & Regards,
Subba Reddy