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

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

Hi Subba,

I think we've got one issue left.

[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).

Currently it is O(p_r), I think.  The difference is very small,
considering the number of advertised prefixes in any RA will be low.

Greg